Fundamentals of Cryptography

Cryptography is the cornerstone of secure digital communication and data storage, providing essential protections like confidentiality, integrity, and authenticity. Understanding the fundamentals of cryptography is crucial for anyone studying computer science, cybersecurity, or related fields. This guide breaks down key cryptographic concepts, from symmetric and asymmetric encryption to hash functions and digital signatures, offering a clear summary for students.

Unpacking the Fundamentals of Cryptography

At its core, cryptography involves transforming information to make it secure and resistant to unauthorized access. This section explores the basic properties and principles that underpin all cryptographic systems.

Core Properties and Definitions in Cryptography

To begin, let's define some critical terms that are fundamental to understanding cryptography:

• Confidentiality: Ensures that non-public information remains accessible only to authorized parties. It's about keeping secrets secret.
• Data Integrity: Guarantees that data remains unaltered, except by authorized parties. It ensures the data hasn't been tampered with.
• Data Authentication: Provides assurance that data is genuine in its appearance or context. It verifies the origin and content are as asserted.
• Entity Authentication: Confirms the identity of a principal involved in a transaction. It proves who someone is.
• Non-repudiation of Origin: Offers strong evidence of unique origination, preventing a sender from falsely denying they sent a message. This is a powerful concept not easily achieved with simple symmetric methods.

Kerckhoffs' Principle: The Foundation of Cryptographic Design

A fundamental principle in cryptography is Kerckhoffs' Principle, which states that a system's security should not rely upon the secrecy of its design details. In other words, the security of a cryptosystem should depend solely on the secrecy of the key, not on the algorithm itself. Claude Shannon later rephrased this as "the enemy knows the system." This principle ensures that even if an adversary knows the algorithm, they cannot break the system without the secret key. If secrets were hardcoded into the system, replacing them if compromised would be a monumental task.

Message Authentication Codes (MACs)

Message Authentication Codes (MACs) are cryptographic mechanisms used to ensure the integrity and authenticity of a message. They rely on a shared secret key between the sender and receiver.

How MACs Work

A MAC generates a small, fixed-size tag that is appended to the protected data. Both sender and receiver use the same shared key to compute and verify this tag. If the computed tag matches the received tag, the data is considered authentic and untampered.

There are two primary approaches to computing MACs:

• CBC-MAC: This method utilizes a block cipher in CBC (Cipher Block Chaining) mode. Each ciphertext block in CBC mode is dependent on all message blocks preceding it and the key. The final ciphertext block effectively becomes the MAC value.
• Keyed Hash Functions: MACs can also be based on hash functions, which are generally faster and widely available. Early, naive proposals like KeyedHash = Hash(Key|Message) were found to have weaknesses. This led to the development of HMAC.

HMAC: A Robust Keyed-Hash MAC

HMAC (Hash-based Message Authentication Code) is an internet standard (RFC2104) that provides a secure way to compute MACs using a cryptographic hash function. HMACs address the weaknesses of simpler keyed-hash approaches. The formula for HMAC is HMAC_K = Hash[(K+ XOR opad) || Hash[(K+ XOR ipad)||M)]], where:

• K+ is the key, padded to the hash function's block size or hashed if it's longer.
• opad and ipad are specified padding constants.
• The overhead for HMAC is just two additional hash calculations beyond what the message alone would need.
• Any cryptographic hash function can be used with HMAC, making it highly flexible.

Authenticated Encryption (AE) and AEAD

Sometimes, confidentiality and authenticity are both required. Authenticated Encryption (AE) combines these two security properties.

Generic Composition for Authenticated Encryption

There are several ways to combine encryption and MACs, known as generic composition:

• MAC-then-Encrypt: First, the plaintext is MACed, then the MAC tag is appended to the plaintext, and both are encrypted together. This approach offers good security and is used in TLS, though padding can be tricky.
• Encrypt-then-MAC: The plaintext is encrypted without a MAC. Then, a MAC is calculated over the ciphertext, and both the ciphertext and MAC tag are sent together. This method provides the highest security but requires using two distinct keys for encryption and MAC.
• Encrypt-and-MAC: The plaintext is input to both the encryption and MAC functions simultaneously. The MAC tag is appended to the ciphertext, and both are sent or stored together. This offers good security and is employed in SSH.

