CHG: Updated the crapto1 imp to latest vesion3.3 ( Thanks @blapost !)

[proxmark3-svn] / tools / nonce2key / crapto1.c

diff --git a/tools/nonce2key/crapto1.c b/tools/nonce2key/crapto1.c
index c0a158b56e7498fbe29c09280cb1898be38475e9..e35daac88eaa5e523a08a7b86f7a551b1aaf6a27 100644 (file)
--- a/tools/nonce2key/crapto1.c
+++ b/tools/nonce2key/crapto1.c
@@ -33,7 +33,7 @@ static void __attribute__((constructor)) fill_lut()
 \r
 static void quicksort(uint32_t* const start, uint32_t* const stop)\r
 {\r
 \r
 static void quicksort(uint32_t* const start, uint32_t* const stop)\r
 {\r

-       uint32_t *it = start + 1, *rit = stop;\r
+       uint32_t *it = start + 1, *rit = stop, t;\r

 \r
        if(it > rit)\r
                return;\r
 \r
        if(it > rit)\r
                return;\r


@@ -44,12 +44,12 @@ static void quicksort(uint32_t* const start, uint32_t* const stop)
                else if(*rit > *start)\r
                        --rit;\r
                else\r
                else if(*rit > *start)\r
                        --rit;\r
                else\r

-                       *it ^= (*it ^= *rit, *rit ^= *it);\r
+                       t = *it,  *it = *rit, *rit = t;\r

 \r
        if(*rit >= *start)\r
                --rit;\r
        if(rit != start)\r
 \r
        if(*rit >= *start)\r
                --rit;\r
        if(rit != start)\r

-               *rit ^= (*rit ^= *start, *start ^= *rit);\r
+               t = *rit,  *rit = *start, *start = t;\r

 \r
        quicksort(start, rit - 1);\r
        quicksort(rit + 1, stop);\r
 \r
        quicksort(start, rit - 1);\r
        quicksort(rit + 1, stop);\r


@@ -57,8 +57,7 @@ static void quicksort(uint32_t* const start, uint32_t* const stop)
 /** binsearch\r
  * Binary search for the first occurence of *stop's MSB in sorted [start,stop]\r
  */\r
 /** binsearch\r
  * Binary search for the first occurence of *stop's MSB in sorted [start,stop]\r
  */\r

-static inline uint32_t*\r
-binsearch(uint32_t *start, uint32_t *stop)\r
+static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop)\r

 {\r
        uint32_t mid, val = *stop & 0xff000000;\r
        while(start != stop)\r
 {\r
        uint32_t mid, val = *stop & 0xff000000;\r
        while(start != stop)\r


@@ -143,13 +142,16 @@ recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
        }\r
 \r
        for(i = 0; i < 4 && rem--; i++) {\r
        }\r
 \r
        for(i = 0; i < 4 && rem--; i++) {\r

-               extend_table(o_head, &o_tail, (oks >>= 1) & 1,\r
-                       LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);\r
+               oks >>= 1;\r
+               eks >>= 1;\r
+               in >>= 2;\r
+               extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1,\r
+                            LF_POLY_ODD << 1, 0);\r

                if(o_head > o_tail)\r
                        return sl;\r
 \r
                if(o_head > o_tail)\r
                        return sl;\r
 \r

-               extend_table(e_head, &e_tail, (eks >>= 1) & 1,\r
-                       LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 3);\r
+               extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,\r
+                            LF_POLY_EVEN << 1 | 1, in & 3);\r

                if(e_head > e_tail)\r
                        return sl;\r
        }\r
                if(e_head > e_tail)\r
                        return sl;\r
        }\r


@@ -191,8 +193,11 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
        odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
        even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
        statelist =  malloc(sizeof(struct Crypto1State) << 18);\r
        odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
        even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
        statelist =  malloc(sizeof(struct Crypto1State) << 18);\r

-       if(!odd_tail-- || !even_tail-- || !statelist)\r
+       if(!odd_tail-- || !even_tail-- || !statelist) {\r
+               free(statelist);\r
+               statelist = 0;\r

                goto out;\r
                goto out;\r

+       }\r

 \r
        statelist->odd = statelist->even = 0;\r
 \r
 \r
        statelist->odd = statelist->even = 0;\r
 \r


