Leaked comp128 algorithm (version 2 and 3) and a refactored, easier to understand, version.

comp128.c

/** Comp128 version 2 and 3 overview by Mathy Vanhoef (based on other contributions mentioned inline) */
#include <string.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>


static uint8_t table0[] = {
	197, 235,  60, 151,  98,  96,   3, 100, 248, 118,  42, 117, 172, 211, 181, 203,
	 61, 126, 156,  87, 149, 224,  55, 132, 186,  63, 238, 255,  85,  83, 152,  33,
	160, 184, 210, 219, 159,  11, 180, 194, 130, 212, 147,   5, 215,  92,  27,  46,
	113, 187,  52,  25, 185,  79, 221,  48,  70,  31, 101,  15, 195, 201,  50, 222,
	137, 233, 229, 106, 122, 183, 178, 177, 144, 207, 234, 182,  37, 254, 227, 231,
	 54, 209, 133,  65, 202,  69, 237, 220, 189, 146, 120,  68,  21, 125,  38,  30,
	  2, 155,  53, 196, 174, 176,  51, 246, 167,  76, 110,  20,  82, 121, 103, 112,
	 56, 173,  49, 217, 252,   0, 114, 228, 123,  12,  93, 161, 253, 232, 240, 175,
	 67, 128,  22, 158,  89,  18,  77, 109, 190,  17,  62,   4, 153, 163,  59, 145,
	138,   7,  74, 205,  10, 162,  80,  45, 104, 111, 150, 214, 154,  28, 191, 169,
	213,  88, 193, 198, 200, 245,  39, 164, 124,  84,  78,   1, 188, 170,  23,  86,
	226, 141,  32,   6, 131, 127, 199,  40, 135,  16,  57,  71,  91, 225, 168, 242,
	206,  97, 166,  44,  14,  90, 236, 239, 230, 244, 223, 108, 102, 119, 148, 251,
	 29, 216,   8,   9, 249, 208,  24, 105,  94,  34,  64,  95, 115,  72, 134, 204,
	 43, 247, 243, 218,  47,  58,  73, 107, 241, 179, 116,  66,  36, 143,  81, 250,
	139,  19,  13, 142, 140, 129, 192,  99, 171, 157, 136,  41,  75,  35, 165,  26};

static uint8_t table1[] = {
	170,  42,  95, 141, 109,  30,  71,  89,  26, 147, 231, 205, 239, 212, 124, 129,
	216,  79,  15, 185, 153,  14, 251, 162,   0, 241, 172, 197,  43,  10, 194, 235,
	  6,  20,  72,  45, 143, 104, 161, 119,  41, 136,  38, 189, 135,  25,  93,  18,
	224, 171, 252, 195,  63,  19,  58, 165,  23,  55, 133, 254, 214, 144, 220, 178,
	156,  52, 110, 225,  97, 183, 140,  39,  53,  88, 219, 167,  16, 198,  62, 222,
	 76, 139, 175,  94,  51, 134, 115,  22,  67,   1, 249, 217,   3,   5, 232, 138,
	 31,  56, 116, 163,  70, 128, 234, 132, 229, 184, 244,  13,  34,  73, 233, 154,
	179, 131, 215, 236, 142, 223,  27,  57, 246, 108, 211,   8, 253,  85,  66, 245,
	193,  78, 190,   4,  17,   7, 150, 127, 152, 213,  37, 186,   2, 243,  46, 169,
	 68, 101,  60, 174, 208, 158, 176,  69, 238, 191,  90,  83, 166, 125,  77,  59,
	 21,  92,  49, 151, 168,  99,   9,  50, 146, 113, 117, 228,  65, 230,  40,  82,
	 54, 237, 227, 102,  28,  36, 107,  24,  44, 126, 206, 201,  61, 114, 164, 207,
	181,  29,  91,  64, 221, 255,  48, 155, 192, 111, 180, 210, 182, 247, 203, 148,
	209,  98, 173,  11,  75, 123, 250, 118,  32,  47, 240, 202,  74, 177, 100,  80,
	196,  33, 248,  86, 157, 137, 120, 130,  84, 204, 122,  81, 242, 188, 200, 149,
	226, 218, 160, 187, 106,  35,  87, 105,  96, 145, 199, 159,  12, 121, 103, 112};


/**
 * =============================================================================
 *    Refactored algorithm (by bla from io.smashthestack.org with minor edits)
 * =============================================================================
 */

void do_round(uint8_t state[32])
{
	uint8_t temp[32];
	uint8_t round[32];
	uint8_t i, j, z, bit;

	memcpy(round, state, 32);
	for (i = 0; i < 5; ++i)
	{
		for(j = 0; j < 16; ++j) {
			temp[     j] = table0[table1[round[16 + j]] ^ round[     j]];
			temp[16 + j] = table0[table1[ temp[     j]] ^ round[16 + j]];
		}

		for(j = 0; j < 16; ++j) {
			z = j + (j & (0xf << i));
			round[z] = temp[j];
			round[31 - z] = temp[31 - j];
		}
	}

	for (i = bit = 0; i < 128; ++i) {
		bit += 19;
		state[i >> 3] >>= 1;
		state[i >> 3] |= (round[bit >> 3] >> (bit & 7)) << 7;
	}
}


