tools/cryptorf/sma_multi.cpp

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