diff options
Diffstat (limited to 'content/posts/2024-09-09-montgomerys-ladder.md')
| -rw-r--r-- | content/posts/2024-09-09-montgomerys-ladder.md | 96 |
1 files changed, 96 insertions, 0 deletions
diff --git a/content/posts/2024-09-09-montgomerys-ladder.md b/content/posts/2024-09-09-montgomerys-ladder.md new file mode 100644 index 0000000..9ff976e --- /dev/null +++ b/content/posts/2024-09-09-montgomerys-ladder.md @@ -0,0 +1,96 @@ +--- +slug: montgomerys-ladder +title: "Montgomery's Ladder" +date: "2024-09-09T02:00:29-04:00" +draft: true +--- + +In response to a question in the comments of an [article][] I posted the +comment below. + +---- + + +Short answer: To protect against timing side-channel attacks, the +implementation should use a constant-time version of [Montgomery's +ladder][montgomery's ladder]. + +Longer answer... + +Definitions: + +- Inversion: a{{< sup "-1" >}}. Calculate the number *b* such that a * b = 1 +- Modular Inversion: a{{< sup "-1" >}} mod p. Calculate the number *b* such that a * b = 1 (mod p). + + +From [Fermat's little theorem][], we know that if *p* is prime, then +a{{< sup "p-1" >}} = 1 (mod p). Doing a bit of arithmetic: + +a{{< sup "p-1" >}} = 1 (mod p) \ +a * a{{< sup "p-2" >}} = 1 (mod p) + +So a{{< sup "p-2" >}} (mod p) is the multiplicative inverse of *a*, modulo +*p*. + +**Example:** Calculate 2{{< sup "-1" >}} mod 5 + += 2{{< sup "-1" >}} mod 5 \ += 2{{< sup "5-2" >}} mod 5 \ += 2{{< sup "3" >}} mod 5 \ += 8 mod 5 \ += 3 + +Check result by verifying a * a{{< sup "-1" >}} = 1 (mod 5): + += 2 * 3 mod 5 \ += 6 mod 5 \ += 1 + +The numbers used in cryptography are extremely large. For example, the +primes for [Ed25519][] and [Poly1305][] are 2{{< sup "255" >}}-19 and +2{{< sup "130" >}}-5, respectively ([djb][] naming :D). To do modular +exponentation with large numbers you use a technique called +[exponentation by squaring][]. + +A common method of exponentation by squaring is [Montgomery's ladder][], +but it is not constant-time. You can make Montgomery's ladder +constant-time by changing the contents of the loop in Montgomery's +ladder from this: + +> if n{{< sub "i" >}} = 0 then \ +> x{{< sub "2" >}} = x{{< sub "1" >}} * x{{< sub "2" >}}; x{{< sub "1" >}} = x{{< sub "1" >}}{{< sup "2" >}} \ +> else \ +> x{{< sub "1" >}} = x{{< sub "1" >}} * x{{< sub "2" >}}; x{{< sub "2" >}} = x{{< sub "2" >}}{{< sup "2" >}} \ +> end + + +To something like this: + +> a = x{{< sub "1" >}} * x{{< sub "2" >}} \ +> b = x{{< sub "1" >}}{{< sup "2" >}} \ +> c = x{{< sub "2" >}}{{< sup "2" >}} \ +> d = is\_non\_zero(n{{< sub "i" >}}) +> +> swap(x{{< sub "2" >}}, a, !d) \ +> swap(x{{< sub "1" >}}, b, !d) \ +> swap(x{{< sub "1" >}}, a, d) \ +> swap(x{{< sub "2" >}}, c, d) + + +Where `swap()` is a constant-time function that swaps the values of the +first two arguments if the third argument is true and does nothing if +the third argument is false. + +Usually `swap()` is implemented with careful bitmasking to prevent +overeager compilers from "optimizing" it. + +[article]: https://arstechnica.com/security/2024/09/yubikeys-are-vulnerable-to-cloning-attacks-thanks-to-newly-discovered-side-channel/ +[comment]: https://arstechnica.com/security/2024/09/yubikeys-are-vulnerable-to-cloning-attacks-thanks-to-newly-discovered-side-channel/?comments=1&comments-page=4 +[montgomery's ladder]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Montgomery%27s_ladder_technique +[fermat's little theorem]: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem +[ed25519]: https://en.wikipedia.org/wiki/EdDSA + "Edwards-curve Digital Signature Algorithm (EdDSA)" +[poly1305]: https://en.wikipedia.org/wiki/Poly1305 +[exponentation by squaring]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring +[djb]: https://en.wikipedia.org/wiki/Daniel_J._Bernstein + "Daniel J. Bernstein" |