summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndreas Bogk <andreas@pt141.(none)>2009-01-16 13:14:34 +0100
committerAndreas Bogk <andreas@pt141.(none)>2009-01-16 13:14:34 +0100
commitd37c094f023f46ee405f1b23bdca5928e4bb5606 (patch)
tree9bda05db34b4fc01796810438ea2d6effd2c45c6
parent02f25aeade71a9addc06e8f9678742e04d25fd59 (diff)
Simple chain generation.
-rw-r--r--A5.1/C/generate.c371
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;
+}
+
personal git repositories of Harald Welte. Your mileage may vary