tools/cryptorf/sma.cpp

   1 /*
   2  *
   3  * SecureMemory recovery
   4  *
   5  * Copyright (C) 2010, Flavio D. Garcia, Peter van Rossum, Roel Verdult
   6  * and Ronny Wichers Schreur. Radboud University Nijmegen
   7  *
   8  * This program is free software: you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation, either version 3 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20  *
  21  * Modified Iceman, 2020
  22  */
  23
  24 #include <stdio.h>
  25 #include <time.h>
  26 #include <string.h>
  27 #include <inttypes.h>
  28 #include <iostream>
  29 #include <vector>
  30 #include <map>
  31 #include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound
  32 #include <functional> // greater, bind2nd
  33 #include "cryptolib.h"
  34 #include "util.h"
  35
  36 #ifdef __cplusplus
  37 extern "C" {
  38 #endif
  39
  40 using namespace std;
  41
  42 #ifdef _MSC_VER
  43 // avoid scanf warnings in Visual Studio
  44 #define _CRT_SECURE_NO_WARNINGS
  45 #define _CRT_SECURE_NO_DEPRECATE
  46 #define inline __inline
  47 #endif
  48
  49 /*
  50 >./sm 4f794a463ff81d81 ffffffffffffffff 1234567812345678
  51 SecureMemory simulator - (c) Radboud University Nijmegen
  52
  53 Authenticate
  54   Gc: 4f 79 4a 46 3f f8 1d 81
  55   Ci: ff ff ff ff ff ff ff ff
  56    Q: 12 34 56 78 12 34 56 78
  57   Ch: 88 c9 d4 46 6a 50 1a 87
  58 Ci+1: de c2 ee 1b 1c 92 76 e9
  59
  60   Ks: de 88 c2 c9 ee d4 1b 46 1c 6a 92 50 76 1a e9 87
  61
  62    left: 1ddeac626
  63   right: 19aba45
  64
  65   left-candidates bins:
  66   004df8a64 (74)
  67   0059ff7d5 (81)
  68   00d2ff4ed (80)
  69   032df8b12 (78)
  70   0337b8b7d (87)
  71   036f7b607 (77)
  72   03a6f882a (79)
  73   03b2ff59b (76)
  74   04445c715 (74)
  75   0452175be (80)
  76   0b29f2a5b (78)
  77   0f6c834fb (76)
  78   0f78aac5b (75)
  79   0f79c8d49 (78)
  80   109691f61 (70)
  81   159d1687e (86)
  82   176e73456 (77)
  83   1ddeac626 (92)
  84   1facee6e5 (78)
  85   2049ed469 (80)
  86   205078bba (74)
  87   31c277406 (81)
  88   31c2777e6 (81)
  89   3770cdaf3 (74)
  90   48916e84e (77)
  91   4ba9b6520 (78)
  92   4ba9b653f (78)
  93   4c51c6463 (82)
  94   4c9432733 (76)
  95   4e3d88819 (81)
  96   4e3d88bf9 (81)
  97   51c8755b5 (76)
  98   5b2aeb858 (76)
  99   5fb612b96 (80)
 100   60531191a (78)
 101   6221539d9 (92)
 102   68918cba9 (79)
 103   6c9a11672 (78)
 104   6f696e09e (70)
 105   7086372b6 (78)
 106   7bade8a41 (82)
 107   7c90849f8 (77)
 108   7cc847482 (87)
 109
 110
 111 const uint64_t left_candidates[43] = {
 112     0x6221539d9ull, 0x1ddeac626ull, 0x7cc847482ull, 0x0337b8b7dull,
 113     0x159d1687eull, 0x7bade8a41ull, 0x4c51c6463ull, 0x4e3d88bf9ull,
 114     0x4e3d88819ull, 0x31c2777e6ull, 0x31c277406ull, 0x0059ff7d5ull,
 115     0x5fb612b96ull, 0x2049ed469ull, 0x0452175beull, 0x00d2ff4edull,
 116     0x68918cba9ull, 0x03a6f882aull, 0x7086372b6ull, 0x6c9a11672ull,
 117     0x60531191aull, 0x4ba9b653full, 0x4ba9b6520ull, 0x1facee6e5ull,
 118     0x0f79c8d49ull, 0x0b29f2a5bull, 0x032df8b12ull, 0x7c90849f8ull,
 119     0x48916e84eull, 0x176e73456ull, 0x036f7b607ull, 0x5b2aeb858ull,
 120     0x51c8755b5ull, 0x4c9432733ull, 0x0f6c834fbull, 0x03b2ff59bull,
 121     0x0f78aac5bull, 0x3770cdaf3ull, 0x205078bbaull, 0x04445c715ull,
 122     0x004df8a64ull, 0x6f696e09eull, 0x109691f61ull
 123 };
 124 */
 125
 126 typedef struct {
 127     uint64_t l;
 128     uint64_t m;
 129     uint64_t r;
 130     nibble b0;
 131     nibble b1;
 132     nibble b1l;
 133     nibble b1r;
 134     nibble b1s;
 135     bool invalid;
 136     uint8_t Gc[8];
 137 } cs_t;
 138 typedef cs_t *pcs;
 139
 140 typedef struct {
 141     uint8_t addition;
 142     uint8_t out;
 143 } lookup_entry;
 144
 145 enum cipher_state_side {
 146     CSS_LEFT,
 147     CSS_RIGHT
 148 };
 149
 150 void print_cs(const char *text, pcs s) {
 151     int pos;
 152
 153     printf("%s", text);
 154     for (pos = 6; pos >= 0; pos--)
 155         printf(" %02x", (uint8_t)(s->l >> (pos * 5)) & 0x1f);
 156     printf(" |");
 157     for (pos = 6; pos >= 0; pos--)
 158         printf(" %02x", (uint8_t)(s->m >> (pos * 7)) & 0x7f);
 159     printf(" |");
 160     for (pos = 4; pos >= 0; pos--)
 161         printf(" %02x", (uint8_t)(s->r >> (pos * 5)) & 0x1f);
 162
 163     printf("\n");
 164 }
 165
 166 static inline uint8_t mod(uint8_t a, uint8_t m) {
 167     if (m == 0) {
 168         return 0; // Actually, divide by zero error
 169     }
 170
 171     // Just return the input when this is less or equal than the modular value
 172     if (a < m) return a;
 173
 174     // Compute the modular value
 175     a %= m;
 176
 177     // Return the funny value, when the output was now zero, return the modular value
 178     return (a == 0) ? m : a;
 179 }
 180
 181 static inline uint8_t bit_rotate_l(uint8_t a, uint8_t n_bits) {
 182     // Rotate value a with the length of n_bits only 1 time
 183     uint8_t mask = (1 << n_bits) - 1;
 184     return ((a << 1) | (a >> (n_bits - 1))) & mask;
 185 }
 186
 187 static inline uint8_t bit_rotate_r(uint8_t a, uint8_t n_bits) {
 188     return ((a >> 1) | ((a & 1) << (n_bits - 1)));
 189 }
 190
 191 static uint8_t lookup_left_subtraction[0x400];
 192 static uint8_t lookup_right_subtraction[0x400];
 193 static lookup_entry lookup_left[0x100000];
 194 static lookup_entry lookup_right[0x8000];
 195 static uint8_t left_addition[0x100000];
 196
 197 static inline void init_lookup_left() {
 198     for (int i = 0; i < 0x400; i++) {
 199         int b6 = i & 0x1f;
 200         int b3 = (i >> 5) & 0x1f;
 201         int index = (b3 << 15) | b6;
 202         b6 = bit_rotate_l(b6, 5);
 203
 204         int temp = mod(b3 + b6, 0x1f);
 205         left_addition[index] = temp;
 206         lookup_left[index].addition = temp;
 207         lookup_left[index].out = ((temp ^ b3) & 0x0f);
 208     }
 209 }
 210
 211 static inline void init_lookup_right() {
 212     for (int i = 0; i < 0x400; i++) {
 213         int b18 = i & 0x1f;
 214         int b16 = (i >> 5) & 0x1f;
 215         int index = (b16 << 10) | b18;
 216
 217         int temp = mod(b18 + b16, 0x1f);
 218         lookup_right[index].addition = temp;
 219         lookup_right[index].out = ((temp ^ b16) & 0x0f);
 220     }
 221 }
 222
 223 static void init_lookup_left_subtraction() {
 224     for (int index = 0; index < 0x400 ; index++) {
 225         uint8_t b3 = (index >> 5 & 0x1f);
 226         uint8_t bx = (index & 0x1f);
 227         lookup_left_subtraction[index] = bit_rotate_r(mod((bx + 0x1f) - b3, 0x1f), 5);
 228     }
 229 }
 230
 231 static void init_lookup_right_subtraction() {
 232     for (int index = 0; index < 0x400 ; index++) {
 233         int b16 = (index >> 5);
 234         uint8_t bx = (index & 0x1f);
 235         lookup_right_subtraction[index] = mod((bx + 0x1f) - b16, 0x1f);
 236     }
 237 }
 238
 239 static inline void previous_left(uint8_t in, vector<cs_t> *candidate_states) {
 240     pcs state;
 241     size_t size = candidate_states->size();
 242     for (size_t pos = 0; pos < size; pos++) {
 243         state = &((*candidate_states)[pos]);
 244
 245         uint8_t bx = (uint8_t)((state->l >> 30) & 0x1f);
 246         unsigned b3 = (unsigned)(state->l >> 5) & 0x3e0;
 247         state->l = (state->l << 5);
 248
 249         //Ignore impossible states
 250         if (bx == 0) {
 251             // Are we dealing with an impossible state?
 252             if (b3 != 0) {
 253                 state->invalid = true;
 254             } else {
 255                 // We only need to consider b6=0
 256                 state->l &= 0x7ffffffe0ull;
 257                 state->l ^= (((uint64_t)in & 0x1f) << 20);
 258             }
 259         } else {
 260             uint8_t b6 = lookup_left_subtraction[b3 | bx];
 261             state->l = (state->l & 0x7ffffffe0ull) | b6;
 262             state->l ^= (((uint64_t)in & 0x1f) << 20);
 263
 264             // Check if we have a second candidate
 265             if (b6 == 0x1f) {
 266                 cs_t nstate = *state;
 267                 nstate.l &= 0x7ffffffe0ull;
 268                 candidate_states->push_back(nstate);
 269             }
 270         }
 271     }
 272 }
 273
 274 static inline void previous_right(uint8_t in, vector<cs_t> *candidate_states) {
 275     pcs state;
 276     size_t size = candidate_states->size();
 277     for (size_t pos = 0; pos < size; pos++) {
 278         state = &((*candidate_states)[pos]);
 279
 280         uint8_t bx = (uint8_t)((state->r >> 20) & 0x1f);
 281         unsigned b16 = (unsigned)(state->r & 0x3e0);//(state->buffer_r >> 10) & 0x1f;
 282
 283         state->r = (state->r << 5);
 284
 285         // Ignore impossible states
 286         if (bx == 0) {
 287             if (b16 != 0) {
 288                 state->invalid = true;
 289             } else {
 290                 // We only need to consider b18=0
 291                 state->r &= 0x1ffffe0ull;
 292                 state->r ^= (((uint64_t)in & 0xf8) << 12);
 293             }
 294         } else {
 295             uint8_t b18 = lookup_right_subtraction[b16 | bx];
 296             state->r = (state->r & 0x1ffffe0ull) | b18;
 297             state->r ^= (((uint64_t)in & 0xf8) << 12);
 298             //state->b_right  = ((b14^b17) & 0x0f);
 299
 300             // Check if we have a second candidate
 301             if (b18 == 0x1f) {
 302                 cs_t nstate = *state;
 303                 nstate.r &= 0x1ffffe0ull;
 304                 candidate_states->push_back(nstate);
 305             }
 306         }
 307     }
 308 }
 309
 310 static inline uint8_t next_left_fast(uint8_t in, uint64_t *left) {
 311     if (in) *left ^= ((in & 0x1f) << 20);
 312     lookup_entry *lookup = &(lookup_left[((*left) & 0xf801f)]);
 313     *left = (((*left) >> 5) | ((uint64_t)lookup->addition << 30));
 314     return lookup->out;
 315 }
 316
 317 /*
 318 static inline uint8_t next_left_ksbyte(uint64_t *left) {
 319     lookup_entry *lookup;
 320     uint8_t bt;
 321
 322     *left = (((*left) >> 5) | ((uint64_t)left_addition[((*left) & 0xf801f)] << 30));
 323     lookup = &(lookup_left[((*left) & 0xf801f)]);
 324     *left = (((*left) >> 5) | ((uint64_t)lookup->addition << 30));
 325     bt = lookup->out << 4;
 326     *left = (((*left) >> 5) | ((uint64_t)left_addition[((*left) & 0xf801f)] << 30));
 327     lookup = &(lookup_left[((*left) & 0xf801f)]);
 328     *left = (((*left) >> 5) | ((uint64_t)lookup->addition << 30));
 329     bt |= lookup->out;
 330     return bt;
 331 }
 332 */
 333
 334 static inline uint8_t next_right_fast(uint8_t in, uint64_t *right) {
 335     if (in) *right ^= ((in & 0xf8) << 12);
 336     lookup_entry *lookup = &(lookup_right[((*right) & 0x7c1f)]);
 337     *right = (((*right) >> 5) | (lookup->addition << 20));
 338     return lookup->out;
 339 }
 340
 341 static inline void sm_left_mask(const uint8_t *ks, uint8_t *mask, uint64_t rstate) {
 342     size_t pos;
 343
 344     for (pos = 0; pos < 16; pos++) {
 345         next_right_fast(0, &rstate);
 346         uint8_t bt = next_right_fast(0, &rstate) << 4;
 347         next_right_fast(0, &rstate);
 348         bt |= next_right_fast(0, &rstate);
 349
 350         // xor the bits with the keystream and count the "correct" bits
 351         bt ^= ks[pos];
 352
 353         // Save the mask for the left produced bits
 354         mask[pos] = bt;
 355     }
 356 }
 357
 358 static inline uint32_t sm_right(const uint8_t *ks, uint8_t *mask, vector<uint64_t> *pcrstates) {
 359     uint8_t tmp_mask[16];
 360     size_t pos, bit, topbits;
 361     uint64_t rstate, counter;
 362     map<uint64_t, uint64_t> bincstates;
 363     map<uint64_t, uint64_t>::iterator it;
 364     uint8_t bt;
 365
 366     topbits = 0;
 367     for (counter = 0; counter < 0x2000000; counter++) {
 368         // Reset the current bitcount of correct bits
 369         size_t bits = 0;
 370
 371         // Copy the state we are going to test
 372         rstate = counter;
 373
 374         for (pos = 0; pos < 16; pos++) {
 375             next_right_fast(0, &rstate);
 376             bt = next_right_fast(0, &rstate) << 4;
 377             next_right_fast(0, &rstate);
 378             bt |= next_right_fast(0, &rstate);
 379
 380             // xor the bits with the keystream and count the "correct" bits
 381             bt ^= ks[pos];
 382
 383             // Save the mask for the left produced bits
 384             tmp_mask[pos] = bt;
 385
 386             for (bit = 0; bit < 8; bit++) {
 387                 // When the bit is xored away (=zero), it was the same, so correct ;)
 388                 if ((bt & 0x01) == 0) bits++;
 389                 bt >>= 1;
 390             }
 391         }
 392
 393         if (bits > topbits) {
 394             topbits = bits;
 395             // Copy the winning mask
 396             memcpy(mask, tmp_mask, 16);
 397         }
 398
 399         // Ignore states under 90
 400         if (bits >= 90) {
 401             //  Make sure the bits are used for ordering
 402             bincstates[(((uint64_t)bits) << 56) | counter] = counter;
 403         }
 404
 405         if ((counter & 0xfffff) == 0) {
 406             printf(".");
 407             fflush(stdout);
 408         }
 409     }
 410     printf("\n");
 411
 412     // Clear the candidate state vector
 413     pcrstates->clear();
 414
 415     // Copy the order the states from lowest-bin to highest-bin
 416     for (it = bincstates.begin(); it != bincstates.end(); ++it) {
 417         pcrstates->push_back(it->second);
 418     }
 419     // Reverse the vector order (so the highest bin comes first)
 420     reverse(pcrstates->begin(), pcrstates->end());
 421
 422     return topbits;
 423 }
 424
 425 static inline void previous_all_input(vector<cs_t> *pcstates, uint32_t gc_byte_index, cipher_state_side css) {
 426     uint8_t btGc, in;
 427     vector<cs_t> ncstates;
 428     vector<cs_t> prev_ncstates;
 429     vector<cs_t>::iterator itnew;
 430
 431     // Loop through the complete entryphy of 5 bits for each candidate
 432     // We ignore zero (xor 0x00) to avoid duplicates
 433     for (btGc = 0; btGc < 0x20; btGc++) {
 434         // Copy the original candidates that are supplied
 435         ncstates = *pcstates;
 436
 437         // Rollback the (candidate) cipher states with this input
 438         if (css == CSS_RIGHT) {
 439             in = btGc << 3;
 440             previous_right(in, &ncstates);
 441         } else {
 442             in = btGc;
 443             previous_left(in, &ncstates);
 444         }
 445
 446         for (itnew = ncstates.begin(); itnew != ncstates.end(); ++itnew) {
 447             // Wipe away the invalid states
 448             if (itnew->invalid == false) {
 449                 itnew->Gc[gc_byte_index] = in;
 450                 prev_ncstates.push_back(*itnew);
 451             }
 452         }
 453     }
 454
 455     // Copy the previous states into the vector
 456     *pcstates = prev_ncstates;
 457 }
 458
 459 static inline void search_gc_candidates_right(const uint64_t rstate_before_gc, const uint64_t rstate_after_gc, const uint8_t *Q, vector<cs_t> *pcstates) {
 460     vector<cs_t>::iterator it;
 461     vector<cs_t> csl_cand;
 462     map<uint64_t, uint64_t> matchbox;
 463     map<uint64_t, uint64_t>::iterator itmatch;
 464     uint64_t rstate;
 465     size_t counter;
 466     cs_t state;
 467
 468     // Generate 2^20 different (5 bits) values for the first 4 Gc bytes (0,1,2,3)
 469     for (counter = 0; counter < 0x100000; counter++) {
 470         rstate  = rstate_before_gc;
 471         next_right_fast((counter >> 12) & 0xf8, &rstate);
 472         next_right_fast((counter >> 7)  & 0xf8, &rstate);
 473         next_right_fast(Q[4], &rstate);
 474         next_right_fast((counter >> 2) & 0xf8, &rstate);
 475         next_right_fast((counter << 3) & 0xf8, &rstate);
 476         next_right_fast(Q[5], &rstate);
 477         matchbox[rstate] = counter;
 478     }
 479
 480     // Reset and initialize the cryptostate and vecctor
 481     memset(&state, 0x00, sizeof(cs_t));
 482     state.invalid = false;
 483     state.r = rstate_after_gc;
 484     csl_cand.clear();
 485     csl_cand.push_back(state);
 486
 487     // Generate 2^20(+splitting) different (5 bits) values for the last 4 Gc bytes (4,5,6,7)
 488     previous_right(Q[7], &csl_cand);
 489     previous_all_input(&csl_cand, 7, CSS_RIGHT);
 490     previous_all_input(&csl_cand, 6, CSS_RIGHT);
 491     previous_right(Q[6], &csl_cand);
 492     previous_all_input(&csl_cand, 5, CSS_RIGHT);
 493     previous_all_input(&csl_cand, 4, CSS_RIGHT);
 494
 495     pcstates->clear();
 496
 497     // Take the intersection of the corresponding states ~2^15 values (40-25 = 15 bits)
 498     for (it = csl_cand.begin(); it != csl_cand.end(); ++it) {
 499         itmatch = matchbox.find(it->r);
 500         if (itmatch != matchbox.end()) {
 501             it->Gc[0] = (itmatch->second >> 12) & 0xf8;
 502             it->Gc[1] = (itmatch->second >>  7) & 0xf8;
 503             it->Gc[2] = (itmatch->second >>  2) & 0xf8;
 504             it->Gc[3] = (itmatch->second <<  3) & 0xf8;
 505             /*
 506              printf("%07llx ",it->r);
 507              printf("(%x)\n",itmatch->second);
 508              */
 509             /*
 510                   if (it->r == 0xff459b)
 511                   {
 512                     print_cs("previous:",&(*it));
 513                     printf("%07llx\n",it->r);
 514                     print_bytes(it->Gc,8);
 515                   }
 516             */
 517             pcstates->push_back(*it);
 518         }
 519     }
 520 }
 521
 522 static inline void sm_left(const uint8_t *ks, const uint8_t *mask, vector<cs_t> *pcstates) {
 523     map<uint64_t, cs_t> bincstates;
 524     map<uint64_t, cs_t>::iterator it;
 525     uint64_t counter;
 526     size_t pos, bits, bit;
 527     uint8_t correct_bits[16];
 528     uint8_t bt;
 529     cs_t state;
 530     lookup_entry *lookup;
 531
 532     // Reset and initialize the cryptostate and vecctor
 533     memset(&state, 0x00, sizeof(cs_t));
 534     state.invalid = false;
 535
 536     for (counter = 0; counter < 0x800000000ull; counter++) {
 537         uint64_t lstate = counter;
 538
 539         for (pos = 0; pos < 16; pos++) {
 540             lstate = (((lstate) >> 5) | ((uint64_t)left_addition[((lstate) & 0xf801f)] << 30));
 541             lookup = &(lookup_left[((lstate) & 0xf801f)]);
 542             lstate = (((lstate) >> 5) | ((uint64_t)lookup->addition << 30));
 543             bt = lookup->out << 4;
 544             lstate = (((lstate) >> 5) | ((uint64_t)left_addition[((lstate) & 0xf801f)] << 30));
 545             lookup = &(lookup_left[((lstate) & 0xf801f)]);
 546             lstate = (((lstate) >> 5) | ((uint64_t)lookup->addition << 30));
 547             bt |= lookup->out;
 548
 549             // xor the bits with the keystream and count the "correct" bits
 550             bt ^= ks[pos];
 551
 552             // When the REQUIRED bits are NOT xored away (=zero), ignore this wrong state
 553             if ((bt & mask[pos]) != 0) break;
 554
 555             // Save the correct bits for statistical information
 556             correct_bits[pos] = bt;
 557         }
 558
 559         // If we have parsed all 16 bytes of keystream, we have a valid CANDIDATE!
 560         if (pos == 16) {
 561             // Count the total correct bits
 562             bits = 0;
 563             for (pos = 0; pos < 16; pos++) {
 564                 // Get the next byte-value with correct bits
 565                 bt = correct_bits[pos];
 566
 567                 // Count all the (correct) bits
 568                 for (bit = 0; bit < 8; bit++) {
 569                     // When the bit is xored away (=zero), it was the same, so correct ;)
 570                     if ((bt & 0x01) == 0) bits++;
 571                     bt >>= 1;
 572                 }
 573             }
 574
 575             // Print the left candidate
 576 //      printf("%09llx (%d)\n",counter,bits);
 577             printf(".");
 578             fflush(stdout);
 579
 580             state.l = counter;
 581             //  Make sure the bits are used for ordering
 582             bincstates[(((uint64_t)bits) << 56) | counter] = state;
 583         }
 584
 585         if ((counter & 0xffffffffull) == 0) {
 586             printf("%02.1f%%.", ((float)100 / 8) * (counter >> 32));
 587             fflush(stdout);
 588         }
 589     }
 590     printf("100%%\n");
 591
 592     // Clear the candidate state vector
 593     pcstates->clear();
 594
 595     // Copy the order the states from lowest-bin to highest-bin
 596     for (it = bincstates.begin(); it != bincstates.end(); ++it) {
 597         pcstates->push_back(it->second);
 598     }
 599     // Reverse the vector order (so the highest bin comes first)
 600     reverse(pcstates->begin(), pcstates->end());
 601 }
 602
 603 static inline void search_gc_candidates_left(const uint64_t lstate_before_gc, const uint8_t *Q, vector<cs_t> *pcstates) {
 604     vector<cs_t> csl_cand, csl_search;
 605     vector<cs_t>::iterator itsearch, itcand;
 606     map<uint64_t, uint64_t> matchbox;
 607     map<uint64_t, uint64_t>::iterator itmatch;
 608     uint64_t lstate;
 609     size_t counter;
 610
 611     // Generate 2^20 different (5 bits) values for the first 4 Gc bytes (0,1,2,3)
 612     for (counter = 0; counter < 0x100000; counter++) {
 613         lstate  = lstate_before_gc;
 614         next_left_fast((counter >> 15) & 0x1f, &lstate);
 615         next_left_fast((counter >> 10) & 0x1f, &lstate);
 616         next_left_fast(Q[4], &lstate);
 617         next_left_fast((counter >> 5) & 0x1f, &lstate);
 618         next_left_fast(counter & 0x1f, &lstate);
 619         next_left_fast(Q[5], &lstate);
 620         matchbox[lstate] = counter;
 621     }
 622
 623     // Copy the input candidate states and clean the output vector
 624     csl_cand = *pcstates;
 625     pcstates->clear();
 626
 627     for (itcand = csl_cand.begin(); itcand != csl_cand.end(); ++itcand) {
 628         csl_search.clear();
 629         csl_search.push_back(*itcand);
 630
 631         // Generate 2^20(+splitting) different (5 bits) values for the last 4 Gc bytes (4,5,6,7)
 632         previous_left(Q[7], &csl_search);
 633         previous_all_input(&csl_search, 7, CSS_LEFT);
 634         previous_all_input(&csl_search, 6, CSS_LEFT);
 635         previous_left(Q[6], &csl_search);
 636         previous_all_input(&csl_search, 5, CSS_LEFT);
 637         previous_all_input(&csl_search, 4, CSS_LEFT);
 638
 639         // Take the intersection of the corresponding states ~2^15 values (40-25 = 15 bits)
 640         for (itsearch = csl_search.begin(); itsearch != csl_search.end(); ++itsearch) {
 641             itmatch = matchbox.find(itsearch->l);
 642             if (itmatch != matchbox.end()) {
 643                 itsearch->Gc[0] = (itmatch->second >> 15) & 0x1f;
 644                 itsearch->Gc[1] = (itmatch->second >> 10) & 0x1f;
 645                 itsearch->Gc[2] = (itmatch->second >>  5) & 0x1f;
 646                 itsearch->Gc[3] = itmatch->second & 0x1f;
 647
 648                 /*
 649                  printf("%07llx ",it->l);
 650                  printf("(%x) ",itmatch->second);
 651                  print_cs("",&(*it));
 652                  */
 653                 /*
 654                         if (itsearch->l == 0x405162420ull)
 655                         {
 656                           print_cs("previous:",&(*itsearch));
 657                           printf("%09llx\n",itsearch->l);
 658                           print_bytes(itsearch->Gc,8);
 659                         }
 660                         count++;
 661                 */
 662                 pcstates->push_back(*itsearch);
 663             }
 664         }
 665 //    printf("%09llx: ",itcand->l);
 666 //    printf("%d - %d\n",csl_search.size(),count);
 667         printf(".");
 668         fflush(stdout);
 669     }
 670     printf("\n");
 671 }
 672
 673 void combine_valid_left_right_states(vector<cs_t> *plcstates, vector<cs_t> *prcstates, vector<uint64_t> *pgc_candidates) {
 674     vector<cs_t>::iterator itl, itr;
 675     size_t pos;
 676     uint64_t gc;
 677     bool valid;
 678
 679     // Clean up the candidate list
 680     pgc_candidates->clear();
 681     for (itl = plcstates->begin(); itl != plcstates->end(); ++itl) {
 682         for (itr = prcstates->begin(); itr != prcstates->end(); ++itr) {
 683             valid = true;
 684             // Check for left and right candidates that share the overlapping bits (8 x 2bits of Gc)
 685             for (pos = 0; pos < 8; pos++) {
 686                 if ((itl->Gc[pos] & 0x18) != (itr->Gc[pos] & 0x18)) {
 687                     valid = false;
 688                     break;
 689                 }
 690             }
 691
 692             if (valid) {
 693                 gc = 0;
 694                 for (pos = 0; pos < 8; pos++) {
 695                     gc <<= 8;
 696                     gc |= (itl->Gc[pos] | itr->Gc[pos]);
 697                 }
 698 //        printf("%016llx\n",gc);
 699                 pgc_candidates->push_back(gc);
 700 //        printf("%09llx - ",itl->l);
 701 //        printf("%07llx\n",itr->r);
 702             }
 703         }
 704     }
 705     printf("Found a total of " _YELLOW_("%llu")" combinations, ", ((unsigned long long)plcstates->size()) * prcstates->size());
 706     printf("but only " _GREEN_("%zu")" were valid!\n", pgc_candidates->size());
 707 }
 708
 709 int main(int argc, const char *argv[]) {
 710     size_t pos;
 711     crypto_state_t ostate;
 712     uint64_t rstate_before_gc, lstate_before_gc;
 713     vector<uint64_t> rstates, pgc_candidates;
 714     vector<uint64_t>::iterator itrstates, itgc;
 715     vector<cs_t> crstates;
 716     vector<cs_t> clstates;
 717     uint32_t rbits;
 718
 719 //  uint8_t   Gc[ 8] = {0x4f,0x79,0x4a,0x46,0x3f,0xf8,0x1d,0x81};
 720 //  uint8_t   Gc[ 8] = {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};
 721 //  uint8_t   Ci[ 8] = {0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff};
 722 //  uint8_t    Q[ 8] = {0x12,0x34,0x56,0x78,0x12,0x34,0x56,0x78};
 723     uint8_t   Gc[ 8];
 724     uint8_t   Ci[ 8];
 725     uint8_t    Q[ 8];
 726     uint8_t   Ch[ 8];
 727     uint8_t Ci_1[ 8];
 728
 729     uint8_t   Gc_chk[ 8];
 730     uint8_t   Ch_chk[ 8];
 731     uint8_t Ci_1_chk[ 8];
 732
 733     //  uint8_t   ks[16] = {0xde,0x88,0xc2,0xc9,0xee,0xd4,0x1b,0x46,0x1c,0x6a,0x92,0x50,0x76,0x1a,0xe9,0x87};
 734     //  uint8_t mask[16] = {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};
 735     //  uint8_t mask[16] = {0x04,0xb0,0xe1,0x10,0xc0,0x33,0x44,0x20,0x20,0x00,0x70,0x8c,0x22,0x04,0x10,0x80};
 736
 737     uint8_t   ks[16];
 738     uint8_t mask[16];
 739
 740     uint64_t nCi;   // Card random
 741     uint64_t nQ;    // Reader random
 742     uint64_t nCh;   // Reader challenge
 743     uint64_t nCi_1; // Card answer
 744
 745     if ((argc != 2) && (argc != 5)) {
 746         printf("SecureMemory recovery - (c) Radboud University Nijmegen\n\n");
 747         printf("syntax: sma simulate\n");
 748         printf("        sma <Ci> <Q> <Ch> <Ci+1>\n\n");
 749         return 1;
 750     }
 751
 752     printf(_CYAN_("\nAuthentication info\n\n"));
 753
 754     // Check if this is a simulation
 755     if (argc == 2) {
 756         // Generate random values for the key and randoms
 757         srand((uint32_t)time(NULL));
 758         for (pos = 0; pos < 8; pos++) {
 759             Gc[pos] = rand();
 760             Ci[pos] = rand();
 761             Q[pos] = rand();
 762         }
 763         sm_auth(Gc, Ci, Q, Ch, Ci_1, &ostate);
 764         printf("  Gc... ");
 765         print_bytes(Gc, 8);
 766     } else {
 767         sscanf(argv[1], "%016" SCNx64, &nCi);
 768         num_to_bytes(nCi, 8, Ci);
 769         sscanf(argv[2], "%016" SCNx64, &nQ);
 770         num_to_bytes(nQ, 8, Q);
 771         sscanf(argv[3], "%016" SCNx64, &nCh);
 772         num_to_bytes(nCh, 8, Ch);
 773         sscanf(argv[4], "%016" SCNx64, &nCi_1);
 774         num_to_bytes(nCi_1, 8, Ci_1);
 775         printf("  Gc... unknown\n");
 776     }
 777
 778     for (pos = 0; pos < 8; pos++) {
 779         ks[2 * pos] = Ci_1[pos];
 780         ks[(2 * pos) + 1] = Ch[pos];
 781     }
 782
 783     printf("  Ci... ");
 784     print_bytes(Ci, 8);
 785     printf("   Q... ");
 786     print_bytes(Q, 8);
 787     printf("  Ch... ");
 788     print_bytes(Ch, 8);
 789     printf("Ci+1... ");
 790     print_bytes(Ci_1, 8);
 791     printf("\n");
 792     printf("  Ks... ");
 793     print_bytes(ks, 16);
 794     printf("\n");
 795
 796     printf("Initializing lookup tables for increasing cipher speed\n");
 797     init_lookup_left();
 798     init_lookup_right();
 799     init_lookup_left_subtraction();
 800     init_lookup_right_subtraction();
 801
 802     // Load in the ci (tag-nonce), together with the first half of Q (reader-nonce)
 803     rstate_before_gc = 0;
 804     lstate_before_gc = 0;
 805     for (pos = 0; pos < 4; pos++) {
 806         next_right_fast(Ci[2 * pos  ], &rstate_before_gc);
 807         next_right_fast(Ci[2 * pos + 1], &rstate_before_gc);
 808         next_right_fast(Q[pos], &rstate_before_gc);
 809
 810         next_left_fast(Ci[2 * pos  ], &lstate_before_gc);
 811         next_left_fast(Ci[2 * pos + 1], &lstate_before_gc);
 812         next_left_fast(Q[pos], &lstate_before_gc);
 813     }
 814
 815     printf("Determing the right states that correspond to the keystream\n");
 816     rbits = sm_right(ks, mask, &rstates);
 817     printf("Top-bin for the right state contains " _GREEN_("%u")" correct bits\n", rbits);
 818     printf("Total count of right bins: " _YELLOW_("%lu") "\n", (unsigned long)rstates.size());
 819
 820     if (rbits < 96) {
 821         printf(_RED_("\n  WARNING!!! Better find another trace, the right top-bin is < 96 bits\n\n"));
 822     }
 823
 824     for (itrstates = rstates.begin(); itrstates != rstates.end(); ++itrstates) {
 825         uint64_t rstate_after_gc = *itrstates;
 826         sm_left_mask(ks, mask, rstate_after_gc);
 827         printf("Using the state from the top-right bin: " _YELLOW_("0x%07" PRIx64)"\n", rstate_after_gc);
 828
 829         search_gc_candidates_right(rstate_before_gc, rstate_after_gc, Q, &crstates);
 830         printf("Found " _YELLOW_("%zu")" right candidates using the meet-in-the-middle attack\n", crstates.size());
 831         if (crstates.size() == 0) continue;
 832
 833         printf("Calculating left states using the (unknown bits) mask from the top-right state\n");
 834         sm_left(ks, mask, &clstates);
 835         printf("Found a total of " _YELLOW_("%zu")" left cipher states, recovering left candidates...\n", clstates.size());
 836         if (clstates.size() == 0) continue;
 837
 838         search_gc_candidates_left(lstate_before_gc, Q, &clstates);
 839         printf("The meet-in-the-middle attack returned " _YELLOW_("%zu")" left cipher candidates\n", clstates.size());
 840         if (clstates.size() == 0) continue;
 841
 842         printf("Combining left and right states, disposing invalid combinations\n");
 843         combine_valid_left_right_states(&clstates, &crstates, &pgc_candidates);
 844
 845         printf("Filtering the correct one using the middle part\n");
 846         for (itgc = pgc_candidates.begin(); itgc != pgc_candidates.end(); ++itgc) {
 847             num_to_bytes(*itgc, 8, Gc_chk);
 848             sm_auth(Gc_chk, Ci, Q, Ch_chk, Ci_1_chk, &ostate);
 849             if ((memcmp(Ch_chk, Ch, 8) == 0) && (memcmp(Ci_1_chk, Ci_1, 8) == 0)) {
 850                 printf("\nValid key found [ " _GREEN_("%016" PRIx64)" ]\n\n", *itgc);
 851                 return 0;
 852             }
 853         }
 854         printf(_RED_("Could not find key using this right cipher state.\n\n"));
 855     }
 856     return 0;
 857 }
 858
 859 #if defined(__cplusplus)
 860 }
 861 #endif