Vida CEM swapping

[Power6]

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.

I think that may be it. If the range of PINs is known to be limited to BCD on the P3, then you only have so many possible PINs, there will be theoretical SEED/KEY pairs for which there is no possible BCD match. I'm not quite sure why you need to iterate through more than the set of possible PINs, but I didn't go far down the road of coding the minimum set of BCD possibilities, as the SPA appears to use the full range of HEX values for PINs on ECUs, so I abandoned the BCD iterations. A lookup table could be generated but that may not be efficient.

[vtl]

Iterating over 3 PIN bytes in HEX: SEED produces unique KEY for PIN. A chance of hitting a match is 1:16.7M

Iterating over 4 PIN bytes in BCD: SEED produces non-unique KEY for PIN. There's a chance of producing duplicate KEY, the probability varies from 1:1 to 1:23. See the table above, this is programmatically generated. On weighted average, the chance is about 1:8.

While going over all 100^4 possible PIN BCD values, there's a 1:8 chance of hitting the right KEY. This gives a PIN match probability of 1 to 100^4 * 1:8 = 1:12.5M. This probability is actually not constant, as the weighted average of 1:8 is really a 1:1 to 1:23 spread.

[Power6]

While going over all 100^4 possible PIN BCD values, there's a 1:8 chance of hitting the right KEY. This gives a PIN match probability of 1 to 100^4 * 1:8 = 1:12.5M. This probability is actually not constant, as the weighted average of 1:8 is really a 1:1 to 1:23 spread.

What makes a PIN more probable than another... For 1:12.5M you'd have to crack maybe thousands of CEMs to say that. For a single CEM, I can code a crack that has 100% probability of the first PIN match. You've probably cracked more than a few though i imagine.

Not being argumentative, if there is some logic to guessing a more likely PIN that could be applied, I wanted to attempt to understand that!

[vtl]

For 1:12.5M you'd have to crack maybe thousands of CEMs to say that.

That's the beauty of math: it explains things you yet have to see If ever.

[Power6]

That's something like what I said to Rick when he didn't buy the "3-bytes of PIN" theory. But we are in agreement after testing it out.

I don't see anything that proves anything, not that you are required to share it! I guess if you start with 100 million PINs, it's true some are more likely than others because you are starting with a ton of duplicates. Rule out a PIN, no reason to consider the duplicates. However you rule those duplicates out works I suppose.

Don't have that problem in HEX, start with 17 million, all unique possibilities. Still a lot though for cracking in the car for SPA with security features though. But way less than 5 bytes of entropy. Will keep working on that.

[gnalan]

That's the beauty of math: it explains things you yet have to see If ever.

Code: Select all

seed = 0xBDFA1A;
pin = 0xFFFFC8E6CD;
real_key = 0x4C0E2B;
v0 = (real_key & 0xFFFFFF);
v1 = (((pin & 0xFF) << 56) | ((pin & 0xFF00) << 40) | ((pin & 0xFF0000) << 24) | ((pin & 0xFF000000) << 8) | ((pin & 0xFF00000000) >> 8) | ((seed & 0xFF) << 16) | (seed & 0xFF00) | ((seed & 0xFF0000) >> 16));
v2 = 0xC541A9;
for x in range(0,64):
    v3 = ((v2 & 1) ^ ((v1 >> x) & 1));
    v4 = (v2 >> 1);
    if v3==1:
        v2 = (v4 ^ 0x909028);
    else:
        v2 = v4;
key = (((v2 & 0xF0000) >> 16) | ((v2 & 0xF) << 4) | ((v2 & 0xF00000) >> 12) | (v2 & 0xF000) | ((v2 & 0xF0) << 12) | ((v2 & 0xF00) << 12));
print("Computed key: 0x%X" % key);
print("Real key: 0x%X" % v0);

I still need to eliminate the bit shifts, and rewrite it in C++, but I came up with a value of 0x909028 that works. A different value from your 'm' value, but it appears that they both work (although I haven't tested your code).

Next is a rewrite of my Algo in C++, cleaned up, without all the bit shifting that is still shown here.

[alevol]

without all the bit shifting that is still shown here.

Why is bit shifting bad?

[gnalan]

Why is bit shifting bad?

It's not bad, it just makes the code look messy.

[gnalan]

That's the beauty of math: it explains things you yet have to see If ever.

I optimized the for loop by looking at the Algo that's everywhere, breaking it down to its separate parts and pieces, and rewriting it. I believe we're on the same page, but doing one step differently which is why your value 'm' takes up an extra nibble.

Also '++i' doesn't need to make a copy of 'i' first like 'i++' does.

Code: Select all

Yours...
unsigned int n = 0xc541a9, m = 0x1212050;
for (i = 0; i < 64; i++, n >>= 1, k >>= 1)
{
    if ((n ^ k) & 0x1)
        n ^= m;
}

Mine...
unsigned int n = 0xc541a9, m = 0x909028;
for(i = 0; i < 64; ++i)
{
    if ((n & 1) ^ ((k >> i) & 1))
    {
        n = ((n >> 1) ^ m);
    }
    else
    {
        n >>= 1;
    }
}

Did I mention I love math?

[alevol]

How do you get ~860 pin/sec? I am getting stable 440 pins/sec using VTL's the most recent build.

I could also not compile VTL's seed-gen.c utility. I was trying to compile with devc++ and with VScode as well. It could not find dependencies.

Thanks

edit: found hash collision in about 2h. Nice. And it was slow cem@440pins/sec