### Re: [Cryptography] Key stretching

```On 10/11/2013 11:22 AM, Jerry Leichter wrote:

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.

There is a completely impractical solution for this which is applicable
in a very few ridiculously constrained situations.  Brute force can
be countered, in very limited circumstances, by brute bandwidth.

You have to use random salt sufficient to ensure that all possible
decryptions of messages transmitted using the insufficient key or
insecure cipher are equally valid.

Unfortunately, this requirement is cumulative for *ALL* messages that
you encrypt using the key, and becomes flatly impossible if the total
amount of ciphertext you're trying to protect with that key is greater
than a very few bits.

So, if you have a codebook that allows you to transmit one of 128 pre-
selected messages (7 bits each) you could use a very short key or an
insecure cipher about five times, attaching (2^35)/5 bits of salt to
each message, to achieve security against brute-force attacks.  At
that point your opponent sees all possible decryptions as equally
likely with at least one possible key that gives each of the possible
total combinations of decryptions (approximately; about 1/(2^k) of the
total number of possible decryptions will be left out, where k is the
size of your actual too-short key).

The bandwidth required is utterly ridiculous, but you can get
security on a few very short messages, assuming there's no identifiable
pattern in your salt.

Unfortunately, you cannot use this to leverage secure transmission of
keys, since whatever key larger than the initial key you transmit
using this scheme, once your opponent has ciphertext transmitted
using the longer key, the brute-force method against the possibilities
for your initial short key becomes applicable to that ciphertext.

Bear

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

```

### Re: [Cryptography] Key stretching

```
On 10/11/13 7:34 PM, Peter Gutmann wrote:

Phillip Hallam-Baker hal...@gmail.com writes:

Quick question, anyone got a good scheme for key stretching?

http://lmgtfy.com/?q=hkdfl=1

Yeah, that's a weaker simplification of the method I've always
advocated, stopping the hash function before the final
MD-strengthing and repeating the input, only doing the
MD-strengthening for the last step for each key.  I used this in
many of my specifications.

In essence, the MD-strengthening counter is the same as the 0xnn
counter they used, although longer and stronger.

This assures there are no releated key attacks, as the internal
chaining variables aren't exposed.

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

```

### Re: [Cryptography] Key stretching

```This is a job for a key derivation function or a cryptographic prng.  I would
use CTR-DRBG from 800-90 with AES256.  Or the extract-then-expand KDF based on
HMAC-SHA512.

--John
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

```

### Re: [Cryptography] Key stretching

```On Oct 11, 2013, at 11:26 AM, Phillip Hallam-Baker hal...@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

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

```

### Re: [Cryptography] Key stretching

```Phillip Hallam-Baker hal...@gmail.com writes:

Quick question, anyone got a good scheme for key stretching?

http://lmgtfy.com/?q=hkdfl=1

Peter :-).
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

```