New Linear Correlations related to State Information of RC4 PRGA using IV in WPA

This slide was presented at FSE 2015.

Transcript

1. New Linear Correlations related to State Information of RC4 PRGA using IV in WPA Keywords: RC4, WPA, Linear correlations Ryoma Ito Atsuko Miyaji Japan Advanced Institute of Science and Technology Supported by Japan Science and Tecjnology Agency (JST CREST） FSE 2015 @ Istanbul, Turkey March 11, 2015
2. Ryoma Ito & Atsuko Miyaji (JAIST)  designed by Rivest in 1987.  Two algorithms: KSA  PRGA Background-RC4 stream cipher Background 2 March 11, 2015 FSE 2015 @ Istanbul, Turkey  Correlations are further increased by:  Application-related setting : SSL/TLS, broadcast encryption  [MS02], [MPS11], [IOWM14],  Key setting in applications: WEP, WPA [GMMPS14] linear correlations between keystreams and keys KSA 0 1 2 PRGA Internal state 0 1 2 N-1 Z1 , Z2 , Z3 , …, Zr keystream K S0 S0 K Si  Correlations between Key and internal state S0 , Si , keystream Zi  [Roos95], [FM01], [PM07], [Klein08] Our target
3. Ryoma Ito & Atsuko Miyaji (JAIST) Our motivations: focus on (unknown) internal states Background Motivation and Contribution 3 March 11, 2015 FSE 2015 @ Istanbul, Turkey  Linear correlations among unknown internal state and keys (known in WPA and unknown in generic) Our linear equations unknown internal states: Xr ϵ {Sr [ir+1 ], Sr [ jr+1 ], jr+1 , tr+1 }, r ϵ [0, 256], a, b, c, d ϵ {-1, 0, 1}, e ϵ {-3, -2, -1, 0, 1, 2, 3} Xr =a･Zr+1 +b･K[0]+c･K[1]+d･K[2]+e State recovery attack in [KMPRV98]  Recover four unknown internal states, Sr [ir+1 ], Sr [ jr+1 ], jr+1 , tr+1, by computing optimum solutions
4. Ryoma Ito & Atsuko Miyaji (JAIST) Our contributions Background Motivation and Contribution 4 March 11, 2015 FSE 2015 @ Istanbul, Turkey  Prove 7 theorems with significant biases Linear correlations RC4 WPA Results S0 [i1 ]=K[0] 0.001450 0 Theorems 1, 2 S0 [i1 ]=K[0]-K[1]-3 0.005337 0.007848 Theorem 3 S0 [i1 ]=K[0]-K[1]-1 0.003922 0.007877 Theorem 4 S255 [i256 ]=K[0] 0.137294 0.138047 Theorem 5 S255 [i256 ]=K[1] 0.003911 0.037189 Theorem 6 Sr [ir+1 ]=K[0]+K[1]+1 a sawtooth distribution Theorem 7 Note: The probability of random association is 1/N (=0.003906)  Discover more than 150 linear correlations  Biases in between Sr [ir+1 ] and {K[0], K[1], K[2], Zr+1 } for r ϵ [0, 256]  Biases in between {S0 [ j1 ], S1 [ j2 ], j2 , t1 , t2 , t3 } and {K[0], K[1], K[2], Zr+1 }
5. Ryoma Ito & Atsuko Miyaji (JAIST)  Preliminary  RC4 stream cipher, WPA (TKIP key generation)  Previous Analysis  Roos biases: correlations between Key and initial state S0  [GMMPS14] : Key-bias K[0]+K[1] under TKIP (known) linear correlations between keystreams and Key (known)  Our results  linear correlations between Internal states S and Key (known)  Prove theoretically (Example: Pr(S255 [i256 ]=K[0])～0.138)  Accuracy is checked by experiments  Conclusion Outline of talk 5 March 11, 2015 FSE 2015 @ Istanbul, Turkey Outline
6. Ryoma Ito & Atsuko Miyaji (JAIST) Algorithm 2 PRGA 1: r  0, i0  0, j0  0 2: for r=0 do 3: ir  ir-1 +1, jr  jr-1 +Sr-1 [ir ] 6: Swap(Sr-1 [ir ], Sr-1 [ jr ]) 7: tr  Sr [ir ]+Sr [ jr ] 8: Output: Zr  Sr [tr ] 9: end loop KSA and PRGA Preliminary RC4 stream cipher and WPA protocol 6 March 11, 2015 FSE 2015 @ Istanbul, Turkey state transition in KSA/PRGA 0 N ・ K: secret key (l bytes) ・ r , N : # of rounds, arrays in S (N=256) ・ Sr K , Sr : r-th round S of KSA, PRGA ・ i, jr K , ir , jr , tr : indices of Sr K , Sr , Zr ・ Zr : output in the r-th round (keystream) Sr-1 Sr ir jr tr Zr Algorithm 1 KSA 1: for i=0 to N-1 do: S0 K[i]  i 2: j0 K  0 3: for i=0 to N-1 do 4: ji+1 K  ji K + Si K[i] + K[i mod l] 5: Swap(Si K[i], Si K[ ji+1 K]) 6: end for
7. Ryoma Ito & Atsuko Miyaji (JAIST) WPA: Wi-Fi Protected Access Preliminary RC4 stream cipher and WPA protocol 7 March 11, 2015 FSE 2015 @ Istanbul, Turkey  standardized as a substitute for WEP in 2003.  Weak features: a 16-byte RC4 key generation known as TKIP  avoid the known WEP attacks using (IV-related) K[1]=255 [FMS01] First 3-byte RC4 keys K[0], K[1] and K[2] are generated by IV16 K[0]=(IV16 >> 8) & 0xFF K[1]=[(IV16 >> 8) | 0x20] & 0x7F K[2]=IV16 & 0xFF  IV16: last 16-bit IV 0 1 K[0] K[1] K[2] IV16 Correlations：K[0] ≒ K[1]
8. Ryoma Ito & Atsuko Miyaji (JAIST) Roos’ biases [Roos95] (proved in [PM07]) Previous works [Roos95] 8 March 11, 2015 FSE 2015 @ Istanbul, Turkey S0 [0]=K[0], S0 [1]=K[0]+K[1]+1, S0 [2]=K[0]+K[1]+K[2]+3, … 0 1 2 N S0 Correlations between K and the initial state S0 [0]-S0 [255] Pr(S0 [y] = y(y+1)/2+K[0]+…+K[y]) = (1-y/N)(1-1/N)[y(y+1)/2+N]+1/N K[0] K[0]+K[1]+1 K[0]+K[1]+ K[1]+3 ・Pr(S0 [0]=K[0])=0.371(=α0 ), Pr(S0 [1]=K[0]+K[1]+1)=0.368 (=α1 ) Pretty high biases≫1/N=0.003906 used in our results In WPA, Pr(S0 [0]=K[1])= δ becomes pretty high since K[0]≒K[1]
9. Ryoma Ito & Atsuko Miyaji (JAIST) Biases induced by TKIP [GMMPS14] Previous works [GMMPS14] 9 March 11, 2015 FSE 2015 @ Istanbul, Turkey  Distribution of K[0]+K[1] in WPA 0 31 128 159 Pr(K[0]+K[1]=v)=0 v is odd, v= 0--31, 128—159.  Induce further correlations between keastreams and key.
10. Ryoma Ito & Atsuko Miyaji (JAIST) Linear correlations between Zr , K[0], K[1] and K[2] [GMMPS14] Previous works [GMMPS14] 10 March 11, 2015 FSE 2015 @ Istanbul, Turkey Linear equation r ϵ [1, 257], a, b, c ϵ {-1, 0, 1}, d ϵ {-3, -2, -1, 0, 1, 2, 3} Zr =a･K[0]+b･K[1]+c･K[2]+d Byte Linear correlation # of ciphertexts 1 Z1 =-K[0]-K[1] 5･213 = 215.322 3 Z3 =K[0]+K[1]+K[2]+3 219 256 Z256 =-K[0] 219 257 Z257 =-K[0]-K[1] 221 Broadcast attack on WPA ・Linear correlations between keystreams and keys (without proof) Zr , K[0], K[1] and K[2] (known in WPA) ・Apply correlations to broadcast attack [IOWM13] in WPA.  Reduce # of ciphertexts to recover Zr (r ϵ {1, 3, 256, 257})  Previous work required about 230 ciphertexts theoretically [IOWM13].
11. Ryoma Ito & Atsuko Miyaji (JAIST) Our newly discovered and proved correlations Our results New linear correlations 11 March 11, 2015 FSE 2015 @ Istanbul, Turkey 0 1 2 255 S0 S254 S1 S255 New linear correlations S0 [i1 ] = K[0] (Theorems 1, 2) S0 [i1 ] = K[0]-K[1]-3(Theorem 3) S0 [i1 ] = K[0]-K[1]-1 (Theorem 4) S255 [i256 ]=K[0] (Theorem 5) S255 [i256 ]=K[1] (Theorem 6) Sr [ir+1 ]=K[0]+K[1]+1 (r ϵ [0, N], Theorem 7) Xr =a･Zr+1 +b･K[0]+c･K[1]+d･K[2]+e unknown internal states: Xr ϵ {Sr [ir+1 ], Sr [ jr+1 ], jr+1 , tr+1 } and K[0], K[1], K[2], r ϵ [0, 256], a,b,c,d ϵ {-1, 0, 1}, e ϵ {-3, -2, -1, 0, 1, 2, 3},
12. Ryoma Ito & Atsuko Miyaji (JAIST) Theorems 1, 2: S0 [i1 ] & K[0], Theorems 3,4: S0 [i1 ], K[0] & K[1] Our results New linear correlations 12 March 11, 2015 FSE 2015 @ Istanbul, Turkey Theorem 1 Pr(S0 [i1 ]=K[0])RC4 =(1-1/N)N-2/N Theorem 2 Pr(S0 [i1 ]=K[0])WPA =0  S0 [i1 ]=K[0] never occurs in WPA.  S0 [i1 ]=K[0]-K[1]-3 and K[0]-K[1]-1 occur with 2/N in WPA. (a double probability of random association) Theorem 3 Pr(S0 [i1 ]=K[0]-K[1]-3)= 2α1 /N+(1-2/N)(1-α1 )/N for RC4, 4α1 /N+(1-4/N)(1-α1 )/N for WPA. Theorem 4 Pr(S0 [i1 ]=K[0]-K[1]-1)= α1 (1+2/N)/N+(1-2/N)(1-α1 )/N for RC4, 4α1 /N+(1-4/N)(1-α1 )/N for WPA. Note: α1 =Pr(S0 [1]=K[0]+K[1]+1) is Roos’ bias.
13. Ryoma Ito & Atsuko Miyaji (JAIST) Proof sketch of Theorems 1 and 2 Proof of Th 1,2 Proof procedures 13 March 11, 2015 FSE 2015 @ Istanbul, Turkey  If S2 K[0]=K[0], then S0 [1]=K[0] never occurs.  If S2 K[1]=K[0], then S0 [1]=K[0] occurs  Sr K[1]=S2 K[1] for r ϵ [3, N-1]. 0 1 j2 K=0 S0 K S1 K S0 K[0] 1 0 K[0] 1 0 K[0] K[0] 1 j1 K S2 K 254 rounds i i Step 1. (S0 [i1 ]=K[0]) can be decomposed in 5 paths completely. Step 2. S2 K[1]=K[0] occurs in 2 out of 5 paths in generic RC4. in 0 out of 5 paths in WPA. Step 3. Compute Pr(S0 [i1 ]=K[0]). Proof Procedures  j1 K=K[0], j2 K=K[0]+K[1]+S1 K[1] Main Facts in KSA
14. Ryoma Ito & Atsuko Miyaji (JAIST) Proof of Theorems 1, 2 - Step 1: Decompose to 5 paths 5 Paths 14 March 11, 2015 FSE 2015 @ Istanbul, Turkey 1. Pr(S0 [i1 ]=K[0]) can be decomposed in 5 paths completely.  Path 1-1: K[0]+K[1]=0 and K[0]=1  Path 1-2: K[0]+K[1]=0 and K[0]≠1  Path 2-1: K[0]+K[1]=255 and K[0]=1  Path 2-2: K[0]+K[1]=255 and K[0]≠1  Path 3: K[0]+K[1]≠0, 255  From the algorithm of KSA,  j1 K=K[0]  j2 K=K[0]+K[1]+S1 K[1] 0 1 254 255 K[0]+K[1] ･･･ 0 1 255 K[0] ･･･ Path 2-1, 2-2 Path 1-1, 2-1 Path 3 Proof of Th 1,2
15. Ryoma Ito & Atsuko Miyaji (JAIST) Proof of Theorems 1, 2 - Step 2: Paths with S2 K[1]=K[0] Proof of Th 1,2 Step 2 15 March 11, 2015 FSE 2015 @ Istanbul, Turkey Path 1-1 and Path 2-2  S2 K[1]=K[0] 0 1 j2 K=0 S0 K S1 K S0 K[0] 1 0 K[0] 1 0 K[0] K[0] 1 j1 K S2 K 254 rounds i i generic RC4: K is uniformly at random Pr(Path 1-1)=1/N2 Pr(Path 2-2)=(1-1/N)/N  If Sr K[1]=S2 K[1] for r ϵ [3, N-1], then S0 [1]=K[0] occurs. Pr(S0 [1]=K[0]|Path 1-1)=(1-1/N)N-2 Pr(S0 [1]=K[0]|Path 2-2)=(1-1/N)N-2 Path 1-1: K[0]+K[1]=0 and K[0]=1 Path 2-2: K[0]+K[1]=255 and K[0]≠1 WPA: Never occurs.
16. Ryoma Ito & Atsuko Miyaji (JAIST) Proof of Theorems 1, 2 - Step 3: Combining all probabilities Proof of Th 1,2 Step 3 16 March 11, 2015 FSE 2015 @ Istanbul, Turkey Compute Pr(S0 [i1 ]=K[0])RC4  Using Bayes’ theorem.  S0 [i1 ]=K[0] occurs only in either Path 1-1 or Path 2-2. Pr(Path 1-1)=1/N2 Pr(Path 2-2)=(1-1/N)/N Pr(S0 [1]=K[0]|Path 1-1)=(1-1/N)N-2 Pr(S0 [1]=K[0]|Path 2-2)=(1-1/N)N-2 Pr(S0 [i1 ]=K[0])RC4 =Pr(S0 [1]=K[0]|Path 1-1)･Pr(Path 1-1) +Pr(S0 [1]=K[0]|Path 2-2)･Pr(Path 2-2) =(1-1/N)N-2･1/N2+(1-1/N)N-2･(1-1/N)/N =(1-1/N)N-2/N Pr(S0 [i1 ]=K[0])WPA =Pr(S0 [1]=K[0]|Path 1-1)･Pr(Path 1-1) +Pr(S0 [1]=K[0]|Path 2-2)･Pr(Path 2-2)=0
17. Ryoma Ito & Atsuko Miyaji (JAIST) Theorem 5: S255 [i256 ] = K[0] Our results New linear correlations 17 March 11, 2015 FSE 2015 @ Istanbul, Turkey Theorem 5 Note: α0 =Pr(S0 [0]=K[0]) is Roos’ bias.  S255 [i256 ]=K[0] occurs with the probability of about 0.138 in generic RC4 and WPA. Pr(S255 [i256 ]=K[0])=α0 (1-1/N)255+(1-α0 )(1-(1-1/N)255)/N  Theorem 5 is induced by Roos’ bias, α0 =Pr(S0 [0]=K[0]) α0 =Pr(S0 [0]=K[0])=(1-1/N)N+1/N=0.371
18. Ryoma Ito & Atsuko Miyaji (JAIST) Theorem 6: S255 [i256 ] = K[1] Our results Theorem 6 18 March 11, 2015 FSE 2015 @ Istanbul, Turkey Note: α0 =Pr(S0 [0]=K[0]) is Roos’ bias, δ=Pr(S0 [0]=K[1]).  S255 [i256 ]=K[1] occurs with the probability of about 0.037 in WPA. Theorem 6 Pr(S255 [i256 ]=K[1])=δ(1-1/N)255+(1-δ)(1-(1-1/N)255)/N  Theorem 6 is induced by Roos’ bias, α0 =Pr(S0 [0]=K[0]).  reflects that the probability of K[1]=K[0] in WPA is 1/4. α0 =Pr(S0 [0]=K[0])=(1-1/N)N+1/N=0.371 δ=Pr(S0 [0]=K[1])=0.094 Lemma 1 (WPA) Pr(S0 [0]=K[1])=(3/N+(1-3/N) α0 )/4
19. Ryoma Ito & Atsuko Miyaji (JAIST) Theorem 7: Sr [ir+1 ] = K[0]+K[1]+1 for r ϵ [0, N] Our results Theorem 7 19 March 11, 2015 FSE 2015 @ Istanbul, Turkey  A sawtooth distribution reflects distribution of K[0]+K[1] in WPA Theorem 7 Pr(Sr [ir+1 ]=K[0]+K[1]+1) α1 α1 γ1 +(1-β1 )ε2 ε0 (1-1/N)N-1+(1-ε0 )(1-(1-1/N)N-1)/N ζ1 (1-1/N)N-1+(1-ζ1 )(1-(1-1/N)N-1)/N ζr+1 (1-1/N)r-1+Σx=1 to r-1 ηx (1-1/N)r-x-1/N if r=0, if r=1, if r=N-1, if r=N, otherwise. = Note: α1 =Pr(S0 [1]=K[0]+K[1]+1), β1 =Pr(S0 [S0 [1]]=K[0]+K[1]+1), γ1 =Pr(K[0]+K[1]=1) εr =Pr(S0 [r]=K[0]+K[1]+1), ζr =Pr(S1 [r]=K[0]+K[1]+1), ηr =Pr(Sr+1 [ir+1 ]=K[0]+K[1]+1)
20. Ryoma Ito & Atsuko Miyaji (JAIST) Remarkable Biases in Sr [ir+1 ] for r ϵ [0, N] Our results Theorem 7 20 March 11, 2015 FSE 2015 @ Istanbul, Turkey  A sawtooth distribution reflects K[0]+K[1] in WPA Experimental result of event (Sr [ir+1 ]=K[0]+K[1]+1)  Theorem 7 is induced by the probability of K[0]+K[1] in WPA.
21. Ryoma Ito & Atsuko Miyaji (JAIST) Results Experimental value Theoretical value ε (%) Theorem 1 0.001449605 0.001445489 0.284 Theorem 2 0 0 0 Theorem 3 for RC4 0.005332558 0.005325263 0.137 for WPA 0.007823541 0.008182569 4.589 Theorem 4 for RC4 0.003922530 0.003898206 0.620 for WPA 0.007851853 0.008182569 4.212 Theorem 5 0.138038917 0.138326988 0.208 Theorem 6 for RC4 0.003909105 0.003893102 0.409 for WPA 0.037186225 0.037105932 0.216 Check the accuracy of Theorems 1-6 Our results Experimental results 21 March 11, 2015 FSE 2015 @ Istanbul, Turkey Comparison between experimental and theoretical value relative error ε ε=(|experimental value – theoretical value|)/experimental value
22. Ryoma Ito & Atsuko Miyaji (JAIST) Check the accuracy of Theorem 7 Our results Experimental results 22 March 11, 2015 FSE 2015 @ Istanbul, Turkey Comparison between experimental and theoretical value in Theorem 7  Theoretical values closely reflects the experimental values  except Theorems 3 and 4 for WPA, Theorem 7.
23. Ryoma Ito & Atsuko Miyaji (JAIST) Summary of this work Conclusion 23 March 11, 2015 FSE 2015 @ Istanbul, Turkey We have proved 7 significant biases Open problems  prove the remaining linear correlations  apply newly discovered correlations to the state recovery attacks Linear correlations RC4 WPA Results S0 [i1 ]=K[0] 0.001445489 0 Theorems 1, 2 S0 [i1 ]=K[0]-K[1]-3 0.005325263 0.008182569 Theorem 3 S0 [i1 ]=K[0]-K[1]-1 0.003898206 0.008182569 Theorem 4 S255 [i256 ]=K[0] 0.138326988 0.138326988 Theorem 5 S255 [i256 ]=K[1] 0.003893102 0.037105932 Theorem 6 Sr [ir+1 ]=K[0]+K[1]+1 a sawtooth distribution Theorem 7