/* proof of concept. does not generate table, only calculate and show one chain. example: ~/a5$ gcc -o generate generate.c ~/a5$ date; ./generate 1010101010101010101 1100110011001100110011 11100011100011100011100 23; date Wed Jan 14 08:50:59 CST 2009 Done in 4142022 steps. 0000000000000000000 0000110111010001100010 01000000001010000101101 Wed Jan 14 08:52:53 CST 2009 */ /* * A pedagogical implementation of A5/1. * * Copyright (C) 1998-1999: Marc Briceno, Ian Goldberg, and David Wagner * * The source code below is optimized for instructional value and clarity. * Performance will be terrible, but that's not the point. * The algorithm is written in the C programming language to avoid ambiguities * inherent to the English language. Complain to the 9th Circuit of Appeals * if you have a problem with that. * * This software may be export-controlled by US law. * * This software is free for commercial and non-commercial use as long as * the following conditions are aheared to. * Copyright remains the authors' and as such any Copyright notices in * the code are not to be removed. * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * The license and distribution terms for any publicly available version or * derivative of this code cannot be changed. i.e. this code cannot simply be * copied and put under another distribution license * [including the GNU Public License.] * * Background: The Global System for Mobile communications is the most widely * deployed cellular telephony system in the world. GSM makes use of * four core cryptographic algorithms, neither of which has been published by * the GSM MOU. This failure to subject the algorithms to public review is all * the more puzzling given that over 100 million GSM * subscribers are expected to rely on the claimed security of the system. * * The four core GSM algorithms are: * A3 authentication algorithm * A5/1 "strong" over-the-air voice-privacy algorithm * A5/2 "weak" over-the-air voice-privacy algorithm * A8 voice-privacy key generation algorithm * * In April of 1998, our group showed that COMP128, the algorithm used by the * overwhelming majority of GSM providers for both A3 and A8 * functionality was fatally flawed and allowed for cloning of GSM mobile * phones. * Furthermore, we demonstrated that all A8 implementations we could locate, * including the few that did not use COMP128 for key generation, had been * deliberately weakened by reducing the keyspace from 64 bits to 54 bits. * The remaining 10 bits are simply set to zero! * * See http://www.scard.org/gsm for additional information. * * The question so far unanswered is if A5/1, the "stronger" of the two * widely deployed voice-privacy algorithm is at least as strong as the * key. Meaning: "Does A5/1 have a work factor of at least 54 bits"? * Absent a publicly available A5/1 reference implementation, this question * could not be answered. We hope that our reference implementation below, * which has been verified against official A5/1 test vectors, will provide * the cryptographic community with the base on which to construct the * answer to this important question. * * Initial indications about the strength of A5/1 are not encouraging. * A variant of A5, while not A5/1 itself, has been estimated to have a * work factor of well below 54 bits. See http://jya.com/crack-a5.htm for * background information and references. * * With COMP128 broken and A5/1 published below, we will now turn our attention * to A5/2. The latter has been acknowledged by the GSM community to have * been specifically designed by intelligence agencies for lack of security. * * We hope to publish A5/2 later this year. * * -- Marc Briceno * Voice: +1 (925) 798-4042 * */ #include /* Masks for the three shift registers */ #define R1MASK 0x07FFFF /* 19 bits, numbered 0..18 */ #define R2MASK 0x3FFFFF /* 22 bits, numbered 0..21 */ #define R3MASK 0x7FFFFF /* 23 bits, numbered 0..22 */ /* Middle bit of each of the three shift registers, for clock control */ #define R1MID 0x000100 /* bit 8 */ #define R2MID 0x000400 /* bit 10 */ #define R3MID 0x000400 /* bit 10 */ /* Feedback taps, for clocking the shift registers. * These correspond to the primitive polynomials * x^19 + x^5 + x^2 + x + 1, x^22 + x + 1, * and x^23 + x^15 + x^2 + x + 1. */ #define R1TAPS 0x072000 /* bits 18,17,16,13 */ #define R2TAPS 0x300000 /* bits 21,20 */ #define R3TAPS 0x700080 /* bits 22,21,20,7 */ /* Output taps, for output generation */ #define R1OUT 0x040000 /* bit 18 (the high bit) */ #define R2OUT 0x200000 /* bit 21 (the high bit) */ #define R3OUT 0x400000 /* bit 22 (the high bit) */ /* #define R1MATCH 0x07ffff #define R2MATCH 0x3f0000 #define R3MATCH 0x000000 */ #define R1LENGTH 18 #define R2LENGTH 21 #define R3LENGTH 22 typedef unsigned char byte; typedef unsigned long word; typedef word bit; /* The three shift registers. They're in global variables to make the code * easier to understand. * A better implementation would not use global variables. */ word R1, R2, R3; /* Calculate the parity of a 32-bit word, i.e. the sum of its bits modulo 2 */ bit parity(word x) { x ^= x>>16; x ^= x>>8; x ^= x>>4; x ^= x>>2; x ^= x>>1; return x&1; } void printreg (void) { int i; word bit; printf(" "); bit = R1OUT; for (i = 0; i <= R1LENGTH; i++) { printf("%01x",parity(R1&bit)); bit /= 2; } printf(" "); bit = R2OUT; for (i = 0; i <= R2LENGTH; i++) { printf("%01x",parity(R2&bit)); bit /= 2; } printf(" "); bit = R3OUT; for (i = 0; i <= R3LENGTH; i++) { printf("%01x",parity(R3&bit)); bit /= 2; } printf("\n"); } /* Clock one shift register */ word clockone(word reg, word mask, word taps) { word t = reg & taps; reg = (reg << 1) & mask; reg |= parity(t); return reg; } /* Look at the middle bits of R1,R2,R3, take a vote, and * return the majority value of those 3 bits. */ bit majority() { int sum; sum = parity(R1&R1MID) + parity(R2&R2MID) + parity(R3&R3MID); if (sum >= 2) return 1; else return 0; } /* Clock two or three of R1,R2,R3, with clock control * according to their middle bits. * Specifically, we clock Ri whenever Ri's middle bit * agrees with the majority value of the three middle bits.*/ void clock() { bit maj = majority(); if (((R1&R1MID)!=0) == maj) R1 = clockone(R1, R1MASK, R1TAPS); if (((R2&R2MID)!=0) == maj) R2 = clockone(R2, R2MASK, R2TAPS); if (((R3&R3MID)!=0) == maj) R3 = clockone(R3, R3MASK, R3TAPS); } /* Clock all three of R1,R2,R3, ignoring their middle bits. * This is only used for key setup. */ void clockallthree() { R1 = clockone(R1, R1MASK, R1TAPS); R2 = clockone(R2, R2MASK, R2TAPS); R3 = clockone(R3, R3MASK, R3TAPS); } /* Generate an output bit from the current state. * You grab a bit from each register via the output generation taps; * then you XOR the resulting three bits. */ bit getbit() { return parity(R1&R1OUT)^parity(R2&R2OUT)^parity(R3&R3OUT); } word bin2hex (char *string) { int i; word res = 0; int length; length = strlen (string); for (i = 0; i < length; i++) { res = res << 1; if (string[0] == '1') res += 1; string++; } return res; } int main(int argv, char **argc) { int i,j,k; word in1, in2, in3, reg, tmp; word R1MATCH, R2MATCH, R3MATCH; int numofbits; int fm = 0; int debug = 0; word counter = 0; in1 = in2 = in3 = 0; if (argv < 5) { printf("usage: %s R1 R2 R3 bit_length [debug]\n",argc[0]); exit(0); } R1 = bin2hex(argc[1]); R2 = bin2hex(argc[2]); R3 = bin2hex(argc[3]); numofbits = atoi (argc[4]); if (argc[5] != 0 && argc[5][0] != 0) debug = 1; // Set mask (number of bits) for chain R1MATCH = R2MATCH = R3MATCH = 0; j = numofbits; tmp = 1 << R1LENGTH; for (i = 0; i < ((R1LENGTH+1)> 1; } j -= (R1LENGTH + 1); tmp = 1 << R2LENGTH; for (i = 0; i < ((R2LENGTH+1)> 1; } j -= (R2LENGTH +1); tmp = 1 << R3LENGTH; for (i = 0; i < ((R3LENGTH+1)> 1; } // generate single chain // while(1) { tmp = 1 << R1LENGTH; reg = 0; for (i = 0; i <= R1LENGTH; i ++) { if (getbit()) reg ^= tmp; tmp = tmp >> 1; clock(); if (debug) printf("%d ",i); if (debug) printreg (); } in1 = reg; tmp = 1 << R2LENGTH; reg = 0; for (i = 0; i <= R2LENGTH; i ++) { if (getbit()) reg ^= tmp; tmp = tmp >> 1; clock(); if (debug) printf("%d ",i); if (debug) printreg (); } in2 = reg; tmp = 1 << R3LENGTH; reg = 0; for (i = 0; i <= R3LENGTH; i ++) { if (getbit()) reg ^= tmp; tmp = tmp >> 1; clock(); if (debug) printf("%d ",i); if (debug) printreg (); } in3=reg; R1 = in1; R2 = in2; R3 = in3; counter ++; if (((R1&R1MATCH) | (R2&R2MATCH) | (R3&R3MATCH)) == 0) break; } // printf("Done in %d steps.\n",counter); printreg(); return 0; }