Re: Time Invariant String Comparison

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

On Mon, Jan 20, 2014 at 1:20 AM, William Ahern
<william@25thandclement.com> wrote:
> On Mon, Jan 20, 2014 at 12:08:20AM -0430, Andres Perera wrote:
>> On Sun, Jan 19, 2014 at 7:37 PM, William Ahern
>> <william@25thandclement.com> wrote:
>>
>> [...]
>>
>> > The marginal security is so low, that's the kind of thing you need to on a
>> > regular basis to make them worthwhile. That's not the kind of thing you need
>> > to do with traditional cryptographic primitives. My 2048-bit RSA key from
>> > 2000 is in real-terms just as safe today as it was 14 years ago. But a
>> > PBKDF2 round variable would be laughable after 14 years.
>>
>> You could even encrypt files with your RSA key! You wouldn't do that
>> with bcrypt output, however, because you negate the whole benefit of
>> recursive hashing: the attacker only needs to find the n-1th
>> intermediate form to crack the file.
>>
>> Would you consider, then, login authentication distinct from general
>> decryption?
>>
>> It's almost as if bcrypt and the like were designed for distinct purposes.
>
> I think the fundamental problem is human-useable passwords. Solutions like
> bcrypt or scrypt are trying to salvage a doomed situation; namely, improving
> the real-world survivability of inherently weak passwords, whether used for
> authentication or encryption. bcrypt and especially scrypt are smart in
> trying to prevent any shortcuts with brute force implementations, but ASIC
> shortcuts aren't the real problem.

Alas, I've made progress in persuading you present your actual
reservation with passwords (not even KDF).

>From the ssh-keygen manual page[0]:

" -a rounds

When saving a new-format private key (i.e. an ed25519 key or any
SSH protocol 2 key when the -o flag is set), this option
specifies the number of KDF (key derivation function) rounds
used.  Higher numbers result in slower passphrase verification
and increased resistance to brute-force password cracking (should
the keys be stolen)."

Your argument has nothing to do with exponential vs linear growth, and
your argument has nothing to do with attacker/user cost difference,
either.

Your argument is that private keys should be protected by private
keys, ad nauseum, or that the user memorize a password with the same
entropy as a private key.

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.

[0] http://www.openbsd.org/cgi-bin/man.cgi?query=ssh-keygen

>
> The amount of entropy in human-useable 6-character or 8-character passwords
> is so low that it doesn't really matter if something like scrypt makes it a
> million times harder to compute each hash--although if I understand the
> original description from the scrypt paper, it's more like roughly only
> 260000 times harder than SHA-2 based on the original parameters.
>
> Note that there purportedly already are scrypt machines (for litecoin) which
> can do 25 million scrypt hashes per second (albeit with an r parameter value
> of 1, so knock it down by some small'ish fixed constant).
>
> A weak password will still be a weak password with or without scrypt.
>
> If you move to something like HOTP systems, the exponential increase in
> search space far exceeds the linear (by comparison) attack cost that scrypt
> buys you.
>
> Solutions like scrypt do make you less vulnerable than the next guy. And
> there's something to be said for that. But that's perilously close to the
> cryptographic equivalent of bike shedding. Or even "you can never go wrong
> by choosing Microsoft" as a contingent defense for when things break.
>
>