Take a look at http://reflextor.com/trac/a51/wiki/FurtherReading There you will find a paper from 2003 which describes the attack (chapter 6). I actually did not read the paper until work was almost finished and collected the pieces of the puzzle from wiki.thc.org/gsm (via web.archive.org), a talk at CCC Summer Camp 2007 (search video.google.com), and gsmfordummies.com. The LAPDm frame we are interested in is the first encrypted frame of the conversation. It is sent from handset to the BTS. The LAPDm command code is CIPHER_MODE_COMPLETE. It informs the BTS that encryption will be used from now on. Since it only carries a boolean message by simply being sent, all other content is at default values. There is also a method that takes advantage of forward error correction being applied before encryption, but i did not dig through the math yet. You can use the same tables in that case. A LAPDm frame is 23 bytes. after forward error correction is applied, that 184 bits become 456 bits. those are sent in 4 bursts, hence 114bits x 4. This is explained in the wiki under the node GSM. With 2^28.5 x 2^8.5 chains you have 2^37 chains or 2^41 bytes which makes 2TB for the whole table. With that amount of stored chains you have an 80% probability of finding the correct value. But you do not need to store 16 bytes per chain, as you can compress away 11 constant bits from the start value, 15 constant bits from the end value (a distinguished point), and about 20 bits from the end value, because the values will be in sorted order. Chopping of 22 bits means you have to store 2^22 32bit values as an index into the compressed sorted end values. So (64 - 11) + (64 - 15 - 22) = 80 bits = 10 bytes per chain, + 16mbyte index per table, so if you sum that together you arrive at less than 2TB. As for your other question, i said i expect people to do continue after reaching 50%, or 80% for that matter, since during the lookup phase, the program will still be running in the background to accept lookup requests which gives the opportunity to keep generating. Also during the lookup phase you need to do precomputation on the lookup values. These precomputations can be reused as new chains and stored. As for the amount of tables produced so far, i know of 2 tables, because they are stored under my table. Besides that, there is only one other node reporting generation of chains to the stats server this other table is about 3% complete. Since reporting to the stats server is optional and we are all playing hide and seek a bit, i dont know myself how many tables are being generated. One important thing to note here is that a node has to compute more than 2^28.5 chains, because not all of them are unique. I dont know the exact number needed, but it will be above 600m definitely (i would be surprised!) less than 1000m. You can then estimate the time needed to complete a table by doing the math with the rate your hardware achieves.
is this attack based on a publicly available paper that we can read ? > where to obtain LAPDm frame ? uplink or downlink ? why did you say we > have got 4*114 bits of known plain text ? how much more data we > should generate comparing to 2TB to achieve 80% success ? you said > people will not continue generating the tables after 50% , its just > because of the lookup time or storing data being expensive or what ? > and finally how much tables have been produced until now ? i have a > free computer with two CUDA enabled cards and i will contribute with > them now its good to have some ideas how much time does it need to be > working ? > > thank you > > post your questions. > > > thanks . sorry this is probably my fault but i couldn't clearly > > understand what would be the success chance of this attack , roughly > > and why . is there any detailed paper on this so i can put some time > > and read to finally understand it or maybe you can elaborate more ? > > > > thank you in advance > > > > > > > > the keyspace of A5/1 is 2^64. When you record a conversation you > can guess > > > a > > > whole LAPDm frame, > > > so you get enough plaintext and thus A5/1 keystream that you can > do 204 > > > lookups in the database. > > > That is because, suppose you have 114 bits of known keystream, > then you can > > > try to reverse the > > > A5/1 register state that produced keystream 0..63 or you can try > to reverse > > > the state that produced > > > keystream bits 1..64 and so on. with 114 bits you would get 51 > values to > > > lookup in the table that > > > gives you a register state for a keystream. we get 4x114 bits of > known > > > plaintext. > > > So a table with 2^57 values stored in it, would give you a success > > > probability of 1/(2^7) (because > > > 57 + 7 = 64). The probability of a failed lookup is thus 1-1/(2^7) > . > > > calculate (1-1/2^7)^204 and you get the probability that 204 > lookups fail. > > > that would be 20%, > > > so the tables at this point of completion can decrypt 80% of the > > > conversations. > > > 50%, 80% ... actually there is no definitive point to say we are > done it is > > > more like > > > the chances of success are continually rising. > > > > > > i'm not advanced on cryptography . would you tell me why 50% ? > > >> > > >> From: *Sascha Krissler*<[email protected]> > > >> Date: Fri, Sep 11, 2009 at 8:16 PM > > >> Subject: Re: [A51] sucess? > > >> To: [email protected] > > >> > > >> When reach our initial goal of 2^8.5 tables with 2^28.5 unique > chains > > >> each, we would get a probability > > >> of around 50%, so at some point this would be the actual > probability. > > >> It is not unlikely that people will carry > > >> on generating, increasing this probability and also increasing > the > > >> lookup speed. > > >> > > >> > suppose the community build all the tables then how much is our > > >> success chance to crack a given recorded conversation ? > > >> > > > _______________________________________________ A51 mailing list A51@ > lists.reflextor.com http://lists.lists.reflextor.com/cgi-bin/mailman/ > > listinfo/a51 ________________________________________________________________ Neu: WEB.DE Doppel-FLAT mit Internet-Flatrate + Telefon-Flatrate für nur 19,99 Euro/mtl.!* http://produkte.web.de/go/02/ _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
