<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Sun, Feb 7, 2016 at 1:14 PM, Ray Dillinger <span dir="ltr"><<a href="mailto:bear@sonic.net" target="_blank">bear@sonic.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><br>
<br>
On 02/06/2016 06:29 AM, Henry Baker wrote:<br>
<br>
> Consequently, you are cordially invited to submit a proposal for a block cipher that :<br>
> Works on block sizes of 1 kbytes, 4 kbytes, 16 kbytes and 64 kbytes. Bonus points for ciphers that work on an arbitrary block size.<br>
> Use a 64 kbyte key.<br>
> Fits In Head<br>
<br>
</span>I have sometimes thought it would be worthwhile to create a block<br>
cipher that could be used on very large blocks. The 64-kbyte<br>
block requirement is actually justified in some applications.<br></blockquote><div><br></div><div>Is this because we can do faster hashing/encryption per byte on very large blocks?  This turns out to be true, but AFAIK, it is not a well known or understood issue.</div><div><br></div><div>If we have a 512 bit block hash and apply it to 64KiB mega-blocks, we can get the same security using fewer hashing rounds in the 512-bit hash.  For example, we can use 1/6 the rounds, and hash the 64KiB twice in such a way that any message change in the first pass is at least 6 hashes away from any resulting change in the second pass, giving an equivalent hashing strength as a single pass with full rounds.  That would give us ~3X speedup assuming we are computation bound.  The memory access pattern is more complex than one would think because we have to ensure that the resulting data dependency graph has no loops of < 6 nodes in this case, and the nodes can be on either pass.  For example a bit-reversal access pattern (like we used in Catena-1) in the second pass does not work (there are loops of size 4).  A pattern more like Gambit's does seem to work (using a step size of 6 in this case), IIRC.</div><div><br></div><div>Is something like that what you had in mind?</div><div><br></div><div>Bill</div></div></div></div>