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?
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 
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.
@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
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.
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.
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 9fyou 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