1
00:00:01,320 --> 00:00:12,700
Hello, I'm Diego Aguirre from Aarhus University, and I'm here to present LadderLeak, our latest attack against ECDSA implementations using less than one bit of non-slick HPUS signature.

2
00:00:12,700 --> 00:00:19,220
The paper was recently accepted in CCS, but a full version is already available in ePrint.

3
00:00:19,340 --> 00:00:31,480
This is joint work with Felipe Novaes from the University of Campinas in Brazil, Akira Takahashi from Aarhus University, Mehdi Tibushi from NTTA in Japan, and Yuval Yaghan from the University of Adelaide in Australia.

4
00:00:32,460 --> 00:00:40,860
In the talk, I will describe new attacks based on randomness leakage against ECDSA Schnorr-type signature schemes.

5
00:00:41,080 --> 00:00:54,780
The attacks are based on newly discovered vulnerabilities in ECDSA implementations contained in the OpenSSL and Relic cryptographic libraries, which motivated theoretical improvements to the attack framework of the hidden number problem.

6
00:00:54,780 --> 00:01:01,100
In the first part, I will talk about how to acquire side-channel information from the vulnerable implementations.

7
00:01:01,100 --> 00:01:08,760
In the second part, Akira will discuss how to exploit this side-channel information to recover the secret key by solving the agent P.

8
00:01:09,700 --> 00:01:14,260
Let's start with some background material on attacking ECDSA analysis.

9
00:01:14,620 --> 00:01:22,420
So as you know, ECDSA and Schnorr signatures are the most popular schemes relying on the hardness of the discrete log problem.

10
00:01:22,740 --> 00:01:28,460
In modern implementations, of course, we instantiate this assumption using elliptic curve proofs.

11
00:01:28,460 --> 00:01:40,080
The signing operation involves a secret value that's sometimes called the nonce, which is actually a major understatement because this value needs to remain secret for a long term.

12
00:01:40,080 --> 00:01:44,100
Otherwise, it has an impact on the security of the signature scheme.

13
00:01:44,580 --> 00:01:49,000
Let's assume a scenario where Alice and Bob want to exchange signatures.

14
00:01:49,660 --> 00:01:54,080
So Alice generates a secret key and sends the matching public key to Bob.

15
00:01:54,160 --> 00:02:09,120
When she wants to sign a message, she samples a nonce k as an integer modulo of the group order and then combines the nonce with the message and her private key to obtain a valid signature that Bob can verify using her public key.

16
00:02:09,140 --> 00:02:22,420
What's interesting here is if you look at the set of the signing equation, valid signatures look like equations relating public values from the valid signature with two unknowns, the nonce and the private key.

17
00:02:22,420 --> 00:02:29,380
This means that if the nonce is exposed somehow, this allows one to immediately compute the private key.

18
00:02:29,640 --> 00:02:33,800
So in practice, the nonce can never be reused or exposed.

19
00:02:33,800 --> 00:02:37,100
Otherwise, the trivial amount of computation gives the private key.

20
00:02:38,960 --> 00:02:41,360
But this is an extreme case.

21
00:02:41,360 --> 00:02:44,000
What happens if the nonce is slightly biased?

22
00:02:44,000 --> 00:02:49,240
For example, an implementation error or randomness failure fix the top bits of the nonce.

23
00:02:49,240 --> 00:02:54,860
Or maybe side-channel leakage in the implementation reveals some of these top bits.

24
00:02:55,000 --> 00:03:09,720
Then the attacker can actually perform a collection of signatures under the same private key and compute the private key at the end by solving the hidden number problem as discussed previously.

25
00:03:10,480 --> 00:03:14,800
This class of attacks is not just of academic interest.

26
00:03:14,800 --> 00:03:19,060
Actually, they manifest in practice in many different ways.

27
00:03:19,060 --> 00:03:34,520
For example, when RNGs are poorly designed or implemented, when a bad entropy source is used to initiate the random number generator, or for example, when a virtual machine resets to a previous snapshot repeating the internal state.

28
00:03:34,840 --> 00:03:43,220
In the context of this talk, side-channel leakage actually reveals some bits of the nonce that, of course, this is also a danger in practice.

29
00:03:43,220 --> 00:04:01,020
The randomness failure became famous with the PlayStation 3 case, where Sony used the same nonce to sign all games, allowing the homebrew community to compute the signing key from just two legitimate games, which had a major impact at the time.

30
00:04:01,420 --> 00:04:15,060
So our set of contributions are a novel class of cache attacks against ECDSA implemented in versions 1.0.2 and 1.1.0 of OpenSSL and version 0.4 of the Relic cryptographic library.

31
00:04:15,280 --> 00:04:24,880
In principle, the affected curves include any curve in which the group order is just below a power of two among the curves implemented in these libraries.

32
00:04:25,860 --> 00:04:41,440
And this is reflected in many of the prime curves standardized by NIST, and also the binary and Koblitz curves supported in the same standard, and also curves from the SECG, the older SECG standard, such as, for example, the Bitcoin curve SECP256K1.

33
00:04:41,440 --> 00:05:01,120
In our first version of the paper, we claimed that the attack was effective in OpenSSL against curve P256, but we later found out, thanks to the CCS reviewer who pointed out this, that OpenSSL has custom code for this curve that's enabled by default at build time.

34
00:05:01,120 --> 00:05:05,400
So it's not vulnerable to the same attacks we found in the rest of the code base.

35
00:05:05,400 --> 00:05:18,160
And there are other compiler build switches that you can use to turn on custom code that's not vulnerable for other curves as well, but these are not enabled by default at build time.

36
00:05:18,460 --> 00:05:26,900
It's hard to tell exactly what products are affected by this vulnerability because the versions of OpenSSL we target are already deprecated.

