RANDOM SUBGRAPH ATTACK ON A5/1

ADissertationsubmittedtotheUniversityofHyderabadinpartialfulfillmentof thedegreeof

MASTER OF TECHNOLOGY
in ComputerScience by N SHIVA KRISHNA

Department of Computers and Information Sciences School of Mathematics and Computers & Information Sciences University of Hyderabad (P.O.) Central University, Gachibowli, Hyderabad 500 046 Andhra Pradesh

CERTIFICATE
ThisistocertifythatthedissertationentitledRANDOMSUBGRAPHATTACK

ON A5/1 submitted by N.SHIVA KRISHNA bearing Reg. No 09MCMT65 in partial fulfillment of the requirements for the award of Master of Technology in Computer Sciencesisabonafideworkcarriedoutbyhimundermysupervisionandguidance. Thedissertationhasnotbeensubmittedpreviouslyinpartorinfulltothisor anyotherUniversityorInstitutionfortheawardofanydegreeordiploma.
MsRukmaRekha (ProjectSupervisor) DepartmentofComputerandInformationSciences UniversityofHyderabad,Hyderabad500046

HeadoftheDepartment

Dean SchoolofMathematics Computer&InformationSciences UniversityofHyderabad

DepartmentofComputer&InformationSciences UniversityofHyderabad

DECLARATION

I, N.SHIVA KRISHNA, hereby declare that this Dissertation entitled RANDOMSUBGRAPHATTACKONA5/1,submittedbymeundertheguidanceand supervisionofMsRukmaRekhaisabonafidework.Ialsodeclarethatithasnotbeen submitted previously in part or in full to this University or other University or Institutionfortheawardofanydegreeordiploma.

Name : N.SHIVA KRISHNA Signature of the Student R No. 09MCMT65

Acknowledgments
Itisagreatpleasuretoacknowledgethesupportandencouragementreceivedinthe successfulcompletionofthisproject.Itisaprivilegetoexpressmyprofoundgratitude andindebtednesstomysupervisorMs N.RukmaRekhaforhervaluable,inspiringand constantsupportthroughouttheprogressofthisproject. IamverymuchthankfultoMr.Y.V .SubbaRaoforthecontinuousguidanceprovided throughouttheproject. IamgratefultotheHeadofDepartment(DCIS),ProfPNGirijaforprovidingus boththefreedomandanexcellentlabfacilitywherewecouldtestourworkeffectively. IamextremelythankfultoA.ILabstafffortheirkindcooperation.Aspecialthanks to all my friends, especially my lab mates for their valuable suggestions and encouragement. Iexpressmygratitudetoallfriendsfortheirimmensesupport,withoutwhichthis workwouldnothavebeenpossible.

N. SHIVA KRISHNA

ABSTRACT
ThisdissertationisaboutakeyrecoveryattackcalledRandomSubgraphAttack onA5/1StreamCipher. A5/1isthestrongversionoftheencryptionalgorithm to protectovertheairprivacyofthe cellular voiceanddatacommunication.A5/1is basedonirregularclockingofthreelinearfeedbackshiftregisters.Thekeysizeis64 bits.Randomsubgraph attack isaTimememory Tradeoffattack.WeuseHellman's TimememoryTradeoffonsubgraphofspecialstates.Aftera2 48 parallelizabledata preparationstage theactualattackscanbecarriedoutinrealtimeonasingle PC. Theimplementationofrandomfunction,generatingspecialstatesisdone.

CONTENTS 1. Introduction
1.1 Cryptography 1.2 Cryptographic Techniques 1.3 Cryptanalysis 1.4 Attacks 1.5 Building Blocks

2. STREAM CIPHERS 2.1 Types of stream ciphers 2.2 Attacks on stream ciphers 3. GSM ARCHITECTURE 3.1 GSM Architecture and A5/1
3.2 Previous attacks on A5/1

4. RANDOM SUBGRAPH ATTACK

4.1 Overview of the attack 4.2 Detailed description of the attack

5. Results and Discussion

5.1 Implementation details 5.2 Analysis and Improvisation

6. Conclusion and Future Work

6.1 Conclusion 6.2 Future Work

BIBILOGRAPHY

1. INTRODUCTION
Cryptologyisthescienceofinformationprotectionagainstunauthorizedparties. Itcanbesplitupintocryptography(designofcryptographicsystems)andcryptanalysis (securityanalysisofcryptographicsystems)[14]. 1.1Cryptography: It is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication. Cryptography is not the only means of providing information security, butratheronesetoftechniquesanditsaimistodetectandpreventtheattacks. 1.2cryptographictechniques: Cryptographictechniquesaredividedinto2types.Theyare
I. Symmetrickeyencryption II. Asymmetrickeyencryption.

