Discussion:
reverse of full sha1 and sha256 limb when hash and block are known
(too old to reply)
Aleksey Cherepanov
2015-09-03 00:34:54 UTC
Permalink
Raw Message
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!
--
Regards,
Aleksey Cherepanov
Aleksey Cherepanov
2015-09-03 00:40:41 UTC
Permalink
Raw Message
Post by Aleksey Cherepanov
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
I meant 2x speed up. That's 100% higher speed. Sorry!
--
Regards,
Aleksey Cherepanov
Aleksey Cherepanov
2015-09-03 14:44:58 UTC
Permalink
Raw Message
Post by Aleksey Cherepanov
tl;dr: if W and hash are known, initial state can be computed. ... PROFIT!
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.
For sha256, it means that it is possible to utilize interleave not
bumping L1 cache size for code. But higher number of registers may be
bad. (Interleave might be tried without reverse on a system with
permitting cache size.) Though for raw-sha256, it is useless unless
only 1 hash is to be cracked. sha256($p.$s) and similar may be
meaningful if there are no salt dupes.
Post by Aleksey Cherepanov
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.
sha224 unlike sha256 is not that easy: it looses 1 integer in the end,
so there is no reliable way back. But it is possible to bruteforce
missing integer. This way, 1 hash gives 2^32 variants of initial
states. So result of the first block have to be checked against all of
them. To reject 1/2^N candidates earlier, it is needed to store 32+N
bits for each state.

sha384 looses 3 integers (64 bits each). So the same trick is not
applicable.

Thanks!
--
Regards,
Aleksey Cherepanov
Aleksey Cherepanov
2015-10-01 00:01:43 UTC
Permalink
Raw Message
Post by Aleksey Cherepanov
tl;dr: if W and hash are known, initial state can be computed. ... PROFIT!
No, it is a mistake.
Post by Aleksey Cherepanov
Looking at sha1 round, it is obvious that each round can be computed
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.
That's true only for a part. But pre-block state is added after block,
so we have f(x) + x == hash where hash is known, x is unknown and f
is known but very complex. My code worked because it is for 1 block:
we know x, but it won't work for 2 block when x is not known and can't
be subtracted from hash.d

Thanks!
--
Regards,
Aleksey Cherepanov
Loading...