git.zerfleddert.de Git - proxmark3-svn/blob - client/loclass/ikeys.c

   1 /*****************************************************************************
   2  * This file is part of iClassCipher. It is a reconstructon of the cipher engine
   3  * used in iClass, and RFID techology.
   4  *
   5  * The implementation is based on the work performed by
   6  * Flavio D. Garcia, Gerhard de Koning Gans, Roel Verdult and
   7  * Milosch Meriac in the paper "Dismantling IClass".
   8  *
   9  * Copyright (C) 2014 Martin Holst Swende
  10  *
  11  * This is free software: you can redistribute it and/or modify
  12  * it under the terms of the GNU General Public License version 2 as published
  13  * by the Free Software Foundation.
  14  *
  15  * This file is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with IClassCipher.  If not, see <http://www.gnu.org/licenses/>.
  22  ****************************************************************************/
  23 /**
  24 From "Dismantling iclass":
  25         This section describes in detail the built-in key diversification algorithm of iClass.
  26         Besides the obvious purpose of deriving a card key from a master key, this
  27         algorithm intends to circumvent weaknesses in the cipher by preventing the
  28         usage of certain ‘weak’ keys. In order to compute a diversified key, the iClass
  29         reader first encrypts the card identity id with the master key K, using single
  30         DES. The resulting ciphertext is then input to a function called hash0 which
  31         outputs the diversified key k.
  32
  33         k = hash0(DES enc (id, K))
  34
  35         Here the DES encryption of id with master key K outputs a cryptogram c
  36         of 64 bits. These 64 bits are divided as c = x, y, z [0] , . . . , z [7] ∈ F 82 × F 82 × (F 62 ) 8
  37         which is used as input to the hash0 function. This function introduces some
  38         obfuscation by performing a number of permutations, complement and modulo
  39         operations, see Figure 2.5. Besides that, it checks for and removes patterns like
  40         similar key bytes, which could produce a strong bias in the cipher. Finally, the
  41         output of hash0 is the diversified card key k = k [0] , . . . , k [7] ∈ (F 82 ) 8 .
  42
  43
  44 **/
  45
  46
  47 #include <stdint.h>
  48 #include <stdbool.h>
  49 #include <string.h>
  50 #include "cipherutils.h"
  51 #include "cipher.h"
  52 #include "../util.h"
  53 #include <stdio.h>
  54 #include "des.h"
  55 #include <inttypes.h>
  56
  57 uint8_t pi[35] = {0x0F,0x17,0x1B,0x1D,0x1E,0x27,0x2B,0x2D,0x2E,0x33,0x35,0x39,0x36,0x3A,0x3C,0x47,0x4B,0x4D,0x4E,0x53,0x55,0x56,0x59,0x5A,0x5C,0x63,0x65,0x66,0x69,0x6A,0x6C,0x71,0x72,0x74,0x78};
  58
  59 static des_context ctx_enc = {DES_ENCRYPT,{0}};
  60 static des_context ctx_dec = {DES_DECRYPT,{0}};
  61
  62 static bool debug_print = false;
  63
  64 /**
  65  * @brief The key diversification algorithm uses 6-bit bytes.
  66  * This implementation uses 64 bit uint to pack seven of them into one
  67  * variable. When they are there, they are placed as follows:
  68  * XXXX XXXX N0 .... N7, occupying the lsat 48 bits.
  69  *
  70  * This function picks out one from such a collection
  71  * @param all
  72  * @param n bitnumber
  73  * @return
  74  */
  75 uint8_t getSixBitByte(uint64_t c, int n)
  76 {
  77         return (c >> (42-6*n)) & 0x3F;
  78         //return (c >> n*6) & 0x3f;
  79 }
  80
  81 /**
  82  * @brief Puts back a six-bit 'byte' into a uint64_t.
  83  * @param c buffer
  84  * @param z the value to place there
  85  * @param n bitnumber.
  86  */
  87 void pushbackSixBitByte(uint64_t *c, uint8_t z, int n)
  88 {
  89         //0x XXXX YYYY ZZZZ ZZZZ ZZZZ
  90         //             ^z0         ^z7
  91         //z0:  1111 1100 0000 0000
  92
  93         uint64_t masked = z & 0x3F;
  94         uint64_t eraser = 0x3F;
  95         masked <<= 42-6*n;
  96         eraser <<= 42-6*n;
  97
  98         //masked <<= 6*n;
  99         //eraser <<= 6*n;
 100
 101         eraser = ~eraser;
 102         (*c) &= eraser;
 103         (*c) |= masked;
 104
 105 }
 106
 107 uint64_t swapZvalues(uint64_t c)
 108 {
 109         uint64_t newz = 0;
 110         pushbackSixBitByte(&newz, getSixBitByte(c,0),7);
 111         pushbackSixBitByte(&newz, getSixBitByte(c,1),6);
 112         pushbackSixBitByte(&newz, getSixBitByte(c,2),5);
 113         pushbackSixBitByte(&newz, getSixBitByte(c,3),4);
 114         pushbackSixBitByte(&newz, getSixBitByte(c,4),3);
 115         pushbackSixBitByte(&newz, getSixBitByte(c,5),2);
 116         pushbackSixBitByte(&newz, getSixBitByte(c,6),1);
 117         pushbackSixBitByte(&newz, getSixBitByte(c,7),0);
 118         newz |= (c & 0xFFFF000000000000);
 119         return newz;
 120 }
 121
 122 /**
 123 * @return 4 six-bit bytes chunked into a uint64_t,as 00..00a0a1a2a3
 124 */
 125 uint64_t ck(int i, int j, uint64_t z)
 126 {
 127
 128 //      printf("ck( i=%d, j=%d), zi=[%d],zj=[%d] \n",i,j,getSixBitByte(z,i),getSixBitByte(z,j) );
 129
 130         if(i == 1 && j == -1)
 131         {
 132                 // ck(1, −1, z [0] . . . z [3] ) = z [0] . . . z [3]
 133                 return z;
 134
 135         }else if( j == -1)
 136         {
 137                 // ck(i, −1, z [0] . . . z [3] ) = ck(i − 1, i − 2, z [0] . . . z [3] )
 138                 return ck(i-1,i-2, z);
 139         }
 140
 141         if(getSixBitByte(z,i) == getSixBitByte(z,j))
 142         {
 143                 // TODO, I dont know what they mean here in the paper
 144                 //ck(i, j − 1, z [0] . . . z [i] ← j . . . z [3] )
 145                 uint64_t newz = 0;
 146                 int c;
 147                 //printf("z[i]=z[i] (0x%02x), i=%d, j=%d\n",getSixBitByte(z,i),i,j );
 148                 for(c = 0; c < 4 ;c++)
 149                 {
 150                         uint8_t val = getSixBitByte(z,c);
 151                         if(c == i)
 152                         {
 153                                 //printf("oops\n");
 154                                 pushbackSixBitByte(&newz, j, c);
 155                         }else
 156                         {
 157                                 pushbackSixBitByte(&newz, val, c);
 158                         }
 159                 }
 160                 return ck(i,j-1,newz);
 161         }else
 162         {
 163                 return ck(i,j-1,z);
 164         }
 165
 166 }
 167 /**
 168
 169         Definition 8.
 170         Let the function check : (F 62 ) 8 → (F 62 ) 8 be defined as
 171         check(z [0] . . . z [7] ) = ck(3, 2, z [0] . . . z [3] ) · ck(3, 2, z [4] . . . z [7] )
 172
 173         where ck : N × N × (F 62 ) 4 → (F 62 ) 4 is defined as
 174
 175                 ck(1, −1, z [0] . . . z [3] ) = z [0] . . . z [3]
 176                 ck(i, −1, z [0] . . . z [3] ) = ck(i − 1, i − 2, z [0] . . . z [3] )
 177                 ck(i, j, z [0] . . . z [3] ) =
 178                 ck(i, j − 1, z [0] . . . z [i] ← j . . . z [3] ),  if z [i] = z [j] ;
 179                 ck(i, j − 1, z [0] . . . z [3] ), otherwise
 180
 181         otherwise.
 182 **/
 183
 184 uint64_t check(uint64_t z)
 185 {
 186         //These 64 bits are divided as c = x, y, z [0] , . . . , z [7]
 187
 188         // ck(3, 2, z [0] . . . z [3] )
 189         uint64_t ck1 = ck(3,2, z );
 190
 191         // ck(3, 2, z [4] . . . z [7] )
 192         uint64_t ck2 = ck(3,2, z << 24);
 193         ck1 &= 0x00000000FFFFFF000000;
 194         ck2 &= 0x00000000FFFFFF000000;
 195
 196         return ck1 | ck2 >> 24;
 197
 198 }
 199
 200 void permute(BitstreamIn *p_in, uint64_t z,int l,int r, BitstreamOut* out)
 201 {
 202         if(bitsLeft(p_in) == 0)
 203         {
 204                 return;
 205         }
 206         bool pn = tailBit(p_in);
 207         if( pn ) // pn = 1
 208         {
 209                 uint8_t zl = getSixBitByte(z,l);
 210                 //printf("permute pushing, zl=0x%02x, zl+1=0x%02x\n", zl, zl+1);
 211                 push6bits(out, zl+1);
 212                 permute(p_in, z, l+1,r, out);
 213         }else // otherwise
 214         {
 215                 uint8_t zr = getSixBitByte(z,r);
 216                 //printf("permute pushing, zr=0x%02x\n", zr);
 217                 push6bits(out, zr);
 218                 permute(p_in,z,l,r+1,out);
 219         }
 220 }
 221 void testPermute()
 222 {
 223
 224         uint64_t x = 0;
 225         pushbackSixBitByte(&x,0x00,0);
 226         pushbackSixBitByte(&x,0x01,1);
 227         pushbackSixBitByte(&x,0x02,2);
 228         pushbackSixBitByte(&x,0x03,3);
 229         pushbackSixBitByte(&x,0x04,4);
 230         pushbackSixBitByte(&x,0x05,5);
 231         pushbackSixBitByte(&x,0x06,6);
 232         pushbackSixBitByte(&x,0x07,7);
 233
 234         uint8_t mres[8] = { getSixBitByte(x, 0),
 235                                                 getSixBitByte(x, 1),
 236                                                 getSixBitByte(x, 2),
 237                                                 getSixBitByte(x, 3),
 238                                                 getSixBitByte(x, 4),
 239                                                 getSixBitByte(x, 5),
 240                                                 getSixBitByte(x, 6),
 241                                                 getSixBitByte(x, 7)};
 242         printarr("input_perm", mres,8);
 243
 244         uint8_t p = ~pi[0];
 245         BitstreamIn p_in = { &p, 8,0 };
 246         uint8_t outbuffer[] = {0,0,0,0,0,0,0,0};
 247         BitstreamOut out = {outbuffer,0,0};
 248
 249         permute(&p_in, x,0,4, &out);
 250
 251         uint64_t permuted = bytes_to_num(outbuffer,8);
 252         //printf("zTilde 0x%"PRIX64"\n", zTilde);
 253         permuted >>= 16;
 254
 255         uint8_t res[8] = { getSixBitByte(permuted, 0),
 256                                                 getSixBitByte(permuted, 1),
 257                                                 getSixBitByte(permuted, 2),
 258                                                 getSixBitByte(permuted, 3),
 259                                                 getSixBitByte(permuted, 4),
 260                                                 getSixBitByte(permuted, 5),
 261                                                 getSixBitByte(permuted, 6),
 262                                                 getSixBitByte(permuted, 7)};
 263         printarr("permuted", res, 8);
 264 }
 265 void printbegin()
 266 {
 267         if(! debug_print)
 268                 return;
 269
 270         printf("          | x| y|z0|z1|z2|z3|z4|z5|z6|z7|\n");
 271 }
 272
 273 void printState(char* desc, int x,int y, uint64_t c)
 274 {
 275         if(! debug_print)
 276                 return;
 277
 278         printf("%s : ", desc);
 279         //uint8_t x =   (c & 0xFF00000000000000 ) >> 56;
 280         //uint8_t y =   (c & 0x00FF000000000000 ) >> 48;
 281         printf("  %02x %02x", x,y);
 282         int i ;
 283         for(i =0 ; i < 8 ; i++)
 284         {
 285                 printf(" %02x", getSixBitByte(c,i));
 286         }
 287         printf("\n");
 288 }
 289
 290 /**
 291  * @brief
 292  *Definition 11. Let the function hash0 : F 82 × F 82 × (F 62 ) 8 → (F 82 ) 8 be defined as
 293  *      hash0(x, y, z [0] . . . z [7] ) = k [0] . . . k [7] where
 294  * z'[i] = (z[i] mod (63-i)) + i        i =  0...3
 295  * z'[i+4] = (z[i+4] mod (64-i)) + i    i =  0...3
 296  * ẑ = check(z');
 297  * @param c
 298  * @param k this is where the diversified key is put (should be 8 bytes)
 299  * @return
 300  */
 301 void hash0(uint64_t c, uint8_t *k)
 302 {
 303         printbegin();
 304         //These 64 bits are divided as c = x, y, z [0] , . . . , z [7]
 305         // x = 8 bits
 306         // y = 8 bits
 307         // z0-z7 6 bits each : 48 bits
 308         uint8_t x =     (c & 0xFF00000000000000 ) >> 56;
 309         uint8_t y =     (c & 0x00FF000000000000 ) >> 48;
 310         printState("origin",x,y,c);
 311         int n;
 312         uint8_t zn, zn4, _zn, _zn4;
 313         uint64_t zP = 0;
 314
 315         for(n = 0;  n < 4 ; n++)
 316         {
 317                 zn = getSixBitByte(c,n);
 318                 zn4 = getSixBitByte(c,n+4);
 319
 320                 _zn = (zn % (63-n)) + n;
 321                 _zn4 = (zn4 % (64-n)) + n;
 322
 323                 pushbackSixBitByte(&zP, _zn,n);
 324                 pushbackSixBitByte(&zP, _zn4,n+4);
 325
 326         }
 327         printState("x|y|z'",x,y,zP);
 328
 329         uint64_t zCaret = check(zP);
 330         printState("x|y|z^",x,y,zP);
 331
 332
 333         uint8_t p = pi[x % 35];
 334
 335         if(x & 1) //Check if x7 is 1
 336         {
 337                 p = ~p;
 338         }
 339     printState("p|y|z^",p,y,zP);
 340         //if(debug_print) printf("p:%02x\n", p);
 341
 342         BitstreamIn p_in = { &p, 8,0 };
 343         uint8_t outbuffer[] = {0,0,0,0,0,0,0,0};
 344         BitstreamOut out = {outbuffer,0,0};
 345         permute(&p_in,zCaret,0,4,&out);//returns 48 bits? or 6 8-bytes
 346
 347         //Out is now a buffer containing six-bit bytes, should be 48 bits
 348         // if all went well
 349         //printf("Permute output is %d num bits (48?)\n", out.numbits);
 350         //Shift z-values down onto the lower segment
 351
 352         uint64_t zTilde = bytes_to_num(outbuffer,8);
 353
 354         //printf("zTilde 0x%"PRIX64"\n", zTilde);
 355         zTilde >>= 16;
 356         //printf("z~ 0x%"PRIX64"\n", zTilde);
 357         printState("p|y|z~", p,y,zTilde);
 358
 359         int i;
 360         int zerocounter =0 ;
 361         for(i =0 ; i < 8  ; i++)
 362         {
 363
 364                 // the key on index i is first a bit from y
 365                 // then six bits from z,
 366                 // then a bit from p
 367
 368                 // Init with zeroes
 369                 k[i] = 0;
 370                 // First, place yi leftmost in k
 371                 //k[i] |= (y  << i) & 0x80 ;
 372
 373                 // First, place y(7-i) leftmost in k
 374                 k[i] |= (y  << (7-i)) & 0x80 ;
 375
 376                 //printf("y%d = %d\n",i,(y  << i) & 0x80);
 377
 378                 uint8_t zTilde_i = getSixBitByte(zTilde, i);
 379                 //printf("zTilde_%d 0x%02x (should be <= 0x3F)\n",i, zTilde_i);
 380                 // zTildeI is now on the form 00XXXXXX
 381                 // with one leftshift, it'll be
 382                 // 0XXXXXX0
 383                 // So after leftshift, we can OR it into k
 384                 // However, when doing complement, we need to
 385                 // again MASK 0XXXXXX0 (0x7E)
 386                 zTilde_i <<= 1;
 387
 388                 //Finally, add bit from p or p-mod
 389                 //Shift bit i into rightmost location (mask only after complement)
 390                 uint8_t p_i = p >> i & 0x1;
 391
 392                 if( k[i] )// yi = 1
 393                 {
 394                         //printf("k[%d] +1\n", i);
 395                         k[i] |= ~zTilde_i & 0x7E;
 396                         k[i] |= p_i & 1;
 397                         k[i] += 1;
 398
 399                 }else // otherwise
 400                 {
 401                         k[i] |= zTilde_i & 0x7E;
 402                         k[i] |= (~p_i) & 1;
 403                 }
 404                 if((k[i]  & 1 )== 0)
 405                 {
 406                         zerocounter ++;
 407                 }
 408         }
 409         //printf("zerocounter=%d (should be 4)\n",zerocounter);
 410         //printf("permute fin, y:0x%02x, x: 0x%02x\n", y, x);
 411
 412         //return k;
 413 }
 414
 415 void reorder(uint8_t arr[8])
 416 {
 417         uint8_t tmp[4] = {arr[3],arr[2],arr[1], arr[0]};
 418         arr[0] = arr[7];
 419         arr[1] = arr[6];
 420         arr[2] = arr[5];
 421         arr[3] = arr[4];
 422         arr[4] = tmp[0];//arr[3];
 423         arr[5] = tmp[1];//arr[2];
 424         arr[6] = tmp[2];//arr[3];
 425         arr[7] = tmp[3];//arr[1]
 426 }
 427
 428 //extern void printarr(char * name, uint8_t* arr, int len);
 429
 430 bool des_getParityBitFromKey(uint8_t key)
 431 {//The top 7 bits is used
 432         bool parity = ((key & 0x80) >> 7)
 433                         ^ ((key & 0x40) >> 6) ^ ((key & 0x20) >> 5)
 434                         ^ ((key & 0x10) >> 4) ^ ((key & 0x08) >> 3)
 435                         ^ ((key & 0x04) >> 2) ^ ((key & 0x02) >> 1);
 436         return !parity;
 437 }
 438 void des_checkParity(uint8_t* key)
 439 {
 440         int i;
 441         int fails =0;
 442         for(i =0 ; i < 8 ; i++)
 443         {
 444                 bool parity = des_getParityBitFromKey(key[i]);
 445                 if(parity != (key[i] & 0x1))
 446                 {
 447                         fails++;
 448                         printf("parity1 fail, byte %d [%02x] was %d, should be %d\n",i,key[i],(key[i] & 0x1),parity);
 449                 }
 450         }
 451         if(fails)
 452         {
 453                 printf("parity fails: %d\n", fails);
 454         }else
 455         {
 456                 printf("Key syntax is with parity bits inside each byte\n");
 457         }
 458 }
 459
 460 void printarr2(char * name, uint8_t* arr, int len)
 461 {
 462         int i ;
 463         printf("%s :", name);
 464         for(i =0 ;  i< len ; i++)
 465         {
 466                 printf("%02x",*(arr+i));
 467         }
 468         printf("\n");
 469 }