Log in

View Full Version : Breaking a challenge response


squidge
March 2nd, 2012, 19:02
I have two black boxes communicating with each other. One sends out a challenge and the other gives back the answer. If the wrong answer is given, the former refuses to communicate further.

The challenge is 8 bytes, the response is 2 bytes. Although box A refuses to communicate further if the answer to its challenge is incorrect, Box B will quite happily respond to any challenge thrown at it, but I only have it for a limited time.

So I've made a small app to talk to box B and fake some challenges.

I was thinking maybe someone has seen this and recognises it as a standard(ish) implementation.

00 00 00 00 00 00 00 00 -> B477
01 00 00 00 00 00 00 00 -> B677
02 00 00 00 00 00 00 00 -> B877
03 00 00 00 00 00 00 00 -> BA77
04 00 00 00 00 00 00 00 -> BC77
05 00 00 00 00 00 00 00 -> BE77
06 00 00 00 00 00 00 00 -> A077 - Ok, so when we rollover, we subtract 1 from upper nibble
07 00 00 00 00 00 00 00 -> A277
08 00 00 00 00 00 00 00 -> A477
09 00 00 00 00 00 00 00 -> A677
0A 00 00 00 00 00 00 00 -> A877
0B 00 00 00 00 00 00 00 -> AA77
0C 00 00 00 00 00 00 00 -> AC77
0D 00 00 00 00 00 00 00 -> AE77
0E 00 00 00 00 00 00 00 -> F077 - But that doesn't work here, maybe 9 is excluded and goes to F
0F 00 00 00 00 00 00 00 -> F277
10 00 00 00 00 00 00 00 -> F477
11 00 00 00 00 00 00 00 -> F677
12 00 00 00 00 00 00 00 -> F877
13 00 00 00 00 00 00 00 -> FA77
14 00 00 00 00 00 00 00 -> FC77
15 00 00 00 00 00 00 00 -> FE77
16 00 00 00 00 00 00 00 -> E077 - Ok
17 00 00 00 00 00 00 00 -> E277
18 00 00 00 00 00 00 00 -> E477
19 00 00 00 00 00 00 00 -> E677
1A 00 00 00 00 00 00 00 -> E877
1B 00 00 00 00 00 00 00 -> EA77
1C 00 00 00 00 00 00 00 -> EC77
1D 00 00 00 00 00 00 00 -> EE77
1E 00 00 00 00 00 00 00 -> F077 - Why goto F? I'd expect D
1F 00 00 00 00 00 00 00 -> F277
20 00 00 00 00 00 00 00 -> F477
21
22
23
24
25
26 00 00 00 00 00 00 00 -> E077
27
28
29
2A
2B
2C
2D 00 00 00 00 00 00 00 -> EE77
2E 00 00 00 00 00 00 00 -> 3077 - What the?
2F
30
31
32
33
34
35 00 00 00 00 00 00 00 -> 3E77
36 00 00 00 00 00 00 00 -> 2077
37
38
39
3A
3B
3C
3D 00 00 00 00 00 00 00 -> 2E77
3E 00 00 00 00 00 00 00 -> 3077
3F 00 00 00 00 00 00 00 -> 3277
40 00 00 00 00 00 00 00 -> 3477
41
42
43
44
45
46 00 00 00 00 00 00 00 -> 2077
47
48
49
4A
4B
4C
4D 00 00 00 00 00 00 00 -> 2E77
4E 00 00 00 00 00 00 00 -> 7077 - Why the sudden hike?
4F
50 00 00 00 00 00 00 00 -> 7477
51
52
53
54
55 00 00 00 00 00 00 00 -> 7E77
56 00 00 00 00 00 00 00 -> 6077
57
58
59
5A
5B
5C
5D 00 00 00 00 00 00 00 -> 6E77
5E 00 00 00 00 00 00 00 -> 7077
5F 00 00 00 00 00 00 00 -> 7277
60 00 00 00 00 00 00 00 -> 7477
61
62
63
64
65
66 00 00 00 00 00 00 00 -> 6077
67
68
69
6A
6B
6C
6D
6E 00 00 00 00 00 00 00 -> B077
6F 00 00 00 00 00 00 00 -> B277
--- Wrap ---
70 00 00 00 00 00 00 00 -> B477

So the high nibble changes are:
BAFEFE32327676B

Some others:

6E 01 00 00 00 00 00 00 -> B3 77
6E 02 00 00 00 00 00 00 -> 6E 77
6E 03 00 00 00 00 00 00 -> B1 77
6E 04 00 00 00 00 00 00 -> B4 77
6E 05 00 00 00 00 00 00 -> B7 77

