1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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"
|
