[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20130818222250.GA31591@openwall.com>
Date: Mon, 19 Aug 2013 02:22:50 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Parallella: bcrypt
Katja, Yaniv -
On Mon, Aug 19, 2013 at 01:58:09AM +0400, Solar Designer wrote:
> On Mon, Aug 19, 2013 at 12:01:46AM +0400, Solar Designer wrote:
> > So far all three have this in common: the second one of two salts, and
> > the (mod 32) password numbers are all within the first half of a
> > 32-password range. (When generating these hashes, one of the two salts
> > was chosen at random, without obvious correlation to hash number. So
> > these are two separate observations.)
>
> This is still almost true for all observations so far, with the only
> exception being 18 (mod 32), but it occurred in the same block with
> 2 (mod 32) also failing - and these two were computed on the same core
> at the same time, if I understand correctly (the difference is 16).
>
> All of the failures are consistently for the second one of the two salts
> so far.
Here's what I think is happening:
When processing the second salt, the keys are unchanged, so they are not
being sent from the host and the start2 field is not used. This lets
Epiphany proceed with computation quicker, based on the start1 field
only. If there's some out-of-order data transfer going on for the
portion of the inputs struct that contains the salt and the start1
field, then it is possible that not-yet-fully-updated salt is used.
When the start2 field is also used, this is just less likely (or maybe
impossible) to trigger, since a fairly large amount of data is
transferred after the salt update and before the computation start.
(A similar issue might arise for the keys themselves, though - perhaps
we get lucky simply because they're 72 bytes long, whereas most
passwords are much shorter, and the out-of-order window is perhaps
pretty small.)
So I think we're actually facing the problem that we previously knew of
theoretically. I think Yaniv gave us some advice on how to avoid it,
but frankly I did not follow the project closely enough at that point.
Katja - perhaps re-read Yaniv's postings on this?
As a workaround, we may try to introduce some padding (e.g. 32 bytes?)
before the start1 field (and before start2 as well?) But this is not
perfect, unless Yaniv tells us what the out-of-order transfer window
size is, if such a concept even exists, and it'd be guaranteed to stay
not larger than a certain size in further (otherwise compatible)
revisions of the platform.
While at it, I noticed that you needlessly copy the keys from external
memory all the time, even when they're unchanged. You only skip the
transfer from the host side, but not the read on Epiphany side. You can
improve the code to skip both (this may provide some speedup in actual
cracking runs when more than one salt is present).
Also, the "flags" variable is mis-described in a comment. You left the
comment at what I had suggested "flags" could be, but its actual meaning
has since deviated from the initial idea. You'll probably want to
update the comment (in both source files).
Meanwhile, here's one more missed password:
$2a$04$112345678911234567891utqNEaCUz02iMFOhD0KkuDRBNqgMKEaW:4621
It's 13 (mod 32).
Oh, and running similar tests on full length 72 passwords would be nice.
Alexander
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.
