PDA

View Full Version : help me on reversing hash function


akimp3
December 17th, 2002, 15:24
Hi

I am trying to code a little proggy for decrypting
award bios password. I know that a lot of this proggy
are ready to use ,but i want to learn something.

I have dumped the cmos with different passwords and
i have found the hash of the password the hash is a 16
bit value.
here is some sample :

@ = 4000
a = 6100
2 = 3200
space = 2000
@a = 6101
@b = 6201
@2 = 3201
@space = 2001
a@ = C401
b@ = C801
2@ = 0801
ba = E901
space@ = C000
aa = E501
@@ = 4001
@a@ = C405
@b@ = C805
@2@ = 0805
@space@ = C004
ab = E601
@aa = E505
@ab = E605
ab@ = D807
space@space = 2003
@@a = 6105
@@2 = 3205
a@@ = 5007
2@@ = 6004
aa@ = D407
a@a = 7107
a@b = 7207
@aa@ = D417
a@@a = A11D
aaaa = 3520
aaaaaaaa = 5555
abcdefgh = C471

at left is the password string and the right side is the hash.
as you see for example the hash of @ is 4000,as you know
the ASCII code of @ is 40h.
hash(@a)=6101 theASCII code of a is 61h and ROL 40,2
(40 rotate left two time is 1) so the hash is 6101.
As you see i can not figure out the hash algoritm used by
Award could you please give me a hand?
how should i analyze this data?
do i need to find more hash examples?

I am waiting for your helps.

squidge
December 17th, 2002, 18:11
Why not just decompile a recent Award bios ?

akimp3
December 17th, 2002, 18:28
Hi
thank you very much for your quick reply if you mean
dissassembling, i have already done that but as you know
the bios code can not use any interrupt becaure there is no OS
and itself is the bios.so it works directly with the hardware.for
example it writes directly to the graphic memory for displaying
a message.So the dissassembled code in not comprehencible,i can not find the hashing part.
if you have any suggestion please don't hesitate.

thanks

mike
December 17th, 2002, 21:39
I think he meant reversing any of the "Award BIOS" cracker programs. I think the hash is a linear function of the inputs, however, so if you get enough in/out pairs for each length you can solve it directly.

Basically, you have a variable for each input bit and a variable for each output bit. Each variable is, of course, either 0 or 1. You put one line in your matrix for each pair and then XOR rows so you get a diagonal matrix of input bits. This will show you what the function is.

If you want to come up with a password that matches the hash, just solve for a diagonal matrix of output bits instead.

naides
December 17th, 2002, 21:45
Just a suggestion:

1 - I think the hash includes a 00 byte at the end of the string, as a string terminator.

Attempt to systematically produce the hash of sequential first single bytes:

00 hash 0000
01 hash 0100
02 hash 0200
.
.
.
FF hash FF00

then pairs of bytes SEQUENTIALLY


0000 HASH ?
0001 HASH ?
.
.
.
6201
.
.
.
6204


And so on. If the hash is simple enough (a VERY wild assumption, the hash can be very complicated) , you may get a glimpse of the nature of the opearations


Also think that the hash takes an undefined number of bytes, and produce a short int. any series of ops have to be constructed under these restrictions.

squidge
December 17th, 2002, 23:28
Yup, that's what I meant, but it ended up getting rushed and so half-finished.

I've attached some source code that recovers BIOS password from a range of bios makes (award, ami, etc as well as some specific laptops). As this source code is freely available on the net for download, I don't see a problem publishing it here for anyone interested.

Note: I've no idea if this code is compilable - it's meant for educational purposes only.

Quote:
Originally posted by mike
I think he meant reversing any of the "Award BIOS" cracker programs. I think the hash is a linear function of the inputs, however, so if you get enough in/out pairs for each length you can solve it directly.

akimp3
December 18th, 2002, 13:14
Hi

than you(sqidge,mike,naides) for your help i found some good details that will solve the problen foe string with one an two
character here are my discoveries:

a@
0000000001100001 61
0000000011000010 rol,1 c2
0000000001000000 40
0000000100000000 100 rol,2
0000000111000010 01c2
0000000111000100 01c4 add 2
0000000111000100 01c4

1100010000000001 c401

rol1 x
rol2 y
x=x+y+2
b@
0000000001100010 62
0000000011000100 rol,1 c4
0000000001000000 40
0000000100000000 100 rol,2
0000000111000100 01c4
0000000111001000

rol 1 x
rol 2 y
ROL,1(low niblle y)
x=x+y
ba
0000000001100010 62
0000000011000100 rol,1 c4
0000000001100001 61
0000000110000100 184 rol,2
0000000111100110 01E6
0000000111101001 low nublle y*2 01E9
rol 1 x
rol 2 y
rol ,1 low nublle y*2
x=x+y

a@a 7107
0000000001100001 61
0000000011000010 rol,1 C2
0000000001000000 40
0000000100000000 rol,2 100
0000000111000010 01C2
0000000111001000 01C4

0000000111001000 01C4
0000001110010000 rol,1 390
0000000001100001 61
0000000110000100 rol,2 184
0000010100010100 514

0000011101110001

0000000111001000 01C4
0000011100100000 rol,2 720
0000000001100001 61
0000001100001000 rol,3 308
0000101000101000 0A28
0000001010110111 0A28-771
0000011101110001 0771


a@b 7207
0000000001100001 61
0000000011000010 rol,1 C2
0000000001000000 40
0000000100000000 rol,2 100
0000000111000010 01C2
0000000111001000 01C4

0000000111001000 01C4
0000001110010000 rol,1 390
0000000001100010 62
0000000011000100 rol,2 C4
0000010001010100 454
as you see the formula is:
1-rotate one time to left the first ascci code.
2-rotate two time to left the second characters ascii code.
3- add this two number
4- rotate to left the low niblle of the new number.

by this formula works fine for string of length 1,2
but the part yhat i rotate the low nibble of the sum is not
rigth for string that have 3 or more character so i have to do
something else instead of rotating.
I don't know witch operation will give me the disired result.
please help me to solve this.

akimp3

akimp3
December 18th, 2002, 14:39
@mike

Hi

I am very stupid and i can not understand the matrix that
you told,could you please give me a shape or an example of the matrix?

thanks

forgive me for being a dumb

akimp3

mike
December 18th, 2002, 20:59
Did you ever do solving systems of linear equations in high school? Like

a+2b+3c=52
a-b+c=8
a-2b+c=0

You make a matrix

1 2 3 52
1 -1 1 8
1 -2 1 0

And then add and subtract multiples of rows until you get

1 0 0 6
0 1 0 8
0 0 1 10

and you know that a=6, b=8, c=10.

In this case, we had 3 inputs and 1 output. In your case, you'll have 8n inputs and 16 outputs, where n is the number of characters in the password. All your variables are either 0 or 1. Use XOR instead of adding or subtracting.

If you're right about adding being part of the algorithm, though, this won't work. Look at the file squidge posted to be sure it's all linear (only rotates, shifts, or xors).

akimp3
December 19th, 2002, 17:01
Hi
Thanks to all of you that helped me in learning.
Finally i have foung the algorithm of generating this hash.
Here it is:

x=0;
i=0;
while(string!=null){
{
rol(x,2); //rotate left
x=x+char[I];
i++;
}

Now that i have the algo,as far as i know a hash is a single way function so after reading the hash from the cmos i have to use a
bruteforce to find what character have produced this value.
Is it really impossible to make a reverse function for the hash
after finding its algo?
if not, is there anyway to optimize the bruteforce?

thanks

akimp3

mike
December 19th, 2002, 21:28
If the password is 4 chars or less, you can reverse it directly, since the rol doesn't bring any bits around to the low end. Pretend rol x,2 is x=x*4 and then you have something like

hash = 4^3 str[0] + 4^2 str[1] + 4 str[2] + str[3]

You may be able to extend it to five chars by guessing high bits of str[0].

Anyway, if you can do four or five chars fast, then you can brute force the rest of the chars very quickly.