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

constantine/constantine/math/arithmetic/finite_fields_square_root.nim

Lines 244 to 257 in 5894a8d

	func sqrt_invsqrt_if_square*[C](sqrt, invsqrt: var Fp[C], a: Fp[C]): SecretBool =
	## Compute the square root and ivnerse square root of ``a``
	##
	## This returns true if ``a`` is square and sqrt/invsqrt contains the square root/inverse square root
	##
	## The result is undefined otherwise
	##
	## The square root, if it exist is multivalued,
	## i.e. both x² == (-x)²
	## This procedure returns a deterministic result
	sqrt_invsqrt(sqrt, invsqrt, a)
	var test {.noInit.}: Fp[C]
	test.square(sqrt)
	result = test == a

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:

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)