phc-discussions - Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

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] [thread-next>] [day] [month] [year] [list]

Date: Mon, 10 Feb 2014 23:10:30 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

On Sat, Feb 8, 2014 at 10:16 PM, Samuel Neves <sneves@....uc.pt> wrote:
> On 09-02-2014 02:52, Bill Cox wrote:
> This is a well-known variant of the addition-chain problem. SPIRAL [1]
> generates the following code sequence, using 7 additions:

In 1984, I was infatuated with the president of the math club at
Berkeley (who was female - no, not Eve), where I hung out with a few
guys who were a lot like SolarDesigner, in that they were simply
smarter than me.  In some comp sci class the prof asked us to compute
x^n, for x and n integers, and of course we all came up with the
power-of-two standard solution, but I was a wise-ass and for the
specific constant the prof asked for, I gave a slightly improved
answer.  My super-genius friends and I grabbed this problem and
couldn't sleep for days.  We had asymptotic lower bounds on the number
of required multiplies, and a formula for increasing sized integers
that converged to it.  We wanted to talk with an expert, and Donald
Knuth was the guy, so one friend of mine who you might know from Junk
Yard Wars as Geo the Guestimator and I dropped by Stanford to see if
we could chat with Donald Knuth about it, but he was out for the
summer on sabbatical.  Thinking to call first was not the sort of
brilliant idea we would have come up with :-)

Geo and I were both from Palo Alto, so we were on our way home for the
weekend anyway.  I loved seeing this related problem, and had to write
some a quick hack to find optimal solutions.  I miss hanging out with
super-geeks who are way smarter than me... they are rare here in NC.
Thus the alter ego waywardgeek...

Bill