Hash Function Notes

Hash functionsSearch on YouTubeBookmarkSaved

DefinitionSearch on YouTubeBookmarkSaved

A function $H$ makes a hash value:

$h = H(M)$

$M$ is a message of variable length. $h$ is a fixed-length hash value. Other names are message digest and hash code. A footnote also calls it a cryptographic checksum.

The source appends the hash value to the message. At that time, the message is known to be correct. The receiver calculates the hash again to authenticate the message.

The hash function is not secret. Thus something must protect the hash value. Figures 10.1 and 10.2 show the basic uses:

• Encrypt the hash value with a secret key.
• Sign the hash value with a private key.
• Hash a shared secret value together with the message.

The purpose of a hash function is to make a "fingerprint" of a file, message or other data block.

Six propertiesSearch on YouTubeBookmarkSaved

$H$ must have these properties for message authentication:

• A function that satisfies properties 1 to 5 is a weak hash function.
• A function that also satisfies property 6 is a strong hash function.

Why properties 4 to 6 matterSearch on YouTubeBookmarkSaved

Property 4 (one-way). It is important when the sender hashes a secret value $S_{AB}$ with the message. The sender does not send $S_{AB}$. If $H$ is not one-way, an attacker can find it:

1. Intercept $M$ and $C = H(S_{AB} \Vert M)$.
2. Invert the hash: $S_{AB} \Vert M = H^{-1}(C)$.
3. Remove the known $M$ to get $S_{AB}$.

Property 5 (weak collision). It prevents forgery when the hash code is encrypted. The opponent can read the message and calculate its hash. But the opponent does not have the secret key. Without property 5, an attacker can do this:

1. Intercept a message and its encrypted hash code.
2. Calculate the unencrypted hash code of the message.
3. Make a different message with the same hash code.

Property 6 (strong collision). It protects against the birthday attack.

General structureSearch on YouTubeBookmarkSaved

Figure 10.3 shows the general structure of a secure hash code. SHA-1 uses this structure.

• The function divides the message into blocks.
• A compression function takes one block and a chaining variable $CV$. It gives the next $CV$.
• The last $CV$ is the hash value.

This structure is similar to CBC mode for symmetric algorithms.

Birthday attackSearch on YouTubeBookmarkSaved

The ideaSearch on YouTubeBookmarkSaved

Suppose that a 64-bit hash code is used. A sender transmits the message $M$ and an encrypted hash code $C$. To replace the message, an opponent must find $M'$ with $H(M') = H(M)$. On average, this needs about $2^{63}$ tries.

The birthday attack needs much less work. The source A signs a message. A appends an $m$-bit hash code and encrypts the hash code with its private key.

Attack stepsSearch on YouTubeBookmarkSaved

1. The opponent makes $2^{m/2}$ variations $x'$ of the valid message $x$. All variations have the same meaning.
2. The opponent makes $2^{m/2}$ variations $y'$ of a fraudulent message $y$.
3. The opponent compares the two sets to find a pair with the same hash code. By the birthday paradox, the probability of success is more than 0.5. If there is no match, the opponent makes more variations.
4. The opponent gives the valid variation to A for signature.
5. The opponent attaches this signature to the fraudulent variation and sends it.

The two variations have the same hash code. Thus they have the same signature. The attack works without the encryption key.

Secure Hash AlgorithmSearch on YouTubeBookmarkSaved

HistorySearch on YouTubeBookmarkSaved

In 2005, NIST announced a plan to stop approval of SHA-1 by 2010. Then a research team described a collision attack on SHA-1. It needs $2^{69}$ operations. Before, people thought that a collision needed $2^{80}$ operations.

SHA-1 stepsSearch on YouTubeBookmarkSaved

SHA-1 takes a message of less than $2^{64}$ bits. It gives a 160-bit digest. It processes the input in 512-bit blocks.

Step 1: append padding bits. Pad the message so that its length is $448 \bmod 512$. The padding is one 1 bit, then the necessary 0 bits. Always add padding, also when the length is already correct. Thus the padding is 1 to 512 bits.

Step 2: append length. Append a 64-bit block. It contains the length of the original message, as an unsigned integer, most significant byte first.

Step 3: initialize the MD buffer. A 160-bit buffer holds the intermediate and final results. It has five 32-bit registers:

