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: Sun, 14 Sep 2014 05:12:43 -0500 (CDT)
From: Steve Thomas <>
Subject: Re: [PHC] Makwa is broken given p and q

Sorry for taking so long I got scared by the long message *ashamed*. Anyway I
wrote down my thoughts on improving Makwa and arguing points. So I thought I
should read and reply to this first.

> On September 11, 2014 at 6:51 AM Thomas Pornin <> wrote:
> On Thu, Sep 11, 2014 at 02:21:01AM -0500, Steve Thomas wrote:
> > 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.
> It IS secure -- I am just going to the end of the logic.
> The CFP called for a desirable feature (among others): "For example, one
> may design a scheme that is slow to evaluate except on a server given
> some server-specific shortcut."
> It so happens that if such a "shortcut" exists, then it can be
> leveraged, by definition, into a much faster attack. The whole core
> assumption of PHC and password-hashing functions is that dictionary
> attacks work, which is why we cannot just use a simple MD5 and be done
> with it. I am then following that idea to its unavoidable conclusion: if
> a "shortcut" exists, then it is almost equivalent to a free password
> recovery for whoever can use it. So I am calling it "escrow" because
> that's what it is.

I'm confused I thought escrow and fast path were different. Also I don't believe
that fast path is an escrow. In your paper, page 12, you have a table that says
that escrow is not possible with pre-hashing and/or post hashing. Either you
need to fix that or escrow and fast path are different. Also I remember from
your Passwordcon14 talk that you purposely had the password in plaintext before
squaring for escrow. So that you can get access to the original password.

> If you think of the shortcut (or "fast path") as a kind of escrow, then
> the correct terminology is that of asymmetric encryption. A password
> hashing function with a possible shortcut really is deterministic
> asymmetric encryption:
> - If you don't know the private key, you can still encrypt the
> password. To _verify_ a password, you also encrypt it, and check that
> you get the same value -- that's the point of the encryption being
> deterministic.

Yeah, I've done this with a Teensy doing AES-CBC-CTS encrypt to prevent a leaked
database from being able to be cracked. I called it "JustEncrypt".

> - If you do know the private key, then you can decrypt, which is all the
> escrow or shortcut that you may need.

Now that's an escrow... shortcut? Oh decrypt then compare password or oh. Did
you mean something like:
"If you do know the private key you can use a short cut and escrow the password
since you can decrypt."

> > I stand corrected, not broken, but my opinion is this is bad.
> There IS one bad thing: as explained above, if you don't want to hear
> about any escrow or shortcut, and be sure that nobody can ever access
> the p and q factors, then you must "forget" them just after having
> generated them and multiplied them together to compute the modulus. This
> is easy enough to do (the generation tools provided with the reference
> implementations of Makwa do just that), but there is no way to do it
> _convincingly_.
> By this I mean that though I can generate a modulus, I have no method to
> convince _you_ that I did not keep the p and q factors around. This is a
> problem for which cryptography has not yet found a reasonable solution
> (there is a published construction, but it results in a very large
> modulus). If such a method was known, I would have applied it, and it
> would have resulted in a modulus that could be hardcoded and used
> everywhere in the whole world.
> Therefore, I turned to the next best thing, which is custom modulus
> generation. That is, if you want a modulus such that you are sure that
> the p and q factors have not been saved anywhere, then just generate it
> yourself. It will be your own modulus. It can be used for hashing all
> the passwords of people who trust YOU.

That's the problem if you tell people it's secure and that you can have a high
cost to attackers while having a low cost to you. People will keep p and q to do
fast path. Basically you can't say "you can keep p and q" to users and tell
critics "well just clear p and q and your issues go away [along with some

Powered by blists - more mailing lists