summaryrefslogtreecommitdiff
path: root/A5.1/C/calculate_chain.c
blob: 28aec0fe59b327add25c9a42ae94f6192d13c1f8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
 * Calculation of chains for A5/1 rainbow table cracking.
 *
 *
 * Loosely based on: A pedagogical implementation of A5/1.
 *
 * Copyright (C) 1998-1999: Marc Briceno, Ian Goldberg, and David Wagner
 *
 * See accompanying file A5.1.c for original version and full copyright
 */


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <math.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. */
#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) */

typedef unsigned char byte;
#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;

bit parity32(uint32 x) {
	x ^= x>>16;
	x ^= x>>8;
	x ^= x>>4;
	x ^= x>>2;
	x ^= x>>1;
	return x&1;
}

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 |= parity32(t);
	return reg;
}

uint32 R1, R2, R3;

inline bit majority() {
	int sum;
	sum = ((R1&R1MID) >> 8) + ((R2&R2MID) >> 10) + ((R3&R3MID) >> 10);
	if (sum >= 2)
		return 1;
	else
		return 0;
}

inline 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);
}

inline bit getbit() {
  return ((R1&R1OUT) >> 18) ^ ((R2&R2OUT) >> 21) ^ ((R3&R3OUT) >> 22);
}

inline uint64 calculate_link (uint64 input, uint32 count) {
  uint64 result;
  int i;

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

/* Linear congruential generator used to whiten start value.
 * Numbers stolen from Lawrence Livermore National Laboratory RNG
 * library: http://nuclear.llnl.gov/CNP/rng/rngman/node4.html 
 */
uint64 start_value_from_index (uint64 count) {
  return 2862933555777941757UL * (count + 1) + 3037000493L;
}

void usage (char* argv[]) {
  printf("Usage: %s <startvalue>\n\nSpecify the start value as 16 hex digits, or chain number as 10 hex digits. Calculates one\nchain of the A5/1 rainbow table, and outputs the end value.\n", argv[0]);
  exit(1);
}

int main(int argc, char* argv[]) {
  int i,j;
  uint64 current;

  if (argc<2) {
    usage(argv);
  } else if (strlen(argv[1])==16 && sscanf(argv[1], "%16lx", &current) == 1) {
    printf("Calculating chain from start value 0x%16.16lx\n", current);
    current = calculate_chain(current, pow(2, 21));
  } else if (sscanf(argv[1], "%16lx", &current) == 1) {
    current = start_value_from_index(current);
    printf("Calculating chain from start value 0x%16.16lx\n", current);
    current = calculate_chain(current, pow(2, 21));
  } else {
    usage(argv);
  }
  printf("End value: 0x%16.16lx\n", current);
  return 0;
}
personal git repositories of Harald Welte. Your mileage may vary