]> cvs.zerfleddert.de Git - proxmark3-svn/blob - client/loclass/elite_crack.c
27a2a1bc372b3b3fc55d46886ec2eaee2308bb1a
[proxmark3-svn] / client / loclass / elite_crack.c
1 #include <stdint.h>
2 #include <stdbool.h>
3 #include <string.h>
4 #include <stdio.h>
5 #include <time.h>
6 #include "cipherutils.h"
7 #include "cipher.h"
8 #include "ikeys.h"
9 #include "elite_crack.h"
10 #include "fileutils.h"
11 #include "des.h"
12
13 /**
14 * @brief Permutes a key from standard NIST format to Iclass specific format
15 * from http://www.proxmark.org/forum/viewtopic.php?pid=11220#p11220
16 *
17 * If you permute [6c 8d 44 f9 2a 2d 01 bf] you get [8a 0d b9 88 bb a7 90 ea] as shown below.
18 *
19 * 1 0 1 1 1 1 1 1 bf
20 * 0 0 0 0 0 0 0 1 01
21 * 0 0 1 0 1 1 0 1 2d
22 * 0 0 1 0 1 0 1 0 2a
23 * 1 1 1 1 1 0 0 1 f9
24 * 0 1 0 0 0 1 0 0 44
25 * 1 0 0 0 1 1 0 1 8d
26 * 0 1 1 0 1 1 0 0 6c
27 *
28 * 8 0 b 8 b a 9 e
29 * a d 9 8 b 7 0 a
30 *
31 * @param key
32 * @param dest
33 */
34 void permutekey(uint8_t key[8], uint8_t dest[8])
35 {
36
37 int i;
38 for(i = 0 ; i < 8 ; i++)
39 {
40 dest[i] = (((key[7] & (0x80 >> i)) >> (7-i)) << 7) |
41 (((key[6] & (0x80 >> i)) >> (7-i)) << 6) |
42 (((key[5] & (0x80 >> i)) >> (7-i)) << 5) |
43 (((key[4] & (0x80 >> i)) >> (7-i)) << 4) |
44 (((key[3] & (0x80 >> i)) >> (7-i)) << 3) |
45 (((key[2] & (0x80 >> i)) >> (7-i)) << 2) |
46 (((key[1] & (0x80 >> i)) >> (7-i)) << 1) |
47 (((key[0] & (0x80 >> i)) >> (7-i)) << 0);
48 }
49
50 return;
51 }
52 /**
53 * Permutes a key from iclass specific format to NIST format
54 * @brief permutekey_rev
55 * @param key
56 * @param dest
57 */
58 void permutekey_rev(uint8_t key[8], uint8_t dest[8])
59 {
60 int i;
61 for(i = 0 ; i < 8 ; i++)
62 {
63 dest[7-i] = (((key[0] & (0x80 >> i)) >> (7-i)) << 7) |
64 (((key[1] & (0x80 >> i)) >> (7-i)) << 6) |
65 (((key[2] & (0x80 >> i)) >> (7-i)) << 5) |
66 (((key[3] & (0x80 >> i)) >> (7-i)) << 4) |
67 (((key[4] & (0x80 >> i)) >> (7-i)) << 3) |
68 (((key[5] & (0x80 >> i)) >> (7-i)) << 2) |
69 (((key[6] & (0x80 >> i)) >> (7-i)) << 1) |
70 (((key[7] & (0x80 >> i)) >> (7-i)) << 0);
71 }
72 }
73
74 /**
75 * Helper function for hash1
76 * @brief rr
77 * @param val
78 * @return
79 */
80 uint8_t rr(uint8_t val)
81 {
82 return val >> 1 | (( val & 1) << 7);
83 }
84 /**
85 * Helper function for hash1
86 * @brief rl
87 * @param val
88 * @return
89 */
90 uint8_t rl(uint8_t val)
91 {
92 return val << 1 | (( val & 0x80) >> 7);
93 }
94 /**
95 * Helper function for hash1
96 * @brief swap
97 * @param val
98 * @return
99 */
100 uint8_t swap(uint8_t val)
101 {
102 return ((val >> 4) & 0xFF) | ((val &0xFF) << 4);
103 }
104
105 /**
106 * Hash1 takes CSN as input, and determines what bytes in the keytable will be used
107 * when constructing the K_sel.
108 * @param csn the CSN used
109 * @param k output
110 */
111 void hash1(uint8_t csn[] , uint8_t k[])
112 {
113 k[0] = csn[0]^csn[1]^csn[2]^csn[3]^csn[4]^csn[5]^csn[6]^csn[7];
114 k[1] = csn[0]+csn[1]+csn[2]+csn[3]+csn[4]+csn[5]+csn[6]+csn[7];
115 k[2] = rr(swap( csn[2]+k[1] ));
116 k[3] = rr(swap( csn[3]+k[0] ));
117 k[4] = ~rr(swap( csn[4]+k[2] ))+1;
118 k[5] = ~rr(swap( csn[5]+k[3] ))+1;
119 k[6] = rr( csn[6]+(k[4]^0x3c) );
120 k[7] = rl( csn[7]+(k[5]^0xc3) );
121 int i;
122 for(i = 7; i >=0; i--)
123 k[i] = k[i] & 0x7F;
124 }
125
126
127 /**
128 * @brief Reads data from the iclass-reader-attack dump file.
129 * @param dump, data from a iclass reader attack dump. The format of the dumpdata is expected to be as follows:
130 * <8 byte CSN><8 byte CC><4 byte NR><4 byte MAC><8 byte HASH1><1 byte NUM_BYTES_TO_RECOVER><3 bytes BYTES_TO_RECOVER>
131 * .. N times...
132 *
133 * So the first attack, with 3 bytes to recover would be : ... 03000145
134 * And a later attack, with 1 byte to recover (byte 0x5)would be : ...01050000
135 * And an attack, with 2 bytes to recover (byte 0x5 and byte 0x07 )would be : ...02050700
136 *
137 * @param cc_nr an array to store cc_nr into (12 bytes)
138 * @param csn an arracy ot store CSN into (8 bytes)
139 * @param received_mac an array to store MAC into (4 bytes)
140 * @param i the number to read. Should be less than 127, or something is wrong...
141 * @return
142 */
143 int _readFromDump(uint8_t dump[], dumpdata* item, uint8_t i)
144 {
145 size_t itemsize = sizeof(dumpdata);
146 //dumpdata item = {0};
147 memcpy(item,dump+i*itemsize, itemsize);
148 if(true)
149 {
150 printvar("csn", item->csn,8);
151 printvar("cc_nr", item->cc_nr,12);
152 printvar("mac", item->mac,4);
153 }
154 return 0;
155 }
156
157 static uint32_t startvalue = 0;
158 /**
159 * @brief Performs brute force attack against a dump-data item, containing csn, cc_nr and mac.
160 *This method calculates the hash1 for the CSN, and determines what bytes need to be bruteforced
161 *on the fly. If it finds that more than three bytes need to be bruteforced, it aborts.
162 *It updates the keytable with the findings, also using the upper half of the 16-bit ints
163 *to signal if the particular byte has been cracked or not.
164 *
165 * @param dump The dumpdata from iclass reader attack.
166 * @param keytable where to write found values.
167 * @return
168 */
169 int bruteforceItem(dumpdata item, uint16_t keytable[])
170 {
171 int errors = 0;
172 uint8_t key_sel_p[8] = { 0 };
173 uint8_t div_key[8] = {0};
174 int found = false;
175 uint8_t key_sel[8] = {0};
176 uint8_t calculated_MAC[4] = { 0 };
177
178 //Get the key index (hash1)
179 uint8_t key_index[8] = {0};
180 hash1(item.csn, key_index);
181
182
183 /*
184 * Determine which bytes to retrieve. A hash is typically
185 * 01010000454501
186 * We go through that hash, and in the corresponding keytable, we put markers
187 * on what state that particular index is:
188 * - CRACKED (this has already been cracked)
189 * - BEING_CRACKED (this is being bruteforced now)
190 * - CRACK_FAILED (self-explaining...)
191 *
192 * The markers are placed in the high area of the 16 bit key-table.
193 * Only the lower eight bits correspond to the (hopefully cracked) key-value.
194 **/
195 uint8_t bytes_to_recover[3] = {0};
196 uint8_t numbytes_to_recover = 0 ;
197 int i;
198 for(i =0 ; i < 8 ; i++)
199 {
200 if(keytable[key_index[i]] & (CRACKED | BEING_CRACKED)) continue;
201 bytes_to_recover[numbytes_to_recover++] = key_index[i];
202 keytable[key_index[i]] |= BEING_CRACKED;
203
204 if(numbytes_to_recover > 3)
205 {
206 prnlog("The CSN requires > 3 byte bruteforce, not supported");
207 printvar("CSN", item.csn,8);
208 printvar("HASH1", key_index,8);
209
210 //Before we exit, reset the 'BEING_CRACKED' to zero
211 keytable[bytes_to_recover[0]] &= ~BEING_CRACKED;
212 keytable[bytes_to_recover[1]] &= ~BEING_CRACKED;
213 keytable[bytes_to_recover[2]] &= ~BEING_CRACKED;
214
215 return 1;
216 }
217 }
218
219 /*
220 *A uint32 has room for 4 bytes, we'll only need 24 of those bits to bruteforce up to three bytes,
221 */
222 uint32_t brute = startvalue;
223 /*
224 Determine where to stop the bruteforce. A 1-byte attack stops after 256 tries,
225 (when brute reaches 0x100). And so on...
226 bytes_to_recover = 1 --> endmask = 0x0000100
227 bytes_to_recover = 2 --> endmask = 0x0010000
228 bytes_to_recover = 3 --> endmask = 0x1000000
229 */
230
231 uint32_t endmask = 1 << 8*numbytes_to_recover;
232
233 for(i =0 ; i < numbytes_to_recover && numbytes_to_recover > 1; i++)
234 prnlog("Bruteforcing byte %d", bytes_to_recover[i]);
235
236 while(!found && !(brute & endmask))
237 {
238
239 //Update the keytable with the brute-values
240 for(i =0 ; i < numbytes_to_recover; i++)
241 {
242 keytable[bytes_to_recover[i]] &= 0xFF00;
243 keytable[bytes_to_recover[i]] |= (brute >> (i*8) & 0xFF);
244 }
245
246 // Piece together the key
247 key_sel[0] = keytable[key_index[0]] & 0xFF;key_sel[1] = keytable[key_index[1]] & 0xFF;
248 key_sel[2] = keytable[key_index[2]] & 0xFF;key_sel[3] = keytable[key_index[3]] & 0xFF;
249 key_sel[4] = keytable[key_index[4]] & 0xFF;key_sel[5] = keytable[key_index[5]] & 0xFF;
250 key_sel[6] = keytable[key_index[6]] & 0xFF;key_sel[7] = keytable[key_index[7]] & 0xFF;
251
252 //Permute from iclass format to standard format
253 permutekey_rev(key_sel,key_sel_p);
254 //Diversify
255 diversifyKey(item.csn, key_sel_p, div_key);
256 //Calc mac
257 doMAC(item.cc_nr, div_key,calculated_MAC);
258
259 if(memcmp(calculated_MAC, item.mac, 4) == 0)
260 {
261 for(i =0 ; i < numbytes_to_recover; i++)
262 prnlog("=> %d: 0x%02x", bytes_to_recover[i],0xFF & keytable[bytes_to_recover[i]]);
263 found = true;
264 break;
265 }
266 brute++;
267 if((brute & 0xFFFF) == 0)
268 {
269 printf("%d",(brute >> 16) & 0xFF);
270 fflush(stdout);
271 }
272 }
273 if(! found)
274 {
275 prnlog("Failed to recover %d bytes using the following CSN",numbytes_to_recover);
276 printvar("CSN",item.csn,8);
277 errors++;
278 //Before we exit, reset the 'BEING_CRACKED' to zero
279 for(i =0 ; i < numbytes_to_recover; i++)
280 {
281 keytable[bytes_to_recover[i]] &= 0xFF;
282 keytable[bytes_to_recover[i]] |= CRACK_FAILED;
283 }
284
285 }else
286 {
287 for(i =0 ; i < numbytes_to_recover; i++)
288 {
289 keytable[bytes_to_recover[i]] &= 0xFF;
290 keytable[bytes_to_recover[i]] |= CRACKED;
291 }
292
293 }
294 return errors;
295 }
296
297
298 /**
299 * From dismantling iclass-paper:
300 * Assume that an adversary somehow learns the first 16 bytes of hash2(K_cus ), i.e., y [0] and z [0] .
301 * Then he can simply recover the master custom key K_cus by computing
302 * K_cus = ~DES(z[0] , y[0] ) .
303 *
304 * Furthermore, the adversary is able to verify that he has the correct K cus by
305 * checking whether z [0] = DES enc (K_cus , ~K_cus ).
306 * @param keytable an array (128 bytes) of hash2(kcus)
307 * @param master_key where to put the master key
308 * @return 0 for ok, 1 for failz
309 */
310 int calculateMasterKey(uint8_t first16bytes[], uint64_t master_key[] )
311 {
312 des_context ctx_e = {DES_ENCRYPT,{0}};
313
314 uint8_t z_0[8] = {0};
315 uint8_t y_0[8] = {0};
316 uint8_t z_0_rev[8] = {0};
317 uint8_t key64[8] = {0};
318 uint8_t key64_negated[8] = {0};
319 uint8_t result[8] = {0};
320
321 // y_0 and z_0 are the first 16 bytes of the keytable
322 memcpy(y_0,first16bytes,8);
323 memcpy(z_0,first16bytes+8,8);
324
325 // Our DES-implementation uses the standard NIST
326 // format for keys, thus must translate from iclass
327 // format to NIST-format
328 permutekey_rev(z_0, z_0_rev);
329
330 // ~K_cus = DESenc(z[0], y[0])
331 des_setkey_enc( &ctx_e, z_0_rev );
332 des_crypt_ecb(&ctx_e, y_0, key64_negated);
333
334 int i;
335 for(i = 0; i < 8 ; i++)
336 {
337 key64[i] = ~key64_negated[i];
338 }
339
340 // Can we verify that the key is correct?
341 // Once again, key is on iclass-format
342 uint8_t key64_stdformat[8] = {0};
343 permutekey_rev(key64, key64_stdformat);
344
345 des_setkey_enc( &ctx_e, key64_stdformat );
346 des_crypt_ecb(&ctx_e, key64_negated, result);
347 prnlog("\nHigh security custom key (Kcus):");
348 printvar("Std format ", key64_stdformat,8);
349 printvar("Iclass format", key64,8);
350
351 if(master_key != NULL)
352 memcpy(master_key, key64, 8);
353
354 if(memcmp(z_0,result,4) != 0)
355 {
356 prnlog("Failed to verify calculated master key (k_cus)! Something is wrong.");
357 return 1;
358 }else{
359 prnlog("Key verified ok!\n");
360 }
361 return 0;
362 }
363 /**
364 * @brief Same as bruteforcefile, but uses a an array of dumpdata instead
365 * @param dump
366 * @param dumpsize
367 * @param keytable
368 * @return
369 */
370 int bruteforceDump(uint8_t dump[], size_t dumpsize, uint16_t keytable[])
371 {
372 uint8_t i;
373 int errors = 0;
374 size_t itemsize = sizeof(dumpdata);
375 clock_t t1 = clock();
376
377 dumpdata* attack = (dumpdata* ) malloc(itemsize);
378
379 for(i = 0 ; i * itemsize < dumpsize ; i++ )
380 {
381 memcpy(attack,dump+i*itemsize, itemsize);
382 errors += bruteforceItem(*attack, keytable);
383 }
384 free(attack);
385 clock_t t2 = clock();
386 float diff = (((float)t2 - (float)t1) / CLOCKS_PER_SEC );
387 prnlog("\nPerformed full crack in %f seconds",diff);
388
389 // Pick out the first 16 bytes of the keytable.
390 // The keytable is now in 16-bit ints, where the upper 8 bits
391 // indicate crack-status. Those must be discarded for the
392 // master key calculation
393 uint8_t first16bytes[16] = {0};
394
395 for(i = 0 ; i < 16 ; i++)
396 {
397 first16bytes[i] = keytable[i] & 0xFF;
398 if(!(keytable[i] & CRACKED))
399 {
400 prnlog("Error, we are missing byte %d, custom key calculation will fail...", i);
401 }
402 }
403 errors += calculateMasterKey(first16bytes, NULL);
404 return errors;
405 }
406 /**
407 * Perform a bruteforce against a file which has been saved by pm3
408 *
409 * @brief bruteforceFile
410 * @param filename
411 * @return
412 */
413 int bruteforceFile(const char *filename, uint16_t keytable[])
414 {
415
416 FILE *f = fopen(filename, "rb");
417 if(!f) {
418 prnlog("Failed to read from file '%s'", filename);
419 return 1;
420 }
421
422 fseek(f, 0, SEEK_END);
423 long fsize = ftell(f);
424 fseek(f, 0, SEEK_SET);
425
426 uint8_t *dump = malloc(fsize);
427 size_t bytes_read = fread(dump, fsize, 1, f);
428
429 fclose(f);
430 if (bytes_read < fsize)
431 {
432 prnlog("Error, could only read %d bytes (should be %d)",bytes_read, fsize );
433 }
434 return bruteforceDump(dump,fsize,keytable);
435 }
436 /**
437 *
438 * @brief Same as above, if you don't care about the returned keytable (results only printed on screen)
439 * @param filename
440 * @return
441 */
442 int bruteforceFileNoKeys(const char *filename)
443 {
444 uint16_t keytable[128] = {0};
445 return bruteforceFile(filename, keytable);
446 }
447
448 // ---------------------------------------------------------------------------------
449 // ALL CODE BELOW THIS LINE IS PURELY TESTING
450 // ---------------------------------------------------------------------------------
451 // ----------------------------------------------------------------------------
452 // TEST CODE BELOW
453 // ----------------------------------------------------------------------------
454
455 int _testBruteforce()
456 {
457 int errors = 0;
458 if(true){
459 // First test
460 prnlog("[+] Testing crack from dumpfile...");
461
462 /**
463 Expected values for the dumpfile:
464 High Security Key Table
465
466 00 F1 35 59 A1 0D 5A 26 7F 18 60 0B 96 8A C0 25 C1
467 10 BF A1 3B B0 FF 85 28 75 F2 1F C6 8F 0E 74 8F 21
468 20 14 7A 55 16 C8 A9 7D B3 13 0C 5D C9 31 8D A9 B2
469 30 A3 56 83 0F 55 7E DE 45 71 21 D2 6D C1 57 1C 9C
470 40 78 2F 64 51 42 7B 64 30 FA 26 51 76 D3 E0 FB B6
471 50 31 9F BF 2F 7E 4F 94 B4 BD 4F 75 91 E3 1B EB 42
472 60 3F 88 6F B8 6C 2C 93 0D 69 2C D5 20 3C C1 61 95
473 70 43 08 A0 2F FE B3 26 D7 98 0B 34 7B 47 70 A0 AB
474
475 **** The 64-bit HS Custom Key Value = 5B7C62C491C11B39 ****
476 **/
477 uint16_t keytable[128] = {0};
478 //save some time...
479 startvalue = 0x7B0000;
480 errors |= bruteforceFile("iclass_dump.bin",keytable);
481 }
482 return errors;
483 }
484
485 int _test_iclass_key_permutation()
486 {
487 uint8_t testcase[8] = {0x6c,0x8d,0x44,0xf9,0x2a,0x2d,0x01,0xbf};
488 uint8_t testcase_output[8] = {0};
489 uint8_t testcase_output_correct[8] = {0x8a,0x0d,0xb9,0x88,0xbb,0xa7,0x90,0xea};
490 uint8_t testcase_output_rev[8] = {0};
491 permutekey(testcase, testcase_output);
492 permutekey_rev(testcase_output, testcase_output_rev);
493
494
495 if(memcmp(testcase_output, testcase_output_correct,8) != 0)
496 {
497 prnlog("Error with iclass key permute!");
498 printarr("testcase_output", testcase_output, 8);
499 printarr("testcase_output_correct", testcase_output_correct, 8);
500 return 1;
501
502 }
503 if(memcmp(testcase, testcase_output_rev, 8) != 0)
504 {
505 prnlog("Error with reverse iclass key permute");
506 printarr("testcase", testcase, 8);
507 printarr("testcase_output_rev", testcase_output_rev, 8);
508 return 1;
509 }
510
511 prnlog("[+] Iclass key permutation OK!");
512 return 0;
513 }
514
515 int testElite()
516 {
517 prnlog("[+] Testing iClass Elite functinality...");
518 prnlog("[+] Testing key diversification ...");
519
520 int errors = 0 ;
521 errors +=_test_iclass_key_permutation();
522 errors += _testBruteforce();
523 return errors;
524
525 }
526
Impressum, Datenschutz