From: pwpiwi Date: Tue, 21 Mar 2017 14:38:18 +0000 (+0100) Subject: Merge pull request #235 from marshmellow42/lfdemod_refactors X-Git-Tag: v3.0.0~45 X-Git-Url: http://git.zerfleddert.de/cgi-bin/gitweb.cgi/proxmark3-svn/commitdiff_plain/7ac59a82ab5d244407254febf5dc9b7be892d2ad?hp=86b8ecb56ed66e2b604703d4fe47efbc6300cc36 Merge pull request #235 from marshmellow42/lfdemod_refactors lfdemod refactor --- diff --git a/COMPILING.txt b/COMPILING.txt index e5abb25f..73201f25 100644 --- a/COMPILING.txt +++ b/COMPILING.txt @@ -81,6 +81,29 @@ Download the ProxSpace environment archive and extract it to C:\ = Mac OS X = ============ +Installing from HomeBrew tap +--------------------------- +This method is recommended and tested on macOS Sierra 10.12.3 + +1. Install homebrew if you haven't yet already done so: http://brew.sh/ + +2. Tap proxmark repo: + brew tap proxmark/proxmark3 + +3. Install Proxmark3: + +Stable release + brew install proxmark3 + +Latest non-stable from GitHub (use this if previous command fails) + brew install --HEAD proxmark3 + +For more information go to https://github.com/Proxmark/homebrew-proxmark3 + + +Compilling from source manually (Legacy) +--------------------------- + Tested on OSX 10.10 Yosemite 1 - Install Xcode and Xcode Command Line Tools diff --git a/armsrc/Makefile b/armsrc/Makefile index 2fbad384..b698d1f2 100644 --- a/armsrc/Makefile +++ b/armsrc/Makefile @@ -19,7 +19,7 @@ SRC_LF = lfops.c hitag2.c hitagS.c lfsampling.c pcf7931.c lfdemod.c protocols.c SRC_ISO15693 = iso15693.c iso15693tools.c SRC_ISO14443a = epa.c iso14443a.c mifareutil.c mifarecmd.c mifaresniff.c SRC_ISO14443b = iso14443b.c -SRC_CRAPTO1 = crapto1.c crypto1.c des.c aes.c +SRC_CRAPTO1 = crypto1.c des.c aes.c SRC_CRC = iso14443crc.c crc.c crc16.c crc32.c #the FPGA bitstream files. Note: order matters! diff --git a/armsrc/crapto1.c b/armsrc/crapto1.c deleted file mode 100644 index bcd31171..00000000 --- a/armsrc/crapto1.c +++ /dev/null @@ -1,488 +0,0 @@ -/* crapto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, - Boston, MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#if !defined LOWMEM && defined __GNUC__ -static uint8_t filterlut[1 << 20]; -static void __attribute__((constructor)) fill_lut() -{ - uint32_t i; - for(i = 0; i < 1 << 20; ++i) - filterlut[i] = filter(i); -} -#define filter(x) (filterlut[(x) & 0xfffff]) -#endif - -static void quicksort(uint32_t* const start, uint32_t* const stop) -{ - uint32_t *it = start + 1, *rit = stop; - uint32_t tmp; - - if(it > rit) - return; - - while(it < rit) - if(*it <= *start) - ++it; - else if(*rit > *start) - --rit; - else { - tmp = *it; - *it = *rit; - *rit = tmp; - } - - if(*rit >= *start) - --rit; - if(rit != start) { - tmp = *rit; - *rit = *start; - *start = tmp; - } - - quicksort(start, rit - 1); - quicksort(rit + 1, stop); -} -/** binsearch - * Binary search for the first occurence of *stop's MSB in sorted [start,stop] - */ -static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop) -{ - uint32_t mid, val = *stop & 0xff000000; - while(start != stop) - if(start[mid = (stop - start) >> 1] > val) - stop = &start[mid]; - else - start += mid + 1; - - return start; -} - -/** update_contribution - * helper, calculates the partial linear feedback contributions and puts in MSB - */ -static inline void -update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) -{ - uint32_t p = *item >> 25; - - p = p << 1 | parity(*item & mask1); - p = p << 1 | parity(*item & mask2); - *item = p << 24 | (*item & 0xffffff); -} - -/** extend_table - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void -extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) -{ - in <<= 24; - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) - if(filter(*tbl) ^ filter(*tbl | 1)) { - *tbl |= filter(*tbl) ^ bit; - update_contribution(tbl, m1, m2); - *tbl ^= in; - } else if(filter(*tbl) == bit) { - *++*end = tbl[1]; - tbl[1] = tbl[0] | 1; - update_contribution(tbl, m1, m2); - *tbl++ ^= in; - update_contribution(tbl, m1, m2); - *tbl ^= in; - } else - *tbl-- = *(*end)--; -} -/** extend_table_simple - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) -{ - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) - if(filter(*tbl) ^ filter(*tbl | 1)) - *tbl |= filter(*tbl) ^ bit; - else if(filter(*tbl) == bit) { - *++*end = *++tbl; - *tbl = tbl[-1] | 1; - } else - *tbl-- = *(*end)--; -} -/** recover - * recursively narrow down the search space, 4 bits of keystream at a time - */ -static struct Crypto1State* -recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, - uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem, - struct Crypto1State *sl, uint32_t in) -{ - uint32_t *o, *e, i; - - if(rem == -1) { - for(e = e_head; e <= e_tail; ++e) { - *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4); - for(o = o_head; o <= o_tail; ++o, ++sl) { - sl->even = *o; - sl->odd = *e ^ parity(*o & LF_POLY_ODD); - sl[1].odd = sl[1].even = 0; - } - } - return sl; - } - - for(i = 0; i < 4 && rem--; i++) { - oks >>= 1; - eks >>= 1; - in >>= 2; - extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, - LF_POLY_ODD << 1, 0); - if(o_head > o_tail) - return sl; - - extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, - LF_POLY_EVEN << 1 | 1, in & 3); - if(e_head > e_tail) - return sl; - } - - quicksort(o_head, o_tail); - quicksort(e_head, e_tail); - - while(o_tail >= o_head && e_tail >= e_head) - if(((*o_tail ^ *e_tail) >> 24) == 0) { - o_tail = binsearch(o_head, o = o_tail); - e_tail = binsearch(e_head, e = e_tail); - sl = recover(o_tail--, o, oks, - e_tail--, e, eks, rem, sl, in); - } - else if(*o_tail > *e_tail) - o_tail = binsearch(o_head, o_tail) - 1; - else - e_tail = binsearch(e_head, e_tail) - 1; - - return sl; -} -/** lfsr_recovery - * recover the state of the lfsr given 32 bits of the keystream - * additionally you can use the in parameter to specify the value - * that was fed into the lfsr at the time the keystream was generated - */ -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) -{ - struct Crypto1State *statelist; - uint32_t *odd_head = 0, *odd_tail = 0, oks = 0; - uint32_t *even_head = 0, *even_tail = 0, eks = 0; - int i; - - for(i = 31; i >= 0; i -= 2) - oks = oks << 1 | BEBIT(ks2, i); - for(i = 30; i >= 0; i -= 2) - eks = eks << 1 | BEBIT(ks2, i); - - odd_head = odd_tail = malloc(sizeof(uint32_t) << 21); - even_head = even_tail = malloc(sizeof(uint32_t) << 21); - statelist = malloc(sizeof(struct Crypto1State) << 18); - if(!odd_tail-- || !even_tail-- || !statelist) { - free(statelist); - statelist = 0; - goto out; - } - - statelist->odd = statelist->even = 0; - - for(i = 1 << 20; i >= 0; --i) { - if(filter(i) == (oks & 1)) - *++odd_tail = i; - if(filter(i) == (eks & 1)) - *++even_tail = i; - } - - for(i = 0; i < 4; i++) { - extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1); - extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1); - } - - in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); - recover(odd_head, odd_tail, oks, - even_head, even_tail, eks, 11, statelist, in << 1); - -out: - free(odd_head); - free(even_head); - return statelist; -} - -static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214, - 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83, - 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA}; -static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60, - 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8, - 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20, - 0x7EC7EE90, 0x7F63F748, 0x79117020}; -static const uint32_t T1[] = { - 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66, - 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B, - 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615, - 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C}; -static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0, - 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268, - 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0, - 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0, - 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950, - 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0}; -static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD}; -static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0}; -/** Reverse 64 bits of keystream into possible cipher states - * Variation mentioned in the paper. Somewhat optimized version - */ -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3) -{ - struct Crypto1State *statelist, *sl; - uint8_t oks[32], eks[32], hi[32]; - uint32_t low = 0, win = 0; - uint32_t *tail, table[1 << 16]; - int i, j; - - sl = statelist = malloc(sizeof(struct Crypto1State) << 4); - if(!sl) - return 0; - sl->odd = sl->even = 0; - - for(i = 30; i >= 0; i -= 2) { - oks[i >> 1] = BEBIT(ks2, i); - oks[16 + (i >> 1)] = BEBIT(ks3, i); - } - for(i = 31; i >= 0; i -= 2) { - eks[i >> 1] = BEBIT(ks2, i); - eks[16 + (i >> 1)] = BEBIT(ks3, i); - } - - for(i = 0xfffff; i >= 0; --i) { - if (filter(i) != oks[0]) - continue; - - *(tail = table) = i; - for(j = 1; tail >= table && j < 29; ++j) - extend_table_simple(table, &tail, oks[j]); - - if(tail < table) - continue; - - for(j = 0; j < 19; ++j) - low = low << 1 | parity(i & S1[j]); - for(j = 0; j < 32; ++j) - hi[j] = parity(i & T1[j]); - - for(; tail >= table; --tail) { - for(j = 0; j < 3; ++j) { - *tail = *tail << 1; - *tail |= parity((i & C1[j]) ^ (*tail & C2[j])); - if(filter(*tail) != oks[29 + j]) - goto continue2; - } - - for(j = 0; j < 19; ++j) - win = win << 1 | parity(*tail & S2[j]); - - win ^= low; - for(j = 0; j < 32; ++j) { - win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]); - if(filter(win) != eks[j]) - goto continue2; - } - - *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail); - sl->odd = *tail ^ parity(LF_POLY_ODD & win); - sl->even = win; - ++sl; - sl->odd = sl->even = 0; - continue2:; - } - } - return statelist; -} - -/** lfsr_rollback_bit - * Rollback the shift register in order to get previous states - */ -uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb) -{ - int out; - uint8_t ret; - uint32_t tmp; - - s->odd &= 0xffffff; - tmp = s->odd; - s->odd = s->even; - s->even = tmp; - - out = s->even & 1; - out ^= LF_POLY_EVEN & (s->even >>= 1); - out ^= LF_POLY_ODD & s->odd; - out ^= !!in; - out ^= (ret = filter(s->odd)) & !!fb; - - s->even |= parity(out) << 23; - return ret; -} -/** lfsr_rollback_byte - * Rollback the shift register in order to get previous states - */ -uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb) -{ - int i, ret = 0; - for (i = 7; i >= 0; --i) - ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i; - return ret; -} -/** lfsr_rollback_word - * Rollback the shift register in order to get previous states - */ -uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb) -{ - int i; - uint32_t ret = 0; - for (i = 31; i >= 0; --i) - ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24); - return ret; -} - -/** nonce_distance - * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y - */ -static uint16_t *dist = 0; -int nonce_distance(uint32_t from, uint32_t to) -{ - uint16_t x, i; - if(!dist) { - dist = malloc(2 << 16); - if(!dist) - return -1; - for (x = i = 1; i; ++i) { - dist[(x & 0xff) << 8 | x >> 8] = i; - x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15; - } - } - return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535; -} - - -static uint32_t fastfwd[2][8] = { - { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB}, - { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}}; -/** lfsr_prefix_ks - * - * Is an exported helper function from the common prefix attack - * Described in the "dark side" paper. It returns an -1 terminated array - * of possible partial(21 bit) secret state. - * The required keystream(ks) needs to contain the keystream that was used to - * encrypt the NACK which is observed when varying only the 3 last bits of Nr - * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3 - */ -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd) -{ - uint32_t c, entry, *candidates = malloc(4 << 10); - int i, size = 0, good; - - if(!candidates) - return 0; - - for(i = 0; i < 1 << 21; ++i) { - for(c = 0, good = 1; good && c < 8; ++c) { - entry = i ^ fastfwd[isodd][c]; - good &= (BIT(ks[c], isodd) == filter(entry >> 1)); - good &= (BIT(ks[c], isodd + 2) == filter(entry)); - } - if(good) - candidates[size++] = i; - } - - candidates[size] = -1; - - return candidates; -} - -/** check_pfx_parity - * helper function which eliminates possible secret states using parity bits - */ -static struct Crypto1State* -check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8], - uint32_t odd, uint32_t even, struct Crypto1State* sl) -{ - uint32_t ks1, nr, ks2, rr, ks3, c, good = 1; - - for(c = 0; good && c < 8; ++c) { - sl->odd = odd ^ fastfwd[1][c]; - sl->even = even ^ fastfwd[0][c]; - - lfsr_rollback_bit(sl, 0, 0); - lfsr_rollback_bit(sl, 0, 0); - - ks3 = lfsr_rollback_bit(sl, 0, 0); - ks2 = lfsr_rollback_word(sl, 0, 0); - ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1); - - nr = ks1 ^ (prefix | c << 5); - rr = ks2 ^ rresp; - - good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24); - good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16); - good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8); - good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0); - good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3; - } - - return sl + good; -} - - -/** lfsr_common_prefix - * Implentation of the common prefix attack. - */ -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8]) -{ - struct Crypto1State *statelist, *s; - uint32_t *odd, *even, *o, *e, top; - - odd = lfsr_prefix_ks(ks, 1); - even = lfsr_prefix_ks(ks, 0); - - s = statelist = malloc((sizeof *statelist) << 20); - if(!s || !odd || !even) { - free(statelist); - statelist = 0; - goto out; - } - - for(o = odd; *o + 1; ++o) - for(e = even; *e + 1; ++e) - for(top = 0; top < 64; ++top) { - *o += 1 << 21; - *e += (!(top & 7) + 1) << 21; - s = check_pfx_parity(pfx, rr, par, *o, *e, s); - } - - s->odd = s->even = 0; -out: - free(odd); - free(even); - return statelist; -} diff --git a/armsrc/crapto1.h b/armsrc/crapto1.h deleted file mode 100644 index b144853c..00000000 --- a/armsrc/crapto1.h +++ /dev/null @@ -1,93 +0,0 @@ -/* crapto1.h - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#ifndef CRAPTO1_INCLUDED -#define CRAPTO1_INCLUDED -#include -#ifdef __cplusplus -extern "C" { -#endif - -struct Crypto1State {uint32_t odd, even;}; -void crypto1_create(struct Crypto1State *s, uint64_t key); -void crypto1_destroy(struct Crypto1State*); -void crypto1_get_lfsr(struct Crypto1State*, uint64_t*); -uint8_t crypto1_bit(struct Crypto1State*, uint8_t, int); -uint8_t crypto1_byte(struct Crypto1State*, uint8_t, int); -uint32_t crypto1_word(struct Crypto1State*, uint32_t, int); -uint32_t prng_successor(uint32_t x, uint32_t n); - -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in); -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3); -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd); -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8]); - -uint8_t lfsr_rollback_bit(struct Crypto1State* s, uint32_t in, int fb); -uint8_t lfsr_rollback_byte(struct Crypto1State* s, uint32_t in, int fb); -uint32_t lfsr_rollback_word(struct Crypto1State* s, uint32_t in, int fb); -int nonce_distance(uint32_t from, uint32_t to); -#define FOREACH_VALID_NONCE(N, FILTER, FSIZE)\ - uint32_t __n = 0,__M = 0, N = 0;\ - int __i;\ - for(; __n < 1 << 16; N = prng_successor(__M = ++__n, 16))\ - for(__i = FSIZE - 1; __i >= 0; __i--)\ - if(BIT(FILTER, __i) ^ parity(__M & 0xFF01))\ - break;\ - else if(__i)\ - __M = prng_successor(__M, (__i == 7) ? 48 : 8);\ - else - -#define LF_POLY_ODD (0x29CE5C) -#define LF_POLY_EVEN (0x870804) -#define BIT(x, n) ((x) >> (n) & 1) -#define BEBIT(x, n) BIT(x, (n) ^ 24) -static inline int parity(uint32_t x) -{ -#if !defined __i386__ || !defined __GNUC__ - x ^= x >> 16; - x ^= x >> 8; - x ^= x >> 4; - return BIT(0x6996, x & 0xf); -#else - asm( "movl %1, %%eax\n" - "mov %%ax, %%cx\n" - "shrl $0x10, %%eax\n" - "xor %%ax, %%cx\n" - "xor %%ch, %%cl\n" - "setpo %%al\n" - "movzx %%al, %0\n": "=r"(x) : "r"(x): "eax","ecx"); - return x; -#endif -} -static inline int filter(uint32_t const x) -{ - uint32_t f; - - f = 0xf22c0 >> (x & 0xf) & 16; - f |= 0x6c9c0 >> (x >> 4 & 0xf) & 8; - f |= 0x3c8b0 >> (x >> 8 & 0xf) & 4; - f |= 0x1e458 >> (x >> 12 & 0xf) & 2; - f |= 0x0d938 >> (x >> 16 & 0xf) & 1; - return BIT(0xEC57E80A, f); -} -#ifdef __cplusplus -} -#endif -#endif diff --git a/armsrc/crypto1.c b/armsrc/crypto1.c deleted file mode 100644 index 74765348..00000000 --- a/armsrc/crypto1.c +++ /dev/null @@ -1,98 +0,0 @@ -/* crypto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#define SWAPENDIAN(x)\ - (x = (x >> 8 & 0xff00ff) | (x & 0xff00ff) << 8, x = x >> 16 | x << 16) - -void crypto1_create(struct Crypto1State *s, uint64_t key) -{ -// struct Crypto1State *s = malloc(sizeof(*s)); - int i; - - for(i = 47;s && i > 0; i -= 2) { - s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); - s->even = s->even << 1 | BIT(key, i ^ 7); - } - return; -} -void crypto1_destroy(struct Crypto1State *state) -{ -// free(state); - state->odd = 0; - state->even = 0; -} -void crypto1_get_lfsr(struct Crypto1State *state, uint64_t *lfsr) -{ - int i; - for(*lfsr = 0, i = 23; i >= 0; --i) { - *lfsr = *lfsr << 1 | BIT(state->odd, i ^ 3); - *lfsr = *lfsr << 1 | BIT(state->even, i ^ 3); - } -} -uint8_t crypto1_bit(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint32_t feedin; - uint32_t tmp; - uint8_t ret = filter(s->odd); - - feedin = ret & !!is_encrypted; - feedin ^= !!in; - feedin ^= LF_POLY_ODD & s->odd; - feedin ^= LF_POLY_EVEN & s->even; - s->even = s->even << 1 | parity(feedin); - - tmp = s->odd; - s->odd = s->even; - s->even = tmp; - - return ret; -} -uint8_t crypto1_byte(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint8_t i, ret = 0; - - for (i = 0; i < 8; ++i) - ret |= crypto1_bit(s, BIT(in, i), is_encrypted) << i; - - return ret; -} -uint32_t crypto1_word(struct Crypto1State *s, uint32_t in, int is_encrypted) -{ - uint32_t i, ret = 0; - - for (i = 0; i < 32; ++i) - ret |= crypto1_bit(s, BEBIT(in, i), is_encrypted) << (i ^ 24); - - return ret; -} - -/* prng_successor - * helper used to obscure the keystream during authentication - */ -uint32_t prng_successor(uint32_t x, uint32_t n) -{ - SWAPENDIAN(x); - while(n--) - x = x >> 1 | (x >> 16 ^ x >> 18 ^ x >> 19 ^ x >> 21) << 31; - - return SWAPENDIAN(x); -} diff --git a/armsrc/iso14443a.c b/armsrc/iso14443a.c index 83907fce..76b82141 100644 --- a/armsrc/iso14443a.c +++ b/armsrc/iso14443a.c @@ -17,7 +17,7 @@ #include "cmd.h" #include "iso14443crc.h" #include "iso14443a.h" -#include "crapto1.h" +#include "crapto1/crapto1.h" #include "mifareutil.h" #include "BigBuf.h" #include "protocols.h" diff --git a/armsrc/mifarecmd.h b/armsrc/mifarecmd.h index 3c00a343..145e2989 100644 --- a/armsrc/mifarecmd.h +++ b/armsrc/mifarecmd.h @@ -20,7 +20,7 @@ #include "iso14443crc.h" #include "iso14443a.h" -#include "crapto1.h" +#include "crapto1/crapto1.h" #include "mifareutil.h" #include "common.h" diff --git a/armsrc/mifaresniff.c b/armsrc/mifaresniff.c index 0cc2963b..7f94b0fe 100644 --- a/armsrc/mifaresniff.c +++ b/armsrc/mifaresniff.c @@ -10,6 +10,15 @@ #include "mifaresniff.h" #include "apps.h" +#include "proxmark3.h" +#include "util.h" +#include "string.h" +#include "iso14443crc.h" +#include "iso14443a.h" +#include "crapto1/crapto1.h" +#include "mifareutil.h" +#include "common.h" + static int sniffState = SNF_INIT; static uint8_t sniffUIDType; diff --git a/armsrc/mifaresniff.h b/armsrc/mifaresniff.h index 22daffee..8a8e31a9 100644 --- a/armsrc/mifaresniff.h +++ b/armsrc/mifaresniff.h @@ -11,29 +11,22 @@ #ifndef __MIFARESNIFF_H #define __MIFARESNIFF_H -#include "proxmark3.h" -#include "apps.h" +#include +#include #include "util.h" -#include "string.h" - -#include "iso14443crc.h" -#include "iso14443a.h" -#include "crapto1.h" -#include "mifareutil.h" -#include "common.h" #define SNF_INIT 0 -#define SNF_NO_FIELD 1 -#define SNF_WUPREQ 2 +#define SNF_NO_FIELD 1 +#define SNF_WUPREQ 2 #define SNF_ATQA 3 -#define SNF_ANTICOL1 4 +#define SNF_ANTICOL1 4 #define SNF_UID1 5 -#define SNF_ANTICOL2 6 +#define SNF_ANTICOL2 6 #define SNF_UID2 7 #define SNF_SAK 8 -#define SNF_CARD_IDLE 9 -#define SNF_CARD_CMD 10 -#define SNF_CARD_RESP 11 +#define SNF_CARD_IDLE 9 +#define SNF_CARD_CMD 10 +#define SNF_CARD_RESP 11 #define SNF_UID_4 0 #define SNF_UID_7 0 @@ -44,4 +37,4 @@ bool RAMFUNC MfSniffSend(uint16_t maxTimeoutMs); bool intMfSniffSend(); bool MfSniffEnd(void); -#endif \ No newline at end of file +#endif diff --git a/armsrc/mifareutil.c b/armsrc/mifareutil.c index 8ef364c2..48fcd57a 100644 --- a/armsrc/mifareutil.c +++ b/armsrc/mifareutil.c @@ -9,6 +9,7 @@ // Work with mifare cards. //----------------------------------------------------------------------------- +#include "mifareutil.h" #include "proxmark3.h" #include "apps.h" #include "util.h" @@ -16,8 +17,7 @@ #include "iso14443crc.h" #include "iso14443a.h" -#include "crapto1.h" -#include "mifareutil.h" +#include "crapto1/crapto1.h" #include "des.h" int MF_DBGLEVEL = MF_DBG_ALL; diff --git a/armsrc/mifareutil.h b/armsrc/mifareutil.h index 3d4dd400..468c5cce 100644 --- a/armsrc/mifareutil.h +++ b/armsrc/mifareutil.h @@ -8,11 +8,12 @@ //----------------------------------------------------------------------------- // code for work with mifare cards. //----------------------------------------------------------------------------- -#include "crapto1.h" #ifndef __MIFAREUTIL_H #define __MIFAREUTIL_H +#include "crapto1/crapto1.h" + // mifare authentication #define CRYPT_NONE 0 #define CRYPT_ALL 1 diff --git a/client/Makefile b/client/Makefile index 2a572c11..ac7e6f98 100644 --- a/client/Makefile +++ b/client/Makefile @@ -15,7 +15,7 @@ OBJDIR = obj LDLIBS = -L/opt/local/lib -L/usr/local/lib -lreadline -lpthread -lm LUALIB = ../liblua/liblua.a LDFLAGS = $(COMMON_FLAGS) -CFLAGS = -std=c99 -D_ISOC99_SOURCE -I. -I../include -I../common -I../zlib -I/opt/local/include -I../liblua -Wall $(COMMON_FLAGS) -g -O4 +CFLAGS = -std=c99 -D_ISOC99_SOURCE -I. -I../include -I../common -I../tools -I../zlib -I/opt/local/include -I../liblua -Wall $(COMMON_FLAGS) -g -O4 LUAPLATFORM = generic ifneq (,$(findstring MINGW,$(platform))) @@ -54,12 +54,11 @@ endif CORESRCS = uart.c \ util.c \ - sleep.c -CMDSRCS = nonce2key/crapto1.c\ - nonce2key/crypto1.c\ - nonce2key/nonce2key.c\ +CMDSRCS = crapto1/crapto1.c\ + crapto1/crypto1.c\ + nonce2key.c\ loclass/cipher.c \ loclass/cipherutils.c \ loclass/des.c \ diff --git a/client/cmdcrc.c b/client/cmdcrc.c index fddf0ac4..01f65f55 100644 --- a/client/cmdcrc.c +++ b/client/cmdcrc.c @@ -8,7 +8,6 @@ // CRC Calculations from the software reveng commands //----------------------------------------------------------------------------- -#include #ifdef _WIN32 # include # include @@ -19,8 +18,8 @@ #include #include -//#include -//#include +#include +#include #include "cmdmain.h" #include "cmdcrc.h" #include "reveng/reveng.h" diff --git a/client/cmdhf.c b/client/cmdhf.c index 17353fb6..cb71b93b 100644 --- a/client/cmdhf.c +++ b/client/cmdhf.c @@ -8,10 +8,12 @@ // High frequency commands //----------------------------------------------------------------------------- +#include #include #include #include "proxmark3.h" #include "util.h" +#include "data.h" #include "ui.h" #include "iso14443crc.h" #include "cmdmain.h" diff --git a/client/cmdhf14a.c b/client/cmdhf14a.c index 3dc501d4..812db8ee 100644 --- a/client/cmdhf14a.c +++ b/client/cmdhf14a.c @@ -431,7 +431,7 @@ int CmdHF14ACUIDs(const char *Cmd) n = n > 0 ? n : 1; PrintAndLog("Collecting %d UIDs", n); - PrintAndLog("Start: %u", time(NULL)); + PrintAndLog("Start: %" PRIu64, msclock()/1000); // repeat n times for (int i = 0; i < n; i++) { // execute anticollision procedure @@ -454,7 +454,7 @@ int CmdHF14ACUIDs(const char *Cmd) PrintAndLog("%s", uid_string); } } - PrintAndLog("End: %u", time(NULL)); + PrintAndLog("End: %" PRIu64, msclock()/1000); return 1; } diff --git a/client/cmdhf14a.h b/client/cmdhf14a.h index aa35dec6..dfdf1f4a 100644 --- a/client/cmdhf14a.h +++ b/client/cmdhf14a.h @@ -12,13 +12,14 @@ #ifndef CMDHF14A_H__ #define CMDHF14A_H__ -int CmdHF14A(const char *Cmd); +#include +int CmdHF14A(const char *Cmd); int CmdHF14AList(const char *Cmd); int CmdHF14AMifare(const char *Cmd); int CmdHF14AReader(const char *Cmd); int CmdHF14ASim(const char *Cmd); int CmdHF14ASnoop(const char *Cmd); - char* getTagInfo(uint8_t uid); + #endif diff --git a/client/cmdhfepa.c b/client/cmdhfepa.c index e50ce708..786d0da1 100644 --- a/client/cmdhfepa.c +++ b/client/cmdhfepa.c @@ -8,15 +8,19 @@ // Commands related to the German electronic Identification Card //----------------------------------------------------------------------------- -#include "util.h" +#include "cmdhfepa.h" +#include +#include +#include +#include +#include +#include "util.h" #include "proxmark3.h" #include "ui.h" #include "cmdparser.h" #include "common.h" #include "cmdmain.h" -#include "sleep.h" -#include "cmdhfepa.h" static int CmdHelp(const char *Cmd); @@ -37,7 +41,7 @@ int CmdHFEPACollectPACENonces(const char *Cmd) n = n > 0 ? n : 1; PrintAndLog("Collecting %u %u-byte nonces", n, m); - PrintAndLog("Start: %u", time(NULL)); + PrintAndLog("Start: %" PRIu64 , msclock()/1000); // repeat n times for (unsigned int i = 0; i < n; i++) { // execute PACE @@ -64,7 +68,7 @@ int CmdHFEPACollectPACENonces(const char *Cmd) sleep(d); } } - PrintAndLog("End: %u", time(NULL)); + PrintAndLog("End: %" PRIu64, msclock()/1000); return 1; } diff --git a/client/cmdhfmf.c b/client/cmdhfmf.c index eb3dc878..47660a6e 100644 --- a/client/cmdhfmf.c +++ b/client/cmdhfmf.c @@ -9,99 +9,45 @@ //----------------------------------------------------------------------------- #include +#include #include #include +#include #include "proxmark3.h" #include "cmdmain.h" #include "util.h" #include "ui.h" #include "mifarehost.h" #include "mifare.h" -#include "nonce2key/nonce2key.h" +#include "nonce2key.h" #define NESTED_SECTOR_RETRY 10 // how often we try mfested() until we give up static int CmdHelp(const char *Cmd); + int CmdHF14AMifare(const char *Cmd) { - uint32_t uid = 0; - uint32_t nt = 0, nr = 0; - uint64_t par_list = 0, ks_list = 0, r_key = 0; - int16_t isOK = 0; - - UsbCommand c = {CMD_READER_MIFARE, {true, 0, 0}}; - - // message - printf("-------------------------------------------------------------------------\n"); - printf("Executing command. Expected execution time: 25sec on average :-)\n"); - printf("Press button on the proxmark3 device to abort both proxmark3 and client.\n"); - printf("-------------------------------------------------------------------------\n"); - - - start: - clearCommandBuffer(); - SendCommand(&c); - - //flush queue - while (ukbhit()) { - int c = getchar(); (void) c; - } - - // wait cycle - while (true) { - printf("."); - fflush(stdout); - if (ukbhit()) { - getchar(); - printf("\naborted via keyboard!\n"); - break; - } - - UsbCommand resp; - if (WaitForResponseTimeout(CMD_ACK, &resp, 1000)) { - isOK = resp.arg[0]; - uid = (uint32_t)bytes_to_num(resp.d.asBytes + 0, 4); - nt = (uint32_t)bytes_to_num(resp.d.asBytes + 4, 4); - par_list = bytes_to_num(resp.d.asBytes + 8, 8); - ks_list = bytes_to_num(resp.d.asBytes + 16, 8); - nr = bytes_to_num(resp.d.asBytes + 24, 4); - printf("\n\n"); - switch (isOK) { - case -1 : PrintAndLog("Button pressed. Aborted.\n"); break; - case -2 : PrintAndLog("Card is not vulnerable to Darkside attack (doesn't send NACK on authentication requests).\n"); break; - case -3 : PrintAndLog("Card is not vulnerable to Darkside attack (its random number generator is not predictable).\n"); break; - case -4 : PrintAndLog("Card is not vulnerable to Darkside attack (its random number generator seems to be based on the wellknown"); - PrintAndLog("generating polynomial with 16 effective bits only, but shows unexpected behaviour.\n"); break; - default: ; - } - break; - } - } + int isOK = 0; + uint64_t key = 0; - printf("\n"); - - // error - if (isOK != 1) return 1; - - // execute original function from util nonce2key - if (nonce2key(uid, nt, nr, par_list, ks_list, &r_key)) { - isOK = 2; - PrintAndLog("Key not found (lfsr_common_prefix list is null). Nt=%08x", nt); - PrintAndLog("Failing is expected to happen in 25%% of all cases. Trying again with a different reader nonce..."); - c.arg[0] = false; - goto start; - } else { - isOK = 0; - printf("------------------------------------------------------------------\n"); - PrintAndLog("Found valid key:%012" PRIx64 " \n", r_key); + isOK = mfDarkside(&key); + switch (isOK) { + case -1 : PrintAndLog("Button pressed. Aborted."); return 1; + case -2 : PrintAndLog("Card is not vulnerable to Darkside attack (doesn't send NACK on authentication requests)."); return 1; + case -3 : PrintAndLog("Card is not vulnerable to Darkside attack (its random number generator is not predictable)."); return 1; + case -4 : PrintAndLog("Card is not vulnerable to Darkside attack (its random number generator seems to be based on the wellknown"); + PrintAndLog("generating polynomial with 16 effective bits only, but shows unexpected behaviour."); return 1; + case -5 : PrintAndLog("Aborted via keyboard."); return 1; + default : PrintAndLog("Found valid key:%012" PRIx64 "\n", key); } PrintAndLog(""); return 0; } + int CmdHF14AMfWrBl(const char *Cmd) { uint8_t blockNo = 0; @@ -688,8 +634,8 @@ int CmdHF14AMfNested(const char *Cmd) } } else { // ------------------------------------ multiple sectors working - clock_t time1; - time1 = clock(); + uint64_t msclock1; + msclock1 = msclock(); e_sector = calloc(SectorsCnt, sizeof(sector_t)); if (e_sector == NULL) return 1; @@ -759,7 +705,7 @@ int CmdHF14AMfNested(const char *Cmd) } } - printf("Time in nested: %1.3f (%1.3f sec per key)\n\n", ((float)clock() - time1)/CLOCKS_PER_SEC, ((float)clock() - time1)/iterations/CLOCKS_PER_SEC); + printf("Time in nested: %1.3f (%1.3f sec per key)\n\n", ((float)(msclock() - msclock1))/1000.0, ((float)(msclock() - msclock1))/iterations/1000.0); PrintAndLog("-----------------------------------------------\nIterations count: %d\n\n", iterations); //print them @@ -1088,7 +1034,7 @@ void readerAttack(nonces_t ar_resp[], bool setEmulatorMem, bool doStandardAttack } } } - } else if (tryMfk32_moebius(ar_resp[i+ATTACK_KEY_COUNT], &key)) { + } else if (mfkey32_moebius(ar_resp[i+ATTACK_KEY_COUNT], &key)) { uint8_t sectorNum = ar_resp[i+ATTACK_KEY_COUNT].sector; uint8_t keyType = ar_resp[i+ATTACK_KEY_COUNT].keytype; diff --git a/client/cmdhfmfu.c b/client/cmdhfmfu.c index b3912023..ed8c588d 100644 --- a/client/cmdhfmfu.c +++ b/client/cmdhfmfu.c @@ -8,12 +8,15 @@ // High frequency MIFARE ULTRALIGHT (C) commands //----------------------------------------------------------------------------- +#include "cmdhfmfu.h" + +#include +#include #include "proxmark3.h" #include "usb_cmd.h" #include "cmdmain.h" #include "ui.h" #include "loclass/des.h" -#include "cmdhfmfu.h" #include "cmdhfmf.h" #include "cmdhf14a.h" #include "mifare.h" diff --git a/client/cmdlfawid.c b/client/cmdlfawid.c index 1ace6bea..8843e9e0 100644 --- a/client/cmdlfawid.c +++ b/client/cmdlfawid.c @@ -10,6 +10,7 @@ // Low frequency AWID26 commands //----------------------------------------------------------------------------- +#include #include // sscanf #include "proxmark3.h" // Definitions, USB controls, etc #include "ui.h" // PrintAndLog diff --git a/client/cmdlfem4x.c b/client/cmdlfem4x.c index f9103126..6a076e33 100644 --- a/client/cmdlfem4x.c +++ b/client/cmdlfem4x.c @@ -14,6 +14,7 @@ #include "proxmark3.h" #include "ui.h" #include "util.h" +#include "data.h" #include "graph.h" #include "cmdparser.h" #include "cmddata.h" @@ -762,9 +763,10 @@ int CmdEM4x05dump(const char *Cmd) { int usage_lf_em_write(void) { PrintAndLog("Write EM4x05/EM4x69. Tag must be on antenna. "); PrintAndLog(""); - PrintAndLog("Usage: lf em 4x05writeword [h]
"); + PrintAndLog("Usage: lf em 4x05writeword [h] [s]
"); PrintAndLog("Options:"); PrintAndLog(" h - this help"); + PrintAndLog(" s - swap data bit order before write"); PrintAndLog(" address - memory address to write to. (0-15)"); PrintAndLog(" data - data to write (hex)"); PrintAndLog(" pwd - password (hex) (optional)"); @@ -777,18 +779,23 @@ int usage_lf_em_write(void) { int CmdEM4x05WriteWord(const char *Cmd) { uint8_t ctmp = param_getchar(Cmd, 0); if ( strlen(Cmd) == 0 || ctmp == 'H' || ctmp == 'h' ) return usage_lf_em_write(); - + bool usePwd = false; - + uint8_t addr = 16; // default to invalid address uint32_t data = 0xFFFFFFFF; // default to blank data uint32_t pwd = 0xFFFFFFFF; // default to blank password - - addr = param_get8ex(Cmd, 0, 16, 10); - data = param_get32ex(Cmd, 1, 0, 16); - pwd = param_get32ex(Cmd, 2, 1, 16); - - + char swap = 0; + + int p = 0; + swap = param_getchar(Cmd, 0); + if (swap == 's' || swap=='S') p++; + addr = param_get8ex(Cmd, p++, 16, 10); + data = param_get32ex(Cmd, p++, 0, 16); + pwd = param_get32ex(Cmd, p++, 1, 16); + + if (swap == 's' || swap=='S') data = SwapBits(data, 32); + if ( (addr > 15) ) { PrintAndLog("Address must be between 0 and 15"); return 1; @@ -797,15 +804,15 @@ int CmdEM4x05WriteWord(const char *Cmd) { PrintAndLog("Writing address %d data %08X", addr, data); else { usePwd = true; - PrintAndLog("Writing address %d data %08X using password %08X", addr, data, pwd); + PrintAndLog("Writing address %d data %08X using password %08X", addr, data, pwd); } - + uint16_t flag = (addr << 8 ) | usePwd; - + UsbCommand c = {CMD_EM4X_WRITE_WORD, {flag, data, pwd}}; clearCommandBuffer(); SendCommand(&c); - UsbCommand resp; + UsbCommand resp; if (!WaitForResponseTimeout(CMD_ACK, &resp, 2000)){ PrintAndLog("Error occurred, device did not respond during write operation."); return -1; @@ -813,7 +820,7 @@ int CmdEM4x05WriteWord(const char *Cmd) { if ( !downloadSamplesEM() ) { return -1; } - //check response for 00001010 for write confirmation! + //check response for 00001010 for write confirmation! //attempt demod: uint32_t dummy = 0; int result = demodEM4x05resp(&dummy,false); diff --git a/client/cmdlfhitag.c b/client/cmdlfhitag.c index ad8fd33b..47a85a1a 100644 --- a/client/cmdlfhitag.c +++ b/client/cmdlfhitag.c @@ -19,7 +19,6 @@ #include "util.h" #include "hitag2.h" #include "hitagS.h" -#include "sleep.h" #include "cmdmain.h" static int CmdHelp(const char *Cmd); diff --git a/client/cmdlfpresco.c b/client/cmdlfpresco.c index c6dbd756..8bb34149 100644 --- a/client/cmdlfpresco.c +++ b/client/cmdlfpresco.c @@ -8,6 +8,7 @@ //----------------------------------------------------------------------------- #include #include +#include #include "cmdlfpresco.h" #include "proxmark3.h" #include "ui.h" diff --git a/client/cmdlfpyramid.c b/client/cmdlfpyramid.c index 7c19fbdb..2494f265 100644 --- a/client/cmdlfpyramid.c +++ b/client/cmdlfpyramid.c @@ -8,6 +8,7 @@ //----------------------------------------------------------------------------- #include #include +#include #include "cmdlfpyramid.h" #include "proxmark3.h" #include "ui.h" diff --git a/client/cmdlft55xx.c b/client/cmdlft55xx.c index 27c84efa..b287ce28 100644 --- a/client/cmdlft55xx.c +++ b/client/cmdlft55xx.c @@ -10,6 +10,8 @@ #include #include #include +#include +#include #include "proxmark3.h" #include "ui.h" #include "graph.h" diff --git a/client/cmdlfvisa2000.c b/client/cmdlfvisa2000.c index 9ce35f98..292fa1a3 100644 --- a/client/cmdlfvisa2000.c +++ b/client/cmdlfvisa2000.c @@ -9,6 +9,9 @@ //----------------------------------------------------------------------------- #include "cmdlfvisa2000.h" + +#include +#include #include "proxmark3.h" #include "ui.h" #include "util.h" diff --git a/client/cmdmain.c b/client/cmdmain.c index 843f9301..44c11aeb 100644 --- a/client/cmdmain.c +++ b/client/cmdmain.c @@ -12,7 +12,6 @@ #include #include #include -#include "sleep.h" #include "cmdparser.h" #include "proxmark3.h" #include "data.h" diff --git a/client/flash.c b/client/flash.c index c840c922..0b940e99 100644 --- a/client/flash.c +++ b/client/flash.c @@ -12,8 +12,9 @@ #include #include #include +#include #include "proxmark3.h" -#include "sleep.h" +#include "util.h" #include "flash.h" #include "elf.h" #include "proxendian.h" diff --git a/client/flasher.c b/client/flasher.c index d6d37706..0c1dbd71 100644 --- a/client/flasher.c +++ b/client/flasher.c @@ -10,8 +10,8 @@ #include #include #include -#include "sleep.h" #include "proxmark3.h" +#include "util.h" #include "flash.h" #include "uart.h" #include "usb_cmd.h" diff --git a/client/hid-flasher/flash.c b/client/hid-flasher/flash.c index 6670d637..da0a17b6 100644 --- a/client/hid-flasher/flash.c +++ b/client/hid-flasher/flash.c @@ -11,7 +11,6 @@ #include #include #include -#include "sleep.h" #include "proxusb.h" #include "flash.h" #include "elf.h" diff --git a/client/hid-flasher/flasher.c b/client/hid-flasher/flasher.c index a4a0e85e..2f0c2007 100644 --- a/client/hid-flasher/flasher.c +++ b/client/hid-flasher/flasher.c @@ -9,7 +9,6 @@ #include #include #include -#include "sleep.h" #include "proxusb.h" #include "flash.h" diff --git a/client/hid-flasher/proxusb.c b/client/hid-flasher/proxusb.c index 3c2b20b4..04dbb784 100644 --- a/client/hid-flasher/proxusb.c +++ b/client/hid-flasher/proxusb.c @@ -18,7 +18,6 @@ #include #include -#include "sleep.h" #include "proxusb.h" #include "proxmark3.h" #include "usb_cmd.h" diff --git a/client/loclass/elite_crack.c b/client/loclass/elite_crack.c index e9814e95..e52c9a6a 100644 --- a/client/loclass/elite_crack.c +++ b/client/loclass/elite_crack.c @@ -40,7 +40,7 @@ #include #include #include -#include +#include "util.h" #include "cipherutils.h" #include "cipher.h" #include "ikeys.h" @@ -512,7 +512,7 @@ int bruteforceDump(uint8_t dump[], size_t dumpsize, uint16_t keytable[]) uint8_t i; int errors = 0; size_t itemsize = sizeof(dumpdata); - clock_t t1 = clock(); + uint64_t t1 = msclock(); dumpdata* attack = (dumpdata* ) malloc(itemsize); @@ -522,9 +522,9 @@ int bruteforceDump(uint8_t dump[], size_t dumpsize, uint16_t keytable[]) errors += bruteforceItem(*attack, keytable); } free(attack); - t1 = clock() - t1; - float diff = ((float)t1 / CLOCKS_PER_SEC ); - prnlog("\nPerformed full crack in %f seconds",diff); + t1 = msclock() - t1; + float diff = (float)t1 / 1000.0; + prnlog("\nPerformed full crack in %f seconds", diff); // Pick out the first 16 bytes of the keytable. // The keytable is now in 16-bit ints, where the upper 8 bits diff --git a/client/mifarehost.c b/client/mifarehost.c index 5e0f4760..cbd79cf7 100644 --- a/client/mifarehost.c +++ b/client/mifarehost.c @@ -13,7 +13,7 @@ #include #include -#include "nonce2key/crapto1.h" +#include "crapto1/crapto1.h" #include "proxmark3.h" #include "usb_cmd.h" #include "cmdmain.h" @@ -33,7 +33,194 @@ #define TRACE_ERROR 0xFF -// MIFARE +static int compare_uint64(const void *a, const void *b) { + // didn't work: (the result is truncated to 32 bits) + //return (*(int64_t*)b - *(int64_t*)a); + + // better: + if (*(uint64_t*)b == *(uint64_t*)a) return 0; + else if (*(uint64_t*)b < *(uint64_t*)a) return 1; + else return -1; +} + + +// create the intersection (common members) of two sorted lists. Lists are terminated by -1. Result will be in list1. Number of elements is returned. +static uint32_t intersection(uint64_t *list1, uint64_t *list2) +{ + if (list1 == NULL || list2 == NULL) { + return 0; + } + uint64_t *p1, *p2, *p3; + p1 = p3 = list1; + p2 = list2; + + while ( *p1 != -1 && *p2 != -1 ) { + if (compare_uint64(p1, p2) == 0) { + *p3++ = *p1++; + p2++; + } + else { + while (compare_uint64(p1, p2) < 0) ++p1; + while (compare_uint64(p1, p2) > 0) ++p2; + } + } + *p3 = -1; + return p3 - list1; +} + + +// Darkside attack (hf mf mifare) +static uint32_t nonce2key(uint32_t uid, uint32_t nt, uint32_t nr, uint64_t par_info, uint64_t ks_info, uint64_t **keys) { + struct Crypto1State *states; + uint32_t i, pos, rr; //nr_diff; + uint8_t bt, ks3x[8], par[8][8]; + uint64_t key_recovered; + static uint64_t *keylist; + rr = 0; + + // Reset the last three significant bits of the reader nonce + nr &= 0xffffff1f; + + for (pos=0; pos<8; pos++) { + ks3x[7-pos] = (ks_info >> (pos*8)) & 0x0f; + bt = (par_info >> (pos*8)) & 0xff; + for (i=0; i<8; i++) { + par[7-pos][i] = (bt >> i) & 0x01; + } + } + + states = lfsr_common_prefix(nr, rr, ks3x, par, (par_info == 0)); + + if (states == NULL) { + *keys = NULL; + return 0; + } + + keylist = (uint64_t*)states; + + for (i = 0; keylist[i]; i++) { + lfsr_rollback_word(states+i, uid^nt, 0); + crypto1_get_lfsr(states+i, &key_recovered); + keylist[i] = key_recovered; + } + keylist[i] = -1; + + *keys = keylist; + return i; +} + + +int mfDarkside(uint64_t *key) +{ + uint32_t uid = 0; + uint32_t nt = 0, nr = 0; + uint64_t par_list = 0, ks_list = 0; + uint64_t *keylist = NULL, *last_keylist = NULL; + uint32_t keycount = 0; + int16_t isOK = 0; + + UsbCommand c = {CMD_READER_MIFARE, {true, 0, 0}}; + + // message + printf("-------------------------------------------------------------------------\n"); + printf("Executing command. Expected execution time: 25sec on average\n"); + printf("Press button on the proxmark3 device to abort both proxmark3 and client.\n"); + printf("-------------------------------------------------------------------------\n"); + + + while (true) { + clearCommandBuffer(); + SendCommand(&c); + + //flush queue + while (ukbhit()) { + int c = getchar(); (void) c; + } + + // wait cycle + while (true) { + printf("."); + fflush(stdout); + if (ukbhit()) { + return -5; + break; + } + + UsbCommand resp; + if (WaitForResponseTimeout(CMD_ACK, &resp, 1000)) { + isOK = resp.arg[0]; + if (isOK < 0) { + return isOK; + } + uid = (uint32_t)bytes_to_num(resp.d.asBytes + 0, 4); + nt = (uint32_t)bytes_to_num(resp.d.asBytes + 4, 4); + par_list = bytes_to_num(resp.d.asBytes + 8, 8); + ks_list = bytes_to_num(resp.d.asBytes + 16, 8); + nr = bytes_to_num(resp.d.asBytes + 24, 4); + break; + } + } + + if (par_list == 0 && c.arg[0] == true) { + PrintAndLog("Parity is all zero. Most likely this card sends NACK on every failed authentication."); + PrintAndLog("Attack will take a few seconds longer because we need two consecutive successful runs."); + } + c.arg[0] = false; + + keycount = nonce2key(uid, nt, nr, par_list, ks_list, &keylist); + + if (keycount == 0) { + PrintAndLog("Key not found (lfsr_common_prefix list is null). Nt=%08x", nt); + PrintAndLog("This is expected to happen in 25%% of all cases. Trying again with a different reader nonce..."); + continue; + } + + qsort(keylist, keycount, sizeof(*keylist), compare_uint64); + keycount = intersection(last_keylist, keylist); + if (keycount == 0) { + free(last_keylist); + last_keylist = keylist; + continue; + } + + if (keycount > 1) { + PrintAndLog("Found %u possible keys. Trying to authenticate with each of them ...\n", keycount); + } else { + PrintAndLog("Found a possible key. Trying to authenticate...\n"); + } + + *key = -1; + uint8_t keyBlock[USB_CMD_DATA_SIZE]; + int max_keys = USB_CMD_DATA_SIZE/6; + for (int i = 0; i < keycount; i += max_keys) { + int size = keycount - i > max_keys ? max_keys : keycount - i; + for (int j = 0; j < size; j++) { + if (last_keylist == NULL) { + num_to_bytes(keylist[i*max_keys + j], 6, keyBlock); + } else { + num_to_bytes(last_keylist[i*max_keys + j], 6, keyBlock); + } + } + if (!mfCheckKeys(0, 0, false, size, keyBlock, key)) { + break; + } + } + + if (*key != -1) { + free(last_keylist); + free(keylist); + break; + } else { + PrintAndLog("Authentication failed. Trying again..."); + free(last_keylist); + last_keylist = keylist; + } + } + + return 0; +} + + int mfCheckKeys (uint8_t blockNo, uint8_t keyType, bool clear_trace, uint8_t keycnt, uint8_t * keyBlock, uint64_t * key){ *key = 0; @@ -49,16 +236,6 @@ int mfCheckKeys (uint8_t blockNo, uint8_t keyType, bool clear_trace, uint8_t key return 0; } -int compar_int(const void * a, const void * b) { - // didn't work: (the result is truncated to 32 bits) - //return (*(uint64_t*)b - *(uint64_t*)a); - - // better: - if (*(uint64_t*)b == *(uint64_t*)a) return 0; - else if (*(uint64_t*)b > *(uint64_t*)a) return 1; - else return -1; -} - // Compare 16 Bits out of cryptostate int Compare16Bits(const void * a, const void * b) { if ((*(uint64_t*)b & 0x00ff000000ff0000) == (*(uint64_t*)a & 0x00ff000000ff0000)) return 0; @@ -100,7 +277,7 @@ void* nested_worker_thread(void *arg) return statelist->head.slhead; } -int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t * resultKey, bool calibrate) +int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t *resultKey, bool calibrate) { uint16_t i; uint32_t uid; @@ -178,8 +355,8 @@ int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo while (Compare16Bits(p1, p2) == 1) p2++; } } - p3->even = 0; p3->odd = 0; - p4->even = 0; p4->odd = 0; + *(uint64_t*)p3 = -1; + *(uint64_t*)p4 = -1; statelists[0].len = p3 - statelists[0].head.slhead; statelists[1].len = p4 - statelists[1].head.slhead; statelists[0].tail.sltail=--p3; @@ -187,24 +364,9 @@ int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo // the statelists now contain possible keys. The key we are searching for must be in the // intersection of both lists. Create the intersection: - qsort(statelists[0].head.keyhead, statelists[0].len, sizeof(uint64_t), compar_int); - qsort(statelists[1].head.keyhead, statelists[1].len, sizeof(uint64_t), compar_int); - - uint64_t *p5, *p6, *p7; - p5 = p7 = statelists[0].head.keyhead; - p6 = statelists[1].head.keyhead; - while (p5 <= statelists[0].tail.keytail && p6 <= statelists[1].tail.keytail) { - if (compar_int(p5, p6) == 0) { - *p7++ = *p5++; - p6++; - } - else { - while (compar_int(p5, p6) == -1) p5++; - while (compar_int(p5, p6) == 1) p6++; - } - } - statelists[0].len = p7 - statelists[0].head.keyhead; - statelists[0].tail.keytail=--p7; + qsort(statelists[0].head.keyhead, statelists[0].len, sizeof(uint64_t), compare_uint64); + qsort(statelists[1].head.keyhead, statelists[1].len, sizeof(uint64_t), compare_uint64); + statelists[0].len = intersection(statelists[0].head.keyhead, statelists[1].head.keyhead); memset(resultKey, 0, 6); // The list may still contain several key candidates. Test each of them with mfCheckKeys diff --git a/client/mifarehost.h b/client/mifarehost.h index e628ba3a..a9db4ec3 100644 --- a/client/mifarehost.h +++ b/client/mifarehost.h @@ -22,8 +22,9 @@ extern char logHexFileName[FILE_PATH_SIZE]; -extern int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t * ResultKeys, bool calibrate); -extern int mfCheckKeys (uint8_t blockNo, uint8_t keyType, bool clear_trace, uint8_t keycnt, uint8_t * keyBlock, uint64_t * key); +extern int mfDarkside(uint64_t *key); +extern int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t *ResultKeys, bool calibrate); +extern int mfCheckKeys (uint8_t blockNo, uint8_t keyType, bool clear_trace, uint8_t keycnt, uint8_t *keyBlock, uint64_t *key); extern int mfEmlGetMem(uint8_t *data, int blockNum, int blocksCount); extern int mfEmlSetMem(uint8_t *data, int blockNum, int blocksCount); diff --git a/client/nonce2key.c b/client/nonce2key.c new file mode 100644 index 00000000..acd551e4 --- /dev/null +++ b/client/nonce2key.c @@ -0,0 +1,137 @@ +//----------------------------------------------------------------------------- +// Merlok - June 2011 +// Roel - Dec 2009 +// Unknown author +// +// This code is licensed to you under the terms of the GNU GPL, version 2 or, +// at your option, any later version. See the LICENSE.txt file for the text of +// the license. +//----------------------------------------------------------------------------- +// MIFARE Darkside hack +//----------------------------------------------------------------------------- + +#include "nonce2key.h" + +#include +#include +#include +#include "mifarehost.h" +#include "util.h" +#include "crapto1/crapto1.h" + +// recover key from 2 different reader responses on same tag challenge +bool mfkey32(nonces_t data, uint64_t *outputkey) { + struct Crypto1State *s,*t; + uint64_t outkey = 0; + uint64_t key = 0; // recovered key + bool isSuccess = false; + uint8_t counter = 0; + + uint64_t t1 = msclock(); + + s = lfsr_recovery32(data.ar ^ prng_successor(data.nonce, 64), 0); + + for(t = s; t->odd | t->even; ++t) { + lfsr_rollback_word(t, 0, 0); + lfsr_rollback_word(t, data.nr, 1); + lfsr_rollback_word(t, data.cuid ^ data.nonce, 0); + crypto1_get_lfsr(t, &key); + crypto1_word(t, data.cuid ^ data.nonce, 0); + crypto1_word(t, data.nr2, 1); + if (data.ar2 == (crypto1_word(t, 0, 0) ^ prng_successor(data.nonce, 64))) { + //PrintAndLog("Found Key: [%012" PRIx64 "]",key); + outkey = key; + counter++; + if (counter == 20) break; + } + } + isSuccess = (counter == 1); + t1 = msclock() - t1; + //if ( t1 > 0 ) PrintAndLog("Time in mfkey32: %.1f seconds \nFound %d possible keys", (float)t1/1000.0, counter); + *outputkey = ( isSuccess ) ? outkey : 0; + crypto1_destroy(s); + /* //un-comment to save all keys to a stats.txt file + FILE *fout; + if ((fout = fopen("stats.txt","ab")) == NULL) { + PrintAndLog("Could not create file name stats.txt"); + return 1; + } + fprintf(fout, "mfkey32,%d,%08x,%d,%s,%04x%08x,%.0Lf\r\n", counter, data.cuid, data.sector, (data.keytype) ? "B" : "A", (uint32_t)(outkey>>32) & 0xFFFF,(uint32_t)(outkey&0xFFFFFFFF),(long double)t1); + fclose(fout); + */ + return isSuccess; +} + +// recover key from 2 reader responses on 2 different tag challenges +bool mfkey32_moebius(nonces_t data, uint64_t *outputkey) { + struct Crypto1State *s, *t; + uint64_t outkey = 0; + uint64_t key = 0; // recovered key + bool isSuccess = false; + int counter = 0; + + //PrintAndLog("Enter mfkey32_moebius"); + uint64_t t1 = msclock(); + + s = lfsr_recovery32(data.ar ^ prng_successor(data.nonce, 64), 0); + + for(t = s; t->odd | t->even; ++t) { + lfsr_rollback_word(t, 0, 0); + lfsr_rollback_word(t, data.nr, 1); + lfsr_rollback_word(t, data.cuid ^ data.nonce, 0); + crypto1_get_lfsr(t, &key); + + crypto1_word(t, data.cuid ^ data.nonce2, 0); + crypto1_word(t, data.nr2, 1); + if (data.ar2 == (crypto1_word(t, 0, 0) ^ prng_successor(data.nonce2, 64))) { + //PrintAndLog("Found Key: [%012" PRIx64 "]",key); + outkey=key; + ++counter; + if (counter==20) + break; + } + } + isSuccess = (counter == 1); + t1 = msclock() - t1; + // PrintAndLog("Time in mfkey32_moebius: %.1f seconds \nFound %d possible keys", (float)t1/1000.0, counter); + *outputkey = ( isSuccess ) ? outkey : 0; + crypto1_destroy(s); + /* // un-comment to output all keys to stats.txt + FILE *fout; + if ((fout = fopen("stats.txt","ab")) == NULL) { + PrintAndLog("Could not create file name stats.txt"); + return 1; + } + fprintf(fout, "moebius,%d,%08x,%d,%s,%04x%08x,%0.Lf\r\n", counter, data.cuid, data.sector, (data.keytype) ? "B" : "A", (uint32_t) (outkey>>32),(uint32_t)(outkey&0xFFFFFFFF),(long double)t1); + fclose(fout); + */ + return isSuccess; +} + +// recover key from reader response and tag response of one authentication sequence +int mfkey64(nonces_t data, uint64_t *outputkey){ + uint64_t key = 0; // recovered key + uint32_t ks2; // keystream used to encrypt reader response + uint32_t ks3; // keystream used to encrypt tag response + struct Crypto1State *revstate; + + // PrintAndLog("Enter mfkey64"); + uint64_t t1 = msclock(); + + // Extract the keystream from the messages + ks2 = data.ar ^ prng_successor(data.nonce, 64); + ks3 = data.at ^ prng_successor(data.nonce, 96); + revstate = lfsr_recovery64(ks2, ks3); + lfsr_rollback_word(revstate, 0, 0); + lfsr_rollback_word(revstate, 0, 0); + lfsr_rollback_word(revstate, data.nr, 1); + lfsr_rollback_word(revstate, data.cuid ^ data.nonce, 0); + crypto1_get_lfsr(revstate, &key); + // PrintAndLog("Found Key: [%012" PRIx64 "]", key); + crypto1_destroy(revstate); + *outputkey = key; + + t1 = msclock() - t1; + // PrintAndLog("Time in mfkey64: %.1f seconds \n", (float)t1/1000.0); + return 0; +} diff --git a/client/nonce2key.h b/client/nonce2key.h new file mode 100644 index 00000000..795f239d --- /dev/null +++ b/client/nonce2key.h @@ -0,0 +1,36 @@ +//----------------------------------------------------------------------------- +// Merlok - June 2011 +// Roel - Dec 2009 +// Unknown author +// +// This code is licensed to you under the terms of the GNU GPL, version 2 or, +// at your option, any later version. See the LICENSE.txt file for the text of +// the license. +//----------------------------------------------------------------------------- +// MIFARE Darkside hack +//----------------------------------------------------------------------------- + +#ifndef __NONCE2KEY_H +#define __NONCE2KEY_H + +#include +#include + +typedef struct { + uint32_t cuid; + uint8_t sector; + uint8_t keytype; + uint32_t nonce; + uint32_t ar; + uint32_t nr; + uint32_t at; + uint32_t nonce2; + uint32_t ar2; + uint32_t nr2; + } nonces_t; + +bool mfkey32(nonces_t data, uint64_t *outputkey); +bool mfkey32_moebius(nonces_t data, uint64_t *outputkey); +int mfkey64(nonces_t data, uint64_t *outputkey); + +#endif diff --git a/client/nonce2key/crapto1.c b/client/nonce2key/crapto1.c deleted file mode 100644 index 1015e27a..00000000 --- a/client/nonce2key/crapto1.c +++ /dev/null @@ -1,573 +0,0 @@ -/* crapto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, - Boston, MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#if !defined LOWMEM && defined __GNUC__ -static uint8_t filterlut[1 << 20]; -static void __attribute__((constructor)) fill_lut() -{ - uint32_t i; - for(i = 0; i < 1 << 20; ++i) - filterlut[i] = filter(i); -} -#define filter(x) (filterlut[(x) & 0xfffff]) -#endif - - - -typedef struct bucket { - uint32_t *head; - uint32_t *bp; -} bucket_t; - -typedef bucket_t bucket_array_t[2][0x100]; - -typedef struct bucket_info { - struct { - uint32_t *head, *tail; - } bucket_info[2][0x100]; - uint32_t numbuckets; - } bucket_info_t; - - -static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop, - uint32_t* const ostart, uint32_t* const ostop, - bucket_info_t *bucket_info, bucket_array_t bucket) -{ - uint32_t *p1, *p2; - uint32_t *start[2]; - uint32_t *stop[2]; - - start[0] = estart; - stop[0] = estop; - start[1] = ostart; - stop[1] = ostop; - - // init buckets to be empty - for (uint32_t i = 0; i < 2; i++) { - for (uint32_t j = 0x00; j <= 0xff; j++) { - bucket[i][j].bp = bucket[i][j].head; - } - } - - // sort the lists into the buckets based on the MSB (contribution bits) - for (uint32_t i = 0; i < 2; i++) { - for (p1 = start[i]; p1 <= stop[i]; p1++) { - uint32_t bucket_index = (*p1 & 0xff000000) >> 24; - *(bucket[i][bucket_index].bp++) = *p1; - } - } - - - // write back intersecting buckets as sorted list. - // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets. - uint32_t nonempty_bucket; - for (uint32_t i = 0; i < 2; i++) { - p1 = start[i]; - nonempty_bucket = 0; - for (uint32_t j = 0x00; j <= 0xff; j++) { - if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only - bucket_info->bucket_info[i][nonempty_bucket].head = p1; - for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++); - bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1; - nonempty_bucket++; - } - } - bucket_info->numbuckets = nonempty_bucket; - } -} - -/** binsearch - * Binary search for the first occurence of *stop's MSB in sorted [start,stop] - */ -static inline uint32_t* -binsearch(uint32_t *start, uint32_t *stop) -{ - uint32_t mid, val = *stop & 0xff000000; - while(start != stop) - if(start[mid = (stop - start) >> 1] > val) - stop = &start[mid]; - else - start += mid + 1; - - return start; -} - -/** update_contribution - * helper, calculates the partial linear feedback contributions and puts in MSB - */ -static inline void -update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) -{ - uint32_t p = *item >> 25; - - p = p << 1 | parity(*item & mask1); - p = p << 1 | parity(*item & mask2); - *item = p << 24 | (*item & 0xffffff); -} - -/** extend_table - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void -extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) -{ - in <<= 24; - - for(uint32_t *p = tbl; p <= *end; p++) { - *p <<= 1; - if(filter(*p) != filter(*p | 1)) { // replace - *p |= filter(*p) ^ bit; - update_contribution(p, m1, m2); - *p ^= in; - } else if(filter(*p) == bit) { // insert - *++*end = p[1]; - p[1] = p[0] | 1; - update_contribution(p, m1, m2); - *p++ ^= in; - update_contribution(p, m1, m2); - *p ^= in; - } else { // drop - *p-- = *(*end)--; - } - } - -} - - -/** extend_table_simple - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void -extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) -{ - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) - if(filter(*tbl) ^ filter(*tbl | 1)) { // replace - *tbl |= filter(*tbl) ^ bit; - } else if(filter(*tbl) == bit) { // insert - *++*end = *++tbl; - *tbl = tbl[-1] | 1; - } else // drop - *tbl-- = *(*end)--; -} - - -/** recover - * recursively narrow down the search space, 4 bits of keystream at a time - */ -static struct Crypto1State* -recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, - uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem, - struct Crypto1State *sl, uint32_t in, bucket_array_t bucket) -{ - uint32_t *o, *e; - bucket_info_t bucket_info; - - if(rem == -1) { - for(e = e_head; e <= e_tail; ++e) { - *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4); - for(o = o_head; o <= o_tail; ++o, ++sl) { - sl->even = *o; - sl->odd = *e ^ parity(*o & LF_POLY_ODD); - } - } - sl->odd = sl->even = 0; - return sl; - } - - for(uint32_t i = 0; i < 4 && rem--; i++) { - extend_table(o_head, &o_tail, (oks >>= 1) & 1, - LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0); - if(o_head > o_tail) - return sl; - - extend_table(e_head, &e_tail, (eks >>= 1) & 1, - LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 3); - if(e_head > e_tail) - return sl; - } - - bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket); - - for (int i = bucket_info.numbuckets - 1; i >= 0; i--) { - sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks, - bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks, - rem, sl, in, bucket); - } - - return sl; -} -/** lfsr_recovery - * recover the state of the lfsr given 32 bits of the keystream - * additionally you can use the in parameter to specify the value - * that was fed into the lfsr at the time the keystream was generated - */ -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) -{ - struct Crypto1State *statelist; - uint32_t *odd_head = 0, *odd_tail = 0, oks = 0; - uint32_t *even_head = 0, *even_tail = 0, eks = 0; - int i; - - // split the keystream into an odd and even part - for(i = 31; i >= 0; i -= 2) - oks = oks << 1 | BEBIT(ks2, i); - for(i = 30; i >= 0; i -= 2) - eks = eks << 1 | BEBIT(ks2, i); - - odd_head = odd_tail = malloc(sizeof(uint32_t) << 21); - even_head = even_tail = malloc(sizeof(uint32_t) << 21); - statelist = malloc(sizeof(struct Crypto1State) << 18); - if(!odd_tail-- || !even_tail-- || !statelist) { - goto out; - } - statelist->odd = statelist->even = 0; - - // allocate memory for out of place bucket_sort - bucket_array_t bucket; - for (uint32_t i = 0; i < 2; i++) - for (uint32_t j = 0; j <= 0xff; j++) { - bucket[i][j].head = malloc(sizeof(uint32_t)<<14); - if (!bucket[i][j].head) { - goto out; - } - } - - - // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream - for(i = 1 << 20; i >= 0; --i) { - if(filter(i) == (oks & 1)) - *++odd_tail = i; - if(filter(i) == (eks & 1)) - *++even_tail = i; - } - - // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even): - for(i = 0; i < 4; i++) { - extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1); - extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1); - } - - // the statelists now contain all states which could have generated the last 10 Bits of the keystream. - // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in" - // parameter into account. - - in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping - - recover(odd_head, odd_tail, oks, - even_head, even_tail, eks, 11, statelist, in << 1, bucket); - - -out: - free(odd_head); - free(even_head); - for (uint32_t i = 0; i < 2; i++) - for (uint32_t j = 0; j <= 0xff; j++) - free(bucket[i][j].head); - - return statelist; -} - -static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214, - 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83, - 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA}; -static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60, - 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8, - 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20, - 0x7EC7EE90, 0x7F63F748, 0x79117020}; -static const uint32_t T1[] = { - 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66, - 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B, - 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615, - 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C}; -static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0, - 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268, - 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0, - 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0, - 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950, - 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0}; -static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD}; -static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0}; -/** Reverse 64 bits of keystream into possible cipher states - * Variation mentioned in the paper. Somewhat optimized version - */ -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3) -{ - struct Crypto1State *statelist, *sl; - uint8_t oks[32], eks[32], hi[32]; - uint32_t low = 0, win = 0; - uint32_t *tail, table[1 << 16]; - int i, j; - - sl = statelist = malloc(sizeof(struct Crypto1State) << 4); - if(!sl) - return 0; - sl->odd = sl->even = 0; - - for(i = 30; i >= 0; i -= 2) { - oks[i >> 1] = BIT(ks2, i ^ 24); - oks[16 + (i >> 1)] = BIT(ks3, i ^ 24); - } - for(i = 31; i >= 0; i -= 2) { - eks[i >> 1] = BIT(ks2, i ^ 24); - eks[16 + (i >> 1)] = BIT(ks3, i ^ 24); - } - - for(i = 0xfffff; i >= 0; --i) { - if (filter(i) != oks[0]) - continue; - - *(tail = table) = i; - for(j = 1; tail >= table && j < 29; ++j) - extend_table_simple(table, &tail, oks[j]); - - if(tail < table) - continue; - - for(j = 0; j < 19; ++j) - low = low << 1 | parity(i & S1[j]); - for(j = 0; j < 32; ++j) - hi[j] = parity(i & T1[j]); - - for(; tail >= table; --tail) { - for(j = 0; j < 3; ++j) { - *tail = *tail << 1; - *tail |= parity((i & C1[j]) ^ (*tail & C2[j])); - if(filter(*tail) != oks[29 + j]) - goto continue2; - } - - for(j = 0; j < 19; ++j) - win = win << 1 | parity(*tail & S2[j]); - - win ^= low; - for(j = 0; j < 32; ++j) { - win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]); - if(filter(win) != eks[j]) - goto continue2; - } - - *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail); - sl->odd = *tail ^ parity(LF_POLY_ODD & win); - sl->even = win; - ++sl; - sl->odd = sl->even = 0; - continue2:; - } - } - return statelist; -} - -/** lfsr_rollback_bit - * Rollback the shift register in order to get previous states - */ -void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb) -{ - int out; - uint32_t tmp; - - s->odd &= 0xffffff; - tmp = s->odd; - s->odd = s->even; - s->even = tmp; - - out = s->even & 1; - out ^= LF_POLY_EVEN & (s->even >>= 1); - out ^= LF_POLY_ODD & s->odd; - out ^= !!in; - out ^= filter(s->odd) & !!fb; - - s->even |= parity(out) << 23; -} -/** lfsr_rollback_byte - * Rollback the shift register in order to get previous states - */ -void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb) -{ - int i; - for (i = 7; i >= 0; --i) - lfsr_rollback_bit(s, BEBIT(in, i), fb); -} -/** lfsr_rollback_word - * Rollback the shift register in order to get previous states - */ -void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb) -{ - int i; - for (i = 31; i >= 0; --i) - lfsr_rollback_bit(s, BEBIT(in, i), fb); -} - -/** nonce_distance - * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y - */ -static uint16_t *dist = 0; -int nonce_distance(uint32_t from, uint32_t to) -{ - uint16_t x, i; - if(!dist) { - dist = malloc(2 << 16); - if(!dist) - return -1; - for (x = i = 1; i; ++i) { - dist[(x & 0xff) << 8 | x >> 8] = i; - x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15; - } - } - return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535; -} - - -static uint32_t fastfwd[2][8] = { - { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB}, - { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}}; - - -/** lfsr_prefix_ks - * - * Is an exported helper function from the common prefix attack - * Described in the "dark side" paper. It returns an -1 terminated array - * of possible partial(21 bit) secret state. - * The required keystream(ks) needs to contain the keystream that was used to - * encrypt the NACK which is observed when varying only the 4 last bits of Nr - * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3 - */ -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd) -{ - uint32_t *candidates = malloc(4 << 21); - uint32_t c, entry; - int size, i; - - if(!candidates) - return 0; - - size = (1 << 21) - 1; - for(i = 0; i <= size; ++i) - candidates[i] = i; - - for(c = 0; c < 8; ++c) - for(i = 0;i <= size; ++i) { - entry = candidates[i] ^ fastfwd[isodd][c]; - - if(filter(entry >> 1) == BIT(ks[c], isodd)) - if(filter(entry) == BIT(ks[c], isodd + 2)) - continue; - - candidates[i--] = candidates[size--]; - } - - candidates[size + 1] = -1; - - return candidates; -} - -/** brute_top - * helper function which eliminates possible secret states using parity bits - */ -static struct Crypto1State* -brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8], - uint32_t odd, uint32_t even, struct Crypto1State* sl, uint8_t no_chk) -{ - struct Crypto1State s; - uint32_t ks1, nr, ks2, rr, ks3, good, c; - - for(c = 0; c < 8; ++c) { - s.odd = odd ^ fastfwd[1][c]; - s.even = even ^ fastfwd[0][c]; - - lfsr_rollback_bit(&s, 0, 0); - lfsr_rollback_bit(&s, 0, 0); - lfsr_rollback_bit(&s, 0, 0); - - lfsr_rollback_word(&s, 0, 0); - lfsr_rollback_word(&s, prefix | c << 5, 1); - - sl->odd = s.odd; - sl->even = s.even; - - if (no_chk) - break; - - ks1 = crypto1_word(&s, prefix | c << 5, 1); - ks2 = crypto1_word(&s,0,0); - ks3 = crypto1_word(&s, 0,0); - nr = ks1 ^ (prefix | c << 5); - rr = ks2 ^ rresp; - - good = 1; - good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24); - good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16); - good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8); - good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0); - good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24); - - if(!good) - return sl; - } - - return ++sl; -} - - -/** lfsr_common_prefix - * Implentation of the common prefix attack. - * Requires the 28 bit constant prefix used as reader nonce (pfx) - * The reader response used (rr) - * The keystream used to encrypt the observed NACK's (ks) - * The parity bits (par) - * It returns a zero terminated list of possible cipher states after the - * tag nonce was fed in - */ -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par) -{ - struct Crypto1State *statelist, *s; - uint32_t *odd, *even, *o, *e, top; - - odd = lfsr_prefix_ks(ks, 1); - even = lfsr_prefix_ks(ks, 0); - - statelist = malloc((sizeof *statelist) << 21); //how large should be? - if(!statelist || !odd || !even) - { - free(statelist); - free(odd); - free(even); - return 0; - } - - s = statelist; - for(o = odd; *o != -1; ++o) - for(e = even; *e != -1; ++e) - for(top = 0; top < 64; ++top) { - *o = (*o & 0x1fffff) | (top << 21); - *e = (*e & 0x1fffff) | (top >> 3) << 21; - s = brute_top(pfx, rr, par, *o, *e, s, no_par); - } - - s->odd = s->even = -1; - //printf("state count = %d\n",s-statelist); - - free(odd); - free(even); - - return statelist; -} diff --git a/client/nonce2key/crapto1.h b/client/nonce2key/crapto1.h deleted file mode 100644 index f6653124..00000000 --- a/client/nonce2key/crapto1.h +++ /dev/null @@ -1,97 +0,0 @@ -/* crapto1.h - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#ifndef CRAPTO1_INCLUDED -#define CRAPTO1_INCLUDED -#include -#ifdef __cplusplus -extern "C" { -#endif - -struct Crypto1State {uint32_t odd, even;}; -struct Crypto1State* crypto1_create(uint64_t); -void crypto1_destroy(struct Crypto1State*); -void crypto1_get_lfsr(struct Crypto1State*, uint64_t*); -uint8_t crypto1_bit(struct Crypto1State*, uint8_t, int); -uint8_t crypto1_byte(struct Crypto1State*, uint8_t, int); -uint32_t crypto1_word(struct Crypto1State*, uint32_t, int); -uint32_t prng_successor(uint32_t x, uint32_t n); - -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in); -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3); -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd); -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par); - - -void lfsr_rollback_bit(struct Crypto1State* s, uint32_t in, int fb); -void lfsr_rollback_byte(struct Crypto1State* s, uint32_t in, int fb); -void lfsr_rollback_word(struct Crypto1State* s, uint32_t in, int fb); -int nonce_distance(uint32_t from, uint32_t to); -#define SWAPENDIAN(x)\ - (x = (x >> 8 & 0xff00ff) | (x & 0xff00ff) << 8, x = x >> 16 | x << 16) - -#define FOREACH_VALID_NONCE(N, FILTER, FSIZE)\ - uint32_t __n = 0,__M = 0, N = 0;\ - int __i;\ - for(; __n < 1 << 16; N = prng_successor(__M = ++__n, 16))\ - for(__i = FSIZE - 1; __i >= 0; __i--)\ - if(BIT(FILTER, __i) ^ parity(__M & 0xFF01))\ - break;\ - else if(__i)\ - __M = prng_successor(__M, (__i == 7) ? 48 : 8);\ - else - -#define LF_POLY_ODD (0x29CE5C) -#define LF_POLY_EVEN (0x870804) -#define BIT(x, n) ((x) >> (n) & 1) -#define BEBIT(x, n) BIT(x, (n) ^ 24) -static inline int parity(uint32_t x) -{ -#if !defined __i386__ || !defined __GNUC__ - x ^= x >> 16; - x ^= x >> 8; - x ^= x >> 4; - return BIT(0x6996, x & 0xf); -#else - __asm( "movl %1, %%eax\n" - "mov %%ax, %%cx\n" - "shrl $0x10, %%eax\n" - "xor %%ax, %%cx\n" - "xor %%ch, %%cl\n" - "setpo %%al\n" - "movzx %%al, %0\n": "=r"(x) : "r"(x): "eax","ecx"); - return x; -#endif -} -static inline int filter(uint32_t const x) -{ - uint32_t f; - - f = 0xf22c0 >> (x & 0xf) & 16; - f |= 0x6c9c0 >> (x >> 4 & 0xf) & 8; - f |= 0x3c8b0 >> (x >> 8 & 0xf) & 4; - f |= 0x1e458 >> (x >> 12 & 0xf) & 2; - f |= 0x0d938 >> (x >> 16 & 0xf) & 1; - return BIT(0xEC57E80A, f); -} -#ifdef __cplusplus -} -#endif -#endif diff --git a/client/nonce2key/crypto1.c b/client/nonce2key/crypto1.c deleted file mode 100644 index 42a44b2d..00000000 --- a/client/nonce2key/crypto1.c +++ /dev/null @@ -1,96 +0,0 @@ -/* crypto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#define SWAPENDIAN(x)\ - (x = (x >> 8 & 0xff00ff) | (x & 0xff00ff) << 8, x = x >> 16 | x << 16) - -struct Crypto1State * crypto1_create(uint64_t key) -{ - struct Crypto1State *s = malloc(sizeof(*s)); - int i; - - for(i = 47;s && i > 0; i -= 2) { - s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); - s->even = s->even << 1 | BIT(key, i ^ 7); - } - return s; -} -void crypto1_destroy(struct Crypto1State *state) -{ - free(state); -} -void crypto1_get_lfsr(struct Crypto1State *state, uint64_t *lfsr) -{ - int i; - for(*lfsr = 0, i = 23; i >= 0; --i) { - *lfsr = *lfsr << 1 | BIT(state->odd, i ^ 3); - *lfsr = *lfsr << 1 | BIT(state->even, i ^ 3); - } -} -uint8_t crypto1_bit(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint32_t feedin; - uint32_t tmp; - uint8_t ret = filter(s->odd); - - feedin = ret & !!is_encrypted; - feedin ^= !!in; - feedin ^= LF_POLY_ODD & s->odd; - feedin ^= LF_POLY_EVEN & s->even; - s->even = s->even << 1 | parity(feedin); - - tmp = s->odd; - s->odd = s->even; - s->even = tmp; - - return ret; -} -uint8_t crypto1_byte(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint8_t i, ret = 0; - - for (i = 0; i < 8; ++i) - ret |= crypto1_bit(s, BIT(in, i), is_encrypted) << i; - - return ret; -} -uint32_t crypto1_word(struct Crypto1State *s, uint32_t in, int is_encrypted) -{ - uint32_t i, ret = 0; - - for (i = 0; i < 4; ++i, in <<= 8) - ret = ret << 8 | crypto1_byte(s, in >> 24, is_encrypted); - - return ret; -} - -/* prng_successor - * helper used to obscure the keystream during authentication - */ -uint32_t prng_successor(uint32_t x, uint32_t n) -{ - SWAPENDIAN(x); - while(n--) - x = x >> 1 | (x >> 16 ^ x >> 18 ^ x >> 19 ^ x >> 21) << 31; - - return SWAPENDIAN(x); -} diff --git a/client/nonce2key/nonce2key.c b/client/nonce2key/nonce2key.c deleted file mode 100644 index a6b33e93..00000000 --- a/client/nonce2key/nonce2key.c +++ /dev/null @@ -1,288 +0,0 @@ -//----------------------------------------------------------------------------- -// Merlok - June 2011 -// Roel - Dec 2009 -// Unknown author -// -// This code is licensed to you under the terms of the GNU GPL, version 2 or, -// at your option, any later version. See the LICENSE.txt file for the text of -// the license. -//----------------------------------------------------------------------------- -// MIFARE Darkside hack -//----------------------------------------------------------------------------- - -#include -#include - -#include "nonce2key.h" -#include "mifarehost.h" -#include "ui.h" -#include "util.h" - -int compar_state(const void * a, const void * b) { - // didn't work: (the result is truncated to 32 bits) - //return (*(int64_t*)b - *(int64_t*)a); - - // better: - if (*(int64_t*)b == *(int64_t*)a) return 0; - else if (*(int64_t*)b > *(int64_t*)a) return 1; - else return -1; -} - -int nonce2key(uint32_t uid, uint32_t nt, uint32_t nr, uint64_t par_info, uint64_t ks_info, uint64_t * key) { - struct Crypto1State *state; - uint32_t i, pos, rr, nr_diff, key_count;//, ks1, ks2; - byte_t bt, ks3x[8], par[8][8]; - uint64_t key_recovered; - int64_t *state_s; - static uint32_t last_uid; - static int64_t *last_keylist; - rr = 0; - - if (last_uid != uid && last_keylist != NULL) - { - free(last_keylist); - last_keylist = NULL; - } - last_uid = uid; - - // Reset the last three significant bits of the reader nonce - nr &= 0xffffff1f; - - PrintAndLog("\nuid(%08x) nt(%08x) par(%016" PRIx64") ks(%016" PRIx64") nr(%08" PRIx32")\n\n",uid,nt,par_info,ks_info,nr); - - for (pos=0; pos<8; pos++) - { - ks3x[7-pos] = (ks_info >> (pos*8)) & 0x0f; - bt = (par_info >> (pos*8)) & 0xff; - for (i=0; i<8; i++) - { - par[7-pos][i] = (bt >> i) & 0x01; - } - } - - printf("|diff|{nr} |ks3|ks3^5|parity |\n"); - printf("+----+--------+---+-----+---------------+\n"); - for (i=0; i<8; i++) - { - nr_diff = nr | i << 5; - printf("| %02x |%08x|",i << 5, nr_diff); - printf(" %01x | %01x |",ks3x[i], ks3x[i]^5); - for (pos=0; pos<7; pos++) printf("%01x,", par[i][pos]); - printf("%01x|\n", par[i][7]); - } - - if (par_info==0) - PrintAndLog("parity is all zero,try special attack!just wait for few more seconds..."); - - state = lfsr_common_prefix(nr, rr, ks3x, par, par_info==0); - state_s = (int64_t*)state; - - //char filename[50] ; - //sprintf(filename, "nt_%08x_%d.txt", nt, nr); - //printf("name %s\n", filename); - //FILE* fp = fopen(filename,"w"); - for (i = 0; (state) && ((state + i)->odd != -1); i++) - { - lfsr_rollback_word(state+i, uid^nt, 0); - crypto1_get_lfsr(state + i, &key_recovered); - *(state_s + i) = key_recovered; - //fprintf(fp, "%012" PRIx64 "\n",key_recovered); - } - //fclose(fp); - - if(!state) - return 1; - - qsort(state_s, i, sizeof(*state_s), compar_state); - *(state_s + i) = -1; - - //Create the intersection: - if (par_info == 0 ) - if ( last_keylist != NULL) - { - int64_t *p1, *p2, *p3; - p1 = p3 = last_keylist; - p2 = state_s; - while ( *p1 != -1 && *p2 != -1 ) { - if (compar_state(p1, p2) == 0) { - printf("p1:%" PRIx64" p2:%" PRIx64 " p3:%" PRIx64" key:%012" PRIx64 "\n",(uint64_t)(p1-last_keylist),(uint64_t)(p2-state_s),(uint64_t)(p3-last_keylist),*p1); - *p3++ = *p1++; - p2++; - } - else { - while (compar_state(p1, p2) == -1) ++p1; - while (compar_state(p1, p2) == 1) ++p2; - } - } - key_count = p3 - last_keylist;; - } - else - key_count = 0; - else - { - last_keylist = state_s; - key_count = i; - } - - printf("key_count:%d\n", key_count); - - // The list may still contain several key candidates. Test each of them with mfCheckKeys - for (i = 0; i < key_count; i++) { - uint8_t keyBlock[6]; - uint64_t key64; - key64 = *(last_keylist + i); - num_to_bytes(key64, 6, keyBlock); - key64 = 0; - if (!mfCheckKeys(0, 0, false, 1, keyBlock, &key64)) { - *key = key64; - free(last_keylist); - last_keylist = NULL; - if (par_info ==0) - free(state); - return 0; - } - } - - - free(last_keylist); - last_keylist = state_s; - - return 1; -} - -// 32 bit recover key from 2 nonces -bool mfkey32(nonces_t data, uint64_t *outputkey) { - struct Crypto1State *s,*t; - uint64_t outkey = 0; - uint64_t key=0; // recovered key - uint32_t uid = data.cuid; - uint32_t nt = data.nonce; // first tag challenge (nonce) - uint32_t nr0_enc = data.nr; // first encrypted reader challenge - uint32_t ar0_enc = data.ar; // first encrypted reader response - uint32_t nr1_enc = data.nr2; // second encrypted reader challenge - uint32_t ar1_enc = data.ar2; // second encrypted reader response - clock_t t1 = clock(); - bool isSuccess = false; - uint8_t counter=0; - - s = lfsr_recovery32(ar0_enc ^ prng_successor(nt, 64), 0); - - for(t = s; t->odd | t->even; ++t) { - lfsr_rollback_word(t, 0, 0); - lfsr_rollback_word(t, nr0_enc, 1); - lfsr_rollback_word(t, uid ^ nt, 0); - crypto1_get_lfsr(t, &key); - crypto1_word(t, uid ^ nt, 0); - crypto1_word(t, nr1_enc, 1); - if (ar1_enc == (crypto1_word(t, 0, 0) ^ prng_successor(nt, 64))) { - //PrintAndLog("Found Key: [%012" PRIx64 "]",key); - outkey = key; - counter++; - if (counter==20) break; - } - } - isSuccess = (counter == 1); - t1 = clock() - t1; - //if ( t1 > 0 ) PrintAndLog("Time in mfkey32: %.0f ticks \nFound %d possible keys", (float)t1, counter); - *outputkey = ( isSuccess ) ? outkey : 0; - crypto1_destroy(s); - /* //un-comment to save all keys to a stats.txt file - FILE *fout; - if ((fout = fopen("stats.txt","ab")) == NULL) { - PrintAndLog("Could not create file name stats.txt"); - return 1; - } - fprintf(fout, "mfkey32,%d,%08x,%d,%s,%04x%08x,%.0Lf\r\n", counter, data.cuid, data.sector, (data.keytype) ? "B" : "A", (uint32_t)(outkey>>32) & 0xFFFF,(uint32_t)(outkey&0xFFFFFFFF),(long double)t1); - fclose(fout); - */ - return isSuccess; -} - -bool tryMfk32_moebius(nonces_t data, uint64_t *outputkey) { - struct Crypto1State *s, *t; - uint64_t outkey = 0; - uint64_t key = 0; // recovered key - uint32_t uid = data.cuid; - uint32_t nt0 = data.nonce; // first tag challenge (nonce) - uint32_t nr0_enc = data.nr; // first encrypted reader challenge - uint32_t ar0_enc = data.ar; // first encrypted reader response - uint32_t nt1 = data.nonce2; // second tag challenge (nonce) - uint32_t nr1_enc = data.nr2; // second encrypted reader challenge - uint32_t ar1_enc = data.ar2; // second encrypted reader response - bool isSuccess = false; - int counter = 0; - - //PrintAndLog("Enter mfkey32_moebius"); - clock_t t1 = clock(); - - s = lfsr_recovery32(ar0_enc ^ prng_successor(nt0, 64), 0); - - for(t = s; t->odd | t->even; ++t) { - lfsr_rollback_word(t, 0, 0); - lfsr_rollback_word(t, nr0_enc, 1); - lfsr_rollback_word(t, uid ^ nt0, 0); - crypto1_get_lfsr(t, &key); - - crypto1_word(t, uid ^ nt1, 0); - crypto1_word(t, nr1_enc, 1); - if (ar1_enc == (crypto1_word(t, 0, 0) ^ prng_successor(nt1, 64))) { - //PrintAndLog("Found Key: [%012" PRIx64 "]",key); - outkey=key; - ++counter; - if (counter==20) - break; - } - } - isSuccess = (counter == 1); - t1 = clock() - t1; - //if ( t1 > 0 ) PrintAndLog("Time in mfkey32_moebius: %.0f ticks \nFound %d possible keys", (float)t1,counter); - *outputkey = ( isSuccess ) ? outkey : 0; - crypto1_destroy(s); - /* // un-comment to output all keys to stats.txt - FILE *fout; - if ((fout = fopen("stats.txt","ab")) == NULL) { - PrintAndLog("Could not create file name stats.txt"); - return 1; - } - fprintf(fout, "moebius,%d,%08x,%d,%s,%04x%08x,%0.Lf\r\n", counter, data.cuid, data.sector, (data.keytype) ? "B" : "A", (uint32_t) (outkey>>32),(uint32_t)(outkey&0xFFFFFFFF),(long double)t1); - fclose(fout); - */ - return isSuccess; -} - -int tryMfk64_ex(uint8_t *data, uint64_t *outputkey){ - uint32_t uid = le32toh(data); - uint32_t nt = le32toh(data+4); // tag challenge - uint32_t nr_enc = le32toh(data+8); // encrypted reader challenge - uint32_t ar_enc = le32toh(data+12); // encrypted reader response - uint32_t at_enc = le32toh(data+16); // encrypted tag response - return tryMfk64(uid, nt, nr_enc, ar_enc, at_enc, outputkey); -} - -int tryMfk64(uint32_t uid, uint32_t nt, uint32_t nr_enc, uint32_t ar_enc, uint32_t at_enc, uint64_t *outputkey){ - uint64_t key = 0; // recovered key - uint32_t ks2; // keystream used to encrypt reader response - uint32_t ks3; // keystream used to encrypt tag response - struct Crypto1State *revstate; - - PrintAndLog("Enter mfkey64"); - clock_t t1 = clock(); - - // Extract the keystream from the messages - ks2 = ar_enc ^ prng_successor(nt, 64); - ks3 = at_enc ^ prng_successor(nt, 96); - revstate = lfsr_recovery64(ks2, ks3); - lfsr_rollback_word(revstate, 0, 0); - lfsr_rollback_word(revstate, 0, 0); - lfsr_rollback_word(revstate, nr_enc, 1); - lfsr_rollback_word(revstate, uid ^ nt, 0); - crypto1_get_lfsr(revstate, &key); - PrintAndLog("Found Key: [%012" PRIx64 "]", key); - crypto1_destroy(revstate); - *outputkey = key; - - t1 = clock() - t1; - if ( t1 > 0 ) PrintAndLog("Time in mfkey64: %.0f ticks \n", (float)t1); - return 0; -} - diff --git a/client/nonce2key/nonce2key.h b/client/nonce2key/nonce2key.h deleted file mode 100644 index fac9c151..00000000 --- a/client/nonce2key/nonce2key.h +++ /dev/null @@ -1,42 +0,0 @@ -//----------------------------------------------------------------------------- -// Merlok - June 2011 -// Roel - Dec 2009 -// Unknown author -// -// This code is licensed to you under the terms of the GNU GPL, version 2 or, -// at your option, any later version. See the LICENSE.txt file for the text of -// the license. -//----------------------------------------------------------------------------- -// MIFARE Darkside hack -//----------------------------------------------------------------------------- - -#ifndef __NONCE2KEY_H -#define __NONCE2KEY_H - -#include -#include -#include "crapto1.h" -#include "common.h" -//#include //for bool - -typedef struct { - uint32_t cuid; - uint8_t sector; - uint8_t keytype; - uint32_t nonce; - uint32_t ar; - uint32_t nr; - uint32_t nonce2; - uint32_t ar2; - uint32_t nr2; - } nonces_t; - -int nonce2key(uint32_t uid, uint32_t nt, uint32_t nr, uint64_t par_info, uint64_t ks_info, uint64_t * key); -bool mfkey32(nonces_t data, uint64_t *outputkey); -bool tryMfk32_moebius(nonces_t data, uint64_t *outputkey); -int tryMfk64_ex(uint8_t *data, uint64_t *outputkey); -int tryMfk64(uint32_t uid, uint32_t nt, uint32_t nr_enc, uint32_t ar_enc, uint32_t at_enc, uint64_t *outputkey); - -//uint64_t mfkey32(uint32_t uid, uint32_t nt, uint32_t nr0_enc, uint32_t ar0_enc, uint32_t nr1_enc, uint32_t ar1_enc); - -#endif diff --git a/client/obj/crapto1/.dummy b/client/obj/crapto1/.dummy new file mode 100644 index 00000000..e69de29b diff --git a/client/obj/nonce2key/.dummy b/client/obj/nonce2key/.dummy deleted file mode 100644 index e69de29b..00000000 diff --git a/client/proxmark3.c b/client/proxmark3.c index ba8c7205..2ed127a4 100644 --- a/client/proxmark3.c +++ b/client/proxmark3.c @@ -22,7 +22,6 @@ #include "cmdmain.h" #include "uart.h" #include "ui.h" -#include "sleep.h" #include "cmdparser.h" #include "cmdhw.h" #include "whereami.h" diff --git a/client/scripting.c b/client/scripting.c index 10d554a0..d68adb3e 100644 --- a/client/scripting.c +++ b/client/scripting.c @@ -8,15 +8,17 @@ // Some lua scripting glue to proxmark core. //----------------------------------------------------------------------------- +#include "scripting.h" + +#include #include #include #include #include "proxmark3.h" #include "usb_cmd.h" #include "cmdmain.h" -#include "scripting.h" #include "util.h" -#include "nonce2key/nonce2key.h" +#include "mifarehost.h" #include "../common/iso15693tools.h" #include "iso14443crc.h" #include "../common/crc16.h" @@ -124,49 +126,27 @@ static int returnToLuaWithError(lua_State *L, const char* fmt, ...) return 2; } -static int l_nonce2key(lua_State *L){ - - size_t size; - const char *p_uid = luaL_checklstring(L, 1, &size); - if(size != 4) return returnToLuaWithError(L,"Wrong size of uid, got %d bytes, expected 4", (int) size); - - const char *p_nt = luaL_checklstring(L, 2, &size); - if(size != 4) return returnToLuaWithError(L,"Wrong size of nt, got %d bytes, expected 4", (int) size); - - const char *p_nr = luaL_checklstring(L, 3, &size); - if(size != 4) return returnToLuaWithError(L,"Wrong size of nr, got %d bytes, expected 4", (int) size); - - const char *p_par_info = luaL_checklstring(L, 4, &size); - if(size != 8) return returnToLuaWithError(L,"Wrong size of par_info, got %d bytes, expected 8", (int) size); - - const char *p_pks_info = luaL_checklstring(L, 5, &size); - if(size != 8) return returnToLuaWithError(L,"Wrong size of ks_info, got %d bytes, expected 8", (int) size); - - - uint32_t uid = bytes_to_num(( uint8_t *)p_uid,4); - uint32_t nt = bytes_to_num(( uint8_t *)p_nt,4); - - uint32_t nr = bytes_to_num(( uint8_t*)p_nr,4); - uint64_t par_info = bytes_to_num(( uint8_t *)p_par_info,8); - uint64_t ks_info = bytes_to_num(( uint8_t *)p_pks_info,8); - - uint64_t key = 0; - - int retval = nonce2key(uid,nt, nr, par_info,ks_info, &key); +static int l_mfDarkside(lua_State *L){ + uint64_t key; + + int retval = mfDarkside(&key); + //Push the retval on the stack - lua_pushinteger(L,retval); + lua_pushinteger(L, retval); //Push the key onto the stack uint8_t dest_key[8]; - num_to_bytes(key,sizeof(dest_key),dest_key); + num_to_bytes(key, sizeof(dest_key), dest_key); //printf("Pushing to lua stack: %012" PRIx64 "\n",key); - lua_pushlstring(L,(const char *) dest_key,sizeof(dest_key)); + lua_pushlstring(L,(const char *)dest_key, sizeof(dest_key)); return 2; //Two return values } + //static int l_PrintAndLog(lua_State *L){ return CmdHF14AMfDump(luaL_checkstring(L, 1));} + static int l_clearCommandBuffer(lua_State *L){ clearCommandBuffer(); return 0; @@ -498,7 +478,7 @@ int set_pm3_libraries(lua_State *L) static const luaL_Reg libs[] = { {"SendCommand", l_SendCommand}, {"WaitForResponseTimeout", l_WaitForResponseTimeout}, - {"nonce2key", l_nonce2key}, + {"mfDarkside", l_mfDarkside}, //{"PrintAndLog", l_PrintAndLog}, {"foobar", l_foobar}, {"ukbhit", l_ukbhit}, diff --git a/client/scripts/mifare_autopwn.lua b/client/scripts/mifare_autopwn.lua index ce6db3c0..e68f7a75 100644 --- a/client/scripts/mifare_autopwn.lua +++ b/client/scripts/mifare_autopwn.lua @@ -8,7 +8,7 @@ author = "Martin Holst Swende" desc = [[ -This is a which automates cracking and dumping mifare classic cards. It sets itself into +This is a script which automates cracking and dumping mifare classic cards. It sets itself into 'listening'-mode, after which it cracks and dumps any mifare classic card that you place by the device. @@ -63,91 +63,6 @@ function wait_for_mifare() return nil, "Aborted by user" end -function mfcrack() - core.clearCommandBuffer() - -- Build the mifare-command - local cmd = Command:new{cmd = cmds.CMD_READER_MIFARE, arg1 = 1} - - local retry = true - while retry do - core.SendCommand(cmd:getBytes()) - local key, errormessage = mfcrack_inner() - -- Success? - if key then return key end - -- Failure? - if errormessage then return nil, errormessage end - -- Try again..set arg1 to 0 this time. - - cmd = Command:new{cmd = cmds.CMD_READER_MIFARE, arg1 = 0} - end - return nil, "Aborted by user" -end - - -function mfcrack_inner() - while not core.ukbhit() do - local result = core.WaitForResponseTimeout(cmds.CMD_ACK,1000) - if result then - - --[[ - I don't understand, they cmd and args are defined as uint32_t, however, - looking at the returned data, they all look like 64-bit things: - - print("result", bin.unpack("HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH", result)) - - FF 00 00 00 00 00 00 00 <-- 64 bits of data - FE FF FF FF 00 00 00 00 <-- 64 bits of data - 00 00 00 00 00 00 00 00 <-- 64 bits of data - 00 00 00 00 00 00 00 00 <-- 64 bits of data - 04 7F 12 E2 00 <-- this is where 'data' starts - - So below I use LI to pick out the "FEFF FFFF", don't know why it works.. - --]] - -- Unpacking the arg-parameters - local count,cmd,isOK = bin.unpack('LI',result) - --print("response", isOK)--FF FF FF FF - if isOK == 0xFFFFFFFF then - return nil, "Button pressed. Aborted." - elseif isOK == 0xFFFFFFFE then - return nil, "Card is not vulnerable to Darkside attack (doesn't send NACK on authentication requests). You can try 'script run mfkeys' or 'hf mf chk' to test various known keys." - elseif isOK == 0xFFFFFFFD then - return nil, "Card is not vulnerable to Darkside attack (its random number generator is not predictable). You can try 'script run mfkeys' or 'hf mf chk' to test various known keys." - elseif isOK == 0xFFFFFFFC then - return nil, "The card's random number generator behaves somewhat weird (Mifare clone?). You can try 'script run mfkeys' or 'hf mf chk' to test various known keys." - elseif isOK ~= 1 then - return nil, "Error occurred" - end - - - -- The data-part is left - -- Starts 32 bytes in, at byte 33 - local data = result:sub(33) - - -- A little helper - local get = function(num) - local x = data:sub(1,num) - data = data:sub(num+1) - return x - end - - local uid,nt,pl = get(4),get(4),get(8) - local ks,nr = get(8),get(4) - - local status, key = core.nonce2key(uid,nt, nr, pl,ks) - if not status then return status,key end - - if status > 0 then - print("Key not found (lfsr_common_prefix problem)") - -- try again - return nil,nil - else - return key - end - end - end - return nil, "Aborted by user" -end - function nested(key,sak) local typ = 1 if 0x18 == sak then --NXP MIFARE Classic 4k | Plus 4k @@ -209,8 +124,15 @@ function main(args) print("Card found, commencing crack", uid) -- Crack it local key, cnt - res,err = mfcrack() - if not res then return oops(err) end + err, res = core.mfDarkside() + if err == -1 then return oops("Button pressed. Aborted.") + elseif err == -2 then return oops("Card is not vulnerable to Darkside attack (doesn't send NACK on authentication requests).") + elseif err == -3 then return oops("Card is not vulnerable to Darkside attack (its random number generator is not predictable).") + elseif err == -4 then return oops([[ +Card is not vulnerable to Darkside attack (its random number generator seems to be based on the wellknown +generating polynomial with 16 effective bits only, but shows unexpected behaviour.]]) + elseif err == -5 then return oops("Aborted via keyboard.") + end -- The key is actually 8 bytes, so a -- 6-byte key is sent as 00XXXXXX -- This means we unpack it as first diff --git a/client/sleep.c b/client/sleep.c deleted file mode 100644 index fe397da9..00000000 --- a/client/sleep.c +++ /dev/null @@ -1,28 +0,0 @@ -//----------------------------------------------------------------------------- -// Copyright (C) 2010 iZsh -// -// This code is licensed to you under the terms of the GNU GPL, version 2 or, -// at your option, any later version. See the LICENSE.txt file for the text of -// the license. -//----------------------------------------------------------------------------- -// platform-independant sleep macros -//----------------------------------------------------------------------------- - -#ifndef _WIN32 - -#define _POSIX_C_SOURCE 199309L -#include "sleep.h" -#include -#include -#include -#include - -void nsleep(uint64_t n) { - struct timespec timeout; - timeout.tv_sec = n/1000000000; - timeout.tv_nsec = n%1000000000; - while (nanosleep(&timeout, &timeout) && errno == EINTR); -} - -#endif // _WIN32 - diff --git a/client/sleep.h b/client/sleep.h deleted file mode 100644 index 81e1dea0..00000000 --- a/client/sleep.h +++ /dev/null @@ -1,27 +0,0 @@ -//----------------------------------------------------------------------------- -// Copyright (C) 2010 iZsh -// -// This code is licensed to you under the terms of the GNU GPL, version 2 or, -// at your option, any later version. See the LICENSE.txt file for the text of -// the license. -//----------------------------------------------------------------------------- -// platform-independant sleep macros -//----------------------------------------------------------------------------- - -#ifndef SLEEP_H__ -#define SLEEP_H__ - -#ifdef _WIN32 -# include -# define sleep(n) Sleep(1000 * n) -# define msleep(n) Sleep(n) -#else -# include -# include - void nsleep(uint64_t n); -# define msleep(n) nsleep(1000000 * n) -# define usleep(n) nsleep(1000 * n) -#endif // _WIN32 - -#endif // SLEEP_H__ - diff --git a/client/snooper.c b/client/snooper.c index 30d39de6..14f07063 100644 --- a/client/snooper.c +++ b/client/snooper.c @@ -8,7 +8,6 @@ // Snooper binary //----------------------------------------------------------------------------- -#include "sleep.h" #include "ui.h" #include "proxusb.h" #include "cmdmain.h" diff --git a/client/ui.c b/client/ui.c index ba230e33..5902cb89 100644 --- a/client/ui.c +++ b/client/ui.c @@ -12,7 +12,6 @@ #include #include #include -#include #include #include @@ -34,7 +33,7 @@ void PrintAndLog(char *fmt, ...) static FILE *logfile = NULL; static int logging=1; - // lock this section to avoid interlacing prints from different threats + // lock this section to avoid interlacing prints from different threads pthread_mutex_lock(&print_lock); if (logging && !logfile) { diff --git a/client/util.c b/client/util.c index e80f5cc9..7c70d55d 100644 --- a/client/util.c +++ b/client/util.c @@ -8,15 +8,26 @@ // utilities //----------------------------------------------------------------------------- -#include +#if !defined(_WIN32) +#define _POSIX_C_SOURCE 199309L // need nanosleep() +#endif + #include "util.h" + +#include +#include +#include +#include +#include +#include +#include "data.h" + #define MAX_BIN_BREAK_LENGTH (3072+384+1) #ifndef _WIN32 #include #include - int ukbhit(void) { int cnt = 0; @@ -42,6 +53,7 @@ int ukbhit(void) } #else + #include int ukbhit(void) { return kbhit(); @@ -245,6 +257,15 @@ void num_to_bytebitsLSBF(uint64_t n, size_t len, uint8_t *dest) { } } +// Swap bit order on a uint32_t value. Can be limited by nrbits just use say 8bits reversal +// And clears the rest of the bits. +uint32_t SwapBits(uint32_t value, int nrbits) { + uint32_t newvalue = 0; + for(int i = 0; i < nrbits; i++) { + newvalue ^= ((value >> i) & 1) << (nrbits - 1 - i); + } + return newvalue; +} // aa,bb,cc,dd,ee,ff,gg,hh, ii,jj,kk,ll,mm,nn,oo,pp // to @@ -591,3 +612,38 @@ void clean_ascii(unsigned char *buf, size_t len) { buf[i] = '.'; } } + + +// Timer functions +#if !defined (_WIN32) +#include + +static void nsleep(uint64_t n) { + struct timespec timeout; + timeout.tv_sec = n/1000000000; + timeout.tv_nsec = n%1000000000; + while (nanosleep(&timeout, &timeout) && errno == EINTR); +} + +void msleep(uint32_t n) { + nsleep(1000000 * n); +} + +#endif // _WIN32 + +// a milliseconds timer for performance measurement +uint64_t msclock() { +#if defined(_WIN32) +#include + struct _timeb t; + if (_ftime_s(&t)) { + return 0; + } else { + return 1000 * t.time + t.millitm; + } +#else + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return (t.tv_sec * 1000 + t.tv_nsec / 1000000); +#endif +} diff --git a/client/util.h b/client/util.h index 7d9943f0..27f9348e 100644 --- a/client/util.h +++ b/client/util.h @@ -8,13 +8,11 @@ // utilities //----------------------------------------------------------------------------- -#include -#include //included in data.h -#include -#include -#include -#include //time, gmtime -#include "data.h" //for FILE_PATH_SIZE +#ifndef UTIL_H__ +#define UTIL_H__ + +#include +#include #ifndef ROTR # define ROTR(x,n) (((uintmax_t)(x) >> (n)) | ((uintmax_t)(x) << ((sizeof(x) * 8) - (n)))) @@ -25,54 +23,69 @@ #ifndef MAX # define MAX(a, b) (((a) > (b)) ? (a) : (b)) #endif + #define EVEN 0 #define ODD 1 -int ukbhit(void); +extern int ukbhit(void); + +extern void AddLogLine(char *fileName, char *extData, char *c); +extern void AddLogHex(char *fileName, char *extData, const uint8_t * data, const size_t len); +extern void AddLogUint64(char *fileName, char *extData, const uint64_t data); +extern void AddLogCurrentDT(char *fileName); +extern void FillFileNameByUID(char *fileName, uint8_t * uid, char *ext, int byteCount); + +extern void print_hex(const uint8_t * data, const size_t len); +extern char *sprint_hex(const uint8_t * data, const size_t len); +extern char *sprint_bin(const uint8_t * data, const size_t len); +extern char *sprint_bin_break(const uint8_t *data, const size_t len, const uint8_t breaks); +extern char *sprint_hex_ascii(const uint8_t *data, const size_t len); +extern char *sprint_ascii(const uint8_t *data, const size_t len); + +extern void num_to_bytes(uint64_t n, size_t len, uint8_t* dest); +extern uint64_t bytes_to_num(uint8_t* src, size_t len); +extern void num_to_bytebits(uint64_t n, size_t len, uint8_t *dest); +extern void num_to_bytebitsLSBF(uint64_t n, size_t len, uint8_t *dest); +extern char *printBits(size_t const size, void const * const ptr); +extern uint32_t SwapBits(uint32_t value, int nrbits); +extern uint8_t *SwapEndian64(const uint8_t *src, const size_t len, const uint8_t blockSize); +extern void SwapEndian64ex(const uint8_t *src, const size_t len, const uint8_t blockSize, uint8_t *dest); -void AddLogLine(char *fileName, char *extData, char *c); -void AddLogHex(char *fileName, char *extData, const uint8_t * data, const size_t len); -void AddLogUint64(char *fileName, char *extData, const uint64_t data); -void AddLogCurrentDT(char *fileName); -void FillFileNameByUID(char *fileName, uint8_t * uid, char *ext, int byteCount); +extern char param_getchar(const char *line, int paramnum); +extern int param_getptr(const char *line, int *bg, int *en, int paramnum); +extern uint8_t param_get8(const char *line, int paramnum); +extern uint8_t param_get8ex(const char *line, int paramnum, int deflt, int base); +extern uint32_t param_get32ex(const char *line, int paramnum, int deflt, int base); +extern uint64_t param_get64ex(const char *line, int paramnum, int deflt, int base); +extern uint8_t param_getdec(const char *line, int paramnum, uint8_t *destination); +extern uint8_t param_isdec(const char *line, int paramnum); +extern int param_gethex(const char *line, int paramnum, uint8_t * data, int hexcnt); +extern int param_gethex_ex(const char *line, int paramnum, uint8_t * data, int *hexcnt); +extern int param_getstr(const char *line, int paramnum, char * str); -void print_hex(const uint8_t * data, const size_t len); -char * sprint_hex(const uint8_t * data, const size_t len); -char * sprint_bin(const uint8_t * data, const size_t len); -char * sprint_bin_break(const uint8_t *data, const size_t len, const uint8_t breaks); -char * sprint_hex_ascii(const uint8_t *data, const size_t len); -char * sprint_ascii(const uint8_t *data, const size_t len); +extern int hextobinarray( char *target, char *source); +extern int hextobinstring( char *target, char *source); +extern int binarraytohex( char *target, char *source, int length); +extern void binarraytobinstring(char *target, char *source, int length); +extern uint8_t GetParity( uint8_t *string, uint8_t type, int length); +extern void wiegand_add_parity(uint8_t *target, uint8_t *source, uint8_t length); -void num_to_bytes(uint64_t n, size_t len, uint8_t* dest); -uint64_t bytes_to_num(uint8_t* src, size_t len); -void num_to_bytebits(uint64_t n, size_t len, uint8_t *dest); -void num_to_bytebitsLSBF(uint64_t n, size_t len, uint8_t *dest); -char * printBits(size_t const size, void const * const ptr); -uint8_t *SwapEndian64(const uint8_t *src, const size_t len, const uint8_t blockSize); -void SwapEndian64ex(const uint8_t *src, const size_t len, const uint8_t blockSize, uint8_t *dest); +extern void xor(unsigned char *dst, unsigned char *src, size_t len); +extern int32_t le24toh(uint8_t data[3]); +extern uint32_t le32toh (uint8_t *data); +extern void rol(uint8_t *data, const size_t len); -char param_getchar(const char *line, int paramnum); -int param_getptr(const char *line, int *bg, int *en, int paramnum); -uint8_t param_get8(const char *line, int paramnum); -uint8_t param_get8ex(const char *line, int paramnum, int deflt, int base); -uint32_t param_get32ex(const char *line, int paramnum, int deflt, int base); -uint64_t param_get64ex(const char *line, int paramnum, int deflt, int base); -uint8_t param_getdec(const char *line, int paramnum, uint8_t *destination); -uint8_t param_isdec(const char *line, int paramnum); -int param_gethex(const char *line, int paramnum, uint8_t * data, int hexcnt); -int param_gethex_ex(const char *line, int paramnum, uint8_t * data, int *hexcnt); -int param_getstr(const char *line, int paramnum, char * str); +extern void clean_ascii(unsigned char *buf, size_t len); - int hextobinarray( char *target, char *source); - int hextobinstring( char *target, char *source); - int binarraytohex( char *target, char *source, int length); -void binarraytobinstring(char *target, char *source, int length); -uint8_t GetParity( uint8_t *string, uint8_t type, int length); -void wiegand_add_parity(uint8_t *target, uint8_t *source, uint8_t length); +// timer functions/macros +#ifdef _WIN32 +# include +# define sleep(n) Sleep(1000 *(n)) +# define msleep(n) Sleep((n)) +#else +extern void msleep(uint32_t n); // sleep n milliseconds +#endif // _WIN32 -void xor(unsigned char *dst, unsigned char *src, size_t len); -int32_t le24toh(uint8_t data[3]); -uint32_t le32toh (uint8_t *data); -void rol(uint8_t *data, const size_t len); +extern uint64_t msclock(); // a milliseconds clock -void clean_ascii(unsigned char *buf, size_t len); +#endif // UTIL_H__ diff --git a/common/Makefile.common b/common/Makefile.common index 7c94e041..53d2a834 100644 --- a/common/Makefile.common +++ b/common/Makefile.common @@ -63,7 +63,7 @@ endif # Also search prerequisites in the common directory (for usb.c), the fpga directory (for fpga.bit), and the zlib directory -VPATH = . ../common ../fpga ../zlib +VPATH = . ../common ../common/crapto1 ../fpga ../zlib INCLUDES = ../include/proxmark3.h ../include/at91sam7s512.h ../include/config_gpio.h ../include/usb_cmd.h $(APP_INCLUDES) diff --git a/common/crapto1/crapto1.c b/common/crapto1/crapto1.c new file mode 100644 index 00000000..01351731 --- /dev/null +++ b/common/crapto1/crapto1.c @@ -0,0 +1,532 @@ +/* crapto1.c + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License + as published by the Free Software Foundation; either version 2 + of the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, US$ + + Copyright (C) 2008-2014 bla +*/ +#include "crapto1.h" +#include + +#if !defined LOWMEM && defined __GNUC__ +static uint8_t filterlut[1 << 20]; +static void __attribute__((constructor)) fill_lut() +{ + uint32_t i; + for(i = 0; i < 1 << 20; ++i) + filterlut[i] = filter(i); +} +#define filter(x) (filterlut[(x) & 0xfffff]) +#endif + + + +typedef struct bucket { + uint32_t *head; + uint32_t *bp; +} bucket_t; + +typedef bucket_t bucket_array_t[2][0x100]; + +typedef struct bucket_info { + struct { + uint32_t *head, *tail; + } bucket_info[2][0x100]; + uint32_t numbuckets; + } bucket_info_t; + + +static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop, + uint32_t* const ostart, uint32_t* const ostop, + bucket_info_t *bucket_info, bucket_array_t bucket) +{ + uint32_t *p1, *p2; + uint32_t *start[2]; + uint32_t *stop[2]; + + start[0] = estart; + stop[0] = estop; + start[1] = ostart; + stop[1] = ostop; + + // init buckets to be empty + for (uint32_t i = 0; i < 2; i++) { + for (uint32_t j = 0x00; j <= 0xff; j++) { + bucket[i][j].bp = bucket[i][j].head; + } + } + + // sort the lists into the buckets based on the MSB (contribution bits) + for (uint32_t i = 0; i < 2; i++) { + for (p1 = start[i]; p1 <= stop[i]; p1++) { + uint32_t bucket_index = (*p1 & 0xff000000) >> 24; + *(bucket[i][bucket_index].bp++) = *p1; + } + } + + + // write back intersecting buckets as sorted list. + // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets. + uint32_t nonempty_bucket; + for (uint32_t i = 0; i < 2; i++) { + p1 = start[i]; + nonempty_bucket = 0; + for (uint32_t j = 0x00; j <= 0xff; j++) { + if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only + bucket_info->bucket_info[i][nonempty_bucket].head = p1; + for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++); + bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1; + nonempty_bucket++; + } + } + bucket_info->numbuckets = nonempty_bucket; + } +} +/** binsearch + * Binary search for the first occurence of *stop's MSB in sorted [start,stop] + */ +static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop) +{ + uint32_t mid, val = *stop & 0xff000000; + while(start != stop) + if(start[mid = (stop - start) >> 1] > val) + stop = &start[mid]; + else + start += mid + 1; + + return start; +} + +/** update_contribution + * helper, calculates the partial linear feedback contributions and puts in MSB + */ +static inline void +update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) +{ + uint32_t p = *item >> 25; + + p = p << 1 | parity(*item & mask1); + p = p << 1 | parity(*item & mask2); + *item = p << 24 | (*item & 0xffffff); +} + +/** extend_table + * using a bit of the keystream extend the table of possible lfsr states + */ +static inline void +extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) +{ + in <<= 24; + for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) + if(filter(*tbl) ^ filter(*tbl | 1)) { + *tbl |= filter(*tbl) ^ bit; + update_contribution(tbl, m1, m2); + *tbl ^= in; + } else if(filter(*tbl) == bit) { + *++*end = tbl[1]; + tbl[1] = tbl[0] | 1; + update_contribution(tbl, m1, m2); + *tbl++ ^= in; + update_contribution(tbl, m1, m2); + *tbl ^= in; + } else + *tbl-- = *(*end)--; +} +/** extend_table_simple + * using a bit of the keystream extend the table of possible lfsr states + */ +static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) +{ + for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) + if(filter(*tbl) ^ filter(*tbl | 1)) + *tbl |= filter(*tbl) ^ bit; + else if(filter(*tbl) == bit) { + *++*end = *++tbl; + *tbl = tbl[-1] | 1; + + } else + *tbl-- = *(*end)--; +} + + +/** recover + * recursively narrow down the search space, 4 bits of keystream at a time + */ +static struct Crypto1State* +recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, + uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem, + struct Crypto1State *sl, uint32_t in, bucket_array_t bucket) +{ + uint32_t *o, *e, i; + bucket_info_t bucket_info; + + if(rem == -1) { + for(e = e_head; e <= e_tail; ++e) { + *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4); + for(o = o_head; o <= o_tail; ++o, ++sl) { + sl->even = *o; + sl->odd = *e ^ parity(*o & LF_POLY_ODD); + sl[1].odd = sl[1].even = 0; + } + } + return sl; + } + + for(i = 0; i < 4 && rem--; i++) { + oks >>= 1; + eks >>= 1; + in >>= 2; + extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, + LF_POLY_ODD << 1, 0); + if(o_head > o_tail) + return sl; + + extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, + LF_POLY_EVEN << 1 | 1, in & 3); + if(e_head > e_tail) + return sl; + } + bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket); + + for (int i = bucket_info.numbuckets - 1; i >= 0; i--) { + sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks, + bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks, + rem, sl, in, bucket); + } + + return sl; +} +/** lfsr_recovery + * recover the state of the lfsr given 32 bits of the keystream + * additionally you can use the in parameter to specify the value + * that was fed into the lfsr at the time the keystream was generated + */ +struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) +{ + struct Crypto1State *statelist; + uint32_t *odd_head = 0, *odd_tail = 0, oks = 0; + uint32_t *even_head = 0, *even_tail = 0, eks = 0; + int i; + + for(i = 31; i >= 0; i -= 2) + oks = oks << 1 | BEBIT(ks2, i); + for(i = 30; i >= 0; i -= 2) + eks = eks << 1 | BEBIT(ks2, i); + + odd_head = odd_tail = malloc(sizeof(uint32_t) << 21); + even_head = even_tail = malloc(sizeof(uint32_t) << 21); + statelist = malloc(sizeof(struct Crypto1State) << 18); + if(!odd_tail-- || !even_tail-- || !statelist) { + free(statelist); + statelist = 0; + goto out; + } + statelist->odd = statelist->even = 0; + + // allocate memory for out of place bucket_sort + bucket_array_t bucket; + for (uint32_t i = 0; i < 2; i++) + for (uint32_t j = 0; j <= 0xff; j++) { + bucket[i][j].head = malloc(sizeof(uint32_t)<<14); + if (!bucket[i][j].head) { + goto out; + } + } + + + for(i = 1 << 20; i >= 0; --i) { + if(filter(i) == (oks & 1)) + *++odd_tail = i; + if(filter(i) == (eks & 1)) + *++even_tail = i; + } + + for(i = 0; i < 4; i++) { + extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1); + extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1); + } + + in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); + recover(odd_head, odd_tail, oks, + even_head, even_tail, eks, 11, statelist, in << 1, bucket); + +out: + free(odd_head); + free(even_head); + for (uint32_t i = 0; i < 2; i++) + for (uint32_t j = 0; j <= 0xff; j++) + free(bucket[i][j].head); + + return statelist; +} + +static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214, + 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83, + 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA}; +static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60, + 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8, + 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20, + 0x7EC7EE90, 0x7F63F748, 0x79117020}; +static const uint32_t T1[] = { + 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66, + 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B, + 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615, + 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C}; +static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0, + 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268, + 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0, + 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0, + 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950, + 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0}; +static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD}; +static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0}; +/** Reverse 64 bits of keystream into possible cipher states + * Variation mentioned in the paper. Somewhat optimized version + */ +struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3) +{ + struct Crypto1State *statelist, *sl; + uint8_t oks[32], eks[32], hi[32]; + uint32_t low = 0, win = 0; + uint32_t *tail, table[1 << 16]; + int i, j; + + sl = statelist = malloc(sizeof(struct Crypto1State) << 4); + if(!sl) + return 0; + sl->odd = sl->even = 0; + + for(i = 30; i >= 0; i -= 2) { + oks[i >> 1] = BEBIT(ks2, i); + oks[16 + (i >> 1)] = BEBIT(ks3, i); + } + for(i = 31; i >= 0; i -= 2) { + eks[i >> 1] = BEBIT(ks2, i); + eks[16 + (i >> 1)] = BEBIT(ks3, i); + } + + for(i = 0xfffff; i >= 0; --i) { + if (filter(i) != oks[0]) + continue; + + *(tail = table) = i; + for(j = 1; tail >= table && j < 29; ++j) + extend_table_simple(table, &tail, oks[j]); + + if(tail < table) + continue; + + for(j = 0; j < 19; ++j) + low = low << 1 | parity(i & S1[j]); + for(j = 0; j < 32; ++j) + hi[j] = parity(i & T1[j]); + + for(; tail >= table; --tail) { + for(j = 0; j < 3; ++j) { + *tail = *tail << 1; + *tail |= parity((i & C1[j]) ^ (*tail & C2[j])); + if(filter(*tail) != oks[29 + j]) + goto continue2; + } + + for(j = 0; j < 19; ++j) + win = win << 1 | parity(*tail & S2[j]); + + win ^= low; + for(j = 0; j < 32; ++j) { + win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]); + if(filter(win) != eks[j]) + goto continue2; + } + + *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail); + sl->odd = *tail ^ parity(LF_POLY_ODD & win); + sl->even = win; + ++sl; + sl->odd = sl->even = 0; + continue2:; + } + } + return statelist; +} + +/** lfsr_rollback_bit + * Rollback the shift register in order to get previous states + */ +uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb) +{ + int out; + uint8_t ret; + uint32_t t; + + s->odd &= 0xffffff; + t = s->odd, s->odd = s->even, s->even = t; + + out = s->even & 1; + out ^= LF_POLY_EVEN & (s->even >>= 1); + out ^= LF_POLY_ODD & s->odd; + out ^= !!in; + out ^= (ret = filter(s->odd)) & !!fb; + + s->even |= parity(out) << 23; + return ret; +} +/** lfsr_rollback_byte + * Rollback the shift register in order to get previous states + */ +uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb) +{ + int i, ret=0; + for (i = 7; i >= 0; --i) + ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i; + return ret; +} +/** lfsr_rollback_word + * Rollback the shift register in order to get previous states + */ +uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb) +{ + int i; + uint32_t ret = 0; + for (i = 31; i >= 0; --i) + ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24); + return ret; +} + +/** nonce_distance + * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y + */ +static uint16_t *dist = 0; +int nonce_distance(uint32_t from, uint32_t to) +{ + uint16_t x, i; + if(!dist) { + dist = malloc(2 << 16); + if(!dist) + return -1; + for (x = i = 1; i; ++i) { + dist[(x & 0xff) << 8 | x >> 8] = i; + x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15; + } + } + return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535; +} + + +static uint32_t fastfwd[2][8] = { + { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB}, + { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}}; +/** lfsr_prefix_ks + * + * Is an exported helper function from the common prefix attack + * Described in the "dark side" paper. It returns an -1 terminated array + * of possible partial(21 bit) secret state. + * The required keystream(ks) needs to contain the keystream that was used to + * encrypt the NACK which is observed when varying only the 3 last bits of Nr + * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3 + */ +uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd) +{ + uint32_t c, entry, *candidates = malloc(4 << 10); + int i, size = 0, good; + + if(!candidates) + return 0; + + for(i = 0; i < 1 << 21; ++i) { + for(c = 0, good = 1; good && c < 8; ++c) { + entry = i ^ fastfwd[isodd][c]; + good &= (BIT(ks[c], isodd) == filter(entry >> 1)); + good &= (BIT(ks[c], isodd + 2) == filter(entry)); + } + if(good) + candidates[size++] = i; + } + + candidates[size] = -1; + + return candidates; +} + +/** check_pfx_parity + * helper function which eliminates possible secret states using parity bits + */ +static struct Crypto1State* +check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8], + uint32_t odd, uint32_t even, struct Crypto1State* sl, uint32_t no_par) +{ + uint32_t ks1, nr, ks2, rr, ks3, c, good = 1; + + for(c = 0; good && c < 8; ++c) { + sl->odd = odd ^ fastfwd[1][c]; + sl->even = even ^ fastfwd[0][c]; + + lfsr_rollback_bit(sl, 0, 0); + lfsr_rollback_bit(sl, 0, 0); + + ks3 = lfsr_rollback_bit(sl, 0, 0); + ks2 = lfsr_rollback_word(sl, 0, 0); + ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1); + + if (no_par) + break; + + nr = ks1 ^ (prefix | c << 5); + rr = ks2 ^ rresp; + + good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24); + good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16); + good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8); + good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0); + good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3; + } + + return sl + good; +} + + +/** lfsr_common_prefix + * Implentation of the common prefix attack. + */ +struct Crypto1State* +lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint32_t no_par) +{ + struct Crypto1State *statelist, *s; + uint32_t *odd, *even, *o, *e, top; + + odd = lfsr_prefix_ks(ks, 1); + even = lfsr_prefix_ks(ks, 0); + + s = statelist = malloc((sizeof *statelist) << 22); // was << 20. Need more for no_par special attack. Enough??? + if(!s || !odd || !even) { + free(statelist); + statelist = 0; + goto out; + } + + for(o = odd; *o + 1; ++o) + for(e = even; *e + 1; ++e) + for(top = 0; top < 64; ++top) { + *o += 1 << 21; + *e += (!(top & 7) + 1) << 21; + s = check_pfx_parity(pfx, rr, par, *o, *e, s, no_par); + } + + s->odd = s->even = 0; +out: + free(odd); + free(even); + return statelist; +} diff --git a/common/crapto1/crapto1.h b/common/crapto1/crapto1.h new file mode 100644 index 00000000..e718b1f2 --- /dev/null +++ b/common/crapto1/crapto1.h @@ -0,0 +1,98 @@ +/* crapto1.h + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License + as published by the Free Software Foundation; either version 2 + of the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + MA 02110-1301, US$ + + Copyright (C) 2008-2014 bla +*/ +#ifndef CRAPTO1_INCLUDED +#define CRAPTO1_INCLUDED +#include +#ifdef __cplusplus +extern "C" { +#endif + +struct Crypto1State {uint32_t odd, even;}; +#if defined(__arm__) +void crypto1_create(struct Crypto1State *s, uint64_t key); +#else +struct Crypto1State *crypto1_create(uint64_t key); +#endif +void crypto1_destroy(struct Crypto1State*); +void crypto1_get_lfsr(struct Crypto1State*, uint64_t*); +uint8_t crypto1_bit(struct Crypto1State*, uint8_t, int); +uint8_t crypto1_byte(struct Crypto1State*, uint8_t, int); +uint32_t crypto1_word(struct Crypto1State*, uint32_t, int); +uint32_t prng_successor(uint32_t x, uint32_t n); + +struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in); +struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3); +uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd); +struct Crypto1State* +lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint32_t no_par); + + +uint8_t lfsr_rollback_bit(struct Crypto1State* s, uint32_t in, int fb); +uint8_t lfsr_rollback_byte(struct Crypto1State* s, uint32_t in, int fb); +uint32_t lfsr_rollback_word(struct Crypto1State* s, uint32_t in, int fb); +int nonce_distance(uint32_t from, uint32_t to); +#define FOREACH_VALID_NONCE(N, FILTER, FSIZE)\ + uint32_t __n = 0,__M = 0, N = 0;\ + int __i;\ + for(; __n < 1 << 16; N = prng_successor(__M = ++__n, 16))\ + for(__i = FSIZE - 1; __i >= 0; __i--)\ + if(BIT(FILTER, __i) ^ parity(__M & 0xFF01))\ + break;\ + else if(__i)\ + __M = prng_successor(__M, (__i == 7) ? 48 : 8);\ + else + +#define LF_POLY_ODD (0x29CE5C) +#define LF_POLY_EVEN (0x870804) +#define BIT(x, n) ((x) >> (n) & 1) +#define BEBIT(x, n) BIT(x, (n) ^ 24) +static inline int parity(uint32_t x) +{ +#if !defined __i386__ || !defined __GNUC__ + x ^= x >> 16; + x ^= x >> 8; + x ^= x >> 4; + return BIT(0x6996, x & 0xf); +#else + __asm( "movl %1, %%eax\n" + "mov %%ax, %%cx\n" + "shrl $0x10, %%eax\n" + "xor %%ax, %%cx\n" + "xor %%ch, %%cl\n" + "setpo %%al\n" + "movzx %%al, %0\n": "=r"(x) : "r"(x): "eax","ecx"); + return x; +#endif +} +static inline int filter(uint32_t const x) +{ + uint32_t f; + + f = 0xf22c0 >> (x & 0xf) & 16; + f |= 0x6c9c0 >> (x >> 4 & 0xf) & 8; + f |= 0x3c8b0 >> (x >> 8 & 0xf) & 4; + f |= 0x1e458 >> (x >> 12 & 0xf) & 2; + f |= 0x0d938 >> (x >> 16 & 0xf) & 1; + return BIT(0xEC57E80A, f); +} +#ifdef __cplusplus +} +#endif +#endif diff --git a/common/crapto1/crypto1.c b/common/crapto1/crypto1.c new file mode 100644 index 00000000..a3f64a9f --- /dev/null +++ b/common/crapto1/crypto1.c @@ -0,0 +1,111 @@ +/* crypto1.c + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License + as published by the Free Software Foundation; either version 2 + of the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + MA 02110-1301, US + + Copyright (C) 2008-2008 bla +*/ +#include "crapto1.h" +#include + +#define SWAPENDIAN(x)\ + (x = (x >> 8 & 0xff00ff) | (x & 0xff00ff) << 8, x = x >> 16 | x << 16) + +#if defined(__arm__) && !defined(__linux__) && !defined(_WIN32) // bare metal ARM lacks malloc()/free() +void crypto1_create(struct Crypto1State *s, uint64_t key) +{ + int i; + + for(i = 47;s && i > 0; i -= 2) { + s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); + s->even = s->even << 1 | BIT(key, i ^ 7); + } + return; +} +void crypto1_destroy(struct Crypto1State *state) +{ + state->odd = 0; + state->even = 0; +} +#else +struct Crypto1State * crypto1_create(uint64_t key) +{ + struct Crypto1State *s = malloc(sizeof(*s)); + int i; + + for(i = 47;s && i > 0; i -= 2) { + s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); + s->even = s->even << 1 | BIT(key, i ^ 7); + } + return s; +} +void crypto1_destroy(struct Crypto1State *state) +{ + free(state); +} +#endif +void crypto1_get_lfsr(struct Crypto1State *state, uint64_t *lfsr) +{ + int i; + for(*lfsr = 0, i = 23; i >= 0; --i) { + *lfsr = *lfsr << 1 | BIT(state->odd, i ^ 3); + *lfsr = *lfsr << 1 | BIT(state->even, i ^ 3); + } +} +uint8_t crypto1_bit(struct Crypto1State *s, uint8_t in, int is_encrypted) +{ + uint32_t feedin, t; + uint8_t ret = filter(s->odd); + + feedin = ret & !!is_encrypted; + feedin ^= !!in; + feedin ^= LF_POLY_ODD & s->odd; + feedin ^= LF_POLY_EVEN & s->even; + s->even = s->even << 1 | parity(feedin); + + t = s->odd, s->odd = s->even, s->even = t; + + return ret; +} +uint8_t crypto1_byte(struct Crypto1State *s, uint8_t in, int is_encrypted) +{ + uint8_t i, ret = 0; + + for (i = 0; i < 8; ++i) + ret |= crypto1_bit(s, BIT(in, i), is_encrypted) << i; + + return ret; +} +uint32_t crypto1_word(struct Crypto1State *s, uint32_t in, int is_encrypted) +{ + uint32_t i, ret = 0; + + for (i = 0; i < 32; ++i) + ret |= crypto1_bit(s, BEBIT(in, i), is_encrypted) << (i ^ 24); + + return ret; +} + +/* prng_successor + * helper used to obscure the keystream during authentication + */ +uint32_t prng_successor(uint32_t x, uint32_t n) +{ + SWAPENDIAN(x); + while(n--) + x = x >> 1 | (x >> 16 ^ x >> 18 ^ x >> 19 ^ x >> 21) << 31; + + return SWAPENDIAN(x); +} diff --git a/tools/mfkey/Makefile b/tools/mfkey/Makefile index f4f7eb82..73ce032f 100755 --- a/tools/mfkey/Makefile +++ b/tools/mfkey/Makefile @@ -1,17 +1,20 @@ +VPATH = ../../common/crapto1 CC = gcc LD = gcc -CFLAGS = -Wall -Winline -O4 +CFLAGS = -I../../common -Wall -O4 LDFLAGS = -OBJS = crapto1.o crypto1.o -HEADERS = -EXES = mfkey64 mfkey32 -LIBS = - -all: $(OBJS) $(EXES) $(LIBS) +OBJS = crypto1.o crapto1.o +EXES = mfkey32 mfkey64 +WINEXES = $(patsubst %, %.exe, $(EXES)) -% : %.c $(OBJS) - $(LD) $(CFLAGS) -o $@ $< $(OBJS) $(LDFLAGS) +all: $(OBJS) $(EXES) + +%.o : %.c + $(CC) $(CFLAGS) -c -o $@ $< + +% : %.c + $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $(OBJS) $< clean: - rm -f $(OBJS) $(EXES) $(LIBS) + rm -f $(OBJS) $(EXES) $(WINEXES) diff --git a/tools/mfkey/crapto1.c b/tools/mfkey/crapto1.c deleted file mode 100755 index 9d491d12..00000000 --- a/tools/mfkey/crapto1.c +++ /dev/null @@ -1,478 +0,0 @@ -/* crapto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, - Boston, MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#if !defined LOWMEM && defined __GNUC__ -static uint8_t filterlut[1 << 20]; -static void __attribute__((constructor)) fill_lut() -{ - uint32_t i; - for(i = 0; i < 1 << 20; ++i) - filterlut[i] = filter(i); -} -#define filter(x) (filterlut[(x) & 0xfffff]) -#endif - -static void quicksort(uint32_t* const start, uint32_t* const stop) -{ - uint32_t *it = start + 1, *rit = stop; - - if(it > rit) - return; - - while(it < rit) - if(*it <= *start) - ++it; - else if(*rit > *start) - --rit; - else - *it ^= (*it ^= *rit, *rit ^= *it); - - if(*rit >= *start) - --rit; - if(rit != start) - *rit ^= (*rit ^= *start, *start ^= *rit); - - quicksort(start, rit - 1); - quicksort(rit + 1, stop); -} -/** binsearch - * Binary search for the first occurence of *stop's MSB in sorted [start,stop] - */ -static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop) -{ - uint32_t mid, val = *stop & 0xff000000; - while(start != stop) - if(start[mid = (stop - start) >> 1] > val) - stop = &start[mid]; - else - start += mid + 1; - - return start; -} - -/** update_contribution - * helper, calculates the partial linear feedback contributions and puts in MSB - */ -static inline void -update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) -{ - uint32_t p = *item >> 25; - - p = p << 1 | parity(*item & mask1); - p = p << 1 | parity(*item & mask2); - *item = p << 24 | (*item & 0xffffff); -} - -/** extend_table - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void -extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) -{ - in <<= 24; - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) - if(filter(*tbl) ^ filter(*tbl | 1)) { - *tbl |= filter(*tbl) ^ bit; - update_contribution(tbl, m1, m2); - *tbl ^= in; - } else if(filter(*tbl) == bit) { - *++*end = tbl[1]; - tbl[1] = tbl[0] | 1; - update_contribution(tbl, m1, m2); - *tbl++ ^= in; - update_contribution(tbl, m1, m2); - *tbl ^= in; - } else - *tbl-- = *(*end)--; -} -/** extend_table_simple - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) -{ - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) - if(filter(*tbl) ^ filter(*tbl | 1)) - *tbl |= filter(*tbl) ^ bit; - else if(filter(*tbl) == bit) { - *++*end = *++tbl; - *tbl = tbl[-1] | 1; - } else - *tbl-- = *(*end)--; -} -/** recover - * recursively narrow down the search space, 4 bits of keystream at a time - */ -static struct Crypto1State* -recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, - uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem, - struct Crypto1State *sl, uint32_t in) -{ - uint32_t *o, *e, i; - - if(rem == -1) { - for(e = e_head; e <= e_tail; ++e) { - *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4); - for(o = o_head; o <= o_tail; ++o, ++sl) { - sl->even = *o; - sl->odd = *e ^ parity(*o & LF_POLY_ODD); - sl[1].odd = sl[1].even = 0; - } - } - return sl; - } - - for(i = 0; i < 4 && rem--; i++) { - oks >>= 1; - eks >>= 1; - in >>= 2; - extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, - LF_POLY_ODD << 1, 0); - if(o_head > o_tail) - return sl; - - extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, - LF_POLY_EVEN << 1 | 1, in & 3); - if(e_head > e_tail) - return sl; - } - - quicksort(o_head, o_tail); - quicksort(e_head, e_tail); - - while(o_tail >= o_head && e_tail >= e_head) - if(((*o_tail ^ *e_tail) >> 24) == 0) { - o_tail = binsearch(o_head, o = o_tail); - e_tail = binsearch(e_head, e = e_tail); - sl = recover(o_tail--, o, oks, - e_tail--, e, eks, rem, sl, in); - } - else if(*o_tail > *e_tail) - o_tail = binsearch(o_head, o_tail) - 1; - else - e_tail = binsearch(e_head, e_tail) - 1; - - return sl; -} -/** lfsr_recovery - * recover the state of the lfsr given 32 bits of the keystream - * additionally you can use the in parameter to specify the value - * that was fed into the lfsr at the time the keystream was generated - */ -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) -{ - struct Crypto1State *statelist; - uint32_t *odd_head = 0, *odd_tail = 0, oks = 0; - uint32_t *even_head = 0, *even_tail = 0, eks = 0; - int i; - - for(i = 31; i >= 0; i -= 2) - oks = oks << 1 | BEBIT(ks2, i); - for(i = 30; i >= 0; i -= 2) - eks = eks << 1 | BEBIT(ks2, i); - - odd_head = odd_tail = malloc(sizeof(uint32_t) << 21); - even_head = even_tail = malloc(sizeof(uint32_t) << 21); - statelist = malloc(sizeof(struct Crypto1State) << 18); - if(!odd_tail-- || !even_tail-- || !statelist) { - free(statelist); - statelist = 0; - goto out; - } - - statelist->odd = statelist->even = 0; - - for(i = 1 << 20; i >= 0; --i) { - if(filter(i) == (oks & 1)) - *++odd_tail = i; - if(filter(i) == (eks & 1)) - *++even_tail = i; - } - - for(i = 0; i < 4; i++) { - extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1); - extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1); - } - - in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); - recover(odd_head, odd_tail, oks, - even_head, even_tail, eks, 11, statelist, in << 1); - -out: - free(odd_head); - free(even_head); - return statelist; -} - -static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214, - 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83, - 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA}; -static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60, - 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8, - 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20, - 0x7EC7EE90, 0x7F63F748, 0x79117020}; -static const uint32_t T1[] = { - 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66, - 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B, - 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615, - 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C}; -static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0, - 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268, - 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0, - 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0, - 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950, - 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0}; -static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD}; -static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0}; -/** Reverse 64 bits of keystream into possible cipher states - * Variation mentioned in the paper. Somewhat optimized version - */ -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3) -{ - struct Crypto1State *statelist, *sl; - uint8_t oks[32], eks[32], hi[32]; - uint32_t low = 0, win = 0; - uint32_t *tail, table[1 << 16]; - int i, j; - - sl = statelist = malloc(sizeof(struct Crypto1State) << 4); - if(!sl) - return 0; - sl->odd = sl->even = 0; - - for(i = 30; i >= 0; i -= 2) { - oks[i >> 1] = BEBIT(ks2, i); - oks[16 + (i >> 1)] = BEBIT(ks3, i); - } - for(i = 31; i >= 0; i -= 2) { - eks[i >> 1] = BEBIT(ks2, i); - eks[16 + (i >> 1)] = BEBIT(ks3, i); - } - - for(i = 0xfffff; i >= 0; --i) { - if (filter(i) != oks[0]) - continue; - - *(tail = table) = i; - for(j = 1; tail >= table && j < 29; ++j) - extend_table_simple(table, &tail, oks[j]); - - if(tail < table) - continue; - - for(j = 0; j < 19; ++j) - low = low << 1 | parity(i & S1[j]); - for(j = 0; j < 32; ++j) - hi[j] = parity(i & T1[j]); - - for(; tail >= table; --tail) { - for(j = 0; j < 3; ++j) { - *tail = *tail << 1; - *tail |= parity((i & C1[j]) ^ (*tail & C2[j])); - if(filter(*tail) != oks[29 + j]) - goto continue2; - } - - for(j = 0; j < 19; ++j) - win = win << 1 | parity(*tail & S2[j]); - - win ^= low; - for(j = 0; j < 32; ++j) { - win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]); - if(filter(win) != eks[j]) - goto continue2; - } - - *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail); - sl->odd = *tail ^ parity(LF_POLY_ODD & win); - sl->even = win; - ++sl; - sl->odd = sl->even = 0; - continue2:; - } - } - return statelist; -} - -/** lfsr_rollback_bit - * Rollback the shift register in order to get previous states - */ -uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb) -{ - int out; - uint8_t ret; - - s->odd &= 0xffffff; - s->odd ^= (s->odd ^= s->even, s->even ^= s->odd); - - out = s->even & 1; - out ^= LF_POLY_EVEN & (s->even >>= 1); - out ^= LF_POLY_ODD & s->odd; - out ^= !!in; - out ^= (ret = filter(s->odd)) & !!fb; - - s->even |= parity(out) << 23; - return ret; -} -/** lfsr_rollback_byte - * Rollback the shift register in order to get previous states - */ -uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb) -{ - int i, ret = 0; - for (i = 7; i >= 0; --i) - ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i; - return ret; -} -/** lfsr_rollback_word - * Rollback the shift register in order to get previous states - */ -uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb) -{ - int i; - uint32_t ret = 0; - for (i = 31; i >= 0; --i) - ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24); - return ret; -} - -/** nonce_distance - * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y - */ -static uint16_t *dist = 0; -int nonce_distance(uint32_t from, uint32_t to) -{ - uint16_t x, i; - if(!dist) { - dist = malloc(2 << 16); - if(!dist) - return -1; - for (x = i = 1; i; ++i) { - dist[(x & 0xff) << 8 | x >> 8] = i; - x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15; - } - } - return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535; -} - - -static uint32_t fastfwd[2][8] = { - { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB}, - { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}}; -/** lfsr_prefix_ks - * - * Is an exported helper function from the common prefix attack - * Described in the "dark side" paper. It returns an -1 terminated array - * of possible partial(21 bit) secret state. - * The required keystream(ks) needs to contain the keystream that was used to - * encrypt the NACK which is observed when varying only the 3 last bits of Nr - * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3 - */ -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd) -{ - uint32_t c, entry, *candidates = malloc(4 << 10); - int i, size = 0, good; - - if(!candidates) - return 0; - - for(i = 0; i < 1 << 21; ++i) { - for(c = 0, good = 1; good && c < 8; ++c) { - entry = i ^ fastfwd[isodd][c]; - good &= (BIT(ks[c], isodd) == filter(entry >> 1)); - good &= (BIT(ks[c], isodd + 2) == filter(entry)); - } - if(good) - candidates[size++] = i; - } - - candidates[size] = -1; - - return candidates; -} - -/** check_pfx_parity - * helper function which eliminates possible secret states using parity bits - */ -static struct Crypto1State* -check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8], - uint32_t odd, uint32_t even, struct Crypto1State* sl) -{ - uint32_t ks1, nr, ks2, rr, ks3, c, good = 1; - - for(c = 0; good && c < 8; ++c) { - sl->odd = odd ^ fastfwd[1][c]; - sl->even = even ^ fastfwd[0][c]; - - lfsr_rollback_bit(sl, 0, 0); - lfsr_rollback_bit(sl, 0, 0); - - ks3 = lfsr_rollback_bit(sl, 0, 0); - ks2 = lfsr_rollback_word(sl, 0, 0); - ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1); - - nr = ks1 ^ (prefix | c << 5); - rr = ks2 ^ rresp; - - good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24); - good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16); - good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8); - good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0); - good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3; - } - - return sl + good; -} - - -/** lfsr_common_prefix - * Implentation of the common prefix attack. - */ -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8]) -{ - struct Crypto1State *statelist, *s; - uint32_t *odd, *even, *o, *e, top; - - odd = lfsr_prefix_ks(ks, 1); - even = lfsr_prefix_ks(ks, 0); - - s = statelist = malloc((sizeof *statelist) << 20); - if(!s || !odd || !even) { - free(statelist); - statelist = 0; - goto out; - } - - for(o = odd; *o + 1; ++o) - for(e = even; *e + 1; ++e) - for(top = 0; top < 64; ++top) { - *o += 1 << 21; - *e += (!(top & 7) + 1) << 21; - s = check_pfx_parity(pfx, rr, par, *o, *e, s); - } - - s->odd = s->even = 0; -out: - free(odd); - free(even); - return statelist; -} diff --git a/tools/mfkey/crapto1.h b/tools/mfkey/crapto1.h deleted file mode 100755 index 127a17d1..00000000 --- a/tools/mfkey/crapto1.h +++ /dev/null @@ -1,93 +0,0 @@ -/* crapto1.h - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#ifndef CRAPTO1_INCLUDED -#define CRAPTO1_INCLUDED -#include -#ifdef __cplusplus -extern "C" { -#endif - -struct Crypto1State {uint32_t odd, even;}; -struct Crypto1State* crypto1_create(uint64_t); -void crypto1_destroy(struct Crypto1State*); -void crypto1_get_lfsr(struct Crypto1State*, uint64_t*); -uint8_t crypto1_bit(struct Crypto1State*, uint8_t, int); -uint8_t crypto1_byte(struct Crypto1State*, uint8_t, int); -uint32_t crypto1_word(struct Crypto1State*, uint32_t, int); -uint32_t prng_successor(uint32_t x, uint32_t n); - -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in); -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3); -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd); -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8]); - -uint8_t lfsr_rollback_bit(struct Crypto1State* s, uint32_t in, int fb); -uint8_t lfsr_rollback_byte(struct Crypto1State* s, uint32_t in, int fb); -uint32_t lfsr_rollback_word(struct Crypto1State* s, uint32_t in, int fb); -int nonce_distance(uint32_t from, uint32_t to); -#define FOREACH_VALID_NONCE(N, FILTER, FSIZE)\ - uint32_t __n = 0,__M = 0, N = 0;\ - int __i;\ - for(; __n < 1 << 16; N = prng_successor(__M = ++__n, 16))\ - for(__i = FSIZE - 1; __i >= 0; __i--)\ - if(BIT(FILTER, __i) ^ parity(__M & 0xFF01))\ - break;\ - else if(__i)\ - __M = prng_successor(__M, (__i == 7) ? 48 : 8);\ - else - -#define LF_POLY_ODD (0x29CE5C) -#define LF_POLY_EVEN (0x870804) -#define BIT(x, n) ((x) >> (n) & 1) -#define BEBIT(x, n) BIT(x, (n) ^ 24) -static inline int parity(uint32_t x) -{ -#if !defined __i386__ || !defined __GNUC__ - x ^= x >> 16; - x ^= x >> 8; - x ^= x >> 4; - return BIT(0x6996, x & 0xf); -#else - asm( "movl %1, %%eax\n" - "mov %%ax, %%cx\n" - "shrl $0x10, %%eax\n" - "xor %%ax, %%cx\n" - "xor %%ch, %%cl\n" - "setpo %%al\n" - "movzx %%al, %0\n": "=r"(x) : "r"(x): "eax","ecx"); - return x; -#endif -} -static inline int filter(uint32_t const x) -{ - uint32_t f; - - f = 0xf22c0 >> (x & 0xf) & 16; - f |= 0x6c9c0 >> (x >> 4 & 0xf) & 8; - f |= 0x3c8b0 >> (x >> 8 & 0xf) & 4; - f |= 0x1e458 >> (x >> 12 & 0xf) & 2; - f |= 0x0d938 >> (x >> 16 & 0xf) & 1; - return BIT(0xEC57E80A, f); -} -#ifdef __cplusplus -} -#endif -#endif diff --git a/tools/mfkey/crypto1.c b/tools/mfkey/crypto1.c deleted file mode 100755 index e2aab71b..00000000 --- a/tools/mfkey/crypto1.c +++ /dev/null @@ -1,93 +0,0 @@ -/* crypto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#define SWAPENDIAN(x)\ - (x = (x >> 8 & 0xff00ff) | (x & 0xff00ff) << 8, x = x >> 16 | x << 16) - -struct Crypto1State * crypto1_create(uint64_t key) -{ - struct Crypto1State *s = malloc(sizeof(*s)); - int i; - - for(i = 47;s && i > 0; i -= 2) { - s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); - s->even = s->even << 1 | BIT(key, i ^ 7); - } - return s; -} -void crypto1_destroy(struct Crypto1State *state) -{ - free(state); -} -void crypto1_get_lfsr(struct Crypto1State *state, uint64_t *lfsr) -{ - int i; - for(*lfsr = 0, i = 23; i >= 0; --i) { - *lfsr = *lfsr << 1 | BIT(state->odd, i ^ 3); - *lfsr = *lfsr << 1 | BIT(state->even, i ^ 3); - } -} -uint8_t crypto1_bit(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint32_t feedin; - uint8_t ret = filter(s->odd); - - feedin = ret & !!is_encrypted; - feedin ^= !!in; - feedin ^= LF_POLY_ODD & s->odd; - feedin ^= LF_POLY_EVEN & s->even; - s->even = s->even << 1 | parity(feedin); - - s->odd ^= (s->odd ^= s->even, s->even ^= s->odd); - - return ret; -} -uint8_t crypto1_byte(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint8_t i, ret = 0; - - for (i = 0; i < 8; ++i) - ret |= crypto1_bit(s, BIT(in, i), is_encrypted) << i; - - return ret; -} -uint32_t crypto1_word(struct Crypto1State *s, uint32_t in, int is_encrypted) -{ - uint32_t i, ret = 0; - - for (i = 0; i < 32; ++i) - ret |= crypto1_bit(s, BEBIT(in, i), is_encrypted) << (i ^ 24); - - return ret; -} - -/* prng_successor - * helper used to obscure the keystream during authentication - */ -uint32_t prng_successor(uint32_t x, uint32_t n) -{ - SWAPENDIAN(x); - while(n--) - x = x >> 1 | (x >> 16 ^ x >> 18 ^ x >> 19 ^ x >> 21) << 31; - - return SWAPENDIAN(x); -} diff --git a/tools/mfkey/mfkey32.c b/tools/mfkey/mfkey32.c index 44fee4a2..a018c5df 100755 --- a/tools/mfkey/mfkey32.c +++ b/tools/mfkey/mfkey32.c @@ -1,5 +1,5 @@ #include -#include "crapto1.h" +#include "crapto1/crapto1.h" #include #include diff --git a/tools/mfkey/mfkey64.c b/tools/mfkey/mfkey64.c index e7eb9dbe..4b9b29ee 100755 --- a/tools/mfkey/mfkey64.c +++ b/tools/mfkey/mfkey64.c @@ -1,5 +1,5 @@ #include -#include "crapto1.h" +#include "crapto1/crapto1.h" #include #include @@ -34,7 +34,7 @@ int main (int argc, char *argv[]) { for (int i = 0; i < encc; i++) { enclen[i] = strlen(argv[i + 6]) / 2; for (int i2 = 0; i2 < enclen[i]; i2++) { - sscanf(argv[i+6] + i2*2,"%2x", (uint8_t*)&enc[i][i2]); + sscanf(argv[i+6] + i2*2,"%2x", (unsigned int *)&enc[i][i2]); } } printf("Recovering key for:\n"); diff --git a/tools/nonce2key/Makefile b/tools/nonce2key/Makefile deleted file mode 100644 index 54abf80e..00000000 --- a/tools/nonce2key/Makefile +++ /dev/null @@ -1,22 +0,0 @@ -CC = gcc -LD = gcc -CFLAGS = -Wall -O4 -c -LDFLAGS = - -OBJS = crypto1.o crapto1.o -HEADERS = crapto1.h -EXES = nonce2key - -all: $(OBJS) $(EXES) - -%.o : %.c - $(CC) $(CFLAGS) -o $@ $< - -% : %.c - $(LD) $(LDFLAGS) -o $@ $(OBJS) $< - -crypto1test: libnfc $(OBJS) - $(LD) $(LDFLAGS) -o crypto1test crypto1test.c $(OBJS) - -clean: - rm -f $(OBJS) $(EXES) diff --git a/tools/nonce2key/crapto1.c b/tools/nonce2key/crapto1.c deleted file mode 100644 index c0a158b5..00000000 --- a/tools/nonce2key/crapto1.c +++ /dev/null @@ -1,494 +0,0 @@ -/* crapto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, - Boston, MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#if !defined LOWMEM && defined __GNUC__ -static uint8_t filterlut[1 << 20]; -static void __attribute__((constructor)) fill_lut() -{ - uint32_t i; - for(i = 0; i < 1 << 20; ++i) - filterlut[i] = filter(i); -} -#define filter(x) (filterlut[(x) & 0xfffff]) -#endif - -static void quicksort(uint32_t* const start, uint32_t* const stop) -{ - uint32_t *it = start + 1, *rit = stop; - - if(it > rit) - return; - - while(it < rit) - if(*it <= *start) - ++it; - else if(*rit > *start) - --rit; - else - *it ^= (*it ^= *rit, *rit ^= *it); - - if(*rit >= *start) - --rit; - if(rit != start) - *rit ^= (*rit ^= *start, *start ^= *rit); - - quicksort(start, rit - 1); - quicksort(rit + 1, stop); -} -/** binsearch - * Binary search for the first occurence of *stop's MSB in sorted [start,stop] - */ -static inline uint32_t* -binsearch(uint32_t *start, uint32_t *stop) -{ - uint32_t mid, val = *stop & 0xff000000; - while(start != stop) - if(start[mid = (stop - start) >> 1] > val) - stop = &start[mid]; - else - start += mid + 1; - - return start; -} - -/** update_contribution - * helper, calculates the partial linear feedback contributions and puts in MSB - */ -static inline void -update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) -{ - uint32_t p = *item >> 25; - - p = p << 1 | parity(*item & mask1); - p = p << 1 | parity(*item & mask2); - *item = p << 24 | (*item & 0xffffff); -} - -/** extend_table - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void -extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) -{ - in <<= 24; - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) - if(filter(*tbl) ^ filter(*tbl | 1)) { - *tbl |= filter(*tbl) ^ bit; - update_contribution(tbl, m1, m2); - *tbl ^= in; - } else if(filter(*tbl) == bit) { - *++*end = tbl[1]; - tbl[1] = tbl[0] | 1; - update_contribution(tbl, m1, m2); - *tbl++ ^= in; - update_contribution(tbl, m1, m2); - *tbl ^= in; - } else - *tbl-- = *(*end)--; -} -/** extend_table_simple - * using a bit of the keystream extend the table of possible lfsr states - */ -static inline void -extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) -{ - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) - if(filter(*tbl) ^ filter(*tbl | 1)) { - *tbl |= filter(*tbl) ^ bit; - } else if(filter(*tbl) == bit) { - *++*end = *++tbl; - *tbl = tbl[-1] | 1; - } else - *tbl-- = *(*end)--; -} -/** recover - * recursively narrow down the search space, 4 bits of keystream at a time - */ -static struct Crypto1State* -recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, - uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem, - struct Crypto1State *sl, uint32_t in) -{ - uint32_t *o, *e, i; - - if(rem == -1) { - for(e = e_head; e <= e_tail; ++e) { - *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4); - for(o = o_head; o <= o_tail; ++o, ++sl) { - sl->even = *o; - sl->odd = *e ^ parity(*o & LF_POLY_ODD); - sl[1].odd = sl[1].even = 0; - } - } - return sl; - } - - for(i = 0; i < 4 && rem--; i++) { - extend_table(o_head, &o_tail, (oks >>= 1) & 1, - LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0); - if(o_head > o_tail) - return sl; - - extend_table(e_head, &e_tail, (eks >>= 1) & 1, - LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 3); - if(e_head > e_tail) - return sl; - } - - quicksort(o_head, o_tail); - quicksort(e_head, e_tail); - - while(o_tail >= o_head && e_tail >= e_head) - if(((*o_tail ^ *e_tail) >> 24) == 0) { - o_tail = binsearch(o_head, o = o_tail); - e_tail = binsearch(e_head, e = e_tail); - sl = recover(o_tail--, o, oks, - e_tail--, e, eks, rem, sl, in); - } - else if(*o_tail > *e_tail) - o_tail = binsearch(o_head, o_tail) - 1; - else - e_tail = binsearch(e_head, e_tail) - 1; - - return sl; -} -/** lfsr_recovery - * recover the state of the lfsr given 32 bits of the keystream - * additionally you can use the in parameter to specify the value - * that was fed into the lfsr at the time the keystream was generated - */ -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) -{ - struct Crypto1State *statelist; - uint32_t *odd_head = 0, *odd_tail = 0, oks = 0; - uint32_t *even_head = 0, *even_tail = 0, eks = 0; - int i; - - for(i = 31; i >= 0; i -= 2) - oks = oks << 1 | BEBIT(ks2, i); - for(i = 30; i >= 0; i -= 2) - eks = eks << 1 | BEBIT(ks2, i); - - odd_head = odd_tail = malloc(sizeof(uint32_t) << 21); - even_head = even_tail = malloc(sizeof(uint32_t) << 21); - statelist = malloc(sizeof(struct Crypto1State) << 18); - if(!odd_tail-- || !even_tail-- || !statelist) - goto out; - - statelist->odd = statelist->even = 0; - - for(i = 1 << 20; i >= 0; --i) { - if(filter(i) == (oks & 1)) - *++odd_tail = i; - if(filter(i) == (eks & 1)) - *++even_tail = i; - } - - for(i = 0; i < 4; i++) { - extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1); - extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1); - } - - in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); - recover(odd_head, odd_tail, oks, - even_head, even_tail, eks, 11, statelist, in << 1); - -out: - free(odd_head); - free(even_head); - return statelist; -} - -static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214, - 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83, - 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA}; -static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60, - 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8, - 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20, - 0x7EC7EE90, 0x7F63F748, 0x79117020}; -static const uint32_t T1[] = { - 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66, - 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B, - 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615, - 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C}; -static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0, - 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268, - 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0, - 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0, - 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950, - 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0}; -static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD}; -static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0}; -/** Reverse 64 bits of keystream into possible cipher states - * Variation mentioned in the paper. Somewhat optimized version - */ -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3) -{ - struct Crypto1State *statelist, *sl; - uint8_t oks[32], eks[32], hi[32]; - uint32_t low = 0, win = 0; - uint32_t *tail, table[1 << 16]; - int i, j; - - sl = statelist = malloc(sizeof(struct Crypto1State) << 4); - if(!sl) - return 0; - sl->odd = sl->even = 0; - - for(i = 30; i >= 0; i -= 2) { - oks[i >> 1] = BIT(ks2, i ^ 24); - oks[16 + (i >> 1)] = BIT(ks3, i ^ 24); - } - for(i = 31; i >= 0; i -= 2) { - eks[i >> 1] = BIT(ks2, i ^ 24); - eks[16 + (i >> 1)] = BIT(ks3, i ^ 24); - } - - for(i = 0xfffff; i >= 0; --i) { - if (filter(i) != oks[0]) - continue; - - *(tail = table) = i; - for(j = 1; tail >= table && j < 29; ++j) - extend_table_simple(table, &tail, oks[j]); - - if(tail < table) - continue; - - for(j = 0; j < 19; ++j) - low = low << 1 | parity(i & S1[j]); - for(j = 0; j < 32; ++j) - hi[j] = parity(i & T1[j]); - - for(; tail >= table; --tail) { - for(j = 0; j < 3; ++j) { - *tail = *tail << 1; - *tail |= parity((i & C1[j]) ^ (*tail & C2[j])); - if(filter(*tail) != oks[29 + j]) - goto continue2; - } - - for(j = 0; j < 19; ++j) - win = win << 1 | parity(*tail & S2[j]); - - win ^= low; - for(j = 0; j < 32; ++j) { - win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]); - if(filter(win) != eks[j]) - goto continue2; - } - - *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail); - sl->odd = *tail ^ parity(LF_POLY_ODD & win); - sl->even = win; - ++sl; - sl->odd = sl->even = 0; - continue2:; - } - } - return statelist; -} - -/** lfsr_rollback_bit - * Rollback the shift register in order to get previous states - */ -void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb) -{ - int out; - - s->odd &= 0xffffff; - s->odd ^= (s->odd ^= s->even, s->even ^= s->odd); - - out = s->even & 1; - out ^= LF_POLY_EVEN & (s->even >>= 1); - out ^= LF_POLY_ODD & s->odd; - out ^= !!in; - out ^= filter(s->odd) & !!fb; - - s->even |= parity(out) << 23; -} -/** lfsr_rollback_byte - * Rollback the shift register in order to get previous states - */ -void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb) -{ - int i; - for (i = 7; i >= 0; --i) - lfsr_rollback_bit(s, BEBIT(in, i), fb); -} -/** lfsr_rollback_word - * Rollback the shift register in order to get previous states - */ -void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb) -{ - int i; - for (i = 31; i >= 0; --i) - lfsr_rollback_bit(s, BEBIT(in, i), fb); -} - -/** nonce_distance - * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y - */ -static uint16_t *dist = 0; -int nonce_distance(uint32_t from, uint32_t to) -{ - uint16_t x, i; - if(!dist) { - dist = malloc(2 << 16); - if(!dist) - return -1; - for (x = i = 1; i; ++i) { - dist[(x & 0xff) << 8 | x >> 8] = i; - x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15; - } - } - return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535; -} - - -static uint32_t fastfwd[2][8] = { - { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB}, - { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}}; - - -/** lfsr_prefix_ks - * - * Is an exported helper function from the common prefix attack - * Described in the "dark side" paper. It returns an -1 terminated array - * of possible partial(21 bit) secret state. - * The required keystream(ks) needs to contain the keystream that was used to - * encrypt the NACK which is observed when varying only the 4 last bits of Nr - * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3 - */ -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd) -{ - uint32_t *candidates = malloc(4 << 21); - uint32_t c, entry; - int size, i; - - if(!candidates) - return 0; - - size = (1 << 21) - 1; - for(i = 0; i <= size; ++i) - candidates[i] = i; - - for(c = 0; c < 8; ++c) - for(i = 0;i <= size; ++i) { - entry = candidates[i] ^ fastfwd[isodd][c]; - - if(filter(entry >> 1) == BIT(ks[c], isodd)) - if(filter(entry) == BIT(ks[c], isodd + 2)) - continue; - - candidates[i--] = candidates[size--]; - } - - candidates[size + 1] = -1; - - return candidates; -} - -/** brute_top - * helper function which eliminates possible secret states using parity bits - */ -static struct Crypto1State* -brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8], - uint32_t odd, uint32_t even, struct Crypto1State* sl) -{ - struct Crypto1State s; - uint32_t ks1, nr, ks2, rr, ks3, good, c; - - for(c = 0; c < 8; ++c) { - s.odd = odd ^ fastfwd[1][c]; - s.even = even ^ fastfwd[0][c]; - - lfsr_rollback_bit(&s, 0, 0); - lfsr_rollback_bit(&s, 0, 0); - lfsr_rollback_bit(&s, 0, 0); - - lfsr_rollback_word(&s, 0, 0); - lfsr_rollback_word(&s, prefix | c << 5, 1); - - sl->odd = s.odd; - sl->even = s.even; - - ks1 = crypto1_word(&s, prefix | c << 5, 1); - ks2 = crypto1_word(&s,0,0); - ks3 = crypto1_word(&s, 0,0); - nr = ks1 ^ (prefix | c << 5); - rr = ks2 ^ rresp; - - good = 1; - good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24); - good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16); - good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8); - good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0); - good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24); - - if(!good) - return sl; - } - - return ++sl; -} - - -/** lfsr_common_prefix - * Implentation of the common prefix attack. - * Requires the 28 bit constant prefix used as reader nonce (pfx) - * The reader response used (rr) - * The keystream used to encrypt the observed NACK's (ks) - * The parity bits (par) - * It returns a zero terminated list of possible cipher states after the - * tag nonce was fed in - */ -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8]) -{ - struct Crypto1State *statelist, *s; - uint32_t *odd, *even, *o, *e, top; - - odd = lfsr_prefix_ks(ks, 1); - even = lfsr_prefix_ks(ks, 0); - - statelist = malloc((sizeof *statelist) << 20); - if(!statelist || !odd || !even) - return 0; - - - s = statelist; - for(o = odd; *o != 0xffffffff; ++o) - for(e = even; *e != 0xffffffff; ++e) - for(top = 0; top < 64; ++top) { - *o = (*o & 0x1fffff) | (top << 21); - *e = (*e & 0x1fffff) | (top >> 3) << 21; - s = brute_top(pfx, rr, par, *o, *e, s); - } - - s->odd = s->even = 0; - - free(odd); - free(even); - - return statelist; -} diff --git a/tools/nonce2key/crapto1.h b/tools/nonce2key/crapto1.h deleted file mode 100644 index 3b2cf173..00000000 --- a/tools/nonce2key/crapto1.h +++ /dev/null @@ -1,94 +0,0 @@ -/* crapto1.h - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US$ - - Copyright (C) 2008-2008 bla -*/ -#ifndef CRAPTO1_INCLUDED -#define CRAPTO1_INCLUDED -#include -#ifdef __cplusplus -extern "C" { -#endif - -struct Crypto1State {uint32_t odd, even;}; -struct Crypto1State* crypto1_create(uint64_t); -void crypto1_destroy(struct Crypto1State*); -void crypto1_get_lfsr(struct Crypto1State*, uint64_t*); -uint8_t crypto1_bit(struct Crypto1State*, uint8_t, int); -uint8_t crypto1_byte(struct Crypto1State*, uint8_t, int); -uint32_t crypto1_word(struct Crypto1State*, uint32_t, int); -uint32_t prng_successor(uint32_t x, uint32_t n); - -struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in); -struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3); -uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd); -struct Crypto1State* -lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8]); - - -void lfsr_rollback_bit(struct Crypto1State* s, uint32_t in, int fb); -void lfsr_rollback_byte(struct Crypto1State* s, uint32_t in, int fb); -void lfsr_rollback_word(struct Crypto1State* s, uint32_t in, int fb); -int nonce_distance(uint32_t from, uint32_t to); -#define FOREACH_VALID_NONCE(N, FILTER, FSIZE)\ - uint32_t __n = 0,__M = 0, N = 0;\ - int __i;\ - for(; __n < 1 << 16; N = prng_successor(__M = ++__n, 16))\ - for(__i = FSIZE - 1; __i >= 0; __i--)\ - if(BIT(FILTER, __i) ^ parity(__M & 0xFF01))\ - break;\ - else if(__i)\ - __M = prng_successor(__M, (__i == 7) ? 48 : 8);\ - else - -#define LF_POLY_ODD (0x29CE5C) -#define LF_POLY_EVEN (0x870804) -#define BIT(x, n) ((x) >> (n) & 1) -#define BEBIT(x, n) BIT(x, (n) ^ 24) -static inline int parity(uint32_t x) -{ -#if !defined __i386__ || !defined __GNUC__ - x ^= x >> 16; - x ^= x >> 8; - x ^= x >> 4; - return BIT(0x6996, x & 0xf); -#else - asm( "movl %1, %%eax\n" - "mov %%ax, %%cx\n" - "shrl $0x10, %%eax\n" - "xor %%ax, %%cx\n" - "xor %%ch, %%cl\n" - "setpo %%al\n" - "movzx %%al, %0\n": "=r"(x) : "r"(x): "eax","ecx"); - return x; -#endif -} -static inline int filter(uint32_t const x) -{ - uint32_t f; - - f = 0xf22c0 >> (x & 0xf) & 16; - f |= 0x6c9c0 >> (x >> 4 & 0xf) & 8; - f |= 0x3c8b0 >> (x >> 8 & 0xf) & 4; - f |= 0x1e458 >> (x >> 12 & 0xf) & 2; - f |= 0x0d938 >> (x >> 16 & 0xf) & 1; - return BIT(0xEC57E80A, f); -} -#ifdef __cplusplus -} -#endif -#endif diff --git a/tools/nonce2key/crypto1.c b/tools/nonce2key/crypto1.c deleted file mode 100644 index fbf88898..00000000 --- a/tools/nonce2key/crypto1.c +++ /dev/null @@ -1,93 +0,0 @@ -/* crypto1.c - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License - as published by the Free Software Foundation; either version 2 - of the License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, - MA 02110-1301, US - - Copyright (C) 2008-2008 bla -*/ -#include "crapto1.h" -#include - -#define SWAPENDIAN(x)\ - (x = (x >> 8 & 0xff00ff) | (x & 0xff00ff) << 8, x = x >> 16 | x << 16) - -struct Crypto1State * crypto1_create(uint64_t key) -{ - struct Crypto1State *s = malloc(sizeof(*s)); - int i; - - for(i = 47;s && i > 0; i -= 2) { - s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); - s->even = s->even << 1 | BIT(key, i ^ 7); - } - return s; -} -void crypto1_destroy(struct Crypto1State *state) -{ - free(state); -} -void crypto1_get_lfsr(struct Crypto1State *state, uint64_t *lfsr) -{ - int i; - for(*lfsr = 0, i = 23; i >= 0; --i) { - *lfsr = *lfsr << 1 | BIT(state->odd, i ^ 3); - *lfsr = *lfsr << 1 | BIT(state->even, i ^ 3); - } -} -uint8_t crypto1_bit(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint32_t feedin; - uint8_t ret = filter(s->odd); - - feedin = ret & !!is_encrypted; - feedin ^= !!in; - feedin ^= LF_POLY_ODD & s->odd; - feedin ^= LF_POLY_EVEN & s->even; - s->even = s->even << 1 | parity(feedin); - - s->odd ^= (s->odd ^= s->even, s->even ^= s->odd); - - return ret; -} -uint8_t crypto1_byte(struct Crypto1State *s, uint8_t in, int is_encrypted) -{ - uint8_t i, ret = 0; - - for (i = 0; i < 8; ++i) - ret |= crypto1_bit(s, BIT(in, i), is_encrypted) << i; - - return ret; -} -uint32_t crypto1_word(struct Crypto1State *s, uint32_t in, int is_encrypted) -{ - uint32_t i, ret = 0; - - for (i = 0; i < 4; ++i, in <<= 8) - ret = ret << 8 | crypto1_byte(s, in >> 24, is_encrypted); - - return ret; -} - -/* prng_successor - * helper used to obscure the keystream during authentication - */ -uint32_t prng_successor(uint32_t x, uint32_t n) -{ - SWAPENDIAN(x); - while(n--) - x = x >> 1 | (x >> 16 ^ x >> 18 ^ x >> 19 ^ x >> 21) << 31; - - return SWAPENDIAN(x); -} diff --git a/tools/nonce2key/nonce2key.c b/tools/nonce2key/nonce2key.c deleted file mode 100644 index cc22ce77..00000000 --- a/tools/nonce2key/nonce2key.c +++ /dev/null @@ -1,57 +0,0 @@ -#include "crapto1.h" -#include -#include -typedef unsigned char byte_t; - -int main(const int argc, const char* argv[]) { - struct Crypto1State *state; - uint32_t pos, uid, nt, nr, rr, nr_diff, ks1, ks2; - byte_t bt, i, ks3x[8], par[8][8]; - uint64_t key, key_recovered; - uint64_t par_info; - uint64_t ks_info; - nr = rr = 0; - - if (argc < 5) { - printf("\nsyntax: %s \n\n",argv[0]); - return 1; - } - sscanf(argv[1],"%08x",&uid); - sscanf(argv[2],"%08x",&nt); - sscanf(argv[3],"%016" SCNx64,&par_info); - sscanf(argv[4],"%016" SCNx64,&ks_info); - - // Reset the last three significant bits of the reader nonce - nr &= 0xffffff1f; - - printf("\nuid(%08x) nt(%08x) par(%016" PRIx64 ") ks(%016" PRIx64 ")\n\n",uid,nt,par_info,ks_info); - - for (pos=0; pos<8; pos++) - { - ks3x[7-pos] = (ks_info >> (pos*8)) & 0x0f; - bt = (par_info >> (pos*8)) & 0xff; - for (i=0; i<8; i++) - { - par[7-pos][i] = (bt >> i) & 0x01; - } - } - - printf("|diff|{nr} |ks3|ks3^5|parity |\n"); - printf("+----+--------+---+-----+---------------+\n"); - for (i=0; i<8; i++) - { - nr_diff = nr | i << 5; - printf("| %02x |%08x|",i << 5, nr_diff); - printf(" %01x | %01x |",ks3x[i], ks3x[i]^5); - for (pos=0; pos<7; pos++) printf("%01x,",par[i][pos]); - printf("%01x|\n",par[i][7]); - } - - state = lfsr_common_prefix(nr,rr,ks3x,par); - lfsr_rollback_word(state,uid^nt,0); - crypto1_get_lfsr(state,&key_recovered); - printf("\nkey recovered: %012" PRIx64 "\n\n",key_recovered); - crypto1_destroy(state); - - return 0; -}