[Cryptography] Key stretching

[Jerry Leichter]

On Oct 11, 2013, at 11:26 AM, Phillip Hallam-Baker <hallam at gmail.com> wrote:
> Quick question, anyone got a good scheme for key stretching?
> 
> I have this scheme for managing private keys that involves storing them as encrypted PKCS#8 blobs in the cloud.
> 
> AES128 seems a little on the weak side for this but there are (rare) circumstances where a user is going to need to type in the key for recovery purposes so I don't want more than 128 bits of key to type in (I am betting that 128 bits is going to be sufficient to the end of Moore's law).
> 
> 
> So the answer is to use AES 256 and stretch the key, but how? I could just repeat the key:
> 
> K = k + k
> 
> Related key attacks make me a little nervous though. Maybe:
The related key attacks out there require keys that differ in a couple of bits.  If k and k' aren't related, k+k and k'+k' won't be either.

> K = (k + 01234567) XOR SHA512 (k)
Let's step back a moment and think about attacks:

1.  Brute force.  No public key-stretching algorithm can help, since the attacker will brute-force the k's, computing the corresponding K's as he goes.
2.  Analytic attack against AES128 that doesn't extend, in general, to AES256.  Without knowing the nature of the attack, it's impossible to estimate whether knowing that the key has some particular form would allow the attack to extend. If so ... what forms?
3.  Analytic attack against AES256.  A recognizable form for keys - e.g., k+k - might conceivably help, but it seems like a minor thing.

Realistically, k+k, or k padded with 0's, or SHA256(k), are probably equally strong except under any attacks specifically concocted to target them (e.g., suppose it turns out that there just happens to be an analytic attack against AES256 for keys with more than 3/4's of the bits equal to 0).

Since you're describing a situation in which performance is not an issue, you might as well use SHA256(k) - whitening the key can't hurt.

                                                        -- Jerry