phc-discussions - OT: [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>] [day] [month] [year] [list]

Date: Thu, 13 Feb 2014 18:33:10 -0800
From: "Dennis E. Hamilton" <dennis.hamilton@....org>
To: <discussions@...sword-hashing.net>
Cc: <sneves@....uc.pt>
Subject: OT: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

The significant amount of number theoretic lore that crops up here fascinates me too, although I am not fluent with it.

I missed the "Duality in Addition Chains" in my scrutiny, though I have it [;<).  The addition-subtraction business works because of the law of exponents, of course.

In the 1998 (third) edition of The Art of Computer Programming, volume 2, it appears that those results and others are folded in, often in the exercises and the discussion that are part of the solutions.  Pippenger's observation about the duality of direction is buried in there.  The Bernstein paper is a wonderful expansion, and the page 10 "Setting the record straight" is a hoot, especially considering patenting of mathematical methods.  (The mentioned patent has expired, but the problem of recognizing prior art when it is not identified the same way is telling.)

Thanks for both links.  I now understand who is being referred to as BJD.  (I'm a newcomer here.)

 - Dennis

-----Original Message-----
From: Samuel Neves [mailto:sneves@....uc.pt] 
Sent: Wednesday, February 12, 2014 18:20
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

This thread has gone rather offtopic by now, but this happens to be a
topic that I like :)

[ ... ]

Addition-subtraction chains are popular with elliptic curves, where
"division", i.e., subtraction, is very cheap. Similarly, multiplication
by a constant can make good use of subtractions. You can see them (plus
many other techniques) put to good use in, e.g., [1].

We can do much better than the binary method, at very little
computational cost. Namely, by doing a small precomputation at the start
and processing w bits of the exponent at a time, we can perform lg(e) +
lg(e)/w + 2^w multiplications on average instead of lg(e) + lg(e)/2.
There are many improvements building on this idea, of course; the survey
by Dan Bernstein [2] is a good read on the subject, on top of Knuth.

> I couldn't find more in any of the Knuth Collected Works papers that I have, and the early paper might be in the Discrete Mathematics volume.  

"Duality in Addition Chains", co-authored with Christos Papadimitriou,
is reprinted in Chapter 31 of Selected Papers on the Analysis of
Algorithms. It does not contain any particular improvement, but it
contains an interesting observation: for each addition chain that
"scans" the exponent bits left-to-right, there is another addition chain
that scans right-to-left, which is its transpose (when looking at the
chains as matrices).

[1] http://www.hyperelliptic.org/EFD/precomp.pdf
[2] http://cr.yp.to/papers/pippenger.pdf