Symmetrickeyencryption The encryption scheme in which sender and receiver use the same key for encryption and decryption. It is also called as private key, single key, conventional or onekeyencryption.The2typesofsymmetrickeyciphersareblockciphersandstream ciphers.
1) Blockciphers

A block cipher is an encryption scheme in which the plaintext bits are transmittedintoblocksofafixedlengthtoveranalphabetA,andencryptsoneblock atatime.ExamplesofblockcipherareIDEA,SAFER,AES,FEAL,RC5andDESetc.
2) Streamciphers

Streamcipherisanencryptionschemeinwhich1bitisencryptedatatime.Examples ofstreamciphersareHC128,GRAIN,SALSA20,TRIVIUM, WG,A5/1andSCREAM etc.. Asymmetrickeyencryption The encryption scheme in which 2 keys are used , one for encryption which is publiclyknownandtheanotherfordecryptionwhichisprivateandsecure.Examples ofpublickeycipherareRSAandElGamal.

1.3Cryptanalysis: Cryptanalysis attempts to defeat cryptographic techniques (in general information security services) by using the mathematical techniques. The goal of cryptanalysis is to find some weakness or insecurity in a cryptographic scheme, thus permitting its subversion or evasion. Cryptanalyst does the job of cryptanalysis. Resistanceagainstallknown cryptanalyticattacksisthemostimportantpropertyofa newcipher.Thereshouldbenoattackfasterthanexhaustivekeysearch.

1.4Attacks Thefollowingaretheattackmodelsincryptography[17].

A ciphertextonly attack is one where the cryptanalyst tries to deduce the decryptionkeyorplaintextbyonlyobservingciphertext.Adversaryknowsonly ciphertext.

Aknownplaintextattackisonewheretheadversaryhasaquantityofplaintext andcorrespondingciphertext.

Achosenplaintextattackisonewheretheadversarychoosesplaintextandis thengivencorrespondingciphertext.

An adaptive chosenplaintext attack is a chosenplaintext attack wherein the choice of plaintext may depend on the ciphertext received from previous requests.

Achosenciphertextattackisonewheretheadversaryselectstheciphertextand is then given the corresponding plaintext . Adversary has the access to the equipmentusedfordecryptionforsomerestrictedamountoftime.

An adaptive chosenciphertext attack is a chosenciphertext attack where the choice of ciphertext may depend on the plaintext received from previous requests.

1.5Buildingblocks: a)LFSR Thisisthemainbuildingblockofstreamciphersbecauseofitssimplicity,the keystream it produces and speed of their hardware implementations. The only linear functionofsinglebitisXOR,thusitisashiftregisterwhoseinputbitisdrivenbythe XORofsomebitsoftheoverallshiftregistervalue.ItiswellknownthatanLFSRwith primitivefeedbackpolynomialofdegreedproducesanoutputwithperiod2d1. A linear feedback shift register (LFSR) of length L consists of L stages numbered0,1,...,L1,eachcapableofstoringonebitandhavingoneinputand one output; and a clock which controls the movement of data. During each unit of timethefollowingoperationsareperformed: (i)thecontentofstage0isoutputandformspartoftheoutputsequence; (ii)thecontentofstageiismovedtostagei1foreachi,1iL1; (iii)thenewcontentofstageL1isthefeedbackbitsjwhichiscalculated

byaddingtogethermodulo2thepreviouscontentsofafixedsubsetofstages0..L1.

ThefollowingareadvantagesofLFSRs[17].

LFSRsarewellsuitedtohardwareimplementation; Theycanproducesequencesoflargeperiod Theycanproducesequenceswithgoodstatisticalpropertiesand Becauseoftheirstructure,theycanbereadilyanalyzedusingalgebraic techniques.

ThemaindisadvantageofLFSRisitslinearitywhichleadseasycryptanalysis.In order to destroy linearity of LFSRs we can use combination generators , filter generatorsandclockcontrolledgenerators.

b)NLFSR In Non linear Feedback Shift Register the current state is a non linear

functionofitspreviousstate.Thestateofan(n,k)NLFSRisdefinedbytheorderedset of values of its state variables (X0 , X1 , . . . , Xn1 ). Since an (n, k)NLFSR is deterministic and finite, any sequence of consecutive states eventually converges to eitherasinglestate,oracycleofstates.Theperiodofan(n,k)NLFSRisthelengthof thelongestcyclicoutputsequenceitproduces.Theperiodofan(n,k)NLFSRcanbe n lessthanorequalto2 . AnumberofdifferentimplementationsofNLFSRbasedstreamciphersfor RFIDandsmartcardsapplicationshavebeenproposed,includingAchterbahn,Grain, KeeLoq, Trivium and VEST . NLFSRs have been shown to be more resistant to cryptanalytic attacks than LFSRs. However, construction of large NLFSRs with guaranteedlongperiodsremainsanopenproblem.AsystematicalgorithmforNLFSR synthesishasnotbeendiscoveredsofar.

