Thu29-06-06_01

Views:

Category: Entertainment

Presentation Description

No description available.

Presentation Transcript

How to Smoke Hash (Functions) :

How to Smoke Hash (Functions) Phil Hawkes Qualcomm International (Australia) [email protected] 2006-06-29

The Recent Attacks :

© Phil Hawkes 2006 [email protected] 2 The Recent Attacks Collision Attacks only That is, two files x,y hash to same value: h(x) = h(y) Relevant to digital signatures E.g. Certificates Several practical examples using MD5 See Stefan’s talk yesterday Other applications still OK E.g. Key generation, challenge/response authentication

The Recent Attacks :

© Phil Hawkes 2006 [email protected] 3 The Recent Attacks

Outline :

© Phil Hawkes 2006 [email protected] 4 Outline (I will focus on SHA-1 Attacks) Description Differential Attacks Analysis of Components Operations , +, rotate Round-dependent Functions Step Function  Differential Patterns Message Expansion  Disturbance Vectors The Fun stuff: the first round…

Phases :

© Phil Hawkes 2006 [email protected] 5 Phases Input: data string of length L 4 phases Padding, Parsing, Message Expansion, Step function Padding: add zeroes and L to make a multiple of 512 bits Parsing Partition into message blocks 512 bits long Padding and parsing ignored

Msg expansion and Step Function :

© Phil Hawkes 2006 [email protected] 6 Msg expansion and Step Function 512-bit Message Block = 16 x 32-bit words Sequence of 32-bit Expanded-Message Words Input State Internal State Step Function Message Expansion Internal State Step Function Internal State Step Function Internal State Next Input State

SHA-0/1:Message Expansion :

© Phil Hawkes 2006 [email protected] 7 SHA-0/1:Message Expansion Expand m[0],…,m[15] to 80 expanded message words SHA-0 m[j] = m[i-3]  m[i-8]  m[i-13]  m[i-16]; SHA-1: m[j] = (m[i-3]  m[i-8]  m[i-13]  m[i-16]) <<< 1;

SHA-1 Step Function :

© Phil Hawkes 2006 [email protected] 8 SHA-1 Step Function Inputs to step i, i=1,2,…,80 Internal state: 5 words ai-1, bi-1, ci-1, di-1, ei-1 Exp-msg word: mi-1 Output: next internal state ai = ROTL(ai-1, 5)+ mi-1 + ei-1 + fi( bi-1, ci-1, di-1)+ ki; bi = ai-1; ci = ROTL(bi-1, 30); di = ci-1; ei = di-1; ROTL(X,r) = left rotation of X by r bits ki are constants (ignored hereon) Function fi() acts bitwise, depends on round

SHA-1 Step Function :

© Phil Hawkes 2006 [email protected] 9 SHA-1 Step Function ai-1 bi-1 ei-1 di-1 ci-1 ai bi ei di ci ROTL30 mi-1 Bit-wise fi ROTL5

SHA-0/1: Functions fi :

© Phil Hawkes 2006 [email protected] 10 SHA-0/1: Functions fi 4 Rounds, each with 20 steps fi (x,y,z) i Round F(x,y,z) = (x & y)  (x & z) [1,20] 1 G(x,y,z) = x  y  z; [21,40] 2 H(x,y,z) = xy  xz  yz; [41,60] 3 I(x,y,z) = x  y  z; [61,80] 4 F(x,y,z) aka IF: if(x==1) then F(x,y,z) = y else F(x,y,z) = z

Outline :

© Phil Hawkes 2006 [email protected] 11 Description Differential Attacks Analysis of Components Operations , +, rotate Round-dependent Functions Step Function  Differential Patterns Message Expansion  Disturbance Vectors The Fun stuff: the first round… Outline

Differential Attacks :

© Phil Hawkes 2006 [email protected] 12 Differential Attacks Input a first messages M’, Input a second message M” with changes Trace changes (Changes in) message blocks  message expansion (Changes in) expanded message words  step function (Introduce, modify or  cancel changes in) internal state

Differential Attacks: Diagram :

© Phil Hawkes 2006 [email protected] 13 Differential Attacks: Diagram Input State Step Function Message Expansion Step Function Step Function Next Input State Internal State Internal State Internal State Internal State

Outline :

© Phil Hawkes 2006 [email protected] 14 Outline Description Differential Attacks Analysis of Components Operations , +, ROTL Round-dependent Functions Step Function  Differential Patterns Message Expansion  Disturbance Vectors The Fun stuff: the first round…

