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: <CALW8-7LTO_nWbGj7YPstQjWCSw5Sqx-YidjAQp=g4U9wkZoo0w@mail.gmail.com>
Date: Mon, 15 Sep 2014 14:19:33 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] A review per day - Catena

It is somewhat strange to not take into account the existing third-party
cryptanalysis when doing such a review. For example

On Sat, Sep 13, 2014 at 7:32 PM, Bill Cox <waywardgeek@...hershed.org>
wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>
> It remains to be seen if there is an effective TMTO attack against
> Catena.  Using even 1 fewer memory locations increases recomputations
> considerably.  However, the defense increases somewhat slowly, and by
> a 1/8 memory attack (compared to the 1/4 that Catena starts with),
> Catena starts losing against other algorithms in my pebbling attacks.
>

This paragraph:
 - ignores the attacks mounted by the Catena designers;
 - ignores the lower bound proof given in the submission;
 - ignores the fact that the proof has a mistake (acknowledged by the
designers);
 - ignores the tradeoff attacks found by our team (also acknowledged by the
designers and verified by other people in the mailing list).

It also does not tell us what are the penalties (found by the author or
someone else) for running Catena with 1/2, 1/4, 1/8 of the memory or
whatever.

>
> ASIC Defense
> - ------------
>
>
The ASIC discussion also:
 - does not introduce any reference attacker's platform, where the cost is
computed;
 - ignores the existing SHA-512 and Blake-512 ASIC implementation, their
latencies, voltages, frequencies etc. compared to that of DRAM or SRAM
designs available on the market or in the development.

> Contrary to what
> has been posted in the discussion forum, a TMTO against Catena will
> almost certainly *increase* power, rather than decrease.
>
>
Whereas the other statements can be considered as a matter of taste, this
one can be verified rather easily. Let us take the platform on where the
exist SHA-512 implementations as the reference platform: (
http://www.iis.ee.ethz.ch/~sha3/ethz_gmu_sha3.pdf )
65nm, 1.08 V, 316 MHz.

The SHA-512 compression function has latency 65 cycles and consumes 9 mW at
this platform.
As a result, 2^20 calls to the SHA-512 compression function would take
9/(316/65) = 1.9mJ.

Catena-3 with 128 MB of memory would need 2^21 64-byte SHA blocks, so 2^23
compression function calls, i.e. 15mJ within 8/(316/65)=1.5 seconds. Our
tradeoffs have computational penalty 3.75q for the memory reduction by q,
so, for instance, running it with 16 MB of memory would require 30x more
energy, or 450mJ within the same 1.5 seconds.

The memory will consume far larger. The 128-MB Catena-3 reads/writes 768 MB
of data from/to RAM, and 1.5 GB in tradeoffs. If we consider GDDR5,
advocated by Bill, and scale it down to 300 MHz, it would at least consume
0.5W, so its energy consumption would be 750mJ, and 94mJ for 16MB.

Therefore, the attacker will reduce his costs even if the memory is reduced
8-fold. And we have not counted the retention energy yet, as it will raise
the tradeoff efficiency even more.

Content of type "text/html" skipped