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 00:30:07 -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 10, 2014 at 11:20 PM Bill Cox <waywardgeek@...hershed.org> wrote:
>
> On 09/10/2014 11: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)
> >
> >
> > 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.
> >
>
> Of course Makwa is broken if an attacker knows p or q. It is pretty
> worthless in that case. Also, I agree that a master secret key is
> better than a fast-path computation with p and q. Delegation is the
> thing that I like about Makwa. The other features are not
> particularly special, IMO.
>

I don't consider post hashing optional. It's ROT13 if you don't. This breaks
Makwa with post hashing. Delegation is nice but it doesn't matter if it only
saves you 2048 squares and 724 multiplies (724 = 1024-300). I guess you could do
65536 bit primes.

// yes I know these are small primes ~512 bits
p = 0x2051c8ee9a388975c85f9cae57c96a822cdc881ff8fe54cad12b9652bd2a790620ba
d615182464cc6444c87f7f40dd9c4b1401f938a623c495f9f0b0e2193e8f
q = 0x706aeb757dac5f5d9e9ddc1f3beb1341b0d3b1c6250d724d50f6fe464fa140adb6ce
a349a9f6cf5783d3cd5c747e141ae7f15b0a5020406566a674b41bb27777
n = p * q
r = 0x436e2835d24ede3ba2b726477243af8e584868e0e7857834f9bbdb3aca9555669c96
0fba68eb94693c7e514e9609956aaf34a30da2e7675b7266049c91cafb75c9f8478ee093ab
7820014196157455dd28cf376477431b51c0028a0cda98c1c92ae0c009bf2b13dec741e570
8e12b39f8f682e7386c9577456dfe423d5e5d28f


// this will never finish
h = r
for i = 1 to 2 ** 128
{
        h = square(h, n)
}

// but this will
pow = powMod(2, 2 ** 128, (p - 1) * (q - 1)) // One time calculation
h = powMod(r, pow, n) // This took 5.75 ms

h = 0x71a1859bfc2ac1412993bfa8a1834698933ec305f96598b60cfe08cc6718a29d6d36
9fa1c97a22102210a7d11a1e6195e099fb31b91b965a70e19387b13d26669e975fcf1f2fc6
87adc3f31de883378274bc55af0900067107ac4e7de01d070a543f1122d93b9102d55e44c5
d710ba69bbcedb7291622ac74cdcc9fd9dda50


// here's one you can verify is correct
h = r
for i = 1 to 2 ** 24 // This took 114'694.9 ms
{
        h = square(h, n)
}
h = 0xd92aa504450bc9d5262f4e36ffab0ca25d943df1066bbfb7aed2a3e2b058a595d0e9
7c59ba7c42d927a3390f5621cee7c4c0c3a62d285fd7d14e67b5f18c2a838e4a0275bb1148
e2c43fb2c391e5544af2aafd0d4ecfc6be93e97b2bbdceaad955c81b7e9f9b2a116144d710
ead6e61757c8afbb5dde16f4fd955c8c41586b2

pow = powMod(2, 2 ** 24, (p - 1) * (q - 1)) // One time calculation
h = powMod(r, pow, n) // This took 4.6 ms
h = 0xd92aa504450bc9d5262f4e36ffab0ca25d943df1066bbfb7aed2a3e2b058a595d0e9
7c59ba7c42d927a3390f5621cee7c4c0c3a62d285fd7d14e67b5f18c2a838e4a0275bb1148
e2c43fb2c391e5544af2aafd0d4ecfc6be93e97b2bbdceaad955c81b7e9f9b2a116144d710
ead6e61757c8afbb5dde16f4fd955c8c41586b2


**** That's 115 seconds vs 0.0046 seconds. ****

Note it's always 4-6 ms regardless of cost... unless cost is less than like
1.5*log2(n). Then squaring is faster.

P.S. I'm using GMP in PHP :) so it's a little slow.