37
00:05:27,300 --> 00:05:41,940
But by searching GitHub, we actually found out that some packages bumped their OpenSSL versions from 1.0.2.U to 1.0.2.V, for example, which indicates that they rely on that specific version of the library.

38
00:05:41,940 --> 00:05:51,220
These products include the Photon lightweight operating system by VMware, the Chef remote maintenance tool, and the Wikr messaging app.

39
00:05:51,460 --> 00:06:02,060
However, it's not clear that the attack will be exploitable in these products in a realistic threat model, just that the implementation is vulnerable in principle, or was vulnerable in principle.

40
00:06:02,340 --> 00:06:17,240
So this class of new cache attacks actually motivate improvements in the Fourier analysis attack on the hidden number problem, significantly reducing the number of signatures required to mount the attack.

41
00:06:17,320 --> 00:06:31,460
And in a way that it becomes feasible even when less than one bit of nonce leakage is available per signature, which means that the attacker gets one bit of the nonce with less than 100% probability by exploiting, in our case, side channel leakage.

42
00:06:31,480 --> 00:06:51,680
By combining these two, we implement a full secret key recovery attack against ECDSA implemented in OpenSSL over two sets of parameters, a 163-bit binary curve standardized by Secchi and a much larger prime curve over a 192-bit prime standardized by NIST.

43
00:06:51,680 --> 00:07:00,140
The attack was mounted in a laptop with the latter, it was mounted using help of cloud computing.

44
00:07:01,500 --> 00:07:04,340
Now let's move to some curve-based cryptography.

45
00:07:04,340 --> 00:07:19,380
And you all know that an elliptic curve is a set of solutions, x and y, over some field that satisfy the bias-stress equation, where the coefficients of the curve are also taken from the field and there are some conditions for the curve to be cryptographically interesting.

46
00:07:20,100 --> 00:07:27,280
The point at infinity serves as the identity element for group law defined over these points.

47
00:07:27,380 --> 00:07:35,740
When the field has a large prime characteristic, the curve can actually be simplified as e1 on the left.

48
00:07:35,940 --> 00:07:42,860
And when the curve is defined over a binary field, the equation can be simplified as e2 on the right.

49
00:07:43,880 --> 00:08:01,400
The set of points under the coordinate tangent point addition operation forms a group of order q, where q is typically chosen as a large prime or must be chosen as a large prime for security, with the point at infinity serving as the identity element for the group law.

50
00:08:01,800 --> 00:08:12,540
For efficiency, points are represented not in affine coordinates during intermediate operations, but in projective coordinates to save computation of expensive field inversions.

51
00:08:12,880 --> 00:08:19,720
And I can give some arithmetic intuition behind that by looking at the group law.

52
00:08:19,820 --> 00:08:32,300
So, point addition on an elliptic curve works by tracing a line across the points being added and reflecting the point consisting of the intersection between the line and the curve across the x-axis.

53
00:08:32,820 --> 00:08:36,320
This line becomes a tangent when the point is being doubled.

54
00:08:36,580 --> 00:08:43,620
So, computing the slope of this line requires a division, which of course implies the computation of a field inversion that's expensive.

55
00:08:43,620 --> 00:08:56,620
So, projective coordinates try to delay the computation of this inversion until the very end by storing the denominator of the slope on the z-coordinate of some intermediate point.

56
00:08:59,910 --> 00:09:05,530
All elliptic curve cryptosystems rely on the scalar multiplication operation both for performance and security.

57
00:09:05,930 --> 00:09:15,050
Scalar multiplication amounts to adding a point to itself a certain number of times, typically a secret number of times, and this signature generation is not different.

58
00:09:15,050 --> 00:09:24,410
It takes a signing key, a message, curve parameters, and a hash function as inputs, and it outputs a valid signature composed of two elements.

59
00:09:25,030 --> 00:09:36,290
It starts by sampling the known scale, a model of the group order following the uniform distribution, and then it multiplies the generator by these nodes.

60
00:09:36,410 --> 00:09:44,430
The x-coordinate of the resulting point is used in the remaining of the computation to obtain the signature over the input message.

61
00:09:44,430 --> 00:09:57,190
Performance reasons we want this scalar multiplication operation to be as fast as possible, but security concerns also determine that the operation should be implemented in a way that's protected against side-channel leakage.

62
00:09:57,190 --> 00:10:03,590
In particular, if we worry about timing attacks, this operation must be implemented in constant time.

63
00:10:04,450 --> 00:10:14,410
And this is extremely challenging in modern CPUs because they have user-learned instructions like CFlush that can reveal secrets across different processes through cache behavior.

64
00:10:14,410 --> 00:10:19,570
For example, when two programs share a library in memory, a flush and reload attack is possible.

65
00:10:19,570 --> 00:10:31,950
In a flush and reload attack, an attacker process probes a set of targeted addresses to find out if a different victim process is accessing them or has accessed them in a certain amount of time.

66
00:10:32,750 --> 00:10:37,350
The flush phase of the attack is actually flushing a set of addresses from the cache.

67
00:10:37,350 --> 00:10:47,830
The reload amounts to reloading those addresses back to the cache and measuring the amount of time it takes for that operation to finish, which tells the attacker if this was a cache hit or a cache miss.

68
00:10:48,750 --> 00:10:59,770
If a certain address was read meanwhile, this means that the reload phase will be shorter and a cache hit was actually observed.

69
00:10:59,890 --> 00:11:06,610
The time it takes between the flush and reload parts of the attack is called the slot and this will be relevant later on.

70
00:11:06,990 --> 00:11:09,610
This is not a completely deterministic attack.

71
00:11:09,610 --> 00:11:22,830
There could be cases in which the memory access performed by the victim's process overlaps with the reload phase and creates confusion for the attacker to distinguish between if the address was read or not.

72
00:11:22,830 --> 00:11:29,850
So that's why we don't have a 100% precision side channel attack in our work.

