Hash Functions

Hash function basicsSearch on YouTubeBookmarkSaved

DefinitionSearch on YouTubeBookmarkSaved

A hash function condenses an arbitrary message to a fixed size:

$h = H(M)$

• The input is a message or data block $M$ of variable length $L$ bits. The output is a hash value $h$ of fixed length.
• We usually assume that the hash function is public. No secret is part of $H$.
• The hash detects changes to the message.

Cryptographic propertiesSearch on YouTubeBookmarkSaved

A cryptographic hash function has two more properties:

• One-way property: it is computationally infeasible to find data that maps to a specific hash, $H(y) = h$.
• Collision-free property: it is computationally infeasible to find two data with the same hash, $H(x) = H(y)$.

Hash function usesSearch on YouTubeBookmarkSaved

MIC, MAC and signatureSearch on YouTubeBookmarkSaved

A MAC uses a shared secret key. Only the two parties can check it, so neither party can prove the origin to a third party. A signature uses a private key, so a third party can check it and settle a dispute.

Symmetric key, unkeyed hashSearch on YouTubeBookmarkSaved

The slides show two diagrams. Source A sends to destination B.

• (a) Message encrypted: A computes $H(M)$, concatenates it with $M$ and encrypts both with key $K$. The channel carries $\mathrm{E}(K, [M \| H(M)])$. B decrypts with $K$, computes the hash of $M$ again and compares.
• (b) Message unencrypted: A encrypts only the hash. The channel carries $M$ with $\mathrm{E}(K, H(M))$. B decrypts the hash with $K$ and compares it with a new hash of $M$.

Symmetric key, keyed hashSearch on YouTubeBookmarkSaved

In the next two diagrams, the hash also takes a shared secret value $S$:

• (c) Message unencrypted: A computes $H(M \| S)$ and sends it with $M$. B computes $H(M \| S)$ with the same $S$ and compares.
• (d) Message encrypted: A encrypts $M$ and $H(M \| S)$ with $K$. The channel carries $\mathrm{E}(K, [M \| H(M \| S)])$. B decrypts with $K$, computes the hash with $S$ and compares.

The secret $S$ changes the plain hash into a MAC. The attacker does not know $S$, so the attacker cannot compute a valid hash for a changed message.

Digital signatures (PKCS)Search on YouTubeBookmarkSaved

The PKCS diagrams use a public-key pair:

• (a) A hashes $M$ and encrypts the digest with the private key: $\mathrm{E}(PR_a, H(M))$. The message and the signature go together. B hashes $M$, decrypts the signature with $PU_a$ and compares.
• (b) This adds confidentiality. A encrypts $M \| \mathrm{E}(PR_a, H(M))$ with a symmetric key $K$. The channel carries $\mathrm{E}(K, [M \| \mathrm{E}(PR_a, H(M))])$. B decrypts with $K$, then verifies the signature with $PU_a$.

Other usesSearch on YouTubeBookmarkSaved

• Pseudorandom function (PRF): generate session keys and nonces. Produce a key from a password. Derive keys from a master key cooperatively.
• Pseudorandom number generator (PRNG).
• One-way password file: store the hash of the password, not the actual password. Unix and Windows NT do this. A salt deters precomputation attacks.
• Intrusion detection and virus detection: keep and check the hash of each file on the system. An example tool is Tripwire.

Two insecure hash functionsSearch on YouTubeBookmarkSaved

Block XORSearch on YouTubeBookmarkSaved

The first toy hash is a bit-by-bit exclusive-OR (XOR) of every block:

$C_i = b_{i1} \mathbin{\mathrm{xor}} b_{i2} \mathbin{\mathrm{xor}} \dots \mathbin{\mathrm{xor}} b_{im}$

Bit $i$ of the hash is the XOR of bit $i$ of all $m$ blocks. This is a longitudinal redundancy check. It is reasonably effective as a data integrity check. One changed message bit changes exactly one hash bit.

Rotate and XORSearch on YouTubeBookmarkSaved

The second toy hash adds a one-bit circular shift on the hash value:

1. Take each successive $n$-bit block.
2. Rotate the current hash value to the left by 1 bit.
3. XOR the block into the hash value.

The slides say that this is good for data integrity but useless for security.

Requirements and attacksSearch on YouTubeBookmarkSaved

Requirements tableSearch on YouTubeBookmarkSaved

Attack typesSearch on YouTubeBookmarkSaved

The attacks are brute-force attacks and cryptanalysis.

• Preimage or second preimage attack: find $y$ such that $H(y)$ equals a given hash value.
• Collision attack (against collision resistance): find two messages $x$ and $y$ with the same hash, $H(x) = H(y)$.

Brute-force effortSearch on YouTubeBookmarkSaved