Step 4: process the message in 512-bit (16-word) blocks. The compression function has four rounds of 20 steps each.

• Each round uses a different logical function: $f_1$, $f_2$, $f_3$ or $f_4$.
• Each round takes the current block $Y_q$ and the buffer $ABCDE$, and updates the buffer.
• Each step $t$ ($0 \le t \le 79$) uses an additive constant $K_t$. There are only four different constants, one for each round.
• The output of round 4 is added to $CV_q$ modulo $2^{32}$. The result is $CV_{q+1}$.

Step 5: output. After all $L$ blocks, the output of the last stage is the 160-bit digest.

The standard values of $K_t$ and $f_t$ (from the SHA lecture) are:

SHA-1 summarySearch on YouTubeBookmarkSaved

$CV_0 = IV$

$CV_{q+1} = SUM_{32}(CV_q, ABCDE_q)$

$MD = CV_L$

Digital signaturesSearch on YouTubeBookmarkSaved

DisputesSearch on YouTubeBookmarkSaved

Message authentication protects two parties from a third party. It does not protect the two parties from each other. Suppose that John sends an authenticated message to Mary. Two disputes are possible:

• Forgery by the receiver. Mary makes a different message and says that it came from John. She uses the key that she shares with John to make the authentication code.
• Denial by the sender. John says that he did not send the message. Mary can forge messages, so nobody can prove that John sent it.

When sender and receiver do not fully trust each other, use a digital signature.

PropertiesSearch on YouTubeBookmarkSaved

A digital signature is similar to a handwritten signature. It must:

• verify the author and the date and time of the signature,
• authenticate the contents at the time of the signature,
• be verifiable by third parties, to resolve disputes.

RequirementsSearch on YouTubeBookmarkSaved

1. The signature is a bit pattern that depends on the signed message.
2. It uses information unique to the sender, to prevent forgery and denial.
3. It is easy to make.
4. It is easy to recognize and verify.
5. It is infeasible to forge. This means a new message for an existing signature, or a false signature for a given message.
6. It is practical to keep a copy of the signature in storage.

ElGamal signaturesSearch on YouTubeBookmarkSaved

KeysSearch on YouTubeBookmarkSaved

The ElGamal signature is related to Diffie-Hellman. It uses exponentiation in a finite (Galois) field. Its security depends on the difficulty of discrete logarithms.

• The global elements are a prime $q$ and $\alpha$, a primitive root of $q$.
• The private key signs. The public key verifies.

Each user A makes a key pair:

• Select a secret $x_A$ with $1 < x_A < q - 1$.
• Calculate the public key $y_A = \alpha^{x_A} \bmod q$.

Signing and verificationSearch on YouTubeBookmarkSaved

Alice signs a message $M$ for Bob:

1. Calculate the hash $m = H(M)$, with $0 \le m \le q-1$.
2. Select a random $K$ with $1 \le K \le q-1$ and $\gcd(K, q-1) = 1$.
3. Calculate the temporary key $S_1 = \alpha^K \bmod q$.
4. Calculate $K^{-1} \bmod (q-1)$.
5. Calculate $S_2 = K^{-1}(m - x_A S_1) \bmod (q-1)$.
6. The signature is $(S_1, S_2)$.

Any user B verifies the signature:

$V_1 = \alpha^m \bmod q, \qquad V_2 = y_A^{S_1} \cdot S_1^{S_2} \bmod q$

The signature is valid if $V_1 = V_2$.

Why it works: $y_A^{S_1} S_1^{S_2} = \alpha^{x_A S_1 + K S_2}$. Also $K S_2 \equiv m - x_A S_1 \pmod{q-1}$. Thus the exponent is $m$, and $V_2 = \alpha^m = V_1$.

Worked exampleSearch on YouTubeBookmarkSaved

Use $GF(19)$: $q = 19$ and $\alpha = 10$.

Keys. Alice selects $x_A = 16$. Then $y_A = 10^{16} \bmod 19 = 4$.

Signing. The message hash is $m = 14$.

• Select $K = 5$. $\gcd(18, 5) = 1$.
• $S_1 = 10^5 \bmod 19 = 3$.
• $K^{-1} \bmod 18 = 5^{-1} \bmod 18 = 11$, because $5 \times 11 = 55 = 54 + 1$.
• $S_2 = 11(14 - 16 \times 3) \bmod 18 = 11 \times (-34) \bmod 18 = 4$.