73
00:11:30,630 --> 00:11:42,630
When you implement scalar multiplication in a way that's protected against these attacks, you usually resort to the Montgomery ladder, here defined over the Weierstrass model of elliptic curve arithmetic.

74
00:11:42,750 --> 00:11:56,210
This algorithm takes an input point p, typically stored in affine coordinates, and the binary representation of the exponent and initializes two accumulators r0 and r1, such that r1 is 2 times p.

75
00:11:56,210 --> 00:12:05,470
Then it scans the bits of the exponent from left to right and computes the same number of group operations per iteration.

76
00:12:05,470 --> 00:12:12,630
What changes per iteration is the inputs of the group operations and the outputs.

77
00:12:13,170 --> 00:12:15,910
And this depends on the key bits.

78
00:12:15,910 --> 00:12:21,150
If you try to implement this algorithm in constant time, there are several things to be taken care of.

79
00:12:21,150 --> 00:12:26,850
For example, the number of iterations must be fixed, otherwise the magnitude of k would be revealed.

80
00:12:26,850 --> 00:12:32,490
The accumulators must be read and written in the same order, independently of the key bits.

81
00:12:32,490 --> 00:12:36,030
And the group law, of course, must be implemented in constant time as well.

82
00:12:36,250 --> 00:12:39,570
Let's see how this can be done in typical implementations.

83
00:12:40,370 --> 00:12:50,550
To make the number of iterations constant, it's usual to add one or two multiples of the group order to the scalar to obtain a related scalar k'.

84
00:12:50,550 --> 00:13:01,870
And it's interesting that if the group order is just below a power of two, this means that k' preserves in its second most significant bit, the most significant bit of the original k.

85
00:13:01,970 --> 00:13:04,970
This will be relevant later on.

86
00:13:05,650 --> 00:13:11,230
Now k' has a fixed length, so the main loop runs for a fixed number of iterations.

87
00:13:11,350 --> 00:13:26,150
The branches in the previous slide can be actually removed by performing a conditional swap between the accumulators r0 and r1 that depends on the key bit, which means that the group law will always be evaluated over the same accumulators in the same order.

88
00:13:26,570 --> 00:13:34,710
So what remains is the careful implementation of the group law such that no correlation with the key bits will leak through any side channels.

89
00:13:35,630 --> 00:13:40,010
And this is exactly the point where our attack becomes relevant.

90
00:13:40,710 --> 00:13:53,230
For example, if the implementation leaks the fact that r1 is being stored in affine coordinates, this means that the points were actually swapped for this iteration which reveals the key bit.

91
00:13:53,230 --> 00:13:55,690
This observation also applies to point addition.

92
00:13:55,690 --> 00:14:06,390
If it's possible to discover if r1 here is represented in projective or affine coordinates, this also tells if the points were swapped or not, which reveals the key bit.

93
00:14:06,850 --> 00:14:24,170
So ladder leak is an attack against the first iteration of the loop when the points are still stored in different coordinate systems and it exploits the tiny differences or timing differences between the two operations in projective or affine coordinates.

94
00:14:24,170 --> 00:14:36,990
After the first iteration of the main loop, the two accumulators are stored in projective coordinates, so the performance or the behavior should look uniform from that point on.

95
00:14:37,770 --> 00:14:57,050
It's critical here that if the attacker is able to distinguish between these two situations, even for the first, just the first iteration of the loop, the attacker can split the set of observed signatures into two different types which are biased by the most significant bit of the known scale.

96
00:14:57,050 --> 00:15:03,490
That's how the hidden number problem is used to recover the signing key.

97
00:15:04,110 --> 00:15:18,450
In our attacks, we targeted browser CPUs with turbo boost disabled for reducing the noise in the measurements to have a slightly more stable attack.

98
00:15:18,570 --> 00:15:30,970
The OpenSSL library was built using the default configuration with debugging symbols turned on to make the text slightly more convenient, and binaries were executed in just userland without requiring any privileges.

99
00:15:30,970 --> 00:15:49,230
In terms of tooling, we used the frtrace binary from the Mastic Section Analysis Toolkit, and we configured the program to use a slot of 5,000 cycles, which show it to be easy to measure against in our target platforms.

100
00:15:49,270 --> 00:16:03,550
We also employed the performance degradation feature of the attack tool by having the idle course evict code from the cache all the time to penalize performance and make computation run slower.

101
00:16:04,310 --> 00:16:10,910
Now let's examine how we mounted these attacks against implementations of both prime and binary curves.

102
00:16:11,170 --> 00:16:19,290
In the case of prime curves, the attacker can detect if r1 is stored in affine coordinates inside the point doubling operation.

103
00:16:19,290 --> 00:16:34,330
So our attack works by probing two different addresses and measuring the time it takes to hit the first address and the second address, and from the timing difference between these two, the attacker is able to figure out what type of computation happened in between.

104
00:16:34,590 --> 00:16:43,590
In the implementation of point doubling, if the z-coordinate is 1, there is a branch in OpenSSL to actually copy an input to the result.

105
00:16:43,830 --> 00:16:49,090
It's much faster than actually performing a complete field multiplication operation.

106
00:16:49,530 --> 00:16:58,630
But it's still an operation that takes just a couple of hundred cycles, which would not be observable in the time of the full-scale multiplication.

107
00:16:59,010 --> 00:17:15,370
So with performance degradation, we penalized calls to the function bnCopy here quite a lot, and we amplified the difference to 15,000 cycles, which allows the flush and reload attack to detect if this function is called with more than 90% precision.

108
00:17:15,630 --> 00:17:18,730
And we can see this behavior in the traces.

109
00:17:18,730 --> 00:17:35,050
So here the y-axis has the access timing cycles for reading some addresses in the cache memory, and the sample number is the number of that specific sample read as scale of multiplication proceeds.

110
00:17:35,130 --> 00:17:46,270
Any memory access that's faster than the red line counts as a cache hit, because it's, memory address... memory access.

