crypt-dev - Re: Password Scrambling

Openwall GNU/*/Linux 3.0 - a small security-enhanced Linux distro for servers

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sat, 19 Jan 2013 10:18:59 +0100
From: Christian Forler <christian.forler@...-weimar.de>
To: crypt-dev@...ts.openwall.com
Subject: Re: Password Scrambling

Am 19.01.2013 09:39, schrieb Colin Percival:

>> Of course, I'm familiar with scrypt. You did a great job. Your idea of
>> using a memory-hard algorithm was beautiful.
> 
> Note that it needs to be *sequential* memory-hard, not just memory-hard -- it's
> easy to construct functions which need a lot of RAM to compute, but much harder
> to construct functions which require a lot of RAM *and* cannot be sped up by
> using O(N) CPU.  In hardware, of course, extra CPUs are "free".

In the password recovery scenario, an adversary A tries to compute as
many password candidates as possible in a given time t.

Let's say A has access to multiple CPUs. Then there are two extreme cases:

1) A can test one candidate per CPU in parallel or
2) A can parallelize the KDF function and test the candidates in a
sequential order.

In both cases, I would assume that the number of computed password
candidates is similar apart a constant factor c. Or is this not the case?

Best regards,
Christian