Proxmark3 community

Research, development and trades concerning the powerful Proxmark3 device.

Remember; sharing is caring. Bring something back to the community.


"Learn the tools of the trade the hard way." +Fravia

You are not logged in.

Announcement

Time changes and with it the technology
Proxmark3 @ discord

Users of this forum, please be aware that information stored on this site is not private.

#1 2009-03-07 03:29:40

rfider
Member
Registered: 2009-01-04
Posts: 15

CRAPTO-1: how to recover key using only ks2

The crapto-1 need 32 bits ks2, and 32 bits to recover secret key.

In Garcia's paper, it is mentioned to recover secret key along with the knowledge of just 32bits key stream(ks2)
by another authentication session.

I'm wondering how and why it would be possible?

Last edited by rfider (2009-03-26 13:59:32)

Offline

#2 2009-03-07 18:42:18

joker
Contributor
Registered: 2008-11-17
Posts: 34

Re: CRAPTO-1: how to recover key using only ks2

the reason that it is possible, is because the secret state only has an entropy of  48 bits. And the vast majority of secret states are mapped to a unique 48bits of resulting keystream. If for the sake of simplicity you assume that each 48bit secret state maps to a unique 48bit of keystream(and hence ignore some duplicates).  since all 48bit numbers would be possible keystream in that situation. There will be (1<<16) possible keystreams who's first 32bit equal your ks2.
In different sessions ks2 will be different since it was influenced with the nonce's. Hence other set of about 1<<16 possible secret states will be discovered. however if you rollback these states until before the nonces were fed in they should end up at the same secret key.


How to do this with crapto1 requires a little bit of coding. Replace the 27 in the recover count to 11. and in the
if(rem == -1) clause, instead of just returning the first found, store all possibilities(carthesian product of odd and even tables) in a list.

rollback the items in the list, using the tag and reader challenge associated with ks2.

Do this for each of the ks2's you have. and crosscheck the respective lists.

Last edited by joker (2009-03-07 19:02:29)

Offline

#3 2009-03-08 15:36:37

rule
Member
Registered: 2008-05-21
Posts: 417

Re: CRAPTO-1: how to recover key using only ks2

Thank you for the valuable contribution. Here are two 32 bits example traces using the same key.

