[PATCH] MPI helper of table lookup, Least Leak Intended

[Jacob Bachmeyer]

On 2/13/25 23:01, NIIBE Yutaka via Gcrypt-devel wrote:
> Hello,
>
> This change introduces a function _gcry_mpih_table_lookup.  The idea is
> accessing the whole table entries (so that cache timing won't possible)
> and select the value by ct_limb_select.
>
> Your suggestions/comments for the implementation and/or for the suitable
> name for the function are welcome.

The obvious comment to me is that the function name should probably 
contain either "_ct" or "_lli" to denote that this is a slow function 
for leak minimization.

There might also be architecture-specific instructions that can be used 
to retrieve a table row without polluting the data cache; allowing 
architecture-specific overrides here could make a very significant 
performance difference, as the basic implementation could easily flush 
the entire data cache if used on a large table.

For the base case, reading the entire table is probably the best that 
you can do, but if you have a "load without temporal locality" 
instruction (I believe that there are such instructions in SSE, for 
example), you can avoid the problem, while accessing only a single table 
row.  (The memory bus is assumed to not be visible to an attacker.)

Even if that instruction can only load to a vector unit, you can simply 
allocate a scratch row on the stack with the required alignment, store 
it there from the vector unit and copy it to the result buffer.  Of 
course the stack and result buffers would be in the data cache, so no 
leak there.

In short, I suggest planning for future enhancement here, using either 
assembler or intrinsics.  This is an operation that, in portable C, is 
going to have nasty performance-hindering side effects but /might/ be 
less expensive on some architectures.


-- Jacob