@@ -255,12 +260,12 @@ struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
        sl->odd = sl->even = 0;\r
 \r
        for(i = 30; i >= 0; i -= 2) {\r
        sl->odd = sl->even = 0;\r
 \r
        for(i = 30; i >= 0; i -= 2) {\r

-               oks[i >> 1] = BIT(ks2, i ^ 24);\r
-               oks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
+               oks[i >> 1] = BEBIT(ks2, i);\r
+               oks[16 + (i >> 1)] = BEBIT(ks3, i);\r

        }\r
        for(i = 31; i >= 0; i -= 2) {\r
        }\r
        for(i = 31; i >= 0; i -= 2) {\r

-               eks[i >> 1] = BIT(ks2, i ^ 24);\r
-               eks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
+               eks[i >> 1] = BEBIT(ks2, i);\r
+               eks[16 + (i >> 1)] = BEBIT(ks3, i);\r

        }\r
 \r
        for(i = 0xfffff; i >= 0; --i) {\r
        }\r
 \r
        for(i = 0xfffff; i >= 0; --i) {\r


@@ -311,38 +316,44 @@ struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
 /** lfsr_rollback_bit\r
  * Rollback the shift register in order to get previous states\r
  */\r
 /** lfsr_rollback_bit\r
  * Rollback the shift register in order to get previous states\r
  */\r

-void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
+uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r

 {\r
        int out;\r
 {\r
        int out;\r

+       uint8_t ret;\r
+       uint32_t t;\r

 \r
        s->odd &= 0xffffff;\r
 \r
        s->odd &= 0xffffff;\r

-       s->odd ^= (s->odd ^= s->even, s->even ^= s->odd);\r
+       t = s->odd, s->odd = s->even, s->even = t;\r

 \r
        out = s->even & 1;\r
        out ^= LF_POLY_EVEN & (s->even >>= 1);\r
        out ^= LF_POLY_ODD & s->odd;\r
        out ^= !!in;\r
 \r
        out = s->even & 1;\r
        out ^= LF_POLY_EVEN & (s->even >>= 1);\r
        out ^= LF_POLY_ODD & s->odd;\r
        out ^= !!in;\r

-       out ^= filter(s->odd) & !!fb;\r
+       out ^= (ret = filter(s->odd)) & !!fb;\r

 \r
        s->even |= parity(out) << 23;\r
 \r
        s->even |= parity(out) << 23;\r

+       return ret;\r

 }\r
 /** lfsr_rollback_byte\r
  * Rollback the shift register in order to get previous states\r
  */\r
 }\r
 /** lfsr_rollback_byte\r
  * Rollback the shift register in order to get previous states\r
  */\r

-void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
+uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r

 {\r
 {\r

-       int i;\r
+       int i, ret = 0;\r

        for (i = 7; i >= 0; --i)\r
        for (i = 7; i >= 0; --i)\r

-               lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
+               ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\r
+       return ret;\r

 }\r
 /** lfsr_rollback_word\r
  * Rollback the shift register in order to get previous states\r
  */\r
 }\r
 /** lfsr_rollback_word\r
  * Rollback the shift register in order to get previous states\r
  */\r

-void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
+uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r

 {\r
        int i;\r
 {\r
        int i;\r

+       uint32_t ret = 0;\r

        for (i = 31; i >= 0; --i)\r
        for (i = 31; i >= 0; --i)\r

-               lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
+               ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);\r
+       return ret;\r

 }\r
 \r
 /** nonce_distance\r
 }\r
 \r
 /** nonce_distance\r


@@ -376,80 +387,63 @@ static uint32_t fastfwd[2][8] = {
  * Described in the "dark side" paper. It returns an -1 terminated array\r
  * of possible partial(21 bit) secret state.\r
  * The required keystream(ks) needs to contain the keystream that was used to\r
  * Described in the "dark side" paper. It returns an -1 terminated array\r
  * of possible partial(21 bit) secret state.\r
  * The required keystream(ks) needs to contain the keystream that was used to\r

- * encrypt the NACK which is observed when varying only the 4 last bits of Nr\r
+ * encrypt the NACK which is observed when varying only the 3 last bits of Nr\r

  * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
  */\r
 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
 {\r
  * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
  */\r
 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
 {\r

-       uint32_t *candidates = malloc(4 << 21);\r
-       uint32_t c,  entry;\r
-       int size, i;\r
+       uint32_t c, entry, *candidates = malloc(4 << 10);\r
+       int i, size = 0, good;\r

 \r
        if(!candidates)\r
                return 0;\r
 \r
 \r
        if(!candidates)\r
                return 0;\r
 \r

-       size = (1 << 21) - 1;\r
-       for(i = 0; i <= size; ++i)\r
-               candidates[i] = i;\r
-\r
-       for(c = 0;  c < 8; ++c)\r
-               for(i = 0;i <= size; ++i) {\r
-                       entry = candidates[i] ^ fastfwd[isodd][c];\r
-\r
-                       if(filter(entry >> 1) == BIT(ks[c], isodd))\r
-                               if(filter(entry) == BIT(ks[c], isodd + 2))\r
-                                       continue;\r
-\r
-                       candidates[i--] = candidates[size--];\r
+       for(i = 0; i < 1 << 21; ++i) {\r
+               for(c = 0, good = 1; good && c < 8; ++c) {\r
+                       entry = i ^ fastfwd[isodd][c];\r
+                       good &= (BIT(ks[c], isodd) == filter(entry >> 1));\r
+                       good &= (BIT(ks[c], isodd + 2) == filter(entry));\r

                }\r
                }\r

+               if(good)\r
+                       candidates[size++] = i;\r
+       }\r

 \r
 \r

-       candidates[size + 1] = -1;\r
+       candidates[size] = -1;\r

 \r
        return candidates;\r
 }\r
 \r
 \r
        return candidates;\r
 }\r
 \r

-/** brute_top\r
+/** check_pfx_parity\r

  * helper function which eliminates possible secret states using parity bits\r
  */\r
 static struct Crypto1State*\r
  * helper function which eliminates possible secret states using parity bits\r
  */\r
 static struct Crypto1State*\r

-brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],\r
+check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],\r

           uint32_t odd, uint32_t even, struct Crypto1State* sl)\r
 {\r
           uint32_t odd, uint32_t even, struct Crypto1State* sl)\r
 {\r

-       struct Crypto1State s;\r
-       uint32_t ks1, nr, ks2, rr, ks3, good, c;\r
-\r
-       for(c = 0; c < 8; ++c) {\r
-               s.odd = odd ^ fastfwd[1][c];\r
-               s.even = even ^ fastfwd[0][c];\r
-               \r
-               lfsr_rollback_bit(&s, 0, 0);\r
-               lfsr_rollback_bit(&s, 0, 0);\r
-               lfsr_rollback_bit(&s, 0, 0);\r
-               \r
-               lfsr_rollback_word(&s, 0, 0);\r
-               lfsr_rollback_word(&s, prefix | c << 5, 1);\r
-               \r
-               sl->odd = s.odd;\r
-               sl->even = s.even;\r
-       \r
-               ks1 = crypto1_word(&s, prefix | c << 5, 1);\r
-               ks2 = crypto1_word(&s,0,0);\r
-               ks3 = crypto1_word(&s, 0,0);\r
+       uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;\r
+\r
+       for(c = 0; good && c < 8; ++c) {\r
+               sl->odd = odd ^ fastfwd[1][c];\r
+               sl->even = even ^ fastfwd[0][c];\r
+\r
+               lfsr_rollback_bit(sl, 0, 0);\r
+               lfsr_rollback_bit(sl, 0, 0);\r
+\r
+               ks3 = lfsr_rollback_bit(sl, 0, 0);\r
+               ks2 = lfsr_rollback_word(sl, 0, 0);\r
+               ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);\r
+\r

                nr = ks1 ^ (prefix | c << 5);\r
                rr = ks2 ^ rresp;\r
 \r
                nr = ks1 ^ (prefix | c << 5);\r
                rr = ks2 ^ rresp;\r
 \r

-               good = 1;\r

                good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
                good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
                good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);\r
                good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);\r
                good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
                good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
                good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);\r
                good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);\r

