Message-ID: <20140907215812.GA14840@bolet.org>
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