Chapter 9 – Hash Functions
Dr. Safi Ibrahim
Content of this Chapter
• Why we need hash functions
• How does it work
• Security properties
• Algorithms
• Example: The Secure Hash Algorithm
SHA-1
2/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Content of this Chapter
• Why we need hash functions
• How does it work
• Security properties
• Algorithms
• Example: The Secure Hash Algorithm
SHA-1
3/22 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
• For more info see Section 11.1 in “Understanding
Cryptography”.
Solution:
Instead of signing the whole message, sign only a digest
(=hash)
Also secure, but much faster
4/22 Needed: Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Hash Functions
Digital Signature with a Hash Function
xi
Notes:
zi = h( xi || zi-1 ) • x has fixed length
• z, y have fixed length
• z, x do not have equal length in
z general
• h(x) does not require a key.
sigkprz)
• h(x) is public.
y = sigkpr(z)
5/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Basic Protocol for Digital Signatures with a Hash Function:
Alice
Kpub
Bob
z = h(x)
s = sigKpr (z)
(x, s)
z' = h(x)
verKpu (s,z')=true/false
b
6/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Principal input–output behavior of hash functions
7/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Content of this Chapter
• Why we need hash functions
• How does it work
• Security properties
• Algorithms
• Example: The Secure Hash Algorithm
SHA-1
8/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
The three security properties of hash functions
9/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Hash Funktionen: 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.
• Second preimage resistance: Given x1, and thus h(x1), it is
computa- tionally 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).
10/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Content of this Chapter
• Why we need hash functions
• How does it work
• Security properties
• Algorithms
• Example: The Secure Hash Algorithm
SHA-1
11/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Hash Funktionen: Algorithms
Hash
Algorithms
Special based on
Algorithms, block
e.g. MD5 - ciphers
family
• MD5 - family
• SHA-1: output - 160 Bit; input - 512 bit chunks of message x;
operations - bitwise AND, OR, XOR, complement und 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.
12/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Content of this Chapter
• Why we need hash functions
• How does it work
• Security properties
• Algorithms
• Example: The Secure Hash Algorithm SHA-1
13/22 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.
• 160-bit output from a message of maximum
length 264 bit.
• Widely used ( even tough some
weaknesses are known)
14/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
SHA-1 High Level Diagramm
• Compression Function consists of 80 rounds which are
divided into four stages of 20 rounds each
15/22 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 bit.
• k ≡ 512 − 64 − 1 − l = 448 − (l + 1) mod 512.
16/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
Hash Algorithms based on Block Cipher
Lessons Learned: Hash-Funktionen
• 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.
22/22 Chapter 11 of Understanding Cryptography by Christof Paar and Jan
Pelzl
