tools/mfc/card_only/nested_util.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <time.h>
   5 #include <inttypes.h>
   6 #include <ctype.h>
   7 #include "parity.h"
   8
   9 #ifdef __WIN32
  10 #include "windows.h"
  11 #else
  12 #include "unistd.h"
  13 #endif
  14
  15 #include "pthread.h"
  16 #include "nested_util.h"
  17
  18
  19 #define MEM_CHUNK               10000
  20 #define TRY_KEYS                50
  21
  22
  23 typedef struct {
  24     uint64_t       key;
  25     int            count;
  26 } countKeys;
  27
  28 typedef struct {
  29     NtpKs1 *pNK;
  30     uint32_t authuid;
  31
  32     uint64_t *keys;
  33     uint32_t keyCount;
  34
  35     uint32_t startPos;
  36     uint32_t endPos;
  37 } RecPar;
  38
  39 inline static int compar_int(const void *a, const void *b) {
  40     if (*(uint64_t *)b == *(uint64_t *)a) return 0;
  41     if (*(uint64_t *)b < * (uint64_t *)a) return 1;
  42     return -1;
  43 }
  44
  45 // Compare countKeys structure
  46 static int compar_special_int(const void *a, const void *b) {
  47     return (((countKeys *)b)->count - ((countKeys *)a)->count);
  48 }
  49
  50 // keys qsort and unique.
  51 static countKeys *uniqsort(uint64_t *possibleKeys, uint32_t size) {
  52     unsigned int i, j = 0;
  53     int count = 0;
  54     countKeys *our_counts;
  55
  56     qsort(possibleKeys, size, sizeof(uint64_t), compar_int);
  57
  58     our_counts = calloc(size, sizeof(countKeys));
  59     if (our_counts == NULL) {
  60         printf("Memory allocation error for our_counts");
  61         exit(EXIT_FAILURE);
  62     }
  63
  64     for (i = 0; i < size; i++) {
  65         if (possibleKeys[i + 1] == possibleKeys[i]) {
  66             count++;
  67         } else {
  68             our_counts[j].key = possibleKeys[i];
  69             our_counts[j].count = count;
  70             j++;
  71             count = 0;
  72         }
  73     }
  74     qsort(our_counts, j, sizeof(countKeys), compar_special_int);
  75     return (our_counts);
  76 }
  77
  78 // nested decrypt
  79 static void *nested_revover(void *args) {
  80     struct Crypto1State *revstate, * revstate_start = NULL;
  81     uint64_t lfsr = 0;
  82     uint32_t i, kcount = 0;
  83     bool is_ok = true;
  84
  85     RecPar *rp = (RecPar *)args;
  86
  87     rp->keyCount = 0;
  88     rp->keys = NULL;
  89
  90     //printf("Start pos is %d, End pos is %d\r\n", rp->startPos, rp->endPos);
  91
  92     for (i = rp->startPos; i < rp->endPos; i++) {
  93         uint32_t nt_probe = rp->pNK[i].ntp ^ rp->authuid;
  94         uint32_t ks1 = rp->pNK[i].ks1;
  95
  96         /*
  97         printf("     ntp = %"PRIu32"\r\n", nt_probe);
  98         printf("     ks1 = %"PRIu32"\r\n", ks1);
  99         printf("\r\n");
 100         */
 101
 102         // And finally recover the first 32 bits of the key
 103         revstate = lfsr_recovery32(ks1, nt_probe);
 104         if (revstate_start == NULL) {
 105             revstate_start = revstate;
 106         }
 107
 108         while ((revstate->odd != 0x0) || (revstate->even != 0x0)) {
 109             lfsr_rollback_word(revstate, nt_probe, 0);
 110             crypto1_get_lfsr(revstate, &lfsr);
 111             if (((kcount % MEM_CHUNK) == 0) || (kcount >= rp->keyCount)) {
 112                 rp->keyCount += MEM_CHUNK;
 113                 // printf("New chunk by %d, sizeof %lu\n", kcount, rp->keyCount * sizeof(uint64_t));
 114                 void *tmp = realloc(rp->keys, rp->keyCount * sizeof(uint64_t));
 115                 if (tmp == NULL) {
 116                     printf("Memory allocation error for pk->possibleKeys");
 117                     rp->keyCount = 0;
 118                     is_ok = false;
 119                     break;
 120                 }
 121                 rp->keys = (uint64_t *)tmp;
 122             }
 123             rp->keys[kcount] = lfsr;
 124             kcount++;
 125             revstate++;
 126         }
 127         --kcount;
 128         free(revstate_start);
 129         revstate_start = NULL;
 130         if (!is_ok) {
 131             break;
 132         }
 133     }
 134     if (is_ok) {
 135         if (kcount != 0) {
 136             rp->keyCount = kcount;
 137             void *tmp = (uint64_t *)realloc(rp->keys, rp->keyCount * sizeof(uint64_t));
 138             if (tmp == NULL) {
 139                 printf("Memory allocation error for pk->possibleKeys");
 140                 rp->keyCount = 0;
 141                 free(rp->keys);
 142             } else {
 143                 rp->keys = tmp;
 144             }
 145         }
 146     } else {
 147         rp->keyCount = 0;
 148         free(rp->keys);
 149     }
 150     return NULL;
 151 }
 152
 153 uint64_t *nested(NtpKs1 *pNK, uint32_t sizePNK, uint32_t authuid, uint32_t *keyCount) {
 154 #define THREAD_MAX 4
 155
 156     *keyCount = 0;
 157     uint32_t i, j, manyThread;
 158     uint64_t *keys = (uint64_t *)NULL;
 159
 160     manyThread = THREAD_MAX;
 161     if (manyThread > sizePNK) {
 162         manyThread = sizePNK;
 163     }
 164
 165     // pthread handle
 166     pthread_t *threads = calloc(sizePNK, sizeof(pthread_t));
 167     if (threads == NULL)  return NULL;
 168
 169     // Param
 170     RecPar *pRPs = calloc(sizePNK, sizeof(RecPar));
 171     if (pRPs == NULL) {
 172         free(threads);
 173         return NULL;
 174     }
 175
 176     uint32_t average = sizePNK / manyThread;
 177     uint32_t modules = sizePNK % manyThread;
 178
 179     // Assign tasks
 180     for (i = 0, j = 0; i < manyThread; i++, j += average) {
 181         pRPs[i].pNK = pNK;
 182         pRPs[i].authuid = authuid;
 183         pRPs[i].startPos = j;
 184         pRPs[i].endPos = j + average;
 185         pRPs[i].keys = NULL;
 186         // last thread can decrypt more pNK
 187         if (i == (manyThread - 1) && modules > 0) {
 188             (pRPs[i].endPos) += modules;
 189         }
 190         pthread_create(&threads[i], NULL, nested_revover, &(pRPs[i]));
 191     }
 192
 193     for (i = 0; i < manyThread; i++) {
 194         // wait thread exit...
 195         pthread_join(threads[i], NULL);
 196         *keyCount += pRPs[i].keyCount;
 197     }
 198     free(threads);
 199
 200     if (*keyCount == 0) {
 201         printf("Didn't recover any keys.\r\n");
 202         free(pRPs);
 203         return NULL;
 204     }
 205
 206     keys = calloc((*keyCount) * sizeof(uint64_t), sizeof(uint8_t));
 207     if (keys == NULL) {
 208         printf("Cannot allocate memory to merge keys.\r\n");
 209         free(pRPs);
 210         return NULL;
 211     }
 212
 213     for (i = 0, j = 0; i < manyThread; i++) {
 214         if (pRPs[i].keyCount > 0) {
 215             // printf("The thread %d recover %d keys.\r\n", i, pRPs[i].keyCount);
 216             if (pRPs[i].keys != NULL) {
 217                 memcpy(
 218                     keys + j,
 219                     pRPs[i].keys,
 220                     pRPs[i].keyCount * sizeof(uint64_t)
 221                 );
 222                 j += pRPs[i].keyCount;
 223                 free(pRPs[i].keys);
 224             }
 225         }
 226     }
 227
 228     countKeys *ck = uniqsort(keys, *keyCount);
 229     free(keys);
 230     keys = (uint64_t *)NULL;
 231     *keyCount = 0;
 232
 233     if (ck == NULL) {
 234         printf("Cannot allocate memory for ck on uniqsort.");
 235         free(ck);
 236         free(pRPs);
 237         return NULL;
 238     }
 239
 240     for (i = 0; i < TRY_KEYS; i++) {
 241         // We don't known this key, try to break it
 242         // This key can be found here two or more times
 243         if (ck[i].count > 0) {
 244             *keyCount += 1;
 245             void *tmp = realloc(keys, sizeof(uint64_t) * (*keyCount));
 246             if (tmp == NULL) {
 247                 printf("Cannot allocate memory for keys on merge.");
 248                 free(ck);
 249                 free(keys);
 250                 free(pRPs);
 251                 return NULL;
 252             }
 253
 254             keys = tmp;
 255             keys[*keyCount - 1] = ck[i].key;
 256         }
 257     }
 258
 259     free(ck);
 260     free(pRPs);
 261     return keys;
 262 }
 263
 264 // Return 1 if the nonce is invalid else return 0
 265 uint8_t valid_nonce(uint32_t Nt, uint32_t NtEnc, uint32_t Ks1, uint8_t *parity) {
 266     return (
 267                (oddparity8((Nt >> 24) & 0xFF) == ((parity[0]) ^ oddparity8((NtEnc >> 24) & 0xFF) ^ BIT(Ks1, 16))) && \
 268                (oddparity8((Nt >> 16) & 0xFF) == ((parity[1]) ^ oddparity8((NtEnc >> 16) & 0xFF) ^ BIT(Ks1, 8))) && \
 269                (oddparity8((Nt >> 8) & 0xFF) == ((parity[2]) ^ oddparity8((NtEnc >> 8) & 0xFF) ^ BIT(Ks1, 0)))
 270            ) ? 1 : 0;
 271 }