client/src/mifare/mfkey.c

   1 //-----------------------------------------------------------------------------
   2 // Copyright (C) Roel Verdult 2009
   3 // Copyright (C) Proxmark3 contributors. See AUTHORS.md for details.
   4 //
   5 // This program is free software: you can redistribute it and/or modify
   6 // it under the terms of the GNU General Public License as published by
   7 // the Free Software Foundation, either version 3 of the License, or
   8 // (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14 //
  15 // See LICENSE.txt for the text of the license.
  16 //-----------------------------------------------------------------------------
  17 // MIFARE Darkside hack
  18 //-----------------------------------------------------------------------------
  19 #include "mfkey.h"
  20
  21 #include "crapto1/crapto1.h"
  22
  23 // MIFARE
  24 int inline compare_uint64(const void *a, const void *b) {
  25     if (*(uint64_t *)b == *(uint64_t *)a) return 0;
  26     if (*(uint64_t *)b < * (uint64_t *)a) return 1;
  27     return -1;
  28 }
  29
  30 // create the intersection (common members) of two sorted lists. Lists are terminated by -1. Result will be in list1. Number of elements is returned.
  31 uint32_t intersection(uint64_t *listA, uint64_t *listB) {
  32     if (listA == NULL || listB == NULL)
  33         return 0;
  34
  35     uint64_t *p1, *p2, *p3;
  36     p1 = p3 = listA;
  37     p2 = listB;
  38
  39     while (*p1 != UINT64_C(-1) && *p2 != UINT64_C(-1)) {
  40         if (compare_uint64(p1, p2) == 0) {
  41             *p3++ = *p1++;
  42             p2++;
  43         } else {
  44             while (compare_uint64(p1, p2) < 0) ++p1;
  45             while (compare_uint64(p1, p2) > 0) ++p2;
  46         }
  47     }
  48     *p3 = UINT64_C(-1);
  49     return p3 - listA;
  50 }
  51
  52 // Darkside attack (hf mf mifare)
  53 // if successful it will return a list of keys, not just one.
  54 uint32_t nonce2key(uint32_t uid, uint32_t nt, uint32_t nr, uint32_t ar, uint64_t par_info, uint64_t ks_info, uint64_t **keys) {
  55     union {
  56         struct Crypto1State *states;
  57         uint64_t *keylist;
  58     } unionstate;
  59
  60     uint32_t i, pos;
  61     uint8_t ks3x[8], par[8][8];
  62     uint64_t key_recovered;
  63
  64     // Reset the last three significant bits of the reader nonce
  65     nr &= 0xFFFFFF1F;
  66
  67     for (pos = 0; pos < 8; pos++) {
  68         ks3x[7 - pos] = (ks_info >> (pos * 8)) & 0x0F;
  69         uint8_t bt = (par_info >> (pos * 8)) & 0xFF;
  70
  71         par[7 - pos][0] = (bt >> 0) & 1;
  72         par[7 - pos][1] = (bt >> 1) & 1;
  73         par[7 - pos][2] = (bt >> 2) & 1;
  74         par[7 - pos][3] = (bt >> 3) & 1;
  75         par[7 - pos][4] = (bt >> 4) & 1;
  76         par[7 - pos][5] = (bt >> 5) & 1;
  77         par[7 - pos][6] = (bt >> 6) & 1;
  78         par[7 - pos][7] = (bt >> 7) & 1;
  79     }
  80
  81     unionstate.states = lfsr_common_prefix(nr, ar, ks3x, par, (par_info == 0));
  82
  83     if (!unionstate.states) {
  84         *keys = NULL;
  85         return 0;
  86     }
  87
  88     for (i = 0; unionstate.keylist[i]; i++) {
  89         lfsr_rollback_word(unionstate.states + i, uid ^ nt, 0);
  90         crypto1_get_lfsr(unionstate.states + i, &key_recovered);
  91         unionstate.keylist[i] = key_recovered;
  92     }
  93     unionstate.keylist[i] = -1;
  94
  95     *keys = unionstate.keylist;
  96     return i;
  97 }
  98
  99 // recover key from 2 different reader responses on same tag challenge
 100 bool mfkey32(nonces_t *data, uint64_t *outputkey) {
 101     struct Crypto1State *s, *t;
 102     uint64_t outkey = 0;
 103     uint64_t key = 0;     // recovered key
 104     bool isSuccess = false;
 105     uint8_t counter = 0;
 106
 107     uint32_t p640 = prng_successor(data->nonce, 64);
 108
 109     s = lfsr_recovery32(data->ar ^ p640, 0);
 110
 111     for (t = s; t->odd | t->even; ++t) {
 112         lfsr_rollback_word(t, 0, 0);
 113         lfsr_rollback_word(t, data->nr, 1);
 114         lfsr_rollback_word(t, data->cuid ^ data->nonce, 0);
 115         crypto1_get_lfsr(t, &key);
 116         crypto1_word(t, data->cuid ^ data->nonce, 0);
 117         crypto1_word(t, data->nr2, 1);
 118         if (data->ar2 == (crypto1_word(t, 0, 0) ^ p640)) {
 119             outkey = key;
 120             counter++;
 121             if (counter == 20) break;
 122         }
 123     }
 124     isSuccess = (counter == 1);
 125     *outputkey = (isSuccess) ? outkey : 0;
 126     crypto1_destroy(s);
 127     return isSuccess;
 128 }
 129
 130 // recover key from 2 reader responses on 2 different tag challenges
 131 // skip "several found keys".  Only return true if ONE key is found
 132 bool mfkey32_moebius(nonces_t *data, uint64_t *outputkey) {
 133     struct Crypto1State *s, *t;
 134     uint64_t outkey  = 0;
 135     uint64_t key     = 0; // recovered key
 136     bool isSuccess = false;
 137     int counter = 0;
 138     uint32_t p640 = prng_successor(data->nonce, 64);
 139     uint32_t p641 = prng_successor(data->nonce2, 64);
 140
 141     s = lfsr_recovery32(data->ar ^ p640, 0);
 142
 143     for (t = s; t->odd | t->even; ++t) {
 144         lfsr_rollback_word(t, 0, 0);
 145         lfsr_rollback_word(t, data->nr, 1);
 146         lfsr_rollback_word(t, data->cuid ^ data->nonce, 0);
 147         crypto1_get_lfsr(t, &key);
 148
 149         crypto1_word(t, data->cuid ^ data->nonce2, 0);
 150         crypto1_word(t, data->nr2, 1);
 151         if (data->ar2 == (crypto1_word(t, 0, 0) ^ p641)) {
 152             outkey = key;
 153             ++counter;
 154             if (counter == 2) break;
 155         }
 156     }
 157     isSuccess  = (counter == 1);
 158     *outputkey = (isSuccess) ? outkey : 0;
 159     crypto1_destroy(s);
 160     return isSuccess;
 161 }
 162
 163 // recover key from 2 reader responses on 2 different tag challenges
 164 // skip "several found keys".  Only return true if ONE key is found
 165 bool mfkey32_nested(nonces_t *data, uint64_t *outputkey) {
 166     struct Crypto1State *s, *t;
 167     uint64_t key     = 0; // recovered key
 168     bool isSuccess = false;
 169
 170     uint32_t uid = data->cuid;
 171     uint32_t nt = data->nonce;
 172     uint32_t nt_enc = data->nonce2;
 173     uint32_t ar = prng_successor(nt, 64);
 174     uint32_t nr_enc = data->nr;
 175     uint32_t ar_enc = data->ar;
 176     uint32_t ks0 = nt_enc ^ nt;
 177     uint32_t ks2 = ar_enc ^ ar;
 178     s = lfsr_recovery32(ks0, uid ^ nt);
 179     for (t = s; t->odd | t->even; ++t) {
 180         crypto1_word(t, nr_enc, 1);
 181         if (ks2 == crypto1_word(t, 0, 0)) {
 182             lfsr_rollback_word(t, 0, 0);
 183             lfsr_rollback_word(t, nr_enc, 1);
 184             lfsr_rollback_word(t, uid ^ nt, 0);
 185             crypto1_get_lfsr(t, &key);
 186             isSuccess = true;
 187             break;
 188         }
 189     }
 190     *outputkey = (isSuccess) ? key : 0;
 191     crypto1_destroy(s);
 192     return isSuccess;
 193 }
 194
 195 // recover key from reader response and tag response of one authentication sequence
 196 int mfkey64(nonces_t *data, uint64_t *outputkey) {
 197     uint64_t key = 0;  // recovered key
 198     uint32_t ks2;      // keystream used to encrypt reader response
 199     uint32_t ks3;      // keystream used to encrypt tag response
 200     struct Crypto1State *revstate;
 201
 202     // Extract the keystream from the messages
 203     ks2 = data->ar ^ prng_successor(data->nonce, 64);
 204     ks3 = data->at ^ prng_successor(data->nonce, 96);
 205     revstate = lfsr_recovery64(ks2, ks3);
 206     lfsr_rollback_word(revstate, 0, 0);
 207     lfsr_rollback_word(revstate, 0, 0);
 208     lfsr_rollback_word(revstate, data->nr, 1);
 209     lfsr_rollback_word(revstate, data->cuid ^ data->nonce, 0);
 210     crypto1_get_lfsr(revstate, &key);
 211     crypto1_destroy(revstate);
 212     *outputkey = key;
 213     return 0;
 214 }