tools/mfc/card_only/staticnested_0nt.c

   1 // Reused Keys Nested Attack
   2 //
   3 // Attack conditions:
   4 // * Know a first key, to be able to activate the nested authentication protocol
   5 // * The card must reuse some keys across several sectors. Or several cards of an infrastructure share the same key
   6 //
   7 // Strategy:
   8 // * Find all possible key candidates for one reference sector, and check on-the-fly if they are compatible with any other sector we want to compare with
   9 //
  10 //  Doegox, 2024, cf https://eprint.iacr.org/2024/1275 for more info
  11
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <string.h>
  15 #include <inttypes.h>
  16 #include <pthread.h>
  17 #include "common.h"
  18 #include "crapto1/crapto1.h"
  19 #include "parity.h"
  20
  21 // max number of concurrent threads
  22 #define NUM_THREADS 20
  23 #define CHUNK_DIVISOR 10
  24
  25 // oversized just in case...
  26 #define KEY_SPACE_SIZE ((1 << 16) * 4)
  27 // we expect intersection to be about 250-500 keys. Oversized just in case...
  28 #define KEY_SPACE_SIZE_STEP2 2000
  29 #define MAX_NR_NONCES 32
  30
  31 typedef struct {
  32     uint32_t ntp;
  33     uint32_t ks1;
  34 } NtpKs1;
  35
  36 typedef struct {
  37     uint32_t authuid;
  38     NtpKs1 *pNK;
  39     uint32_t sizeNK;
  40     uint32_t nt_enc;
  41     uint8_t nt_par_enc;
  42 } NtData;
  43
  44 typedef struct {
  45     NtData NtDataList[MAX_NR_NONCES];
  46     uint32_t nr_nonces;
  47 } NtpKs1List;
  48
  49 // Struct for thread data
  50 typedef struct {
  51     NtpKs1List *pNKL;
  52     uint32_t startPos;
  53     uint32_t endPos;
  54     uint32_t *keyCount[MAX_NR_NONCES];
  55     uint64_t *result_keys[MAX_NR_NONCES];
  56     uint32_t thread_id;
  57     pthread_mutex_t *keyCount_mutex[MAX_NR_NONCES];
  58     uint32_t num_nonces;
  59 } thread_data_t;
  60
  61 static bool thread_status[NUM_THREADS];  // To keep track of active threads
  62 static pthread_mutex_t status_mutex = PTHREAD_MUTEX_INITIALIZER;
  63 static pthread_cond_t status_cond = PTHREAD_COND_INITIALIZER;
  64
  65 static uint32_t hex_to_uint32(const char *hex_str) {
  66     return (uint32_t)strtoul(hex_str, NULL, 16);
  67 }
  68
  69 static int bin_to_uint8_arr(const char *bin_str, uint8_t bit_arr[], uint8_t arr_size) {
  70     if (strlen(bin_str) != arr_size) {
  71         fprintf(stderr, "Error: Binary string (%s) length does not match array size (%i).\n", bin_str, arr_size);
  72         return 1;
  73     }
  74
  75     for (uint8_t i = 0; i < arr_size; i++) {
  76         if (bin_str[i] == '0') {
  77             bit_arr[i] = 0;
  78         } else if (bin_str[i] == '1') {
  79             bit_arr[i] = 1;
  80         } else {
  81             fprintf(stderr, "Error: Invalid character '%c' in binary string.\n", bin_str[i]);
  82             return 1;
  83         }
  84     }
  85     return 0;
  86 }
  87
  88 static uint8_t valid_nonce(uint32_t Nt, uint32_t ks1, uint8_t nt_par_enc) {
  89     return (oddparity8((Nt >> 24) & 0xFF) == (((nt_par_enc >> 3) & 1) ^ BIT(ks1, 16))) &&
  90            (oddparity8((Nt >> 16) & 0xFF) == (((nt_par_enc >> 2) & 1) ^ BIT(ks1,  8))) &&
  91            (oddparity8((Nt >>  8) & 0xFF) == (((nt_par_enc >> 1) & 1) ^ BIT(ks1,  0)));
  92 }
  93
  94 static bool search_match(NtData *pND, NtData *pND0, uint64_t key) {
  95     bool ret = 0;
  96     struct Crypto1State *s;
  97     s = crypto1_create(0);
  98     if (s == NULL) {
  99         fprintf(stderr, "\nMalloc error in search_match!\n");
 100         return 0;
 101     }
 102     crypto1_init(s, key);
 103     uint32_t authuid = pND->authuid;
 104     uint32_t nt_enc = pND->nt_enc;
 105     uint8_t nt_par_enc = pND->nt_par_enc;
 106     uint32_t nt = crypto1_word(s, nt_enc ^ authuid, 1) ^ nt_enc;
 107     // filter: we know nt should be valid, no need to spend time on other ones
 108     if (validate_prng_nonce(nt)) {
 109         // look for same nt
 110         for (uint32_t k = 0; k < pND->sizeNK; k++) {
 111             if (nt == pND->pNK[k].ntp) {
 112                 // Possible match
 113                 // filter: check the full 4 bits of parity (actually only the last one might be wrong)
 114                 uint32_t ks1, ks2;
 115                 uint8_t par1, par2, ksp;
 116                 par1 = (oddparity8((nt >> 24) & 0xFF) << 3) | (oddparity8((nt >> 16) & 0xFF) << 2) | (oddparity8((nt >> 8) & 0xFF) << 1) | (oddparity8(nt & 0xFF));
 117                 ks1 = nt ^ nt_enc;
 118                 ks2 = crypto1_word(s, 0, 0);
 119                 ksp = (((ks1 >> 16) & 1) << 3) | (((ks1 >> 8) & 1) << 2) | (((ks1 >> 0) & 1) << 1) | ((ks2 >> 24) & 1);
 120                 par2 = nt_par_enc ^ ksp;
 121
 122                 if (par1 != par2) {
 123                     continue;
 124                 }
 125
 126                 // filter: same check on the full 4 bits of parity of initial nonce
 127                 // check is slow so we do it only now
 128                 crypto1_init(s, key);
 129                 authuid = pND0->authuid;
 130                 nt_enc = pND0->nt_enc;
 131                 nt_par_enc = pND0->nt_par_enc;
 132                 nt = crypto1_word(s, nt_enc ^ authuid, 1) ^ nt_enc;
 133                 par1 = (oddparity8((nt >> 24) & 0xFF) << 3) | (oddparity8((nt >> 16) & 0xFF) << 2) | (oddparity8((nt >> 8) & 0xFF) << 1) | (oddparity8(nt & 0xFF));
 134                 ks1 = nt ^ nt_enc;
 135                 ks2 = crypto1_word(s, 0, 0);
 136                 ksp = (((ks1 >> 16) & 1) << 3) | (((ks1 >> 8) & 1) << 2) | (((ks1 >> 0) & 1) << 1) | ((ks2 >> 24) & 1);
 137                 par2 = nt_par_enc ^ ksp;
 138                 if (par1 != par2) {
 139                     continue;
 140                 }
 141
 142                 k = pND->sizeNK;
 143                 ret = 1;
 144             }
 145         }
 146     }
 147     crypto1_destroy(s);
 148     return ret;
 149 }
 150
 151 static void *generate_and_intersect_keys(void *threadarg) {
 152     thread_data_t *data = (thread_data_t *)threadarg;
 153     NtpKs1List *pNKL = data->pNKL;
 154     uint32_t startPos = data->startPos;
 155     uint32_t endPos = data->endPos;
 156     uint32_t thread_id = data->thread_id;
 157     uint32_t num_nonces = data->num_nonces;
 158
 159     struct Crypto1State *revstate, *revstate_start = NULL;
 160     uint64_t lfsr = 0;
 161
 162     uint32_t authuid = pNKL->NtDataList[0].authuid;
 163     for (uint32_t i = startPos; i < endPos; i++) {
 164         uint32_t ntp = pNKL->NtDataList[0].pNK[i].ntp;
 165         uint32_t ks1 = pNKL->NtDataList[0].pNK[i].ks1;
 166         uint32_t nt_probe = ntp ^ authuid;
 167
 168         revstate = lfsr_recovery32(ks1, nt_probe);
 169         if (revstate == NULL) {
 170             fprintf(stderr, "\nMalloc error in generate_and_intersect_keys!\n");
 171             pthread_exit(NULL);
 172         }
 173         if (revstate_start == NULL) {
 174             revstate_start = revstate;
 175         }
 176         uint32_t keyCount0 = 0;
 177         while ((revstate->odd != 0x0) || (revstate->even != 0x0)) {
 178             lfsr_rollback_word(revstate, nt_probe, 0);
 179             crypto1_get_lfsr(revstate, &lfsr);
 180             keyCount0++;
 181             for (uint32_t nonce_index = 1; nonce_index < num_nonces; nonce_index++) {
 182                 if (search_match(&pNKL->NtDataList[nonce_index], &pNKL->NtDataList[0], lfsr)) {
 183                     pthread_mutex_lock(data->keyCount_mutex[nonce_index]);
 184                     data->result_keys[nonce_index][*data->keyCount[nonce_index]] = lfsr;
 185                     (*data->keyCount[nonce_index])++;
 186                     pthread_mutex_unlock(data->keyCount_mutex[nonce_index]);
 187                     if (*data->keyCount[nonce_index] == KEY_SPACE_SIZE_STEP2) {
 188                         fprintf(stderr, "No space left on result_keys[%d], abort!\n", nonce_index);
 189                         i = endPos;
 190                         break;
 191                     }
 192                 }
 193             }
 194             revstate++;
 195         }
 196         free(revstate_start);
 197         revstate_start = NULL;
 198
 199         pthread_mutex_lock(data->keyCount_mutex[0]);
 200         (*data->keyCount[0]) += keyCount0;
 201         keyCount0 = 0;
 202         pthread_mutex_unlock(data->keyCount_mutex[0]);
 203     }
 204
 205     pthread_mutex_lock(&status_mutex);
 206     thread_status[thread_id] = false;  // Mark thread as inactive
 207     pthread_cond_signal(&status_cond);       // Signal the main thread
 208     pthread_mutex_unlock(&status_mutex);
 209     pthread_exit(NULL);
 210     return NULL; // Make some compilers happy
 211 }
 212
 213 static uint64_t **unpredictable_nested(NtpKs1List *pNKL, uint32_t keyCounts[]) {
 214     pthread_t threads[NUM_THREADS];
 215     thread_data_t thread_data[NUM_THREADS];
 216     pthread_mutex_t keyCount_mutex[MAX_NR_NONCES];
 217
 218     uint64_t **result_keys = (uint64_t **)calloc(MAX_NR_NONCES, sizeof(uint64_t *));
 219     for (uint32_t i = 0; i < MAX_NR_NONCES; i++) {
 220         // no result_keys[0] stored, would be too large
 221         if (i != 0) {
 222             result_keys[i] = (uint64_t *)calloc(KEY_SPACE_SIZE_STEP2, sizeof(uint64_t));
 223         }
 224         keyCounts[i] = 0;
 225         pthread_mutex_init(&keyCount_mutex[i], NULL);
 226     }
 227
 228     const uint32_t chunk_size = pNKL->NtDataList[0].sizeNK / NUM_THREADS / CHUNK_DIVISOR;
 229     uint32_t startPos = 0;
 230
 231     while (startPos < pNKL->NtDataList[0].sizeNK) {
 232         pthread_mutex_lock(&status_mutex);
 233         uint32_t activeThreads = 0;
 234
 235         // Count active threads
 236         for (int i = 0; i < NUM_THREADS; i++) {
 237             if (thread_status[i]) activeThreads++;
 238         }
 239         // Spawn new threads if there are available slots
 240         for (uint32_t t = 0; activeThreads < NUM_THREADS && startPos < pNKL->NtDataList[0].sizeNK && t < NUM_THREADS; t++) {
 241             if (!thread_status[t]) {
 242                 uint32_t endPos = startPos + chunk_size;
 243                 if (endPos > pNKL->NtDataList[0].sizeNK) {
 244                     endPos = pNKL->NtDataList[0].sizeNK;
 245                 }
 246
 247                 thread_data[t].pNKL = pNKL;
 248                 thread_data[t].startPos = startPos;
 249                 thread_data[t].endPos = endPos;
 250                 thread_data[t].thread_id = t;
 251                 thread_data[t].num_nonces = pNKL->nr_nonces;
 252                 for (uint32_t i = 0; i < MAX_NR_NONCES; i++) {
 253                     thread_data[t].result_keys[i] = result_keys[i];
 254                     thread_data[t].keyCount[i] = &keyCounts[i];
 255                     thread_data[t].keyCount_mutex[i] = &keyCount_mutex[i];
 256                 }
 257
 258                 thread_status[t] = true;  // Mark thread as active
 259                 pthread_create(&threads[t], NULL, generate_and_intersect_keys, (void *)&thread_data[t]);
 260                 activeThreads++;
 261                 startPos = endPos;
 262             }
 263         }
 264
 265         // Wait for any thread to complete
 266         while (activeThreads >= NUM_THREADS) {
 267             pthread_cond_wait(&status_cond, &status_mutex);
 268             activeThreads = 0;
 269             for (int i = 0; i < NUM_THREADS; i++) {
 270                 if (thread_status[i]) activeThreads++;
 271             }
 272         }
 273
 274         pthread_mutex_unlock(&status_mutex);
 275         printf("\33[2K\rProgress: %02.1f%%", (double)(startPos + 1) * 100 / pNKL->NtDataList[0].sizeNK);
 276         printf(" keys[%d]:%9i", 0, keyCounts[0]);
 277         for (uint32_t nonce_index = 1; nonce_index < pNKL->nr_nonces; nonce_index++) {
 278             printf(" keys[%d]:%5i", nonce_index, keyCounts[nonce_index]);
 279         }
 280         fflush(stdout);
 281     }
 282
 283     pthread_mutex_lock(&status_mutex);
 284     uint32_t activeThreads = 0;
 285
 286     // Count active threads
 287     for (int i = 0; i < NUM_THREADS; i++) {
 288         if (thread_status[i]) activeThreads++;
 289     }
 290     while (activeThreads) {
 291         pthread_cond_wait(&status_cond, &status_mutex);
 292         activeThreads = 0;
 293         for (int i = 0; i < NUM_THREADS; i++) {
 294             if (thread_status[i]) activeThreads++;
 295         }
 296     }
 297
 298     pthread_mutex_unlock(&status_mutex);
 299
 300     for (uint32_t i = 1; i < MAX_NR_NONCES; i++) {
 301         if (keyCounts[i] == 0) {
 302             free(result_keys[i]);
 303             result_keys[i] = NULL;
 304         }
 305     }
 306
 307     return result_keys;
 308 }
 309 // Function to compare keys and keep track of their occurrences
 310 static void analyze_keys(uint64_t **keys, uint32_t keyCounts[MAX_NR_NONCES], uint32_t nr_nonces) {
 311     // Assuming the maximum possible keys
 312 #define MAX_KEYS (MAX_NR_NONCES * KEY_SPACE_SIZE_STEP2)
 313     uint64_t combined_keys[MAX_KEYS] = {0};
 314     uint32_t combined_counts[MAX_KEYS] = {0};
 315     uint32_t combined_length = 0;
 316
 317     printf("Analyzing keys...\n");
 318     for (uint32_t i = 0; i < nr_nonces; i++) {
 319         if (i == 0) {
 320             printf("nT(%i): %i key candidates\n", i, keyCounts[i]);
 321             continue;
 322         } else {
 323             printf("nT(%i): %i key candidates matching nT(0)\n", i, keyCounts[i]);
 324         }
 325         for (uint32_t j = 0; j < keyCounts[i]; j++) {
 326             uint64_t key = keys[i][j];
 327             // Check if key is already in combined_keys
 328             bool found = false;
 329             for (uint32_t k = 0; k < combined_length; k++) {
 330                 if (combined_keys[k] == key) {
 331                     combined_counts[k]++;
 332                     found = true;
 333                     break;
 334                 }
 335             }
 336             // If key not found, add it to combined_keys
 337             if (!found) {
 338                 combined_keys[combined_length] = key;
 339                 combined_counts[combined_length] = 1;
 340                 combined_length++;
 341             }
 342         }
 343     }
 344
 345     for (uint32_t i = 0; i < combined_length; i++) {
 346         if (combined_counts[i] > 1) {
 347             printf("Key %012" PRIx64 " found in %d arrays: 0", combined_keys[i], combined_counts[i] + 1);
 348             for (uint32_t ii = 1; ii < nr_nonces; ii++) {
 349                 for (uint32_t j = 0; j < keyCounts[ii]; j++) {
 350                     if (combined_keys[i] == keys[ii][j]) {
 351                         printf(", %2i", ii);
 352                     }
 353                 }
 354             }
 355             printf("\n");
 356         }
 357     }
 358 }
 359
 360 int main(int argc, char *const argv[]) {
 361     if (argc < 2) {
 362         int cmdlen = strlen(argv[0]);
 363         printf("Usage:\n  %s <uid1> <nt_enc1> <nt_par_err1> <uid2> <nt_enc2> <nt_par_err2> ...\n", argv[0]);
 364         printf("  UID placeholder: if uid(n)==uid(n-1) you can use '.' as uid(n+1) placeholder\n");
 365         printf("  parity example:  if nt in trace is 7b! fc! 7a! 5b , then nt_enc is 7bfc7a5b and nt_par_err is 1110\n");
 366         printf("Example:\n");
 367         printf("  %*s a13e4902 2e9e49fc 1111 . 7bfc7a5b 1110 a17e4902 50f2abc2 1101\n", cmdlen, argv[0]);
 368         printf("  %*s +uid1    |        |    +uid2=uid1 |    +uid3    |        |\n", cmdlen, "");
 369         printf("  %*s          +nt_enc1 |      +nt_enc2 |             +nt_enc3 |\n", cmdlen, "");
 370         printf("  %*s                   +nt_par_err1    +nt_par_err2           +nt_par_err3\n", cmdlen, "");
 371         return 1;
 372     }
 373     if (argc < 1 + 2 * 3) {
 374         fprintf(stderr, "Too few nonces, abort. Need 2 nonces min.\n");
 375         return 1;
 376     }
 377     if (argc > 1 + MAX_NR_NONCES * 3) {
 378         fprintf(stderr, "Too many nonces, abort. Choose max %i nonces.\n", MAX_NR_NONCES);
 379         return 1;
 380     }
 381
 382     NtpKs1List NKL = {0};
 383     uint64_t **keys = NULL;
 384     uint32_t keyCounts[MAX_NR_NONCES] = {0};
 385
 386     uint32_t authuid = hex_to_uint32(argv[1]);
 387     // process all args.
 388     printf("Generating nonce candidates...\n");
 389     for (uint32_t i = 1; i < argc; i += 3) {
 390         // uid + ntEnc + parEnc
 391         if (strcmp(argv[i], ".") != 0) {
 392             authuid = hex_to_uint32(argv[i]);
 393         }
 394         uint32_t nt_enc = hex_to_uint32(argv[i + 1]);
 395         uint8_t nt_par_err_arr[4];
 396         if (bin_to_uint8_arr(argv[i + 2], nt_par_err_arr, 4)) {
 397             return 1;
 398         }
 399         uint8_t nt_par_enc = ((nt_par_err_arr[0] ^ oddparity8((nt_enc >> 24) & 0xFF)) << 3) |
 400                              ((nt_par_err_arr[1] ^ oddparity8((nt_enc >> 16) & 0xFF)) << 2) |
 401                              ((nt_par_err_arr[2] ^ oddparity8((nt_enc >>  8) & 0xFF)) << 1) |
 402                              ((nt_par_err_arr[3] ^ oddparity8((nt_enc >>  0) & 0xFF)) << 0);
 403         NtData *pNtData = &NKL.NtDataList[NKL.nr_nonces];
 404         // Try to recover the keystream1
 405         uint32_t nttest = prng_successor(1, 16); // a first valid nonce
 406         pNtData->pNK = (NtpKs1 *)calloc(8192, sizeof(NtpKs1)); // 2**16 filtered with 3 parity bits => 2**13
 407         if (pNtData->pNK == NULL) {
 408             return 1;
 409         }
 410         uint32_t j = 0;
 411         for (uint16_t m = 1; m; m++) {
 412             uint32_t ks1 = nt_enc ^ nttest;
 413             if (valid_nonce(nttest, ks1, nt_par_enc)) {
 414                 pNtData->pNK[j].ntp = nttest;
 415                 pNtData->pNK[j].ks1 = ks1;
 416                 j++;
 417             }
 418             nttest = prng_successor(nttest, 1);
 419         }
 420         printf("uid=%08x nt_enc=%08x nt_par_err=%i%i%i%i nt_par_enc=%i%i%i%i %i/%i: %d\n", authuid, nt_enc,
 421                nt_par_err_arr[0], nt_par_err_arr[1], nt_par_err_arr[2], nt_par_err_arr[3],
 422                (nt_par_enc >> 3) & 1, (nt_par_enc >> 2) & 1, (nt_par_enc >> 1) & 1, nt_par_enc & 1,
 423                NKL.nr_nonces + 1, (argc - 1) / 3, j);
 424
 425         pNtData->authuid = authuid;
 426         pNtData->sizeNK = j;
 427         pNtData->nt_enc = nt_enc;
 428         pNtData->nt_par_enc = nt_par_enc;
 429         NKL.nr_nonces++;
 430     }
 431
 432     printf("Finding key candidates...\n");
 433     keys = unpredictable_nested(&NKL, keyCounts);
 434     printf("\n\nFinding phase complete.\n");
 435
 436     for (uint32_t k = 0; k < NKL.nr_nonces; k++)
 437         free(NKL.NtDataList[k].pNK);
 438
 439     analyze_keys(keys, keyCounts, NKL.nr_nonces);
 440     FILE *fptr;
 441     // opening the file in read mode
 442     fptr = fopen("keys.dic", "w");
 443     if (fptr != NULL) {
 444         for (uint32_t i = 1; i < NKL.nr_nonces; i++) {
 445             if (keyCounts[i] > 0) {
 446                 for (uint32_t j = 0; j < keyCounts[i]; j++) {
 447                     fprintf(fptr, "%012" PRIx64 "\n", keys[i][j]);
 448                 }
 449             }
 450         }
 451         fclose(fptr);
 452     } else {
 453         fprintf(stderr, "Warning: Cannot save keys in keys.dic\n");
 454     }
 455     for (uint32_t i = 1; i < NKL.nr_nonces; i++) {
 456         if (keys[i] != NULL) {
 457             free(keys[i]);
 458         }
 459     }
 460     if (keys != NULL) {
 461         free(keys);
 462     }
 463
 464     return 0;
 465 }