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

Date: Sun, 23 Mar 2014 15:28:00 +0100 From: Thomas Pornin <pornin@...et.org> To: discussions@...swordhashing.net Subject: Re: [PHC] On Delegation (Was: "Why I Don't Recommend Scrypt") On Sun, Mar 23, 2014 at 03:31:42AM +0400, Solar Designer wrote: > My excuse is that it got a bit long (covering several topics at once) Indeed, I have a strong tendency for verbosity. > Being on the panel for PHC, I am aware that you made this submission > (thank you!), but I did not look at it closely yet because (1) I didn't > have time for that yet, and (2) you didn't make it public yet, which > might be deliberate, so I didn't want to be "exposed" to it yet (given > my plans to possibly make a PHC submission too). That's more a consequence of my own mental rigidity, and a habit from previous competitions: radio silence until the deadline. My candidate (called "Makwa"), in a nutshell, is based on squarings modulo a composite integer N (a Blum integer, i.e. the product of two bir primes p and q such that p and q are equal to 3 modulo 4). Input password is first padded into a big integer modulo N (deterministic padding, using a custom KDF and the salt), then squared repeatedly. Pre and posthashing (again with the KDF) can be optionally applied, if you want to support an arbitrarily long input password and/or an unbiased and short output. When p and q are not known, there seems to be no known shortcut to doing all the squarings. When p and q are known, however, computations can be done modulo p and modulo q, and assembled with the CRT, so the total cost is about the same as a RSA private key operation, regardless of the actual work factor (number of squarings): that's the "fast path". Offline cost upgrade is done by simply taking the value and squaring it again (note: posthashing breaks that functionality). Squaring is a permutation of quadratic residues modulo a Blum integer, so there is no "space reduction" to fear here. If p and q are known, offline cost _downgrades_ are possible as well (ultimately, it can also serve as an escrow mechanism for the password). Delegation indeed uses some kind of blinding, though not the same as RSA blinding. Normal RSA blinding is about choosing a random r, multiplying with r^e on entry and 1/r on exit. Here, the exponent "e" is equal to a big power of 2, and computing that blinding would be as expensive as computing the whole function, which defeats the purpose. Instead, I precompute 300 "blinding pairs" and I apply a random selection of them. This is akin to a multiplicative knapsack problem. The cost of delegation is then close to that of a RSA private key operation. As can be seen, such a function is not memory hard; the bulk of computations fit in about 256 bytes (for a 2048bit modulus). By all rights, a GPU or, even more so, a dedicated ASIC ought to be quite faster than a plain PC for such jobs. The idea of Makwa is that delegation allows for harnessing external systems (including the connecting clients themselves), making up for that relative inefficiency. It seems, though, that the boost that can be achieved with a GPU for a given budget is not that big, because modular squarings is all multiplications, and modern x86 are very good at it (in particular, they have a fast 64x64>128 multiplier). > The code in OpenBSD is the spec. I guess that's the point. I come from the "academic crypto world" where articles rule, and implementations are only secondary elements of often poor quality. In these circles, the notion of "the code is the spec" is quite alien. Thomas Pornin
Powered by blists  more mailing lists