phc-discussions - Re: [PHC] Password hashing as a self-overwriting Turing machine; Protection of keys in SSH; & new version (July 3)

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: <CAOLP8p4ZHHiAkjXVDdYeEjr4vUPN=w_OU=8FoD7nPg-3pNdZSQ@mail.gmail.com>
Date: Fri, 3 Jul 2015 18:37:23 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Password hashing as a self-overwriting Turing machine;
 Protection of keys in SSH; & new version (July 3)

On Fri, Jul 3, 2015 at 5:59 PM, denis bider <pwhashing@...isbider.com>
wrote:

> Bill -
>
> I appreciate your thoughts! Thank you for your replies.
>

yw

> With regard to Momentum (birthday paradox based proof of work) - that's an
> interesting idea. I'm wondering, though, if the authors aren't trying to
> "smuggle an exponentiality" where it isn't being explicitly considered -
> like in this Scott Aaronson's refutation of Memcomputing:
>
> http://www.scottaaronson.com/blog/?p=2212
>
> Figure (1) in their paper looks great at first sight. The probability that
> there are *any two* matches is exponentially lower than the probability
> of there being a match for a chosen value. Surely, then, it should be
> exponentially more efficient to look for *any two* matches?
>
> Except that looking for *any two* members of a set that satisfy a
> property has exponential cost; whereas looking for *any one* match in a
> set has linear cost, but an exponentially lower probability.
>
> I question whether these two exponential factors in fact cancel out, so
> that the exponentially higher cost of looking for *any two* members
> cancels out the exponentially lower number of members that need to be
> searched.
>

Your intuition is sound.  I spent the day sailing in the San Francisco Bay,
and put some thought into attacking Momentum.  Filling memory can be done
massively parallel at multiple "nodes", and your chance of finding a
collision goes as the square of the memory you manage to fill.  The problem
of finding collisions then becomes a matter of broadcasting hashes
generated in each node to nodes responsible for finding collisions in the
range where the hashes occur.  Acronix FPGAs might be the best silicon I
can buy for this routing problem.  They really smoke.  Once each node has
all the hashes for it's range, it should do a fast (preferably linear) time
sort algorithm to find collisions.

In other words, Momentum is massively parallelizable, with commodity
hardware, custom boards and Achronix FPGAs.  I wish there were still a good
crypto-coin mining operation going on using Momentum.  I'd have to go make
some boards :-)

The problems in Momentum are quite significant.  I can fix a few, but it is
still highly parallelizable.

Bill

Content of type "text/html" skipped