c)Nonlinearfiltergenerator AlthoughLFSRsequenceshavemanydesirableproperties,usingthe LFSR

output sequence directly as keystream is not advisable due to the linearity of LFSR sequences. To make use of the desirable properties of the LFSR in a keystream generator for a stream cipher, it is necessary to introduce nonlinearity. A simple method is to use the contents of several stages of the LFSR as inputs to a nonlinear Booleanfunction,andusetheoutputofthefunctionasthekeystream.Thenonlinear Booleanfunctionisreferredtoasafilterfunction,andkeystreamgeneratorsbasedon a single LFSR and a nonlinear combining functions are known as nonlinear filter generators

d)SBoxes An SBox (Substitutionbox) is a basic component of symmetrickey

encryptionwhich performs substitution. In block ciphers they are typically used to obscuretherelationshipbetweenthekeyandtheciphertext.

e)FiniteStatemachine Inadigitalcircuit,anFSMmaybebuiltusingaprogrammablelogicdevice, programmablelogiccontroller,logicgates,andflipflopsorrelays.Morespecifically,a hardware implementation requires a register to store state variables, a block of combinational logic which determines the state transition, and a second block of combinationallogicthatdeterminestheoutputofanFSM.Oneoftheclassichardware implementationsistheRichardscontroller.

2. STREAM CIPHERS
InCryptography,astreamcipherisasymmetrickeycipherwhereplaintextbits are combined with a pseudorandom bit stream (i.e. keystream), typically by an exclusiveor (XOR) operation. Stream ciphers are based on OneTimePad. Stream ciphersareanimportantclassofsymmetrickeyencryptionalgorithms. Stream ciphers can be designed to be exceptionally fast, much faster than any block cipher. While block ciphers operate on large blocks of data, stream ciphers typically operate on smaller units of plaintext, usually bits. The encryption of any particular plaintext with a block cipher will result in the same ciphertext when the same key is used.Withastreamcipher,thetransformationofthesesmallerplaintextunitswillvary, depending on when they are encountered during the encryption process. A stream cipher generates a sequence of bits used as a key, which is called as keystream. Encryption is accomplished by combining the keystream with the plaintext, usually withthebitwiseXORoperation. Onetimepads Aonetimepad, sometimescalledVernam cipheruses astringof bits whichare generated completely at random. The keystream is the same length as the plaintext message and the random string is combined using bitwise XOR with the plaintext to producetheciphertext.Sincetheentirekeystreamisrandom,evenanopponentwith infinite computational resources can only guess the plaintext if he or she sees the ciphertext. Such a cipher is said to offer perfect secrecy, and the analysis of the one timepadisseenasoneofthecornerstonesofmoderncryptography.Whiletheonetime pad saw use during wartime over diplomatic channels requiring exceptionally high security,thefactthatthesecretkey(whichcanbeusedonlyonce)isaslongasthe

messageintroducesseverekeymanagementproblems.Whileperfectlysecure,theone timepadisingeneralimpractical.Streamciphersweredevelopedasanapproximation to the action of the onetime pad. While contemporary stream ciphers are unable to provide the satisfying theoretical security of the onetime pad, they are at least practical.

2.1 Types of stream ciphers

A stream cipher generates successive elements of the keystream based on an internal state. This state is updated in essentially two ways: if the state changes independently of the plaintext or ciphertext messages, the cipher is classified as a synchronousstreamcipher.Bycontrast,selfsynchronisingstreamciphersupdatetheir statebasedonpreviousciphertextbits. Synchronousstreamciphers In a synchronous stream cipher a stream of pseudorandom digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext(toencrypt)ortheciphertext(todecrypt).Inthemostcommonform,binary digitsareused,andthekeystreamiscombinedwiththeplaintextusingtheExclusive ORoperation(XOR).Thisistermedabinaryadditivestreamcipher. Inasynchronousstreamcipher,thesenderandreceivermustbeexactlyinstep fordecryptiontobesuccessful.Ifdigitsareaddedorremovedfromthemessageduring transmission,synchronisationislost.Torestoresynchronisation,variousoffsetscanbe tried systematically to obtain the correct decryption. Another approach is to tag the ciphertextwithmarkersatregularpointsintheoutput. If,however,adigitiscorruptedintransmission,ratherthanaddedorlost,onlya singledigitintheplaintextisaffectedandtheerrordoesnotpropagatetootherparts of the message. This property is useful when the transmission error rate is high; however,itmakesitlesslikelytheerrorwouldbedetectedwithoutfurther

