armsrc/optimized_ikeys.c

   1 //-----------------------------------------------------------------------------
   2 // Borrowed initially from https://github.com/holiman/loclass
   3 // Copyright (C) 2014 Martin Holst Swende
   4 // Copyright (C) Proxmark3 contributors. See AUTHORS.md for details.
   5 //
   6 // This program is free software: you can redistribute it and/or modify
   7 // it under the terms of the GNU General Public License as published by
   8 // the Free Software Foundation, either version 3 of the License, or
   9 // (at your option) any later version.
  10 //
  11 // This program is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15 //
  16 // See LICENSE.txt for the text of the license.
  17 //-----------------------------------------------------------------------------
  18 // WARNING
  19 //
  20 // THIS CODE IS CREATED FOR EXPERIMENTATION AND EDUCATIONAL USE ONLY.
  21 //
  22 // USAGE OF THIS CODE IN OTHER WAYS MAY INFRINGE UPON THE INTELLECTUAL
  23 // PROPERTY OF OTHER PARTIES, SUCH AS INSIDE SECURE AND HID GLOBAL,
  24 // AND MAY EXPOSE YOU TO AN INFRINGEMENT ACTION FROM THOSE PARTIES.
  25 //
  26 // THIS CODE SHOULD NEVER BE USED TO INFRINGE PATENTS OR INTELLECTUAL PROPERTY RIGHTS.
  27 //-----------------------------------------------------------------------------
  28 // It is a reconstruction of the cipher engine used in iClass, and RFID techology.
  29 //
  30 // The implementation is based on the work performed by
  31 // Flavio D. Garcia, Gerhard de Koning Gans, Roel Verdult and
  32 // Milosch Meriac in the paper "Dismantling IClass".
  33 //-----------------------------------------------------------------------------
  34
  35 /**
  36 From "Dismantling iclass":
  37     This section describes in detail the built-in key diversification algorithm of iClass.
  38     Besides the obvious purpose of deriving a card key from a master key, this
  39     algorithm intends to circumvent weaknesses in the cipher by preventing the
  40     usage of certain ‘weak’ keys. In order to compute a diversified key, the iClass
  41     reader first encrypts the card identity id with the master key K, using single
  42     DES. The resulting ciphertext is then input to a function called hash0 which
  43     outputs the diversified key k.
  44
  45     k = hash0(DES enc (id, K))
  46
  47     Here the DES encryption of id with master key K outputs a cryptogram c
  48     of 64 bits. These 64 bits are divided as c = x, y, z [0] , . . . , z [7] ∈ F 82 × F 82 × (F 62 ) 8
  49     which is used as input to the hash0 function. This function introduces some
  50     obfuscation by performing a number of permutations, complement and modulo
  51     operations, see Figure 2.5. Besides that, it checks for and removes patterns like
  52     similar key bytes, which could produce a strong bias in the cipher. Finally, the
  53     output of hash0 is the diversified card key k = k [0] , . . . , k [7] ∈ (F 82 ) 8 .
  54
  55 **/
  56 #include "optimized_ikeys.h"
  57
  58 #include <stdint.h>
  59 #include <stdbool.h>
  60 #include <inttypes.h>
  61 #include "mbedtls/des.h"
  62 #include "optimized_cipherutils.h"
  63
  64 static uint8_t pi[35] = {
  65     0x0F, 0x17, 0x1B, 0x1D, 0x1E, 0x27, 0x2B, 0x2D,
  66     0x2E, 0x33, 0x35, 0x39, 0x36, 0x3A, 0x3C, 0x47,
  67     0x4B, 0x4D, 0x4E, 0x53, 0x55, 0x56, 0x59, 0x5A,
  68     0x5C, 0x63, 0x65, 0x66, 0x69, 0x6A, 0x6C, 0x71,
  69     0x72, 0x74, 0x78
  70 };
  71
  72 static mbedtls_des_context ctx_enc;
  73
  74 /**
  75  * @brief The key diversification algorithm uses 6-bit bytes.
  76  * This implementation uses 64 bit uint to pack seven of them into one
  77  * variable. When they are there, they are placed as follows:
  78  * XXXX XXXX N0 .... N7, occupying the last 48 bits.
  79  *
  80  * This function picks out one from such a collection
  81  * @param all
  82  * @param n bitnumber
  83  * @return
  84  */
  85 static uint8_t getSixBitByte(uint64_t c, int n) {
  86     return (c >> (42 - 6 * n)) & 0x3F;
  87 }
  88
  89 /**
  90  * @brief Puts back a six-bit 'byte' into a uint64_t.
  91  * @param c buffer
  92  * @param z the value to place there
  93  * @param n bitnumber.
  94  */
  95 static void pushbackSixBitByte(uint64_t *c, uint8_t z, int n) {
  96     //0x XXXX YYYY ZZZZ ZZZZ ZZZZ
  97     //             ^z0         ^z7
  98     //z0:  1111 1100 0000 0000
  99
 100     uint64_t masked = z & 0x3F;
 101     uint64_t eraser = 0x3F;
 102     masked <<= 42 - 6 * n;
 103     eraser <<= 42 - 6 * n;
 104
 105     //masked <<= 6*n;
 106     //eraser <<= 6*n;
 107
 108     eraser = ~eraser;
 109     (*c) &= eraser;
 110     (*c) |= masked;
 111
 112 }
 113 /**
 114  * @brief Swaps the z-values.
 115  * If the input value has format XYZ0Z1...Z7, the output will have the format
 116  * XYZ7Z6...Z0 instead
 117  * @param c
 118  * @return
 119  */
 120 static uint64_t swapZvalues(uint64_t c) {
 121     uint64_t newz = 0;
 122     pushbackSixBitByte(&newz, getSixBitByte(c, 0), 7);
 123     pushbackSixBitByte(&newz, getSixBitByte(c, 1), 6);
 124     pushbackSixBitByte(&newz, getSixBitByte(c, 2), 5);
 125     pushbackSixBitByte(&newz, getSixBitByte(c, 3), 4);
 126     pushbackSixBitByte(&newz, getSixBitByte(c, 4), 3);
 127     pushbackSixBitByte(&newz, getSixBitByte(c, 5), 2);
 128     pushbackSixBitByte(&newz, getSixBitByte(c, 6), 1);
 129     pushbackSixBitByte(&newz, getSixBitByte(c, 7), 0);
 130     newz |= (c & 0xFFFF000000000000);
 131     return newz;
 132 }
 133
 134 /**
 135 * @return 4 six-bit bytes chunked into a uint64_t,as 00..00a0a1a2a3
 136 */
 137 static uint64_t ck(int i, int j, uint64_t z) {
 138     if (i == 1 && j == -1) {
 139         // ck(1, −1, z [0] . . . z [3] ) = z [0] . . . z [3]
 140         return z;
 141     } else if (j == -1) {
 142         // ck(i, −1, z [0] . . . z [3] ) = ck(i − 1, i − 2, z [0] . . . z [3] )
 143         return ck(i - 1, i - 2, z);
 144     }
 145
 146     if (getSixBitByte(z, i) == getSixBitByte(z, j)) {
 147         //ck(i, j − 1, z [0] . . . z [i] ← j . . . z [3] )
 148         uint64_t newz = 0;
 149         int c;
 150         for (c = 0; c < 4; c++) {
 151             uint8_t val = getSixBitByte(z, c);
 152             if (c == i)
 153                 pushbackSixBitByte(&newz, j, c);
 154             else
 155                 pushbackSixBitByte(&newz, val, c);
 156         }
 157         return ck(i, j - 1, newz);
 158     } else {
 159         return ck(i, j - 1, z);
 160     }
 161 }
 162 /**
 163
 164     Definition 8.
 165     Let the function check : (F 62 ) 8 → (F 62 ) 8 be defined as
 166     check(z [0] . . . z [7] ) = ck(3, 2, z [0] . . . z [3] ) · ck(3, 2, z [4] . . . z [7] )
 167
 168     where ck : N × N × (F 62 ) 4 → (F 62 ) 4 is defined as
 169
 170         ck(1, −1, z [0] . . . z [3] ) = z [0] . . . z [3]
 171         ck(i, −1, z [0] . . . z [3] ) = ck(i − 1, i − 2, z [0] . . . z [3] )
 172         ck(i, j, z [0] . . . z [3] ) =
 173         ck(i, j − 1, z [0] . . . z [i] ← j . . . z [3] ),  if z [i] = z [j] ;
 174         ck(i, j − 1, z [0] . . . z [3] ), otherwise
 175
 176     otherwise.
 177 **/
 178
 179 static uint64_t check(uint64_t z) {
 180     //These 64 bits are divided as c = x, y, z [0] , . . . , z [7]
 181
 182     // ck(3, 2, z [0] . . . z [3] )
 183     uint64_t ck1 = ck(3, 2, z);
 184
 185     // ck(3, 2, z [4] . . . z [7] )
 186     uint64_t ck2 = ck(3, 2, z << 24);
 187
 188     //The ck function will place the values
 189     // in the middle of z.
 190     ck1 &= 0x00000000FFFFFF000000;
 191     ck2 &= 0x00000000FFFFFF000000;
 192
 193     return ck1 | ck2 >> 24;
 194 }
 195
 196 static void permute(BitstreamIn_t *p_in, uint64_t z, int l, int r, BitstreamOut_t *out) {
 197     if (bitsLeft(p_in) == 0)
 198         return;
 199
 200     bool pn = tailBit(p_in);
 201     if (pn) { // pn = 1
 202         uint8_t zl = getSixBitByte(z, l);
 203
 204         push6bits(out, zl + 1);
 205         permute(p_in, z, l + 1, r, out);
 206     } else { // otherwise
 207         uint8_t zr = getSixBitByte(z, r);
 208
 209         push6bits(out, zr);
 210         permute(p_in, z, l, r + 1, out);
 211     }
 212 }
 213
 214 /**
 215  * @brief
 216  *Definition 11. Let the function hash0 : F 82 × F 82 × (F 62 ) 8 → (F 82 ) 8 be defined as
 217  *  hash0(x, y, z [0] . . . z [7] ) = k [0] . . . k [7] where
 218  * z'[i] = (z[i] mod (63-i)) + i      i =  0...3
 219  * z'[i+4] = (z[i+4] mod (64-i)) + i  i =  0...3
 220  * ẑ = check(z');
 221  * @param c
 222  * @param k this is where the diversified key is put (should be 8 bytes)
 223  * @return
 224  */
 225 void hash0(uint64_t c, uint8_t k[8]) {
 226     c = swapZvalues(c);
 227
 228     //These 64 bits are divided as c = x, y, z [0] , . . . , z [7]
 229     // x = 8 bits
 230     // y = 8 bits
 231     // z0-z7 6 bits each : 48 bits
 232     uint8_t x = (c & 0xFF00000000000000) >> 56;
 233     uint8_t y = (c & 0x00FF000000000000) >> 48;
 234     uint64_t zP = 0;
 235
 236     for (int n = 0;  n < 4 ; n++) {
 237         uint8_t zn = getSixBitByte(c, n);
 238         uint8_t zn4 = getSixBitByte(c, n + 4);
 239         uint8_t _zn = (zn % (63 - n)) + n;
 240         uint8_t _zn4 = (zn4 % (64 - n)) + n;
 241         pushbackSixBitByte(&zP, _zn, n);
 242         pushbackSixBitByte(&zP, _zn4, n + 4);
 243     }
 244
 245     uint64_t zCaret = check(zP);
 246     uint8_t p = pi[x % 35];
 247
 248     if (x & 1) //Check if x7 is 1
 249         p = ~p;
 250
 251     BitstreamIn_t p_in = { &p, 8, 0 };
 252     uint8_t outbuffer[] = {0, 0, 0, 0, 0, 0, 0, 0};
 253     BitstreamOut_t out = {outbuffer, 0, 0};
 254     permute(&p_in, zCaret, 0, 4, &out); //returns 48 bits? or 6 8-bytes
 255
 256     //Out is now a buffer containing six-bit bytes, should be 48 bits
 257     // if all went well
 258     //Shift z-values down onto the lower segment
 259
 260     uint64_t zTilde = x_bytes_to_num(outbuffer, sizeof(outbuffer));
 261
 262     zTilde >>= 16;
 263
 264     for (int i = 0; i < 8; i++) {
 265         // the key on index i is first a bit from y
 266         // then six bits from z,
 267         // then a bit from p
 268
 269         // Init with zeroes
 270         k[i] = 0;
 271         // First, place yi leftmost in k
 272         //k[i] |= (y  << i) & 0x80 ;
 273
 274         // First, place y(7-i) leftmost in k
 275         k[i] |= (y  << (7 - i)) & 0x80 ;
 276
 277         uint8_t zTilde_i = getSixBitByte(zTilde, i);
 278         // zTildeI is now on the form 00XXXXXX
 279         // with one leftshift, it'll be
 280         // 0XXXXXX0
 281         // So after leftshift, we can OR it into k
 282         // However, when doing complement, we need to
 283         // again MASK 0XXXXXX0 (0x7E)
 284         zTilde_i <<= 1;
 285
 286         //Finally, add bit from p or p-mod
 287         //Shift bit i into rightmost location (mask only after complement)
 288         uint8_t p_i = p >> i & 0x1;
 289
 290         if (k[i]) { // yi = 1
 291             k[i] |= ~zTilde_i & 0x7E;
 292             k[i] |= p_i & 1;
 293             k[i] += 1;
 294
 295         } else { // otherwise
 296             k[i] |= zTilde_i & 0x7E;
 297             k[i] |= (~p_i) & 1;
 298         }
 299     }
 300 }
 301 /**
 302  * @brief Performs Elite-class key diversification
 303  * @param csn
 304  * @param key
 305  * @param div_key
 306  */
 307 void diversifyKey(uint8_t *csn, uint8_t *key, uint8_t *div_key) {
 308     // Prepare the DES key
 309     mbedtls_des_setkey_enc(&ctx_enc, key);
 310
 311     uint8_t crypted_csn[8] = {0};
 312
 313     // Calculate DES(CSN, KEY)
 314     mbedtls_des_crypt_ecb(&ctx_enc, csn, crypted_csn);
 315
 316     //Calculate HASH0(DES))
 317     uint64_t c_csn = x_bytes_to_num(crypted_csn, sizeof(crypted_csn));
 318
 319     hash0(c_csn, div_key);
 320 }
 321