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
| ||
|
Date: Sun, 7 Sep 2014 23:58:12 +0200 From: Thomas Pornin <pornin@...et.org> To: discussions@...sword-hashing.net Subject: Re: [PHC] A review per day - skipping Makwa On Sun, Sep 07, 2014 at 05:27:05PM -0400, Bill Cox wrote: > Will concerns about lack of 4096 support still be an issue say 3 years > from now? Issues of lack of portability / support tend to linger for years or even decades, and then disappear suddenly without much prior warning. It is hard to predict. > Will 2048 still be wide enough? NIST says that 2048-bit RSA is fine until at least 2030. This is the general consensus among researchers (see http://www.keylength.com/ for a comparison of such estimates published by several bodies). A crucial point is that the last real breakthrough in factorization was the General Number Field Sieve, back in 1989 (25 years ago); since then, we got a lot of fine-tuning, and the usual progress in available computer power for a given budget (aka "Moore's law"), but no significant theoretical progress (at least none of the same magnitude). Estimates on RSA key strength in future years assume that things will stay that way for the next two decades. > I was wondering if it might make sense to use a single prime as the > modulus, rather than a Blum integer? If you compute modulo p, then the time cost can no longer be applied. It is not that you have no fast-path; instead, everybody has the fast-path. Indeed, for any x (non-zero) modulo p, and nonnegative integer w: x^(2^w) = x^(2^w mod p-1) mod p Thus, the amount of CPU involved in the w squarings remains fairly low. If you want to use squarings or any kind of exponentiation modulo a known prime as the "heavy" operation, then you have to do it many times successively, with some hashing between any two such operations. This basically means no delegation. > Do we really need the extra complexity and delay in each client for > finding good primes, and then computing 300 2048 bit values to the > power of 2^w mod n? These need to get created when the user changes > his password. Where would all the alpha and beta values be stored? There may be some misunderstanding here. In a classic "server authenticates incoming clients" setup, it is expected that the passwords for _all_ users on the same server rely on the same modulus, which is generated by the server once and for all. In fact, the whole world could use the same modulus, if there was a way to generate a modulus such that everybody is convinced that the prime factors were not kept anywhere. To avoid this trust issue, and to possibly allow for a fast-path or unescrow feature, each system that must hash passwords with Makwa is expected to generate its own modulus at installation time -- i.e. only once per decade. It does not need to be done for each user, and certainly not whenever a password is changed. Now if you consider a scenario where a given device uses Makwa for, say, hashing its internal storage (a TrueCrypt-like situation), then the OS may still use a hardcoded modulus: since usage of an OS binary is relative to how much you trust whoever compiled it, you may as well trust a modulus that was included in the binary at compilation time. Namely, you trust that whoever generated the modulus (which is hardcoded) did not keep the factors anywhere. Alternatively, generating your own modulus is not very expensive in general, and the alpha+beta pairs can be efficiently computed with the fast path if you produce them at the same time (since you have the factors at that point); on a modern PC, the whole generation process will be done within one second or so. For storage, the 300 alpha+beta pairs amount to about 150 kB: not a lot if you need Makwa for password-based encryption of a SSD. Note that, there again, there is no need to change the modulus when you change your password. --Thomas Pornin
Powered by blists - more mailing lists