mechanisms. Moreover, because of this property, synchronous stream ciphers are very susceptible to active attacks if an attacker can change a digit in the ciphertext, he might be able to make predictable changes to the corresponding plaintext bit; for example, flipping a bit in the ciphertext causes the same bit to be flipped in the plaintext.

Selfsynchronizingstreamciphers
AnotherapproachusesseveralofthepreviousNciphertextdigitstocomputethe keystream. Such schemes are known as selfsynchronizing stream ciphers, asynchronous stream ciphers or ciphertext autokey (CTAK). The advantage that the receiverwillautomaticallysynchronisewiththekeystreamgeneratorafterreceivingN ciphertext digits, making it easier to recover if digits are dropped or added to the message stream. Singledigit errors are limited in their effect, affecting only up to N plaintext digits. An example of a selfsynchronising stream cipher is a block cipher in CFBmode.

2.2AttacksonStreamCiphers
LFSRsynthesis The linear complexity C of any binary sequence is defined by the length of the shortestLFSRthatgeneratesthesequence.Givenatleast2Cbitsofabinarysequence withlinearcomplexityC,theBerlekampMasseyalgorithm[10]determinesanLFSRof lengthCinO(C2)time. AlgebraicAttacks Any stream cipher can be expressed as a system of multivariate algebraic equations, depending on the secret key and on the known keystream. The observed keystream canbesubstitutedinthissystem,andthesystemcanbesolvedtorecover thesecretkey.Thesetwosteps(findequationsandsolvethesystem)aretheprinciple

of algebraic attacks[12] . If the system corresponds to simultaneous equations in a largenumberofunknownsandofacomplex(nonlinear)type,thensolvingthesystem isdifficult.Anoverdefinednonlinearsystemcouldbelinearized(whereeachmonomial isreplacedbyanewvariable)andsolvedbyGaussianelimination.Theefficiencyofthe methoddependsonthealgebraicdegreeoftheequations. CorrelationandLinearAttacks In correlation and linear attacks one considers an overdefined system of linear inputoutput relations of some correlation (i.e. some noisy equations). In contrast, algebraicattacksdealwithexactequations. Correlation Attacks: The main scenario of correlation attacks are combination generators, assuming that the keystream bit Zt is correlated to one individual LFSR outputsequenceXtduetothecombiningfunction,hencePr(Xt=Zt)=p=0.5. Linear Attacks: The bitcorrelations of correlation attacks can be viewed as a special case of linear cryptanalysis[16], which tries to take advantage of high probability occurrencesoflinearrelationsinvolvingkeystreambitsandinitialstatebits.Ingeneral, thestartingpointisasystemoflinearrelationsinsomeoftheinitialstatebitsxwhich holdwithprobabilitiesdifferentfrom1/2fortheobservedkeystream. DifferentialAttacks Differential cryptanalysis [13] is a general method of cryptanalysis that is applicableprimarilytoblockciphers,butalsotostreamciphersandcryptographichash functions. One investigates how a difference in the input of the cipher affects the differenceintheoutput(requiringchosenplaintext).Thedifferenceistracedthrough the network of transformations F , discovering where the cipher exhibits nonrandom behavior.Thegoalistofindasuitabledifferential,i.e.afixedinputdifferencexanda fixed output difference z such that z=F(x) F(xx ) with high probability for a randominputx.Thedifferentialcanbeexploitedtodistinguishtheoutputwith

statistical methods (or to recover the key using more sophisticated variants). The statistical properties of the differential mainly depend on the nonlinear part of the cipher. TradeoffAttacks: Tradeoffattacksaregenericattacks,whereatradeoffintime,memoryanddata canbe achievedtoattackthestreamcipher.Duringtheprecomputationphase,which requiresPsteps,theadversaryexploresthegeneralstructureofthestreamcipherand summarizes his findings in large tables, requiring memory of size M. During the realtimephase,whichrequiresTsteps,theadversaryisgivenDframes(i.e.datawhich corresponds to D different keystreams produced by unknown keys and IVs), and his goalistousethetablestofindthekeyofoneframeasfastaspossible.In[6],Babbage concludesthatthe internalstateofthestreamciphershouldbeatleasttwiceaslarge asthekey.BiryukovandShamirpresentedsomeimprovedTMDtradeoffsin[1].

3. GSM Architecture
3.1 GSM Architecture and A5/1 Global system for mobile communication (GSM) is a globally accepted standard for digital cellular communication. GSM is the name of a standardization group established in 1982 to create a common European mobile telephone standard that would formulate specifications for a panEuropean mobile cellular radio system operatingat900MHz.Thebelowfigure[19]depictstheparametersofGSMsecurity.

The cipher used for voice communication confidentiality is commonly

knownasA5/1,whichisusedinEurope.AweakerversioncalledtheA5/2alsoexists, but it provides security against attackers capable of significantly less than 216 operations. The algorithms were intended to be kept secret, but have been reverse

