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

[Jerry Leichter]

> 
>> What I don't understand is why the various symmetric cipher modes we have
>> keep the key fixed and modify the data.
>> 
>> ...
>> 
>> The main reason for not doing this seems to be that the key schedule has to
>> be recalculated and that was expensive for DES. But that shouldn't be a
>> major problem on a modern CPU.
> 
> I think it is the cost of recalculating the key schedule. Some ciphers, e.g. Blowfish, deliberately have expensive key schedules to deter exhaustive search attacks.
If you want to go this route, don't change the raw key; change the key schedule directly.  That is:  The raw key goes through a transformation into a series of round keys which get saved and then repeatedly drive the algorithm.  You can modify the round keys directly.  The exact effect of some particular change on the raw key on each of the round keys could be computed; it would be a bit complex, but potentially much less complex than recomputing a deliberately- complex-to-compute schedule.

Of course, *most* modifications of the key schedule do not correspond to *any* possible raw key (simple counting argument).  What changes can be made *safely* is an interesting question to which I doubt a full answer is known.  Since we do know that key scheduling is essential to resistance to various attacks, you'd want to analyze this carefully before going this route.

                                                        -- Jerry