<div dir="ltr"><div>Dear Jerry,</div><div><br></div><div><br></div><div>Thank you for your questions. </div><div><br></div><div>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.</div><div><br></div><div>Our results on this topic are presented in the preprint <a href="http://eprint.iacr.org/2016/628">http://eprint.iacr.org/2016/628</a>, 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.</div><div><br></div><div>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.</div><div><br></div><div><br></div><div>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.</div><div><br></div><div>I'd be glad to answer all your questions about the construction, the analysis and the applications.</div><div><br></div><div>Thank you again for your interest.</div><div><br></div><div>Best regards,</div><div>Stanislav V. Smyshlyaev, Ph.D.,</div><div>Head of Information Security Department,</div><div>CryptoPro LLC</div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><p><font color="#1f497d">С уважением,</font></p><p><font color="#1f497d">Станислав Смышляев, к.ф.-м.н.,</font></p><p><font color="#1f497d">Начальник отдела защиты информации </font></p><p><font color="#1f497d">ООО «КРИПТО-ПРО»</font></p><div><br></div></div></div></div>
<br><div class="gmail_quote">2016-08-29 18:06 GMT+04:00 Dmitry Belyavsky <span dir="ltr"><<a href="mailto:beldmit@gmail.com" target="_blank">beldmit@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Dear Jerry,<div class="gmail_extra"><br><div class="gmail_quote">On Mon, Aug 29, 2016 at 12:59 PM, Jerry Leichter <span dir="ltr"><<a href="mailto:leichter@lrw.com" target="_blank">leichter@lrw.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><span><blockquote type="cite"><div dir="ltr"><div>Regarding the discussion of the Sweet32 attack, it's worth mentioning that </div><div>there is a specification of so called key meshing for the Russian GOST cipher (which has 64-bit block as well).</div><div>Key meshing is a procedure of a predictable change of the current key after processing an certain amount of data. </div><div>It is described in RFC 4357, Section 2.3 (<a href="https://tools.ietf.org/html/rfc4357#section-2.3" target="_blank">https://tools.ietf.org/html/r<wbr>fc4357#section-2.3</a>). </div><div><br></div><div>This key meshing defends against any attack that uses a big portion of data encrypted with the same key.</div><div><br></div><div>May be it is useful to specify the similar procedure for modern ciphers too.</div></div></blockquote></span>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.</div></div></blockquote><div><br></div><div>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.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><br></div><div>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.</div><div><br></div><div>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).</div></div></blockquote><div><br></div><div>Also there are some problems with DTLS. We are currently working on solving them.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><br></div><div><div>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.)</div><div><br></div></div><div>A more modern analogue might be to use a tweakable cipher and change the tweak frequently.</div><span><font color="#888888"><div><div><br></div></div></font></span></div></blockquote><div> </div><div>There can be a lot of rekeying algorithms, but the idea of using any of them seems to be present only in academic papers.</div></div><span class="HOEnZb"><font color="#888888"><br clear="all"><div><br></div>-- <br><div data-smartmail="gmail_signature">SY, Dmitry Belyavsky</div>
</font></span></div></div>
<br>______________________________<wbr>_________________<br>
The cryptography mailing list<br>
<a href="mailto:cryptography@metzdowd.com">cryptography@metzdowd.com</a><br>
<a href="http://www.metzdowd.com/mailman/listinfo/cryptography" rel="noreferrer" target="_blank">http://www.metzdowd.com/<wbr>mailman/listinfo/cryptography</a><br></blockquote></div><br></div>