engineered[3]basedoninformationreleasedin[9].Thispaperconsidersattacksonly against the cipher A5/1. A5/1 is a synchronous symmetrickey stream cipher, which reliesona64bitsecretkey. GSMusesA3AuthenticationAlgorithm,A8KeyGeneratingAlgorithmfor authenticationandkeygenerationrespectively. A3Algorithm: TheA3algorithmcomputesa32bitSignedResponse(SRES).TheK i andRANDaregivenasinputintotheA3algorithmandtheresultisthe32bitSRES. TheA3algorithmresidesontheSIMcardandattheAuC(AuthenticationCenter). A8AlgorithmTheA8algorithmcomputesa64bitcipheringkey(Kc).TheKiandthe RAND are inputted into the A8 algorithm and the result is the 64bit Kc. The A8 algorithmresidesontheISMcardandattheAuC. TherearethreeversionsoftheA5algorithm: 1)A5/1Thecurrentstandard for U.S.andEuropean networks.A5/1 isastream cipher. 2)A5/2ThedeliberatelyweakenedversionofA5/1thatisintendedforexporttonon westerncountries.A5/2isalsoastreamcipher. 3)A5/3Anewlydevelopedalgorithmusedfor3Gcommunication.A5/3isablock cipher.

A5/1
A5/1isanencryptionalgorithmusedintheGSMcellulartelephonestandardfor privacy which is used by 100 million customers in Europe.It isahardwareefficient streamcipherusedforGSMconversation.AGSMconversationissentasasequenceof frames, each frame containing 114 bits representing the digitized A to B communication, and 114 bits representing the digitized B to A communication, every

4.6millisecond.Anewsessionkeyisusedforeveryconversationandapubliclyknown frame counter Fn is mixed with session key Kc. Handset(Mobile Station) and Base Stationusethefirstandlasthalvesalternativelytoencryptanddecrypt. Pictorial representation of encryption and decryption using A5/1 is given
below[8].

Fig 2 A5/1 encryption and decryption using A5/1 for GSM

It uses 64bit secret key and 22bit publicly known frame counter which are loaded in parallel into 3 LFSRs of lengths 19 ,22 and 23 bits. All the 3 registers are clockedbasedonamajorityfunctionwhichisbasedonclockingtapsofthe3registers and registers whose clocking tap agrees with majority bit are clocked. The msbs of 3 LFSRs are XORed to produce 1bit key stream after every single clock. Random

subgraphattackandBirthdaybiasattackarethetwoimportantattacksagainstA5/1.

ThesetwoattacksarebasedonTimeMemoryTradeOff[1]. ThepictorialrepresentationofA5/1keystreamgeneratorisgivenbelow[18].

Fig 3 A5/1 Key Stream Generator

But there are subtle flaws in tap structure of registers,their non invertible clocking and frequent resets. In 2000, Alex Biryukov, Adi Shamir and David Wagner showedthatA5/1can becryptanalysedinrealtimeusing atimememorytradeoff attack,based onearlierworkbyJavanGolic[4].Thereare2attacksonallegedA5/1 inwhichsmallamountofdataisneededtoextractthekeyinrealtime.Firstattackis BiasedBirthdayattackwhichrequire2minutesofdataand1secondprocessingtime. Secondattack is Randomsubgraphattack which needs2seconds ofdataand several minutesofprocessingtime.Bothrequireextensivepreprocessingof248steps.These2 attacksarebasedonspecialstateswhichgenerateoutputbitsstartingwithaparticular patternoflengthk=16.Useofspecialstatesreducesnumberofdiskaccesses. Knownplaintextattackcanbecarriedoutinfollowing3steps[8],forthe

random subgraph and biased birthday attacks the initial step is performed using a time/memorytradeoffalgorithm. 1. Determine from the set of output bit streams the internal state of A5/1 for some cyclet>100. 2.ReverseA5/1todetermineasetofpossibleinitialstates. 3.ReversethemixingoftheframecountertodetermineastateofA5/1withonlythe sessionkeymixedin. Thestateobtainedinthelaststepcanbeusedtogenerateabitstreamforany desiredframecounterandthereforeissufficienttoperformdecryptionandencryption forthesessionkey.

3.2PreviousattacksonA5/1 Anderson and Roe[2] proposed an attack based on guessing the 41 bits in the shorterR1andR2registers,andderivingthe23bitsofthelongerR3registerfromthe output. However, they occasionally have to guess additional bits to determine the majoritybasedclockingsequence,andthusthetotalcomplexityoftheattackisabout O(245).AssumingthatastandardPCcantesttenmillionguessespersecond,thisattack needsmorethanamonthtofindonekey. Briceno[3]foundoutthatinallthedeployedversionsoftheA5/1algorithm,the 10 least significant of the 64 key bits were always set to zero. The complexity of exhaustivesearchisthusreducedtoO(254) Golic[4] described an improved attack which requires O(240) steps. However, eachoperationinthisattackismuchmorecomplicated,sinceitisbasedonthesolution ofasystemoflinearequations.Inpractice,thisalgorithmisnotlikelytobefasterthan thepreviousattackonaPC.

