Welcome to the new Woodmann RCE Messageboards Regroupment
Please be patient while the rest of the site is restored.

To all Members of the old RCE Forums:
In order to log in, it will be necessary to reset your forum login password ("I forgot my password") using the original email address you registered with. You will be sent an email with a link to reset your password for that member account.

The old vBulletin forum was converted to phpBB format, requiring the passwords to be reset. If this is a problem for some because of a forgotten email address, please feel free to re-register with a new username. We are happy to welcome old and new members back to the forums! Thanks.

All new accounts are manually activated before you can post. Any questions can be PM'ed to Kayaker.

Breaking a challenge response

To discuss DES MD5 El-Gamal RSA PGP and others....
Locked
User avatar
squidge
Posts: 631
Joined: Tue Sep 03, 2002 10:10 pm

Breaking a challenge response

Post by squidge »

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
Member
Posts: 61
Joined: Tue Jul 31, 2007 8:38 am

Post by dion »

never seen that.

why not trying above 70 for 1st byte?

BA FEFE 3232 7676 B

it might be repeated for above 70h.
User avatar
squidge
Posts: 631
Joined: Tue Sep 03, 2002 10:10 pm

Post by squidge »

It does repeat - that's what I mean by 'wraps around'
User avatar
Maximus
Posts: 481
Joined: Mon Sep 19, 2005 3:09 am
Location: NDA

Post by Maximus »

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: Select all

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.
I want to know God's thoughts ...the rest are details.
(A. Einstein)
--------
..."a shellcode is a command you do at the linux shell"...
User avatar
squidge
Posts: 631
Joined: Tue Sep 03, 2002 10:10 pm

Post by squidge »

Thanks for that, seems a little different to my version, which is basically:

Code: Select all

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: Select all

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.
User avatar
Maximus
Posts: 481
Joined: Mon Sep 19, 2005 3:09 am
Location: NDA

Post by Maximus »

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).
I want to know God's thoughts ...the rest are details.
(A. Einstein)
--------
..."a shellcode is a command you do at the linux shell"...
User avatar
squidge
Posts: 631
Joined: Tue Sep 03, 2002 10:10 pm

Post by squidge »

Maximus wrote: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).
Sorry, don't quite get what you mean here.

If we assume byte 0 is 0x00, then result is B477. If byte 1 is also 0x00, then the result isn't modified (still B477). If byte 1 is anything else, the above code works fine.

The following code also works nice (ignoring MSB for now):

Code: Select all

chklow = (4 + (2*(byte/2)) + (3*(byte & 1))) & 0xF;
However, if byte 0 is 0x01, then the above code doesn't work, and I can't work out how to make it work :o

The sequence changes from 47698BADCFE10325 to 67C9AB8DEF412305. Every other nibble in the sequence is identical (79BD, etc).

If byte 0 is 0x02, then we seem to get yet another sequence 8B6947AD03E1CF25. Again, 8 nibbles are common, the remaining being different (by an offset of 4).

Maybe I'm just not looking at this right.
Locked