Method 2
• Initially set the -bit hash value to zero.
• Process each successive -bit block of data as follows:
o Rotate the current hash value to the left by one bit.
o XOR the block into the hash value
Birthday Attacks
Birthday paradox
• The birthday paradox is often presented in elementary probability courses to
demonstrate that probability results are sometimes counterintuitive.
• What is the minimum value of k such that the probability is greater than 0.5 that
at least two people in a group of k people have the same birthday?
• Ignore February 29 and assume that each birthday is equally likely
Birthday Attack
• The source, A, is prepared to "sign" a message by appending the appropriate
m-bit hash code and encrypting that hash code with A's private key
• The opponent generates 2m/2 variations on the message, all of which convey essentially the
same meaning
o The opponent prepares an equal number of messages, all of which are
variations on the fraudulent message to be substituted for the real one.
• The two sets of messages are compared to find a pair of messages that produces the same
hash code.
o The probability of success, by the birthday paradox, is greater than 0.5.
o If no match is found, additional valid and fraudulent messages are generated until a
match is made
• The opponent offers the valid variation to A for signature.
o This signature can then be attached to the fraudulent variation for transmission to the
intended recipient
o Because the two variations have the same hash code, they will produce the
same signature; the opponent is assured of success even though the
encryption key is not known
Meet in the middle attack possible
Security of Hash Functions and Macs
• Brute-force Attack
o Hash Function
o Message Authentication Codes
• Cryptanalysis
o Hash Functions
o Message Authentication Codes
Brute-Force Attacks
• The nature of brute-force attacks differs somewhat for hash functions and MACs
Hash Functions
The strength of a hash function against brute-force attacks depends solely on the
length of the hash code produced by the algorithm
there are three desirable properties
Property Description Effort Needed
One-way For any given code h, it is computationally infeasible
to find x such that H(x) = h
2n
Weak
collision
resistance
For any given block x, it is computationally
infeasible to find y ≠ x with H(y) = H(x). 2n
Strong
collision
resistance
It is computationally infeasible to find any
pair (x, y) such that H (x) = H(y). 2n/2
Message Authentication Codes
• A brute-force attack on a MAC is a difficult undertaking because it requires known
message-MAC pairs
• Security of the MAC algorithm depends on the relative size of the key and the MAC.
• we need to state the desired security property of a MAC algorithm
Computation resistance
Given one or more text-MAC pairs [xi, C(K, xi)], it is computationally infeasible to compute
any text-MAC pair [x, C(K, x)] for any new input x ≠ xi
There are two lines of attack possible:
• Attack the key space
• attack the MAC value
Cryptanalysis
an ideal hash or MAC algorithm will require a cryptanalytic effort greater than or equal to the
brute-force effort
Hash Functions
General Structure of Secure Hash Code
• The hash function takes an input message and partitions it into L fixed-sized blocks of b bits
each.
• If necessary, the final block is padded to b bits.
• The final block also includes the value of the total length of the input to the hash function.
• The inclusion of the length makes the job of the opponent more difficult.
• Either the opponent must find two messages of equal length that hash to the same value or
two messages of differing lengths that, together with their length values, hash to the same
value.
• The hash algorithm involves repeated use of a compression function, f,
Message Authentication Codes
• There is much more variety in the structure of MACs than in hash functions
• Hence it is difficult to generalize about the cryptanalysis of MACs.
• far less work has been done on developing such attacks
MD5
MD5 Overview
• pad message so its length is 448 mod 512
• append a 64-bit length value to message
• initialise 4-word (128-bit) MD buffer (A,B,C,D)
• process message in 16-word (512-bit) blocks:
o using 4 rounds of 16 bit operations on message block & buffer
o add output to buffer input to form new buffer value
• output hash value is the final buffer value
MD5 Compression Function
• each round has 16 steps of the form:
• a = b+((a+g(b,c,d)+X[k]+T[i])<<<s)
• a,b,c,d refer to the 4 words of the buffer
o this updates 1 word only of the buffer
o after 16 steps each word is updated 4 times
• where g(b,c,d) is a different nonlinear
function in each round (F,G,H,I)
• T[i] is a constant value derived from sin
Strength of MD5
• MD5 hash is dependent on all message bits
• Rivest claims security is good as can be
• known attacks are:
o Berson 92 attacked any 1
round using differential
cryptanalysis (but can’t
extend)
o Boer & Bosselaers 93 found a
pseudo collision (again unable to
extend)
o Dobbertin 96 created collisions
on MD compression function
(but initial constants prevent
exploit)
• conclusion is that MD5 looks vulnerable soon
Processing 512 Bit Block
Secure Hash Algorithm (SHA)
Comparison of SHA Parameters
Overview
• most widely used hash function
• produces 160-bit hash values
• based on MD5
• The input is a message with length is < 2^64 bits
• The output is a message digest of length 160 bit
• The processing is done 512 bit blocks
Algorithm
Processing of a single 512-bit block
Single Round Function
Steps
Step 1: Append Padding Bits
Message is “padded” with a 1 and as many 0’s as necessary to bring the message length
to 64 bits fewer than an even multiple of 512
Step 2: Append Length
64 bits are appended to the end of the padded message. These bits hold the binary
format of 64 bits indicating the length of the original message
Step 3: Initialize MD buffer
• 160 bit buffer is used to hold the intermediate and final results
• The buffer is represented as 5 – 32 bit registes A, B, C, D, E
• Initialized as A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476, E =
0xC3D2E1F0
Step 4: Process the message in 512 bit word blocks
Step 1: Append Padding Bits
Message is “padded” with a 1 and as many 0’s as necessary to bring the message length
to 64 bits fewer than an even multiple of 512
Step 2: Append Length
64 bits are appended to the end of the padded message. These bits hold the binary
format of 64 bits indicating the length of the original message
Step 3: Initialize MD buffer
• 160 bit buffer is used to hold the intermediate and final results
• The buffer is represented as 5 – 32 bit registes A, B, C, D, E
• Initialized as A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476, E =
0xC3D2E1F0
Step 4: Process the message in 512 bit word blocks
• The number of rounds = 4
• Each round has 20 steps
• Four different logical functions f1, f2, f3 and f4
• Each round makes use of additive constant Kt where 0 < t < 79
• 4 different constants are used 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6
• The output of the 80th round is added to the input to the 1st round to produce the output
Step 5: Output
• After all 512 bit block is processed, the output from the Lth stage is 160 bit message
digest
• CV0 = IV
• Yq+1 = sum32 (CVq, ABCDEq)
• MD = CVL
• IV: Initial value of the ABCDE buffer
• ABCDEq = Output of the last round of processing of the qth block
• L = The no of blocks (after padding and appending length)
• Sum32 = Addition modulo 2^32 done on each word separately
• MD = Final Message Digest
SHA-1 Compression Function
Describe the picture
Comparison of SHA-1 and MD5
Security against Brute Force Attack
• SHA, operations are 2 ^ 160
• MD5, operations are 2 ^ 128
• It is difficult to have same message digest for 2 different messages
• brute force attack is harder for SHA-1(160 vs 128 bits for MD5)
Security against crypt analysis
• MD5 is vulnerable, SHA1 is not vulnerable
Speed
• MD5 executes faster when compared to SHA1 due to less bits needed, 64 steps versus 80
steps
• Both depend on addition modulo of 2^32 and could run well on 32 bit processors
Simplicity and Compactness
• Both are simple to describe and implement
• MD5 uses little endian, SHA 1 uses big endian
RACE Integrity Primitives Evaluation Message Digest (RIPEMD)
• RIPEMD-160 was developed in
Europe as part of RIPE project in
96
• by researchers involved in attacks on MD4/5
• initial proposal strengthen
following analysis to become
RIPEMD-160
• somewhat similar to MD5/SHA
• uses 2 parallel lines of 5 rounds of 16 steps
• creates a 160-bit hash value
• slower, but probably more secure, than SHA
RIPEMD-160 Overview
• pad message so its length is 448 mod 512
• append a 64-bit length value to message
• initialise 5-word (160-bit) buffer (A,B,C,D,E) to
• (67452301, efcdab89,98badcfe,
• 10325476, c3d2e1f0)
• process
message in 16-
word (512-bit)
chunks:
• use 10 rounds of 16-bit operations on
message block & buffer – in 2 parallel lines
of 5
• add output to
input to form new
buffer value
• output hash value is the final buffer value
RIPEMD-160 Compression Function
Refer Picture
RIPEMD-160 Design Criteria
• use 2 parallel lines of 5 rounds for increased complexity
• for simplicity the 2 lines are very similar
• step operation very close to MD5
• permutation varies parts of message used
• circular shifts designed for best results
RIPEMD-160 verses MD5 & SHA-1
• brute force attack
harder (160 like
SHA-1 vs 128 bits
for MD5)
• not vulnerable to
known attacks, like
SHA- 1 though
stronger (compared
to MD4/5)
• slower than MD5 (more steps)
• all designed as simple and compact
• SHA-1 optimised for big endian CPU's vs
RIPEMD-160 & MD5 optimised for little endian CPU’