[Cryptography] Key meshing (Re: [Crypto-practicum] Retire all 64-bit block ciphers.)

[Jerry Leichter]

> Regarding the discussion of the Sweet32 attack, it's worth mentioning that 
> there is a specification of so called key meshing for the Russian GOST cipher (which has 64-bit block as well).
> Key meshing is a procedure of a predictable change of the current key after processing an certain amount of data. 
> It is described in RFC 4357, Section 2.3 (https://tools.ietf.org/html/rfc4357#section-2.3 <https://tools.ietf.org/html/rfc4357#section-2.3>). 
> 
> This key meshing defends against any attack that uses a big portion of data encrypted with the same key.
> 
> May be it is useful to specify the similar procedure for modern ciphers too.
What I find most interesting is that the procedure as specified is run so often:  Every 1024 octets.  One wonders what class of attacks the designers were concerned about.  The text says it's to deal with "timing and EMI analysis"; the connection between that and frequent rekeying is unclear.

Looking more closely at the specified meshing algorithm:  If someone mounts a full key recovery attack against block n, they can readily compute all past and future keys, as K[i+1] is the decryption of a fixed, known constant with K[i].  If they also then recover any IV, they can similarly recover all IV's.  This makes the attack model even more obscure.

The cost is substantial:  An extra two cipher operations and a rekeying every 16 blocks.  And you lose the ability to parallelize encryption and decryption and the ability to resynchronize if blocks are lost (not that the latter is available in most good modes anyway; it's very hazardous, since the loss might be the result of a deliberate attack).

Back when DES was the only algorithm out there, I (and many others no doubt) thought about using something of this form to effectively double the key size:  Use two DES keys, with one used to periodically create a new block key from the other.  (This doesn't add nearly as much keying material as you'd naively expect; hardly worth the cost.  You can think of DESX as a much cheaper mechanism that actually does help.)

A more modern analogue might be to use a tweakable cipher and change the tweak frequently.
                                                        -- Jerry


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160829/fa7bb6f2/attachment.html>