path: root/A5.1/C/generate.c

/*
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;
}