summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--A5.1/C/calculate_chain.c181
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;
}
personal git repositories of Harald Welte. Your mileage may vary