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: Thu, 13 Feb 2014 09:31:01 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

On Wed, Feb 12, 2014 at 9:19 PM, Samuel Neves <sneves@....uc.pt> wrote:
> This thread has gone rather offtopic by now, but this happens to be a
> topic that I like :)
>
> On 11-02-2014 20:31, Dennis E. Hamilton wrote:
>> The Art of Computer Programming volume 2 section 4.6.3 (pp.461-485!) is all about Evaluation of Powers.  This devolves into an extensive treatment about addition chains, which have certain applications to optimization of arithmetic, including some interesting material about x^n mod w).  Some of this material seems relevant to folks concerned about speed-ups that overcome work-factor-increasing devices.
>>
>> The use of multiplications and divisions for powers is a case of addition-subtraction chains and the only mention I spotted is in exercise 4.6.3-30.  There are times when the addition-subtraction chains are shorter than the addition chain and the solution mentions some heavy-duty analysis (i.e., by Paul Erdos) and also ties to other material where addition-subtraction chains are workable (although having 1/x available as part of it strikes me as a stretch for integer work, but maybe not for modular arithmetic).  These matter when n is a known constant.  Otherwise the so-called binary method is what works best.
>
> 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

Thanks for the links.  I've been avoiding studying up on ECC, and now
I guess I'll have to spend a weekend making my wife mad while I read
up on this :-)

So, multiplication and division become addition and subtraction...
that's very cool.

Bill