Vida CEM swapping

[gnalan]

Great explanation, vtl, and thank you for the link. Now I follow what's going on. Very clean code. I'll take a look at that link and see if it's something I can use. Trying all of the bitshifts in C++ keeps giving me overflow errors.

I thought cleaning up the Algo the way I have and coming up with 0x109028 would help me clean it up even more. I didn't realize your 0x1212050 was my value bitshifted left one bit with 1 appended to the msb. I didn't take the time to actually look at the binary bits or I would've seen it. Great work!

I'm still looking over my code to shorten it even more, if I'm able to. Looks like you beat me to it though but I like the challenge and learning experience. Plus I really enjoy all forms of math. (In high school I was tutoring a college professor in math. Come to think of it, I was doing polynomial division, just because I thought it was fun, and he didn't have a clue what I was doing. Who knew I'd actually need it one day.)

[vtl]

P3 owners: Would you prefer a lower maximum crack time (10.5 hours ) or a chance of finding the PIN real fast?
With the chance finding the PIN real fast comes the risk that it will take real long time ( 63 hours ).

One does not follow from another.

From the hash properties, iterating over 3 bytes in HEX gives you 1:1 match, i.e. only one combination of PIN bytes produces a valid KEY for a given SEED.

Iterating over 4 bytes in BCD gives you match variability from 1:1 to 1:23. I calculated it as follow:

Code: Select all

repeats     hit ratio (one key matches N pins for a constant seed)
 852992       1:1
1710848       1:2
1905664       1:3
2139648       1:4
1632000       1:5
1842176       1:6
1288960       1:7
1286400       1:8
 775680       1:9
 869888      1:10
 650496      1:11
 622848      1:12
 303360      1:13
 250368      1:14
  90880      1:15
 112640      1:16
  40192      1:17
  38144      1:18
  15360      1:19
   4352      1:20
   9984      1:21
    768      1:22
   1024      1:23

As you see, probability of hitting a match while iterating over the whole range is greater than 1 in 16444672. I had too many beers tonight to apply remnants of my school math and say the exact probability. Maybe someone more sober can do that.

Also, cracking my P3 CEM with 3 HEX bytes:

Code: Select all

SEED 57 0c 3d, PIN 00 00 cc 8c b1, KEY 31 77 70, 865 pins/s
reply: 02 67 02 00 00 00 00 00 
hash collision found

4h30m in HEX vs like 2h20m in BCD for my CEM. Other PIN will give other BCD/HEX times.

[vtl]

Those interested: check out the P3 branch, it got a fix for "ugh", and cracking in HEX as well.

I don't have a slow P3 CEM, can't test how the new code works there.

1000 random seed/key crack simulation shows average cracking time of 2h 41m running at 866 pin/s.

[RickHaleParker]

As you see, probability of hitting a match while iterating over the whole range is greater than 1 in 16444672. I had too many beers tonight to apply remnants of my school math and say the exact probability. Maybe someone more sober can do that.

Also, cracking my P3 CEM with 3 HEX bytes:

Code: Select all

SEED 57 0c 3d, PIN 00 00 cc 8c b1, KEY 31 77 70, 865 pins/s
reply: 02 67 02 00 00 00 00 00 
hash collision found

4h30m in HEX vs like 2h20m in BCD for my CEM. Other PIN will give other BCD/HEX times.

At 865 pins/s

3 bytes hex Max time: 256^3 / 865 / 3600 = 5.39 hours
3 bytes hex AVG time: (256^3 / 865 / 3600 ) / 2 = 2.69 hours. ( assuming even distribution across units)

4 bytes BCD Max time: 100^4 / 865 / 3600 = 32.11 hours.
4 bytes BCD AVG time: ( 100^4 / ((23+1)/2) / 865 / 3600 ) 2 = 1.35 h. ( assuming even distribution across units: )

Summery
3 bytes hex: Adv 2.69 hours, Max 5.39 hours
4 bytes BCD Adv 1.35 hours, Max 32.11 hours.

