8
$\begingroup$

I'm implementing Schnorr signatures following a variant used in Bitcoin Cash (BCH) of this algorithm: GitHub - Schnorr Signatures for secp256k1.

A notable difference is that the BCH schnorr algorithm uses this variant: IETF - Variant for k calculation.

I'm in scala using bouncy castle from Java. I calculate k by using something i call here nonceRFC6979 which is the implementation what i showed on the link above

    def sign(unsigned: ByteVector, privkey: PrivateKey): Result[Signature] = {
      val d = privkey.toBigInteger
      val N = ecc.domain.getN
      val G = ecc.domain.getG

      /** Calculate k*/
      val nonceFunction = nonceRFC6979
      nonceFunction.init(N, new ECPrivateKeyParameters(d, ecc.domain).getD, unsigned.toArray, additionalData.toArray)
      val k0 = nonceFunction.nextK.mod(N)
      if (k0.equals(BigInteger.ZERO)) Failure(Err("Fail to generate signature"))

      /** R = k * G. Negate nonce if R.y is not a quadratic residue */
      val R = G.multiply(k0).normalize
      val k = if (hasSquareY(R)) k0 else N.subtract(k0)

      /** e = Hash(R.x || compressed(P) || m) mod n */
      val P        = G.multiply(d)
      val pubBytes = P.getEncoded(true).toByteVector
      val rx       = R.getXCoord.toBigInteger.toUnsignedByteVector
      val e        = Sha256.hash(rx ++ pubBytes ++ unsigned).toBigInteger.mod(N)

      /** s = (k + e * priv) mod n */
      val s = e.multiply(d).add(k).mod(N).toUnsignedByteVector

      /** Signature = (R.x, s) */
      val sig = rx ++ s
      Successful(Signature(sig))
    }

this is the nonceRFC6979 implementation its identical from HMacDSAKCalculator on calculating nextK the only difference as mentioned before is that we append some extra data here named additionalData

Now I'm trying to make this signing algorithm constant time to avoid timing attacks. My understanding is that multiplycould be an issue particularly kG. from looking at the above code and for those that know Bouncy castle, what should i bee looking into to check that this is indeed constant?

$\endgroup$
  • 1
    $\begingroup$ Something to look at is Meltdown/Spectre and other cache miss timing related attacks. They can be pretty darn tricky, since your hardware isn't constant time. $\endgroup$ – Cort Ammon May 7 at 1:54
  • $\begingroup$ Some low-level techinques: stackoverflow.com/questions/27865974/… $\endgroup$ – Nayuki May 7 at 16:17
25
$\begingroup$

How to confirm my implementation is constant time? I'm in scala using bouncy castle from Java.

This code is not constant time, for no platform is specified. Computing platforms that run in constant time or cycles are the exception. I don't know any device with internet and video currently for sale that does. That's actually contributing to make attacks harder!

For cryptographic security, what matters is Data-Dependent Timing Variation: execution time that varies depending on the data manipulated¹. The question's code most likely exhibits some DDTV, since it apparently uses Java's BigInteger type, which is not designed to avoid DDTV, and doesn't even come close. Bouncy Castle is riddled with DDTVs where it uses BigInteger, more or less sizable depending on version and platforms, at least in it's generic RSA decryption code (the only part I have studied in depth). The BC developers approach that issue by lowering DDTV when that's easy, and trying to hide it with some degree of noise when that's not. That's probably the best they can in the framework of a portable Java crypto library.

Except starting from scratch using techniques geared for constant-time down to the bare hardware for all the crypto primitives (like done for crypto accelerators in high security devices, and in BearSSL), I see little hope to reach zero DDTV, which is the most satisfying option form a security standpoint, and is practiced.


For lack of that, the only option is try making DDTVs low enough that they do not open to attack, and try to assess that. It's complicated.

In the following I'll discuss just a few down-to-earth incremental countermeasures that can be added on top of existing libraries, and may help. I'm sure neither that its necessary, nor sufficient, nor even certainly without security drawback.

One general-purpose countermeasure, effective in theory (even perfectly so) is to start a timer at the beginning of the calculation, set to elapse after it ends considering a worst-case scenario (perhaps, the experimental maximum time plus a few times the experimental standard deviation $\sigma$), and at the end of the calculation wait precisely until the timer elapses before releasing the result. But that's a portability nightmare; adversaries (or poor control of the platform) can increase the computation time (e.g. by adding workload) or slow the CPU so that it exceeds the timer; or maybe adversaries will manage to get a measure of CPU time not accounting for waiting that the timer elapses.

