armsrc/optimized_ikeys.c

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