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
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 11 Sep 2014 06:53:49 -0400
From: Bill Cox <>
Subject: Re: [PHC] Makwa is broken given p and q

Hash: SHA1

On 09/11/2014 03:21 AM, Steve Thomas wrote:
>> On September 11, 2014 at 12:57 AM Andy Lutomirski
>> <> wrote:
>> On Wed, Sep 10, 2014 at 8:55 PM, Steve Thomas <>
>> wrote:
>>> Given p and q you can do: e = 2 ** cost e' = 2 ** cost (mod
>>> (p-1)*(q-1)) x ** e = x ** e' (mod p*q)
>> This is described (in the CRT formulation) in the Makwa paper.
> So it was known that you can modulus the exponent and have it run
> in constant time, in comparison to the cost factor.

Yes.  This exact algorithm is described in the "False Path" section on
page 13.  He recommends using this trick to compute the 300-ish
alpha/beta pairs.

A significant weakness in Makwa is that p and q are essentially a
shared secret key between all passwords using the same p and q, which
would typically be all the passwords hashed by a particular company.
Revealing p and q could destroy the security of an entire database of
passwords.  Once the alph/beta pairs are computed, p and q should be
securely scrubbed from memory.

However, what's to keep all the major online companies from being
NSL-ed with demands to hand over p and q to the government before they
are scrubbed from memory?  Makwa is a dream come true for Big Brother

>>> You could pick the cost to be 2 ** 128. Without p and q you
>>> can't test a password. powConst = powm(2, pow(2, 128),
>>> (p-1)*(q-1)) hash = powm(password, powConst, p*q) but you could
>>> just do HMAC(password, secretKey)
>>> Sorry but even if you came up with the perfect server-specific
>>> shortcut, HMAC or encryption with a secret key is better.
>>> If you don't know the secret, it takes 3x longer. vs If you
>>> don't know the secret, you can't do anything.
>> Huh? I don't think that anyone is proposing using Makwa with cost
>> 2^128.
> I was picking an absurd number to prove a point that apparently was
> known. I guess the escrow should have tipped me off that we don't
> see eye to eye on what we think is secure.
> I stand corrected, not broken, but my opinion is this is bad.

Calling "Escrow" a positive feature of Makwa kind of gave me chills.
At least the author was quite explicit about how p and q might be used
by governments that demand a fast path.

I would like Makwa more if we could securely compute n once for every
user, and make sure that all knowledge of p an q are destroyed.  This
would simplify implementations a lot, though security would be lower
in the sense that a single factored number would compromise the whole
world's password databases.

Short of that, I would want every user to generate p and q locally and
scrub them from memory, so p and q never leave a smart-phone, for
example.  In order to log in from multiple devices, the server would
have to pre-compute alpha/beta pairs, without the benefit of the false
path - either that or complicate the authentication protocol and have
the device send alpha/beta pairs to the server.

In my P2P Internet of Things vision, this is less of a problem.  A
user trying to control his home devices remotely would authenticate
with his personal home server device, which would authenticate him
using remote ASIC based Makwa boxes.  Also, remember that Makwa gives
an ASIC attacker a very large computational advantage vs our PCs, so
Makwa needs to be built with ASICs from the start.

I still put Makwa in the "other" category.  It is not a memory hard
password hashing algorithm, and cannot replace Scrypt in many
applications.  However, it's delegation feature is potentially
game-changing in applications which don't even exist yet because we
could not get the security right.  One of our biggest challenges is
figuring how a toaster's worth of compute power can protect it's
communication as securely as a mainframe.  Delegation solves a major

Version: GnuPG v1


Powered by blists - more mailing lists