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.