The goal of project Lif is the development of a technique that transforms a function into a version of it that is time and memory invariant. This property ensures that the set of instructions executed will always be the same regardless of the inputs. As a consequence, the execution time of said function will be constant. Such transformation method eliminates side-channels in implementations of cryptography.
This repository is split into two folders described above:
lang
: A small and simple language implemented in Haskell. It exists primarily with the purpose of implementing a skeleton of the invariant transformation pass.llvm
: A LLVM implementation of the invariant pass.
Consider the following function, which takes two lists, A and B, and returns 1 if they are equal or 0 otherwise:
int comp(int *A, int *B) {
for (int i = 0; i < N; i++)
if (A[i] != B[i]) return 0;
return 1;
}
Let A = [0, 0, 0, 0] and B = [0, 0, 0, 0]. In this case, the loop
body will be executed N times. Now, let A' = [1, 0, 0, 0]. When
calling comp
with A' and B, since the first test A'[i] != B[i]
already fails, the loop body will be executed only once and the
function will then return. Hence, if N is large, the execution
time of this function w.r.t the first input will take longer than
the execution time for the second input. This difference can, for
example, be used by an external observer to retrieve informations
related to those inputs.