Hush Functions
CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapter 5)
Ryszard Janicki
Hash Functions 1/21
Motivation I
Notation
Sign message M with Alice’s private key: [M]Alice Encrypt message M with Alice’s public key: {M}Alice
Suppose Alice signs M
Alice sends M and S = [M]Alice to Bob Bob verifies that M = {S}Alice
Can Alice just send S?
If M is big, [M]Alice costly to compute and send.
Suppose instead, Alice signs h(M), where h(M) is a much smaller “fingerprint” of M
Alice sends M and S = [h(M)]Alice to Bob Bob verifies that h(M) = {S}Alice
Ryszard Janicki
Hash Functions 2/21
Motivation II
So, Alice signs h(M)
That is, Alice computes S = [h(M)]Alice
Alice then sends (M,S) to Bob Bob verifies that h(M) = {S}Alice
What properties must h(M) satisfy?
Suppose Trudy (attacker) finds M′ so that h(M) = h(M′) Then Trudy can replace (M, S) with (M′, S)
Does Bob detect this tampering?
No, since h(M′) = h(M) = {S}Alice
Ryszard Janicki
Hash Functions 3/21
Crypto Hash Functions
Crypto hash function h(x) must provide Compression – output length is small
Efficiency – h(x) easy to compute for any x
One-way – given a value y it is infeasible to find an x such that h(x) = y
Weak collision resistance – given x and h(x), infeasible to find y ̸= x such that h(y) = h(x)
Strong collision resistance – infeasible to find any x and y, with x ̸= y such that h(x) = h(y)
Lots of collisions exist, but hard to find any
Ryszard Janicki
Hash Functions 4/21
Birthday Problem
Suppose there are N people in a room (assume 365 days) How large must N be before the probability someone has
same birthday as me is ≥ 1/2? Solution: 1−(364)N =1 =⇒ N=253
365 2
How many people must be in a room before probability is
≥ 1/2 that any two (or more) have same birthday? 1−365·364···365−N+1=1 =⇒ N=23
365 365 365 2 Intuitively it should be about (slightly bigger) than
365 = 19.105 since we compare all pairs of x and y, and there are possible 365 birthdays.
√
Ryszard Janicki
Hash Functions 5/21
Hashes and Birthdays
If h(x) is N bits, then 2N different hash values are possible √NN
So, if you hash about 2 = 2 2 values then you expect to
find a collision
Implication? “Exhaustive search” attack. . . N
Secure N -bit hash requires 2 2 work to “break”
Recall that secure N-bit symmetric cipher has work factor of
2N −1
To prevent this attack, we could choose a hash function for
which N, the size of the hash function output, is so large that N
the attacker cannot compute 2 2 hashes.
Ryszard Janicki
Hash Functions 6/21
Non-crypto Hash 1
Data X = (X1,X2,X3,…,Xn), each Xi is a byte Define h(X) = (X1 +X2 +X3 +…+Xn) mod 256 Is this a secure cryptographic hash?
Example: X = (10101010, 00001111)
Hash is h(X ) = 10111001
If Y = (00001111, 10101010) then h(X ) = h(Y ) Easy to find collisions, so not secure
Versions of it are often used in algorithm courses as an example of hash functions, as otherwise it has “nice” properties
In many applications, the hash functions do not need to be secure!
Ryszard Janicki
Hash Functions 7/21
Non-crypto Hash 2
Data X = (X0,X1,X2,…,Xn−1) Suppose hash is defined as
h(X) = (nX1+(n−1)X2+(n−2)X3+…+2Xn−1+Xn) mod 256
Is this a secure cryptographic hash?
Note that h(10101010, 00001111) ̸= h(00001111, 10101010)
But hash of (00000001, 00001111) is same as hash of (00000000, 00010001)
Not “secure”, but this hash is used in several (non-crypto) applications
Ryszard Janicki
Hash Functions 8/21
Popular Cryptograhic Hashes
MD5 – 128 bit output
SHA-1 – 160 bit output. A U.S. government standard, inner
workings similar to MD5
Many other hashes, but MD5 and SHA-1 are the most widely used, however they are both rather lengthy and not so easy to present, we will present their more elegant and systematic version TIGER.
Hashes work by hashing message in bloc
Ryszard Janicki
Hash Functions 9/21
Cryptographic Hash Design
Desired property: avalanche effect:
Change to 1 bit of input should affect about half of output bits
Crypto hash functions consist of some number of rounds We want security and speed
“Avalanche effect” after few rounds But simple rounds
Analogous to design of block ciphers
Ryszard Janicki
Hash Functions 10/21
Tiger Hash
“Fast and strong” Design criteria
Secure
Optimized for 64-bit processors
Easy replacement for MD5 or SHA-1
Like MD5/SHA-1, input divided into 512 bit blocks (padded)
Unlike MD5/SHA-1, output is 192 bits (three 64-bit words) Truncate output if replacing MD5 or SHA-1
Intermediate rounds are all 192 bits
4 S-boxes, each maps 8 bits to 64 bits A “key schedule” is used
Ryszard Janicki
Hash Functions 11/21
Tiger Outer Round
Input X = (X0,X1,…,Xn−1), X is padded and each Xi is 512 bits.
Tiger Outer Round
a
b
c
Xi
W
W W
There are n iterations of diagram at
F5
left – one for each input block.
Input is X
Initially a = 0x0123456789ABCDEF,
o X = (X0,X1,…,Xn-1)
b = 0xFEDCBA9876543210.
o X is padded
c = 0xF096A5B4C3B2E187 in hex.
F7
o Each X is 512 bits Final (a, b, ci ) is hash.
There are n iterations
Each function F5, F7, F9 consists of 8
of diagram at left
F9
key schedule
key schedule
inner rounds as illustrated next. o One for each input block
a
b
c
W = (w0,w1,…,w7), with each wi
of 64 bits, is 512 bit input to the inner
Initial (a,b,c) constants
rounds.
Final (a,b,c) is hash
W is changed twice by key schedule.
a
b
c
Looks like block cipher!
Part 1 Cryptography 175
Outer round looks like block cipher.
Ryszard Janicki
Hash Functions 12/21
Tiger Inner Rounds
Tiger Inner Rounds
All lines are 64 bits. W = (w0,w1,…,w7).
Each F consists of m
b
Each f is a function of a,b,c,w and m. m,i i
precisely 8 rounds
Input values of a, b, c are from previous round, and
fm,0
their permutations for i = 0,1,…,7 are: 512 bit input W to F
0 : (a,b,e), 1 : (b,c,a), 2 : (c,a,b), 3 : (a,b,c),
4 : (b,c,a), 5 : (c,a,b), 6 : (a,b,c), 7 : (b,c,a). o W=(w ,w ,…,w )
And c = (c , c , . . . , c ). 017
017
o W is one of the input
Output of f is (−, +, · are numerical operators):
fm.1
fm,2
m,i blocks X
i
c = c ⊕ wi
a = a − (S0[c0] ⊕ S1[c2] ⊕ S2[c4] ⊕ S3[c6])
All lines are 64 bits
b = b + (S3[c1] ⊕ S2[c3] ⊕ S1[c5] ⊕ S0[c7])
b=b·m m,i
The f depend on the
Each Si is S-box: 8 bits mapped to 64 bits. S-boxes (next slide)
Details will not be discussed. Si ’s are not easy to program in hardware.
m
a
fm,7
b
c
w0 w1 w2
w7
a
c
Part 1 Cryptography Ryszard Janicki
Hash Functions 13/21
176
Tiger Hash Key Schedule
Bits operators: x,<<,>> 100110 = 011001
100110 << 2 = 011000
100110 >> 2 = 001001
100110 << 2 = 011001 << 2 = 100100
Input W = (w0,w1,...,w7)
−, +, · are numerical operators.
Small change in W will produce large change in key schedule output.
Table 5.1: Tiger "Key Schedule"
w 0 := w0 - {w7Θ 0xA5A5A5A5A5A5A5A5) W\ ■= W\ ®w0
W2 ■= X2 + W\ w3 ■■ 2
= W3-{WΘ(wi<19)) W4■= WA®W3
w5 ■=w5+ Wi
w6 = we - {w5 φ (w4 > 23))
wr = wr ®w6
w0 = w0 + wr
W\ = W\-{woφ{w7<19))
W2 = W2ffiwi
w3 = W3 + W2
W4 = Wi - {w3 Θ (w2 » 23))
w5 = w5 ®Wi
we= we+w5
u>r= wr – {weΘ 0x0123456789ABCDEF)
Trudy from changi
Ryszard Janicki
g the hash value. Perhaps the most obv
Hash Functions 14/21
n
Tiger Hash Summary
Hash and intermediate values are 192 bits 24 (inner) rounds
S-boxes: Claimed that each input bit affects a, b and c after 3 rounds
Key schedule: Small change in message affects many bits of intermediate hash values
Multiply: Designed to ensure that input to S-box in one round mixed into many S-boxes in next
S-boxes, key schedule and multiply together designed to ensure strong avalanche effect
Uses lots of ideas from block ciphers
S-boxes
Multiple rounds
Mixed mode arithmetic
At a higher level, Tiger employs
Confusion (obscure relationship between plaintext and ciphertext)
Diffusion (spread plaintext statistics through the ciphertext)
Ryszard Janicki
Hash Functions 15/21
Data Integrity wrt Cryptography and MAC (Repetition)
Integrity – detect unauthorized writing (i.e., detect unauthorized mod of data)
Example: Inter-bank fund transfers
Confidentiality may be nice, integrity is critical Encryption provides confidentiality (prevents unauthorized
disclosure)
Encryption alone does not provide integrity Message Authentication Code (MAC)
Used for data integrity
Integrity not the same as confidentiality
MAC is computed as CBC residue
That is, compute CBC encryption, saving only final
ciphertextblock, the MAC
The MAC serves as a cryptographic checksum for data
Ryszard Janicki
Hash Functions 16/21
MAC Computation (Repetition)
MAC computation (assuming N blocks)
C0 =E(IV ⊕P0,K),C1 =E(C0 ⊕P1,K),C2 =
E(C1 ⊕P2,K),…,CN−1 =E(CN−2 ⊕PN−1,K)=MAC Send IV,P0,P1,…,PN−1 and MAC
Receiver does same computation and verifies that result agrees with MAC
Both sender and receiver must know K
Suppose Alice has 4 plaintext blocks
Alice computes
C0 =E(IV ⊕P0,K),C1 =E(C0 ⊕P1,K),C2 =
E(C1 ⊕P2,K),C3 =E(C2 ⊕P3,K)=MAC
Alice sends IV , P0, P1, P2, P3 and MAC to Bob
Suppose Bad Trudy changes P1 to X
Bob computes C0 = E(IV ⊕P0,K),C1 = E(C0 ⊕X,K),C2 = E(C1 ⊕P2,K),C3 =E(C2 ⊕P3,K)=MAC ̸=MAC
It works since error propagates into MAC
Trudy can not make MAC = MAC without K
Ryszard Janicki
Hash Functions 17/21
HMAC I
Can Alice protect the integrity of M by simply computing h(M) and sending both M and h(M) to Bob? Note that if M changes, Bob will detect the change, provided that h(M) has not changed (and vice versa).
However, if Trudy replaces M with M′ and also replaces h(M) with h(M′), then Bob will have no way to detect the tampering.
Obvious solution: Alice sends E(h(M),K) to Bob, however, a slightly different approach is actually used to compute a hashed MAC, or HMAC.
Instead of encrypting the hash, we directly mix the key into M when computing the hash, so HMAC is a keyed hash.
How to compute HMAC?
Two obvious choices: h(K,M) and h(M,K).
Ryszard Janicki
Hash Functions 18/21
HMAC II
Should we compute HMAC as h(K,M) ?
Hashes computed in blocks:
h(B1, B2) = F (F (A, B1), B2) for some F (for example Tiger Hash) and constant A.
Then h(B1, B2) = F (h(B1), B2)
Let M′ = (M,X)
Then h(K,M′) = F(h(K,M),X)
Attacker can compute HMAC of M′ without K
Is h(M,K) better?
Yes, but. . . if h(M′) = h(M) then we might have
h(M,K) = F(h(M),K) = F(h(M′),K) = h(M′,K) Hence some improvement is necessary!
Ryszard Janicki
Hash Functions 19/21
Correct HMAC
Described in RFC 2104
Let B be the block length of hash, in bytes
B = 64 for MD5 and SHA-1 and Tiger ipad = 0x36 repeated B times
opad = 0x5C repeated B times
Then
HMAC(M,K)=h(K ⊕opad,h(K ⊕ipad,M))
Ryszard Janicki
Hash Functions 20/21
Hash Uses
Authentication (HMAC)
Message integrity (HMAC)
Message fingerprint
Data corruption detection
Digital signature efficiency
Anything you can do with symmetric crypto Also, many, many clever/surprising uses
Ryszard Janicki
Hash Functions 21/21