[cryptography] A small public key encryption program

Solar Designer solar at openwall.com
Mon Aug 6 19:36:32 EDT 2012


Hi,

On Mon, Aug 06, 2012 at 11:27:45PM +0300, Elias Yarrkov wrote:
> I use a custom KDF. I intend to write about this manner of constructing KDFs
> later. The goal is to cause a high area*time cost for massively parallel brute
> force via ASIC, similar to scrypt.

Please do write about this.

It is curious how you deliberately use a narrow pipe for the expensive
component of the KDF (but not for the KDF as a whole).  You'd need to
include some explanation/proof that this is safe (given certain threat
models).

Also, I am curious how you derive your area*time cost estimate, and
whether you considered other metrics of cost (those more relevant for
non-ASIC attacks).  Your zen32() does use RAM, but it only uses a tiny
fraction of the CPU's logic (little more than a 32-bit ALU - no SIMD),
which is suboptimal against attacks with CPUs.  It looks like
SIMD-enhanced attacks won't even require scatter/gather addressing
(which, by the way, might become widely available, such as with Intel
MIC) since your array indices are not data-dependent.  Also, such
attacks would use the available memory bandwidth more fully.  When you
make a 32-bit memory access, an entire cache line is fetched anyway, but
your second loop only uses the 32-bit value.  With SIMD or/and similar
grouping of memory accesses for multiple keys, the entire cache line
would be actually made use of.

In general, your algorithm appears to be memory bandwidth bound, whereas
scrypt avoids that (by including some non-trivial computation) - it is
memory-hard, but not memory bandwidth bound.

With your algorithm, an attacker with the same amount of RAM, but with
higher memory bandwidth for random 32-bit accesses (such as with many
independent 32-bit buses), would have an advantage.  This is probably
not what you wanted.

It is entirely possible that I am missing something or/and that I missed
a more serious attack.

Thanks,

Alexander



More information about the cryptography mailing list