[Cryptography] Stupid question on S-boxes

[Henry Baker]

At 10:52 AM 1/25/2019, Jerry Leichter wrote:
>> S-boxes leak secret key info through cache timing attacks.  IMO, they should be avoided.
>Responding more directly to Henry's comment:  Small S-boxes, if the code is properly arranged, can stay entirely in the cache - you can access every entry in the table up front to get them all in there, for example - so are less likely to leak information through cache timing attacks.  Large S-boxes, on the other hand, are more likely to get partially loaded/knocked out of the cache, giving more purchase to cache timing attacks.

The last time I looked (several years ago), there appeared to be *no way* on many architectures to empty a cache line *without writing it to memory*, and more importantly, no way to guarantee that a cache line is *never written to memory*.  There used to be architectures that would guarantee that a memory reference would *bypass* the cache(s), but that's now so slow that no one seems to care about that any more.

As is becoming obvious, our current models of programming languages and hardware architectures are completely inadequate to the task of assuring no bit leaks.  We need new *typing models* for programming languages, and new constraints for HW that guarantee that certain bits will only go where they're told to go, and *no place else*.

Yes, there will continue to be devastating DPA attacks, but for the vast majority of privacy issues, it would be great that anyone pawing through the trash (memory, registers, caches, etc.) won't see private bits.

For example, caches might want to become *exclusive* -- i.e., an (address,value) can't reside in more than one location (memory,L3,L2,L1,etc.) at one time; it might even be interesting to include *registers* in this list (yes, tagging will be required, but is long overdue for modern architectures).  Perhaps this constraint should only apply to pages marked RW, as some RO pages -- e.g., shared .exe pages -- might be less interesting.