Golic[4] describes a general timememory tradeoff attack on stream ciphers (which was independently discovered by Babbage two years earlier), and concludes that it is possible to find the A5/1 key in 224 probes into random locations in a precomputed table with 248 128 bit entries. Since such a table requires a 64 terabyte harddisk,thespacerequirementisunrealistic.Alternatively,itispossibletoreducethe spacerequirementto862GB,butthenthenumberofprobesincreasestoO(228).Since random access to the fastest commercially available PC disks requires about 6 milliseconds, the total probing time is almost three weeks. In addition, this tradeoff point can only be used to attack GSM phone conversations that lasts more than 3 hours,whichagainmakesitunrealistic.

4. RANDOM SUBGRAPH ATTACK

4.1Overviewoftheattack Thisattackcanbecarriedoutinthefollowingsteps.
1. Generationofrandomspecialstates 2. GenerationofStartpoints. 3. IterateRandomFunctiononeachofthestartpoints(SP).Store(StartPoint,End

Point)pairs
4. DefinedifferentvariantsofRandomFunction. 5. Actualattack.Gives64bitinternalstateofA5/1forsomet>100.(t=noof

clockings

6. Reverseengineeroninternalstatetodetermineasetofpossibleinitialstates.

7. ReversethemixingoftheframecountertodetermineastateofA5/1withonly thesessionkeymixedin. 4.1.1GeneratingRandomspecialstates In this step we have to generate 64bit special states from 41bit partial states. Weneedtogenerate2 randomspecialstatesinthisstep. 4.1.2GenerationofStartpoints Inthisstepwehavetogenerate2 partialstates.
24 24

48bitrandomstartpointsfromthe41bit

4.1.3Store(StartPointEndPoint)pairs Iteraterandomfunctionon2
24

48bit random start points. After 212 iterations

storethe48bitoutputasEndpoint.Storeallthe(StartPoint,Endpoint)pairsonHard Disk,sortedintoincreasingendpointorder. 4.1.4VariantsofRandomFunction Wehavetofind2 differentvariantsofrandomfunctionbypermutingtheorder ofoutputbitsofrandomfunction.

12

4.1.5ActualAttack Ifwearegivenf(K)(48bitkeystream)forsomeunknownkeyKwhichislocated somewherealongoneofthecoveredpaths,wecanrecoverKbyrepeatedlyapplyingf intheeasyforwarddirectionuntilwehitastoredendpoint,jumptoitscorresponding startpointandcontinuetoapplyffromthere.Thelastpointbeforewehitf(K)againis likelytobethekeyKwhichcorrespondstothegivenciphertextf(K)[1]. 4.1.6ReverseengineeronInternalstate After a set of initial states S(t) for 101t327 has been obtained the attack proceeds to determining the actual premixing phase state S(0). Each register R1, R2 andR3hasbeenclockedbetween0andt1timesduringthemixing.Iteratethrough the106<220possiblecombinationsandseewhichonescreateinitialstatesS(0)that generatetheknownbitstream[8]. 4.1.7ReversemixingofFramecounter Thefinalstepoftheattackistocomputethesessionkey.Itissufficienttoreverse themixingof the framecounter andcomputeS(22). This state ofA5/1 with onlykc mixedinissufficienttoencryptanddecryptforkc[8].

4.2Detaileddescriptionoftheattack
RandomsubgraphattackisaTimeMemoryTradeoffattack.Thisattackrequires 2 seconds of GSM conversation and we can carry out the attack in 4 minutes of executiontimeonaPC,aftera2 preprocessing(storesspecialstatesonHD)stage which explores the structure of random function f, which maps one special into anotherspecialstate.Astateiscalledasspecialstateitproducesoutputsequencethat start with a particular kbit pattern alpha with k = 16. The probabilityofaframe containingsuchasequenceis(22864)2 =1642 .Thismeansinpractice
16 16 48

4.6ms2 /164<2sofGSMvoicetraffic.Themainideaoftheattackistomake mostofthespecialstatesaccessiblebysimplecomputationsfromthesubsetofspecial stateswhichareactuallystoredontheharddisk.

16

4.2.1TimeMemoryTradeoff Timememorytradeoff(TMTO)isasituationwherethecomputationtimecan be reduced at the cost of increased memory use, conversely the memory use can be reduced at the cost of slower program execution. As the relative costs of CPU cycles, RAMspace,andharddrivespacechangeharddrivespacehasforsometimebeen getting cheaper at a much faster rate than other components of computers the appropriate choices for timememory tradeoffs have changed radically. Often, by exploitingatimememorytradeoff,aprogramcanbemadetorunmuchfaster.Usually, aTMTOisdevelopedtoimprovethespeedofanalgorithmbyutilizingonetimework, which results in increased storage (memory) requirements when the resulting algorithmisexecuted. InTMTOtheattackrequiressomeonetimework,producinga tableofresults.Thistableisthenusedinordertoreducetheamountofworkrequired inanyparticularattack.

4.2.2Precomputationphase: InPrecomputationphaseallthespecialstatesmust
be produced. Approximately2 (2 *2 ) special states are possible for k=16. We can generateonlyspecialstatesasthereispossibilitythatclockingtapsareandoutputtaps areunrelatedfor16clockcycles.Butwehavetomakesurethatalphaisnotcoincided withshiftedversionsitself.Specialstatescanbeproducedasfollows[1].
1. Chose19arbitrarybitsforregisterR1,11arbitrarybitseachforregistersR2and
48 64 k

R3forrightmostbits.Nowwecanmakesurethatclockingtapsareknowntous for16clockcyclesaseachregistermoveswithaprobabilityof0.75.This41bit stateiscalledaspartialstate.

2. Foreachpartialstate,andforeachtransitionwecaneasilychoseunknownbits

ofR2andR3aswehaveknowledgeofclockingtaps,outputbitofR1andoutput bit.
3. For every transition either R2 or R3 or both will be moved. When only one

register is moved ( either R1 or R2 ) one new bit is shifted and its choice is forced. When 2 registers are moved 2 bits are shifted and there will be two valuations for each bit. These bits are called choice bits. If the state is not yet fully defined after 16 clock cycles then the undefined bits may be treated as choicebitsandanyassignmenttothemisvalid.
4. 41arbitrarybitsanditscorrespondingfirst7choicebitsgiveusaspecialstate. 5. Aboveprocessisrepeatedforeverypartialstate.

Define a random function f : {0, 1}48 {0, 1}48 . Let a be the special state identified by the 48bit input(i.e. 48 bit sequence following ). Initialize the internal state of A5/1 to this and clock A5/1 for 64 cycles. Now y(1)...y(16) = . Let bits y(17)...y(64)betheresultoff(a). The recommended preprocessing stage stores 2 tables on the hard disk. Each
12 24 12

tableisdefinedbyiteratingoneofthevariantsfi2 timeson2 randomlychosen48 bitstrings.Eachtable contains 2 (startpoint,endpoint)pairs,butimplicitlycovers about2 intermediatestates.Thecollectionofallthe2 tablesrequires2 diskspace, butimplicitlycoversabout2 redstates. At 6ms per probe, this requires more than a day. However, we can again use Rivest'sideaofspecialpoints:Wesaythataredstateisbrightifthefirst28bitsofits outputsequencecontainthe16bitalphaextendedby12additionalzerobits.During preprocessing,wepickarandomredstartpoint,andusefitoquicklyjumpfromone
48 36 12 36 24

red state to another. After approximately 2 jumps, weexpect to encounter another bright red state, at which we stop and store the pair of (start point, endpoint) in the harddisk.Duringtheactualattack,wefindthefirstredstateinthedata,iterateeach oneofthe 2 variantsoffoverituntilweencounterabrightredstate,andonlythen searchthisstateamongthepairsstoredinthedisk.Wethushavetoprobethediskonly once in each one of the t= 2 tables, and the totalprobing time is reduced to 24 seconds.Thetimecomplexityoftheattackis2 assumingtablelookupsareperformed inconstanttime.TheattackcanbeperformedonaPCin4minutes[1].
24 12 12

12

5. RESULTS AND DISCUSSION

5.1ImplementationDetails In this section we will discuss about the implementation details of random functionandgenerationofspecialstates. GenerationofSpecialStates: Inputtothismoduleis 41bit partial state.Thenitgives 64bit special state as output,whichguaranteestoproduceoutputbitsstartingwith16bitlengthalpha. Output: Initialvaluesof3registers R1=0444aa R2=000000 R3=0007ff No.oftimesR2&R3clockedisR2counter=9R3counter=7. Partialstateissuccessful. Specialstateis R11=0444aa R22=394000 R33=6687FF.

Belowisthescreenshotoftheaboveoutput.

Wehaveverifiedthespecialstatewhetheritgenerateskeystreamthatstartswith 16bitalphaornot. Output: The64bitspecialstatetakenis R1=0444aa R2=394000 R3=6687FF

First16bitsofkeystreamis 1000000000000000. Belowisthescreenshotoftheaboveoutput.

RandomFunction: Randomfunctiontakes48bitoutputprefixasinput,expandsitto64bitinternal stateandrunsA5/1Algorithmfor64clockcycles.Thendeletesfirst16bits(i.e.,alpha) from the 64bit output sequence and gives remaining 48 bits as output. The 48bit outputisusedasinputtotherandomfunction.

Output: 48bitinputtotheRandomfunctionisAA AA Thepartialstateis Specialstateis AA AA AA AA

02AAAA,000555,0002AA 000555 04 04 4002AA 04 04

02AAAA 04

48bitoutputis: 04

BelowisthescreenshotoftheoutputofRandomfunction.

5.2 Analysis and Improvisation

Thisattackrequiresasignificanteffortduringthesetup,butcanlaterbeusedto performrealtimeattacks using asingle PC .Somuch effort is neededingenerating special states and we need 224 probes( 212 per each of the table) to random disk locations.At6msperprobe,thisrequiresmorethanaday.Asolutiontothisproblem

iscallaspecialstateabrightaredstateifthefirst12bits followingareall0s.We cangeneratethetablenowbyiteratingthefunctionsfifromthestartpoint onwards untilabrightredstateisencountered(onanaverageevery212specialstateisalsoa bright red state). A bright red state can be generated by sampling special states and filteringoutnonbrightredstates.Nowduringtheactualattackdiskaccessisneeded onanaverageonlyforevery212 special states.Ittakes24secondsoftime(i.e.,6msX 212diskprobes)whichmakestheattackfeasible.But samplingoftableforbrightred states is a huge and complex process as we don't know how to sample the table of bright red states[1].Theattackrequiresapproximately160GB ofdiskspace,and4 minutesofexecutiontimeonaPC[8]]

6. CONCLUSION AND FUTURE WORK

6.1 Conclusion:
We have generated few special states from 41bit arbitrary partial states. We have implemented Random function. The Random function, which maps one specialstateintoanotherspecialstate.

6.2 Future Work:

AsafutureworkRandomSubgraphAttack canbefullyimplemented.Byusing Random Function we can store (Start point,End point) pairs. Develop 212 different variantsofRandomFunctionsothatwecancoveralltheSpecialStates. Wehaveto samplespecialstatesbygeneratingbrightredstateswhichmakestheattackfeasible.

BIBILOGRAPHY
1)AlexBiryukov AdiShamir David Wagner "Real TimeCryptanalysisof A5/1on a PC" 2)R.Anderson,M.Roe,A5,http://jya.com/cracka5.htm,1994. 3)M.Briceno,I.Goldberg,D.Wagner,ApedagogicalimplementationofA5/1, 3)An implementation of the GSM A/3 and A/8 algorithms:

