Cryptography Essentials

Cheatsheet Content

1. Hash Functions Definition: A function $H: \{0,1\}^* \to \{0,1\}^n$ that maps an arbitrary length input to a fixed-length output. Properties: Preimage Resistance (One-way): Given $h$, it's computationally infeasible to find $x$ such that $H(x) = h$. Second Preimage Resistance (Weak Collision Resistance): Given $x_1$, it's computationally infeasible to find $x_2 \neq x_1$ such that $H(x_1) = H(x_2)$. Collision Resistance (Strong Collision Resistance): It's computationally infeasible to find any $x_1 \neq x_2$ such that $H(x_1) = H(x_2)$. Applications: Digital signatures, message integrity, password storage. Birthday Attack: Exploits collision resistance. Finding a collision for an $n$-bit hash function takes about $2^{n/2}$ attempts. Examples: MD5 (broken), SHA-1 (broken), SHA-256, SHA-3. 2. Message Authentication Codes (MACs) Definition: A symmetric key primitive used for message integrity and authentication. Sender computes $T = \text{MAC}_K(M)$. Receiver computes $T' = \text{MAC}_K(M')$ and checks if $T = T'$. Properties: Data integrity, data origin authentication. Types: HMAC (Hash-based MAC): Uses a cryptographic hash function (e.g., HMAC-SHA256). $H(K \oplus \text{opad} \parallel H(K \oplus \text{ipad} \parallel M))$. CMAC (Cipher-based MAC): Uses a block cipher (e.g., AES-CMAC). Security: Resistant to existential forgery under chosen-message attack. 3. Digital Signatures Definition: Asymmetric key primitive providing authenticity, integrity, and non-repudiation. Sender signs $M$ with private key $SK$: $\text{Sig} = \text{Sign}_{SK}(M)$. Receiver verifies $\text{Sig}$ with public key $PK$: $\text{Verify}_{PK}(M, \text{Sig})$. Properties: Authentication, integrity, non-repudiation. Algorithms: RSA Signatures: Based on RSA encryption. Sign by decrypting hash with private key, verify by encrypting with public key. DSA (Digital Signature Algorithm): Based on discrete logarithms. ECDSA (Elliptic Curve Digital Signature Algorithm): DSA adapted for elliptic curves, offering smaller key sizes for equivalent security. Hash-then-Sign Paradigm: Sign $H(M)$ instead of $M$ directly for efficiency and security. 4. Public Key Infrastructure (PKI) Goal: Associate public keys with identities and distribute them securely. Components: Certificate Authority (CA): Trusted entity that issues and revokes digital certificates. Digital Certificate: Binds a public key to an identity (e.g., X.509 standard). Contains public key, identity, validity period, CA signature. Registration Authority (RA): Verifies identity before certificate issuance. Certificate Revocation List (CRL): List of revoked certificates. Online Certificate Status Protocol (OCSP): Real-time certificate status checking. Trust Models: Hierarchical: Root CA signs intermediate CAs, which sign end-entity certificates. Web of Trust (PGP): Users sign each other's keys, building a network of trust. 5. Key Exchange Goal: Allow two parties to establish a shared secret key over an insecure channel. Diffie-Hellman Key Exchange (DH): Public parameters: large prime $p$, generator $g$. Alice chooses secret $a$, computes $A = g^a \pmod{p}$. Bob chooses secret $b$, computes $B = g^b \pmod{p}$. Alice sends $A$ to Bob, Bob sends $B$ to Alice. Alice computes $K = B^a \pmod{p}$. Bob computes $K = A^b \pmod{p}$. Shared secret $K = g^{ab} \pmod{p}$. Vulnerable to Man-in-the-Middle (MitM) attack without authentication. Elliptic Curve Diffie-Hellman (ECDH): DH adapted to elliptic curves, offering smaller key sizes. Key Transport: One party generates a symmetric key and encrypts it with the other party's public key. (e.g., RSA key transport). 6. Transport Layer Security (TLS/SSL) Goal: Provide secure communication over a computer network. Layers: TLS Record Protocol: Provides confidentiality (encryption) and integrity (MAC). TLS Handshake Protocol: Negotiates cipher suite, authenticates server (and optionally client), establishes shared secret key. Handshake Steps (simplified): ClientHello: Ciphers, random nonce. ServerHello: Chosen cipher, random nonce, certificate. Certificate: Server sends its certificate. ServerKeyExchange (if needed): DH parameters. CertificateRequest (optional): Server requests client certificate. ServerHelloDone. ClientKeyExchange: Client sends pre-master secret (encrypted with server's public key or DH param). CertificateVerify (if client auth): Client signs a hash of handshake messages. ChangeCipherSpec: Client switches to new cipher. Finished: Client sends MAC of handshake messages. ChangeCipherSpec: Server switches to new cipher. Finished: Server sends MAC of handshake messages. Perfect Forward Secrecy (PFS): Property where compromise of a long-term private key does not compromise past session keys (e.g., using DH/ECDH for key exchange). 7. Block Cipher Modes of Operation Goal: Extend a block cipher (encrypts fixed-size blocks) to handle arbitrary length messages. Common Modes: ECB (Electronic Codebook): Each block encrypted independently. $C_i = E_K(P_i)$ Weak: Reveals patterns, not secure for most applications. CBC (Cipher Block Chaining): Each plaintext block is XORed with the previous ciphertext block before encryption. $C_i = E_K(P_i \oplus C_{i-1})$, $C_0 = IV$ (Initialization Vector). Requires IV, provides confidentiality. Error in one block propagates. CTR (Counter Mode): Block cipher acts as a stream cipher. Encrypts a counter, then XORs with plaintext. $C_i = P_i \oplus E_K(\text{Counter}_i)$. Allows parallel encryption/decryption. Requires unique counter for each message. GCM (Galois/Counter Mode): Authenticated Encryption with Associated Data (AEAD). Provides confidentiality and integrity. Combines CTR mode with a MAC (GHASH). Widely used (e.g., TLS 1.3). 8. Cryptocurrencies (Brief Overview) Blockchain: Distributed ledger, immutable chain of blocks. Each block contains transactions and a hash of the previous block. Mining: Process of adding new blocks to the blockchain by solving a computational puzzle (Proof-of-Work). Proof-of-Work (PoW): Mechanism to deter denial-of-service attacks and ensure consensus. Miners compete to find a nonce that makes the block hash meet certain criteria. Consensus: Agreement among participants on the true state of the ledger. Longest chain rule in PoW. Digital Signatures: Used to authorize transactions (sender signs transaction with private key). Double Spending: Attempting to spend the same cryptocurrency units twice. Prevented by the blockchain's consensus mechanism. 9. Zero-Knowledge Proofs (ZKP) Definition: A method by which one party (the prover) can prove to another party (the verifier) that they know a value $x$, without conveying any information apart from the fact that they know the value. Properties: Completeness: If the statement is true, an honest prover can convince an honest verifier. Soundness: If the statement is false, no dishonest prover can convince an honest verifier. Zero-Knowledge: If the statement is true, the verifier learns nothing beyond the fact that the statement is true. Applications: Authentication, privacy-preserving transactions (e.g., Zcash). 10. Post-Quantum Cryptography Motivation: Current public-key cryptosystems (RSA, ECC, DH) are vulnerable to Shor's algorithm on a sufficiently large quantum computer. Goal: Develop cryptographic algorithms that are secure against both classical and quantum computers. Categories of Algorithms: Lattice-based cryptography: Based on hard problems in lattices (e.g., learning with errors - LWE). Code-based cryptography: Based on error-correcting codes (e.g., McEliece). Multivariate polynomial cryptography: Based on solving systems of multivariate polynomial equations. Hash-based signatures: Based on one-way hash functions (e.g., Merkle trees). Isogeny-based cryptography: Based on supersingular elliptic curve isogenies. NIST Standardization: Ongoing effort to standardize quantum-resistant algorithms.