Constants in common_prefix (crapto v2.3)

marcus2608 · 2009-07-25 13:22:00

Hi all,

In the latest version of crapto1 (2.3), there is a new function common_prefix() that implements part of the attack in the "Dark Side" paper. However, the author left out the constants (refer to the comments above the code) and said they are "in the paper". I have searched through the paper a few times but have not found them. Can someone please give me some hints as to where they are? Thank you!

adam@algroup.co.uk · 2009-07-25 16:42:32

The latest version appears to be 2.4, but it's gone missing:

http://code.google.com/u/blapost/updates

Did anyone get a copy?

marcus2608 · 2009-08-01 10:18:13

Thank you, hat, for the help!

I have managed to get complete the constants on pg 6, but I have a different 48 bits for the 00000002 entry. Did any one also have the same result as me?

I have another question. In the paper it states that 21 state bits determine the 2 keystream bits ks3(0) and ks3(2). However from my understanding only 20 bits (odd numbers 9th, 11th, 13th, .., 47th) are used as inputs to the filter functions. So how did the author arrive at 21 bits?

Thanks~

[Is it that for ks3(0) it uses bits 9th,..,47th and for ks3(2) it uses bits 11th,..,49th so there should be 21 bits used?]

Last edited by marcus2608 (2009-08-13 00:40:31)

marcus2608 · 2009-08-12 23:55:40

Sure thanks! But do let me know how you managed to get the key.

So looking at the ks decrypted from my data points, we will get the even keystream bits as shown in post 18. I don't understand how the pairs of even bits can reduce the search space to 2^5=32. My pseudocode for calculating step 6 of the attack (as described in the paper) is like this:

for state_bits from 0x0 to 0xffff
{
   if state_bits generate ks3(0) 
   {
       new_state_bits = state_bits<<1;
       if new_state_bits generate ks3(2) //possible state

       new_state_bits = state_bits<<1 | 0x1;
       if new_state_bits generate ks3(2) //possible state

   }
}

This code allows me to reduce the space by 4 only with 1 pair of ks. But I don't know how to incorporate the remaining 7 pairs to further reduce the space to 32.

Last edited by marcus2608 (2009-08-13 01:22:30)

marcus2608 · 2009-08-13 09:59:51

Unfortunately I do not have the key to this tag. But here is another set of data:

{Nr}{Ar}                              {Pc}                     {Nack}        ks (calculated using {Nack}^0x5)
a4  5b  7a  80  b6  35  ac  d4      1  1  1  0  1  0  0  0          5           0 (0000)
a4  5b  7a  81  b6  35  ac  d4      1  1  1  0  0  0  0  0          3           6 (0110)
a4  5b  7a  82  b6  35  ac  d4      1  1  1  1  1  1  1  0          E           B (1011)
a4  5b  7a  83  b6  35  ac  d4      1  1  1  1  0  0  1  0          C           9 (1001)
a4  5b  7a  84  b6  35  ac  d4      1  1  1  1  1  0  0  1          9           C (1100)
a4  5b  7a  85  b6  35  ac  d4      1  1  1  1  1  1  0  0          3           6 (0110)
a4  5b  7a  86  b6  35  ac  d4      1  1  1  1  0  1  1  1          E           B (1011)
a4  5b  7a  87  b6  35  ac  d4      1  1  1  0  1  0  1  1          F           A (1010)

As for the code snippet, I understand your point, but I am saving the new_state_bits, not the old one, so the range is from 0x0 to 0xfffff (if 0xfffff produces ks3(0), then I will test 0x1ffffe and 0x1fffff to see if they produce ks3(2)).

marcus2608 · 2009-08-13 10:30:47

Hmm well I see your point about the byte ordering. So far I have been coding using libnfc, and the byte ordering I have been using in my code follows the convention in the papers by roel et al. ie,

0x26,
0x93, 0x20,
0x93, 0x70, ....
0x60, 0x04, ....
0xa4, 0x5b, 0x7a, 0x80, 0xb6, 0x35, 0xac, 0xd4
0x50, 0x00, 0x57, 0xcd

The bit ordering requires that the 3 msb be varied to obtain the data.

Last edited by marcus2608 (2009-08-23 09:51:33)

marcus2608 · 2009-08-14 09:48:06

Yeah that's fine, I will continue to debug my code.

Looking back at post 17, you mentioned that:

filter(possible_state) = ks3(0)
filter(possible_state << 1 | extra possible state bit) = ks3(2)
possible_state' = possible_state ^ some_constant_which_depends_only_on_[Nr]^[Nr']

Is the possible_state 20 bits wide (9th - 47th)?

