/
incskip.c
311 lines (260 loc) · 10.7 KB
/
incskip.c
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
// Test code to demonstrate traversal of the incremental search space in John the Ripper.
//
// Author: taviso@...xchg8b.com, Jun 2012.
// Modified by cc@nycheads.com
struct header {
uint32_t version;
uint32_t check[6];
uint8_t min;
uint8_t max;
uint8_t length;
uint8_t count;
uint32_t offsets[8];
struct {
uint8_t length;
uint8_t fixed;
uint8_t count;
} order[3420];
} __attribute__((packed));
static const uint32_t kMinLength = 1;
static const uint32_t kMaxLength = 8;
static const uint32_t kCharsetLen = 95;
static const uint32_t kTotalShards = 1 << 21;
// static const uint64_t kTotalKeySpace = pow(kCharsetLen, kMaxLength);
// $ bc <<< 'obase=16;95^8'
// 1791C60F6FED01
static const uint64_t kTotalKeySpace = 0x1791C60F6FED01ULL;
// $ bc <<< 'obase=16;(95^8)/(2^21)'
// BC8E307B
static const uint64_t kWorkUnit = 0xBC8E307BULL;
// Convert an array of numdigits integers of a specified base into an integer.
static uint64_t convert_from_base(uint8_t *digits,
uint8_t numdigits,
uint8_t base)
{
uint64_t result;
uint32_t i;
for (result = i = 0; numdigits--; i++) {
result += digits[numdigits] * pow(base, i);
}
return result;
}
// Convert an integer into an array of digits.
static bool convert_to_base(uint8_t *digits,
uint8_t numdigits,
uint8_t base,
uint64_t value)
{
int32_t i;
// Not possible to represent numbers in an unsigned integer base less than
// one, return failure.
if (base == 0) return false;
// Distribute value digits appropriately.
for (i = numdigits - 1; i >= 0; i--) {
digits[i] = value % base;
value = value / base;
}
return true;
}
// Given a { length, fixed, count } triplet, calculate the maximum amount of
// work expected in inc_key_loop().
static uint64_t calculate_maximum_attempts(uint32_t length,
uint32_t fixed,
uint32_t count)
{
uint64_t result;
uint32_t pos;
// A table of coefficients required to compensate for fixed characters in
// JtR character files.
static const int64_t kOrderCoefficients[][8] = {
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, -1, 0, 0, 0, 0, 0, 0 },
{ 0, -2, 1, 0, 0, 0, 0, 0 },
{ 0, -3, 3, -1, 0, 0, 0, 0 },
{ 0, -4, 6, -4, 1, 0, 0, 0 },
{ 0, -5, 10, -10, 5, -1, 0, 0 },
{ 0, -6, 15, -20, 15, -6, 1, 0 },
{ 0, -7, 21, -35, 35, -21, 7, -1 },
};
// Calculate base complexity of this rule.
result = pow(count + 1, length);
// Compensate for fixed characters.
for (pos = 0; pos < kMaxLength; pos++) {
result += kOrderCoefficients[fixed][pos] * pow(count + 1, length - pos);
}
return result;
}
// Given a { length, fixed, count } triplet, calculate the internal state of
// inc_key_loop() after the specified number of crypt operations.
//
// Note that the state produced may be a few crypts early due to the
// number_cache behaviour. This is unavoidable, john does the same thing with
// REC files internally.
static bool calculate_number_state(uint8_t *numbers,
uint32_t length,
uint32_t fixed,
uint32_t count,
uint64_t crypts)
{
// Compensate for the number_cache in inc_key_loop() skipping certain
// increments of numbers[].
if (fixed != length)
crypts = crypts - (crypts % (count + 1));
// Convert number of crypts into a k-digit base-n representation
// of crypts. This closely matches how John stores it's internal state,
// with the exception of fixed digits.
convert_to_base(numbers, kMaxLength, count + 1, crypts);
// Move the digits above the fixed digit down one position, because the
// fixed digit will displace them. This is the same as partial
// multiplication of these digits by base, but moving them is more
// efficient than having to convert them to integers.
memmove(&numbers[0], &numbers[1], fixed);
// Now we can force the fixed digit into the correct position.
numbers[fixed] = count;
// Finally, we need to adjust the digits above the fixed position
// independently. This is because John will never set a digit in those
// positions to count, however other arithmetic rules still apply.
//
// We can interpret this algorithm behaviour as setting these digits to one
// base lower than the rest of the digits. Yes, this is confusing.
convert_to_base(numbers,
fixed,
count,
convert_from_base(numbers, fixed, count + 1));
// Complete.
return true;
}
// A simplified version of the inc_key_loop() algorithm from John the Ripper
// used for verifying prediction results.
static uint64_t inc_key_loop(uint8_t *numbers,
uint32_t length,
uint32_t fixed,
uint32_t count)
{
int32_t numbers_cache;
int32_t pos = 0;
uint64_t crypts = 0;
numbers[fixed] = count;
update_ending:
numbers_cache = numbers[length];
update_last:
// A crypt() operation would happen here.
crypts++;
pos = length;
if (fixed < length) {
if (++numbers_cache <= count) {
if (length >= 2) goto update_last;
numbers[length] = numbers_cache;
goto update_ending;
}
numbers[pos--] = 0;
while (pos > fixed) {
if (++numbers[pos] <= count) goto update_ending;
numbers[pos--] = 0;
}
}
while (pos-- > 0) {
if (++numbers[pos] < count) goto update_ending;
numbers[pos] = 0;
}
return crypts;
}
int main(int argc, char **argv)
{
struct header header; // Header of CHR file.
uint64_t crypts; // Total number of crypt() operations expected.
uint64_t dunn; // crypt()s accounted for
uint64_t myunit = 21600000000ULL; // units of crypt() for work
uint64_t estimated; // Estimated number of crypts() required to complete this order entry.
uint32_t entry; // Current order index (a table stored in the CHR files).
uint64_t result;
uint32_t i;
// There are two important components of JtR internal state for incremental
// cracking. First, the entry number (essentially an index into the order
// table of the CHR files). Second is the numbers array, for which the bulk
// of the algorithm is in inc_key_loop() in John's inc.c.
uint8_t john_numbers_state[kMaxLength];
// Read in CHR file from stdin.
fread(&header, sizeof header, 1, stdin);
fprintf(stderr, "Version: %08X\n", header.version);
fprintf(stderr, "Check: %08X\n", header.check[0]);
fprintf(stderr, "Min: %u\n", header.min);
fprintf(stderr, "Max: %u\n", header.max);
fprintf(stderr, "Length: %u\n", header.length);
fprintf(stderr, "Count: %u\n", header.count);
fprintf(stderr, "Offsets (ignored):\n");
fprintf(stderr, "\t%08X %08X %08X %08X %08X\n\t...\n",
header.offsets[0],
header.offsets[1],
header.offsets[2],
header.offsets[3],
header.offsets[4]);
for (entry = 0, crypts = 0, dunn = myunit;
entry < (sizeof header.order / sizeof header.order[0]);
entry++) {
// This logic duplicated from do_incremental_crack()
if (header.order[entry].fixed && !header.order[entry].count)
continue;
if (header.order[entry].length + 1 < kMinLength)
continue;
if (header.order[entry].length >= kMaxLength)
continue;
if (header.order[entry].count >= kCharsetLen)
continue;
// Calculate worst case requirements for crypt() operations this entry
// requires. We still need to adjust for 'Fixed' characters, which is
// done with the table below.
estimated = calculate_maximum_attempts(header.order[entry].length,
header.order[entry].fixed,
header.order[entry].count);
fprintf(stderr, "\tentry %u { %u, %u, %u }, 0 0 0 0 0 0 0 0 @all crypt()\n",
entry,
header.order[entry].length,
header.order[entry].fixed,
header.order[entry].count);
// Not the most efficient, we are going to make different entries
// go to different work units. This means we'll have at least 3000
// work units (one per entry) and the early ones will be really
// short - but estimated seems off for tiny entries.
crypts = 0;
while (estimated) {
if (estimated < myunit )
break;
estimated -= myunit;
crypts += myunit;
// Find the state after num crypt operations, so we can skip to an
// arbitrary position.
if (calculate_number_state(john_numbers_state,
header.order[entry].length,
header.order[entry].fixed,
header.order[entry].count,
crypts) == false) {
fprintf(stderr, "error: calculate_number_state() returned failure\n");
return 1;
}
fprintf(stderr, "\tentry %u { %u, %u, %u }, %u %u %u %u %u %u %u %u @%llu crypt()\n",
entry,
header.order[entry].length,
header.order[entry].fixed,
header.order[entry].count,
john_numbers_state[0], john_numbers_state[1],
john_numbers_state[2], john_numbers_state[3],
john_numbers_state[4], john_numbers_state[5],
john_numbers_state[6], john_numbers_state[7],
crypts);
// result = inc_key_loop(john_numbers_state,
// header.order[entry].length,
// header.order[entry].fixed,
// header.order[entry].count);
// fprintf(stderr, "crypts executed %llu\n", result);
}
}
return 0;
}