© Phil Hawkes 2006 [email protected] 15 ADD Differences X is a variable X’ = value for first message X”= value for second message a’i = ROTL(a’i-1, 5) + m’i-1 + e’i-1 + fi( b’i-1, c’i-1, d’i-1 ) +ki a”i = ROTL(a”i-1, 5) + m”i-1+ e”i-1 + fi( b”i-1, c”i-1, d”i-1) +ki ADD difference: +X = X” – X’ (mod 232) +(X+Y) = +X+ +Y + ai = +ROTL(ai-1, 5) + +mi-1 + +ei-1+ +fi( bi-1, ci-1, di-1) ki cancel out

Slide 16:

© Phil Hawkes 2006 [email protected] 16 +ROTL ( ai-1, 5)? a’i-1, a”i-1 b’i-1, b”i-1 d’i-1, d”i-1 c’i-1, c”i-1 a’i, a”i b’i,b”i e’i,e”i d’i,d”i c’i,c”i ROTL30 m’i-1, m”i-1 f’i, f”i ROTL5 +mi-1? e’i-1, e”i-1 +di-1 +ci-1 +bi-1 +ai-1 +ei-1 +fi? +ei= +di= +ci? +bi= +ai +di-1 +ci-1 +ai-1 M’, M” Message Expansion Yellow indicates problem areas

Complications :

© Phil Hawkes 2006 [email protected] 17 Complications Message expansion Uses “” not “+” (SHA-1 also uses rotation) How do we determine +mi-1 from M’,M”? +ROTL(...) (what happens here?) +fi(ai-1,bi-1,ci-1) (acts bitwise) Need bit level information

XOR Differences :

© Phil Hawkes 2006 [email protected] 18 XOR Differences X = X”  X’ Specifies location of Bit-wise differences Linear w.r.t  and ROTL (X  Y) = X  Y ROTL( X,r ) =ROTL( X, r ): r always fixed Message expansion All operations linear w.r.t  M  mi-1 But we need +mi-1!!!! Also need +fi(ai-1,bi-1,ci-1), +ROTL(...)

Nabla representation X :

© Phil Hawkes 2006 [email protected] 19 Nabla representation X X[j] = @ if X”[j]  X’[j] + if (X”[j],X’[j]) = (1,0)  X”[j]- X’[j] = +1 - if (X”[j],X’[j]) = (0,1)  X”[j]- X’[j] = -1 * if X”[j] = X’[j] 0 if X”[j] = X’[j] = 0 1 if X”[j]  X’[j] = 1 +X = +,- X[j] 2j

Motivation :

© Phil Hawkes 2006 [email protected] 20 Motivation Bit3322222222221111111111 10987654321098765432109876543210 X’=00111010101010100101101010101000 X”=10101010011010010101100100101000 X=+01-1010-+1010-+010110-+-0101000 =10010000110000110000001110000000 += +231 -228 -223 +222 -217 +216 -29 +28 -27 = 1874787968 X’, X”  X  +X, X

Observations :

© Phil Hawkes 2006 [email protected] 21 Observations  ROTL(X,r) = ROTL(X,r) XOR diffs only where @,+,- ADD diff fully defined by +,- (& @ MSB only) Constant bits don’t affect XOR diff or Add diff Ignore constant bits for now. For given XOR diff,  multiple ADD diffs For given ADD diff,  multiple XOR diffs Exception is zero diff

Slide 22:

© Phil Hawkes 2006 [email protected] 22 ROTL(ai-1, 5)  ROTL30 ROTL5 +mi-1? ai-1 +fi? M’, M” Message Expansion ei-1 di-1 ci-1 bi-1 ai ei +ai bi ci= ROTL(bi-1,30) di m’i-1, m”i-1 fi  ? Solved Problems Remaining Problems

If XOR known, find ADD diffs :

© Phil Hawkes 2006 [email protected] 23 If XOR known, find ADD diffs Bit332222222222… 109876543210… =000100001100…0 0=***+****++**… +=+228 +223 +222 1=***+****+-**… +=+228 +223 -222 2=***+****-+**… +=+228 - 223 +222 3=***+****--**… +=+228 - 223 -222 4=***-****++**… +=-228 +223 +222 5=***-****+-**… +=-228 +223 -222 6=***-****-+**… +=-228 -223 +222 7=***-****--**… +=-228 -223 -222 Each is different addition difference

© Phil Hawkes 2006 [email protected] 24 Comments thus far… Note if there is diff in MSB, then both +/- give same ADD diff Message expansion For given bit changes in M (i.e. M)… …can determine mi-1 NOW, for known mi-1… … we know the possible +mi-1 … we can choose best option for+mi-1 We will come back to this if we have time!!!

Slide 25:

© Phil Hawkes 2006 [email protected] 25 ROTL(ai-1, 5) ROTL30 ROTL5 ai-1 +fi? Message Expansion ei-1 di-1 ci-1 bi-1 ai ei +ai bi ci= ROTL(bi-1,30) di Specify M  mi-1 fi ? Choose +mi-1  Solved Problems Remaining Problems