111
00:17:47,050 --> 00:17:57,270
So in the bottom trace, we can see that there is a first cache hit here when bnCopy is called in the first time for the first point doubling the letter when r1 is initialized.

112
00:17:57,270 --> 00:18:05,630
And then we see another set of cache hits here that amount to the point doubling the first iteration of the loop.

113
00:18:05,630 --> 00:18:15,250
If the bnCopy function is called, it takes a bit longer around three slots for the operation to finish, which makes it visible here.

114
00:18:15,250 --> 00:18:29,310
And of course, the same behavior is not present when the most significant bit is 1, which allows the attacker to distinguish the two different situations by just observing what happens in the first iteration of the loop.

115
00:18:29,750 --> 00:18:34,270
A similar attack was mounted against binary curve implementations.

116
00:18:34,270 --> 00:18:41,330
In this case, the attacker finds out if r1 was stored in protective coordinates during point addition.

117
00:18:41,410 --> 00:18:48,730
The formula for point addition, the first field multiplication multiplies the x-coordinate of r0 by the z-coordinate of r1.

118
00:18:48,730 --> 00:18:59,210
So of course, if the z-coordinate of r1 is non-trivial, this field multiplication will give a non-trivial double precision result that needs to be modular reduced.

119
00:18:59,230 --> 00:19:07,250
By using performance degradation, we penalize calls to the modular reduction code to make this field multiplication take much longer than necessary.

120
00:19:07,250 --> 00:19:21,770
And we managed to amplify the difference between 200,000 cycles, which allowed us again to detect if the z-coordinate of r1 is one with over than 99% precision.

121
00:19:22,850 --> 00:19:27,050
By looking at the traces, we see similar pattern.

122
00:19:27,710 --> 00:19:45,250
On the bottom trace, you can see that there are two consecutive cache hits when modular reduction is called and they are around 20 slots apart, which tells that the difference in execution time between these two points in time was close to 100,000 cycles.

123
00:19:45,330 --> 00:19:57,810
And the same pattern is not present when the most significant bit has a different value and the modular reduction code actually finishes much faster because the result being reduced is trivial.

124
00:20:00,560 --> 00:20:04,440
There are at least three possible fixes for these vulnerabilities.

125
00:20:04,540 --> 00:20:18,340
The first one, and perhaps most natural, is to randomize the z-coordinates at the beginning of this scalar multiplication for the two accumulators in a way that all points' intermediate values are stored in projective coordinates, so no special cases arise.

126
00:20:18,380 --> 00:20:30,180
Another possibility is to implement the group law in constant time using, for example, complete addition formulas without branches, or to implement the Montgomery letter over co-z arithmetic to not handle z-coordinates directly.

127
00:20:31,060 --> 00:20:47,560
We disclosed the vulnerabilities to OpenSSL in December last year when the versions we targeted were still maintained, and the vulnerabilities were fixed in April this year using the first countermeasure as the solution.

128
00:20:48,840 --> 00:21:03,260
The main takeaways of this part of the talk is securely implementing brittle cryptographic algorithms is still very hard and we should not underestimate timing leakage even if it looks tiny at first or not easy to exploit.

129
00:21:03,520 --> 00:21:20,060
For the audience, I can recommend upgrading OpenSSL to the recent releases as soon as possible because the development team has done a wonderful job at improving the security and quality of the codebase across time, so we should all benefit from that.

130
00:21:20,200 --> 00:21:24,800
From this point on, Akira continues with the part two of the presentation.

131
00:21:24,860 --> 00:21:26,580
Thanks for your attention so far.

132
00:21:28,460 --> 00:21:30,860
Hello everyone, my name is Akira.

133
00:21:30,860 --> 00:21:33,100
I'm from OSU University in Denmark.

134
00:21:33,260 --> 00:21:43,260
So in this part I'm going to explain how to exploit the randomness bias or leakage that we obtained during the side-channel attack against ECGSA nonce.

135
00:21:43,640 --> 00:21:45,260
So here is the overview.

136
00:21:45,620 --> 00:21:59,040
So in the second part, we'd like to recover the ECGSA secret key by solving the so-called hidden number problem, which was originally stated by Bonnet and Ben-Carteson.

137
00:21:59,420 --> 00:22:06,580
And our approach follows the Fourier analysis-based attack originally devised by Blahenbacher.

138
00:22:06,900 --> 00:22:11,460
And here, our main contributions can be summarized as follows.

139
00:22:11,740 --> 00:22:18,540
First, we established a unified time-space data trade-off formula to solve the hidden number problem.

140
00:22:18,780 --> 00:22:30,000
And then, we gave a generalized analysis that holds even in the presence of erroneous leakage information, which is crucial when mounting the side-channel attack in practice.

141
00:22:31,480 --> 00:22:43,780
Also, the techniques devised in this part, in principle, apply to other sources of bias or leakage, independent of the ladder-leak vulnerability.

142
00:22:44,800 --> 00:22:58,620
And as a result, we draw an interesting connection between the hidden number problem and the generalized per-state problem, which often appears in the context of symmetric key cryptology.

143
00:23:00,660 --> 00:23:04,880
So first, let's define the problem we tackle.

144
00:23:04,900 --> 00:23:12,580
So we are interested in solving the hidden number problem with most significant bit leakage.

145
00:23:12,600 --> 00:23:19,000
So here, h and z are public information, which can be computed from the ECGSA signature.

146
00:23:19,220 --> 00:23:29,760
And the sample h and the nonce k follows the uniform distribution over z cube, and then satisfy this equation.

147
00:23:30,300 --> 00:23:40,620
And here, the hidden number problem asks to find the secret key given the pairs h, z, and the most significant bit information of k.

148
00:23:40,740 --> 00:23:51,380
However, as we observed during the side-channel attack phase, the most significant bit information doesn't come with probability 1.

