Re: Time Invariant String Comparison

[Andres Perera <andres.p@...>]

On Sat, Jan 25, 2014 at 1:42 AM, William Ahern
<william@25thandclement.com> wrote:
> On Mon, Jan 20, 2014 at 02:40:35AM -0430, Andres Perera wrote:
> <snip>
>> But real world tools employ KDF-augmented password over keys as a
>> two-factor auth mechanism, in essence recognizing that the two
>> complement rather than replace each other. See TrueCrypt, OpenBSD
>> CRYPTO discipline for softraid, and the previously cited OpenBSD SSH.
>>
>
> Once upon a time using ciphers in CBC mode was considered the gold standard.
> That was before padding attacks were realized.
>
> Key stretching is slightly different because nobody seriously argues that
> it's generically secure--like they did CBC. It's highly dependent on
> context. It's more a soft measure than a hard measure. By soft measure I
> mean things like password entropy estimators or CAPTCHA barriers. These
> things aren't in the same domain as hard cryptographic primitives.

We are sorting these items; CBC, CAPTCHA, password evaluators, and
KDF, into groups of "{soft,hard} measures" and "generically secure"
without discussing their individual purposes.

KDF was designed to grant additional protection to the original key,
not streams or blocks encrypted with a cipher initialized by KDF
output. In the latter case, you may still employ KDF when
reutilization of the key and precomputed attacks are concerns.

During this conversation, an equation explaining the O() increase of
retrieving the original key was presented.

The equation was dismissed because it was supposedly inadequate for
discussing the asymptotic costs of cracking a password, even though
it's the *parting* complexity expression, and the only constant is the
base of the exponentiation.

Do CAPTCHA and password evaluators make deterministic guarantees?


>
> If hard cryptographic primitives with generic, rigorous proofs can fail, why
> should I put much stock in soft measures? Especially ones that depend on
> highly perishable assumptions about how much compute power my attacker has?

The failure would be specific to the block cipher.

[...]

>
> Here's a blurb from the scrypt webpage:
>
>         We estimate that on modern (2009) hardware, if 5 seconds are spent
>         computing a derived key, the cost of a hardware brute-force attack
>         against scrypt is roughly 4000 times greater than the cost of a
>         similar attack against bcrypt (to find the same password), and 20000
>         times greater than a similar attack against PBKDF2.
>
> Who in their right mind would allow their website authentication system to
> spend 5 seconds (an eternity!) hogging a CPU? Especially when you could
> instead mandate passwords just three or four characters longer for the same
> benefit and without crippling your throughput?

Such desicions should be made with usage statistics in hand. The
machines I've configured with /etc/passwd bcrypt hashes handle less
than 100 logins/minute.

>
> Anything over a millisecond is already too long for real websites. At that
> point, the differential between scrypt and braindead SHA256+salt is so low
> in real terms that you've hardly inconvenienced an attacker doing a
> dictionary attack on user passwords. On a database he _already_ stole, mind
> you, which should be your real concern!

Actually, SHA256+salt = 2^(strlen(pass)*8) for every salt, assuming
that you know how the salt is concatenated. Your comparison is
entirely inadequate because salt is about making pre-computed attacks
take infeasible amounts of space, whereas KDF does that *in addition*
to its main purpose.

>
>