phc-discussions - Pebble placement complexity

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

Message-ID: <CAOLP8p7OfXL7U7SE0CgVSUeyWBif6Hu12A3DgwEK5oH1N5b97Q@mail.gmail.com>
Date: Sat, 1 Feb 2014 18:34:07 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Pebble placement complexity

II strongly suspect that it is NP-Complete to find an optimal pebble
placement of p pebbles on a DAG G with n nodes to minimize average
recomputation costs when node values are read randomly, forcing an
attacker to produce them.  Does anyone know if this is the case?  I
feel like I'm close to finding an embedding for Boolean SAT in optimal
pebble placement.

If I can show optimal pebble placement to minimize recomputations
required when doing password dependent memory reads is NP-hard, then I
can write optimization algorithms like I do all the time for a living,
and they become evidence that attackers cannot substantially improve
on my results.  Simulated annealing, for example, when done right, can
be used to find a pretty good pebble placement on small DAGs, and we
can project expected results to large DAGs.

To state the problem precisely, we have a fixed DAG of n nodes with
fan-out degree 2.  An attacker can place p pebbles wherever he likes,
and I can then compute based on that placement an average
recomputation penalty, which is the total of the sizes of the
non-pebbled sub-DAGs feeding each non-pebbled node, divided by the
number of nodes.  NoelKDF's second loop was designed to maximize that
number.

Bill