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
| ||
|
Date: Thu, 11 Sep 2014 06:53:49 -0400 From: Bill Cox <waywardgeek@...hershed.org> To: discussions@...sword-hashing.net Subject: Re: [PHC] Makwa is broken given p and q -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 09/11/2014 03:21 AM, Steve Thomas wrote: >> 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. 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 governments. >>> >>> 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 problem. Bill -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQIcBAEBAgAGBQJUEX85AAoJEAcQZQdOpZUZl6MP/2SrtigwOz1a1DdpBlxYPuq8 8hiwCy4B7kUAbAdITJqnfKORPDQKFgo3d1FhCZO2W5m69VuAKSqPv4IxRMGe6XFj SIac9Umh+vCZUQMAhsGK9oWgO+Jykaxrpq3MtFJ8QYmYGx3vKyb5t1uO9ouPkivV t82qMx4Xx/AsoNtzfDBP62tLNmL/bnSQRMc8oIUz+jMCjbHqKSsuUgzn3Z+Q3Dfz KPYTHqRYvxt7uEYT2Fn/9xH/CEeh6cEmjicFfag0Zzrccsgl5+UP7Qorm5N4fpcO HCB78/Okhi8NxYVURXcctYbq8ABlH9/zN/ruw0vyC5ALEQY+tfrSLwW+AZcPXxmN JgG1+y+L5fziCIzF/OUclduumvlsPswMXJKM8MLHpxBURHzLDlgrdPO9Dg1ihagG 21b9ie1I7TczNsvXJ1ottDyy1ovQp/29sLwRtWXvzpKJTR15lAI3sfpp2CpEUPds WtYbs+E7nOs6Fn0TWwICFV5iHCIiuOp+h4O0FiuByxeIHteeBu/9utSLCk9QFan4 4lJeyAGG+QSDmJ3MAugOFxR5xQuNPraOvdbMhS0yVfK8o5IQcfZ0VI5JN51ZUxeX APwgEAHFuxD9SnEFE978i1aijdei7vlXKlp4K/8+eCca9/WDjfkji9wuQimbNdZQ nvxlo6VGVJtnbG8s/fRf =UR0z -----END PGP SIGNATURE-----
Powered by blists - more mailing lists