[cryptography] A small public key encryption program

Solar Designer solar at openwall.com
Mon Aug 6 21:34:54 EDT 2012


Elias -

On Tue, Aug 07, 2012 at 03:36:32AM +0400, Solar Designer wrote:
> 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).

Here's an attack:

For each in a set of passphrases to be tested, compute the KDF value
assuming that its expensive component returned 0, and test the keys.
If no match found, assume that the expensive component returned 1 and
repeat - and so on until either the key is found (which may be
double-checked by computing the KDF fully) or the set of possible return
values from the expensive component is exhausted.

In your example, with the expensive component returning a 32-bit value,
this attack will succeed after testing 2**31 possible values on average
when there is in fact a correct passphrase among those tested, and it
will fail after testing 2**32 possible values otherwise.

This puts an upper bound on the cost, regardless of the (possibly
configurable) cost of the expensive component.  It also lets an attacker
avoid the memory cost altogether (but pay for this with the processing
cost of the algorithm above).  The latter is fine if you're only
concerned about area*time cost rather than also about preventing certain
devices (such as GPUs) from being used for the attack efficiently.
In fact, scrypt deliberately allows for a similar tradeoff:

http://www.openwall.com/lists/crypt-dev/2011/07/01/2

Overall, I think that having a narrower-pipe expensive component in a
KDF might be OK (especially if there are multiple invocations of such
components per a full KDF computation), but 32 bits for the only
expensive component is likely too narrow for some otherwise reasonable
uses (cost settings).

Alexander



More information about the cryptography mailing list