phc-discussions - RE: [PHC] Initial multiply-compute-hardened Catena-3 benchmark

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-next>] [day] [month] [year] [list]

Message-ID: <99a75bf65d5c1be6f4d671bc179b4204.squirrel@webmail.larc.usp.br>
Date: Thu, 23 Jan 2014 20:51:45 -0200 (BRDT)
From: "Marcos Simplicio" <mjunior@...c.usp.br>
To: discussions@...sword-hashing.net
Cc: "waywardgeek@...il.com" <waywardgeek@...il.com>
Subject: RE: [PHC] Initial multiply-compute-hardened Catena-3 benchmark

Hi.

> Assume the attacker is able to rent a virtual machine sharing the same CPU
> as the defender. By observing his own perceived cache latency carefully,
> he is able to learn what memory locations are accessed by the defender
> during the hashing of a specific user's password. This has been
> demonstrated possible in practice.

That is a very interesting information. Could you provide the source for
future reference? In Catena's paper, they only mention "At the current
point of time, our cache-timing attacks are theoretical."

Or the demonstrations you are referring to are meant for other primitives?
I could find some discussions for AES (against --
http://cseweb.ucsd.edu/~hovav/dist/aes_cache.pdf -- and pro --
http://research.microsoft.com/pubs/64024/aes-timing.pdf), but nothing on
KDFs.

/Marcos.

>
> Now say the PHC algorithm imposes memory-latency hardness by using the
> supplied password to generate a seed with which to initialize a PRNG
> sequence to pick memory addresses within a large memory block. Going by
> the general rule that 50% of users choose one of the 10,000 most common
> passwords, the attacker only needs to learn just one or two cache line
> addresses in order to have a better than 50% chance of guessing the user's
> password on the first try.
>
> - Marsh
>
> -----Original Message-----
> From: Dennis E. Hamilton [mailto:dennis.hamilton@....org]
> Sent: Thursday, January 23, 2014 12:56 PM
> To: discussions@...sword-hashing.net
> Cc: waywardgeek@...il.com
> Subject: RE: [PHC] Initial multiply-compute-hardened Catena-3 benchmark
>
> I notice that "timing attack" is used here yet I don't think the usual use
> of that term seems to apply.
>
> Do you really mean that there is a feasible way to mitigate a work factor
> that a particular measure imposes?
>
> Maybe those should be "speed-up" or "accelerator" attacks?
>
> If you do mean "timing attack," please say more about what you are
> thinking of.
>
>  - Dennis
>
> -----Original Message-----
> From: Bill Cox [mailto:waywardgeek@...il.com]
> Sent: Thursday, January 23, 2014 11:10
> To: discussions@...sword-hashing.net
> Subject: [PHC] Initial multiply-compute-hardened Catena-3 benchmark
>
> I've signed in a branch of Catena that replaces the hashing function with
> a simple multiply, OR, and ADD.  I also made it hash blocks of
> 4096 bytes of memory at once rather than 64.  The result runs 13X faster,
> filling 1GB of memory in 1.37 seconds on a single thread.
>
> In comparison, NoelKDF hashes 1GB in 0.42 seconds on 1 thread, or 3.2X
> faster.  However, there's a TMTO attack against NoelKDF that requires
> almost the same runtime, but only uses 0.5GB.  There is no such attack
> against Catena-3, IMO.
>
> Taking that into account, Catena-3 takes only about 40% longer to hash the
> same memory as an attacker optimized version of NoelKDF.  I'm leaning
> towards Catena-3 now, for timing attack resistance, at least if we have an
> option for a fast hash in the inner loop.
>
> Bill
>
>