6E 00 01 00 00 00 00 00 -> B0 77
6E 00 02 00 00 00 00 00 -> B0 77
6E 00 03 00 00 00 00 00 -> B0 77
6E 00 04 00 00 00 00 00 -> B0 77
6E 00 FF 00 00 00 00 00 -> B0 77 - I don't think the 3rd byte is actually used!

6E 00 00 FF 00 00 00 00 -> B4 77

00 00 00 00 FF 00 00 00 -> B7 74

00 00 00 00 00 FF 00 00 -> B4 77

00 00 00 00 00 00 FF 00 -> B7 74

00 00 00 00 00 00 00 FF -> B7 75

Any ideas?

dion
March 3rd, 2012, 04:35
never seen that.

why not trying above 70 for 1st byte?

BA FEFE 3232 7676 B

it might be repeated for above 70h.

squidge
March 3rd, 2012, 04:41
It does repeat - that's what I mean by 'wraps around'

Maximus
March 14th, 2012, 11:56
hiya,
I've played a bit with your data, and the hash seems pretty simple -and pretty bad.
if you take the upper nibble sequence, and you append an [a] you obtain a full repeating ring - if you move the 'origin' backward there, and you 'backtrace' the initial '4' to the missing [a] you can see that it is wholly determined (as long as we dont consider 2-8 bytes) by it.

* take B4, now make it our '00' point. you now see that the low nibble is (for now) FULLY determined by the mod8 of the byte; low nibble is given by (XL+2)*2 mod 8 (XL is low nibble)
* Take upper byte sequence and move it again to our virtual [a] - consider now only the upper nibble: you see it repeats every mod32, so high nibble is given by ((XH-3, on XH mod 16)/2 mod 4)*4 + (3 -the overflow of the low nibble mod).

Something like
Code:

XL = (Byte & 0x0F)
XH = (Byte & 0xF0)>>4

Low Nibble = (XL + 2)*2)
Low Nibble Overflow = Low Nibble % 0xF
Low Nibble = Low Nibble & 0xF

High Nibble = (XH+5)/2 mod 4 (+5 is like -3 if you go module 16)
High Nibble = High Nibble<<2 + (3-Low Nibble Overflow)

1st Byte = High Nibble<<4 + Low Nibble


For the other values you'd need a bit more values. From a simple look, the 2nd byte does a similar low nibble loop, with different adder - but again, you need more values (and some 'mix' to see how it interacts/which operand is used to combine with first byte's low nibble values - i.e. + or or etc.)

about the
6E 02 00 00 00 00 00 00 -> 6E 77
I'd go for a specialized challenge/answer request/order (maybe such value has a meaning or such), outside the hash algorithm.

...if you spend a bit of time there, I'm sure you can get it out pretty easily, it seems VERY weak to me.

squidge
March 15th, 2012, 11:17
Thanks for that, seems a little different to my version, which is basically:

Code:

byte += 2;
bl = (byte & 0x0F);
bh = (byte & 0xF0)>>4;
chklow = (bl << 1) & 0xF;
chklow_ovf = bl >> 3;
chkhi = (((5+bh) >> 1) << 2) + (3-chklow_ovf);
return (chkhi << 4) | chklow;


The 2nd byte is simple enough:

Low nibble of incoming byte/Low nibble of resultant checksum: (Overflow happening like above, not shown)
0 -> 4 (ie. B477)
1 -> 7 (ie. B777)
2 -> 6
3 -> 9
4 -> 8
5 -> B
6 -> A
7 -> D
8 -> C
9 -> F
A -> E
B -> 1
C -> 0
D -> 3
E -> 2
F -> 5

This works out as:
Code:

u8 X = (byte + 3) & 0xF;
u8 R = (((X/2) * 4) + (3-X)) & 0xF;

(Ie. VERY similar to above)


But it does seem to interface with B0 also. For example:

Low nibble in / Result when B0 = 1 / Result when B0 = 2
0 -> 6 / 8
1 -> 7 / B
2 -> C / 6
3 -> 9 / 9
4 -> A / 4
5 -> B / 7
6 -> 8 / A
7 -> D / D
[ Same as above with msb flipped]
8 -> E / 0
9 -> F / 3
A -> 4 / E
B -> 1 / 1
C -> 2 / C
D -> 3 / F
E -> 0 / 2
F -> 5 / 5

Not quite sure why yet. Well, I have an obination of a program using loops, lookup tables and the like to figure it out, but I keep thinking there's got to be a better way.

Maximus
March 16th, 2012, 10:42
hi, sorry, I made some typo copying from the paper scrap - i.e. overflow had to be "Low Nibble Overflow = Low Nibble >>4".

yep, i did notice the '3' dependency, but your initial data wasnt too much to draw conclusions

for the low nibble, contribution from 1 to 2 varies by +3 &0xF from the first byte, check it out from 2 to 3 etc to see if it's coherent (also, take care of msb flip).