Aleksey Cherepanov

2015-09-03 00:34:54 UTC

tl;dr: if W and hash are known, initial state can be computed. ... PROFIT!

Looking at sha1 round, it is obvious that each round can be computed

backwards (i.e. starting from hash and going to initial state):

consider a, b, c, d, e after round known, then there are only 2

unknown variables: w[i] and e at the beginning of round. So knowing

w[i], it is trivial to right a formula to compute e. This way we go

reverse.

sha256 is a bit more complex, but it has only 1 unknown variable too.

So it is possible to write reverse algo straight-forward. PoC is

attached.

So sha1 and sha256 behave like block ciphers: you "encrypt" initial

state ("block of data") with W, that is expanded block of message

("key"). And it is possible to "decrypt" hash to get initial state.

There are several applications. The following 2 were pointed out to me

by Alexander Cherepanov, there are my ideas then.

1) To check 1 password against 1 hash, it is possible to meet in the

middle computing halves in parallel. First of all, it is

interleaving, but it is possible to vectorize shared part of

regular and reverse algorithms. It is possible to speed up

defensive usage this way.

2) To check 1 checksum against 1 big file, it is possible to compute

checksum using 2 threads. (But usually(really?) checksums are

checked for multiple files at the same time, thus multithreading is

already there.)

3) Passwords longer than 1 block with repeating tails and same length

have trade off: 1 computation for each hash for each tail or 1 full

computation for each passwords. Lengths 56-64 (inclusive) need 2

limbs but second block does not change at all (1 value for each

length).

4) It is possible to hash beginning and tail independently if memory

permits: compute initial states for each tail for each hash, put

all of them into bitmask (lookup table), compute beginnings and

check against the bitmask. (Is not it called "meet in the middle"

attack?)

Easy practical application

Consider a hash sha256(sha256(...).sha256(...)), for instance

sha256(sha256($p).sha256($s))

sha256($p).sha256($s) produces exactly 1 block of message, so the

second block is 0x80, padding and constant length always. So we can

reverse the second block and check intermediate state computing only 1

limb instead of 2. That's up to 50% higher speed (considering that we

already have other optimizations including caching for sha256($p) and

sha256($s)). With all optimizations and many salts, it should have

same c/s as single block raw-sha256.

I only checked sha1 and sha256. But (many?) other hash functions can

have this behaviour. Also other crypto schemes can give constant

blocks. It is needed to investigate it more.

Thanks!

Looking at sha1 round, it is obvious that each round can be computed

backwards (i.e. starting from hash and going to initial state):

consider a, b, c, d, e after round known, then there are only 2

unknown variables: w[i] and e at the beginning of round. So knowing

w[i], it is trivial to right a formula to compute e. This way we go

reverse.

sha256 is a bit more complex, but it has only 1 unknown variable too.

So it is possible to write reverse algo straight-forward. PoC is

attached.

So sha1 and sha256 behave like block ciphers: you "encrypt" initial

state ("block of data") with W, that is expanded block of message

("key"). And it is possible to "decrypt" hash to get initial state.

There are several applications. The following 2 were pointed out to me

by Alexander Cherepanov, there are my ideas then.

1) To check 1 password against 1 hash, it is possible to meet in the

middle computing halves in parallel. First of all, it is

interleaving, but it is possible to vectorize shared part of

regular and reverse algorithms. It is possible to speed up

defensive usage this way.

2) To check 1 checksum against 1 big file, it is possible to compute

checksum using 2 threads. (But usually(really?) checksums are

checked for multiple files at the same time, thus multithreading is

already there.)

3) Passwords longer than 1 block with repeating tails and same length

have trade off: 1 computation for each hash for each tail or 1 full

computation for each passwords. Lengths 56-64 (inclusive) need 2

limbs but second block does not change at all (1 value for each

length).

4) It is possible to hash beginning and tail independently if memory

permits: compute initial states for each tail for each hash, put

all of them into bitmask (lookup table), compute beginnings and

check against the bitmask. (Is not it called "meet in the middle"

attack?)

Easy practical application

Consider a hash sha256(sha256(...).sha256(...)), for instance

sha256(sha256($p).sha256($s))

sha256($p).sha256($s) produces exactly 1 block of message, so the

second block is 0x80, padding and constant length always. So we can

reverse the second block and check intermediate state computing only 1

limb instead of 2. That's up to 50% higher speed (considering that we

already have other optimizations including caching for sha256($p) and

sha256($s)). With all optimizations and many salts, it should have

same c/s as single block raw-sha256.

I only checked sha1 and sha256. But (many?) other hash functions can

have this behaviour. Also other crypto schemes can give constant

blocks. It is needed to investigate it more.

Thanks!

--

Regards,

Aleksey Cherepanov

Regards,

Aleksey Cherepanov