Authentication Function 2: Message Authentication Code

Authentication Function 2: Message Authentication Code

Message Authentication Code (MAC) • generated by an algorithm that creates a small fixed-sized block – depending on both message and some key – like encryption though need not be reversible (receiver also recomputes it. No decryption needed) • appended to message as a signature • receiver performs same computation on message and checks it matches the MAC • provides assurance that message is unaltered and comes from sender – Message: M – Shared secret key: K – MAC function: C

Message Authentication Code (MAC) •

If we assume that only receiver and sender knows the key, and if received MAC matches the calculated MAC, then

3. the receiver is assured that the message has not been altered 4. the receiver is assured that the message is from alleged sender. 5. the attacker cannot alter the sequence number

Message Authentication Code (I)

MAC

MAC=

Message Authentication Code (II)

MAC

MAC=

Message Authentication Code (III)

MAC

MAC=

Importance of MAC

• as shown the MAC provides confidentiality • can also use encryption for secrecy – generally use separate keys for each – can compute MAC either before or after encryption – is generally regarded as better if done before • why use a MAC? – sometimes only authentication is needed

Uses of MAC • Same message is broadcasts to a number of destinations. eg. alarm signal in a military control server. • Time can be reduced in case of decrypting all incoming messages. • It can save the processor resource and give assurance of the integrity of the program

MAC Properties • a MAC is a cryptographic checksum MAC = CK(M) – condenses a variable-length message M – using a secret key K – to a fixed-sized authenticator • is a many-to-one function – potentially many messages have same MAC

Properties of MAC Function • A MAC function is similar to encryption. But, it need not be reversible, as it must be for decryption. • For n-bit MAC, there are 2n possible MACs. But there might be N >> 2n possible messages. So, it is a many-toone function. – e.g. 100-bit messages and we use a 10-bit MAC. There are 2100 different messages but only 210 different MACs. On average, each MAC represents 2100/210=290 different messages. • It turned out that MAC is less vulnerable to be broken than encryption.

Requirements for MAC Functions • •

taking into account the types of attacks Brute-force technique to discover the authentication key is as hard as decryption without key – Suppose key size > MAC size (k>n). Given a known plaintext M1 and its MAC1=CK(M1): • attacker may generate MACi=CKi(Mi) for all 2k keys. The opponent generates 2k MACs. But there are only 2n real MAC values. • On average a total of 2k/2n=2(k-n) keys will produce a match

Requirements for MAC Functions cont’ • and the opponent wouldn’t know which one is correct. • m round where k=m.n is needed to find the key. • Need the MAC to satisfy the following: 1.knowing a message and MAC, is infeasible to find another message with same MAC 2.MACs should be uniformly distributed 3.MAC should depend equally on all bits of the message

Hash Functions • A one-way hash function can be used as the message authentication code. • Other names: compression function, contraction function, message digest, fingerprint, cryptographic checksum, message integrity check (MIC), modification detection code (MDC). • condenses arbitrary message to fixed size, H(M) • usually assume that the hash function is public and not keyed – Contrary to the MAC which is keyed • hash used to detect changes to message

Hash Functions (I)

Hash Functions (II)

Hash Functions (III)

Hash Functions (IV)

Hash Functions (V)

S: Common secret value (If attacker can do H-1(C)=S||M, then having also M, he can easily find S)

Hash Functions (VI)

S: Common secret value

Hash Function Properties • a Hash Function produces a fingerprint of some file/message/data h = H(M) • condenses a variable-length message M to a fixed-sized fingerprint • assumed to be public

Requirements for Hash Functions 1. 2. 3. 4.

can be applied to any sized message M produces fixed-length output h is easy to compute h=H(M) for any message M given h is infeasible to find x s.t. H(x)=h • one-way property (level of effort needed by attacker ≈ 2m for hash code of length m) 5. given x is infeasible to find y s.t. H(y)=H(x) • weak collision resistance (level of effort needed 2m) 6. is infeasible to find any x,y s.t. H(y)=H(x) • strong collision resistance (level of effort needed 2m/2)

Simple Hash Functions • are several proposals for simple functions • based on XOR of message blocks – e.g. longitudinal redundancy check is a simple parity for each bit position Ci=bi1 ⊕ bi2 ⊕ … ⊕ bim • not secure since can manipulate bits (bij) in message that either not change hash code (C) or change the hash itself • need a stronger cryptographic function (Chapter 12)

The Secure Hash Algorithm (SHA-1) SHA-1 A message composed of b bits

160-bit message digest

Step 1 -- Padding Padding  the total length of a padded message is multiple of 512 Every message is

Padding (cont.) Message

1

zeros

1 bit

Multiple of 512

Message length

64 bits

Padding (cont.) Padding is done by appending to the input: A single bit, 1 Enough additional bits, all 0, to make the final 512 block exactly 448 bits long A 64-bit integer representing the

Example

 M = 01100010 11001010 1001 (20 bits)  Padding is done by appending to the input: A single bit, 1 427 0s A 64-bit integer representing 20  Pad(M) = 01100010 11001010 10011000 … 00010100

Example  Length of M = 500 bits  Padding is done by appending to the input: A single bit, 1 459 0s A 64-bit integer representing 500  Length of Pad(M) = 1024 bits

