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", ¤t) == 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", ¤t) == 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;
}
|
