phc-discussions - Re: [PHC] Are password trailing 0's a problem?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20140312102146.GA21190@openwall.com>
Date: Wed, 12 Mar 2014 14:21:46 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Are password trailing 0's a problem?

On Sat, Mar 08, 2014 at 03:22:57AM +0400, Solar Designer wrote:
> On Fri, Mar 07, 2014 at 05:21:06PM -0500, Bill Cox wrote:
> > On Fri, Mar 7, 2014 at 11:49 AM, CodesInChaos <codesinchaos@...il.com> wrote:
> > > As an example with nice printable characters in both passwords:
> > >
> > > `plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd`
> > > and `eBkXQTfuBqp'cTcar&g*` have the same PBKDF2-HMAC-SHA1 hash (no
> > > matter the salt or the number of iterations).
> > >
> > > I found those with a CPU and unoptimized code. One of our GPU hashing
> > > friends could easily find a similar pair for PBKDF2-HMAC-SHA-256.
> > 
> > Sweet.  I assume the only difficulty is finding a printable character
> > hash, which is something like 70 out of 256 values, so the printable
> > hashes for HMAC-SHA256 would be 1 in (70/256)^32.  We'd have to search
> > about 1e18 to find one, so a billion billion... definitely time for a
> > GPU farm.
> 
> There are 95 printable 7-bit ASCII characters, not 70.  The attached
> trivial program may do the trick in a couple of weeks on a fast server.

The program was buggy: for a good chance of success, we need to be
changing 8 chars in the template, not 7.  The 64^7 space is too small.
Sorry!

Running a corrected revision of this, I got:

scrypt(PBKDF2-HMAC-SHA256-fail-affects-scrypt-no-security-issue-bGoDFpr8) = scrypt(;`B3nR6wQ2-_LSg"mH #yszm`[#z8B&L) for any salt, N, r, p

(Tweeted it.)

The embedded " and ` are not great, but on the other hand there's no '.
The total number of different characters in the shorter password is 26.
(The total number of different characters across both passwords could be
made much smaller by repeating the same character in place of the
message.  Then it'd probably contain only 9 different characters.)

This may be usable to check whether a site uses something based on
HMAC-SHA256 (with PBKDF2's order of key and salt inputs) or not.

Alexander