[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150903144458.GA4495@openwall.com>
Date: Thu, 3 Sep 2015 17:44:58 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: reverse of full sha1 and sha256 limb when hash and block are
known
On Thu, Sep 03, 2015 at 03:34:54AM +0300, Aleksey Cherepanov wrote:
> 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.
> 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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