AEAD: Authenticated Encryption with Associated Data

Authenticated Encryption with Associated Data (AEAD) goes a step further by providing authentication for both the ciphertext and any associated unencrypted data (metadata) that needs to be integrity-protected but not encrypted. This is particularly useful for headers or other non-confidential information that must not be tampered with.

Public-Key Cryptography: Asymmetric Security

Public-key cryptography, also known as asymmetric cryptography, revolutionized secure communication. Unlike symmetric cryptography which uses a single shared secret key, public-key cryptography uses a pair of keys.

The Birth of Non-Secret Encryption

The initial motivation for public-key cryptography came from the desire for easier key distribution, specifically researched by governments like GCHQ (UK) in the 1970s. The breakthrough was the realization that public keys do not have to be confidential. The decryption process relies on a private key that the sending party does not possess.

Key Pairs and Their Roles

In public-key cryptography, each participant generates a key pair:

• A public key: Used for encryption (by anyone) or signature verification. It's meant to be widely distributed.
• A private key: Used for decryption (only by the owner) or signature generation. It must be kept absolutely confidential.

Key distribution in public-key systems is much simpler than in symmetric systems because only the public key needs to be securely shared. For integrity and ownership, the public key's authenticity is critical. For the private key, confidentiality (and integrity) is paramount.

Communication is typically one-directional for key generation: if Bob wants to send a message to Alice, Alice generates her key-pair. For Alice to send to Bob, Bob generates his own key-pair.

Avoiding Dual-Purpose Keys

While some algorithms like RSA can theoretically use the same key for both encryption and digital signatures, it is strongly not recommended and can introduce security risks. Different time guarantees are often required for confidentiality and authenticity, and using separate key-pairs simplifies compliance with legal requests (e.g., law enforcement access to decryption keys). Algorithms like DSA were explicitly designed for signing only to prevent their use for encryption that could hide information.

Fundamental Requirements of Public-Key Cryptography

Public-key systems must meet several stringent requirements:

• The public key is public; its authenticity (integrity) and association with its owner are critical.
• The private key is confidential; its confidentiality (and integrity) is critical.
• Recovering plaintext from ciphertext and the public key alone must be computationally infeasible.
• Recovering the private key from the public key and any amount of ciphertexts must be computationally infeasible.

Digital Signatures: Guaranteeing Authenticity and Non-Repudiation

Digital signatures provide functionalities that were not initially conceived when public-key encryption was developed. They are a cornerstone of trust in digital interactions.

The Power of Digital Signatures

A digital signature provides three crucial security properties:

• Data Integrity: Ensures the signed data has not been altered.
• Data Origin Authentication: Confirms the identity of the signer.
• Non-repudiation of Origin: Prevents the signer from later denying they signed the document. This proof can be presented to third parties like a court or arbiter, unlike MACs.

Due to the relative slowness of asymmetric cryptographic operations, typically the hash of the data is signed, not the entire data itself. This makes the process much more efficient.

Key Management for Digital Signatures

• Private Key: Used for signing and must be kept absolutely confidential by the signer.
• Public Key: Used for signature verification and must be authentic (reliably linked to the signer) and available to verifiers.

Steps in Digital Signature Process

The digital signature process involves several key steps:

1. Key Generation: The signer creates their public/private key pair.
2. Public-key Certification/Signing: The public key is often certified by a trusted third party (e.g., a Certificate Authority) to establish its authenticity.
3. Signature Generation: The signer uses their private key to sign the hash of the data.
4. Signature Verification: A verifier uses the signer's public key to check if the signature is valid for the given data and hash.

Cryptographic Hash Functions: Integrity Checkers

Cryptographic hash functions are mathematical algorithms that map data of arbitrary size to a fixed-size bit array, called a hash value, message digest, or digital fingerprint. They are unkeyed algorithms.