Also suppose if [Nr] and [Nr'] differ in 0001, then should I do

possible_state' = possible_state ^ 0x947A4 (odd bits from 0x8DC1B21F6E10, starting from 9th bit)

If so, then the constants that we really need are:

ODD:
0001 ==> 0x947A4
0002 ==> 0x1A6E0
0004 ==> 0x28F48

EVEN:
0001 ==> 0x8D370
0002 ==> 0x947A4
0004 ==> 0x1A6E0

My libnfc code should get the data set ideally in less than 30 min, sometimes less depending on my cranky laptop. I know it is not fast, as compared to the paper's author reported 5 min, but I am sure my code can be further optimized.

Last edited by marcus2608 (2009-08-14 10:09:16)

marcus2608 · 2009-08-16 23:26:51

I found out the bit ordering is something like this (from left to right):

7 6 5 4 3 2 1 0      15 14 13 12 11 10 9 8     23 22 21 20 19 18 17 16    ....

The test code I have written is based on crapto1. First I obtained all the different lfsr states for generating all 8 of the ks3(0), ks3(1), ks3(2) and ks3(3). Then by choosing one {Nr} and one {Nr'}, I XORed the their LFSRs to get the difference in states. Using the bit ordering above, I reordered the state difference and (painfully) split according to odd and even bits and got the following constants.

Constants that determine ks3(0):

Difference      Even bits(0,2,4,6,..)           Odd bits(1,3,5,7,..)
100                0x003b2c                          0x012f14
010                0x012f14                          0x007658
001                0x007658                          0x025e29

Constants that determine ks3(2):

Difference      Even bits(0,2,4,6,..)           Odd bits(1,3,5,7,..)
100                0x007658                          0x025e29
010                0x025e29                          0x00ecb1
001                0x00ecb1                          0x04bc53

As in post 17, after applying the filter function, I used the odd bits constants from above to apply on the possible state to get the next possible depending on the bit difference between data points. But I still cannot get the same lists as you have, hat.

Last edited by marcus2608 (2009-08-23 09:52:25)

phadom · 2009-08-16 23:57:25

Sorry i jump into the conversation but iam trying to follow you and i must admit i am a bit lost. By fixing the timing these specific values come up. Bits 29,30,31 of the 4th byte of C are only changed giving us the table below, where the parity is for example
3D--> 00111101
3A-->00111010 etc etc

UID: 1482F8D7B9
Card Nonce: 7E3C0DBD

Bits 29,30 and 31 | Parity | Encrypted Nack

000| 3D| 09
100| 3A| 0C
010| 2B| 0C
110| 2B| 09
001| 2B| 09
101| 2C| 0D
011| 3F| 00
111| 3A| 0F

I understand that by XORing [NACK] with NACK i get the first 4bits of ks3.
I also understand that i have to create a table of binary representations of numbers from 0 to 2 in the power of 21.
Will i have to input that table into the filter function and keep only the results that satisfy the condition that
filter_function(table)=ks3(0)
filter_function(table)=ks3(2)

where ks3(0)=1bit that i got from the NACK.

How do the rest of the NACKs come into play? Please correct me if iam wrong in any of my assumptions.

phadom · 2009-08-17 00:42:59

Im not currently in the labs so i dont have the C and the responses i was using,i will post them here the moment i can.
Thank you for your explanation it clarified the situation alot. Will post here with my progress or any questions that will arise.

phadom · 2009-08-17 16:57:22

@marcus Did you find any problems with the filter function included in the crapto v2.4 or you just decided to write it from scratch?

marcus2608 · 2009-08-18 12:01:59

Just to share with you guys.. I just found a problem with my code. The ks3 bits should be reversed, ie. {NACK}^0x5=ks3(3) ks3(2) ks3(1) ks3(0). I verified this separately with my test code when I printed out the ks3 bits one by one. Now I have 21 and 88 items in the 2 lists. I think they are the closest to the ones that hat has kindly provided (20, 87). Now to figure out why I have one extra in each list...

@phadom: I am using the filter function now... after tracing the code to know what it is doing exactly

Last edited by marcus2608 (2009-08-23 09:54:03)

marcus2608 · 2009-08-18 14:10:36

hat wrote:

btw a good indication that you're lists are correct is to notice that quite a few of the list items appear twice. once with the last bit 0, once 1. imho this is because of the same weakness of the filter function this attack exploits.

Yes I notice this phenomena in my lists, more obvious in the ks3(1)/ks3(3) list than in the ks3(0)/ks3(2) list. Guess I am on track again

But first I need to merge the two lists into 42-bit possible states, by taking a cross product of the two lists to get 21*88 elements? Do I check the parity after i have successfully extended it to 48-bit and rolled back to initial keys?

Last edited by marcus2608 (2009-08-18 14:14:19)

marcus2608 · 2009-08-19 10:56:21

Hi,

I have some questions to ask here.

Is each of the crossproduct 42-bit states just BEFORE ks3(3) is generated? Something like this:

state ==> get ks3(0) ==> state' ==> get ks3(1) ==> state'' ==> get ks3(2) ==> state''' (this one?) ==> get ks3(3)

Reason I am asking is that this may affect how much rollback to perform. If it is just before ks3(3) like above, then I rollback (3+32) bits to reach the state just after Nr is fed in. Hope you understand what I mean here.

Also can I use the rollback function in crapto1, like this?

for all crossproduct result extended to 48bits {
    struct Crypto1State * s = crypto1_create(crossproduct);
    lfsr_rollback(s, 0, 0); //have to figure out a way to rollback only 3 bits, as in the scenario above
    lfsr_rollback(s, 0, 0); //rollback 32 bits to just after Nr is fed in
    lfsr_rollback(s, nr, 1); //rollback to before Nr is fed in, as what you mentioned, but which Nr from the 8 to use? Any one?
    .... //continue parity check
}

Thank you for the patience..

phadom · 2009-08-19 13:47:53

One question to help me with some debugging. The paper mentions that by filtering down we manage to cut our search space by 4. Is its actually exactly by 4? i mean if our initial table is 2<<21 after the first filtering we must have a table of( 2<<21)/4 exactly?

phadom · 2009-08-19 14:46:55

The moment i have the hardware again on my hands i will post all the values.

For the sake of interest, i am also trying to understand the common_prefix code in crapto. As i understand it takes as input the nacks,the size and a variable called isodd. From what i can tell, isodd is being used as a boolean. However i dont get to where it is refering? I mean it can't be that simple just calling common_prefix(table_of_nacks,sizeoftable,0) and getting back the candidates.right?

I want to thank you for all the valuable help and the constant support.

Last edited by phadom (2009-08-19 14:47:56)

phadom · 2009-08-19 19:51:37

i would edit my post but its better to just a new one with the correct values cause copy pasting sometimes can lead you to disasters

So
Odd Even
000 0x000000000000
001 0x8DC1b21F6E10 ----------->ecb15 | bc538
002 0x1B83643EDC20------------>5e29c | ecb14
003 0xA945165E4A30------------->cc807 | 2edb0
004 0x3706C87DB840------------->7658a | 5e29c
005 0xC4C87A9D2650------------->a5e51 | 9c62a
006 0x528A2CBC9460------------->176d8 | cc807
007 0xE04BDEDC0270------------->85dc3 | 0ef23

is the table i have. Is there a way to verify on my own that im on the right track so i wont be spamming the forum(like i do now)?

Im not using the crapto code(that was a question out of curiousity...).
Being a newbie in bitwise operations this project is quite hard to tackle...

Last edited by phadom (2009-08-19 22:08:19)

marcus2608 · 2009-08-23 10:02:16

Well I must say my thanks to hat - you have been extremely helpful in your posts here. I now admit it is not really that tough to code out the Nicolas attack, after _really_ understanding the description in the paper. The key points to note are the bit ordering, and to be consistent in using the constants in the code. Like what hat said, there is no need to stick to those constants in the paper, as you can always get them by writing some test code to obtain the state differences.

phadom · 2009-08-23 14:15:31

Yes i guess getting the constants right is the most important part. Although i still try to understand where the bit order you are mentioning in the forum comes into play. Guess the really really good understanding of the paper is the most important thing.

Proxmark3 community

Announcement

#1 2009-07-25 13:22:00

Constants in common_prefix (crapto v2.3)

#2 2009-07-25 16:42:32

Re: Constants in common_prefix (crapto v2.3)

#3 2009-08-01 10:18:13

Re: Constants in common_prefix (crapto v2.3)

#4 2009-08-12 23:55:40

Re: Constants in common_prefix (crapto v2.3)

#5 2009-08-13 09:59:51

Re: Constants in common_prefix (crapto v2.3)

#6 2009-08-13 10:30:47

Re: Constants in common_prefix (crapto v2.3)

#7 2009-08-14 09:48:06

Re: Constants in common_prefix (crapto v2.3)

#8 2009-08-16 23:26:51

Re: Constants in common_prefix (crapto v2.3)

#9 2009-08-16 23:57:25

Re: Constants in common_prefix (crapto v2.3)

#10 2009-08-17 00:42:59

Re: Constants in common_prefix (crapto v2.3)

#11 2009-08-17 16:57:22

Re: Constants in common_prefix (crapto v2.3)

#12 2009-08-18 12:01:59

Re: Constants in common_prefix (crapto v2.3)

#13 2009-08-18 14:10:36

Re: Constants in common_prefix (crapto v2.3)

#14 2009-08-19 10:56:21

Re: Constants in common_prefix (crapto v2.3)

#15 2009-08-19 13:47:53

Re: Constants in common_prefix (crapto v2.3)

#16 2009-08-19 14:46:55

Re: Constants in common_prefix (crapto v2.3)

#17 2009-08-19 19:51:37

Re: Constants in common_prefix (crapto v2.3)

#18 2009-08-23 10:02:16

Re: Constants in common_prefix (crapto v2.3)

#19 2009-08-23 14:15:31

Re: Constants in common_prefix (crapto v2.3)

Board footer