precomp square root in constant time

[advaita-saha]

The square root with precomp optimisation is not currently in constant-time

PR #354 adds the precomp optimisation to the square-root for Banderwagon/Bandersnatch. The implementation needs to be changed to a constant-time implementation and all the _vatime functions to be changes/removed related to the optimised square root.

Once the implementation is in constant-time, a check for the curve type should be added here and the precomp sqrt to be called https://github.com/mratsim/constantine/blob/5894a8da757bb935b681c73d1fdc92a7838f94ed/constantine/math/arithmetic/finite_fields_square_root.nim#L244-L257

The problem which need to be fixed

So the problem is in the access of the LUT table in constantine/math/constants/banderwagon_sqrt.nim and constantine/math/constants/bandersnatch_sqrt.nim. We need to fetch values corresponding to the key, but if the key is not present we need to return zero. This is currently done using the tableLUT.getOrDefault(key, 0). But this is function is not in constant time. If this access is made in constant-time then the whole implementation will be in constant-time

[rupam-04]

I came up with a quite simple solution to this issue, but I am not sure if its actually in constant time. While reading the code I came across a certain key value pair in the table (65534: 0). The problem was the time for accessing a value in a table with its key was not the same as returning 0. We can kind of avoid this issue with the following implementation:

func sqrtAlg_NegDlogInSmallDyadicSubgroup(x: Fp): int {.tags:[VarTime], raises: [KeyError].} =
  let key = cast[int](x.mres.limbs[0] and SecretWord 0xFFFF)
  if Fp.C.sqrtDlog(dlogLUT).hasKey(key):
    return Fp.C.sqrtDlog(dlogLUT)[key]
  else:
    return Fp.C.sqrtDlog(dlogLUT)[65534]

Since in both the cases of the if we are accessing a table element, it is supposed to be in constant time I think. So this might be a workaround for now.

[mratsim]

Unfortunately this is still susceptible to cache-timing attacks, like Percival: https://koclab.cs.ucsb.edu/teaching/cren/project/2010/gallegos.pdf

The data in Fp.C.sqrtDlog(dlogLUT)[65534] would be read often and be hot in cache and so would result in timing differences compared to a "real" key.

Beyond timing differences, this would also result in different power draw or electromagnetic profile depending on the data taken, while on a PC it would be drowned in noise, this can be read on embedded devices like a Raspberry Pi or a Phone.

This technique is often called "double-and-always-add" using a dummy point in elliptic curve scalar multiplication and there is a lot of litterature on attacks it cannot prevent:

• Survey for Performance & Security Problems of Passive Side-channel Attacks Countermeasures in ECC\ Rodrigo Abarúa, Claudio Valencia, and Julio López, 2019\ https://eprint.iacr.org/2019/010
• State-of-the-art of secure ECC implementations:a survey on known side-channel attacks and countermeasures\ Junfeng Fan,XuGuo, Elke De Mulder, Patrick Schaumont, Bart Preneel and Ingrid Verbauwhede, 2010\ https://www.esat.kuleuven.be/cosic/publications/article-1461.pdf

In Aburúa, Valencia, López paper, 7 ways to defeat that approach are listed:

---

In general, to achieve constant-time property, the data access pattern MUST NOT depend on secret data. Hence you need to always access the whole table when dealing with lookup tables:

https://github.com/mratsim/constantine/blob/661a4818406e22971b00ed9c32390aee8ac0d291/constantine/platforms/constant_time/ct_routines.nim#L181-L189