A5 Decryption(contents of the old THC Wiki page on the subject, partly edited, needs more work) AboutThe A5 algorithm has been broken (in theory) in 1998 but it's still widely used. The mobile operators still insist that the GSM customers (that's you and me!) are protected and that our data is safe. Tob build AirProbe, a A5/1 and A5/2 decryption is needed to be able to analyze real world networks. The decryption does not need to be realtime and it should not require an FPGA in the computer running AirProbe. The goal is to generate the rainbow table in a way that makes sure that at no point in time one person or computer is the holder of the keys to the kingdom. This means that we need an algorithm that can share the current state of computing between a number or hosts. If this means that things will be slower, need more bandwith or more CPU, that is all totally acceptable, as long as we can make sure that the table is not again in the hands of one person that can be pressured, influenced or bribed not to release it. How you can help
TODO
RequirementsThe project comes in stages.
Our ultimate goal is to crack A5/1:
A5 weaknessA5 is weak. That's A5/1 and A5/2. When you look at the algorithm it just gives you a bad feeling.
I did a quick example to visualize the entroypy. Crypto people love entropy. An easy way to visualize the entropy is to generate a picture of the relationship between two, three or four successive numbers generated by the algorithm. Ideally we should not see any structure. All pixels should be distributed randomly. lcamtufs ISN analyzsis explains more details about this method. I use a matlab script to generate the graphics. x.txt contains the output of the a5/1 key initialization algorithm. a = 0; b = 0; c = 0; d = 0; XD = 256; YD = 256; ZD = 256; M = dlmread('x.txt', ' '); V = M(2,2) I(1:((XD - 1) * 2), 1:((YD - 1) * 2)) = 0; for i=1:25600
end imshow(I); Figure 1: Key set to 0. FrameNumber? runs from 0-25600. We can see a structure. There is a relationship between the key state with FrameNumber? N and the key state with FrameNumber? N - 1. key_0_fn_0-25600.png TODO: add more. A5/GSM encryption exampleTODO: write down how a5 works and how the data looks that is encrypted and what the first encrypted message from/to basestation is and which bits are static/known/guessable. The Frame Number (FN) wrapps around every 3h 28min 53 sec and 750ms. A layer 1 GSM message is 23 octet long. It is padded with 0x2b if less than 23 octet content data are to be send. How to encode 1 GSM message (after padding):
First encrypted message send from MS to BTS is 'Ciphering Mode Complete': 000: ?? ?? ?? 06 32 2b 2b 2b - 2b 2b 2b 2b 2b 2b 2b 2b 001: 2b 2b 2b 2b 2b 2b 2b
This message tells the BTS to start ciphering. The first encrypted message send from the BTS to the MS is either a MMIdentityRequest followed by a empty GSM message or a empty GSM message. Both of them contain plenty known plaintext: The 0x2b GSM message padding octet. 000: 03 42 0d 05 18 03 2b 2b - 2b 2b 2b 2b 2b 2b 2b 2b 001: 2b 2b 2b 2b 2b 2b 2b
or 000: 03 03 01 2b 2b 2b 2b 2b - 2b 2b 2b 2b 2b 2b 2b 2b 001: 2b 2b 2b 2b 2b 2b 2b
Misc Ideas
FPGA IdeasBrute ForceSome initial thoughts on A5/1 and FPGA. All this needs to be calculated more precisely. Each clock cycle the A5 implementation should output 64 bit of streamcipher. We can put multiple A5 implementations on the same FPGA chip. The calculation is based on a pipelined implementation of A5. The three LSFR registers are in total 19 + 22 + 23 = 64bit long. The first LSFR requires 5 Logical Units (LU's, e.g xor). The second requires 3 LU's and the last one requires 5 LU's. All together 13 LU's and 64 bit. The Trap register add's 1 LU per LSFR. Makes 16 LU's and 64bit. Generating the state (with key and FrameNumber? (FN)) requires 64 + 22 = 88 steps. This is followed by another 100 cycles. Each of the 100 cycles requires 1 LU less per LSFR. After these 100 cycles we want to generate about 64 bit of output (e.g. enother 64 cycles).
After 88 + 100 + 64 cycles we will start seeing 64 bit of stream cipher output for each cycle. This is all not optimized. We do not need the first 9 steps because the Tap register only start at bit 8. we also do not need all the LU's or registers for the first 18 steps because the first LSFR is not fully used until step 18. Same for the last 64 steps. For each of the last 64 steps we only need 2 LU's and 1 register less for each step. We decided to use Xilinx. Altera is a good choice as well but at the moment most of us worked with xilinx before. The Virtex-5 from Xilinx LX330 has 330.000 LU's and runs at 500 Mhz. That brings us down to 4 days per development board?! But the boards and chips are to expensive. Better to stick with LX50. Brute Force II
Some more precise calculation by David Hulton: With this design, we will probably only be able to fit 4 fully pipelined instances of A5/1 on here unless we can hand-optimize the placement better than the Xilinx tools and code in some of the shortcuts that you mentioned on the a5 cracking page. I'll work on this a bit more and see if I can reduce the logic down. Slice Logic Utilization:
Slice Logic Distribution:
IO Utilization:
Specific Feature Utilization:
Total equivalent gate count for design: 155,730 Additional JTAG gate count for IOBs: 4,224 Possible boards
The LX330 boards cost $5.000. Because we can put 4x more a5/1 implementations on them and they run 6.6x faster it might be worth it. Rainbow TableTraditional rainbow tables take the key as input. Our key is 88 bit (of which the last 22 bit are the known Frame Number). We can not generate a rainbox table for 288 key combinations. Idea IThe state table of all 3 LSFR's combined is just 64 bit. The A5 initialization process (e.g. seeding in key + FN and mixing it 100 cycles) is reverseable. Thus once we know the key state we can compute the key easily. Generating rainbow tables for 64 bit keys is difficult (TODO: calculate how difficult and how many FPGA's required). This attack would work regardless of the frame number and regardless of the key length (54, 64 or 128 bit). It also uses less LU's than the normal key brute force implementation. All 3 LSFR can be stuck together to get one 64bit register: | R1 19bit | R2 22bit | R3 23bit | Rought idea of generating rainbow table with 236 tables:
Problems:
Idea II(This Idea is now obsolete) Maybe it's enough to generate a rainbow table for FrameNumber? 0. Calculating all 254 keys with an FPGA and generating a rainbow tables is a matter of days (e.g. possible). Can a rainbow table generated with FrameNumber? == 0 be used to decrypt packets that do not have Frame Number set to 0? Idea IIIIs it possible to reduce a LSFR register? By this i mean exist there a shorter LSFR register that would produce the same output (for a certain class of keys)? Idea IVWe do not need to generate rainbow tables for all possible keystates. Let's assume we generate rainbow tables for 1/4 of all keystates (e.g 62bit). If we sniff 64 bit known plaintext our chances that we can crack it with the rainbow table is 25%. A5 is reversable: Let N be the index of current working bit of the A5 algorithm (e.g. after N bits of output have been produced and N bit of plaintext have been encrypted). Let keystate(N) be the state of the keystate after N bits have been produced. Let plaintext(N) be the N-th bit of the plaintext. It is possible to calculate keystate(N-1) if keystate(N) and plaintext(0..N) is known. Let's assume we know 65 bit of plaintext. We first try to find a match in the rainbow table for bit 0..63 and then we try to find a match for bit 1..64. The probability for 65 bit known plaintext it is already 1 - (3/4)(65 - 64 + 1) = 43.75%. For 80 bit known plaintext it is 1 - (3/4)(80 - 64 + 1) = 98.997%. Let's get this further down: Generate 1/64 of all rainbow tables (which makes it a 58bit problem): If we get 128 bit of known plaintext our chances of decoding it are 1 - (63/64)(128 - 64 + 1) == 64% or 95% if 256 bit of plaintext are known. The maximum number of bits that are encrypted under the same keystate is 114. There are 4 bursts of 114 bit and the plaintext of each of the bursts is known. For each burst the propability of cracking it with only 1/64th of the rainbow table is: 1-(63/64)(114 - 64 + 1) = 55.2% Considering that we have a 55.2% chance for each of the 4 burst: 1 - (1 - 0.552)4 = 95.97% Limitation: It is obivous that this is working if we are dealing with successive bits of plaintext. It is less obvious that this also works as long as the 65 bit plaintext as distributed equaly (FIXME: can we optimize this?).
Further optimization:
Idea VWe have known plaintext. The first encrypted message send from the BTS to the MS is amost all 0x2b (except for the first three octets). This means we can implement the attack by Anderson and Roe: Guessing the 41 bit in the shorter R1 and R2 registers, and deriving the 23bit of the longer R3 register from the output. Anderson and Roe's attack is further described in A5/1 FPGA cracking. Calculating Rainbow tables for this is the next challenge. Combing this with Idea IV makes it a 41-6 = 35 bit problem. Idea VIAre there 'useless' bits in R2? It only has two trap registers. Does this help us calculating the value of others? Resources
List of used encryption around the WorldKnown GSM Netowrk Encryption usage Version 1.12 8th December 2005 gsm_network_encryption_list.csv If you have updates (what about France??) please send an email to a5 at lists.airprobe.org.
Converting the CSV to wiki table: cat gsm_network_encryption_list.csv | sed 's/"g' | while read x; do echo "
History: When A5/1 came out mostly germany (as the bordering country to the soviet block) wanted to implement strong encryption. Other Nato members (led by france) were worried that the middle east would use strong encryption. Thus they cut a deal to come up with a weaker version, A5/2. These days both (A5/1 and A5/2) have been broken. A5/3 has not been seen in the wild yet. Other comments:
How to check if A5/1 is usedThere are two ways. You can either use Nokia's Netmonitor (aka Field Tester) or you can use any dct3 mobile (like the nokia 3310) and gammu + PC to find out. The netmonitor is the easier way because you do not need a PC. The netmonitor software runs on many famous mobiles phones (nokia 6630, 6680, n70, sony erricson, ..)
Example how it looks like: Results of this example:
The other method is by using gammu and a dct3 trace mobile (like the nokia 3310) connected to the PC. Start a trace, make a phonecall and send in the out.xml file that gammu produces. See our main project page on how to use gammu and dct3 trace mobiles. Check the GSMSP Project for more infos on how to use gammu. HD Random Access TimeThe cracking of A5/1 requires very fast random access to the harddrive. We are currently looking for the most performing harddrives and raids. If you have access to a raid with at least 8 disks please run this test for us. Download: random_access.c ; The example assumes that the raid is available at /dev/sda and has 8 harddrives. # gcc -Wall -O2 -o random_acccess random_access.c # for x in seq 1 8; do ./random_access /dev/sda >log${x}.txt &; done # cat log*.txt >results.txt Send results.txt, the type of raid and the number of harddrives in the raid to a5 at lists.airprobe.org.net. News Links =
Links
注:deCryption(原文出处,翻译整理仅供参考!) |