Date: Sun, 07 Sep 2014 17:27:05 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - skipping Makwa

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thanks again for the detailed reply.  Some comments below.  Sorry you
have to deal with a noob at cryptography, but at least I'm willing to
do my best to attack your system now.  I'm sure better brains will get
involved soon enough.

On 09/07/2014 09:22 AM, Thomas Pornin wrote:
> 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.

I agree that we're not going to see Chinese ASICs anytime soon for
Makwa hashing, at least initially.  Even a low-end ASIC based Makwa
server is a multi-million dollar development effort before there would
be profits.

However, the MiB may be building a Makwa ASIC right now :-)  They
already have RSA ASICs.  While I have no direct knowledge of this, I
would be completely shocked if they did not.

I certainly don't need to explain to someone with your expertise that
there are different levels of protection needed for different
applications.  I would prefer to see Makwa safe for even government
use.  Classified documents must be encrypted when transmitted in some
countries, and those passwords need key strengthening.  That would
best be done using an ASIC base Makwa server, IMO, if Makwa were to be
used at all.  The memory-hard alternatives, like Yescrypt, would
provide a much higher level of ASIC defense when run on the user's CPU.

> 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.

A Makwa ASIC server may indeed have other uses.  This is one reason I
am particularly intrigued by Makwa.

> 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).

One of the reasons I got involved in this competition was I woke up
one morning and realized I could probably build ASICs to crack every
password I had ever used up to that point, but that only the MiB could
afford such attacks.

Protecting our privacy, especially from our own governments, is
something I consider very important.  It is simply not good enough to
protect against GPU based hackers.

I think that it is important to promote Makwa ASIC development for
this to take off.  Once that infrastructure starts gaining momentum,
what we could do with it might be very cool...

>> - - 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.

Thanks for that explanation.  It makes perfect sense.

>> - - 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.

In that case, to make tin-foil hat wearing dweebs like me happy, I
would like to see 20 as the recommended minimum :-)  The opportunity
for bugs that could be exploited seems like an unnecessary risk.
Being able to claim input collision resistance I think should be a
goal of the winners of this competition - not a critical one, but why
not check that box?

>> - - 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.

2048 bit seems perfectly fine, at least in the near term.  If I were
building an ASIC, I might want to go wider, just in case that's where
we are headed.  It's good to think at least a couple years ahead with
an ASIC design.  Will concerns about lack of 4096 support still be an
issue say 3 years from now?  Will 2048 still be wide enough?  I guess
so, from what I've read so far.

I was wondering if it might make sense to use a single prime as the
modulus, rather than a Blum integer?  In particular, that would let us
pick a specific modulus for any given bit width, like we often do with
Duffie-Helman.  We could provide pre-computed alpha and beta
parameters for each work level.  The fast-path goes away, but we
wouldn't need it as badly if we used precomputed values for the
knapsack problem.  Wouldn't this make it faster to login from a new
device, since it would not have to generate all these values?

Sure, the squarings could be reversed, but with a final traditional
cryptographic hash, there's no real threat of inverting the password hash.

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?
If on the server only, does that restrict mobile devices from farming
out password hashing themselves?  One thing I like about Makwa is the
possibility of keeping the user password close to the vest, and not
spewing it all over the Internet before key stretching.

If they were just hard-coded values in the app, there's nothing to
pre-compute, and no p and q to steal.

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUDM2lAAoJEAcQZQdOpZUZEnAP/1nEnit/nKsOCOlqoWQW9ZA7
sYDoIGcW2HuVOBClse883HSMXhYa0O9CYbcCqSPmWIfeaU6FmFtxKa2gBzHRCmva
DEclFWLHoUB71TdSPvfqhxzXopPPP6F8DYso36vL3CBcadBNHkUe4RoABOJ1o9Bb
4BWlqj2LVvw6ZQxHGrk7RzdjBQRAa4oHTeburg4lxAphRXtSutwO17Yks+9CQxHq
k53gDIQFFrOucMNAeFGLeSM3/1FBOjeNs80RkoblIywoLtRvZsShA14RzqHZ13ZH
S6n3OqRsUIcJltOb3JU/Us902mMEQhYZVt3WPG6GTet8/EcKsh5gzHgDqQv1b0eO
eujlOEAq7dUPhhHAw7f0Hj0LzyxXT9THmWdPC7V9o2R7q9NRRN6bcC7bRw3M/+GP
LtmlNyQq7dQCS5BZ6CzsFDV7ZVULwyfaVzXArPqkZ4vLNQKIT0oYR9dKBqk7naCt
9LIchQIyRGVxKSGcTWX8+fAa2LCMx8Ogdy1HOnxbaIvuHX5d+0wxMLGwExY6Oal8
VaCvMU/stKvsxZMvvUGsbzi8BnNd4EoiAz70XM6Dcl89QqxPGejl22fVOO1Quhgu
nyxynhRE+wAuPh5ORIH/duFfbhTke2QyBVsX4W73lqCFfatAmYxWorDow49byZS2
ACkkBlUfcqi6+pFUHAbh
=t31Q
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists