WEBVTT 00:01.320 --> 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. 00:12.700 --> 00:19.220 The paper was recently accepted in CCS, but a full version is already available in ePrint. 00:19.340 --> 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. 00:32.460 --> 00:40.860 In the talk, I will describe new attacks based on randomness leakage against ECDSA Schnorr-type signature schemes. 00:41.080 --> 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. 00:54.780 --> 01:01.100 In the first part, I will talk about how to acquire side-channel information from the vulnerable implementations. 01:01.100 --> 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. 01:09.700 --> 01:14.260 Let's start with some background material on attacking ECDSA analysis. 01:14.620 --> 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. 01:22.740 --> 01:28.460 In modern implementations, of course, we instantiate this assumption using elliptic curve proofs. 01:28.460 --> 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. 01:40.080 --> 01:44.100 Otherwise, it has an impact on the security of the signature scheme. 01:44.580 --> 01:49.000 Let's assume a scenario where Alice and Bob want to exchange signatures. 01:49.660 --> 01:54.080 So Alice generates a secret key and sends the matching public key to Bob. 01:54.160 --> 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. 02:09.140 --> 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. 02:22.420 --> 02:29.380 This means that if the nonce is exposed somehow, this allows one to immediately compute the private key. 02:29.640 --> 02:33.800 So in practice, the nonce can never be reused or exposed. 02:33.800 --> 02:37.100 Otherwise, the trivial amount of computation gives the private key. 02:38.960 --> 02:41.360 But this is an extreme case. 02:41.360 --> 02:44.000 What happens if the nonce is slightly biased? 02:44.000 --> 02:49.240 For example, an implementation error or randomness failure fix the top bits of the nonce. 02:49.240 --> 02:54.860 Or maybe side-channel leakage in the implementation reveals some of these top bits. 02:55.000 --> 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. 03:10.480 --> 03:14.800 This class of attacks is not just of academic interest. 03:14.800 --> 03:19.060 Actually, they manifest in practice in many different ways. 03:19.060 --> 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. 03:34.840 --> 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. 03:43.220 --> 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. 04:01.420 --> 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. 04:15.280 --> 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. 04:25.860 --> 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. 04:41.440 --> 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. 05:01.120 --> 05:05.400 So it's not vulnerable to the same attacks we found in the rest of the code base. 05:05.400 --> 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. 05:18.460 --> 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. 05:27.300 --> 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. 05:41.940 --> 05:51.220 These products include the Photon lightweight operating system by VMware, the Chef remote maintenance tool, and the Wikr messaging app. 05:51.460 --> 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. 06:02.340 --> 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. 06:17.320 --> 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. 06:31.480 --> 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. 06:51.680 --> 07:00.140 The attack was mounted in a laptop with the latter, it was mounted using help of cloud computing. 07:01.500 --> 07:04.340 Now let's move to some curve-based cryptography. 07:04.340 --> 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. 07:20.100 --> 07:27.280 The point at infinity serves as the identity element for group law defined over these points. 07:27.380 --> 07:35.740 When the field has a large prime characteristic, the curve can actually be simplified as e1 on the left. 07:35.940 --> 07:42.860 And when the curve is defined over a binary field, the equation can be simplified as e2 on the right. 07:43.880 --> 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. 08:01.800 --> 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. 08:12.880 --> 08:19.720 And I can give some arithmetic intuition behind that by looking at the group law. 08:19.820 --> 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. 08:32.820 --> 08:36.320 This line becomes a tangent when the point is being doubled. 08:36.580 --> 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. 08:43.620 --> 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. 08:59.910 --> 09:05.530 All elliptic curve cryptosystems rely on the scalar multiplication operation both for performance and security. 09:05.930 --> 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. 09:15.050 --> 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. 09:25.030 --> 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. 09:36.410 --> 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. 09:44.430 --> 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. 09:57.190 --> 10:03.590 In particular, if we worry about timing attacks, this operation must be implemented in constant time. 10:04.450 --> 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. 10:14.410 --> 10:19.570 For example, when two programs share a library in memory, a flush and reload attack is possible. 10:19.570 --> 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. 10:32.750 --> 10:37.350 The flush phase of the attack is actually flushing a set of addresses from the cache. 10:37.350 --> 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. 10:48.750 --> 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. 10:59.890 --> 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. 11:06.990 --> 11:09.610 This is not a completely deterministic attack. 11:09.610 --> 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. 11:22.830 --> 11:29.850 So that's why we don't have a 100% precision side channel attack in our work. 11:30.630 --> 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. 11:42.750 --> 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. 11:56.210 --> 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. 12:05.470 --> 12:12.630 What changes per iteration is the inputs of the group operations and the outputs. 12:13.170 --> 12:15.910 And this depends on the key bits. 12:15.910 --> 12:21.150 If you try to implement this algorithm in constant time, there are several things to be taken care of. 12:21.150 --> 12:26.850 For example, the number of iterations must be fixed, otherwise the magnitude of k would be revealed. 12:26.850 --> 12:32.490 The accumulators must be read and written in the same order, independently of the key bits. 12:32.490 --> 12:36.030 And the group law, of course, must be implemented in constant time as well. 12:36.250 --> 12:39.570 Let's see how this can be done in typical implementations. 12:40.370 --> 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'. 12:50.550 --> 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. 13:01.970 --> 13:04.970 This will be relevant later on. 13:05.650 --> 13:11.230 Now k' has a fixed length, so the main loop runs for a fixed number of iterations. 13:11.350 --> 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. 13:26.570 --> 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. 13:35.630 --> 13:40.010 And this is exactly the point where our attack becomes relevant. 13:40.710 --> 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. 13:53.230 --> 13:55.690 This observation also applies to point addition. 13:55.690 --> 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. 14:06.850 --> 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. 14:24.170 --> 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. 14:37.770 --> 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. 14:57.050 --> 15:03.490 That's how the hidden number problem is used to recover the signing key. 15:04.110 --> 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. 15:18.570 --> 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. 15:30.970 --> 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. 15:49.270 --> 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. 16:04.310 --> 16:10.910 Now let's examine how we mounted these attacks against implementations of both prime and binary curves. 16:11.170 --> 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. 16:19.290 --> 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. 16:34.590 --> 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. 16:43.830 --> 16:49.090 It's much faster than actually performing a complete field multiplication operation. 16:49.530 --> 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. 16:59.010 --> 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. 17:15.630 --> 17:18.730 And we can see this behavior in the traces. 17:18.730 --> 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. 17:35.130 --> 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. 17:47.050 --> 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. 17:57.270 --> 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. 18:05.630 --> 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. 18:15.250 --> 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. 18:29.750 --> 18:34.270 A similar attack was mounted against binary curve implementations. 18:34.270 --> 18:41.330 In this case, the attacker finds out if r1 was stored in protective coordinates during point addition. 18:41.410 --> 18:48.730 The formula for point addition, the first field multiplication multiplies the x-coordinate of r0 by the z-coordinate of r1. 18:48.730 --> 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. 18:59.230 --> 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. 19:07.250 --> 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. 19:22.850 --> 19:27.050 By looking at the traces, we see similar pattern. 19:27.710 --> 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. 19:45.330 --> 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. 20:00.560 --> 20:04.440 There are at least three possible fixes for these vulnerabilities. 20:04.540 --> 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. 20:18.380 --> 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. 20:31.060 --> 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. 20:48.840 --> 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. 21:03.520 --> 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. 21:20.200 --> 21:24.800 From this point on, Akira continues with the part two of the presentation. 21:24.860 --> 21:26.580 Thanks for your attention so far. 21:28.460 --> 21:30.860 Hello everyone, my name is Akira. 21:30.860 --> 21:33.100 I'm from OSU University in Denmark. 21:33.260 --> 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. 21:43.640 --> 21:45.260 So here is the overview. 21:45.620 --> 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. 21:59.420 --> 22:06.580 And our approach follows the Fourier analysis-based attack originally devised by Blahenbacher. 22:06.900 --> 22:11.460 And here, our main contributions can be summarized as follows. 22:11.740 --> 22:18.540 First, we established a unified time-space data trade-off formula to solve the hidden number problem. 22:18.780 --> 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. 22:31.480 --> 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. 22:44.800 --> 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. 23:00.660 --> 23:04.880 So first, let's define the problem we tackle. 23:04.900 --> 23:12.580 So we are interested in solving the hidden number problem with most significant bit leakage. 23:12.600 --> 23:19.000 So here, h and z are public information, which can be computed from the ECGSA signature. 23:19.220 --> 23:29.760 And the sample h and the nonce k follows the uniform distribution over z cube, and then satisfy this equation. 23:30.300 --> 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. 23:40.740 --> 23:51.380 However, as we observed during the side-channel attack phase, the most significant bit information doesn't come with probability 1. 23:51.380 --> 24:02.540 That's why we have to slightly generalize the hidden number problem by incorporating the erroneous most significant bit leakage information. 24:02.560 --> 24:08.560 And this is exactly what we call less than 1-bit nonce leakage. 24:09.140 --> 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. 24:24.960 --> 24:30.560 And this error rate models attacker's misdetection during the side-channel acquisition phase. 24:30.580 --> 24:35.780 If epsilon is 0, then this is same as the original hidden number problem. 24:35.780 --> 24:43.000 If epsilon is 1.5, then essentially the attacker doesn't know anything about the nonce bit. 24:43.320 --> 24:47.380 So this is the problem we'd like to solve. 24:48.220 --> 24:51.780 So how do we attack the hidden number problem? 24:51.780 --> 24:54.120 There are basically two approaches. 24:54.120 --> 24:59.080 The first one is more famous, which is called the lattice attack. 24:59.140 --> 25:07.760 So lattice attack usually works very efficiently, even with fewer number of signatures. 25:08.280 --> 25:17.760 However, lattice attack only works if you have a relatively large bias or leakage information about nonce. 25:17.760 --> 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. 25:29.500 --> 25:34.600 So here, the Fourier analysis-based attack comes into play. 25:34.860 --> 25:44.960 So the nice feature of the Fourier analysis-based attack is that it can attack less bias or less leakage information. 25:45.100 --> 25:51.320 However, usually this approach requires much more signatures as input. 25:53.640 --> 26:00.260 So in this context, we set the new attack records for the hidden number problem. 26:00.500 --> 26:06.700 So here's the comparison with the previous attack records of the hidden number problem. 26:06.700 --> 26:12.360 The green ones are based on Fourier analysis, while the purple ones are based on lattices. 26:12.880 --> 26:16.380 And we basically solved these four cases. 26:17.080 --> 26:28.020 For a 160-bit HNP with 1-bit leak, compared to prior records, we required fewer input signatures to attack. 26:28.680 --> 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. 26:41.680 --> 26:48.560 So we set some new attack records in these attack parameters. 26:49.800 --> 26:58.240 Okay, so before describing our technique, let me briefly go over the fundamentals of the Fourier analysis-based attack. 26:58.360 --> 27:01.380 So what is the Fourier analysis-based attack? 27:01.380 --> 27:06.940 So this was originally proposed by Brian Bacher already 20 years ago. 27:06.940 --> 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. 27:18.120 --> 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. 27:29.820 --> 27:37.320 And another great feature is that it can handle the erroneous input out of the box, so to speak. 27:37.400 --> 27:44.720 However, as I mentioned, the large data complexity is the major bottleneck of this approach. 27:44.720 --> 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. 27:58.600 --> 28:03.420 So of course, the natural question is, can we reduce the data complexity? 28:03.800 --> 28:07.000 I'm going to answer this question later. 28:08.220 --> 28:14.120 But first, let's see how Brian Bacher's attack works. 28:14.120 --> 28:15.680 So here's a high-level overview. 28:16.440 --> 28:21.320 So the step one is to quantify the modular bias of randomness k. 28:22.240 --> 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. 28:38.160 --> 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. 28:48.380 --> 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. 28:59.020 --> 29:07.330 And this optimization step is very important to detect the bias peak correctly and efficiently. 29:08.450 --> 29:10.470 Okay, so that's the overview. 29:10.810 --> 29:14.450 So first, what is the bias function? 29:14.550 --> 29:21.130 So the bias function can be essentially defined in the form of discrete Fourier transform. 29:21.710 --> 29:30.930 So in order to interpret this definition, it is useful to imagine the complex plane and the unit circle on it. 29:31.830 --> 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. 29:46.930 --> 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. 29:58.950 --> 30:06.090 On the other hand, what if the nonce bit is biased? 30:06.090 --> 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. 30:24.270 --> 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. 30:34.750 --> 30:39.470 So this is the intuitive way to interpret the bias function. 30:40.450 --> 30:46.450 So we can actually concretely calculate the output of the bias function. 30:46.470 --> 30:49.590 So here's the useful lemma. 30:50.070 --> 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. 31:07.050 --> 31:12.630 So using this form, we can indeed calculate the value of the bias function. 31:12.630 --> 31:23.670 And as you can see here, if the biased bits are larger, then the resulting bias gets closer to one. 31:25.330 --> 31:29.290 So this is the concrete behavior of the bias function. 31:29.290 --> 31:39.010 But in order to model the error-nearest input, we have to give more analysis of the bias function. 31:39.010 --> 31:41.790 So this is what is given in the paper. 31:42.830 --> 31:48.610 So in our case, we are particularly interested in the one-bit bias case. 31:49.050 --> 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. 32:18.870 --> 32:27.390 So this is how the bias value decays depending on the noise to epsilon. 32:28.130 --> 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. 32:44.810 --> 32:52.990 So we are going to use this bias function under the randomness input in the complete analysis. 32:54.090 --> 32:58.910 So now, using this bias function, we'd like to detect the bias peak. 32:58.910 --> 33:00.830 Here's a naive approach. 33:00.870 --> 33:06.290 So first, we are given m samples of signatures satisfying this module equation. 33:07.050 --> 33:13.830 Then, we pick a secret key candidate and compute the corresponding randomness. 33:14.550 --> 33:24.350 Then, using the set of corresponding randomness candidates, we compute the bias function with a suitable FFT algorithm. 33:26.150 --> 33:32.930 And finally, if the guess is correct, we can detect a significant non-zero sample bias. 33:33.190 --> 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. 33:51.410 --> 34:00.990 But of course, this naive approach is inefficient because the peak only appears if you hit the exact solution. 34:02.010 --> 34:08.090 And so this approach is of course clearly invisible if the modulus Q is large. 34:08.090 --> 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. 34:23.050 --> 34:25.950 So, how do we circumvent this issue? 34:26.550 --> 34:35.830 So, Gleichenbacher gave a very clever observation to reduce the complexity of the FFT algorithm. 34:36.790 --> 34:43.090 So, this is the most important step called collision search space. 34:43.750 --> 34:48.450 So, this is useful to broaden the peak of the bias. 34:48.710 --> 34:50.710 So, Gleichenbacher's observation is as follows. 34:50.710 --> 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. 35:01.630 --> 35:11.230 And by taking the linear combinations h samples, peak width actually broadens to approximately Q over l. 35:11.570 --> 35:16.110 However, as a negative side effect, the peak height actually decays. 35:17.330 --> 35:26.410 But anyway, thanks to the broadened peak, it is sufficient to check only l candidates of the secret key. 35:27.050 --> 35:36.230 And now the complexity of FFT is much smaller if you choose the l appropriately. 35:37.110 --> 35:43.890 And by checking the l candidates, at least you can expect that you hit somewhere in this model. 35:43.890 --> 35:49.070 So, this is the overall idea of the collision search space. 35:49.470 --> 35:55.650 So, more formally, collision search problem in Gleichenbacher's framework can be stated as follows. 35:55.650 --> 36:01.620 So again, we are given m signature pairs and we set the memory budget for FFT. 36:02.190 --> 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. 36:12.350 --> 36:20.230 Also, we have to make sure that the coefficients of the linear combination is sparse. 36:20.230 --> 36:26.470 And this is important because otherwise the bias peak decays a lot. 36:26.530 --> 36:34.030 So, we have to make sure that the decayed bias peak is at least larger than the noise floor. 36:35.070 --> 36:44.050 So, we have to find some good balance between the smallness of the linear combination and the sparsity of the coefficients. 36:44.870 --> 36:49.370 So actually, this problem looks really like a subset sum problem. 36:49.370 --> 36:52.310 However, there's a subtle difference. 36:52.310 --> 36:58.170 In our context, we need many linear combinations instead of a single exact solution. 36:58.570 --> 37:05.830 So, we have to use some appropriate algorithm to solve this collision search problem. 37:05.830 --> 37:15.710 So, in our work, we apply Cayley's sum algorithm, which was usually applied to attack the generalized first step problem. 37:16.450 --> 37:23.130 So, here's the very high-level overview of the Cayley's sum algorithm for generalized first step problem. 37:24.090 --> 37:30.710 So, in Cayley's sum algorithm, you are usually given multiple lists of the samples. 37:31.630 --> 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. 37:43.550 --> 37:51.480 Then, you find some linear combinations such that the top bit corresponds to a certain value. 37:52.210 --> 37:56.950 Then, you construct the intermediate lists. 37:57.610 --> 38:08.040 Then, by taking the difference between those two lists, we find some small linear combinations, four. 38:08.310 --> 38:19.490 And thanks to the intermediate collision found in the prior phase, we can expect that the resulting difference is somewhat small. 38:19.490 --> 38:23.100 So, that's the very high-level idea of this algorithm. 38:24.070 --> 38:29.170 And in particular, we apply Howard Graham Joe's Cayley's sum algorithm. 38:29.170 --> 38:37.290 There are many variants, but this version of the Cayley's sum algorithm has two great advantages. 38:37.290 --> 38:42.480 First, it has configurable time-memory trade-offs. 38:43.210 --> 38:49.220 Also, it is highly parallelizable, and this is important when we implement a typing practice. 38:50.090 --> 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. 39:01.930 --> 39:08.330 We have to introduce the third parameter, that is, input data complexity. 39:09.190 --> 39:11.370 So, our question is as follows. 39:11.370 --> 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? 39:24.750 --> 39:26.530 We answer this question in the paper. 39:27.470 --> 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. 39:38.970 --> 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. 39:56.090 --> 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. 40:18.090 --> 40:28.050 On the other hand, if you have to find many bit collisions, then probably we get less number of samples. 40:28.570 --> 40:31.170 So, that's the intuition. 40:32.010 --> 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. 40:46.250 --> 40:47.630 So, here's the result. 40:47.630 --> 40:53.990 So, we calculated the trade-off curves for each HNAP instances. 40:54.110 --> 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. 41:12.670 --> 41:17.610 And if you can spend much less time, then you need more data as input. 41:18.310 --> 41:22.510 And the same analysis applies to the other NIST curves. 41:22.910 --> 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. 41:37.730 --> 41:48.710 So, to show the usefulness of our analysis, we implemented the entire attack. 41:48.710 --> 41:56.350 Here's the experimental results on the full-key recovery for the OpenSSL. 41:57.250 --> 42:06.510 First, when we attacked P192, our highly optimized parallel implementation helped a lot. 42:06.650 --> 42:16.730 So, we executed our attack using AWS EC2 instances, and we used 24 instances here. 42:16.810 --> 42:23.930 And in the end, we were able to recover the many most significant bits of the secret key. 42:24.470 --> 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. 42:37.690 --> 42:47.750 And on the other hand, the attack against 163R1 was very modest in terms of computational complexity. 42:48.550 --> 42:55.730 And we can actually infer that the attack against this case is even feasible with an everyday laptop. 42:56.290 --> 43:02.070 And also, the input data complexity was much more modest compared to the prior work. 43:02.730 --> 43:08.030 Actually, we improved the data complexity by a factor of 1000. 43:09.470 --> 43:17.010 And of course, the attack works against both the samples with errors and without errors. 43:17.810 --> 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. 43:28.470 --> 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. 43:43.990 --> 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. 43:51.730 --> 44:01.950 And we draw the interesting connection between two different cryptographic problems, which appear in the different contexts usually. 44:02.730 --> 44:06.730 And after the analysis, we got multiple open questions. 44:06.850 --> 44:11.970 Of course, the first one is the least-sum algorithm. 44:11.970 --> 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. 44:28.750 --> 44:40.040 Also, in the FFT computation part, we basically used the existing library as black box. 44:40.630 --> 44:48.520 So, of course, there's probably some room for improvement for the FFT computation phase. 44:49.080 --> 44:56.580 And as I mentioned earlier, this analysis is not restricted to ladder-leak vulnerability. 44:57.320 --> 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. 45:23.500 --> 45:31.900 Also, we are interested in analyzing the behavior of bias function for more general patterns of noise indication. 45:32.960 --> 45:35.220 Okay, so that's it for me. 45:35.220 --> 45:36.260 Thank you for listening. 45:36.620 --> 45:40.320 If you have any questions, I will be happy to answer. 45:40.540 --> 45:46.720 And if you are interested in more details, you can find our paper in this address. 46:00.740 --> 46:02.580 Welcome back, everybody. 46:03.460 --> 46:09.600 You were just listening to ladder-leak, breaking ECGSA with less than one bit of non-sleekage. 46:09.600 --> 46:12.780 I have Diego and Akira right here with me. 46:13.280 --> 46:14.980 Welcome back, everybody. 46:15.480 --> 46:17.500 Hello, hope you enjoyed the talk. 46:18.560 --> 46:20.640 So, we have two questions. 46:20.640 --> 46:23.780 I'll start with the easy one first, because you answered in the Discord chat. 46:23.780 --> 46:26.680 Again, we take questions in the Discord chat. 46:26.680 --> 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? 46:33.400 --> 46:35.680 Obviously, you're participating in the Discord chat. 46:35.680 --> 46:36.520 It's over there. 46:36.520 --> 46:38.120 Anything you want to add to that? 46:39.380 --> 46:40.040 Yeah. 46:40.040 --> 46:41.420 So, yes. 46:41.420 --> 46:44.980 So, we already published a code in our repository. 46:45.280 --> 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. 46:55.300 --> 47:02.680 So, certainly, after we revise our paper, we'd like to also revise the documentation. 47:03.040 --> 47:07.520 And then, hopefully, you can rerun the attack. 47:08.220 --> 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. 47:19.200 --> 47:19.840 Okay. 47:19.840 --> 47:22.180 Next question. 47:22.180 --> 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? 47:30.380 --> 47:35.080 So, I think you can classify roughly attacks against elliptic curves in two types. 47:35.080 --> 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. 47:42.320 --> 47:46.520 And usually, they destroy that class of curves from the cryptographic perspective. 47:46.520 --> 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. 47:56.020 --> 47:58.960 This basically kills supersingular curves for ACC. 47:59.100 --> 48:05.380 In this case, we have implementation artifacts that allow an attacker to be effective against an implementation. 48:05.380 --> 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. 48:15.020 --> 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. 48:23.480 --> 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. 48:34.500 --> 48:35.440 Well, thank you. 48:35.440 --> 48:37.200 That was a fascinating talk. 48:37.400 --> 48:39.060 Let's just... we're going to say goodbye. 48:39.060 --> 48:41.580 So, thanks again, Diego and Akira. 48:41.580 --> 48:42.360 Goodbye. 48:42.840 --> 48:43.720 Thank you. 48:43.720 --> 48:45.180 Enjoy the rest of the conference.