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  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: Sun, 19 Apr 2015 01:57:40 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: variable TMTO factor for average-aware TMTO (was: "Attack on the iterative compression function")

Dmitry,

On Sat, Apr 18, 2015 at 11:42:06PM +0300, Solar Designer wrote:
[...]
> how the average (rather than peak) memory usage is reduced with TMTO.
> The recomputation depth grows the longer the algorithm runs, so the
> average (across the running time) is skewed towards a higher portion of
> the TMTO'd memory size.

BTW, a more efficient TMTO attack (not just on the possible iterative
component, but in general) might involve the TMTO factor changing during
the attack.

For example, target 1/3 memory during the memory filling phase (possibly
for roughly 1/4 average) and 1/4 memory for the subsequent processing.
That way, average will be closer to 1/4 all the time, and you might pack
more such TMTO'd parallel instances in the same total amount of memory.

Alternatively, on the contrary increase the amount of memory for further
processing to mitigate the recomputation tree depth growth.  With
optimal phase shifts between the parallel TMTO'd instances, this too
might help increase the total number of instances.

Switching the TMTO factor may have a cost of its own, but not always.
If you choose to increase the amount of memory e.g. between yescrypt's
SMix1 and SMix2, you may simply let SMix2 perform its writes to the
extra portion of memory.  In fact, I did something like this in my old
sim-tmto.c, where I use TMTO factor of 5 for SMix1 and 2 for SMix2's
extra writes, for a total of 1/5+1/2 = 7/10 of non-TMTO memory (plus
indices).  That exact attack doesn't apply to the current yescrypt,
as previously discussed (because sim-tmto.c assumes original scrypt's
SMix1).  But it shows that the approach with variable TMTO factor is
potentially viable in general.

Alexander

Powered by blists - more mailing lists