tools/mfc/card_only/staticnested_2x1nt_rf08s.c

   1 // Faster Backdoored Nested Attack against Fudan FM11RF08S tags
   2 //
   3 // Attack conditions:
   4 // * Backdoor
   5 // * keyA and keyB are different for the targeted sector
   6 //
   7 // Strategy:
   8 // * Use backdoor on the targeted sector to get the clear static nested nT for keyA and for keyB
   9 // * Generate 2 lists of key candidates based on clear and encrypted nT
  10 // * Search couples of keyA/keyB satisfying some obscure relationship
  11 // * Use the resulting dictionary to bruteforce the keyA (and staticnested_2x1nt_rf08s_1key for keyB)
  12 //
  13 //  Doegox, 2024, cf https://eprint.iacr.org/2024/1275 for more info
  14
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <stdbool.h>
  18 #include <string.h>
  19 #include <inttypes.h>
  20
  21 uint16_t i_lfsr16[1 << 16] = {0};
  22 uint16_t s_lfsr16[1 << 16] = {0};
  23
  24 static void init_lfsr16_table(void) {
  25     uint16_t x = 1;
  26     for (uint16_t i = 1; i; ++i) {
  27         i_lfsr16[(x & 0xff) << 8 | x >> 8] = i;
  28         s_lfsr16[i] = (x & 0xff) << 8 | x >> 8;
  29         x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
  30     }
  31 }
  32
  33 // static uint16_t next_lfsr16(uint16_t nonce) {
  34 //     return s_lfsr16[(i_lfsr16[nonce]+1) % 65535];
  35 // }
  36
  37 static uint16_t prev_lfsr16(uint16_t nonce) {
  38     return s_lfsr16[(i_lfsr16[nonce] - 1) % 65535];
  39 }
  40
  41 static uint16_t compute_seednt16_nt32(uint32_t nt32, uint64_t key) {
  42     uint8_t a[] = {0, 8, 9, 4, 6, 11, 1, 15, 12, 5, 2, 13, 10, 14, 3, 7};
  43     uint8_t b[] = {0, 13, 1, 14, 4, 10, 15, 7, 5, 3, 8, 6, 9, 2, 12, 11};
  44     uint16_t nt = nt32 >> 16;
  45     uint8_t prev = 14;
  46     for (uint8_t i = 0; i < prev; i++) {
  47         nt = prev_lfsr16(nt);
  48     }
  49     uint8_t prevoff = 8;
  50     bool odd = 1;
  51
  52     for (uint8_t i = 0; i < 6 * 8; i += 8) {
  53         if (odd) {
  54             nt ^= (a[(key >> i) & 0xF]);
  55             nt ^= (b[(key >> i >> 4) & 0xF]) << 4;
  56         } else {
  57             nt ^= (b[(key >> i) & 0xF]);
  58             nt ^= (a[(key >> i >> 4) & 0xF]) << 4;
  59         }
  60         odd ^= 1;
  61         prev += prevoff;
  62         for (uint8_t j = 0; j < prevoff; j++) {
  63             nt = prev_lfsr16(nt);
  64         }
  65     }
  66     return nt;
  67 }
  68
  69 int main(int argc, char *const argv[]) {
  70
  71     if (argc != 3) {
  72         printf("Usage:\n  %s keys_<uid:08x>_<sector:02>_<nt1:08x>.dic keys_<uid:08x>_<sector:02>_<nt2:08x>.dic\n"
  73                "  where both dict files are produced by staticnested_1nt *for the same UID and same sector*\n",
  74                argv[0]);
  75         return 1;
  76     }
  77
  78     uint32_t uid1, sector1, nt1, uid2, sector2, nt2;
  79     char *filename1 = argv[1], *filename2 = argv[2];
  80
  81     int result = sscanf(filename1, "keys_%8x_%2u_%8x.dic", &uid1, &sector1, &nt1);
  82     if (result != 3) {
  83         fprintf(stderr, "Error: Failed to parse the filename %s.\n", filename1);
  84         return 1;
  85     }
  86
  87     result = sscanf(filename2, "keys_%8x_%2u_%8x.dic", &uid2, &sector2, &nt2);
  88     if (result != 3) {
  89         fprintf(stderr, "Error: Failed to parse the filename %s.\n", filename2);
  90         return 1;
  91     }
  92
  93     if (uid1 != uid2) {
  94         fprintf(stderr, "Error: Files must belong to the same UID.\n");
  95         return 1;
  96     }
  97
  98     if (sector1 != sector2) {
  99         fprintf(stderr, "Error: Files must belong to the same sector.\n");
 100         return 1;
 101     }
 102
 103     if (nt1 == nt2) {
 104         fprintf(stderr, "Error: Files must belong to different nonces.\n");
 105         return 1;
 106     }
 107
 108     init_lfsr16_table();
 109
 110     uint32_t keycount1 = 0;
 111     uint64_t *keys1 = NULL;
 112     uint8_t *filter_keys1 = NULL;
 113     uint16_t *seednt1 = NULL;
 114     uint32_t keycount2 = 0;
 115     uint64_t *keys2 = NULL;
 116     uint8_t *filter_keys2 = NULL;
 117     FILE *fptr;
 118
 119     fptr = fopen(filename1, "r");
 120     if (fptr != NULL) {
 121
 122         uint64_t buffer;
 123         while (fscanf(fptr, "%012" PRIx64, &buffer) == 1) {
 124             keycount1++;
 125         }
 126
 127         keys1 = (uint64_t *)calloc(1, keycount1 * sizeof(uint64_t));
 128         filter_keys1 = (uint8_t *)calloc(keycount1, sizeof(uint8_t));
 129         if ((keys1 == NULL) || (filter_keys1 == NULL)) {
 130             perror("Failed to allocate memory");
 131             fclose(fptr);
 132             goto end;
 133         }
 134
 135         rewind(fptr);
 136
 137         for (uint32_t i = 0; i < keycount1; i++) {
 138             if (fscanf(fptr, "%012" PRIx64, &keys1[i]) != 1) {
 139                 perror("Failed to read key");
 140                 fclose(fptr);
 141                 goto end;
 142             }
 143         }
 144         fclose(fptr);
 145     } else {
 146         fprintf(stderr, "Warning: Cannot open %s\n", filename1);
 147         goto end;
 148     }
 149
 150     fptr = fopen(filename2, "r");
 151     if (fptr != NULL) {
 152
 153         uint64_t buffer;
 154         while (fscanf(fptr, "%012" PRIx64, &buffer) == 1) {
 155             keycount2++;
 156         }
 157
 158         keys2 = (uint64_t *)calloc(1, keycount2 * sizeof(uint64_t));
 159         filter_keys2 = (uint8_t *)calloc(keycount2, sizeof(uint8_t));
 160         if ((keys2 == NULL) || (filter_keys2 == NULL)) {
 161             perror("Failed to allocate memory");
 162             fclose(fptr);
 163             goto end;
 164         }
 165
 166         rewind(fptr);
 167
 168         for (uint32_t i = 0; i < keycount2; i++) {
 169             if (fscanf(fptr, "%012" PRIx64, &keys2[i]) != 1) {
 170                 perror("Failed to read key");
 171                 fclose(fptr);
 172                 goto end;
 173             }
 174         }
 175         fclose(fptr);
 176     } else {
 177         fprintf(stderr, "Warning: Cannot open %s\n", filename2);
 178         goto end;
 179     }
 180
 181     printf("%s: %u keys loaded\n", filename1, keycount1);
 182     printf("%s: %u keys loaded\n", filename2, keycount2);
 183
 184     seednt1 = (uint16_t *)calloc(1, keycount1 * sizeof(uint16_t));
 185     if (seednt1 == NULL) {
 186         perror("Failed to allocate memory");
 187         goto end;
 188     }
 189
 190     for (uint32_t i = 0; i < keycount1; i++) {
 191         seednt1[i] = compute_seednt16_nt32(nt1, keys1[i]);
 192     }
 193
 194     for (uint32_t j = 0; j < keycount2; j++) {
 195         uint16_t seednt2 = compute_seednt16_nt32(nt2, keys2[j]);
 196         for (uint32_t i = 0; i < keycount1; i++) {
 197             if (seednt2 == seednt1[i]) {
 198 //                printf("MATCH: key1=%012" PRIx64 " key2=%012" PRIx64 "\n", keys1[i], keys2[j]);
 199                 filter_keys1[i] = 1;
 200                 filter_keys2[j] = 1;
 201             }
 202         }
 203     }
 204
 205     char filter_filename1[40];
 206     uint32_t filter_keycount1 = 0;
 207     snprintf(filter_filename1, sizeof(filter_filename1), "keys_%08x_%02u_%08x_filtered.dic", uid1, sector1, nt1);
 208
 209     fptr = fopen(filter_filename1, "w");
 210     if (fptr != NULL) {
 211
 212         for (uint32_t j = 0; j < keycount1; j++) {
 213             if (filter_keys1[j]) {
 214                 filter_keycount1++;
 215                 fprintf(fptr, "%012" PRIx64 "\n", keys1[j]);
 216             }
 217         }
 218         fclose(fptr);
 219
 220     } else {
 221         fprintf(stderr, "Warning: Cannot save keys in %s\n", filter_filename1);
 222     }
 223
 224     char filter_filename2[40];
 225     uint32_t filter_keycount2 = 0;
 226     snprintf(filter_filename2, sizeof(filter_filename2), "keys_%08x_%02u_%08x_filtered.dic", uid2, sector2, nt2);
 227
 228     fptr = fopen(filter_filename2, "w");
 229     if (fptr != NULL) {
 230
 231         for (uint32_t j = 0; j < keycount2; j++) {
 232             if (filter_keys2[j]) {
 233                 filter_keycount2++;
 234                 fprintf(fptr, "%012" PRIx64 "\n", keys2[j]);
 235             }
 236         }
 237         fclose(fptr);
 238
 239     } else {
 240         fprintf(stderr, "Warning: Cannot save keys in %s\n", filter_filename2);
 241     }
 242     printf("%s: %u keys saved\n", filter_filename1, filter_keycount1);
 243     printf("%s: %u keys saved\n", filter_filename2, filter_keycount2);
 244
 245 end:
 246     if (keys1 != NULL) {
 247         free(keys1);
 248     }
 249
 250     if (keys2 != NULL) {
 251         free(keys2);
 252     }
 253
 254     if (filter_keys1 != NULL) {
 255         free(filter_keys1);
 256     }
 257
 258     if (filter_keys2 != NULL) {
 259         free(filter_keys2);
 260     }
 261
 262     if (seednt1 != NULL) {
 263         free(seednt1);
 264     }
 265
 266     return 0;
 267 }