-               good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);\r
-\r
-               if(!good)\r
-                       return sl;\r
+               good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r

        }\r
 \r
        }\r
 \r

-       return ++sl;\r
+       return sl + good;\r

 } \r
 \r
 \r
 } \r
 \r
 \r


@@ -471,24 +465,24 @@ lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])
        odd = lfsr_prefix_ks(ks, 1);\r
        even = lfsr_prefix_ks(ks, 0);\r
 \r
        odd = lfsr_prefix_ks(ks, 1);\r
        even = lfsr_prefix_ks(ks, 0);\r
 \r

-       statelist = malloc((sizeof *statelist) << 20);\r
-       if(!statelist || !odd || !even)\r
-                return 0;\r
-\r
+       s = statelist = malloc((sizeof *statelist) << 20);\r
+       if(!s || !odd || !even) {\r
+               free(statelist);\r
+               statelist = 0;\r
+                goto out;\r
+       }\r

 \r
 \r

-       s = statelist;\r
-       for(o = odd; *o != 0xffffffff; ++o)\r
-               for(e = even; *e != 0xffffffff; ++e)\r
+       for(o = odd; *o + 1; ++o)\r
+               for(e = even; *e + 1; ++e)\r

                        for(top = 0; top < 64; ++top) {\r
                        for(top = 0; top < 64; ++top) {\r

-                               *o = (*o & 0x1fffff) | (top << 21);\r
-                               *e = (*e & 0x1fffff) | (top >> 3) << 21;\r
-                               s = brute_top(pfx, rr, par, *o, *e, s);\r
+                               *o += 1 << 21;\r
+                               *e += (!(top & 7) + 1) << 21;\r
+                               s = check_pfx_parity(pfx, rr, par, *o, *e, s);\r

                        }\r
 \r
        s->odd = s->even = 0;\r
                        }\r
 \r
        s->odd = s->even = 0;\r

-\r
+out:\r

        free(odd);\r
        free(even);\r
        free(odd);\r
        free(even);\r

-\r

        return statelist;\r
 }\r
        return statelist;\r
 }\r