Sponge Function and Birthday Attack

Sponge Construction Phases

• During the absorbing phase, an input message gets absorbed in blocks of r bits.
• For each block of the input message, a permutation is applied once.
• The number of permutation calls equals ceil(message_length / r).
• During the squeezing phase, the output is generated r bits at a time.
• The permutation is applied each time more output is needed.
• r determines performance in absorbing and squeezing, a larger r means fewer permutation calls.

Blind Tag Guessing

• You know a message m and want to guess a tag t such that MACₖ(m) = t, without knowing the key K.
• The goal is to guess the correct tag for a given m, not to find a collision.
• If the MAC tag is t bits long, success probability per guess is 1/2ᵗ.
• Example: If the MAC tag is 48 bits long, the success probability per guess is 1/2⁴⁸.
• The security strength is t bits.

Birthday Paradox

• This applies when trying to find two messages m1, m2 such that MACₖ(m1) = MACₖ(m2) which is a collision.
• The objective is to find any two matching tags, not a specific tag.
• The number of queries until a collision is approximately 2^(t/2) due to the birthday bound.
• Thus the security strength is t/2 bits.

MD5

• Designed by Ron Rivest in 1991, one of the inventors of RSA.
• Based on MD4, which was an earlier, less secure design.
• Produces a 128-bit digest, or output hash.
• It is known to be broken, meaning collision attacks exist.

SHA-1

• Inspired by MD5 and designed by the NSA in 1995.
• Followed SHA-0, an earlier version from 1993 that had flaws.
• Produces a 160-bit digest.
• SHA-1 is no longer considered secure because practical collision attacks exist.

SHA-2 Series

• Versions of SHA-1 which are reinforced, redesigned to resist known attacks.
• Includes 6 hash functions: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256.
• Output lengths vary from 224 to 512 bits.
• Currently considered secure, SHA-3 is recommended for future-proofing.

Internals of MD5, SHA-1, and SHA-2

• All of them use Merkle-Damgård iteration mode.
• This is a method for building a variable-length hash function from a fixed-size compression function.
• It splits the message into blocks and processes them sequentially, each depending on the previous.
• The core function used in Merkle-Damgård is Compression function F.
• In SHA-1 and SHA-2, F is based on a block cipher-like structure, often built using Davies-Meyer mode.
• Davies-Meyer construction is a way to turn a block cipher into a compression function: F(h, m) = Em(h) ⊕ h.
• E_m(h) = block cipher encryption of h using m as the key.
• h XOR with input chaining variable.

Merkle–Damgård Usage

• MD5, SHA-1, and SHA-2 all use Merkle–Damgård.
• All three families (MD5, SHA-1, SHA-2) follow the Merkle-Damgård paradigm.
• This makes them vulnerable to length-extension attacks, constructions like HMAC are designed to avoid those problems.

Summary of Algorithms

• MD5
  • Digest Size: 128 bits
  • Uses Merkle-Damgård?: Yes
  • Status: Broken
• SHA-1
  • Digest Size: 160 bits
  • Uses Merkle-Damgård?: Yes
  • Status: Broken
• SHA-2
  • Digest Size: 224-512 bits
  • Uses Merkle-Damgård?: Yes
  • Status: Secure (as of now)

Collision Resistance

• Collision resistance ensures it's hard to find any two inputs x ≠ x' such that h(x) = h(x').

Second Preimage Resistance

• Second preimage resistance ensures given a specific input x, it is hard to find a different input x´ ≠ x such that h(x) = h(x').

Collision vs Second Preimage

• Collision resistance is about finding any two messages that collide, allowing free choice of both.
• Second preimage resistance is about being given a specific message and then trying to find a second one that collides with it.
• It is harder to find a second one that collides with it.
• Collision resistance does not imply second preimage resistance, second preimage resistance does imply collision resistance.
• If the compression function F is collision-resistant, then the full Merkle–Damgård hash function h is also collision-resistant.

Primitives vs Constructions

• Primitive is a basic cryptographic building block, designed to be used by other constructions.
• Construction is a method or recipe that builds something bigger (like a hash function, MAC, stream cipher, etc.) from primitives.

SHA-2 as a primitive

• SHA-2 (like SHA-256 or SHA-512) is built internally using a construction (Merkle–Damgård with Davies-Meyer compression).
• From a higher-level perspective, SHA-2 is a hash function that is already packaged and ready to use.
• Internally, SHA-2 uses constructions.
• However, as a whole, it's a standardized hash function primitive used in protocols, applications, digital signatures, etc.
• This means:
  • It is used directly in real-world protocols like TLS, Bitcoin, HMAC, etc.
  • It takes variable-length input and produces a fixed-length digest.
  • You don't "build" SHA-2 yourself, instead using it as-is, as a black-box function with known security properties.
• Construction: When you build a hash function using the Merkle–Damgård construction, you are composing a new function from:
  • A compression function F
  • Padding
  • Iteration logic
• Analogy: Merkle-Damgård is the recipe to make chocolate cake; SHA-256 is the store-bought chocolate cake to eat or use in recipes.

PRP (Pseudorandom Permutation Security)

• A pseudorandom permutation (PRP) is a function that is computationally indistinguishable from a truly random permutation when given only forward queries.
• Definition: A block cipher E: {0, 1}ᵏ x {0, 1}ⁿ → {0, 1}ⁿ is PRP if, for any efficient adversary, distinguishing between Eₖ(·) (where k is a secret key) and a random permutation is computationally infeasible.
  • The adversary only has access to the encryption function Eₖ(x) (forward direction).
  • PRP security does not require that the adversary is given access to the inverse function Eₖ⁻¹(x).
• PRP security is sufficient when an application only requires encryption (not decryption).
• Example: Counter (CTR) mode, Output Feedback mode (stream modes).

SPRP Security

• A strong SPRP extends PRP by requiring that the function is indistinguishable from a random permutation even if the adversary is given access to both encryption and decryption functions.
• Definition: A block definition E: {0, 1}ᵏ x {0, 1}ⁿ → {0, 1}ⁿ is SPRP, if for any efficient adversary with access to both Ek(·), Eₖ⁻¹(·), distinguishing it from a truly random permutation is computationally infeasible.
• SPRP security is needed when the inverse function (decryption) is used, which is common in MACs and some modes.
• CBC-MAC requires access to decryption.
• CMC, EMAC require SPRP security.