The signature is $(3, 4)$.

Verification.

• $V_1 = 10^{14} \bmod 19 = 16$
• $V_2 = 4^3 \cdot 3^4 \bmod 19 = 64 \times 81 \bmod 19 = 5184 \bmod 19 = 16$

$16 = 16$, so the signature is valid.

Digital Signature StandardSearch on YouTubeBookmarkSaved

HistorySearch on YouTubeBookmarkSaved

NIST published FIPS 186, the Digital Signature Standard (DSS). DSS uses SHA and a new technique, the Digital Signature Algorithm (DSA).

DSA gives only the signature function. Unlike RSA, it cannot encrypt or exchange keys. It is a public-key technique. Its security depends on the difficulty of discrete logarithms, as in Diffie-Hellman.

Parameters and keysSearch on YouTubeBookmarkSaved

A group of users can share three public parameters:

• $q$: a 160-bit prime.
• $p$: a prime of 512 to 1024 bits, with $q \mid (p-1)$.
• $g = h^{(p-1)/q} \bmod p$, with $1 < h < p - 1$ and $g > 1$.

Each user selects a private key $x$ randomly or pseudorandomly. The standard uses $0 < x < q$. (The notes write "1 to $p-1$".) The public key is $y = g^x \bmod p$. It is easy to calculate $y$ from $x$. It is infeasible to find $x$ from $y$.

Signing and verificationSearch on YouTubeBookmarkSaved

To sign, the user calculates $r$ and $s$. They use $(p, q, g)$, the private key $x$, the hash $H(M)$ and a random $k$. Use a new $k$ for each signature.

$r = \left(g^k \bmod p\right) \bmod q$

$s = k^{-1}\left(H(M) + x r\right) \bmod q$

The receiver calculates $v$ from the public parameters, the public key of the sender and the hash of the message:

$w = s^{-1} \bmod q$

$u_1 = H(M) \cdot w \bmod q, \qquad u_2 = r \cdot w \bmod q$

$v = \left(g^{u_1} \cdot y^{u_2} \bmod p\right) \bmod q$

The signature is valid if $v = r$.

Quick self-testSearch on YouTubeBookmarkSaved

Give the six properties of a hash function for message authentication.

Any input size. Fixed-length output. Easy to calculate. One-way. Weak collision resistance. Strong collision resistance.

How does the one-way property protect $S_{AB}$ in $C = H(S_{AB} \Vert M)$?

If an attacker can invert $H$, it gets $S_{AB} \Vert M$ from $C$. It knows $M$, so it gets $S_{AB}$. A one-way $H$ prevents this.

Describe the birthday attack and its effort for a 64-bit hash.

Make $2^{32}$ valid and $2^{32}$ fraudulent variations. Find a pair with the same hash. Get A to sign the valid variation, then attach the signature to the fraudulent one. The effort is about $2^{32}$, not $2^{63}$.

What is the difference between a weak and a strong hash function?

A weak hash function satisfies properties 1 to 5. A strong hash function also satisfies property 6, so it resists the birthday attack.

Give the five SHA-1 processing steps.

Append padding to $448 \bmod 512$. Append the 64-bit length. Initialize ABCDE. Process each 512-bit block in four rounds of 20 steps. Output the 160-bit $CV_L$.

What collision attack on SHA-1 do the notes give?

A research team found collisions with $2^{69}$ operations. Before, people thought that this needed $2^{80}$ operations.

Why must a digital signature use information unique to the sender?

It prevents forgery by the receiver and denial by the sender. Only the sender can make the signature.

In the $GF(19)$ ElGamal example, give the signature and the check.

$y_A = 4$, $S_1 = 3$, $K^{-1} = 11$, $S_2 = 4$. $V_1 = 10^{14} \bmod 19 = 16$ and $V_2 = 4^3 \cdot 3^4 \bmod 19 = 16$. The signature is valid.

Give the DSA signing and verification equations.

Sign: $r = (g^k \bmod p) \bmod q$ and $s = k^{-1}(H(M) + xr) \bmod q$. Verify: $w = s^{-1}$, $u_1 = H(M) w$, $u_2 = r w$, $v = (g^{u_1} y^{u_2} \bmod p) \bmod q$. Valid if $v = r$.