Understanding Cryptography – A Textbook for
Students and Practitioners
by Christof Paar and Jan Pelzl
www.crypto-textbook.com
Chapter 11 – Hash Functions
ver. October 29, 2009
These slides were prepared by Stefan Heyse and Christof Paar and Jan Pelzl
And modified by Sam Bowne
Contents of this Chapter
11.1 Motivation: Signing Long Messages
11.2 Security Requirements of Hash Functions
11.3 Overview of Hash Algorithms
11.4 The Secure Hash Algorithm SHA-1
3 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
11.1 Motivation: Signing Long Messages
4 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Motivation
Problem:
Naive signing of long messages generates a signature of same length.
• Three Problems
• Computational overhead
• Message overhead
• Security limitations
• Attacker could re-order or re-use signed blocks
Solution:
Instead of signing the whole message, sign only a digest (=hash)
Also secure, but much faster
Needed:
5 Hash Functions
Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Solution
• Hash, then sign
Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Principal input–output behavior of hash functions
7 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
11.2 Security Requirements of Hash Functions
8 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
The three security properties of hash functions
9 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Hash Functions: Security Properties
• Preimage resistance: For a given output z, it is impossible to
find any input x such that h(x) = z, i.e., h(x) is one-way
(Also called one-wayness)
• Second preimage resistance: Given x1, and thus h(x1), it is
computationally infeasible to find any x2 such that h(x1) = h(x2)
(Also called weak collision resistance)
• Collision resistance: It is computationally infeasible to find
any pairs x1 ≠ x2 such that h(x1) = h(x2)
(Also called strong collision resistance)
10 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Hash Functions: Security
• Collison 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 ?
• No! Not 365/2=183
• 23 are enough ! This is called the birthday paradox (Search
takes ≈√2n steps)
• To deal with this paradox, hash functions need a output size of
at least 160 bits
11 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Hash Functions: Security
12 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
11.3 Overview of Hash Algorithms
13 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Hash Functions: Algorithms
Hash Algorithms
Special Algorithms, based on
e.g. MD4 family block ciphers
• MD4 family
• SHA-1: output - 160 Bit; input - 512 bit chunks of message x;
operations - bitwise AND, OR, XOR, complement and cyclic shifts.
• RIPE-MD 160: output - 160 Bit; input - 512 bit chunks of message
x; operations – like in SHA-1, but two in parallel and combinations
of them after each round.
14 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Hash Functions from Block Ciphers
• Matyas-Meyer-Oseas hash
function
• Break original file into
blocks
• Start with known public
block H0, which may be all
zeroes
• Encrypt a block using
previous H as the key, then
XOR with next block of file
data to form the new H
• Repeat through whole file
15 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
Other Hash Functions from Block Ciphers
16 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
11.4 The Secure Hash Algorithm SHA-1
17 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
SHA-1
• Part of the MD-4 family.
• Based on a Merkle-Dåmgard construction
• Similar to a Feistel block cipher
• 160-bit output from a message of maximum length
264 bit.
• Widely used ( even tough some weaknesses are
known)
18 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
How Big is 2**60 bits?
• 2**10 = 1024 = 1Kb
• 2**20 = 1Mb
• 2**30 = 1Gb
• 2**40 = 1 Tb
• 2**60 = 1 million Tb
• 2**63 = 1 million TB
• 2**54 = 2 million TB
19 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
SHA-1 High Level Diagram
Compression
Function
consists of 80
rounds which
are divided
into four
stages of 20
rounds each
20 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
SHA-1: Padding
• Message x has to be padded to fit a size of a multiple of
512 bits
• Add k zero bits
• k = 512 − 64 − 1 − l = 448 − (l + 1) mod 512
21 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
SHA-1: Padding Example
• Message is abc
24 bits long
k = 512 − 64 − 1 − 24 = 423
64 bits long
Value = 24 in binary
22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
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 W0, W1, ..., W79
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.
23 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
24 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
SHA-1: All four stages
Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
25
SHA-1:
Internals of
a Round
Stage t Round j Constant Kt Function ft
1 00…19 5A827999 (B∧C)∨(¯ B∧D) AND
2 20…39 6ED9EBA1 B⊕C⊕D OR
3 40…59 8F1BBCDC (B⊕C)∨(B⊕D)∨(C⊕D) NOT
4 60…79 CA62C1D6 B⊕C⊕D XOR
Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
SHA-1 Collision Found
• Collision found on Feb. 23, 2017
• Links Ch 12-2017-1, 2, and 3 in CNIT 123
28
29
Browsers Deprecated SHA-1
• Link Ch 12zr in CNIT 123
■ Lessons Learned: Hash-Functions
• 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 ongoing SHA-3 competition will result in new standardized hash
functions in a few years.
31 Chapter 11 of Understanding Cryptography by Christof Paar and Jan Pelzl
