armsrc/optimized_cipher.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 /**
  40
  41   This file contains an optimized version of the MAC-calculation algorithm. Some measurements on
  42   a std laptop showed it runs in about 1/3 of the time:
  43
  44     Std: 0.428962
  45     Opt: 0.151609
  46
  47   Additionally, it is self-reliant, not requiring e.g. bitstreams from the cipherutils, thus can
  48   be easily dropped into a code base.
  49
  50   The optimizations have been performed in the following steps:
  51   * Parameters passed by reference instead of by value.
  52   * Iteration instead of recursion, un-nesting recursive loops into for-loops.
  53   * Handling of bytes instead of individual bits, for less shuffling and masking
  54   * Less creation of "objects", structs, and instead reuse of alloc:ed memory
  55   * Inlining some functions via #define:s
  56
  57   As a consequence, this implementation is less generic. Also, I haven't bothered documenting this.
  58   For a thorough documentation, check out the MAC-calculation within cipher.c instead.
  59
  60   -- MHS 2015
  61 **/
  62
  63 /**
  64
  65   The runtime of opt_doTagMAC_2() with the MHS optimized version was 403 microseconds on Proxmark3.
  66   This was still to slow for some newer readers which didn't want to wait that long.
  67
  68   Further optimizations to speedup the MAC calculations:
  69   * Optimized opt_Tt logic
  70   * Look up table for opt_select
  71   * Removing many unnecessary bit maskings (& 0x1)
  72   * updating state in place instead of alternating use of a second state structure
  73   * remove the necessity to reverse bits of input and output bytes
  74
  75   opt_doTagMAC_2() now completes in 270 microseconds.
  76
  77   -- piwi 2019
  78 **/
  79
  80 /**
  81   add the possibility to do iCLASS on device only
  82   -- iceman 2020
  83 **/
  84
  85 #include "optimized_cipher.h"
  86 #include "optimized_elite.h"
  87 #include "optimized_ikeys.h"
  88 #include "optimized_cipherutils.h"
  89
  90 static const uint8_t opt_select_LUT[256] = {
  91     00, 03, 02, 01, 02, 03, 00, 01, 04, 07, 07, 04, 06, 07, 05, 04,
  92     01, 02, 03, 00, 02, 03, 00, 01, 05, 06, 06, 05, 06, 07, 05, 04,
  93     06, 05, 04, 07, 04, 05, 06, 07, 06, 05, 05, 06, 04, 05, 07, 06,
  94     07, 04, 05, 06, 04, 05, 06, 07, 07, 04, 04, 07, 04, 05, 07, 06,
  95     06, 05, 04, 07, 04, 05, 06, 07, 02, 01, 01, 02, 00, 01, 03, 02,
  96     03, 00, 01, 02, 00, 01, 02, 03, 07, 04, 04, 07, 04, 05, 07, 06,
  97     00, 03, 02, 01, 02, 03, 00, 01, 00, 03, 03, 00, 02, 03, 01, 00,
  98     05, 06, 07, 04, 06, 07, 04, 05, 05, 06, 06, 05, 06, 07, 05, 04,
  99     02, 01, 00, 03, 00, 01, 02, 03, 06, 05, 05, 06, 04, 05, 07, 06,
 100     03, 00, 01, 02, 00, 01, 02, 03, 07, 04, 04, 07, 04, 05, 07, 06,
 101     02, 01, 00, 03, 00, 01, 02, 03, 02, 01, 01, 02, 00, 01, 03, 02,
 102     03, 00, 01, 02, 00, 01, 02, 03, 03, 00, 00, 03, 00, 01, 03, 02,
 103     04, 07, 06, 05, 06, 07, 04, 05, 00, 03, 03, 00, 02, 03, 01, 00,
 104     01, 02, 03, 00, 02, 03, 00, 01, 05, 06, 06, 05, 06, 07, 05, 04,
 105     04, 07, 06, 05, 06, 07, 04, 05, 04, 07, 07, 04, 06, 07, 05, 04,
 106     01, 02, 03, 00, 02, 03, 00, 01, 01, 02, 02, 01, 02, 03, 01, 00
 107 };
 108
 109 /********************** the table above has been generated with this code: ********
 110 #include "util.h"
 111 static void init_opt_select_LUT(void) {
 112     for (int r = 0; r < 256; r++) {
 113         uint8_t r_ls2 = r << 2;
 114         uint8_t r_and_ls2 = r & r_ls2;
 115         uint8_t r_or_ls2  = r | r_ls2;
 116         uint8_t z0 = (r_and_ls2 >> 5) ^ ((r & ~r_ls2) >> 4) ^ ( r_or_ls2 >> 3);
 117         uint8_t z1 = (r_or_ls2 >> 6) ^ ( r_or_ls2 >> 1) ^ (r >> 5) ^ r;
 118         uint8_t z2 = ((r & ~r_ls2) >> 4) ^ (r_and_ls2 >> 3) ^ r;
 119         opt_select_LUT[r] = (z0 & 4) | (z1 & 2) | (z2 & 1);
 120     }
 121     print_result("", opt_select_LUT, 256);
 122 }
 123 ***********************************************************************************/
 124
 125 #define opt__select(x,y,r)  (4 & (((r & (r << 2)) >> 5) ^ ((r & ~(r << 2)) >> 4) ^ ( (r | r << 2) >> 3)))\
 126     |(2 & (((r | r << 2) >> 6) ^ ( (r | r << 2) >> 1) ^ (r >> 5) ^ r ^ ((x^y) << 1)))\
 127     |(1 & (((r & ~(r << 2)) >> 4) ^ ((r & (r << 2)) >> 3) ^ r ^ x))
 128
 129 /*
 130  * Some background on the expression above can be found here...
 131 uint8_t xopt__select(bool x, bool y, uint8_t r)
 132 {
 133
 134     //r:      r0 r1 r2 r3 r4 r5 r6 r7
 135     //r_ls2:  r2 r3 r4 r5 r6 r7  0  0
 136     //                       z0
 137     //                          z1
 138
 139 //  uint8_t z0 = (r0 & r2) ^ (r1 & ~r3) ^ (r2 | r4); // <-- original
 140     uint8_t z0 = (r_and_ls2 >> 5) ^ ((r & ~r_ls2) >> 4) ^ ( r_or_ls2 >> 3);
 141
 142 //  uint8_t z1 = (r0 | r2) ^ ( r5 | r7) ^ r1 ^ r6 ^ x ^ y;  // <-- original
 143     uint8_t z1 = (r_or_ls2 >> 6) ^ ( r_or_ls2 >> 1) ^ (r >> 5) ^ r ^ ((x^y) << 1);
 144
 145 //  uint8_t z2 = (r3 & ~r5) ^ (r4 & r6 ) ^ r7 ^ x;  // <-- original
 146     uint8_t z2 = ((r & ~r_ls2) >> 4) ^ (r_and_ls2 >> 3) ^ r ^ x;
 147
 148     return (z0 & 4) | (z1 & 2) | (z2 & 1);
 149 }
 150 */
 151
 152 static void opt_successor(const uint8_t *k, State *s, uint8_t y) {
 153 // #define opt_T(s) (0x1 & ((s->t >> 15) ^ (s->t >> 14) ^ (s->t >> 10) ^ (s->t >> 8) ^ (s->t >> 5) ^ (s->t >> 4)^ (s->t >> 1) ^ s->t))
 154     // uint8_t Tt = opt_T(s);
 155     uint16_t Tt = s->t & 0xc533;
 156     Tt = Tt ^ (Tt >> 1);
 157     Tt = Tt ^ (Tt >> 4);
 158     Tt = Tt ^ (Tt >> 10);
 159     Tt = Tt ^ (Tt >> 8);
 160
 161     s->t = (s->t >> 1);
 162     s->t |= (Tt ^ (s->r >> 7) ^ (s->r >> 3)) << 15;
 163
 164     uint8_t opt_B = s->b;
 165     opt_B ^= s->b >> 6;
 166     opt_B ^= s->b >> 5;
 167     opt_B ^= s->b >> 4;
 168
 169     s->b = s->b >> 1;
 170     s->b |= (opt_B ^ s->r) << 7;
 171
 172     uint8_t opt_select = opt_select_LUT[s->r] & 0x04;
 173     opt_select |= (opt_select_LUT[s->r] ^ ((Tt ^ y) << 1)) & 0x02;
 174     opt_select |= (opt_select_LUT[s->r] ^ Tt) & 0x01;
 175
 176     uint8_t r = s->r;
 177     s->r = (k[opt_select] ^ s->b) + s->l ;
 178     s->l = s->r + r;
 179 }
 180
 181 static void opt_suc(const uint8_t *k, State *s, uint8_t *in, uint8_t length, bool add32Zeroes) {
 182     for (int i = 0; i < length; i++) {
 183         uint8_t head;
 184         head = in[i];
 185         opt_successor(k, s, head);
 186
 187         head >>= 1;
 188         opt_successor(k, s, head);
 189
 190         head >>= 1;
 191         opt_successor(k, s, head);
 192
 193         head >>= 1;
 194         opt_successor(k, s, head);
 195
 196         head >>= 1;
 197         opt_successor(k, s, head);
 198
 199         head >>= 1;
 200         opt_successor(k, s, head);
 201
 202         head >>= 1;
 203         opt_successor(k, s, head);
 204
 205         head >>= 1;
 206         opt_successor(k, s, head);
 207     }
 208     //For tag MAC, an additional 32 zeroes
 209     if (add32Zeroes) {
 210         for (int i = 0; i < 16; i++) {
 211             opt_successor(k, s, 0);
 212             opt_successor(k, s, 0);
 213         }
 214     }
 215 }
 216
 217 static void opt_output(const uint8_t *k, State *s,  uint8_t *buffer) {
 218     for (uint8_t times = 0; times < 4; times++) {
 219         uint8_t bout = 0;
 220         bout |= (s->r & 0x4) >> 2;
 221         opt_successor(k, s, 0);
 222         bout |= (s->r & 0x4) >> 1;
 223         opt_successor(k, s, 0);
 224         bout |= (s->r & 0x4);
 225         opt_successor(k, s, 0);
 226         bout |= (s->r & 0x4) << 1;
 227         opt_successor(k, s, 0);
 228         bout |= (s->r & 0x4) << 2;
 229         opt_successor(k, s, 0);
 230         bout |= (s->r & 0x4) << 3;
 231         opt_successor(k, s, 0);
 232         bout |= (s->r & 0x4) << 4;
 233         opt_successor(k, s, 0);
 234         bout |= (s->r & 0x4) << 5;
 235         opt_successor(k, s, 0);
 236         buffer[times] = bout;
 237     }
 238 }
 239
 240 static void opt_MAC(uint8_t *k, uint8_t *input, uint8_t *out) {
 241     State _init  =  {
 242         ((k[0] ^ 0x4c) + 0xEC) & 0xFF,// l
 243         ((k[0] ^ 0x4c) + 0x21) & 0xFF,// r
 244         0x4c, // b
 245         0xE012 // t
 246     };
 247
 248     opt_suc(k, &_init, input, 12, false);
 249     opt_output(k, &_init, out);
 250 }
 251
 252 static void opt_MAC_N(uint8_t *k, uint8_t *input, uint8_t in_size, uint8_t *out) {
 253     State _init  =  {
 254         ((k[0] ^ 0x4c) + 0xEC) & 0xFF,// l
 255         ((k[0] ^ 0x4c) + 0x21) & 0xFF,// r
 256         0x4c, // b
 257         0xE012 // t
 258     };
 259
 260     opt_suc(k, &_init, input, in_size, false);
 261     opt_output(k, &_init, out);
 262 }
 263
 264 void opt_doReaderMAC(uint8_t *cc_nr_p, uint8_t *div_key_p, uint8_t mac[4]) {
 265     uint8_t dest [] = {0, 0, 0, 0, 0, 0, 0, 0};
 266     opt_MAC(div_key_p, cc_nr_p, dest);
 267     memcpy(mac, dest, 4);
 268 }
 269
 270 void opt_doReaderMAC_2(State _init,  uint8_t *nr, uint8_t mac[4], const uint8_t *div_key_p) {
 271     opt_suc(div_key_p, &_init, nr, 4, false);
 272     opt_output(div_key_p, &_init, mac);
 273 }
 274
 275
 276 void doMAC_N(uint8_t *in_p, uint8_t in_size, uint8_t *div_key_p, uint8_t mac[4]) {
 277     uint8_t dest [] = {0, 0, 0, 0, 0, 0, 0, 0};
 278     opt_MAC_N(div_key_p, in_p, in_size, dest);
 279     memcpy(mac, dest, 4);
 280 }
 281
 282 void opt_doTagMAC(uint8_t *cc_p, const uint8_t *div_key_p, uint8_t mac[4]) {
 283     State _init  =  {
 284         ((div_key_p[0] ^ 0x4c) + 0xEC) & 0xFF,// l
 285         ((div_key_p[0] ^ 0x4c) + 0x21) & 0xFF,// r
 286         0x4c, // b
 287         0xE012 // t
 288     };
 289     opt_suc(div_key_p, &_init, cc_p, 12, true);
 290     opt_output(div_key_p, &_init, mac);
 291 }
 292
 293 /**
 294  * The tag MAC can be divided (both can, but no point in dividing the reader mac) into
 295  * two functions, since the first 8 bytes are known, we can pre-calculate the state
 296  * reached after feeding CC to the cipher.
 297  * @param cc_p
 298  * @param div_key_p
 299  * @return the cipher state
 300  */
 301 State opt_doTagMAC_1(uint8_t *cc_p, const uint8_t *div_key_p) {
 302     State _init  =  {
 303         ((div_key_p[0] ^ 0x4c) + 0xEC) & 0xFF,// l
 304         ((div_key_p[0] ^ 0x4c) + 0x21) & 0xFF,// r
 305         0x4c, // b
 306         0xE012 // t
 307     };
 308     opt_suc(div_key_p, &_init, cc_p, 8, false);
 309     return _init;
 310 }
 311
 312 /**
 313  * The second part of the tag MAC calculation, since the CC is already calculated into the state,
 314  * this function is fed only the NR, and internally feeds the remaining 32 0-bits to generate the tag
 315  * MAC response.
 316  * @param _init - precalculated cipher state
 317  * @param nr - the reader challenge
 318  * @param mac - where to store the MAC
 319  * @param div_key_p - the key to use
 320  */
 321 void opt_doTagMAC_2(State _init,  uint8_t *nr, uint8_t mac[4], const uint8_t *div_key_p) {
 322     opt_suc(div_key_p, &_init, nr, 4, true);
 323     opt_output(div_key_p, &_init, mac);
 324 }
 325
 326
 327 void iclass_calc_div_key(uint8_t *csn, uint8_t *key, uint8_t *div_key, bool elite) {
 328     if (elite) {
 329         uint8_t keytable[128] = {0};
 330         uint8_t key_index[8] = {0};
 331         uint8_t key_sel[8] = { 0 };
 332         uint8_t key_sel_p[8] = { 0 };
 333         hash2(key, keytable);
 334         hash1(csn, key_index);
 335         for (uint8_t i = 0; i < 8 ; i++)
 336             key_sel[i] = keytable[key_index[i]];
 337
 338         //Permute from iclass format to standard format
 339         permutekey_rev(key_sel, key_sel_p);
 340         diversifyKey(csn, key_sel_p, div_key);
 341     } else {
 342         diversifyKey(csn, key, div_key);
 343     }
 344 }