tools/hitag2crack/crack5opencl/hitag2.c

   1 #include <stdio.h>
   2 #include "ht2crack5opencl.h"
   3 #include "hitag2.h"
   4
   5 //#if FORCE_HITAG2_FULL == 0
   6
   7 // return a single bit from a value
   8 int bitn(uint64_t x, int bit) {
   9     const uint64_t bitmask = (uint64_t)(1) << bit;
  10
  11     return (x & bitmask) ? 1 : 0;
  12 }
  13
  14 // the sub-function R that rollback depends upon
  15 int fnR(uint64_t x) {
  16     // renumbered bits because my state is 0-47, not 1-48
  17     return (bitn(x, 1) ^ bitn(x, 2) ^ bitn(x, 5) ^
  18             bitn(x, 6) ^ bitn(x, 7) ^ bitn(x, 15) ^
  19             bitn(x, 21) ^ bitn(x, 22) ^ bitn(x, 25) ^
  20             bitn(x, 29) ^ bitn(x, 40) ^ bitn(x, 41) ^
  21             bitn(x, 42) ^ bitn(x, 45) ^ bitn(x, 46) ^ bitn(x, 47));
  22 }
  23
  24 // the three filter sub-functions that feed fnf
  25 int fa(unsigned int i) {
  26     return bitn(0x2C79, (int)i);
  27 }
  28
  29 int fb(unsigned int i) {
  30     return bitn(0x6671, (int)i);
  31 }
  32
  33 // the filter function that generates a bit of output from the prng state
  34 int fnf(uint64_t s) {
  35     const unsigned int x1 = (unsigned int)((bitn(s,  2) << 0) | (bitn(s,  3) << 1) | (bitn(s,  5) << 2) | (bitn(s,  6) << 3));
  36     const unsigned int x2 = (unsigned int)((bitn(s,  8) << 0) | (bitn(s, 12) << 1) | (bitn(s, 14) << 2) | (bitn(s, 15) << 3));
  37     const unsigned int x3 = (unsigned int)((bitn(s, 17) << 0) | (bitn(s, 21) << 1) | (bitn(s, 23) << 2) | (bitn(s, 26) << 3));
  38     const unsigned int x4 = (unsigned int)((bitn(s, 28) << 0) | (bitn(s, 29) << 1) | (bitn(s, 31) << 2) | (bitn(s, 33) << 3));
  39     const unsigned int x5 = (unsigned int)((bitn(s, 34) << 0) | (bitn(s, 43) << 1) | (bitn(s, 44) << 2) | (bitn(s, 46) << 3));
  40
  41     const unsigned int x6 = (unsigned int)((fa(x1) << 0) | (fb(x2) << 1) | (fb(x3) << 2) | (fb(x4) << 3) | (fa(x5) << 4));
  42
  43     return bitn(0x7907287B, (int) x6);
  44 }
  45
  46 uint32_t hitag2_crypt(uint64_t x) {
  47     const uint32_t ht2_function4a = 0x2C79; // 0010 1100 0111 1001
  48     const uint32_t ht2_function4b = 0x6671; // 0110 0110 0111 0001
  49     const uint32_t ht2_function5c = 0x7907287B; // 0111 1001 0000 0111 0010 1000 0111 1011
  50
  51     uint32_t bitindex;
  52
  53     bitindex = (ht2_function4a >> pickbits2_2(x, 1, 4)) & 1;
  54     bitindex |= ((ht2_function4b << 1) >> pickbits1_1_2(x, 7, 11, 13)) & 0x02;
  55     bitindex |= ((ht2_function4b << 2) >> pickbits1x4(x, 16, 20, 22, 25)) & 0x04;
  56     bitindex |= ((ht2_function4b << 3) >> pickbits2_1_1(x, 27, 30, 32)) & 0x08;
  57     bitindex |= ((ht2_function4a << 4) >> pickbits1_2_1(x, 33, 42, 45)) & 0x10;
  58
  59 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
  60     printf("hitag2_crypt bitindex = %02x\n", bitindex);
  61 #endif
  62
  63     return (ht2_function5c >> bitindex) & 1;
  64 }
  65
  66 /*
  67  * Return up to 32 crypto bits.
  68  * Last bit is in least significant bit, earlier bits are shifted left.
  69  * Note that the Hitag transmission protocol is least significant bit,
  70  * so we may want to change this, or add a function, that returns the
  71  * crypto output bits in the other order.
  72  *
  73  * Parameters:
  74  * Hitag_State* pstate - in/out, internal cipher state after initialisation
  75  * uint32_t steps      - number of bits requested, (capped at 32)
  76  */
  77 uint32_t hitag2_nstep(Hitag_State *pstate, uint32_t steps) {
  78     uint64_t cur_state = pstate->shiftreg;
  79     uint32_t result = 0;
  80     uint64_t lfsr = pstate->lfsr;
  81
  82     if (steps == 0) return 0;
  83
  84     do {
  85         // update shift registers
  86         if (lfsr & 1) {
  87             cur_state = (cur_state >> 1) | 0x800000000000;
  88             lfsr = (lfsr >> 1) ^ 0xB38083220073;
  89
  90             // accumulate next bit of crypto
  91             result = (result << 1) | hitag2_crypt(cur_state);
  92         } else {
  93             cur_state >>= 1;
  94             lfsr >>= 1;
  95
  96             result = (result << 1) | hitag2_crypt(cur_state);
  97         }
  98     } while (--steps);
  99
 100 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 101 #ifdef _ISOC99_SOURCE
 102     printf("hitag2_nstep cur_state = %012I64x, result %02x\n", cur_state, result);
 103 #else
 104     printf("hitag2_nstep cur_state = %012" STR(OFF_FORMAT_X) ", result %02x\n", cur_state, result);
 105 #endif
 106 #endif // DEBUG_HITAG2
 107
 108     pstate->shiftreg = cur_state;
 109     pstate->lfsr = lfsr;
 110     return result;
 111 }
 112
 113 /*
 114  * Parameters:
 115  * Hitag_State* pstate - output, internal state after initialisation
 116  * uint64_t sharedkey  - 48 bit key shared between reader & tag
 117  * uint32_t serialnum  - 32 bit tag serial number
 118  * uint32_t initvector - 32 bit random IV from reader, part of tag authentication
 119  */
 120 void hitag2_init(Hitag_State *pstate, uint64_t sharedkey, uint32_t serialnum, uint32_t initvector) {
 121     // init state, from serial number and lowest 16 bits of shared key
 122     uint64_t cur_state = ((sharedkey & 0xFFFF) << 32) | serialnum;
 123
 124     // mix the initialisation vector and highest 32 bits of the shared key
 125     initvector ^= (uint32_t)(sharedkey >> 16);
 126
 127     // move 16 bits from (IV xor Shared Key) to top of uint64_t state
 128     // these will be XORed in turn with output of the crypto function
 129     cur_state |= (uint64_t) initvector << 48;
 130     initvector >>= 16;
 131
 132     // unrolled loop is faster on PIC32 (MIPS), do 32 times
 133     // shift register, then calc new bit
 134     cur_state >>= 1;
 135
 136     int i;
 137
 138     for (i = 0; i < 16; i++) {
 139         cur_state = (cur_state >> 1) ^ (uint64_t) hitag2_crypt(cur_state) << 46;
 140     }
 141
 142     // highest 16 bits of IV XOR Shared Key
 143     cur_state |= (uint64_t) initvector << 47;
 144
 145     for (i = 0; i < 15; i++) {
 146         cur_state = (cur_state >> 1) ^ (uint64_t) hitag2_crypt(cur_state) << 46;
 147     }
 148
 149     cur_state ^= (uint64_t) hitag2_crypt(cur_state) << 47;
 150
 151     pstate->shiftreg = cur_state;
 152 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 153 #ifdef _ISOC99_SOURCE
 154     printf("hitag2_init shiftreg = %012I64x\n", pstate->shiftreg);
 155 #else
 156     printf("hitag2_init shiftreg = %012" STR(OFF_FORMAT_X) "\n", pstate->shiftreg);
 157 #endif
 158 #endif // DEBUG_HITAG2
 159
 160     /* naive version for reference, LFSR has 16 taps
 161     pstate->lfsr = state ^ (state >>  2) ^ (state >>  3) ^ (state >>  6)
 162              ^ (state >>  7) ^ (state >>  8) ^ (state >> 16) ^ (state >> 22)
 163              ^ (state >> 23) ^ (state >> 26) ^ (state >> 30) ^ (state >> 41)
 164              ^ (state >> 42) ^ (state >> 43) ^ (state >> 46) ^ (state >> 47);
 165     */
 166
 167     // optimise with one 64-bit intermediate
 168     uint64_t temp = cur_state ^ (cur_state >> 1);
 169
 170     pstate->lfsr = cur_state ^ (cur_state >>  6) ^ (cur_state >> 16) ^
 171                    (cur_state >> 26) ^ (cur_state >> 30) ^ (cur_state >> 41) ^
 172                    (temp >>  2) ^ (temp >>  7) ^ (temp >> 22) ^ (temp >> 42) ^ (temp >> 46);
 173
 174 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 175 #ifdef _ISOC99_SOURCE
 176     printf("hitag2_init lfsr = %012I64x\n", pstate->lfsr);
 177 #else
 178     printf("hitag2_init lfsr = %012" STR(OFF_FORMAT_X) "\n", pstate->lfsr);
 179 #endif
 180 #endif // DEBUG_HITAG2
 181 }
 182
 183 // try state
 184
 185 // todo, changes arguments, only what is needed
 186 bool try_state(uint64_t s, uint32_t uid, uint32_t aR2, uint32_t nR1, uint32_t nR2, uint64_t *key) {
 187 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 188     printf("s : %lu, uid: %u, aR2: %u, nR1: %u, nR2: %u\n", s, uid, aR2, nR1, nR2);
 189     fflush(stdout);
 190 #endif
 191
 192     Hitag_State hstate;
 193     uint64_t keyrev, nR1xk;
 194     uint32_t b = 0;
 195
 196     hstate.shiftreg = s;
 197
 198     //rollback(&hstate, 2);
 199     hstate.shiftreg = (uint64_t)(((hstate.shiftreg << 1) & 0xffffffffffff) | (uint64_t)fnR(hstate.shiftreg));
 200     hstate.shiftreg = (uint64_t)(((hstate.shiftreg << 1) & 0xffffffffffff) | (uint64_t)fnR(hstate.shiftreg));
 201
 202 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 203     printf("shiftreg : %lu\n", hstate.shiftreg);
 204     fflush(stdout);
 205 #endif
 206
 207     // recover key
 208     keyrev = hstate.shiftreg & 0xffff;
 209     nR1xk = (hstate.shiftreg >> 16) & 0xffffffff;
 210
 211 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 212     printf("keyrev: %lu, nR1xk: %lu\n", keyrev, nR1xk);
 213     fflush(stdout);
 214 #endif
 215
 216     for (int i = 0; i < 32; i++) {
 217         hstate.shiftreg = ((hstate.shiftreg) << 1) | ((uid >> (31 - i)) & 0x1);
 218         b = (b << 1) | (unsigned int) fnf(hstate.shiftreg);
 219     }
 220
 221 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 222     printf("shiftreg: %lu\n", hstate.shiftreg);
 223     fflush(stdout);
 224 #endif
 225
 226     keyrev |= (nR1xk ^ nR1 ^ b) << 16;
 227
 228 #if defined(DEBUG_HITAG2) && DEBUG_HITAG2 == 1
 229     printf("keyrev: %lu\n", keyrev);
 230     fflush(stdout);
 231 #endif
 232
 233     // test key
 234     hitag2_init(&hstate, keyrev, uid, nR2);
 235     if ((aR2 ^ hitag2_nstep(&hstate, 32)) == 0xffffffff) {
 236         *key = rev64(keyrev);
 237
 238 #if DEBUGME >= 2
 239 #if ENABLE_EMOJ == 1
 240         printf("\nKey found ╭☞  ");
 241 #else
 242         printf("\nKey found: ");
 243 #endif
 244         for (int i = 0; i < 6; i++) {
 245             printf("%02X", (uint8_t)(*key & 0xff));
 246             *key = *key >> 8;
 247         }
 248         printf("\n");
 249 #endif
 250         return true;
 251     }
 252
 253     return false;
 254 }
 255
 256 //#endif // FORCE_HITAG2_FULL = 0