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.