diff options
| -rw-r--r-- | A5.1/C/calculate_chain.c | 181 |
1 files changed, 53 insertions, 128 deletions
diff --git a/A5.1/C/calculate_chain.c b/A5.1/C/calculate_chain.c index a7d3266..5b6d18e 100644 --- a/A5.1/C/calculate_chain.c +++ b/A5.1/C/calculate_chain.c @@ -1,94 +1,12 @@ /* - * A pedagogical implementation of A5/1. + * Calculation of chains for A5/1 rainbow table cracking. * - * 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! + * Loosely based on: A pedagogical implementation of A5/1. * - * 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 + * Copyright (C) 1998-1999: Marc Briceno, Ian Goldberg, and David Wagner * + * See accompanying file A5.1.c for original version and full copyright */ @@ -108,10 +26,7 @@ #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. */ +/* Feedback taps, for clocking the shift registers. */ #define R1TAPS 0x072000 /* bits 18,17,16,13 */ #define R2TAPS 0x300000 /* bits 21,20 */ #define R3TAPS 0x700080 /* bits 22,21,20,7 */ @@ -122,12 +37,17 @@ #define R3OUT 0x400000 /* bit 22 (the high bit) */ typedef unsigned char byte; -typedef unsigned long word; -typedef word bit; +#ifdef BITSIZE_32 +typedef unsigned long uint32; +typedef unsigned long long uint64; +#else +typedef unsigned int uint32; +typedef unsigned long uint64; +#endif + +typedef unsigned int bit; -/* Calculate the parity of a 32-bit word, i.e. the sum of its bits modulo 2 */ -bit parity(word x) { - // x ^= x>>32; +bit parity32(uint32 x) { x ^= x>>16; x ^= x>>8; x ^= x>>4; @@ -136,22 +56,26 @@ bit parity(word x) { return x&1; } -/* Clock one shift register */ -word clockone(word reg, word mask, word taps) { - word t = reg & taps; +bit parity64(uint64 x) { + x ^= x>>32; + x ^= x>>16; + x ^= x>>8; + x ^= x>>4; + x ^= x>>2; + x ^= x>>1; + return x&1; +} + +uint32 clockone(uint32 reg, uint32 mask, uint32 taps) { + uint32 t = reg & taps; reg = (reg << 1) & mask; - reg |= parity(t); + reg |= parity32(t); return reg; } -/* 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; +uint32 R1, R2, R3; -/* Look at the middle bits of R1,R2,R3, take a vote, and - * return the majority value of those 3 bits. */ -bit majority() { +inline bit majority() { int sum; sum = ((R1&R1MID) >> 8) + ((R2&R2MID) >> 10) + ((R3&R3MID) >> 10); if (sum >= 2) @@ -160,10 +84,6 @@ bit majority() { 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.*/ inline void clock() { bit maj = majority(); if (((R1&R1MID)!=0) == maj) @@ -174,43 +94,48 @@ inline void clock() { 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); +inline bit getbit() { return ((R1&R1OUT) >> 18) ^ ((R2&R2OUT) >> 21) ^ ((R3&R3OUT) >> 22); } -inline word calculate_link (word input, word count) { - word result; +inline uint64 calculate_link (uint64 input, uint32 count) { + uint64 result; int i; - input ^= count ^ (count << 23) ^ (count << (22 + 23)); - - R1 = (input >> (22 + 23)) & R1MASK; - R2 = (input >> 23) & R2MASK; - R3 = input & R3MASK; + /* Reduction function. */ + R1 = ((input >> (22 + 23))^count) & R1MASK; + R2 = ((input >> 23)^count) & R2MASK; + R3 = (input^count) & R3MASK; result = getbit(); for(i=1;i<64;i++) { + // Yes, virginia, we only need to clock 63 times for 64 bits of output clock(); result = (result << 1)| getbit(); } return result; } - + +uint64 calculate_chain (uint64 input, uint32 count) { + int i; + + for(i=count-1; i>=0; i--) { + input = calculate_link(input, i); + } + return input; +} int main(int argc, char* argv[]) { int i,j; - word current; - - sscanf(argv[1], "%16lx", ¤t); + uint64 current; - for(i=pow(2,21);i>0;i--) { - current = calculate_link(current, i); + if (argc<2 || sscanf(argv[1], "%16lx", ¤t) != 1) { + printf("Usage: %s <startvalue>\n\nSpecify the start value as 16 hex digits. Calculates one\nchain of the A5/1 rainbow table, and outputs the end value.\n", argv[0]); + exit(1); } + current = calculate_chain(current, pow(2, 21)); + printf("%16.16lx\n", current); return 0; } |