precomp square root in constant time about constantine

[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:

constantine/constantine/platforms/constant_time/ct_routines.nim

Lines 181 to 189 in 661a481

	func secretLookup*[T; S: Ct](table: openArray[T], index: S): T =
	## Return table[index]
	## This is constant-time, whatever the `index`, its value is not leaked
	## This is also protected against cache-timing attack by always scanning the whole table
	var val: S
	for i in 0 ..< table.len:
	let selector = S(i) == index
	selector.ccopy(val, S table[i])
	return T(val)

[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.