Still looks like 3 bytes Hex is the better way to go. Hex over 3 bytes will get a PIN in less then 5.40 hours at 865 pins/s. BCD over 4 bytes can take up to 32.11 hours at 865 pins/s.

To calculate the slower P3 CEMS multiply the times above by ( 865 / X ) where X is your pins/s rate.

For example if your pin/s rate is 445:
865 / 445 = 1.944

3 bytes hex: Adv 1.944 * 2.69 hours, Max 1.944 * 5.39 hours = Adv 5.23 hours, Max 10.48 hours
4 bytes BCD Adv 1.944 * 1.35 hours, Max 1.944 * 32.11 hours = Adv 2.62 hours, Max 62.42 hours

[vtl]

4 bytes BCD AVG time: ( 100^4 / ((23+1)/2) / 865 / 3600 ) 2 = 1.35 h. ( assuming even distribution across units: )

It's not even. avg is somewhere around 1:5.

Also what is 2 after 3600?

[RickHaleParker]

4 bytes BCD AVG time: ( 100^4 / ((23+1)/2) / 865 / 3600 ) 2 = 1.35 h. ( assuming even distribution across units: )

It's not even. avg is somewhere around 1:5.

Also what is 2 after 3600?

How do you come up with an average of 1:5 ?

((23+1)/2) = ( 1 + 2 + 3 + 4 + 5 + 6 +7 +8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 ) / 23 = `12

Average of a sequence of consecutive number is the midpoint between start and finish.
Midpoint between 0 and 2.7 h = 2.7 h /2 = 1.35 h.

[vtl]

How do you come up with an average of 1:5 ?

Ratios are weighted: viewtopic.php?p=599297#p599297
I was wrong weighted average is 1:8, slightly less.

[RickHaleParker]

I was wrong weighted average is 1:8, slightly less.

It appears we have different objectives. You are trying to calculate for your unit. I am calculating for all P3 units collectively.

[vtl]

It appears we have different objectives. You are trying to calculate for your unit. I am calculating for all P3 units collectively.

No, it's a pin->key map for a constant seed. Seed is constant, pin goes from 0 to max (256^3 for HEX and 100^4 for BCD). There are 256^3 key varieties (apparently, key is 3 HEX bytes), so some pins produce the same key for the given seed.

While pin range of 100^4 is 6 times more than 256^3, the right key will be hit with 1 in 100^4/8=12500000 probability for BCD, while for HEX it is 1 in 256^3. BCD is 1:12.5M, HEX is 1:16.7M.

It still makes sense to iterate in HEX, since the max time is so much lower.

[Power6]

One does not follow from another.

From the hash properties, iterating over 3 bytes in HEX gives you 1:1 match, i.e. only one combination of PIN bytes produces a valid KEY for a given SEED.

Iterating over 4 bytes in BCD gives you match variability from 1:1 to 1:23. I calculated it as follow:

As you see, probability of hitting a match while iterating over the whole range is greater than 1 in 16444672. I had too many beers tonight to apply remnants of my school math and say the exact probability. Maybe someone more sober can do that.

My mind is fairly blown here. How can you increase the probability of a match?? I know the general answer in probability, which is you need to know some additional piece of information. Like flipping a coin is 50% heads or tails....unless you know that the coin has two heads.

So what I can't follow, is what additional knowledge is at play here? Typical brute force, the value of all "not-match" is the same. A KEY match failure would have no information about choosing the next PIN to try, I would think. You have a SEED, and a set of ~17 million PINs to try, why would any specific "next PIN" be more likely than any other...

Maybe you know why that is, or I suppose if the results are through observation, it could be inadvertent. Like if the way Volvo chose PINs on the P3 is not sufficiently random, there could be an unknown pattern. Then you may have, knowingly or otherwise, come upon the way to iterate through the more common PIN assignments earlier in the process. Though I can't see how you'd have a sample size large enough to observe and predict probability over ~17 million PINs for any CEM.