Date: Sun, 7 Sep 2014 15:22:01 +0200
From: Thomas Pornin <pornin@...et.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - skipping Makwa

On Fri, Sep 05, 2014 at 04:10:24PM -0400, Bill Cox wrote:
> This is because his estimate than an ASIC attack would be ineffective
> is wrong, by a very large margin.

For the record, I don't estimate that an ASIC attack would be
ineffective. I kind of state the opposite, even. My point is that
FPGA-based attacks, and, even more, ASIC-based attacks, become worth the
effort (i.e. cheaper than a PC farm on a per-cracked-password basis)
only within an _economic_ context which does not exist yet. As you write
in another message, budget for an high-end ASIC is in the dozens of
millions of dollars. An attacker who indulges in ASIC is not after
passwords for Facebook accounts... So, for such ASIC to make sense, you
need to imagine a scenario where the password hashes to crack are very
valuable, or there are an awful lot of them, or both.

Bitcoin-like mining is a good example, because it provides a lot of
incentive (money !) and has demonstrably spurred the development of
dedicated ASIC. As you point out, if such ASIC become available, then
Makwa's support for delegation eases the leveraging of that techonology
by the defender too, which brings balance back. As an aside, an ASIC
that can speed up Makwa is also an ASIC that can speed up RSA, and that
may open other markets completely unrelated to passwords.

The undercurrent of all this is that high-end attacks are not only a
technological problem; at least half of the issue is about economics,
which is another specialty that I don't master at all. Hence I try not
to make predictions in that area. Cheaper attackers, in the sub-100k$
budget range, are easier to deal with: since they must use off-the-shelf
CPU, GPU or FPGA, then I can use current market prices to work out what
hardware is best for the attacker, and it turns out that when the target
is Makwa, then the CPU wins (although not by much) -- which is the best
I can hope for (and more than I actually hoped for; before looking for
benchmarks, I expected GPU to be like 5 to 10 times faster than CPU at
RSA/Makwa, and I was quite surprised that it was apparently not the
case).


> - - Step 4 on page 8 scrambles V, so that step 5 has a V which may
> contain 0x1 values, so the 0x1 is not easily seen as a terminator.
> Should step 4 be removed?

The 0x01 in step 5 does not serve as terminator; the length of V is
known and fixed (it is equal to the output size of the underlying
hash function) so there is no need for a "terminator". The point of
the 0x01 is to be distinct from the 0x00 used in step 3 (or at least
so it appears to be).


> - - Step 8 generates Hs(m) which is trivially determined to be
> non-random.  Should he simply append a counter and hash for each
> output word instead?

The whole "inner KDF" used in Makwa and described in section 2.3 of the
specification is a faithful, exact copy of HMAC_DRBG. This is voluntary.
The security of any cryptographic construction can be ascertained in
mostly two ways: through "security proofs", and through "battlefield
testing" (i.e. being published and reviewed by many people for many
years). HMAC_DRBG offers both: it has been around for a decade, _and_
some in-depth security analysis have already been published. Any custom
modification of mine would annihilate these properties. I don't want
that.

This is a generic design goal of Makwa: as much as possible, I reuse
existing components, because this means reusing the corresponding
security analysis. This also has benefits for performance: for instance,
by using squarings modulo what is, basically, a RSA modulus, any Makwa
implementation can use existing _optimized_ RSA implementations (the C
reference implementation, for instance, uses OpenSSL's "BN" code, which
has been optimized for RSA). That way, I don't have to go through the
very tiresome process of writing assembly code for a dozen architectures
and then testing it on a hundred machines; I can simply reuse what
already exists, both for code and benchmarks.


> - - Note: 10 byte output hash is recommended as the minimum, but if that
> is used, we will be able to find input collisions with only 2^40
> tries.  This could be used by an attacker to exploit bugs in some
> cases, so I would prefer to use 20 byte output as the minimum

Honestly I don't find such collision-exploit scenarios realistic.
However, if that bothers you, then you are free to go to 12, 16, 20 or
457 bytes if you wish it so.


> - - If we do pre and post hashing, supporting to 4096 isn't too ugly

There are a few big-number implementations optimized for RSA which
can use 2048-bit integers but not 4096-bit integers. This is an edge
case, but it might matter for some systems (especially embedded
systems). I also like the "2048-bit" size because it maps well to
recommendations for RSA.


> For Makwa to be secure, we need some assurance that picking a random x
> value and squaring it many times continues to do useful work, and will
> not cycle back on itself quickly.

As we discussed, this assurance really is a subcase of a more general
property: we need the modulus to resist factorization. There again, I
don't invent anything; resistance of RSA modulus against factorization
has been intensively studied for more than three decades (arguably,
factorization has been studied for more than 2500 years, but the
cryptographic implications date back from the late 1970s). The general
conclusion is that random prime selection is fine, and aiming at "safe"
primes (for any notion of "safe") does not actually increases security.

The only departure from "true RSA" key generation in Makwa is the
insistance of using a Blum integer. 25% of randomly generated RSA keys
are Blum integers, so that's not a big worry.


	--Thomas Pornin

Powered by blists - more mailing lists