Core Properties of Cryptographic Hash Functions

For a hash function to be cryptographically secure, it must possess several properties based on computational security:

1. Speed and Avalanche Effect: They must be efficiently computable. A secure hash function exhibits an avalanche effect, meaning even a single bit change in the input results in an entirely unpredictable (roughly 50% of bits changing) output hash.
2. One-Wayness (Preimage Resistance): Given a hash value h, it must be computationally infeasible to find any message m such that H(m) = h.
3. Second Preimage Resistance (Weak Collision Resistance): Given an input m1, it must be computationally infeasible to find a different input m2 such that H(m1) = H(m2).
4. Collision Resistance (Strong Collision Resistance): It must be computationally infeasible to find any pair of distinct inputs m1 and m2 such that H(m1) = H(m2). This is harder to achieve than second preimage resistance because both m1 and m2 can be freely chosen.

Practical Use of Hash Functions for Data Integrity

Consider verifying data integrity over a phone call, a separate channel for verification. Alice sends a file to Bob. If Alice also sends the hash of the file via a secure, out-of-band channel (like a phone call), Bob can compute the hash of the received file and compare it. If they match, the file's integrity is confirmed. If an attacker modifies the file in transit, Bob's computed hash won't match Alice's, immediately revealing the tampering.

Attacks on Hash Functions and Deprecation

Hash functions are susceptible to specific attacks, notably those leveraging the Birthday Paradox, which suggests that collisions can be found much faster than brute-forcing preimages. For a hash of size s, collisions can be found with O(2^(s/2)) complexity.

• MD5 (128-bit hash): Despite a theoretical 2^64 birthday paradox complexity, weaknesses found in 1996 led to practical collision attacks in minutes (Wang et al. 2004, V. Klima 2005) and prefix collisions in seconds (Stevens et al. 2009). MD5 is now considered cryptographically broken and deprecated for security purposes.
• SHA-1 (160-bit hash): Also considered deprecated after a practical collision was found in 2017.

Stronger hash functions like SHA-256 and SHA-512 (part of SHA-2 family) and SHA-3 are recommended for modern applications.

Cryptographic Algorithms and Keys

Cryptography involves both algorithms and keys. Algorithms are the mathematical procedures, while keys are the secret parameters that make the algorithm's output unique and secure.

Algorithms with and Without Keys

• Algorithms with keys: These include ciphers (symmetric and asymmetric), and MACs, where a secret key is essential for their operation.
• Algorithms without keys: These are typically hash functions and Random Number Generators (RNGs), which produce outputs based on inputs without needing a secret key.

The Danger of Inventing Your Own Crypto

The history of cryptography is littered with examples of proprietary or custom-built cryptographic systems failing spectacularly. A notable case is KeeLoq, a block cipher used in car remote keyless entry systems. Conceived in the 80s, it was proprietary and closed-design, meaning it wasn't subject to rigorous public scrutiny. In 2008, Ruhr University Bochum presented a complete break, allowing the extraction of manufacturer keys and cloning of remote controls, demonstrating the critical importance of public review and expert examination for cryptographic algorithms.

Symmetric Block Cipher Modes of Operation

Block ciphers encrypt fixed-size blocks of data. To encrypt messages longer than a single block, modes of operation are used. A good cipher itself does not guarantee good encryption; the mode of operation is critical.

ECB (Electronic Codebook) Mode

• Mechanism: Each plaintext block is encrypted independently using the same key.
• Characteristics: Repetitions in the plaintext are directly reflected in the ciphertext. This makes it insecure for most data, as patterns can be easily discerned.
• Main Use: Sending only a few blocks of data where patterns are unlikely to emerge or are irrelevant.

CBC (Cipher Block Chaining) Mode

• Mechanism: Each plaintext block is XORed with the previous ciphertext block before encryption. The first block uses an Initialization Vector (IV).
• Characteristics: Each ciphertext block depends on all preceding message blocks, hiding patterns effectively. The IV must be known by both sender and receiver but cannot be sent in clear as it introduces predictability.
• Caution: Requires careful handling of the last