phc-discussions - Re: [PHC] A review per day

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]

Message-ID: <5a7558c3-0566-422e-8ff0-75f12afd792b@email.android.com>
Date: Thu, 04 Sep 2014 09:07:27 -0400
From: waywardgeek@...hershed.org
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - skipping Makwa

I would massively pipeline a multiplier for this circuit. With a 4096 by 4096 multiplier I might have up to 8192 pipeline stages. This is a much stronger attack than the one on bcrypt.  How fast can a CPU do a large multiply like this?

This attack will spend far less power per multiply.  However in reality this attack will be limited by how quickly power can be sucked out of the ASIC.  I would be tempted to consider a booth multiplier and dynamic logic to lower power and size. Regardless, it will still produce one multiply result per clock. It should be built in a low power process so it will not run as fast as your CPU.   The better the geometry the better the power.

-------- Original Message --------
From: Thomas Pornin <pornin@...et.org>
Sent: September 4, 2014 7:21:35 AM EDT
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - skipping Makwa

On Thu, Sep 04, 2014 at 06:51:11AM -0400, Bill Cox wrote:
> However, Makwa does not replace either bcrypt or Scrypt.

Actually I'd love to see some ASIC comparisons between bcrypt and Makwa.
Bcrypt needs a 4 kB array, which means (roughly) 200000 transistors
(with SRAM). I am not sure how fast could a Makwa ASIC go, if it has
200000 transistors to work with (mostly to store some fast-multiplier
circuits); in other words, while I am quite convinced that an
ASIC-wielding attacker will get more Makwa per second for a given budget
than a CPU-based attacker, I am not sure that the boost will be greater
than what the same attacker could do against bcrypt.

In that sense, it is possible that Makwa actually fares no worse than
bcrypt against ASIC-powered attackers. This requires some investigations
(by people who grasp the particulars of ASIC design better than me).

Similarly, while I initially assumed that a GPU should also be quite
good at doing the kind of computations that Makwa relies on, benchmarks
I found (about RSA) seem to indicate that the picture is not that clear:
GPU being on par with CPU, but not substantially better.

The point of Makwa is to support delegation, but it is not inconceivable
that even without delegation, it still stands its ground decently,
sufficiently to be envisioned as a replacement for bcrypt even on
stand-alone systems. That's why I would really like to see people trying
to benchmark it under these terms as well.(*)

	--Thomas Pornin

(*) I expect Makwa to perform poorly on pure 32-bit systems, because
that's what you get with RSA. Big-integer multiplications really love
64x64->128 bits multiplications.

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.
Content of type "text/html" skipped