149
00:23:51,380 --> 00:24:02,540
That's why we have to slightly generalize the hidden number problem by incorporating the erroneous most significant bit leakage information.

150
00:24:02,560 --> 00:24:08,560
And this is exactly what we call less than 1-bit nonce leakage.

151
00:24:09,140 --> 00:24:24,940
So in this setting, the hidden number problem with error rate epsilon, which is between 0 and 1.5, asks to find the secret key given h, z, and the most significant information of k with probability 1-epsilon.

152
00:24:24,960 --> 00:24:30,560
And this error rate models attacker's misdetection during the side-channel acquisition phase.

153
00:24:30,580 --> 00:24:35,780
If epsilon is 0, then this is same as the original hidden number problem.

154
00:24:35,780 --> 00:24:43,000
If epsilon is 1.5, then essentially the attacker doesn't know anything about the nonce bit.

155
00:24:43,320 --> 00:24:47,380
So this is the problem we'd like to solve.

156
00:24:48,220 --> 00:24:51,780
So how do we attack the hidden number problem?

157
00:24:51,780 --> 00:24:54,120
There are basically two approaches.

158
00:24:54,120 --> 00:24:59,080
The first one is more famous, which is called the lattice attack.

159
00:24:59,140 --> 00:25:07,760
So lattice attack usually works very efficiently, even with fewer number of signatures.

160
00:25:08,280 --> 00:25:17,760
However, lattice attack only works if you have a relatively large bias or leakage information about nonce.

161
00:25:17,760 --> 00:25:29,440
And in particular, if you only have 1-bit information about nonce, it is known that lattice attack doesn't give you the correct solution of the hidden number problem.

162
00:25:29,500 --> 00:25:34,600
So here, the Fourier analysis-based attack comes into play.

163
00:25:34,860 --> 00:25:44,960
So the nice feature of the Fourier analysis-based attack is that it can attack less bias or less leakage information.

164
00:25:45,100 --> 00:25:51,320
However, usually this approach requires much more signatures as input.

165
00:25:53,640 --> 00:26:00,260
So in this context, we set the new attack records for the hidden number problem.

166
00:26:00,500 --> 00:26:06,700
So here's the comparison with the previous attack records of the hidden number problem.

167
00:26:06,700 --> 00:26:12,360
The green ones are based on Fourier analysis, while the purple ones are based on lattices.

168
00:26:12,880 --> 00:26:16,380
And we basically solved these four cases.

169
00:26:17,080 --> 00:26:28,020
For a 160-bit HNP with 1-bit leak, compared to prior records, we required fewer input signatures to attack.

170
00:26:28,680 --> 00:26:41,300
And on the other hand, to the best of our knowledge, there has been no attack records for the 192-bit HNP with 1-bit leakage.

171
00:26:41,680 --> 00:26:48,560
So we set some new attack records in these attack parameters.

172
00:26:49,800 --> 00:26:58,240
Okay, so before describing our technique, let me briefly go over the fundamentals of the Fourier analysis-based attack.

173
00:26:58,360 --> 00:27:01,380
So what is the Fourier analysis-based attack?

174
00:27:01,380 --> 00:27:06,940
So this was originally proposed by Brian Bacher already 20 years ago.

175
00:27:06,940 --> 00:27:16,860
And in the last decade, this was revisited by Demaldo et al., and also two other works, including some of us as authors.

176
00:27:18,120 --> 00:27:28,860
And the great feature of the Fourier analysis-based attack is that it can exploit arbitrary small bias or leakage of randomness to solve HNP.

177
00:27:29,820 --> 00:27:37,320
And another great feature is that it can handle the erroneous input out of the box, so to speak.

178
00:27:37,400 --> 00:27:44,720
However, as I mentioned, the large data complexity is the major bottleneck of this approach.

179
00:27:44,720 --> 00:27:58,080
In particular, for instance, if you attack a 160-bit HNP, the prior attack required billions of signatures to attack 1-bit leakage.

180
00:27:58,600 --> 00:28:03,420
So of course, the natural question is, can we reduce the data complexity?

181
00:28:03,800 --> 00:28:07,000
I'm going to answer this question later.

182
00:28:08,220 --> 00:28:14,120
But first, let's see how Brian Bacher's attack works.

183
00:28:14,120 --> 00:28:15,680
So here's a high-level overview.

184
00:28:16,440 --> 00:28:21,320
So the step one is to quantify the modular bias of randomness k.

185
00:28:22,240 --> 00:28:37,820
And we first define the bias function, such that it outputs something close to 0 if the noise is uniform in ZQ, while it should output something close to 1 if k is somewhat biased in ZQ.

186
00:28:38,160 --> 00:28:47,760
Then, using this bias function, we'd like to find a candidate secret key, which leads to the peak of this bias function.

187
00:28:48,380 --> 00:28:57,950
And then there's an important optimization step, which is called collision search of integers h, where h is a part of the signature.

188
00:28:59,020 --> 00:29:07,330
And this optimization step is very important to detect the bias peak correctly and efficiently.

189
00:29:08,450 --> 00:29:10,470
Okay, so that's the overview.

190
00:29:10,810 --> 00:29:14,450
So first, what is the bias function?

191
00:29:14,550 --> 00:29:21,130
So the bias function can be essentially defined in the form of discrete Fourier transform.

192
00:29:21,710 --> 00:29:30,930
So in order to interpret this definition, it is useful to imagine the complex plane and the unit circle on it.

193
00:29:31,830 --> 00:29:46,030
For instance, if the noise k is uniformly distributed in ZQ, then we can imagine that each vector is directed to different directions.

194
00:29:46,930 --> 00:29:58,950
So of course, if you take the sum of those vectors and normalize them, then we can expect that the resulting norm of the sum vector is small.

195
00:29:58,950 --> 00:30:06,090
On the other hand, what if the nonce bit is biased?

