|
29 December 1999: For worldwide DVD CSS sources see:
http://cryptome.org/dvd-v-500.htm
DVD CSS messages and source code:
http://cryptome.org/dvd-msgs.htm
EFF to Oppose DVD Complaint:
http://cryptome.org/eff-v-dvd.htmhttp://www.eff.org/pub/EFF/Newsletters/EFFector/current.html
27 October 1999
Source:
http://livid.on.openprojects.net/pipermail/livid-dev/1999-October/000589.html
Frank Andrew Stevenson
frank@funcom.com
Wed, 27 Oct 1999 08:55:01 +0200 (CEST)
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<H`*)2HFQA89-6PL5;!' M00(8>&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.<NW+M.*[C&>-]>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-D,VI8X@XCK!J:7_&3[MZW\FDTHOXLS7':N_%@;$'OP$Q@%%5`WD@I2 ME!SEFP#UIX!^<DV/FJ0:X[!G4X&I07FNE$$UB>=4&<Q8RK13`TV9R3^K4HYT M5)9!JG6H185Q%V?`!K?+O*LP)0I182KSK<)PC6W>L@I[ZA49S=S`0S=PT6<B M@RZKF<TSV)*1B,H5&;^,+3)T^P^E2/,@_\2&-GB:TI!@@ZC\Y&!!E:*-9G!$ M&^@-ITO-X1)X0+6RC56&.LT!$YPX51Z0->=EXH$5^FQE++P1342)"\RM%&DP M_^1-D<K*&=(N4SA%ZDN`P^$9OW;&++\%*`S^V1N_@.6AI_%+;]`"V,-XQ9T: M7>90@7%/+!>TIUC:)D=),I1I`D0&_]PFEGHJ$M6^%)@W%;-5YPE9S,3CJF)Z MR4W:^50Q.]8R3UEP.),+3+*T>3.C$<MP^$(8M>PF-:%)#E<3RZ+/\-(T9S%. M6@*+V&4:YZR>,<U7@/-7P_@V@\I])2R9(POGSI*6H(#N5EO8D@Q*QQ[49:A' M8+L1X61#+#ZI#:*%D:@B*:I->^GGH@6,*&TF&LN*I@ZD]Q$I7@JUT9)V=)`? MG1Y&.:110KH4+]FD#TKQ0$":CK2EHC%I0W?:4\S4%`_+NBD><AK3AX8THS^U M:5!?.E29/M6G*R7I5'%J4:NF%*I9!6I[A'HZHJI4BV(]S4MUZE6>GI6E4ATK M5<O:UJ*^,*QQ52M73UK7MVI5KGNMJE._BE6TYM6D;!VL6\%J6*1R-+!T5:Q= MCYK4K2ZUJY+U:UK)FEC!S-2H476L4IGJ4,]>%;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<U>]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?<X@Y7 M^,,<QC"#=6M?Z:I8P\/-<8BU>V(2N_C&,!:RC"-L9!N;F,<H+C&1H=QD';\8 MRC$^L'[#6V,K(QG+2M;RC)7+VQ0[=\5[S?*/$4QF-9\9R-'MJYB97&8IHSG( M71[RG2?GS\N)17-E(>CGV$*#T<FE!W1I+1SOXR6U?9)K_J+3@\S$2[(93&X3 M@TI#X=0@.;GM87"+&)K0J"9:HDUA9D,8)NFSLAYU;$5*RV'/9C:EDA7)?423 MD=2PTM"712EFWW,:C*!VLB.E+$G\0YH2C>9&^H#'3]%DE^*\Q;?T4(J$AC(7 MX>@E.:HTM(^2.@^\'"<OR"$/41M4E+H0AR[#M?)T=U2-IZS'+![Z:E;`,95L MUF<LSU"+,`U]E6]B)3YH<49:J%JCJFR3/V49$5F[.QV7$N0FK862;0TCDQ=1 MZ$O[.5)L!,OB?O)X6F)F"&!@$QB6S*BE_,C2,?JR&K[>T]"--:EE(J(>'I96 M&*:-;$@BTE@LX8?(*0J-:D!J3I!"UKU2@@AH%[M1QG+D(?W9K$+<E#"H7".J MPP`K,<+"%&DT91J_S,]65L25$$_'*=VTRGR\LN$\206;RV#0LOU3Y&66B%-K M!:HY@JH.N/PF+L`-#T\KU).V\(8MNUV3/H%T%#.YI3=W,8YYA/J@>&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<B`PT&=@\0(J<(S(F(S*N(S,V(S.>(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`<Z``(ET!IX`)E],IF1B0-XP`5N(`(LP(]2P8]4P8\S``(I ML)-^Z1.!"0(B\`9U0`=PT)J/*0*DN9-F\`9R\)%IH)<@L`,]D1`@4":[V1,K ML`*D:1>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`)<Y9U5B9\S4)[GR0<YZ9TVT)ZIES33*1?>60,K ML)8VL`+JF0`)<)J`*9B1*0.3R9DWJ:"759KS60/;V0,XL)-]8!<D2@>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`;<N)6F)V@"80>$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[<!2;W_6Y,6>E#,N5#/>:'229W'N[50 M^9+_F<&Q&P/U&9[C":'\20,>G)81S!:K5Y/R^;\%6XT'00;QZ+<J2[S6Z\#5 MJ[)$::UT@*UML`55N[QH^;MHF0:I:;U0FY-)^Y%*3)Q<19HLVBAF<,)&S,0J M6[,UJ:U-'+.\ZY1$S(\JVP)$J9XN;+T="L8@0)QD_,`ZK(\D>[E*W,+_:[`W MFJ,GB@<O<,>JV9DUR<<J6YKS^\4&FRR;\P)A*L`$[+>C:<@W3+_5F[P@X*`) M4;/GF;M@?,+6&Z.WF\%UN[7WFJ^'TKUC/`/8^\+:6Z7["@(JVP:VZ;=I0+[\ M>+X##!.AC!#D\:3ZVKTF&<AK:[^/ZYNM^JJQ.JNU>JNYZK19^\40[)X3[)SN M><%3J<S8R<'<B<D@#)XQ()[D:9XEC,G)>:$K')^87*'W:9_YZ0/[6:#_R9\" MZ@,$VI_;B:`L:KS*W*`S2<(2BJYE7*$-FZ%R7+T<ZJ$@:L)?7,61;+W$RU50 M>[42>ZV-\\.:"[5B@*UK@,DPZ@,RRLF>N[4&_;(]0)3!#*NR2JNVBJNZ"K5: MN[8&2P3GZ["%DZ5W@!9D`+$+409P`+&$>\K<NQ&B&<L@$,,SK(]YN[>+F<HX MK,&0_,FX7,LG;+\>K;2_K+_(C-)?_,%).Y,@D-"7=<+(N\0];;NXZZ(NG+V- M,P<!:;Z<0XZ0$:9/"@*'D[!URIIGT(X3W9J!8YL%/)!H819N;9L@D*;=.P=H M8,2(^:T9Z\C_:[]JH)N\J09,>[.-[;HI/=983922K-7J,3EF`+6Z^Y&.79Z_ M>0-S.]9@7)_E?,[I#,_<R<X&^L[M+,\+6M4<?<0Z/,9R*]$4O;QV4:,NS-O_ M6\>"B:]+O:^/&9DS8)F529F8N:.=V90PP`<H8+H#F@(L8+I1G$T]+=9;V\D^ MZJ-`6HTWT09PT)%N?:ADNX]H/8XC6Z4_@8V3"=@(Z],_J;@&Z[R(^9AWD`9L MP`8@<`9+BA!L2@9OT`;H.P=UP`9T`+%&S+I1ZMX_C1/K"+%H@1`"\9I>>: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+>[<CN[?+6N&M"0+YO=]P'@9V@!!^28Y!?09H43AG@!"* MVP=%6XS5V`1A(!#E/1#G'<@*\)/T*!`B^Q-H<08GLN%R4(W!;@=;P.7^6Z__ MFJX!"^2A'`9`'-+#3-+&K*ORN=$=^[$$^9'1WMR=2>TC7<PF#>E%G)K!SHT^ M``+B3LPE?<S$>=O+WI==FZ,Y#@+TZ`8!&>Q$7J<)GK;:C9:27@>4#@)Q*Z^= M;-#I[IM_/.]<BYJ"605S$`:M7MP0BP>3B?$@X`(<'\D@4`,%"YDOZ^#P/>?, M':9R<`;(CI3A[JHB[>[7/MKH.^G[>/#IVLE.G;1$"[D+S[_)O+;1_K-QR[DT MC@<VCN,ZSN,HK_(_R^4(O]$*G_+<^-'L[O+53N[P_IL_O[4&J]=FWHXM6Y0` MR<M;"]RJ&01FZK%P\*OYV*Q9"O`9;%!N_ZS>?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)
For related CSS files:
http://cryptome.org/css.tar.gz
Thanks to AS.