phc-discussions - Re: Some KDF stumbling blocks, plus Common

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: <loom.20141216T165627-607@post.gmane.org>
Date: Wed, 17 Dec 2014 14:22:00 +0000 (UTC)
From: Adam Back <adam@...herspace.org>
To: discussions@...sword-hashing.net
Subject: Re: Some KDF stumbling blocks, plus Common

Thomas Pornin <pornin@...> writes:
> [storing 300 * 2048-bit values allows faster nonce generation]
> [...]
> With 300 base pairs, cost is about 300 multiplications on average, i.e.
> six times better than the "information theoretic" method, and 15 to 20
> times faster than the g^b/y^b method with a sliding window
> exponentiation. Depending on the available resources (both in CPU and
> storage size), that kind of speed-up may or may not matter.

I suppose also if each blinding factor is were moderately expensive 
relative to the device CPU then computing 300 of them at setup
might be a noticeable delay.

Except for embedded devices its probably fairly cheap on a modern 
smart-phone or ARM based device to just do it the straight forward way.  
Your optimisation is reasonable for computational security, and I've seen 
analogous used before eg the Jacobsson paper Icited earlier in the thread, 
I just had not focussed on optimisation..

Information theoretic security is normally more valued for privacy in
the long-term view.  As the blockchain is a matter of long-term public
record, and if someone has a brainwallet then the private key is the
(KDF stretched) password.  Using info-theoretic security, with
properly whitened CRNG, at no time in the far future even with crazy
amounts of computing power or hypothetical 1000-bit quantum computers,
can the attacker who has recorded derivations make any progress at all
on narrowing which coins were spent by which user.

Cracking old ECDSA keys is of no consequence, as by then those keys
will be spent and the signature replaced with a new quantum resistant
scheme in the direction of the work on post-quantum cryptography.

Adam