196
00:30:06,090 --> 00:30:23,650
For instance, if the top bit of the nonce is fixed to zero, then we can actually see that each corresponding vector is concentrated in the upper half of the unit circle.

197
00:30:24,270 --> 00:30:34,710
Then in that case, if you take the sum of those vectors, then the resulting norm is expected to be much larger than the other case.

198
00:30:34,750 --> 00:30:39,470
So this is the intuitive way to interpret the bias function.

199
00:30:40,450 --> 00:30:46,450
So we can actually concretely calculate the output of the bias function.

200
00:30:46,470 --> 00:30:49,590
So here's the useful lemma.

201
00:30:50,070 --> 00:31:06,250
If the randomness k's top bits are fixed, for instance, if the nonce bits, are fixed to zero one, like this, then its modular bias can be estimated by this form.

202
00:31:07,050 --> 00:31:12,630
So using this form, we can indeed calculate the value of the bias function.

203
00:31:12,630 --> 00:31:23,670
And as you can see here, if the biased bits are larger, then the resulting bias gets closer to one.

204
00:31:25,330 --> 00:31:29,290
So this is the concrete behavior of the bias function.

205
00:31:29,290 --> 00:31:39,010
But in order to model the error-nearest input, we have to give more analysis of the bias function.

206
00:31:39,010 --> 00:31:41,790
So this is what is given in the paper.

207
00:31:42,830 --> 00:31:48,610
So in our case, we are particularly interested in the one-bit bias case.

208
00:31:49,050 --> 00:32:18,330
So here, this lemma says that if the nonce bit, if the nonce is a one-bit bias with probability one minus epsilon, then its bias value can be described by a bias for, sorry, the bias function value for full one-bit bias multiplied by one minus two epsilon.

209
00:32:18,870 --> 00:32:27,390
So this is how the bias value decays depending on the noise to epsilon.

210
00:32:28,130 --> 00:32:44,190
For instance, if the most significant bit of the case speaks to zero, except one percent fraction, in other words, if epsilon is equal to 0.01, then the bias function can be calculated like this.

211
00:32:44,810 --> 00:32:52,990
So we are going to use this bias function under the randomness input in the complete analysis.

212
00:32:54,090 --> 00:32:58,910
So now, using this bias function, we'd like to detect the bias peak.

213
00:32:58,910 --> 00:33:00,830
Here's a naive approach.

214
00:33:00,870 --> 00:33:06,290
So first, we are given m samples of signatures satisfying this module equation.

215
00:33:07,050 --> 00:33:13,830
Then, we pick a secret key candidate and compute the corresponding randomness.

216
00:33:14,550 --> 00:33:24,350
Then, using the set of corresponding randomness candidates, we compute the bias function with a suitable FFT algorithm.

217
00:33:26,150 --> 00:33:32,930
And finally, if the guess is correct, we can detect a significant non-zero sample bias.

218
00:33:33,190 --> 00:33:50,590
If the guess is incorrect, then actually we can show that the noise floor of the bias function is approximately 1 over square root m, which should be small if the m is sufficiently large.

219
00:33:51,410 --> 00:34:00,990
But of course, this naive approach is inefficient because the peak only appears if you hit the exact solution.

220
00:34:02,010 --> 00:34:08,090
And so this approach is of course clearly invisible if the modulus Q is large.

221
00:34:08,090 --> 00:34:22,230
In the concrete case, the Q is at least 160 bit, so we cannot really compute because FFT algorithm takes order Q space and order Q times log Q time.

222
00:34:23,050 --> 00:34:25,950
So, how do we circumvent this issue?

223
00:34:26,550 --> 00:34:35,830
So, Gleichenbacher gave a very clever observation to reduce the complexity of the FFT algorithm.

224
00:34:36,790 --> 00:34:43,090
So, this is the most important step called collision search space.

225
00:34:43,750 --> 00:34:48,450
So, this is useful to broaden the peak of the bias.

226
00:34:48,710 --> 00:34:50,710
So, Gleichenbacher's observation is as follows.

227
00:34:50,710 --> 00:35:01,630
By reducing the range of the input samples h to 0 and l, where this l should be much smaller than the original modulus Q.

228
00:35:01,630 --> 00:35:11,230
And by taking the linear combinations h samples, peak width actually broadens to approximately Q over l.

229
00:35:11,570 --> 00:35:16,110
However, as a negative side effect, the peak height actually decays.

230
00:35:17,330 --> 00:35:26,410
But anyway, thanks to the broadened peak, it is sufficient to check only l candidates of the secret key.

231
00:35:27,050 --> 00:35:36,230
And now the complexity of FFT is much smaller if you choose the l appropriately.

232
00:35:37,110 --> 00:35:43,890
And by checking the l candidates, at least you can expect that you hit somewhere in this model.

233
00:35:43,890 --> 00:35:49,070
So, this is the overall idea of the collision search space.

234
00:35:49,470 --> 00:35:55,650
So, more formally, collision search problem in Gleichenbacher's framework can be stated as follows.

235
00:35:55,650 --> 00:36:01,620
So again, we are given m signature pairs and we set the memory budget for FFT.

236
00:36:02,190 --> 00:36:11,620
Then we'd like to find sufficiently many linear combinations, such that the resulting linear combination is smaller than the memory budget for FFT.

237
00:36:12,350 --> 00:36:20,230
Also, we have to make sure that the coefficients of the linear combination is sparse.

238
00:36:20,230 --> 00:36:26,470
And this is important because otherwise the bias peak decays a lot.

239
00:36:26,530 --> 00:36:34,030
So, we have to make sure that the decayed bias peak is at least larger than the noise floor.

240
00:36:35,070 --> 00:36:44,050
So, we have to find some good balance between the smallness of the linear combination and the sparsity of the coefficients.

241
00:36:44,870 --> 00:36:49,370
So actually, this problem looks really like a subset sum problem.

