diff options
| -rw-r--r-- | A5.1/C/generate.c | 371 |
1 files changed, 371 insertions, 0 deletions
diff --git a/A5.1/C/generate.c b/A5.1/C/generate.c new file mode 100644 index 0000000..55bcfbb --- /dev/null +++ b/A5.1/C/generate.c @@ -0,0 +1,371 @@ +/* +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 <marc@scard.org> + * Voice: +1 (925) 798-4042 + * + */ + +#include <stdio.h> + +/* 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)<j?(R1LENGTH+1):j); i++) + { + R1MATCH ^= tmp; + tmp = tmp >> 1; + } + j -= (R1LENGTH + 1); + tmp = 1 << R2LENGTH; + for (i = 0; i < ((R2LENGTH+1)<j?(R2LENGTH+1):j); i++) + { + R2MATCH ^= tmp; + tmp = tmp >> 1; + } + j -= (R2LENGTH +1); + tmp = 1 << R3LENGTH; + for (i = 0; i < ((R3LENGTH+1)<j?(R3LENGTH+1):j); i++) + { + R3MATCH ^= tmp; + tmp = tmp >> 1; + } + +// generate single chain +// <generate> + 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; + + } +// </generate> + + printf("Done in %d steps.\n",counter); + printreg(); + + return 0; +} + |