http://www.scard.org/gsm/a3a8.txt 4)J. Golic, Cryptanalysis of Alleged A5 Stream Cipher, proceedings of EUROCRYPT'97,LNCS1233,pp.239{255,SpringerVerlag1997. 5)M. E. Hellman, A Cryptanalytic TimeMemory TradeOff, IEEE Transactions on InformationTheory,Vol.IT26,N4,pp.401{406,July1980. 6)S. Babbage, A Space/Time Tradeoff in Exhaustive Search Attacks on Stream Ciphers,EuropeanConventiononSecurityandDetection,IEEE Conference publication,No.408,May1995. 7)TimGuneysu,TimoKasper,MartinNovotny,ChristofPaar,Member,IEEE,andAndy Rupp"CryptanalysiswithCOPACOBANA" 8)LauriTarkkala"Tik110.551:AttacksagainstA5". [9] Racal Research Ltd. Extracts from Technical Information GSM System Security Study.10.6.1988[referred28.10.2000]. <http://jya.com/gsm061088.htm,RacalResearchLtd,19880610> 10)JamesMassey.ShiftRegisterSynthesisandBCHDecoding.IEEETransactionson InformationTheory,15(1):122127,1969.
11)

websourceshttp://en.wikipedia.org/wiki/Cryptography

12)NicolasCourtoisandWilliMeier.AlgebraicAttacksonStreamCipherswithLinear Feedback.InEliBiham,editor,EUROCRYPT,volume2656ofLectureNotesin ComputerScience,pages345359.Springer,2003. 13)EliBihamandAdiShamir.DifferentialCryptanalysisofDESlikeCryptosystems. J.Cryptology,4(1):372,1991. 14)AnalysisofLightWeightStreamCiphersbySimonFISCHER 15)GSMhttp://www.gsmfordummies.com 16)MitsuruMatsui.LinearCryptoanalysisMethodforDESCipher. 17) Handbook of Applied Cryptography, by A. Menezes, P van Oorschot, and S. . Vanstone,CRCPress,1996. 18)Wikipediahttp://en.wikipedia.org/wiki/A5/1 19)OtherWebSources