Given +=228 + 225 find XOR diffs :

© Phil Hawkes 2006 [email protected] 26 Given +=228 + 225 find XOR diffs 0=***+**+*… =00010010… 1=***+*+-*… =00010110… 2=***++--*… =00011110… 3=**+*---*… =00101110… 4=**+-**+*… =00110010… 5=**+-*+-*… =00110110… 6=**+-+--*… =00111110… 7=*+--**+*… =01110010… 8=*+--*+-*… =01110110… 9=*+--+--*… =01111110… A=*+-*---*… =01101110… B=+---**+*… =11110010… C=----**+*… =11110010… D=+---*+-*… =11110110… E=----*+-*… =11110110… etc Carry addition differences up to higher order bits Cancel with existing higher order differences or… Add to higher order differences

+ai-1 = 228 + 225, +ROTL(ai-1,5)=? :

© Phil Hawkes 2006 [email protected] 27 +ai-1 = 228 + 225, +ROTL(ai-1,5)=? 0=***+**+*… R0=*+*…***+* =230+21 1=***+*+-*… R1=+-*…***+*  +R0 2=***++--*… R2=--*…***++ =230+21+20 3=**+*---*… R3=--*…**+*-  +R2 4=**+-**+*… R4=*+*…**+-*  +R0 5=**+-*+-*… R5=+-*…**+-*  +R0 6=**+-+--*… R6=--*…**+-+  +R2 7=*+--**+*… R7=*+*…*+--*  +R0 8=*+--*+-*… R8=+-*…*+--*  +R0 9=*+--+--*… R9=--*…*+--+  +R2 A=*+-*---*… RA=--*…*+-*-  +R2 B=+---**+*… RB=*+*…+---*  +R0 C=----**+*… RC=*+*…----* =230-24-23-22-21 D=+---*+-*… RD=+-*…+---*  +R0 E=----*+-*… RE=+-*…----*  +RC etc

Slide 28:

© Phil Hawkes 2006 [email protected] 28 ROTL(ai-1, 5) ROTL30 ROTL5 ai-1 +fi? Message Expansion ei-1 di-1 ci-1 bi-1 ai ei +ai bi ci= ROTL(bi-1,30) di Specify M mi-1 fi Choose or Hope  Choose +mi-1  Solved Problems Remaining Problems

Outline :

© Phil Hawkes 2006 [email protected] 29 Outline Description Differential Attacks Analysis of Components Operations , +, rotate Round-dependent Functions Step Function  Differential Patterns Message Expansion  Disturbance Vectors The Fun stuff: the first round…

Bitwise Functions: Rounds 2,4 :

© Phil Hawkes 2006 [email protected] 30 Bitwise Functions: Rounds 2,4 Round 2: fi = G(bi-1,ci-1,di-1) =bi-1ci-1 di-1 Round 4: fi = I(bi-1,ci-1,di-1) =bi-1ci-1 di-1 fi = bi-1  ci-1  di-1 Bit diffs fully determined by bi-1, ci-1, di-1 NOW, for known bit diffs in fi… … we know the possible +fi … we can choose best option for+fi

Bitwise Functions: Round 3 :

© Phil Hawkes 2006 [email protected] 31 Bitwise Functions: Round 3 Round 3: fi = H(bi-1,ci-1,di-1) =bi-1ci-1  bi-1di-1  ci-1di-1 With some probability can approx fi = bi-1  ci-1  di-1 …which is specified by bi-1, ci-1, di-1 Once again, for known bit diffs in fi… … we know the possible +fi … we can choose best option for+fi

Rounds 2-4 (Steps 21-80) :

© Phil Hawkes 2006 [email protected] 32 Rounds 2-4 (Steps 21-80) Current Approach:… Approx effect of fi on differences by: fi = bi-1  ci-1  di-1 Hope for correct sign of bit differences +fi introduce or cancel correct ADD diffs on a bit by bit basis basically like probabilistic XORing

Slide 33:

© Phil Hawkes 2006 [email protected] 33 ROTL(ai-1, 5) ROTL30 ROTL5 ai-1 Hope +fi di-1 Message Expansion ei-1 di-1 ci-1 bi-1 ai ei +ai bi ci= ROTL(bi-1,30) di ci-1 bi-1 fi Specify M mi-1 Choose +mi-1 Hope Solved Problems

Slide 34:

© Phil Hawkes 2006 [email protected] 34 ROTL(ai-1, 5) ROTL30 ROTL5 ai-1 di-1 Message Expansion ei-1 di-1 ci-1 bi-1 ai ei +ai bi ci= ROTL(bi-1,30) di ci-1 bi-1 fi Specify M mi-1 Hope ei-1 Hope Choose Known Solved Problems

