Not constant time #243
Description
The SBOX is implemented by looking up a bytes in a 256 byte table.
This is very insecure as demonstrated here and allows key recovery for a remote attacker.
There are 3 ways I can think of that could be used to mitigate this:
- Bitslicing the SBOX as demonstrated here. This is constant time since it basically evaluates a circuit representing the SBOX transformation. This is medium slow.
- Reading each entry of the SBOX in sequence, ANDing it with a mask that is generated from the index in constant time (0x00 for all entries except for the one we want which gets 0xff) and ORing it into a final result that is returned. This is really slow as it doesn't do anything 99.6% of the time in the SBOX part
- Prefetching the SBOX in 64 byte or 16 byte blocks so all reside in the cache. This depends on the cache line width of the CPU this is running on and can be broken by a context switch mid-prefetching.
I initially found this at c3lang/c3c#2806 but their code is just a translation of this code.