Another countermeasure adds a random delay. It needs to have fine granularity. A simple method draws a uniformly random integer and wait that number of cycles (or if not possible, dummy loops²), with the maximum integer calibrated for an average of a few $\sigma'$ ³ for lack of a more rationally determined value⁴. While it is possible for an attacker to mitigate such delays by correlating different experiments, or repeating the same and averaging or keeping the minimum measured time⁵, they are useful by adding uncertainty in the adversary's inputs, which tends to make a successful attack require more measurements, thus more time.

Problem with the above delays (final or randomly added) is that they are not or marginally useful against side channels other than pure timing (differential power analysis, electromagnetic and audio variants, hardware features like caches..).

A general class of countermeasure targeting a wider spectrum of side-channel attacks is blinding. The general principle is to mix-in a random value that changes how the computation is made (hence its timing and other side-channel leakage, in a manner unrelated to secret data), but not its final outcome, thanks to mathematic properties.

One blinding countermeasure applicable to computations modulo $n$, for example that of $s=(k+e\cdot\text{Priv})\bmod n$, is to

  • add $r_i\cdot n$ for random(s) $r_i$ (say in range $[0,2^{64})$ ) to some or all inputs (here $k$, $e$, $\text{Priv}$ ) of the formula
  • perform the computation modulo $u\,n$ instead of $n$, for some $u$ (say in a range $[2^{63},2^{64})$, fixed or dynamically chosen at random),
  • finally reduce modulo $n$.

Another countermeasure in that spirit, with a chance to make timing differences in elliptic curve scalar multiplication less exploitable, while only increasing the execution time moderately (like 30%), is to indirectly generate $k$ and compute $R=k\times G$ (where $\times$ is point multiplication on the elliptic curve):

  • Choose some parameter $m\approx2^{32}\sqrt n$ and precompute $G_m=m\times G$ ($m$ can be fixed and public including a power of two, or a secret randomly chosen at a time when performance does not matter much).
  • Generate random $k_a$ and $k_b$ in $[0,m')$ with $m'\approx m$, perhaps fixed $m'=2^{\left\lceil\log_2(m)\right\rceil}$
  • Compute $R=(k_a\times G_m)+(k_b\times G)$ where $+$ is point addition on the elliptic curve.
  • Use $k_a\cdot m+k_b$ instead of $k$ in the computation of $s=(k+e\cdot\text{Priv})\bmod n$. The choice of the equivalent $k$ is not quite perfectly uniformly random, but it remains fine for the purpose of Schnorr signatures. The reduction modulo $n$ can be differed to the final computation of $s$. The test $k=0$ can be replaced by a check of $R=\infty$ (in practice that will only occur if there is some bug or fault, e.g. in the RNG, and the best course of action is to zeroize/burninate the private key, if that causes no huge loss).

Conclusions:

  • Forget about constant time on most modern computing platforms.
  • Zero DDTV is desirable and achievable, commonly in hardware, and even in software, but forget about it when using Java's standard BigInteger class.
  • Starting from this code, the most reachable short-term objective is mitigating DDTVs to bring them below the level where they are demonstrably exploitable by known means in practical conditions.
  • How, and how to assess it, are vast subjects, barely touched in this answer.

¹ We really only care for data that is secret, but in this code fragment a lot is.

² With the issue that they could get optimized out by a smarter compiler, or JITC of the target platform.

³ Contrary to the previous $\sigma$, this $\sigma'$ needs to account mostly for DDTVs, not for platform-related variability.

⁴ Computing how much is necessary would require some model of the actual DDTVs, and an hypothesis on the time available for the attacker.

⁵ Which (from an attacker's perspective) is a more robust strategy than averaging if measurements are plagued by spurious activity adding to the timings. A distribution of the random delays that seldom is minimum, including near Gaussian as resulting from multiple equal delays spread along the calculation to thwart resynchronization, will give a harder time than a uniform delay to an attacker that must rely on this strategy.

Orphan note: It conceivably could help to replace random sources used in random delays and blinding by a CSPRNG, keyed by a long-term random symmetric key and the input of the computation (here, the message to sign). That will make timing deterministic, thwarting any attempts to remove the random delays (explicit, or induced by blinding) using multiple measurements with the same input. But that might not be a good idea: it's typically a better attack strategy to correlate timing measurements with as many varying inputs as possible, rather than repeating fewer measurements to make them more precise; the timing is deterministic only inasmuch as the adversary can't force the re-seeding of the fixed long-term random symmetric key; and being deterministic can well turn a disaster if the adversary manages to extract that key, or if the input of the computation is secret, or if the adversary is trying to synchronize a fault-injection attack.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.