From frank@funcom.com Tue Nov 9 13:22:51 1999 Date: Wed, 27 Oct 1999 08:55:01 +0200 (CEST) From: Frank Andrew Stevenson To: livid-dev@livid.on.openprojects.net Subject: [Livid-dev] Successfull attack on CSS algorithm Hi, I am a new member to this list, in fact I subscribed just today, in order to send this message, and answer to followups. My main interest in this is purely cryptographical, so I have little or no knowledge of the problems associated with CSS. What I have done is device an attack that will recover a CSS key with a complexity of 2^16 and as little as 6 known output bytes. This should reduce the keyrecovery time from ~17 hours to a fraction of a second. The CSS algorith is fataly flawed. A divide and conquer attack is possible by guessing the 16 unknown bits of LFSR1. LFSR1 is then clocked 4 times, and the known keystream bytes are then used to reconstruct the state of LFSR2. The whole cipher is then clocked another 2-6 times to validate the key. If the key is correct LFSR2 is clocked backwards 4 times to retrieve the initial state. The fine details can be found in the source code below. I hope this mail isn't too long, but I have included source for a complete cracker which works as follows: hippopotamus:~/pc/temp> scramble 3e 4c 13 2e 9c Doing encryption Keystate at start: 13e 4c 01385c2b output: 80 18 e2 cc c1 21 85 0d 9f 8c This produces the 10 first bytes of the keystream for the given key, and also dumps the initial keystate. hippopotamus:~/pc/temp> time scramble 80 18 e2 cc c1 21 85 0d 9f 8c Attempting crack Candidate: 13e 4c 01385c2b 0.090u 0.000s 0:00.10 90.0% 0+0k 0+0io 87pf+0w With 10 bytes as input, the initial state is here recovered in 1/10th of a second on a PPro200. frank ---------- The following is C code for the attack -------- /******************************************************** * * The Divide and conquer attack * * Deviced and written by Frank A. Stevenson 26 Oct 1999 * * ( frank@funcom.com ) * Released under the GPL license * ********************************************************/ #define KEYSTREAMBYTES 10 static unsigned char invtab4[256]; void CSScracker( unsigned char* pStream ) { unsigned int t1,t2,t3,t4,t5,t6; unsigned int nTry; unsigned int vCandidate; int i; unsigned int j; /* Test that CSStab4 is a permutation */ memset( invtab4, 0, 256 ); for( i = 0 ; i < 256 ; i++ ) invtab4[ CSStab4[i] ] = 1; for( i = 0 ; i < 256 ; i++ ) if( invtab4[ i ] != 1 ) { printf( "Permutation error\n" ); exit( -1 ); } /* initialize the inverse of table4 */ for( i = 0 ; i < 256 ; i++ ) invtab4[ CSStab4[i] ] = i; for( nTry = 0 ; nTry < 65536 ; nTry++ ) { t1 = nTry >> 8 | 0x100; t2 = nTry & 0xff; t3 = 0; /* not needed */ t5 = 0; /* iterate cipher 4 times to reconstruct LFSR2 */ for( i = 0 ; i < 4 ; i++ ) { /* advance LFSR1 normaly */ t4=CSStab2[t2]^CSStab3[t1]; t2=t1>>1; t1=((t1&1)<<8)^t4; t4=CSStab5[t4]; /* deduce t6 & t5 */ t6 = pStream[ i ]; if( t5 ) t6 = ( t6 + 0xff )&0x0ff; if( t6 < t4 ) t6 += 0x100; t6 -= t4; t5 += t6 + t4; t6 = invtab4[ t6 ]; /* printf( "%02x/%02x ", t4, t6 ); */ /* feed / advance t3 / t5 */ t3 = (t3 << 8) | t6; t5 >>= 8; } vCandidate = t3; /* iterate 6 more times to validate candidate key */ for( ; i < KEYSTREAMBYTES ; i++ ) { t4=CSStab2[t2]^CSStab3[t1]; t2=t1>>1; t1=((t1&1)<<8)^t4; t4=CSStab5[t4]; t6=(((((((t3>>3)^t3)>>1)^t3)>>8)^t3)>>5)&0xff; t3=(t3<<8)|t6; t6=CSStab4[t6]; t5+=t6+t4; if( (t5 & 0xff) != pStream[i] ) break; t5>>=8; } if( i == KEYSTREAMBYTES ) { /* Do 4 backwards steps of iterating t3 to deduce initial state */ t3 = vCandidate; for( i = 0 ; i < 4 ; i++ ) { t1 = t3 & 0xff; t3 = ( t3 >> 8 ); /* easy to code, and fast enough bruteforce search for byte shifted in */ for( j=0 ; j < 256 ; j++ ) { t3 = (t3 & 0x1ffff) | ( j << 17 ); t6=(((((((t3>>3)^t3)>>1)^t3)>>8)^t3)>>5)&0xff; if( t6 == t1 ) break; } } printf( "Candidate: %03x %02x %08x\n", 0x100|(nTry>>8),nTry&0x0ff, t3 ); } } } ----------- Following is a complete cracker ------------------- ------ compiles with VC++ / gcc linux, runs on x86 ----------- begin 640 scramble.c.Z M'YV0(]*X&<.F#IDR('C,H4,FS1L7:'PH"#BPX,&$"^4(/`-1(D6"!A'R&$,G M#YPR'2<*!'E1(4,V:<2D5%#'S9PT9]R4(0-"(!T00Z9,H1-&#(PM,6)TZ;&G M!@L8+&*PD,%B!@L:3Z-.K7JUSPX%-&WBU,ES#)HP&98Q7MC;UXQ3_'(L!'8AE\9?FT`YDL8[XPR@6]`=MQ8\&(\-B8+UFRC M\@W`=O&2\9O#+YG+,"K3\`O#+XW+.2H?#)Q#,YG*,"[3T`Q#,XW*.4#?Q5/C M1N`8QO'6,!,8!U6\8Y+CP2%]#'.\,9X3#W.-]>ODQVF,P#XV' M3`[:[T5+Q0L#*EX:\?'`R$]C/IX<]K6'`VT#BA8@#/[14*!^"](08`Y2L3<# M&9%1Z)A3>,F`%5XV6"B8AS9@B,<-&^8U1F0G.E8B7(6E*)B+-I1X@U/LD>%A M#AZ2(2(,)=+@(0P>TB!B#B62X6(.+I)1(@PBTN`B#"[24&(.-`Y70WXQY%># M?S@$.$9^..0WAG\Q!%C#@C$L6$.`./@WQH(X+#A&@$FQ4*-T.4A'AG@P:$># M=#!(1X-X.6A'1GDYE$>&=C"(1T-Y,)1'@W8YK&>E7S'X5<-E.%0VAE\X^#7& M93%45H-F,6@65W.7C:$9#IJ-45D,PN$EAE]F^"7&96%45H9?8?A5QF5F5":& M9F9H)D9E1056AF9A:%9&96;4FI=T-T@W@W@R:&>#=#)(9X-X-V@W0WDWE#># M=C*(9T-Y,I1G@W8W6&IK?F;DUU9@80181GYAY%>&?V8$*,:"9BQH%+_^E;%@ M&`N6$:`9$5KI80P>UB`B#B6.X2$.'HXA8@PEUN!B#"[64"(.(H[A(@XNCE%B M#%7:ZJ$9'HHA8A@E[L2OAV6(:$:)8KAHAHMBE!B&B&6X&(:+991H1LUYY7=# M?C/X)T.`-N0G0WXV^'=#@#,L>,.",P0H@W\V+"C#@C8$>$/%MDIGAG1BB!>& M=F5(%X9T98AGAG9BE&=&>6)H%X9X99071GEE:&>&&0IX!59--^6T$PAFH:76 M4$7)\%9<<]4U7'V!(9@ZHZPMN2-N@.8'PX*YI0[ICT_R"1E[V1V'*9UDSBH= MR<>-3&IY61Z'IGBI'G?QB>QI&!B+&586[O1J:\WN81[*X&*[TVOV]?1N7Q:O MG=4&L@I[ZA49S=S`0S=PT6=EXH$5^FQE++P1342)"\RM%&DP M_^1-D90@7%/+!>TIUC:)D=),I1I`D0&_]PFEGHJ$M6^%)@W%;-5YPE9S,3CJF)Z MR4W:^50Q.]8R3UEP.),+3+*T>3.C$PF-:%)#E<3RZ+/\-(T9S%. M6@*+V&4:YZR>,^GGH@6,*&TF&LN*I@ZD]Q$I7@JUT9)V=)`? MG1Y&.:110KH4+]FD#TKQ0$":CK2EHC%I0W?:4\S4%`_+NBD>GI6E4ATK M5%;1X%:UELRE8TQ(6M8VM+&`O MR]?,,A:NJITM:R/KVL46%K>RU2MM.RN]U]XUMH^E;6N+ZUO8`C>YI#7K;?\J MW-T2][/'?>YH,=O;R88VN)QM:G]BUBI>YWDTM>.=ZW=-FE[J(/2]V*0M= MCY86O>3-;76YB]_I;I:]\G4O?;=;V_'ZM[R0;:]Q![Q:_L[WN_6%Z7T?K-X( M*[BY[_UO@@.\8`@3^,+I12Z!ETMA$3>XP/W]+7P!/&$!>_C$(,[O>C?V(2N_C&,!:RC"-L9!N;F,CGV$*#T9&^H#'3]%DE^*\Q;?T4(J$AC(7 MX>@E.:HTM(^2.@^\'"T]"--:EE(J(>'I96 M&*:-;$@BTE@LX8?(*0J-:D!J3I!"UKU2@@AH%[M1QG+D(?W9K$+&KI&/$\ MDB^"HYSE`#J6S76NH&LI2@T,S5!LDLOSXKF?:#1/&\R[,X:GG-[D"QCYU'GT M;I%AO/P4GT'$'\?PA2'\]`1?0.G@D3Z/7^K>*>F_5]J][L>9>V'B/KVW'Y!5 MJ;-6KJJH2+.7/8-C]YVSP#[*Z76]@%M/W=IQBL2<59WJ(:1-U)WU])]-C^D% M]#$_0B'L,361473R(R(ZTD*T\7/.(B(ZA!<\ER$X5T`VESI4DR^1$7,`%$LM M!Q_'H7*%@7+3(R;\`2:R0W/8!'**Y'&QQ'&TH7'.@G$,,ST55T`3ESI9M$U\ MX7#X8TL9I'#'@7"%87#A4TP#UQR\$7$XY6]BI3ZQI&^T@6_.8F_\0F_%)&_- M@1L`ATWMIDCK%DOI1AOGYBSEQB_C5DSAUAR0\FXXQ6V*I&VQA&VAU3OL1&W\ M(FW%!&W-P2C>ADW+IDC)%DO'UD;'06PP)('!5DR_]D>ITVQ+I6N*A&NQ9&NT M06OUA$/\`FO35$"MECJ\ADVIIDBG-DL=1"#*XRRAQB^?5DR=UARTLVI+A6F, M1#^Q1&FT(6G.`FG\XFC.5$!L(P*``(J M$(TJ``)4@`8(43@W,0:?PSEI``?8F!9C\`8'08WF*(T@<`5I0`=H``)RL!-U MX"H\T09AX`9G`!/VV!-N``+LB!!K4`9Y``)S4`9T4`=P<([3*(W/N)`,V9`O M`!9V\`9IP!,&=1!S,`9R$`9M(`9L4`8H``*84WJ!YCDJ\(\!F0*)E@`A"6CZ M^!-T(!5T0!5T8!5T@!5TX!1T8`-?H9)_)E`^T1/_E``OV0,@8));``-=``)> M``+841\[&9-$:91*\90ST`,HH`(H@`(KZ9-N\!,JD`(H8)(K(`,I4)9?`0+\ M2`,],),F<`-4N98SH`(RL`(XT`(U^90UT`,P\$]H"0<:T95F\)$BL`0`N1!A M0`<(<9@"211R0`F(Y1J:5!L(3HQV05>H)Q%,0-;\))=L)-"*0-K&0,^X`,Q8)U#F94O M:0(QD`(\P`,XD`)><)=V@9P]`)TZ,YTT4)WKF9-6F97VB0(SN9TS@)XSF0+; M.9[IN9_;>9X!ZI\^4`,I8`)60,K ML)8VL`+JF0`)<)J`*9B1*0.3R9DWJ:"759KS60/;V0,XL)-]8!I*0*: M*9LN6J-@H0#&V)!".J0-B9!H>8T(001I8`<3F9AN4!9OX`9Q4`=ED!:'211C ML`9&"@)$4`9,*H\@4(\\<0<:00>(N8]B$)!&D)%NL`8@$`0N``)#X:5E8!-1 M"@*#`0)/0!*_F0-^NJ4?:09LN@9`8`8U,8YMX`*(6ISH"`)24`8=&08#R1,U M<1!IT8\@<`10P`0@`!.N8A-E@)!$.JJDFHP/.1$'808"@1!+4`19,`54(`5% M$`1-(`190`5%,`6_.8P*8)ATD`;$QGK_%)$3^3D8^33_>)L@ MV9/#BA;5"`=#\8X:29H@4!=H*:P\\9,OR0(Q*:XT:9,XJ9/1&*T!M3D_Z094 M(`=Y<);J*I(M"0)V,`1B.I&'60;R^I-I(*_>6J]JP)<@8(S66`8+P8]G\1/N M20,],0=A"@(G(0=MT)J'Z1#[J`(/B99M4`9M,)!T@)MN8*Q%@15,V9EP80.S MF:ZU":UI``)$"0/!^;(\@*=Q,;/#J:W%>JR#5K);D`9)F91$V9T@P+*VB9LP MRY0SZYLIB[/$F0(]D9H[Z[.]F90A,+3:RJUH*;%_B:.""0556K%$\:MW6J5R M8)L[NK);"P)E@`?K^)$M$`-J"P(^BI8&*Q#KF`9A`!-Z@!"86JQ5.I`@\`9F MP(]%T9$.J[%&Z[))*[.\2;,VJ[*/F[-0.[48VK,8"K0@(+1`"19HV;(?Z:[P MVKC!*;H!6;,A4D*2"P*F2[G;FJYH^9)):[H@L)T@@`,@P`=,B0=ELI>P"YJS M^ZX!:0*[.SGR&KNC&;.\:;?5Z`9O\!,ZL1.;H[AK>Y.-2[#,VQ.(F9&(Z8W@ M6*4@X+"_VK$02P=OX(Y-$Z49$8\_P01&,`52(`/2N+%;"[J]&;-+6[,..[E/ M^[IKF[UA0`9V4(^N`@+N"[]RZ[P4N[E#,N5#/>:'229W'N[50 M^9+_F<&Q&P/U&9[C":'\20,>G)81S!:K5Y/R^;\%6XT'00;QZ++X##!.AC!#D\:3ZVKTF&JNYZK19^\40[)X3[)SN M><%3J:$K')^87*'W:9_YZ0/[6:#_R9\" MZ@,$VI_;B:`L:KS*W*`S2<(2BJYE7*$-FZ%R7+T[42>ZV-\\.:"[5B@*UK@,DPZ@,RRLF>N[4&_;(]0)3!#*NR2JNVBJNZ"K5: MN[8&2P3GZ["%DZ5W@!9D`+$+409P`+&$>\K+FK;2_K+_(C-)?_,%).Y,@D-"7=<+(N\0];;NXZZ(NG+V- M,P[.-[;HI/=983922K-7J,3EF`+6Z^Y&.79Z_ M>0-S.]9@7)_E?,[I#,_"B:]+O:^/&9DS8)F529F8N:.=V90PP`>:J^ M"JP#Y3GNW1#^G>!(<0.<*P((@AA"\BUA4A0>$SA<``,B\$\9SHT_B01M*P1Y M@)A4\`9)T)4?J=X)>WK2"`=.4`<;";Y4C99`;A;]VI7N2+!\/<9OP`9O<`=5 M^I%"3N3'(@='F93:G19#J[+5B`(^`9:+*0=F`:T=#N$)WIE\#;4M``)I_N$0 MJ]U/'LM23N70>N5%KN5*,;=R<,9BWI5DGA%G_I%Q'N%LWHYN#N=MZ^$1OK+I M^HX%*0?[F!9:+<7+>[TC7E%G)K!SHT^ M``+B3LPE?=O+WI==FZ,Y#@+TZ`8!&>Q$7J<)GK;:C9:27@>4#@)Q*Z^= M;-#I[IM_/.]3B?$@X`(<'\D@4`,%"YDOZ^#P/>?, M':9R<`;(CI3A[JHB[>[7/MKH.^G[>/#IVLE.G;1$"[D+S[_)O+;1_K-QR[DT MC@?IAA,+>P#JF".]D&"P5G*\-Y MK9'C[8^%V<,/3?;T#O&JR=(\7:<8:1+G#?>_6Y$(VZP;V9%U3Q1XO]$#3^D? %*;,]"A:% ` end This sentence is unique in this respect; it can safely be attributed to my employer, Funcom Oslo AS. E3D2BCADBEF8C82F A5891D2B6730EA1B PGPmail preferred, finger for key There is no place like N59 50.558' E010 50.870'. (WGS84) _______________________________________________ Livid-dev maillist - Livid-dev@livid.on.openprojects.net http://livid.on.openprojects.net/mailman/listinfo/livid-dev