Make chain calculation more robust.

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", &current);
+  uint64 current;
 
-  for(i=pow(2,21);i>0;i--) {
-    current = calculate_link(current, i);
+  if (argc<2 || sscanf(argv[1], "%16lx", &current) != 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;
 }