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

[Stanislav V. Smyshlyaev]

Dear Jerry,


Thank you for your questions.

The reason for using key meshing is the increase of the limits on the total
size of plaintext that is allowed to be encrypted in a specific mode due to
1) evident combinatorial reasons (birthday paradox etc), 2) side-channel
attacks using leakages that occur when you use a key (e.g. when you xor
your key with some data you always have a signal on a bus that induces a
leakage - the more you use the key, the more you leak about it) and 3)
classical cryptanalysis techniques such as linear cryptanalysis that
require certain material to be applicable.

Our results on this topic are presented in the preprint
http://eprint.iacr.org/2016/628, where it is shown that the bounds on total
material that can be encrypted in CTR mode increase quadratically in
classical models. Maybe you will find them interesting and answering your
questions.

About "so often" - the change is made during each session (for every new
start with a fresh IV), so the total material that is actually encrypted on
the first key is 1024*number of starts. And this can be a reasonable number
if you have to deal with powerful adversaries using side-channels. But the
constant (as "1024") depends on your adversary model.


Your considerations about the possibility of learning all following keys
when you know a particular one are right - but that's a completely
different task that can be solved by using key trees methods, KDFs from a
single master secret etc.

I'd be glad to answer all your questions about the construction, the
analysis and the applications.

Thank you again for your interest.

Best regards,
Stanislav V. Smyshlyaev, Ph.D.,
Head of Information Security Department,
CryptoPro LLC

С уважением,

Станислав Смышляев, к.ф.-м.н.,

Начальник отдела защиты информации

ООО «КРИПТО-ПРО»


2016-08-29 18:06 GMT+04:00 Dmitry Belyavsky <beldmit at gmail.com>:

> Dear Jerry,
>
> On Mon, Aug 29, 2016 at 12:59 PM, Jerry Leichter <leichter at lrw.com> wrote:
>
>> 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/r
>> fc4357#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.
>>
>
> I think, the designers were just paranoid ones :-). They were paranoid
> enough to specify 256-bit key in 1989, so the key meshing does not seem to
> be something extra in this case.
>
>
>> 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).
>>
>
> Also there are some problems with DTLS. We are currently working on
> solving them.
>
>
>>
>> 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.
>>
>>
> There can be a lot of rekeying algorithms, but the idea of using any of
> them seems to be present only in academic papers.
>
>
> --
> SY, Dmitry Belyavsky
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160830/ce07e112/attachment.html>