Date: Thu, 11 Sep 2014 15:54:19 +0200
From: pornin@...et.org
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Makwa parameter generation

> Makwa shares this problem with ZeroCoin, which uses a composite
> modulus in its accumulator. I believe the ZeroCoin developers work on
> creating RSA moduli via secure multi party computation.

The ZeroCoin article:

  http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

talks about generating the modulus for the accumulator through
either a "trusted setup phase", or with Sander's RSA UFO, described
here:

  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.4015

The core idea of RSA UFO is the following: if we want a modulus with
two prime factors of at least k bits, then we generate several random
integers of 3k bits, and multiply them all together. If we use enough
such integers, then probability that at least one of them has two
prime factors of at least k bits can be made arbitrarily close to 1.
However, the resulting modulus is very large. Sander says that if
you want 512-bit-or-more primes, and a probability of having at least
two such factors in the final product of at least 1-2^(-80), then the
modulus will have size "much greater than 40000 bits".

To keep on with security levels as recommended in 2014, we would
prefer prime factors of at least 1024 bits, so the modulus size will
probably need to be more than 80000 bits, in fact probably much more
than that (I did not do the maths to get the actual size, and I suspect
that Sander did not either).


Now a raw Makwa could run with a huge modulus; there is no intrinsic
limitation (the reference code has some limitations -- the encoding
format I used to serialize the modulus and other values cannot
tolerate more than 524280 bits -- but they are artificial and do not
follow from the Makwa maths or even specification). However, this
raises three issues:

 - Not all prime factors of the huge modulus will be equal to 3 modulo
   4. I have not worked out all the implications, but some thinking
   would have to be devoted to that issue, so as to avoid leaking some
   information through Jacobi symbol computations (for instance).

 - When the modulus is large, classic implementations of the squaring
   operation (Montgomery multiplication) are no longer optimal; to
   get the fastest code (and you want to get it, because that's what
   the attacker will do), you have to switch to more advanced
   algorithms such as FFT-based multiplication, and that entails
   considerable development effort. When Makwa uses a 2048-bit RSA
   modulus, then existing optimized code for RSA can be reused, and
   that is a good thing; huge moduli deprive us of that advantage.

 - Delegation cost raises with the modulus size (quadratically, if you
   use Montgomery multiplication). With a behemoth of a modulus, the
   delegation cost will be so high that delegation is no longer worth
   the effort. Without delegation, Makwa loses quite a bit of its
   attractiveness (it will not fall apart, but it would not be much
   better than PBKDF2).

Now if the ZeroCoin people find something better, then Makwa could
benefit from it.


We might imagine a procedural solution, if we don't find a cryptographic
one. Conceivably, we could organize a party where some "big names"
gather together (e.g. Adi Shamir, Linus Torvalds,... or maybe the whole
PHC panel, for good measure) and, in that order: buy a computer,
implement a RSA modulus generator that does not save the prime
factors, run it a few times, publish the resulting moduli, and burn the
computer down ("it's the only way to be sure"). The equivalent of a
"key ceremony" as is customary for setting up CA in the X.509 world.

This would result in a few moduli that people could trust and use. The
event would have to be well-publicized and organized in such a way that
the absence of a spying device in the hardware can be convincingly
asserted; if Stallman is invited he would probably insist on using a
completely-opensource Lemote YeeLoong laptop, though opensourceness does
not preclude spying if you did not witness the complete hardware
assembly process. Maybe building up something from an Arduino kit ?
Or keeping the machine within a Faraday cage and blasting it to
smithereens at the end, so that any potential leak would be stopped.

Either way, it looks hard.


        --Thomas Pornin

Powered by blists - more mailing lists