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 linuxcveannounce PHC  
Open Source and information security mailing list archives
 

Date: Thu, 11 Sep 2014 15:54:19 +0200 From: pornin@...et.org To: discussions@...swordhashing.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 512bitormore primes, and a probability of having at least two such factors in the final product of at least 12^(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 FFTbased multiplication, and that entails considerable development effort. When Makwa uses a 2048bit 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 wellpublicized 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 completelyopensource 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