Linear Model :

© Phil Hawkes 2006 [email protected] 35 Linear Model Provided conditions hold… …differential acts like XOR for rounds 2-4 See figure on next slide. Conditions hold with some probability (discussed below)

Slide 36:

© Phil Hawkes 2006 [email protected] 36 ROTL( ai-1, 5) ROTL30 ROTL5 ai-1 Message Expansion ei-1 di-1 ci-1 bi-1 ei ai bi ci= ROTL(bi-1,30) di ci-1 bi-1 fi Specify M mi-1 Linear Model Hope Choose Hope

Outline :

© Phil Hawkes 2006 [email protected] 37 Outline Description Differential Attacks Analysis of Components Operations , +, rotate Round-dependent Functions Step Function  Differential Patterns Message Expansion  Disturbance Vectors The Fun stuff: the first round…

Difference Patterns: Rounds 2-4 :

© Phil Hawkes 2006 [email protected] 38 Difference Patterns: Rounds 2-4 Now we know how components affect differences Difference Pattern “Inject” a difference through mi-1 into ai Use differences in mi, mi+1,…, mi+4 to cancel difference being feedback through ri+1 = ROTL(ai, 5), +ai  0 fi+2(bi+1,ci+1,di+1), +bi+1 0 fi+3(bi+2,ci+2,di+2), +ci+2 0 fi+4(bi+3,ci+3,di+3), +di+2 0 ei+4, +ei+4  0

Difference Pattern: Example :

© Phil Hawkes 2006 [email protected] 39 Difference Pattern: Example

Combining Difference Patterns :

© Phil Hawkes 2006 [email protected] 40 Combining Difference Patterns Previous example showed single bit difference pattern Linear model allows combining difference patterns to form more complex patterns Combine multiple bit difference patterns… …at multiple steps! Rather than cancel bits using mi-1, use feedback difference to inject new difference Observe: highest probability = low weight

Combining Difference Patterns :

© Phil Hawkes 2006 [email protected] 41 Combining Difference Patterns For linear combination of injected differences… … required differences in mi-1 = same linear combination of diff patterns Recall: highest probability = low weight

Outline :

© Phil Hawkes 2006 [email protected] 42 Outline Description Differential Attacks Analysis of Components Operations , +, rotate Round-dependent Functions Step Function  Differential Patterns Message Expansion  Disturbance Vectors The Fun stuff: the first round…

Disturbance Vectors :

© Phil Hawkes 2006 [email protected] 43 Disturbance Vectors Linear model allows linear combinations of difference patterns Linear message expansion XOR differences in m0,…,m79 form a codeword Recall: highest probability = low weight Look for low weight codewords for Message Expansion

SHA-0 Message Expansion :

© Phil Hawkes 2006 [email protected] 44 SHA-0 Message Expansion No rotation in message expansion GF(232) Codeword corresponds to 32 copies of GF(2) codewords Only 216 GF(2) codewords Exhaustively test to find minimum weight Recall MSB diffs translate with probability 1

SHA-1 Message Expansion :

© Phil Hawkes 2006 [email protected] 45 SHA-1 Message Expansion 1-bit Rotation in message expansion GF(232) Codeword cannot be broken down to GF(2) codewords 2512 codewords to test Infeasible!!!! Search using heuristics Recall MSB diffs translate with probability 1

Outline :

© Phil Hawkes 2006 [email protected] 46 Outline Description Differential Attacks Analysis of Components Operations , +, rotate Round-dependent Functions Step Function  Differential Patterns Message Expansion  Disturbance Vectors The Fun stuff: the first round…

First Round: Problems :

© Phil Hawkes 2006 [email protected] 47 First Round: Problems Linear model can break down in Round 1 Suppose bi-1[j]=0, ci-1[j]=1, di-1[j]=1 Then fi[j]=1: Two differences don’t always cancel Optimal codewords for disturbance patterns assume initial state already includes some bit differences

But… :

© Phil Hawkes 2006 [email protected] 48 But… Can control values in Round 1 We know initial state, and control M Control sign of bit differences & constant bits Don’t assume linear model holds Addition differences carry to higher order bits The IF functions is very flexible By controlling sign of bit differences …and values of constant bits… Can absorb bit diffs, cancel bit diffs, etc. Allow ROTL to move bit differences

Hypothesis & Future Research :

© Phil Hawkes 2006 [email protected] 49 Hypothesis & Future Research For any input difference… …is there a differential path with correct input difference for Round 2? For given disturbance vector… …which differential path is optimal? How do improvements to MD5 attacks apply to SHA-0/1?