Message Digest Generation Using SHA-1

SHA-1 Processing of single 512Bit Block

SHA Overview • • •

4.

5.

pad message so that we have: length mod 512 = 448 or equivalently length ≡ 448 (mod 512) append a 64-bit length value to message initialize 5-word (160-bit) buffer (A,B,C,D,E) to the following using big-endian format: (67452301, efcdab89, 98badcfe, 10325476, c3d2e1f0) process message in 16-word (512-bit) chunks: – expand 16 words into 80 words by mixing & shifting – use 4 rounds of 20 bit operations on message block & buffer – add output to input to form new buffer value output hash value is the final buffer value

Single 512-Bit Block Function in SHA-1

Summary of SHA-1 Behavior • The SHA-1 behaviour can be summarized as: – CV0 = IV – CVq+1= SUM32 [CVq, ABCDEq] – MD = CVL • Where: – IV: Initial value (stored in ABCDE buffers) – ABCDEq: the output of the last round of processing in the qth 512-bit block of the message – L: number of blocks in the message (including padding and the length fields) – CVq: chaining variable processed with the qth block – SUM32: addition mod 232 performed separately on each word of the pair of inputs – MD: final message digest value

SHA-1 Compression Function • each round has 20 steps which replaces the 5 buffer words thus: [A,B,C,D,E] [(E+f(t,B,C,D)+S5(A)+Wt+Kt),A,S30(B),C,D] • a,b,c,d refer to the 4 words of the buffer • t is the step number (0≤t≤79) • Sk: circular left-shift (rotation) of the 32-bit argument by k bits (same as “<<< k”) • f(t,B,C,D) is a nonlinear function for round • Wt is derived from the message block • Kt is a additive constant value derived from integer part of 232 x i0.5 for i=2,3,5,10. • All +’s are modulo 232 additions

SHA-1 Compression Function

Circular Left Shift (rotation) by k bits

Logical Functions f

• In terms of logical operations: – – – –

0≤t≤19 20≤t≤39 40≤t≤59 60≤t≤79

f1= f2= f3= f4=

f(t,B,C,D)= f(t,B,C,D)= f(t,B,C,D)= f(t,B,C,D)=

BC + B’D B ⊕ C ⊕ D BC + BD + CD B ⊕ C ⊕ D

Additive Constant Kt • Only 4 distinct constants are used:

Hash Algorithms

Hash Algorithms • see similarities in the evolution of hash functions & block ciphers – increasing power of brute-force attacks – leading to evolution in algorithms – from DES to AES in block ciphers – from MD4 & MD5 to SHA-1 & RIPEMD160 in hash algorithms

• likewise tend to use common iterative structure as do block

MD5/MD4 Algorithm

MD5 • designed by Ronald Rivest (the R in RSA – Rivest-Shamir-Adleman) • latest in a series of MD2, MD4 • produces a 128-bit hash value • until recently was the most widely used hash algorithm – in recent times have both brute-force & cryptanalytic concerns

• specified as Internet standard

MD5 Overview • Step 1: pad message so that we have: length mod 512 = 448 or equivalently length ≡ 448 (mod 512) – The above makes the length of padded message to be 64 bits less than an integer multiple of 512 bits. – Padding is always added even if the message is already of the desired length. e.g. if the message is 448 bits long, it is padded by 512 bits to a length of 960 bits. – Number of padding bits is in range of 1 to 512 bits. – Padding is a single “1” followed by the necessary number of “0”s

MD5 Overview (cont.) • Step 3: initialize 4-word (128-bit) MD buffer (A,B,C,D) to given values: – A=67452301, B=EFCDAB89, C=98BADCFE, D=10325476 Save the values in little-endian format (the least significant byte of a word in the low-address position) – Word A= 01 23 45 67, Word B= 89 AB CD EF, – Word C= FE DC BA 98 , Word D= 76 54 32 10 • Step 4: process message in 16-word (512-bit) blocks: – using 4 rounds of 16 bit operations on message block & buffer – add output to buffer input to form new buffer

MD5 Structure

Single 512-bit (HMD5) Block

Summary of MD5 Behavior • The MD5 behaviour can be summarized as: – CV0 = IV – CVq+1= SUM32[CVq,RFI(Yq,RFH(Yq,RFG(Yq,RFF(Yq,CVq))))] – MD = CVL-1 • Where: – IV: Initial value (stored in ABCD buffers) – Yq: the qth 512-bit block of the message – L: number of blocks in the message – CVq: chaining variable processed with the qth block – RFx: round function using primitive logical function x – SUM32: addition mod 232 performed separately on each word of the pair of inputs

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, but used in varying permutations – note this updates 1 word only of the buffer – 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) (see book for details) • X[k]=M[q*16+k]=the kth 32-bit word in the qth 512-bit block of the message • T[i] is a constant value derived from sin, that is T[i] = 232 * abs[sin(i)] and can be found in a lookup table (matrix T) • <<< s is circular shift of the 32-bit argument by s bits

SHA-1 versus MD5 • brute force attack is harder (160 vs 128 bits for MD5) • not vulnerable to any known attacks (compared to MD4/5) • a little slower than MD5 (80 vs 64 steps) • both designed as simple and compact • optimized for big-endian CPU's (vs

Summary of SHA-384

Summary of SHA-512