MIFARE Classic two times 32 bits trace, []=Encrypted

      UID: c2  a8  2d  f4

       Nt: 07  a2  d6  6b  
 [Nr,Nt']: 73! 98! f5! 9d  e9  1c! de  4e!

       Nt: 42  97  c0  a4  
 [Nr,Nt']: 97! fc! 26  5f! 83! f9  63  35!

Last edited by rule (2009-03-08 19:23:53)

Offline

#4 2009-03-08 17:38:40

joker
Contributor
Registered: 2008-11-17
Posts: 34

Re: CRAPTO-1: how to recover key using only ks2

You might also want to provide the matching UID, in order to facilitate the rolling back of the tag nonce

Offline

#5 2009-03-08 19:25:35

rule
Member
Registered: 2008-05-21
Posts: 417

Re: CRAPTO-1: how to recover key using only ks2

You are right, I've added the UID to the traces.

Offline

#6 2009-03-08 19:53:50

joker
Contributor
Registered: 2008-11-17
Posts: 34

Re: CRAPTO-1: how to recover key using only ks2

SPOILER
yes thanks with that uid my sources tell me that the key is the very plausible B00BB00BB00B

Last edited by joker (2009-03-08 20:06:21)

Offline

#7 2009-03-08 20:54:21

rule
Member
Registered: 2008-05-21
Posts: 417

Re: CRAPTO-1: how to recover key using only ks2

Perfect!

Offline

#8 2009-03-09 01:46:21

rfider
Member
Registered: 2009-01-04
Posts: 15

Re: CRAPTO-1: how to recover key using only ks2

Joker, thanks for you vivid explanation!

But I still puzzled here.
I do not understand why 2 of these (1<<16) secret states will end up the same sectet key(one and only one?).

each ks2 has an entropy of 32bits, so 2 ks2 have an entropy of 64bits?

joker wrote:

the reason that it is possible, is because the secret state only has an entropy of  48 bits. And the vast majority of secret states are mapped to a unique 48bits of resulting keystream. If for the sake of simplicity you assume that each 48bit secret state maps to a unique 48bit of keystream(and hence ignore some duplicates).  since all 48bit numbers would be possible keystream in that situation. There will be (1<<16) possible keystreams who's first 32bit equal your ks2.
In different sessions ks2 will be different since it was influenced with the nonce's. Hence other set of about 1<<16 possible secret states will be discovered. however if you rollback these states until before the nonces were fed in they should end up at the same secret key.


How to do this with crapto1 requires a little bit of coding. Replace the 27 in the recover count to 11. and in the
if(rem == -1) clause, instead of just returning the first found, store all possibilities(carthesian product of odd and even tables) in a list.

rollback the items in the list, using the tag and reader challenge associated with ks2.

Do this for each of the ks2's you have. and crosscheck the respective lists.

Offline

#9 2009-03-09 03:27:04

joker
Contributor
Registered: 2008-11-17
Posts: 34

Re: CRAPTO-1: how to recover key using only ks2

@rfider: actually nobody ever said there will only be one.

There must be at least one, because well the traces were created this way, so there is a solution.(else the data was not valid).

[[It's similar to rsa keys, if you take the product of two large primes; n =  p * q, n is the public modulus. People know there must be at least 2 prime factors, but if the CA messed up their primetests p and q might not be prime and you might end up
having more prime factors. however the tests are designed however to make this very unlikely, not impossible though.]]


Here too, there is a chance that more states remain after using 2 separate ks2 traces. in fact the chances of that are again in the order of magnitude of 1 in 1<<16 (64 -48). However if you ignore this and just take the first found you'll only be wrong once every 1<<17 times or in human numbers once every 130.000 times; which you can safely ignore in POC code. The chance that 3 states remain is again ...

In the case of ks2 only you could just get another trace, and check the few states you have remaining against that list.

However it's a poorly kept secret that the ks2,ks3 methods have the exact same situation. it's not too hard to find a ks2,ks3 pair that can be generated by more than one secret state. For example 7131DC93, 5FC03AF0 or 5A537F7B, DBD7DF49

This isn't a huge problem as the chances of hitting these corner cases are slim and easily dealt with. If you have 2 possibilities you can just try them both. This is why 1bit ciphers aren't really fashionable.

@roel
it's a bit awkward at this time, I'll give rfider, and others a chance to try to implement it first. Perhaps we can trick more people into learning the lost art of C tongue

Offline

#10 2009-03-09 08:32:49

rule
Member
Registered: 2008-05-21
Posts: 417

Re: CRAPTO-1: how to recover key using only ks2

About the entropy, with 32 bits of the keystream (ks2) you can recover 32 bits of the LFSR. this means 16 bits are still unknown. Therefor you have still 2^16 = 65536 candidate keys left. If you have a second trace, you can try all these keys and will find (very most likely) only one that will recover nt' from the second example. The nt' you are trying to recover is again 32 bits, which gives a very low chance that two candidates from the 2^16 will fit. I added the parity bits to make the trace complete.

MIFARE Classic two times 32 bits trace, []=Encrypted

      UID: c2  a8  2d  f4

       Nt: 07  a2  d6  6b  
 [Nr,Nt']: cd! d4  73  0f  62  8e  cc! 23!

       Nt: 42  97  c0  a4  
 [Nr,Nt']: 96  50  69! 99! b1  27! a6  55!

Offline

#11 2009-03-11 03:06:22

rfider
Member
Registered: 2009-01-04
Posts: 15

Re: CRAPTO-1: how to recover key using only ks2

I was mistaken, but I just do not understand why the chance 2 separate ks2 traces end up in more than 1 state(or can I say 1 key?) is in the order of magnitude of 1 in 1<<16 (64 -48).

I made some modification in crapto-1:
I tried to store the list of states for ks2, and rollbacked them to their keys.
Then I did it for another ks2, and rolled them back.

So I get 2 lists of keys(actually the initial state of lfsr) there.

But I could not found a single match from the 2 lists.

I guessed it is probably some error with my code, I'd really like to check your POC out.

It's very kind of you.

joker wrote:

@rfider: actually nobody ever said there will only be one.

There must be at least one, because well the traces were created this way, so there is a solution.(else the data was not valid).

[[It's similar to rsa keys, if you take the product of two large primes; n =  p * q, n is the public modulus. People know there must be at least 2 prime factors, but if the CA messed up their primetests p and q might not be prime and you might end up
having more prime factors. however the tests are designed however to make this very unlikely, not impossible though.]]


Here too, there is a chance that more states remain after using 2 separate ks2 traces. in fact the chances of that are again in the order of magnitude of 1 in 1<<16 (64 -48). However if you ignore this and just take the first found you'll only be wrong once every 1<<17 times or in human numbers once every 130.000 times; which you can safely ignore in POC code. The chance that 3 states remain is again ...

In the case of ks2 only you could just get another trace, and check the few states you have remaining against that list.

However it's a poorly kept secret that the ks2,ks3 methods have the exact same situation. it's not too hard to find a ks2,ks3 pair that can be generated by more than one secret state. For example 7131DC93, 5FC03AF0 or 5A537F7B, DBD7DF49

This isn't a huge problem as the chances of hitting these corner cases are slim and easily dealt with. If you have 2 possibilities you can just try them both. This is why 1bit ciphers aren't really fashionable.

@roel
it's a bit awkward at this time, I'll give rfider, and others a chance to try to implement it first. Perhaps we can trick more people into learning the lost art of C tongue

Offline

#12 2009-03-11 10:52:07

joker
Contributor
Registered: 2008-11-17
Posts: 34

Re: CRAPTO-1: how to recover key using only ks2

how about you just publish what you have and we'll have a looksie at it. Don't give up too fast. This type of code is very volatile. From the moment you mess up one bit everything chages.

there are plenty of things you can do to test your code yourself:
- check how large the lists are.
- use a test where you know what key you want to recover after rolling back. and check in which lists it is. If it isn't check why...

Offline

#13 2009-03-12 02:14:38

rfider
Member
Registered: 2009-01-04
Posts: 15

Re: CRAPTO-1: how to recover key using only ks2

Those codes are based on older version of crapto-1, since it is much more easy to understand.

I just list out the important modification pieces:

void
lfsr_recovery_32(struct Crypto1State ** s, int *len, uint32_t ks2)
{  
  uint32_t odd_ks = 0, even_ks = 0;
  uint64_t *odd_table = 0, *even_table = 0;
  uint64_t *omatch_table = 0, *ematch_table = 0;
  uint32_t otab_len = 0, etab_len = 0;
  uint32_t p, odd_res, even_res;
  uint64_t lfsr = 0;
  int i, j, k;
  uint64_t *ot = 0, *et = 0;

  odd_table = malloc(8 << 21);
  even_table = malloc(8 << 21);
  if(!odd_table || !even_table)
    goto out;

  //split ks2,ks3 into a odd and even bits
  for(i = 0; i < 32; i += 2)
  {
     even_ks |= BIT(ks2, i ^ 24) << (i/2);
    odd_ks |= BIT(ks2, (i + 1) ^ 24) << (i/2);
  }

  //seed the tables using the first 2 bits of keystream
  for(i = 0; i < (1 << 20); i++)
  {
    if(filter(i) == BIT(even_ks, 0))
      even_table[etab_len++] = i;

    if(filter(i) == BIT(odd_ks, 0))
      odd_table[otab_len++] = i;
  }

  for(i = 1; i < 16; i++)
  {
    etab_len = extend_table(even_table, etab_len, BIT(even_ks, i));
    otab_len = extend_table(odd_table, otab_len, BIT(odd_ks, i));
  }

  ematch_table = malloc(etab_len << 3);
  omatch_table = malloc(otab_len << 3);
  if(!ematch_table || !omatch_table)
    goto out;

  //compute the lsfr contributions of the even bits
  for(i = 0; i < etab_len; i++)
  {
    ematch_table[i] = 0;
    for(j = 0; j < (16 - 5); j++)
    {
      ematch_table[i] <<= 1;
      p = even_table[i] >> j & (LF_POLY_EVEN * 2 + 1);
      ematch_table[i] |= parity(p);

      ematch_table[i] <<= 1;
      p = even_table[i] >> j & LF_POLY_ODD;
      ematch_table[i] |= parity(p);
    }
  }
  
  //compute the lsfr contributions of the odd bits
  for(i = 0; i < otab_len; i++)
  {
    omatch_table[i] = 0;
    for(j = 0; j < (16 - 5); j++)
    {
      omatch_table[i] <<= 1;
      p = odd_table[i] >> j & LF_POLY_ODD * 2;
      omatch_table[i] |= parity(p);

      omatch_table[i] <<= 1;
      p = odd_table[i] >> j & (LF_POLY_EVEN * 2 + 1);
      omatch_table[i] |= parity(p);
    }
  }


  //find a matches of even and odd contributions
  quicksort(ematch_table, even_table, 0, etab_len - 1);
  quicksort(omatch_table, odd_table, 0, otab_len - 1);

  ot = malloc(8 << 17);
  et = malloc(8 << 17);
  if(!ot || !et)
    goto out;

  i = j = *len = 0;
  while(i < etab_len && j < otab_len) {
    if (ematch_table[i] == omatch_table[j]) {
      et[*len] = even_table[i++];
      ot[(*len)++] = odd_table[j++];      
    }
    else if(ematch_table[i] < omatch_table[j])
      ++i;
    else if(ematch_table[i] > omatch_table[j])
      ++j;
  }
  
  *s = malloc(sizeof(struct Crypto1State) * (*len));
  for (i = 0; i < (*len); i++) {
        //perform lf shift and change bit format
     p = ot[i] & LF_POLY_ODD;
     p ^= et[i] & LF_POLY_EVEN;
     et[i] = et[i] << 1 | parity(p);

     (*s)[i].odd = et[i];
     (*s)[i].even = ot[i];
    }

out:
  free(omatch_table);
  free(ematch_table);
  free(odd_table);
  free(even_table);
  free(ot);
  free(et);


}

it is the main part of the program:

    struct Crypto1State **revstate;
    revstate = malloc(sizeof(struct Crypto1State *) * NUMTESTS);
    lfsr = malloc(sizeof(uint64_t *) * NUMTESTS);
    for (k = 0; k < NUMTESTS; k++) {
        ks2 = tc32[k].reader_response ^ prng_successor(tc32[k].tag_challenge, 64);
        lfsr_recovery_32(&(revstate[k]), &(len[k]), ks2);
        lfsr[k] = malloc(8 * len[k]);
        for (i = 0; i < len[k]; i++) {
          //rollback lfsr to get key
          lfsr_rollback(&(revstate[k][i]), 0, 0);
          lfsr_rollback(&(revstate[k][i]), tc32[k].reader_challenge_enc, 1);
          lfsr_rollback(&(revstate[k][i]), tc32[k].uid ^ tc32[k].tag_challenge, 0);
          crypto1_get_lfsr(&(revstate[k][i]), &(lfsr[k][i]));
        }
        quicksort(lfsr[k], 0, len[k] - 1);
    }

any idea?

Offline

#14 2009-03-12 22:04:13

joker
Contributor
Registered: 2008-11-17
Posts: 34

Re: CRAPTO-1: how to recover key using only ks2

Yeah there are several problems with that ...
keep in mind that old code typically has old bugs.

You might want to look up what i meant with the cartesian product of the tables ;-)

  while(i < etab_len && j < otab_len) {
    if (ematch_table[i] == omatch_table[j]) {
      et[*len] = even_table[i++];
      ot[(*len)++] = odd_table[j++];      
    }

even = [a, b, c]
odd = [d, e, f]
ematch was [1,2,2]
omatch was [ 1, 2, 3]

you would get: (d,a), (e,b)
while you want (d,a), (e,b), (e,c)

it get's much worse for more duplicates, .. the rest of the code looks ok at first glance

Offline

#15 2009-03-13 02:01:33

rfider
Member
Registered: 2009-01-04
Posts: 15

Re: CRAPTO-1: how to recover key using only ks2

I did not really understand the optimizations in the latest code,
Your instruction will probably help me a lot.

joker wrote:

Yeah there are several problems with that ...
keep in mind that old code typically has old bugs.

You got the problem right there,
I forgot the same match_table did not mean the same state table.

joker wrote:

You might want to look up what i meant with the cartesian product of the tables ;-)

  while(i < etab_len && j < otab_len) {
    if (ematch_table[i] == omatch_table[j]) {
      et[*len] = even_table[i++];
      ot[(*len)++] = odd_table[j++];      
    }

even = [a, b, c]
odd = [d, e, f]
ematch was [1,2,2]
omatch was [ 1, 2, 3]

you would get: (d,a), (e,b)
while you want (d,a), (e,b), (e,c)

it get's much worse for more duplicates, .. the rest of the code looks ok at first glance

I really appreciate your help, JOKER^^

Offline

#16 2009-04-05 22:36:55

touf
Contributor
Registered: 2008-12-11
Posts: 27

Re: CRAPTO-1: how to recover key using only ks2

RFIDER can you give us more information about your functions extend_table and quicksort ?
they must be different from the ones included in crapto ...

Offline

#17 2009-04-06 01:25:00

rfider
Member
Registered: 2009-01-04
Posts: 15

Re: CRAPTO-1: how to recover key using only ks2

I am using a very old version of CRAPTO-1

you can get it here
http://code.google.com/p/crapto1/source … c=svn5&r=5

Offline

#18 2009-04-06 07:37:37

touf
Contributor
Registered: 2008-12-11
Posts: 27

Re: CRAPTO-1: how to recover key using only ks2

i had been looking up to the v0.6,
thanks for your answer

Offline

#19 2009-04-09 20:25:56

touf
Contributor
Registered: 2008-12-11
Posts: 27

Re: CRAPTO-1: how to recover key using only ks2

a few more traces for thoses who'd like to test their coding :

26
 +     64:   0: TAG 04  00
 +   7016:    :     93  20
 +     64:   0: TAG 95  6e  a8  6d  3e
 +   7322:    :     93  70  95  6e  a8  6d  3e  be  32
 +     65:   0: TAG 88  be  59
 +   5784:    :     60  0b  26  c5
 +    113:   0: TAG d0  9e  48  ee
 +   3184:    :     f4  e8  4e  40  54  df  87  d0


  26
 +     64:   0: TAG 04  00
 +   6706:    :     93  20
 +     64:   0: TAG 95  6e  a8  6d  3e
 +   6161:    :     93  70  95  6e  a8  6d  3e  be  32
 +     64:   0: TAG 88  be  59
 +   5281:    :     60  0b  26  c5
 +    112:   0: TAG d6  62  2f  2d
 +   3016:    :     10  d3  37  83  b1  13  29  37


 26
 +     64:   0: TAG 04
 +   6786:    :     93  20
 +     64:   0: TAG 95  6e  a8  6d  3e
 +   7489:    :     93  70  95  6e  a8  6d  3e  be  32
 +     64:   0: TAG 00!
 +   5865:    :     60  0b  26  c5
 +    112:   0: TAG cc  86  90  33
 +   3280:    :     84  4d  b7  06  3c  a1  cf  9f

you should find that key : [00 00 00 00 00 01 ]

Offline

#20 2009-04-15 01:58:16

Dennyxiao
Contributor
Registered: 2008-11-01
Posts: 43

Re: CRAPTO-1: how to recover key using only ks2

A question ,
what the len for  for in the funciton recovery . What valud it should be?

lfsr_recovery_32(struct Crypto1State ** s, int *len, uint32_t ks2).

Offline

#21 2009-04-15 02:13:58

Dennyxiao
Contributor
Registered: 2008-11-01
Posts: 43

Re: CRAPTO-1: how to recover key using only ks2

Why the *len=0;
then   *s = malloc(sizeof(struct Crypto1State) * (*len));
?

Offline

#22 2009-04-15 07:16:38

touf
Contributor
Registered: 2008-12-11
Posts: 27

Re: CRAPTO-1: how to recover key using only ks2

for each right answer, you got :

et[*len] = even_table[i++];
ot[(*len)++] = odd_table[j++];

so when you do the malloc, len point out to the number of possible states.
so you do alloc the correct numer of spaces.


to answer your previous question, the len=0 when it's passed to the recovery function .
the point is to update it's value while running the recovery function in order to know the right number of possible state and use it later.

Offline

#23 2009-05-06 03:36:21

Dennyxiao
Contributor
Registered: 2008-11-01
Posts: 43

Re: CRAPTO-1: how to recover key using only ks2

In crapto1 2.2 what the parameter in should be?

struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
Thanks,

Offline

#24 2010-07-09 09:05:32

henry2010
Member
Registered: 2010-06-11
Posts: 9

Re: CRAPTO-1: how to recover key using only ks2

I get the trace of  the using keyb auth block 0
Could you somebody tell me the key for sector 0?
Many thanks.

 +   8935:    :     26    
 +     65:   0: TAG 01  40    
 +    512:   0: TAG 72  eb  18  03  7d!   
 + 136532:    :     93  70  72  eb  61  0e  f6  40  f9    
 +     64:   0: TAG 02! 56  3b    
 +    735:    :     61  00  2d  62    
 +     89:   0: TAG 04! 18  78  20    
 +    983:    :     70  bc  4e  c0  6b  09  6d  74      !crc
 +     65:   0: TAG e2  0d! 16! 7d!

  uint32_t uid               =      0x72eb1803;
  uint32_t tag_challenge      = 0x4187820;
  uint32_t nr_enc             = 0x70bc4ec0;
  uint32_t reader_resonse     = 0x6b096d74;
  uint32_t tag_resonse        = 0xe20d167d;

Last edited by henry2010 (2010-07-09 09:21:33)

Offline

#25 2010-07-12 02:41:57

hat
Contributor
Registered: 2009-04-12
Posts: 160

Re: CRAPTO-1: how to recover key using only ks2

+    512:   0: TAG 72  eb  18  03  7d!   
+ 136532:    :     93  70  72  eb  61  0e  f6  40  f9

--error error error ---
the tag is advertising an uid that's different from the one that the reader selects, the trace is probably corrupt.
it's not a valid mifare classic auth session anyway.

72  eb  18  03  7d!  <-- 7D check byte is not correct

72  eb  61  0e  f6 <-- f6 is correct
so at least the read thinks it's talking to  0x72eb610e


04! 18  78  20<-- this is supposed to be the tag challenge, which is sent unencrypted so the ! indicating a parity check failure, indeed indicates a failure.

the information sent by the tag is not trustworthy.

all is not lost, but based on this information alone, given you can't trust the tag, info it would only be possible if not too many of the bits are wrong and require some code, if you have more of the trace it will become trivial again. but based on this it would require some work.

Offline

#26 2013-07-26 03:24:57

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: CRAPTO-1: how to recover key using only ks2

Anyone in this topic is alive?

Offline

#27 2013-07-28 23:51:23

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: CRAPTO-1: how to recover key using only ks2

See: http://www.proxmark.org/forum/viewtopic.php?pid=7897#p7897

Offline

Board footer

Powered by FluxBB