For an $m$-bit hash, a brute-force preimage attack needs about $2^m$ trials. A collision attack needs only about $2^{m/2}$ trials, because of the birthday paradox.

Birthday attacksSearch on YouTubeBookmarkSaved

Birthday paradoxSearch on YouTubeBookmarkSaved

A 64-bit hash can look secure. Because of the birthday paradox, it is not. With about $2^{m/2}$ random messages, the probability of a match is more than $0.5$.

Attack stepsSearch on YouTubeBookmarkSaved

1. A user is prepared to sign a valid message $x$.
2. The opponent generates $2^{m/2}$ variations $x'$ of $x$, all with essentially the same meaning, and saves them.
3. The opponent generates $2^{m/2}$ variations $y'$ of a desired fraudulent message $y$.
4. The opponent compares the two sets to find a pair with the same hash. The probability is more than 0.5 because of the birthday paradox.
5. The user signs the valid message. The opponent then puts the forgery in its place, and the forgery has a valid signature.

The conclusion of the slides: use a larger MAC or hash.

Comparison tableSearch on YouTubeBookmarkSaved

Find $i$ and $j$ such that $H(y'_j) = H(x'_i)$:

Each cell compares $H(x'_i)$ with $H(y'_j)$. One equal cell is sufficient. The forged $y'_j$ gets the signature of the signed $x'_i$. A full table takes $O(N^2)$ time. Sorted lists are faster and take $O(N \log N)$ time.

Quick self-testSearch on YouTubeBookmarkSaved

Give the two cryptographic properties a hash function must have.

One-way property: it is computationally infeasible to find data that maps to a specific hash, $H(y) = h$. Collision-free property: it is computationally infeasible to find two messages $x, y$ with $H(x) = H(y)$.

Name the three main uses of hash functions and what each sends.

MIC: send the hash (digest) of the message. The MIC is always encrypted, the message optionally. MAC: send a keyed hash of the message, with the message optionally encrypted. Digital signature: encrypt the hash with the private signing key and verify with the public key. This gives non-repudiation.

Describe the four symmetric-key message authentication diagrams.

Unkeyed hash: (a) send $\mathrm{E}(K,[M \| H(M)])$; (b) send clear $M$ with $\mathrm{E}(K, H(M))$. Keyed hash: (c) send $M$ with $H(M \| S)$; (d) send $\mathrm{E}(K,[M \| H(M \| S)])$. In each case, the destination computes the hash again and compares.

Show the PKCS digital signature flow with its formulas.

(a) The source sends $M$ with $\mathrm{E}(PR_a, H(M))$. The destination hashes $M$, decrypts the signature with $PU_a$ and compares. (b) For confidentiality, the source sends $\mathrm{E}(K, [M \| \mathrm{E}(PR_a, H(M))])$. The destination decrypts with $K$, then verifies with $PU_a$.

List the PRF, PRNG, password and intrusion-detection uses.

PRF: generate session keys and nonces, produce a key from a password, derive keys from a master key cooperatively. PRNG: generate pseudorandom numbers. Password files: store the hash with a salt, as Unix and Windows NT do. Intrusion and virus detection: keep and check the hash of each file, as Tripwire does.

Give the two simple insecure hash functions and why they fail.

Block XOR: $C_i = b_{i1} \mathrm{xor} b_{i2} \dots \mathrm{xor} b_{im}$, a longitudinal redundancy check. Rotate and XOR: rotate the hash left by 1 bit for each block, then XOR the block. Both are good for data integrity but useless for security. They are easy to invert, so they have no preimage or collision resistance.

Recite the seven hash function requirements.

Variable input size. Fixed output size. Efficiency. Preimage resistant (one-way). Second preimage resistant (weak collision resistant). Collision resistant (strong collision resistant). Pseudorandomness.

Differentiate preimage, second preimage and collision attacks.

Preimage: find $y$ such that $H(y)$ equals a given hash value, about $2^m$ trials. Second preimage: for a given $x$, find $y \ne x$ with $H(y) = H(x)$, also about $2^m$ trials. Collision: find any pair $x \ne y$ with equal hashes, about $2^{m/2}$ trials because of the birthday paradox.

Walk the birthday attack against a signer, step by step.

The user is prepared to sign the valid message $x$. The opponent generates $2^{m/2}$ variations $x'$ with the same meaning. The opponent generates $2^{m/2}$ variations $y'$ of a fraudulent message $y$. A comparison finds $H(x'_i) = H(y'_j)$ with probability more than 0.5. The user signs $x'_i$, and the opponent puts $y'_j$ in its place.

Which search times does the birthday slide give, and why is a 64-bit hash unsafe?

A full table comparison takes $O(N^2)$ time. Sorted lists take $O(N \log N)$ time. With $m = 64$, each set needs about $2^{32}$ variations, which is affordable. The slide concludes: use a larger MAC or hash.