Skip to content

Instantly share code, notes, and snippets.

@vanhoefm
Created February 5, 2016 23:30
Show Gist options
  • Save vanhoefm/39347363856b46087ce8 to your computer and use it in GitHub Desktop.
Save vanhoefm/39347363856b46087ce8 to your computer and use it in GitHub Desktop.
Leaked comp128 algorithm (version 2 and 3) and a refactored, easier to understand, version.
/** 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment