lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Fri, 3 Jul 2015 18:37:23 0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...swordhashing.net" <discussions@...swordhashing.net>
Subject: Re: [PHC] Password hashing as a selfoverwriting 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
cryptocoin 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
Powered by blists  more mailing lists