/**
 * @param output	Output of the algorithm
 * @param ki		Key
 * @param nonce		Challenge nonce sent by the base station
 */
void comp128(uint8_t output[16], const uint8_t ki[16], const uint8_t nonce[16])
{
	uint8_t state[32];
	int i;

	/** state = NONCE || XOR(ki, NONCE) */
	for (i = 0; i < 16; i++) {
		state[15 - i] = nonce[i];
		state[31 - i] = ki[ i] ^ nonce[i];
	}

	/** Main algorithm: perform 8 rounds, where each round updates only state[:16]. */
	for (i = 0; i < 8; i++)
		do_round(state);

	for (i = 0; i < 16; ++i)
		output[i] = state[15 - i];
}



/**
 * =============================================================================
 *    Original leaked version of the algorithm ( http://hackingprojects.net )
 *    Taken from http://git.osmocom.org/libosmocore/tree/src/gsm/comp128v23.c
 * =============================================================================
 */

#define RAND_SIZE 16
#define KI_SIZE   16

static void _comp128v23_internal(uint8_t *output, const uint8_t *kxor, const uint8_t *rand)
{
	uint8_t temp[RAND_SIZE];
	uint8_t km_rm[RAND_SIZE+KI_SIZE];
	uint8_t i,j,k,z;

	memset(temp,0,sizeof(temp)/sizeof(uint8_t));
	memcpy(km_rm,rand,RAND_SIZE);
	memcpy(km_rm+RAND_SIZE,kxor,KI_SIZE);

	for (i=0; i<5; i++) {
		for (z=0; z<16; z++) {
			temp[z] = table0[table1[km_rm[16+z]]^km_rm[z]];
		}
		j=0;
		while ((1<<i)>j) {
			k = 0;
			while ((1<<(4-i))>k) {
				km_rm[((2*k+1)<<i)+j] = table0[table1[temp[(k<<i)+j]]^(km_rm[(k<<i)+16+j])];
				km_rm[(k<<(i+1))+j] = temp[(k<<i)+j];
				k++;
			}
			j++;
		}
	}

	memset(output,0,16);

	for (i=0; i<16; i++) {
		for (j=0; j<8; j++) {
			output[i] ^= (((km_rm[(19*(j+8*i)+19)%256/8]>>(3*j+3)%8)&1)<< j);
		}
	}
}

int comp128v23_asleaked(const uint8_t *ki, const uint8_t *rand, uint8_t version, uint8_t output[16])
{
	uint8_t k_mix[KI_SIZE];
	uint8_t rand_mix[RAND_SIZE];
	uint8_t katyvasz[KI_SIZE];
	uint8_t i;

	if (!(version==2 || version==3))
		return 1;

	memset(k_mix,0,sizeof(k_mix)/sizeof(uint8_t));
	memset(rand_mix,0,sizeof(rand_mix)/sizeof(uint8_t));
	memset(katyvasz,0,sizeof(katyvasz)/sizeof(uint8_t));
	memset(output,0,16);

	for (i=0; i<8; i++) {
		k_mix[i] = ki[15 - i];
		k_mix[15 - i] = ki[i];
	}

	for (i=0; i<8; i++) {
		rand_mix[i] = rand[15 - i];
		rand_mix[15 - i] = rand[i];
	}

	for (i=0; i<16; i++) {
		katyvasz[i] = k_mix[i]^rand_mix[i];
	}

	for (i=0; i<8; i++) {
		_comp128v23_internal(rand_mix,katyvasz,rand_mix);
	}

	for (i=0; i<16; i++) {
		output[i] = rand_mix[15-i];
	}

	if (version==2) {
		output[15] = 0;
		output[14] = 4*(output[14]>>2);
	}

	// For testing refactored algorithm we *don't* drop the bytes in the middle
#if 0
	uint8_t s = 8;
	i = 0;
	while (i<4) {
		output[s+i-4] = output[s+i];
		output[s+i] = output[s+i+4];
		i++;
	}
#endif

	return 0;
}


/**
 * =============================================================================
 *               Assure leaked and Refactored algorithm are the same
 * =============================================================================
 */

int main(int argc, char *argv[])
{
	uint8_t key[16] = {0},
		nonce  [16] = {0},
		output1[16] = {0},
		output2[16] = {0};
	int i, j;

	srand(time(NULL));

	// Compare output of several nonces (nonce is challenge sent by base station)
	for (i = 0; i < 10; ++i)
	{
		// Set some random key and nonce
		for (j = 0; j < 16; ++j) {
			key[j] = rand();
			nonce[j] = rand();
		}
			
		comp128(output1, key, nonce);
		comp128v23_asleaked(key, nonce, 3, output2);

		if (memcmp(output1, output2, 16) != 0) {
			printf("Error: output of refactored algorithm differs from leaked\n");
			return 1;
		}

		// From the output we extract srand (authentication response) and kc (encryption key for A5/1, A5/2, A5/3, ...).
		// Note that not all bytes of the output are used to construct srand and kc.
		printf("srand = %02X%02X%02X%02X | kc = %02X%02X%02X%02X%02X%02X%02X%02X\n",
			output1[0], output1[1], output1[2], output1[3], // srand
			output1[8], output1[9], output1[10], output1[11], output1[12], output1[13], output1[14], output1[15]); // Kc
	}

	return 0;
}