ࡱ> \^[5@ 0bjbj22 ,*XX    ffff,$vTzzzzSSSSSSS$VRjXT $$$Tzz0T$$$$8z zS$$S$$@jL Qz f gf(N2S$FT0vTNY@YdQQXY QZ@$'4[TTCollege of Computer and Information Science Northeastern University CSG252: Cryptography and Communication Security Fall 2005  Problem Set 5 Due 12/1/2005 Send to  HYPERLINK "mailto:tmorgan@ccs.neu.edu" tmorgan@ccs.neu.edu, with CC to  HYPERLINK "mailto:noubir@ccs.neu.edu" noubir@ccs.neu.edu Problem 1 (20 points): Textbook exercise 4.5, page 151. Problem 2 (80 points): This problem aims at cracking Comp-128 one of the implementations of the GSM A3/A8 algorithm. GSM is a standard for cellular phones ( HYPERLINK "http://www.gsmworld.com/index.shtml" http://www.gsmworld.com/index.shtml). In the US it is used by operators such as tmobile and cingular. Authentication of subscribers relies on a SIM card (Subscriber Identity Module) which is essentially a smart card with a secret key and two cryptographic algorithms (A3, A8). These algorithms are used for authenticating the subscribers and establishing a secret key for encrypting the traffic. The SIM card is tamperproof (i.e., you cannot read the secret key inside), but you can query it. For more information on GSM security, read sections 3.1 & 3.2 of GSM Interception by Lauri Pesonen ( HYPERLINK "http://www.dia.unisa.it/professori/ads/corso-security/www/CORSO-9900/a5/Netsec/netsec.html" http://www.dia.unisa.it/professori/ads/corso-security/www/CORSO-9900/a5/Netsec/netsec.html). Problem Statement: Assume that you have access to a SIM card that implements COMP128. You can only make the following call: void SIMcard(Byte rand[16],Byte simoutput[12]); Given an input rand computes simoutput (See link to a3a8.c for an implementation of COM128:  HYPERLINK "http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/a3a8.c" http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/a3a8.c Your task is to find the secret key inside the SIM card. Analyze Comp-128 algorithm, and write a program to find the key in the SIM card. Document your approach/strategy. Demonstrate that you are able to recover a key. Hints: There's a narrow "pipe" inside COMP128. Bytes i,i+8,i+16,i+24 at the output of the second level depend only on bytes i,i+8,i+16,i+24 of the input to COMP128. Since the second level has only 7 valid bits for each byte, by using differential technique you will be able to compute the secret key inside the chip.) Bonus Points: SIM.h and SIM.o (compiled for CCIS Unix System) are given to you to emulate the SIM card. Find the secret key in SIM.o. Remember the result should be reproducible.  HYPERLINK "http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.h" http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.h  HYPERLINK "http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.o" http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.o Note: Since the first attack against COMP-128 was discovered, most operators have moved to more secure versions such as COMP128-2, COMP128-3. Additional links:  HYPERLINK "http://calliope.uwaterloo.ca/~ssjsin/COMP128.pdf" http://calliope.uwaterloo.ca/~ssjsin/COMP128.pdf  HYPERLINK "http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/GSM-Cloning-WangKleiner.ppt" http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/GSM-Cloning-WangKleiner.ppt  HYPERLINK "http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/COMP128-WangKleiner-Report.doc" http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/COMP128-WangKleiner-Report.doc }~     . / 0 ƻƂ{q{`Thd8/h`60J5\!jvhd8/h`65U\h`6h`65\ h`65\jh`65U\h&h> )0J5\!jh&h> )5U\h> )h> )5\ h> )5\jh> )5U\ hT5\ hUN5\ hi?5\ h_=5\ h.c5\ h1\5\h h.cCJ h_=CJ,Dtu[YQ$a$gd.cnkd$$Ifl0d&L0&64 la$h$If^ha$gd_=$h$If^ha$gd.c $Ifgd_= h$If^hgd_= 0 1 H i j + , [ \ o p  h$a$gdi5$a$gd h $a$gdHd$a$gdh$a$gdC$a$gd6,$a$gd_=$a$gd_=$a$gd> )$a$gd.c0 1 G H h j s    8 : ; < _ ` = P Q ) W X Z [ \ ŹŲŧŚŚxokh}h&hHd0JjJhHdU hHdhHdjhHdUhHdhhhhh&h h 0JjEh h U h h h h jh h UhCh h h6,hP5\ hP5\hPhR*hPh_=5\hPhP5\h_=hT5\)\ o p    )3@fghi=>',-7W[hk˿˴ǡ˗擋jhO,UhO,hi5hi55\h[Fh[F5\h&hi50Jj+hi5Ujhi5Uh[Fhi5hHdOJQJ^JhHdhHdOJQJ^Jh h hHdhhh}hHdhHd5\6h` `gdevgdev$a$gdO($a$gdC$a$gd_= $`a$gdO,$a$gdi5 $^a$gd[F $h^ha$gd[F$a$gd[F$a$gd h $`a$gdi5]^`am  kmno|xqxf|j h_pU h_ph_ph_pjh_pUhhev0Jj hevU h3hevhevjhevU hO(5\hevhev5\hChHdhC5\h h jhO,Uh&hO,0JjhO,UjhO,U hO,hO,hO,&o-/01h[lh/hevhev5\j h_pU h_ph_ph_p hevhevhevjh_pUh&h_p0J $a$gdO(gdev`gdevgd_p *1h/R :pD?/ =!"#$%$$If!vh55L#v#vL:V l0&655L/ 4DyK tmorgan@ccs.neu.eduyK 6mailto:tmorgan@ccs.neu.eduDyK noubir@ccs.neu.eduyK 4mailto:noubir@ccs.neu.eduDyK $http://www.gsmworld.com/index.shtmlyK Hhttp://www.gsmworld.com/index.shtmlDyK [http://www.dia.unisa.it/professori/ads/corso-security/www/CORSO-9900/a5/Netsec/netsec.htmlyK http://www.dia.unisa.it/professori/ads/corso-security/www/CORSO-9900/a5/Netsec/netsec.htmlyDyK Ahttp://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/a3a8.cyK http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/a3a8.cuDyK @http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.hyK http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.huDyK @http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.oyK http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.o9DyK 1http://calliope.uwaterloo.ca/~ssjsin/COMP128.pdfyK bhttp://calliope.uwaterloo.ca/~ssjsin/COMP128.pdfDyK Vhttp://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/GSM-Cloning-WangKleiner.pptyK http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/GSM-Cloning-WangKleiner.pptDyK Yhttp://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/COMP128-WangKleiner-Report.docyK http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/COMP128-WangKleiner-Report.docH@H _=Normal CJOJPJQJ_HmH sH tH DA@D Default Paragraph FontRi@R  Table Normal4 l4a (k@(No List6U@6 T Hyperlink >*B*phFV@F _pFollowedHyperlink >*B* ph  *,Dtu01Hij+,[\op  h  `  0000 00 0 00000000p00000000000000000000 000000000000p00p000M900,Dtu01+,[\op  h  `  000000000000000000@0@00000000O900<D. 0O900O90000O90000M90$0M90$0@08@08 @08@08 @08@08 @080x0 \ o h   .;_Wh  ] `  n 0 XXXXXXXXXXl,2$9>n@0(  B S  ?  tk tTtLtttO jj ll B*urn:schemas-microsoft-com:office:smarttagscountry-region8*urn:schemas-microsoft-com:office:smarttagsdateV*urn:schemas-microsoft-com:office:smarttagsplacehttp://www.5iantlavalamp.com/=*urn:schemas-microsoft-com:office:smarttags PlaceType=*urn:schemas-microsoft-com:office:smarttags PlaceName 1122005DayMonthYear)2' , 1 6 J N 33u1    G. NoubirvF'4hq"A HqC ¯$" HcT1l@HcvF'To+^e(4ls@8bOG"A h                                                                                                                          [t                         [t        (!J}*J}*~-LB:e +lwvc @ G=59s_w h O(> )R*6,`b,;/4i5G7}:N;L<^s<0t<_=:?D?EJ?i?F+Ex F[FvG_IHgK LUN-.Q/;QRgT>ZJ\d].cbcHdd>]difhh"h[lio p.s"]syI3y} %T!YJL.ff%_p[By[O,K=vZ1\N;$vDN'1S',)RCMw/P]~ ev7F\`6L1x8i}GA21TbBF`AN6 %uu @% @UnknownGz Times New Roman5Symbol3& z Arial?5 z Courier New;SimSun[SO3z Times;Wingdings"qhjjs  24d  3q H)?!+College of Computer and Information Science G. Noubir G. Noubird                 Oh+'0   4@ \ h t ,College of Computer and Information Scienceoll G. Noubir C. N. N Normal.dotC G. NoubirC21NMicrosoft Word 10.0@r@n?if@D @Lf ՜.+,D՜.+,l( hp  Northeastern University A ,College of Computer and Information Science Title 8@ _PID_HLINKSA<EYhttp://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/COMP128-WangKleiner-Report.doc Vhttp://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/GSM-Cloning-WangKleiner.pptC1http://calliope.uwaterloo.ca/~ssjsin/COMP128.pdffi@http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.ofi@http://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/SIM.hVF Ahttp://www.ccs.neu.edu/home/noubir/Courses/CSG252/F05/PS5/a3a8.c33 [http://www.dia.unisa.it/professori/ads/corso-security/www/CORSO-9900/a5/Netsec/netsec.html>l$http://www.gsmworld.com/index.shtml[2mailto:noubir@ccs.neu.edukmailto:tmorgan@ccs.neu.edu  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJLMNOPQRTUVWXYZ]Root Entry F g_Data 1TablerYWordDocument,*SummaryInformation(KDocumentSummaryInformation8SCompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q