[Cryptography] Key stretching

Ray Dillinger bear at sonic.net
Sun Oct 13 12:55:50 EDT 2013


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



More information about the cryptography mailing list