phc-discussions - Re: [PHC] Makwa is broken given p and q

lists.openwall.net		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 02:21:01 -0500 (CDT)
From: Steve Thomas <steve@...tu.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Makwa is broken given p and q

> On September 11, 2014 at 12:57 AM Andy Lutomirski <luto@...capital.net> wrote:
>
>
> On Wed, Sep 10, 2014 at 8:55 PM, Steve Thomas <steve@...tu.com> 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.


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