242
00:36:49,370 --> 00:36:52,310
However, there's a subtle difference.

243
00:36:52,310 --> 00:36:58,170
In our context, we need many linear combinations instead of a single exact solution.

244
00:36:58,570 --> 00:37:05,830
So, we have to use some appropriate algorithm to solve this collision search problem.

245
00:37:05,830 --> 00:37:15,710
So, in our work, we apply Cayley's sum algorithm, which was usually applied to attack the generalized first step problem.

246
00:37:16,450 --> 00:37:23,130
So, here's the very high-level overview of the Cayley's sum algorithm for generalized first step problem.

247
00:37:24,090 --> 00:37:30,710
So, in Cayley's sum algorithm, you are usually given multiple lists of the samples.

248
00:37:31,630 --> 00:37:43,550
And then, if the number of the list is four, for instance, you first take the linear combinations of two between two lists.

249
00:37:43,550 --> 00:37:51,480
Then, you find some linear combinations such that the top bit corresponds to a certain value.

250
00:37:52,210 --> 00:37:56,950
Then, you construct the intermediate lists.

251
00:37:57,610 --> 00:38:08,040
Then, by taking the difference between those two lists, we find some small linear combinations, four.

252
00:38:08,310 --> 00:38:19,490
And thanks to the intermediate collision found in the prior phase, we can expect that the resulting difference is somewhat small.

253
00:38:19,490 --> 00:38:23,100
So, that's the very high-level idea of this algorithm.

254
00:38:24,070 --> 00:38:29,170
And in particular, we apply Howard Graham Joe's Cayley's sum algorithm.

255
00:38:29,170 --> 00:38:37,290
There are many variants, but this version of the Cayley's sum algorithm has two great advantages.

256
00:38:37,290 --> 00:38:42,480
First, it has configurable time-memory trade-offs.

257
00:38:43,210 --> 00:38:49,220
Also, it is highly parallelizable, and this is important when we implement a typing practice.

258
00:38:50,090 --> 00:39:01,930
So, the question we asked earlier can be elaborated as follows, because now it is not sufficient to consider time-memory trade-offs.

259
00:39:01,930 --> 00:39:08,330
We have to introduce the third parameter, that is, input data complexity.

260
00:39:09,190 --> 00:39:11,370
So, our question is as follows.

261
00:39:11,370 --> 00:39:24,750
For a given most significant bit information from a hidden number problem and a typical budget for computational resources, what would be the optimal balance between the time, memory, and input data complexities?

262
00:39:24,750 --> 00:39:26,530
We answer this question in the paper.

263
00:39:27,470 --> 00:39:38,970
So, again, here's the high-level description of the unifying time-memory data trade-off that we derived based on the prior work.

264
00:39:38,970 --> 00:39:56,090
So, I'm not going to explain how we derived this formula, but intuitively, to interpret this formula, you can see the behavior of each variable as follows.

265
00:39:56,090 --> 00:40:17,510
So, first, the goal of our program is to find many solutions, which is m i minus one, and intuitively, if you spend more time or if you have more memory space, then we can expect that we find many output samples.

266
00:40:18,090 --> 00:40:28,050
On the other hand, if you have to find many bit collisions, then probably we get less number of samples.

267
00:40:28,570 --> 00:40:31,170
So, that's the intuition.

268
00:40:32,010 --> 00:40:45,450
And then, together with a trade-off formula and the constraints that I showed earlier from Blahen-Blahen, we can indeed estimate the optimal time-memory data complexity balance.

269
00:40:46,250 --> 00:40:47,630
So, here's the result.

270
00:40:47,630 --> 00:40:53,990
So, we calculated the trade-off curves for each HNAP instances.

271
00:40:54,110 --> 00:41:11,950
So, for instance, in order to attack 6163 R1 curve, if you can spend around 2 to the 55 time, then you only need around less than a million signatures.

272
00:41:12,670 --> 00:41:17,610
And if you can spend much less time, then you need more data as input.

273
00:41:18,310 --> 00:41:22,510
And the same analysis applies to the other NIST curves.

274
00:41:22,910 --> 00:41:36,090
Also, even though I focused on a 1-bit bias case, our paper has various trade-off graphs and improved complexity estimates for 2 or 3-bit bias.

275
00:41:37,730 --> 00:41:48,710
So, to show the usefulness of our analysis, we implemented the entire attack.

276
00:41:48,710 --> 00:41:56,350
Here's the experimental results on the full-key recovery for the OpenSSL.

277
00:41:57,250 --> 00:42:06,510
First, when we attacked P192, our highly optimized parallel implementation helped a lot.

278
00:42:06,650 --> 00:42:16,730
So, we executed our attack using AWS EC2 instances, and we used 24 instances here.

279
00:42:16,810 --> 00:42:23,930
And in the end, we were able to recover the many most significant bits of the secret key.

280
00:42:24,470 --> 00:42:36,010
And the attack was successful for both cases, where there was no error in the input samples, and there was 1% error in the input samples.

281
00:42:37,690 --> 00:42:47,750
And on the other hand, the attack against 163R1 was very modest in terms of computational complexity.

282
00:42:48,550 --> 00:42:55,730
And we can actually infer that the attack against this case is even feasible with an everyday laptop.

283
00:42:56,290 --> 00:43:02,070
And also, the input data complexity was much more modest compared to the prior work.

284
00:43:02,730 --> 00:43:08,030
Actually, we improved the data complexity by a factor of 1000.

285
00:43:09,470 --> 00:43:17,010
And of course, the attack works against both the samples with errors and without errors.

286
00:43:17,810 --> 00:43:27,310
And once you recover the top bits of the secret key, recovering the remaining bits of the secret key is much cheaper in Bly-Hendel's framework.

287
00:43:28,470 --> 00:43:42,230
And based on this empirical result, we can infer that the attacks against P224 with 1-bit bias or P256 with 2-bit bias are also tractable.

