11 – Hash Functions 雜湊函數
• Why we need hash functions
• Security properties
• Secure Hash Algorithms
1/19
Content
• Why we need hash functions
• Security properties
• Secure Hash Algorithms
2/19
Motivation
Problem:
Naive signing of long messages generates a signature of same length.
• Three Problems
• Computational overhead
• Message overhead
• Security limitations
Solution:
• Instead of signing the whole message, sign only a digest (=hash)
• Also secure, but much faster
Needed:
Hash Functions
3/19
Digital Signature with a Hash Function
4/19
Basic Protocol for Digital Signatures
with a Hash Function
Alice Kpub Bob
z = h(x)
s = sigKpr(z)
(x, s)
z' = h(x)
verKpub(s, z') = true/false
5/19
Principal input – output behavior of
hash functions
6/19
Content
• Why we need hash functions
• Security properties
• Secure Hash Algorithms
7/19
The three security properties of hash
functions
8/19
Hash Function: Security Properties
• Pre-image resistance:
For a given output z, it is computationally infeasible to
find any input x such that h(x) = z, i.e., h(x) is one-way
• Second pre-image resistance:
Given x1, and thus h(x1), it is computationally
infeasible to find any x2 such that h(x1) = h(x2)
• Collision resistance:
It is computationally infeasible to find any pairs x1 x2
such that h(x1) = h(x2)
9/19
Hash Function : Security
It turns out that collision resistance causes most problems
• How hard is it to find a collision with a probability of 0.5?
• Related Problem: How many people are needed such
that two of them have the same birthday with a
probability of 0.5?
• Far fewer than 365/2 = 182.5! This is called the birthday
paradox (Search takes ≈ 2𝑛 steps)
• To deal with this paradox, hash functions need a output
size of at least 160 bits
10/19
Content
• Why we need hash functions
• Security properties
• Secure Hash Algorithms
11/19
Hash Function: Algorithms
Hash Algorithms
special algorithms, based on
e.g. MD4 - family block ciphers
• MD4 – family (MD Message Digest)
• SHA-1: output - 160 bits; input - 512 bits chunks of
message x; operations - bitwise AND, OR, XOR,
complement and cyclic shifts
• RIPE-MD 160: output - 160 bits; input - 512 bits chunks
of message x; operations – like in SHA-1, but two in
parallel and combinations of them after each round
12/19
SHA-1
• Part of the MD-4 family
• Based on a Merkle-Damgård construction
• 160-bit output from a message of arbitrary length
• Widely used (even tough some weaknesses are
known)
13/19
SHA-1 High-Level Diagram
• Compression Function is used in 80 rounds which are
divided into four stages of 20 rounds each
14/19
SHA-1: Padding
• Message x has to be padded to fit a size of a multiple of
512 bits
• k 512 − 64 − 1 − l = 447 − l mod 512
15/19
SHA-1: Hash Computation
• Each message block xi is processed in four stages with 20
rounds each
SHA-1 uses:
• A message schedule which computes a 32-bit word W 0, W 1,
..., W 79 for each of the 80 rounds
• Five working registers of size of 32 bits A, B, C, D, E
• A hash value Hi consisting of five 32-bit words Hi(0), Hi(1), Hi(2) ,
Hi(3), Hi(4)
• In the beginning, the hash value holds the initial value H0,
which is replaced by a new hash value after the processing of
each single message block
• The final hash value Hn is equal to the output h(x) of SHA-1
16/19
SHA-1: All four stages
17/19
SHA-1: Internals of a Round
Stage t Round j Constant K t Function ft
1 00…19 K = 5A827999 f (B, C, D) = (B∧C)∨(B∧D)
2 20…39 K = 6ED9EBA1 f (B, C, D) = B⊕C⊕D
3 40…59 K = 8F1BBCDC f (B, C, D) = (B⊕C)∨(B⊕D)∨(C⊕D)
4 60…79 K = CA62C1D6 f (B, C, D) = B⊕C⊕D
18/19
Lessons Learned
• Hash functions are keyless. The two most important applications of
hash functions are their use in digital signatures and in message
authentication codes such as HMAC
• The three security requirements for hash functions are one-
wayness, second preimage resistance and collision resistance
• Hash functions should have at least 160-bit output length in order
to withstand collision attacks; 256-bit or more is desirable for long-
term security
• MD5, which was widely used, is insecure. Serious security
weaknesses have been found in SHA-1, and the hash function
should be phased out. The SHA-2 algorithms all appear to be
secure
• The SHA-3 competition results in new standardized hash functions
19/19