ptrkrysik | 18b631e | 2014-12-15 09:09:18 +0100 | [diff] [blame] | 1 | /* |
| 2 | * A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" |
| 3 | * encryption algorithms. |
| 4 | * |
| 5 | * Copyright (C) 1998-1999: Marc Briceno, Ian Goldberg, and David Wagner |
| 6 | * |
| 7 | * The source code below is optimized for instructional value and clarity. |
| 8 | * Performance will be terrible, but that's not the point. |
| 9 | * |
| 10 | * This software may be export-controlled by US law. |
| 11 | * |
| 12 | * This software is free for commercial and non-commercial use as long as |
| 13 | * the following conditions are adhered to. |
| 14 | * Copyright remains the authors' and as such any Copyright notices in |
| 15 | * the code are not to be removed. |
| 16 | * Redistribution and use in source and binary forms, with or without |
| 17 | * modification, are permitted provided that the following conditions |
| 18 | * are met: |
| 19 | * |
| 20 | * 1. Redistributions of source code must retain the copyright |
| 21 | * notice, this list of conditions and the following disclaimer. |
| 22 | * 2. Redistributions in binary form must reproduce the above copyright |
| 23 | * notice, this list of conditions and the following disclaimer in the |
| 24 | * documentation and/or other materials provided with the distribution. |
| 25 | * |
| 26 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED |
| 27 | * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF |
| 28 | * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| 29 | * IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY |
| 30 | * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 31 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE |
| 32 | * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| 33 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER |
| 34 | * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR |
| 35 | * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN |
| 36 | * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 37 | * |
| 38 | * The license and distribution terms for any publicly available version |
| 39 | * or derivative of this code cannot be changed. i.e. this code cannot |
| 40 | * simply be copied and put under another distribution license |
| 41 | * [including the GNU Public License]. |
| 42 | * |
| 43 | * Background: The Global System for Mobile communications is the most |
| 44 | * widely deployed digital cellular telephony system in the world. GSM |
| 45 | * makes use of four core cryptographic algorithms, none of which has |
| 46 | * been published by the GSM MOU. This failure to subject the |
| 47 | * algorithms to public review is all the more puzzling given that over |
| 48 | * 215 million GSM subscribers are expected to rely on the claimed |
| 49 | * security of the system. |
| 50 | * |
| 51 | * The four core GSM cryptographic algorithms are: |
| 52 | * A3 authentication algorithm |
| 53 | * A5/1 "stronger" over-the-air voice-privacy algorithm |
| 54 | * A5/2 "weaker" over-the-air voice-privacy algorithm |
| 55 | * A8 voice-privacy key generation algorithm |
| 56 | * |
| 57 | * In April of 1998, our group showed that COMP128, the algorithm used by the |
| 58 | * overwhelming majority of GSM providers for both A3 and A8 functionality |
| 59 | * is fatally flawed and allows for cloning of GSM mobile phones. |
| 60 | * |
| 61 | * Furthermore, we demonstrated that all A8 implementations we could locate, |
| 62 | * including the few that did not use COMP128 for key generation, had been |
| 63 | * deliberately weakened by reducing the keyspace from 64 bits to 54 bits. |
| 64 | * The remaining 10 bits are simply set to zero! |
| 65 | * |
| 66 | * See http://www.scard.org/gsm for additional information. |
| 67 | * |
| 68 | * [May 1999] |
| 69 | * One question so far unanswered is if A5/1, the "stronger" of the two |
| 70 | * widely deployed voice-privacy algorithm is at least as strong as the |
| 71 | * key. Meaning: "Does A5/1 have a work factor of at least 54 bits"? |
| 72 | * Absent a publicly available A5/1 reference implementation, this question |
| 73 | * could not be answered. We hope that our reference implementation below, |
| 74 | * which has been verified against official A5/1 test vectors, will provide |
| 75 | * the cryptographic community with the base on which to construct the |
| 76 | * answer to this important question. |
| 77 | * |
| 78 | * Initial indications about the strength of A5/1 are not encouraging. |
| 79 | * A variant of A5, while not A5/1 itself, has been estimated to have a |
| 80 | * work factor of well below 54 bits. See http://jya.com/crack-a5.htm for |
| 81 | * background information and references. |
| 82 | * |
| 83 | * With COMP128 broken and A5/1 published below, we will now turn our |
| 84 | * attention to A5/2. |
| 85 | * |
| 86 | * [August 1999] |
| 87 | * 19th Annual International Cryptology Conference - Crypto'99 |
| 88 | * Santa Barbara, California |
| 89 | * |
| 90 | * A5/2 has been added to the previously published A5/1 source. Our |
| 91 | * implementation has been verified against official test vectors. |
| 92 | * |
| 93 | * This means that our group has now reverse engineered the entire set |
| 94 | * of cryptographic algorithms used in the overwhelming majority of GSM |
| 95 | * installations, including all the over-the-air "voice privacy" algorithms. |
| 96 | * |
| 97 | * The "voice privacy" algorithm A5/2 proved especially weak. Which perhaps |
| 98 | * should come as no surprise, since even GSM MOU members have admitted that |
| 99 | * A5/2 was designed with heavy input by intelligence agencies to ensure |
| 100 | * breakability. Just how insecure is A5/2? It can be broken in real time |
| 101 | * with a work factor of a mere 16 bits. GSM might just as well use no "voice |
| 102 | * privacy" algorithm at all. |
| 103 | * |
| 104 | * We announced the break of A5/2 at the Crypto'99 Rump Session. |
| 105 | * Details will be published in a scientific paper following soon. |
| 106 | * |
| 107 | * |
| 108 | * -- Marc Briceno <marc@scard.org> |
| 109 | * Voice: +1 (925) 798-4042 |
| 110 | * |
| 111 | */ |
| 112 | |
| 113 | #ifndef A5_1_2_H |
| 114 | #define A5_1_2_H |
| 115 | |
| 116 | #include <stdio.h> |
| 117 | |
| 118 | |
| 119 | /* Masks for the shift registers */ |
| 120 | #define R1MASK 0x07FFFF /* 19 bits, numbered 0..18 */ |
| 121 | #define R2MASK 0x3FFFFF /* 22 bits, numbered 0..21 */ |
| 122 | #define R3MASK 0x7FFFFF /* 23 bits, numbered 0..22 */ |
| 123 | #ifdef A5_2 |
| 124 | #define R4MASK 0x01FFFF /* 17 bits, numbered 0..16 */ |
| 125 | #endif /* A5_2 */ |
| 126 | |
| 127 | |
| 128 | #ifndef A5_2 |
| 129 | /* Middle bit of each of the three shift registers, for clock control */ |
| 130 | #define R1MID 0x000100 /* bit 8 */ |
| 131 | #define R2MID 0x000400 /* bit 10 */ |
| 132 | #define R3MID 0x000400 /* bit 10 */ |
| 133 | #else /* A5_2 */ |
| 134 | /* A bit of R4 that controls each of the shift registers */ |
| 135 | #define R4TAP1 0x000400 /* bit 10 */ |
| 136 | #define R4TAP2 0x000008 /* bit 3 */ |
| 137 | #define R4TAP3 0x000080 /* bit 7 */ |
| 138 | #endif /* A5_2 */ |
| 139 | |
| 140 | |
| 141 | /* Feedback taps, for clocking the shift registers. |
| 142 | * These correspond to the primitive polynomials |
| 143 | * x^19 + x^5 + x^2 + x + 1, x^22 + x + 1, |
| 144 | * x^23 + x^15 + x^2 + x + 1, and x^17 + x^5 + 1. */ |
| 145 | |
| 146 | |
| 147 | #define R1TAPS 0x072000 /* bits 18,17,16,13 */ |
| 148 | #define R2TAPS 0x300000 /* bits 21,20 */ |
| 149 | #define R3TAPS 0x700080 /* bits 22,21,20,7 */ |
| 150 | #ifdef A5_2 |
| 151 | #define R4TAPS 0x010800 /* bits 16,11 */ |
| 152 | #endif /* A5_2 */ |
| 153 | |
| 154 | |
| 155 | typedef unsigned char byte; |
| 156 | typedef unsigned long word; |
| 157 | typedef word bit; |
| 158 | |
| 159 | |
| 160 | /* Calculate the parity of a 32-bit word, i.e. the sum of its bits modulo 2 |
| 161 | */ |
| 162 | bit parity(word x) |
| 163 | { |
| 164 | x ^= x >> 16; |
| 165 | x ^= x >> 8; |
| 166 | x ^= x >> 4; |
| 167 | x ^= x >> 2; |
| 168 | x ^= x >> 1; |
| 169 | return x&1; |
| 170 | } |
| 171 | |
| 172 | |
| 173 | /* Clock one shift register. For A5/2, when the last bit of the frame |
| 174 | * is loaded in, one particular bit of each register is forced to '1'; |
| 175 | * that bit is passed in as the last argument. */ |
| 176 | #ifndef A5_2 |
| 177 | word clockone(word reg, word mask, word taps) |
| 178 | { |
| 179 | #else /* A5_2 */ |
| 180 | word clockone(word reg, word mask, word taps, word loaded_bit) { |
| 181 | #endif /* A5_2 */ |
| 182 | word t = reg & taps; |
| 183 | reg = (reg << 1) & mask; |
| 184 | reg |= parity(t); |
| 185 | #ifdef A5_2 |
| 186 | reg |= loaded_bit; |
| 187 | #endif /* A5_2 */ |
| 188 | return reg; |
| 189 | } |
| 190 | |
| 191 | |
| 192 | /* The three shift registers. They're in global variables to make the code |
| 193 | * easier to understand. |
| 194 | * A better implementation would not use global variables. */ |
| 195 | word R1, R2, R3; |
| 196 | #ifdef A5_2 |
| 197 | word R4; |
| 198 | #endif /* A5_2 */ |
| 199 | |
| 200 | |
| 201 | /* Return 1 iff at least two of the parameter words are non-zero. */ |
| 202 | bit majority(word w1, word w2, word w3) { |
| 203 | int sum = (w1 != 0) + (w2 != 0) + (w3 != 0); |
| 204 | if (sum >= 2) |
| 205 | return 1; |
| 206 | else |
| 207 | return 0; |
| 208 | } |
| 209 | |
| 210 | |
| 211 | /* Clock two or three of R1,R2,R3, with clock control |
| 212 | * according to their middle bits. |
| 213 | * Specifically, we clock Ri whenever Ri's middle bit |
| 214 | * agrees with the majority value of the three middle bits. For A5/2, |
| 215 | * use particular bits of R4 instead of the middle bits. Also, for A5/2, |
| 216 | * always clock R4. |
| 217 | * If allP == 1, clock all three of R1,R2,R3, ignoring their middle bits. |
| 218 | * This is only used for key setup. If loaded == 1, then this is the last |
| 219 | * bit of the frame number, and if we're doing A5/2, we have to set a |
| 220 | * particular bit in each of the four registers. */ |
| 221 | void clock(int allP, int loaded) { |
| 222 | #ifndef A5_2 |
| 223 | bit maj = majority(R1 & R1MID, R2 & R2MID, R3 & R3MID); |
| 224 | if (allP || (((R1&R1MID) != 0) == maj)) |
| 225 | R1 = clockone(R1, R1MASK, R1TAPS); |
| 226 | if (allP || (((R2&R2MID) != 0) == maj)) |
| 227 | R2 = clockone(R2, R2MASK, R2TAPS); |
| 228 | if (allP || (((R3&R3MID) != 0) == maj)) |
| 229 | R3 = clockone(R3, R3MASK, R3TAPS); |
| 230 | #else /* A5_2 */ |
| 231 | bit maj = majority(R4 & R4TAP1, R4 & R4TAP2, R4 & R4TAP3); |
| 232 | if (allP || (((R4&R4TAP1) != 0) == maj)) |
| 233 | R1 = clockone(R1, R1MASK, R1TAPS, loaded << 15); |
| 234 | if (allP || (((R4&R4TAP2) != 0) == maj)) |
| 235 | R2 = clockone(R2, R2MASK, R2TAPS, loaded << 16); |
| 236 | if (allP || (((R4&R4TAP3) != 0) == maj)) |
| 237 | R3 = clockone(R3, R3MASK, R3TAPS, loaded << 18); |
| 238 | R4 = clockone(R4, R4MASK, R4TAPS, loaded << 10); |
| 239 | #endif /* A5_2 */ |
| 240 | } |
| 241 | |
| 242 | |
| 243 | /* Generate an output bit from the current state. |
| 244 | * You grab a bit from each register via the output generation taps; |
| 245 | * then you XOR the resulting three bits. For A5/2, in addition to |
| 246 | * the top bit of each of R1,R2,R3, also XOR in a majority function |
| 247 | * of three particular bits of the register (one of them complemented) |
| 248 | * to make it non-linear. Also, for A5/2, delay the output by one |
| 249 | * clock cycle for some reason. */ |
| 250 | bit getbit() { |
| 251 | bit topbits = (((R1 >> 18) ^ (R2 >> 21) ^ (R3 >> 22)) & 0x01); |
| 252 | #ifndef A5_2 |
| 253 | return topbits; |
| 254 | #else /* A5_2 */ |
| 255 | static bit delaybit = 0; |
| 256 | bit nowbit = delaybit; |
| 257 | delaybit = ( |
| 258 | topbits |
| 259 | ^ majority(R1 & 0x8000, (~R1) & 0x4000, R1 & 0x1000) |
| 260 | ^ majority((~R2) & 0x10000, R2 & 0x2000, R2 & 0x200) |
| 261 | ^ majority(R3 & 0x40000, R3 & 0x10000, (~R3) & 0x2000) |
| 262 | ); |
| 263 | return nowbit; |
| 264 | #endif /* A5_2 */ |
| 265 | } |
| 266 | |
| 267 | |
| 268 | /* Do the A5 key setup. This routine accepts a 64-bit key and |
| 269 | * a 22-bit frame number. */ |
| 270 | void keysetup(byte key_reversed[8], word frame) { |
| 271 | int i; |
| 272 | bit keybit, framebit; |
| 273 | |
| 274 | byte key[8]; |
| 275 | for(i=0; i<8; i++){ |
| 276 | key[i] = key_reversed[7-i]; |
| 277 | } |
| 278 | /* Zero out the shift registers. */ |
| 279 | R1 = R2 = R3 = 0; |
| 280 | #ifdef A5_2 |
| 281 | R4 = 0; |
| 282 | #endif /* A5_2 */ |
| 283 | |
| 284 | |
| 285 | /* Load the key into the shift registers, |
| 286 | * LSB of first byte of key array first, |
| 287 | * clocking each register once for every |
| 288 | * key bit loaded. (The usual clock |
| 289 | * control rule is temporarily disabled.) */ |
| 290 | for (i = 0; i < 64; i++) { |
| 291 | clock(1, 0); /* always clock */ |
| 292 | keybit = (key[i/8] >> (i & 7)) & 1; /* The i-th bit of the key */ |
| 293 | R1 ^= keybit; |
| 294 | R2 ^= keybit; |
| 295 | R3 ^= keybit; |
| 296 | #ifdef A5_2 |
| 297 | R4 ^= keybit; |
| 298 | #endif /* A5_2 */ |
| 299 | } |
| 300 | |
| 301 | |
| 302 | /* Load the frame number into the shift registers, LSB first, |
| 303 | * clocking each register once for every key bit loaded. |
| 304 | * (The usual clock control rule is still disabled.) |
| 305 | * For A5/2, signal when the last bit is being clocked in. */ |
| 306 | for (i = 0; i < 22; i++) { |
| 307 | clock(1, i == 21); /* always clock */ |
| 308 | framebit = (frame >> i) & 1; /* The i-th bit of the frame # */ |
| 309 | R1 ^= framebit; |
| 310 | R2 ^= framebit; |
| 311 | R3 ^= framebit; |
| 312 | #ifdef A5_2 |
| 313 | R4 ^= framebit; |
| 314 | #endif /* A5_2 */ |
| 315 | } |
| 316 | |
| 317 | |
| 318 | /* Run the shift registers for 100 clocks |
| 319 | * to mix the keying material and frame number |
| 320 | * together with output generation disabled, |
| 321 | * so that there is sufficient avalanche. |
| 322 | * We re-enable the majority-based clock control |
| 323 | * rule from now on. */ |
| 324 | for (i = 0; i < 100; i++) { |
| 325 | clock(0, 0); |
| 326 | } |
| 327 | /* For A5/2, we have to load the delayed output bit. This does _not_ |
| 328 | * change the state of the registers. For A5/1, this is a no-op. */ |
| 329 | getbit(); |
| 330 | |
| 331 | |
| 332 | /* Now the key is properly set up. */ |
| 333 | } |
| 334 | |
| 335 | |
| 336 | /* Generate output. We generate 228 bits of |
| 337 | * keystream output. The first 114 bits is for |
| 338 | * the A->B frame; the next 114 bits is for the |
| 339 | * B->A frame. You allocate a 15-byte buffer |
| 340 | * for each direction, and this function fills |
| 341 | * it in. */ |
| 342 | void run(byte AtoBkeystream[], byte BtoAkeystream[]) { |
| 343 | int i; |
| 344 | |
| 345 | |
| 346 | /* Zero out the output buffers. */ |
| 347 | for (i = 0; i <= 113 / 8; i++) |
| 348 | AtoBkeystream[i] = BtoAkeystream[i] = 0; |
| 349 | |
| 350 | |
| 351 | /* Generate 114 bits of keystream for the |
| 352 | * A->B direction. Store it, MSB first. */ |
| 353 | for (i = 0; i < 114; i++) { |
| 354 | clock(0, 0); |
| 355 | AtoBkeystream[i/8] |= getbit() << (7 - (i & 7)); |
| 356 | } |
| 357 | |
| 358 | |
| 359 | /* Generate 114 bits of keystream for the |
| 360 | * B->A direction. Store it, MSB first. */ |
| 361 | for (i = 0; i < 114; i++) { |
| 362 | clock(0, 0); |
| 363 | BtoAkeystream[i/8] |= getbit() << (7 - (i & 7)); |
| 364 | } |
| 365 | } |
| 366 | |
ptrkrysik | a1871f5 | 2014-12-15 09:38:00 +0100 | [diff] [blame] | 367 | void runA51(byte AtoBkeystream[], byte BtoAkeystream[]) { |
ptrkrysik | 18b631e | 2014-12-15 09:09:18 +0100 | [diff] [blame] | 368 | int i; |
| 369 | |
| 370 | /* Zero out the output buffers. */ |
ptrkrysik | a1871f5 | 2014-12-15 09:38:00 +0100 | [diff] [blame] | 371 | for (i = 0; i < 114; i++){ |
ptrkrysik | 18b631e | 2014-12-15 09:09:18 +0100 | [diff] [blame] | 372 | AtoBkeystream[i] = 0; |
ptrkrysik | a1871f5 | 2014-12-15 09:38:00 +0100 | [diff] [blame] | 373 | } |
ptrkrysik | 18b631e | 2014-12-15 09:09:18 +0100 | [diff] [blame] | 374 | |
| 375 | /* Generate 114 bits of keystream for the |
| 376 | * A->B direction. Store it, MSB first. */ |
| 377 | for (i = 0; i < 114; i++) { |
| 378 | clock(0, 0); |
| 379 | AtoBkeystream[i] = getbit(); |
| 380 | } |
ptrkrysik | a1871f5 | 2014-12-15 09:38:00 +0100 | [diff] [blame] | 381 | |
| 382 | /* Generate 114 bits of keystream for the |
| 383 | * B->A direction. Store it, MSB first. */ |
| 384 | for (i = 0; i < 114; i++) { |
| 385 | clock(0, 0); |
| 386 | BtoAkeystream[i] = getbit(); |
| 387 | } |
ptrkrysik | 18b631e | 2014-12-15 09:09:18 +0100 | [diff] [blame] | 388 | } |
| 389 | |
| 390 | |
| 391 | |
| 392 | #endif /* A5_1_2_H */ |