288
00:43:43,990 --> 00:43:51,730
Okay, so to conclude, in this work, we show that even less than 1-bit of nodes leakage becomes a practical concern.

289
00:43:51,730 --> 00:44:01,950
And we draw the interesting connection between two different cryptographic problems, which appear in the different contexts usually.

290
00:44:02,730 --> 00:44:06,730
And after the analysis, we got multiple open questions.

291
00:44:06,850 --> 00:44:11,970
Of course, the first one is the least-sum algorithm.

292
00:44:11,970 --> 00:44:27,800
Because we only analyzed particular instances of the k-least-sum algorithms, we are interested in exploring more trade-offs obtained by other variants of the least-sum algorithms.

293
00:44:28,750 --> 00:44:40,040
Also, in the FFT computation part, we basically used the existing library as black box.

294
00:44:40,630 --> 00:44:48,520
So, of course, there's probably some room for improvement for the FFT computation phase.

295
00:44:49,080 --> 00:44:56,580
And as I mentioned earlier, this analysis is not restricted to ladder-leak vulnerability.

296
00:44:57,320 --> 00:45:23,000
So, in the future, if there are more sources of small leakage in the ECGSA nodes, in particular, according to our analysis, if two or three bits of leakage of bias are available, then the tactic attack is much more efficient, and our analysis in principle applies.

297
00:45:23,500 --> 00:45:31,900
Also, we are interested in analyzing the behavior of bias function for more general patterns of noise indication.

298
00:45:32,960 --> 00:45:35,220
Okay, so that's it for me.

299
00:45:35,220 --> 00:45:36,260
Thank you for listening.

300
00:45:36,620 --> 00:45:40,320
If you have any questions, I will be happy to answer.

301
00:45:40,540 --> 00:45:46,720
And if you are interested in more details, you can find our paper in this address.

302
00:46:00,740 --> 00:46:02,580
Welcome back, everybody.

303
00:46:03,460 --> 00:46:09,600
You were just listening to ladder-leak, breaking ECGSA with less than one bit of non-sleekage.

304
00:46:09,600 --> 00:46:12,780
I have Diego and Akira right here with me.

305
00:46:13,280 --> 00:46:14,980
Welcome back, everybody.

306
00:46:15,480 --> 00:46:17,500
Hello, hope you enjoyed the talk.

307
00:46:18,560 --> 00:46:20,640
So, we have two questions.

308
00:46:20,640 --> 00:46:23,780
I'll start with the easy one first, because you answered in the Discord chat.

309
00:46:23,780 --> 00:46:26,680
Again, we take questions in the Discord chat.

310
00:46:26,680 --> 00:46:33,400
So, would the speakers be able to share their software on GitHub or so that we can rerun the research on the newer libraries?

311
00:46:33,400 --> 00:46:35,680
Obviously, you're participating in the Discord chat.

312
00:46:35,680 --> 00:46:36,520
It's over there.

313
00:46:36,520 --> 00:46:38,120
Anything you want to add to that?

314
00:46:39,380 --> 00:46:40,040
Yeah.

315
00:46:40,040 --> 00:46:41,420
So, yes.

316
00:46:41,420 --> 00:46:44,980
So, we already published a code in our repository.

317
00:46:45,280 --> 00:46:55,300
However, if you want to reproduce our result, probably it's a bit difficult because we didn't document our code very well.

318
00:46:55,300 --> 00:47:02,680
So, certainly, after we revise our paper, we'd like to also revise the documentation.

319
00:47:03,040 --> 00:47:07,520
And then, hopefully, you can rerun the attack.

320
00:47:08,220 --> 00:47:18,380
And also, of course, if you have any questions about the setup or dependencies to rerun attack, I would be happy to answer the question.

321
00:47:19,200 --> 00:47:19,840
Okay.

322
00:47:19,840 --> 00:47:22,180
Next question.

323
00:47:22,180 --> 00:47:29,140
When attack is discovered in ECs, is there a way to know about which curves will be affected by properties, or is it a guessing game?

324
00:47:30,380 --> 00:47:35,080
So, I think you can classify roughly attacks against elliptic curves in two types.

325
00:47:35,080 --> 00:47:42,320
They could be algebraic attacks against some specific class of curves that rely on the mathematical properties of those curves to be effective.

326
00:47:42,320 --> 00:47:46,520
And usually, they destroy that class of curves from the cryptographic perspective.

327
00:47:46,520 --> 00:47:56,020
So, you can think of supersingular curves as a prime example of that by transferring the discrete log to another statement where tools are more powerful for the attacker.

328
00:47:56,020 --> 00:47:58,960
This basically kills supersingular curves for ACC.

329
00:47:59,100 --> 00:48:05,380
In this case, we have implementation artifacts that allow an attacker to be effective against an implementation.

330
00:48:05,380 --> 00:48:15,020
And then, what's common about this is you have some creative step to think of an attack, and then you need to find a matching scenario for it to be relevant.

331
00:48:15,020 --> 00:48:23,480
And then, it's about rigorously maximizing properties of interesting curves that are standardized or maybe used in practice to see where they apply.

332
00:48:23,480 --> 00:48:32,420
So, there is a creative part and just a follow-up rigorous part of maximizing what's the real impact by looking at curves that are interesting.

333
00:48:34,500 --> 00:48:35,440
Well, thank you.

334
00:48:35,440 --> 00:48:37,200
That was a fascinating talk.

335
00:48:37,400 --> 00:48:39,060
Let's just... we're going to say goodbye.

336
00:48:39,060 --> 00:48:41,580
So, thanks again, Diego and Akira.

337
00:48:41,580 --> 00:48:42,360
Goodbye.

338
00:48:42,840 --> 00:48:43,720
Thank you.

339
00:48:43,720 --> 00:48:45,180
Enjoy the rest of the conference.