[00:01.320 --> 00:05.260]  Hello, I'm Diego Aguirre from Aarhus University, and I'm here to present
[00:05.260 --> 00:11.080]  LadderLeak, our latest attack against ECDSA implementations using less than one bit of
[00:11.080 --> 00:17.460]  non-slick HPUS signature. The paper was recently accepted in CCS, but a full version is already
[00:17.460 --> 00:22.120]  available in ePrint. This is joint work with Felipe Novaes from the University of Campinas
[00:22.120 --> 00:28.520]  in Brazil, Akira Takahashi from Aarhus University, Mehdi Tibushi from NTTA in Japan, and Yuval
[00:28.520 --> 00:34.920]  Yaghan from the University of Adelaide in Australia. In the talk, I will describe new
[00:34.920 --> 00:41.280]  attacks based on randomness leakage against ECDSA Schnorr-type signature schemes. The
[00:41.280 --> 00:45.540]  attacks are based on newly discovered vulnerabilities in ECDSA implementations
[00:45.540 --> 00:51.100]  contained in the OpenSSL and Relic cryptographic libraries, which motivated theoretical
[00:51.100 --> 00:55.800]  improvements to the attack framework of the hidden number problem. In the first part,
[00:55.800 --> 01:01.100]  I will talk about how to acquire side-channel information from the vulnerable implementations.
[01:01.100 --> 01:05.520]  In the second part, Akira will discuss how to exploit this side-channel information to
[01:05.520 --> 01:11.900]  recover the secret key by solving the agent P. Let's start with some background material
[01:11.900 --> 01:18.800]  on attacking ECDSA analysis. So as you know, ECDSA and Schnorr signatures are the most
[01:18.800 --> 01:23.940]  popular schemes relying on the hardness of the discrete log problem. In modern implementations,
[01:23.940 --> 01:29.300]  of course, we instantiate this assumption using elliptic curve proofs. The signing operation
[01:29.300 --> 01:35.380]  involves a secret value that's sometimes called the nonce, which is actually a major
[01:35.380 --> 01:40.560]  understatement because this value needs to remain secret for a long term. Otherwise, it
[01:40.560 --> 01:46.840]  has an impact on the security of the signature scheme. Let's assume a scenario where Alice
[01:46.840 --> 01:52.900]  and Bob want to exchange signatures. So Alice generates a secret key and sends the matching
[01:52.900 --> 01:59.680]  public key to Bob. When she wants to sign a message, she samples a nonce k as an integer
[01:59.680 --> 02:04.240]  modulo of the group order and then combines the nonce with the message and her private
[02:04.240 --> 02:09.980]  key to obtain a valid signature that Bob can verify using her public key. What's interesting
[02:09.980 --> 02:15.940]  here is if you look at the set of the signing equation, valid signatures look like equations
[02:15.940 --> 02:21.980]  relating public values from the valid signature with two unknowns, the nonce and the private
[02:21.980 --> 02:28.140]  key. This means that if the nonce is exposed somehow, this allows one to immediately compute
[02:28.140 --> 02:34.240]  the private key. So in practice, the nonce can never be reused or exposed. Otherwise,
[02:34.240 --> 02:41.360]  the trivial amount of computation gives the private key. But this is an extreme case.
[02:41.360 --> 02:46.760]  What happens if the nonce is slightly biased? For example, an implementation error or randomness
[02:46.760 --> 02:51.740]  failure fix the top bits of the nonce. Or maybe side-channel leakage in the implementation
[02:52.560 --> 02:56.820]  reveals some of these top bits. Then the attacker can actually
[02:59.360 --> 03:04.580]  perform a collection of signatures under the same private key and compute the private key at the end
[03:05.780 --> 03:09.720]  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.620]  Actually, they manifest in practice in many different ways. For example,
[03:19.620 --> 03:26.260]  when RNGs are poorly designed or implemented, when a bad entropy source is used to initiate
[03:26.260 --> 03:31.620]  the random number generator, or for example, when a virtual machine resets to a previous snapshot
[03:31.620 --> 03:38.220]  repeating the internal state. In the context of this talk, side-channel leakage actually
[03:38.220 --> 03:43.220]  reveals some bits of the nonce that, of course, this is also a danger in practice.
[03:43.220 --> 03:50.160]  The randomness failure became famous with the PlayStation 3 case, where Sony used the same
[03:50.160 --> 03:56.100]  nonce to sign all games, allowing the homebrew community to compute the signing key from just two
[03:56.100 --> 04:03.440]  legitimate games, which had a major impact at the time. So our set of contributions are
[04:04.120 --> 04:10.820]  a novel class of cache attacks against ECDSA implemented in versions 1.0.2 and 1.1.0 of OpenSSL
[04:10.820 --> 04:17.580]  and version 0.4 of the Relic cryptographic library. In principle, the affected curves
[04:17.580 --> 04:23.120]  include any curve in which the group order is just below a power of two among the curves
[04:23.120 --> 04:28.720]  implemented in these libraries. And this is reflected in many of the prime curves
[04:28.720 --> 04:33.640]  standardized by NIST, and also the binary and Koblitz curves supported in the same standard,
[04:33.640 --> 04:38.800]  and also curves from the SECG, the older SECG standard, such as, for example, the Bitcoin
[04:38.800 --> 04:46.820]  curve SECP256K1. In our first version of the paper, we claimed that the attack was effective
[04:46.820 --> 04:54.620]  in OpenSSL against curve P256, but we later found out, thanks to the CCS reviewer who pointed out
[04:54.620 --> 05:01.120]  this, that OpenSSL has custom code for this curve that's enabled by default at build time.
[05:01.120 --> 05:06.120]  So it's not vulnerable to the same attacks we found in the rest of the code base. And there
[05:06.120 --> 05:12.440]  are other compiler build switches that you can use to turn on custom code that's not
[05:12.440 --> 05:19.540]  vulnerable for other curves as well, but these are not enabled by default at build time. It's hard to
[05:19.540 --> 05:24.540]  tell exactly what products are affected by this vulnerability because the versions of OpenSSL
[05:24.540 --> 05:31.280]  we target are already deprecated. But by searching GitHub, we actually found out that some packages
[05:31.280 --> 05:39.260]  bumped their OpenSSL versions from 1.0.2.U to 1.0.2.V, for example, which indicates that they
[05:39.260 --> 05:44.380]  rely on that specific version of the library. These products include the Photon lightweight
[05:44.380 --> 05:51.220]  operating system by VMware, the Chef remote maintenance tool, and the Wikr messaging app.
[05:51.460 --> 05:56.920]  However, it's not clear that the attack will be exploitable in these products in a realistic
[05:56.920 --> 06:01.500]  threat model, just that the implementation is vulnerable in principle, or was vulnerable in
[06:01.500 --> 06:10.000]  principle. So this class of new cache attacks actually motivate improvements in the Fourier
[06:10.000 --> 06:15.640]  analysis attack on the hidden number problem, significantly reducing the number of signatures
[06:15.640 --> 06:21.580]  required to mount the attack. And in a way that it becomes feasible even when less than one bit
[06:21.580 --> 06:26.340]  of nonce leakage is available per signature, which means that the attacker gets one bit of the nonce
[06:26.340 --> 06:32.560]  with less than 100% probability by exploiting, in our case, side channel leakage. By combining
[06:32.560 --> 06:38.380]  these two, we implement a full secret key recovery attack against ECDSA implemented in OpenSSL
[06:38.380 --> 06:46.360]  over two sets of parameters, a 163-bit binary curve standardized by Secchi and a much larger
[06:46.360 --> 06:54.800]  prime curve over a 192-bit prime standardized by NIST. The attack was mounted in a laptop
[06:54.800 --> 07:00.140]  with the latter, it was mounted using help of cloud computing.
[07:01.500 --> 07:06.320]  Now let's move to some curve-based cryptography. And you all know that an elliptic curve is a set
[07:06.320 --> 07:12.180]  of solutions, x and y, over some field that satisfy the bias-stress equation, where the
[07:12.180 --> 07:17.440]  coefficients of the curve are also taken from the field and there are some conditions for the curve
[07:17.440 --> 07:23.760]  to be cryptographically interesting. The point at infinity serves as the identity element for
[07:24.800 --> 07:30.940]  group law defined over these points. When the field has a large prime characteristic,
[07:30.940 --> 07:38.100]  the curve can actually be simplified as e1 on the left. And when the curve is defined over a
[07:38.100 --> 07:45.820]  binary field, the equation can be simplified as e2 on the right. The set of points under the
[07:45.820 --> 07:51.780]  coordinate tangent point addition operation forms a group of order q, where q is typically chosen as
[07:51.980 --> 07:58.480]  a large prime or must be chosen as a large prime for security, with the point at infinity serving
[07:58.480 --> 08:05.160]  as the identity element for the group law. For efficiency, points are represented not in
[08:05.160 --> 08:09.320]  affine coordinates during intermediate operations, but in projective coordinates to save
[08:09.320 --> 08:15.840]  computation of expensive field inversions. And I can give some arithmetic intuition behind that
[08:15.840 --> 08:22.640]  by looking at the group law. So, point addition on an elliptic curve works by
[08:22.640 --> 08:26.680]  tracing a line across the points being added and reflecting the point
[08:27.900 --> 08:32.300]  consisting of the intersection between the line and the curve across the x-axis.
[08:32.820 --> 08:38.520]  This line becomes a tangent when the point is being doubled. So, computing the slope of this
[08:38.520 --> 08:42.720]  line requires a division, which of course implies the computation of a field inversion that's
[08:42.720 --> 08:47.940]  expensive. So, projective coordinates try to delay the computation of this inversion
[08:48.460 --> 08:55.500]  until the very end by storing the denominator of the slope on the z-coordinate of some intermediate
[08:55.500 --> 09:03.830]  point. All elliptic curve cryptosystems rely on the scalar multiplication operation both for
[09:03.830 --> 09:09.130]  performance and security. Scalar multiplication amounts to adding a point to itself a certain
[09:09.130 --> 09:14.370]  number of times, typically a secret number of times, and this signature generation is not
[09:14.370 --> 09:20.410]  different. It takes a signing key, a message, curve parameters, and a hash function as inputs,
[09:20.410 --> 09:28.910]  and it outputs a valid signature composed of two elements. It starts by sampling the known scale,
[09:29.050 --> 09:33.710]  a model of the group order following the uniform distribution, and then it multiplies the
[09:33.710 --> 09:39.650]  generator by these nodes. The x-coordinate of the resulting point is used in the remaining
[09:39.650 --> 09:45.690]  of the computation to obtain the signature over the input message. Performance reasons we want
[09:45.690 --> 09:50.330]  this scalar multiplication operation to be as fast as possible, but security concerns
[09:50.950 --> 09:55.970]  also determine that the operation should be implemented in a way that's protected against
[09:55.970 --> 10:01.810]  side-channel leakage. In particular, if we worry about timing attacks, this operation must be
[10:01.810 --> 10:07.430]  implemented in constant time. And this is extremely challenging in modern CPUs because they have
[10:07.430 --> 10:12.190]  user-learned instructions like CFlush that can reveal secrets across different processes
[10:12.790 --> 10:18.150]  through cache behavior. For example, when two programs share a library in memory, a flush and
[10:18.150 --> 10:24.350]  reload attack is possible. In a flush and reload attack, an attacker process probes a set of
[10:24.350 --> 10:29.550]  targeted addresses to find out if a different victim process is accessing them or has accessed
[10:29.550 --> 10:36.270]  them in a certain amount of time. The flush phase of the attack is actually flushing a set of
[10:36.270 --> 10:41.270]  addresses from the cache. The reload amounts to reloading those addresses back to the cache and
[10:41.270 --> 10:45.350]  measuring the amount of time it takes for that operation to finish, which tells the attacker if
[10:45.350 --> 10:54.450]  this was a cache hit or a cache miss. If a certain address was read meanwhile, this means that the
[10:54.450 --> 11:01.490]  reload phase will be shorter and a cache hit was actually observed. The time it takes between the
[11:01.490 --> 11:06.610]  flush and reload parts of the attack is called the slot and this will be relevant later on.
[11:06.990 --> 11:10.810]  This is not a completely deterministic attack. There could be cases in which
[11:10.810 --> 11:16.690]  the memory access performed by the victim's process overlaps with the reload phase and
[11:16.690 --> 11:22.830]  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:35.370]  When you implement scalar multiplication in a way that's protected against these attacks, you
[11:35.370 --> 11:41.390]  usually resort to the Montgomery ladder, here defined over the Weierstrass model of elliptic
[11:41.390 --> 11:47.850]  curve arithmetic. This algorithm takes an input point p, typically stored in affine coordinates,
[11:47.850 --> 11:53.690]  and the binary representation of the exponent and initializes two accumulators r0 and r1,
[11:53.690 --> 11:59.330]  such that r1 is 2 times p. Then it scans the bits of the exponent from left to right
[12:00.990 --> 12:08.130]  and computes the same number of group operations per iteration. What changes per iteration is the
[12:08.130 --> 12:16.870]  inputs of the group operations and the outputs. And this depends on the key bits. If you try to
[12:16.870 --> 12:21.250]  implement this algorithm in constant time, there are several things to be taken care of. For
[12:21.250 --> 12:26.850]  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:46.810]  To make the number of iterations constant, it's usual to add one or two multiples of the group
[12:46.810 --> 12:53.210]  order to the scalar to obtain a related scalar k'. And it's interesting that if the group order
[12:53.210 --> 12:59.310]  is just below a power of two, this means that k' preserves in its second most significant bit,
[12:59.310 --> 13:07.690]  the most significant bit of the original k. This will be relevant later on. Now k' has a fixed
[13:07.690 --> 13:12.930]  length, so the main loop runs for a fixed number of iterations. The branches in the previous slide
[13:12.930 --> 13:19.470]  can be actually removed by performing a conditional swap between the accumulators r0 and r1 that
[13:19.470 --> 13:24.250]  depends on the key bit, which means that the group law will always be evaluated over the same
[13:24.250 --> 13:29.850]  accumulators in the same order. So what remains is the careful implementation of the group law such
[13:29.850 --> 13:36.490]  that no correlation with the key bits will leak through any side channels. And this is exactly
[13:36.490 --> 13:45.030]  the point where our attack becomes relevant. For example, if the implementation leaks the fact that
[13:45.030 --> 13:50.850]  r1 is being stored in affine coordinates, this means that the points were actually swapped for
[13:50.850 --> 13:55.690]  this iteration which reveals the key bit. This observation also applies to point addition.
[13:55.690 --> 14:01.850]  If it's possible to discover if r1 here is represented in projective or affine coordinates,
[14:01.850 --> 14:08.190]  this also tells if the points were swapped or not, which reveals the key bit. So ladder leak is an
[14:08.190 --> 14:13.970]  attack against the first iteration of the loop when the points are still stored in different coordinate
[14:13.970 --> 14:20.770]  systems and it exploits the tiny differences or timing differences between the two operations
[14:20.770 --> 14:27.010]  in projective or affine coordinates. After the first iteration of the main loop, the two accumulators
[14:27.010 --> 14:34.030]  are stored in projective coordinates, so the performance or the behavior should look
[14:34.030 --> 14:42.410]  uniform from that point on. It's critical here that if the attacker is able to distinguish
[14:42.410 --> 14:46.930]  between these two situations, even for the first, just the first iteration of the loop,
[14:46.930 --> 14:53.190]  the attacker can split the set of observed signatures into two different types which are
[14:53.190 --> 15:00.470]  biased by the most significant bit of the known scale. That's how the hidden number problem is
[15:00.470 --> 15:10.190]  used to recover the signing key. In our attacks, we targeted browser CPUs with turbo boost disabled
[15:10.190 --> 15:19.450]  for reducing the noise in the measurements to have a slightly more stable attack. The OpenSSL
[15:19.450 --> 15:24.490]  library was built using the default configuration with debugging symbols turned on to make the
[15:24.490 --> 15:29.950]  text slightly more convenient, and binaries were executed in just userland without requiring any
[15:29.950 --> 15:36.090]  privileges. In terms of tooling, we used the frtrace binary from the Mastic Section Analysis
[15:36.090 --> 15:43.470]  Toolkit, and we configured the program to use a slot of 5,000 cycles, which show it to be
[15:43.470 --> 15:51.930]  easy to measure against in our target platforms. We also employed the performance degradation
[15:51.930 --> 15:59.550]  feature of the attack tool by having the idle course evict code from the cache all the time
[15:59.550 --> 16:06.850]  to penalize performance and make computation run slower. Now let's examine how we mounted
[16:06.850 --> 16:12.370]  these attacks against implementations of both prime and binary curves. In the case of prime
[16:12.370 --> 16:18.430]  curves, the attacker can detect if r1 is stored in affine coordinates inside the point doubling
[16:18.430 --> 16:23.130]  operation. So our attack works by probing two different addresses and measuring the time it
[16:23.130 --> 16:27.850]  takes to hit the first address and the second address, and from the timing difference between
[16:27.850 --> 16:34.330]  these two, the attacker is able to figure out what type of computation happened in between.
[16:34.590 --> 16:39.710]  In the implementation of point doubling, if the z-coordinate is 1, there is a branch in OpenSSL
[16:39.710 --> 16:47.210]  to actually copy an input to the result. It's much faster than actually performing a complete
[16:47.210 --> 16:53.730]  field multiplication operation. But it's still an operation that takes just a couple of hundred
[16:53.730 --> 16:59.390]  cycles, which would not be observable in the time of the full-scale multiplication. So with
[16:59.390 --> 17:04.830]  performance degradation, we penalized calls to the function bnCopy here quite a lot, and we
[17:04.830 --> 17:10.390]  amplified the difference to 15,000 cycles, which allows the flush and reload attack to detect if
[17:10.390 --> 17:18.030]  this function is called with more than 90% precision. And we can see this behavior in the
[17:18.030 --> 17:25.810]  traces. So here the y-axis has the access timing cycles for reading some addresses in the cache
[17:25.810 --> 17:33.750]  memory, and the sample number is the number of that specific sample read as scale of multiplication
[17:33.750 --> 17:43.670]  proceeds. Any memory access that's faster than the red line counts as a cache hit, because it's,
[17:43.670 --> 17:50.750]  memory address... memory access. So in the bottom trace, we can see that there is a first
[17:50.750 --> 17:55.090]  cache hit here when bnCopy is called in the first time for the first point doubling the letter
[17:55.090 --> 18:03.630]  when r1 is initialized. And then we see another set of cache hits here that amount to the point
[18:03.630 --> 18:09.470]  doubling the first iteration of the loop. If the bnCopy function is called, it takes a bit longer
[18:10.190 --> 18:15.910]  around three slots for the operation to finish, which makes it visible here. And of course,
[18:15.910 --> 18:20.650]  the same behavior is not present when the most significant bit is 1, which allows the attacker
[18:20.650 --> 18:28.190]  to distinguish the two different situations by just observing what happens in the first iteration
[18:28.190 --> 18:35.750]  of the loop. A similar attack was mounted against binary curve implementations. In this case,
[18:35.750 --> 18:41.330]  the attacker finds out if r1 was stored in protective coordinates during point addition.
[18:41.410 --> 18:46.190]  The formula for point addition, the first field multiplication multiplies the x-coordinate of
[18:46.190 --> 18:51.990]  r0 by the z-coordinate of r1. So of course, if the z-coordinate of r1 is non-trivial,
[18:51.990 --> 18:58.090]  this field multiplication will give a non-trivial double precision result that needs to be modular
[18:58.090 --> 19:03.990]  reduced. By using performance degradation, we penalize calls to the modular reduction code
[19:03.990 --> 19:08.710]  to make this field multiplication take much longer than necessary. And we managed to amplify
[19:08.710 --> 19:14.050]  the difference between 200,000 cycles, which allowed us again to detect if the
[19:14.050 --> 19:25.350]  z-coordinate of r1 is one with over than 99% precision. By looking at the traces, we see
[19:25.350 --> 19:33.250]  similar pattern. On the bottom trace, you can see that there are two consecutive cache hits
[19:33.250 --> 19:39.090]  when modular reduction is called and they are around 20 slots apart, which tells that the
[19:39.090 --> 19:45.250]  difference in execution time between these two points in time was close to 100,000 cycles.
[19:45.330 --> 19:51.630]  And the same pattern is not present when the most significant bit has a different value and the
[19:51.630 --> 19:57.810]  modular reduction code actually finishes much faster because the result being reduced is trivial.
[20:00.560 --> 20:06.280]  There are at least three possible fixes for these vulnerabilities. The first one, and perhaps most
[20:06.280 --> 20:09.920]  natural, is to randomize the z-coordinates at the beginning of this scalar multiplication
[20:09.920 --> 20:15.240]  for the two accumulators in a way that all points' intermediate values are stored in
[20:15.240 --> 20:20.200]  projective coordinates, so no special cases arise. Another possibility is to implement the
[20:20.200 --> 20:24.560]  group law in constant time using, for example, complete addition formulas without branches,
[20:24.560 --> 20:30.180]  or to implement the Montgomery letter over co-z arithmetic to not handle z-coordinates directly.
[20:31.060 --> 20:36.880]  We disclosed the vulnerabilities to OpenSSL in December last year when the versions we
[20:36.880 --> 20:43.580]  targeted were still maintained, and the vulnerabilities were fixed in April this
[20:43.580 --> 20:50.800]  year using the first countermeasure as the solution. The main takeaways of this part
[20:50.800 --> 20:56.680]  of the talk is securely implementing brittle cryptographic algorithms is still very hard and
[20:56.680 --> 21:03.260]  we should not underestimate timing leakage even if it looks tiny at first or not easy to exploit.
[21:03.520 --> 21:09.620]  For the audience, I can recommend upgrading OpenSSL to the recent releases as soon as possible
[21:09.620 --> 21:15.900]  because the development team has done a wonderful job at improving the security and quality of the
[21:15.900 --> 21:22.160]  codebase across time, so we should all benefit from that. From this point on, Akira continues
[21:22.160 --> 21:26.580]  with the part two of the presentation. Thanks for your attention so far.
[21:28.460 --> 21:34.520]  Hello everyone, my name is Akira. I'm from OSU University in Denmark. So in this part I'm going
[21:34.520 --> 21:40.160]  to explain how to exploit the randomness bias or leakage that we obtained during the
[21:40.160 --> 21:48.520]  side-channel attack against ECGSA nonce. So here is the overview. So in the second part, we'd like to recover
[21:48.520 --> 21:55.280]  the ECGSA secret key by solving the so-called hidden number problem, which was originally
[21:56.020 --> 22:03.260]  stated by Bonnet and Ben-Carteson. And our approach follows the Fourier analysis-based attack
[22:03.980 --> 22:11.460]  originally devised by Blahenbacher. And here, our main contributions can be summarized as follows.
[22:11.740 --> 22:17.400]  First, we established a unified time-space data trade-off formula to solve the hidden number
[22:17.400 --> 22:24.800]  problem. And then, we gave a generalized analysis that holds even in the presence of erroneous
[22:24.800 --> 22:30.000]  leakage information, which is crucial when mounting the side-channel attack in practice.
[22:31.480 --> 22:38.760]  Also, the techniques devised in this part, in principle, apply to other sources of
[22:39.280 --> 22:46.660]  bias or leakage, independent of the ladder-leak vulnerability. And as a result, we
[22:47.440 --> 22:53.020]  draw an interesting connection between the hidden number problem and the generalized
[22:53.020 --> 22:58.620]  per-state problem, which often appears in the context of symmetric key cryptology.
[23:00.660 --> 23:07.900]  So first, let's define the problem we tackle. So we are interested in solving the hidden number
[23:07.900 --> 23:16.180]  problem with most significant bit leakage. So here, h and z are public information,
[23:16.180 --> 23:22.280]  which can be computed from the ECGSA signature. And the sample h and the nonce k
[23:22.960 --> 23:29.760]  follows the uniform distribution over z cube, and then satisfy this equation.
[23:30.300 --> 23:37.320]  And here, the hidden number problem asks to find the secret key given the pairs h, z,
[23:37.320 --> 23:45.060]  and the most significant bit information of k. However, as we observed during the side-channel
[23:45.060 --> 23:51.380]  attack phase, the most significant bit information doesn't come with probability 1.
[23:51.380 --> 23:59.400]  That's why we have to slightly generalize the hidden number problem by incorporating the erroneous
[23:59.400 --> 24:06.140]  most significant bit leakage information. And this is exactly what we call less than
[24:06.140 --> 24:13.470]  1-bit nonce leakage. So in this setting, the hidden number problem with error rate epsilon,
[24:13.740 --> 24:20.520]  which is between 0 and 1.5, asks to find the secret key given h, z, and the most significant
[24:20.520 --> 24:27.620]  information of k with probability 1-epsilon. And this error rate models attacker's misdetection
[24:27.620 --> 24:34.240]  during the side-channel acquisition phase. If epsilon is 0, then this is same as the original
[24:34.240 --> 24:40.820]  hidden number problem. If epsilon is 1.5, then essentially the attacker doesn't know anything
[24:40.820 --> 24:47.380]  about the nonce bit. So this is the problem we'd like to solve.
[24:48.220 --> 24:54.120]  So how do we attack the hidden number problem? There are basically two approaches.
[24:54.120 --> 25:02.120]  The first one is more famous, which is called the lattice attack. So lattice attack usually works
[25:02.120 --> 25:10.920]  very efficiently, even with fewer number of signatures. However, lattice attack only works
[25:10.920 --> 25:18.940]  if you have a relatively large bias or leakage information about nonce. And in particular,
[25:19.240 --> 25:25.740]  if you only have 1-bit information about nonce, it is known that lattice attack doesn't give you
[25:26.220 --> 25:32.040]  the correct solution of the hidden number problem. So here, the Fourier analysis-based
[25:32.040 --> 25:39.180]  attack comes into play. So the nice feature of the Fourier analysis-based attack is that
[25:39.940 --> 25:48.000]  it can attack less bias or less leakage information. However, usually this approach
[25:48.000 --> 25:58.040]  requires much more signatures as input. So in this context, we set the new attack records
[25:58.040 --> 26:03.100]  for the hidden number problem. So here's the comparison with the previous attack records
[26:04.100 --> 26:09.420]  of the hidden number problem. The green ones are based on Fourier analysis,
[26:09.420 --> 26:16.380]  while the purple ones are based on lattices. And we basically solved these four cases.
[26:17.080 --> 26:25.960]  For a 160-bit HNP with 1-bit leak, compared to prior records, we required fewer input signatures
[26:26.700 --> 26:34.160]  to attack. And on the other hand, to the best of our knowledge, there has been no
[26:35.080 --> 26:45.040]  attack records for the 192-bit HNP with 1-bit leakage. So we set some new attack records
[26:46.260 --> 26:54.440]  in these attack parameters. Okay, so before describing our technique, let me briefly go
[26:54.440 --> 27:00.600]  over the fundamentals of the Fourier analysis-based attack. So what is the Fourier analysis-based
[27:00.600 --> 27:07.540]  attack? So this was originally proposed by Brian Bacher already 20 years ago. And in the last
[27:07.540 --> 27:15.340]  decade, this was revisited by Demaldo et al., and also two other works, including some of us
[27:15.340 --> 27:22.360]  as authors. And the great feature of the Fourier analysis-based attack is that
[27:22.360 --> 27:28.860]  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:54.200]  In particular, for instance, if you attack a 160-bit HNP, the prior attack required
[27:54.200 --> 28:01.140]  billions of signatures to attack 1-bit leakage. So of course, the natural question is,
[28:01.140 --> 28:07.000]  can we reduce the data complexity? I'm going to answer this question later.
[28:08.220 --> 28:15.680]  But first, let's see how Brian Bacher's attack works. 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:28.340]  And we first define the bias function, such that it outputs something close to 0
[28:28.820 --> 28:36.160]  if the noise is uniform in ZQ, while it should output something close to 1 if k is somewhat
[28:36.160 --> 28:43.840]  biased in ZQ. Then, using this bias function, we'd like to find a candidate secret key,
[28:43.840 --> 28:51.960]  which leads to the peak of this bias function. And then there's an important optimization step,
[28:51.960 --> 28:57.950]  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:15.890]  Okay, so that's the overview. So first, what is the bias function? So the bias function can be
[29:15.890 --> 29:23.970]  essentially defined in the form of discrete Fourier transform. So in order to interpret
[29:23.970 --> 29:30.930]  this definition, it is useful to imagine the complex plane and the unit circle on it.
[29:31.830 --> 29:40.130]  For instance, if the noise k is uniformly distributed in ZQ, then we can imagine that
[29:40.770 --> 29:49.730]  each vector is directed to different directions. So of course, if you take the sum of those vectors
[29:49.730 --> 29:58.950]  and normalize them, then we can expect that the resulting norm of the sum vector is small.
[29:58.950 --> 30:09.370]  On the other hand, what if the nonce bit is biased? For instance, if the top bit of the
[30:09.370 --> 30:19.110]  nonce is fixed to zero, then we can actually see that each corresponding vector is concentrated
[30:20.070 --> 30:27.750]  in the upper half of the unit circle. Then in that case, if you take the sum of those vectors,
[30:27.750 --> 30:34.710]  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:47.250]  So we can actually concretely calculate the output of the bias function. So here's the
[30:47.990 --> 30:57.730]  useful lemma. If the randomness k's top bits are fixed, for instance, if the nonce bits,
[30:57.730 --> 31:06.250]  are fixed to zero one, like this, then its modular bias can be estimated by this form.
[31:07.050 --> 31:13.410]  So using this form, we can indeed calculate the value of the bias function. And as you can see
[31:13.410 --> 31:23.670]  here, if the biased bits are larger, then the resulting bias gets closer to one.
[31:25.330 --> 31:32.770]  So this is the concrete behavior of the bias function. But in order to model the error-nearest
[31:32.770 --> 31:41.790]  input, we have to give more analysis of the bias function. So this is what is given in the paper.
[31:42.830 --> 31:50.710]  So in our case, we are particularly interested in the one-bit bias case. So here, this lemma says
[31:50.710 --> 32:01.980]  that if the nonce bit, if the nonce is a one-bit bias with probability one minus epsilon,
[32:02.290 --> 32:11.510]  then its bias value can be described by a bias for, sorry, the bias function
[32:12.280 --> 32:20.110]  value for full one-bit bias multiplied by one minus two epsilon. So this is how
[32:21.030 --> 32:30.790]  the bias value decays depending on the noise to epsilon. For instance, if the most significant
[32:30.790 --> 32:37.110]  bit of the case speaks to zero, except one percent fraction, in other words, if epsilon
[32:37.110 --> 32:47.110]  is equal to 0.01, then the bias function can be calculated like this. So we are going to use
[32:47.110 --> 32:52.990]  this bias function under the randomness input in the complete analysis.
[32:54.090 --> 33:00.830]  So now, using this bias function, we'd like to detect the bias peak. 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:21.330]  Then, using the set of corresponding randomness candidates, we compute the bias function
[33:22.150 --> 33:24.350]  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:39.310]  If the guess is incorrect, then actually we can show that the noise floor
[33:40.510 --> 33:47.870]  of the bias function is approximately 1 over square root m, which should be small
[33:47.870 --> 33:54.530]  if the m is sufficiently large. But of course, this naive approach is inefficient
[33:55.390 --> 34:00.990]  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:14.970]  In the concrete case, the Q is at least 160 bit, so we cannot really compute because FFT
[34:15.690 --> 34:22.230]  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 --> 34:56.190]  By reducing the range of the input samples h to 0 and l,
[34:56.190 --> 35:01.630]  where this l should be much smaller than the original modulus Q.
[35:01.630 --> 35:06.070]  And by taking the linear combinations h samples,
[35:06.070 --> 35:11.230]  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:24.470]  But anyway, thanks to the broadened peak, it is sufficient to check only l candidates
[35:25.050 --> 35:26.410]  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:05.660]  Then we'd like to find sufficiently many linear combinations,
[36:06.090 --> 36:11.620]  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:41.150]  So, we have to find some good balance between the smallness of the linear combination
[36:41.730 --> 36:44.050]  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:09.270]  So, in our work, we apply Cayley's sum algorithm,
[37:09.470 --> 37:15.710]  which was usually applied to attack the generalized first step problem.
[37:16.450 --> 37:22.250]  So, here's the very high-level overview of the Cayley's sum algorithm for generalized first step
[37:22.250 --> 37:30.710]  problem. So, in Cayley's sum algorithm, you are usually given multiple lists of the samples.
[37:31.630 --> 37:37.230]  And then, if the number of the list is four, for instance,
[37:37.230 --> 37:43.550]  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:03.170]  Then, by taking the difference between those two lists,
[38:03.700 --> 38:08.040]  we find some small linear combinations, four.
[38:08.310 --> 38:13.230]  And thanks to the intermediate collision found in the prior phase,
[38:13.230 --> 38:19.490]  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 --> 38:57.410]  So, the question we asked earlier can be elaborated as follows, because
[38:58.110 --> 39:01.930]  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:13.590]  So, our question is as follows. For a given most significant bit information
[39:13.590 --> 39:19.070]  from a hidden number problem and a typical budget for computational resources,
[39:19.070 --> 39:24.750]  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:35.510]  So, again, here's the high-level description of the unifying time-memory data trade-off
[39:35.510 --> 39:43.110]  that we derived based on the prior work. So, I'm not going to explain how we derived this formula,
[39:43.110 --> 39:56.090]  but intuitively, to interpret this formula, you can see the behavior of each variable as follows.
[39:56.090 --> 40:05.850]  So, first, the goal of our program is to find many solutions, which is m i minus one,
[40:05.850 --> 40:13.130]  and intuitively, if you spend more time or if you have more memory space, then we can expect that
[40:13.990 --> 40:23.250]  we find many output samples. On the other hand, if you have to find many bit collisions,
[40:23.250 --> 40:31.170]  then probably we get less number of samples. So, that's the intuition.
[40:32.010 --> 40:39.390]  And then, together with a trade-off formula and the constraints that I showed earlier from
[40:39.390 --> 40:45.450]  Blahen-Blahen, we can indeed estimate the optimal time-memory data complexity balance.
[40:46.250 --> 40:50.430]  So, here's the result. So, we calculated the trade-off curves
[40:51.330 --> 41:00.690]  for each HNAP instances. So, for instance, in order to attack 6163 R1 curve,
[41:01.590 --> 41:11.950]  if you can spend around 2 to the 55 time, then you only need around less than a million signatures.
[41:12.670 --> 41:19.450]  And if you can spend much less time, then you need more data as input. And the same analysis
[41:19.450 --> 41:27.870]  applies to the other NIST curves. Also, even though I focused on a 1-bit bias case, our paper
[41:27.870 --> 41:36.090]  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:15.170]  So, we executed our attack using AWS EC2 instances, and we used 24 instances
[42:15.950 --> 42:23.930]  here. And in the end, we were able to recover the many most significant bits of the secret key.
[42:24.470 --> 42:33.070]  And the attack was successful for both cases, where there was no error in the input samples,
[42:33.070 --> 42:36.010]  and there was 1% error in the input samples.
[42:37.690 --> 42:45.870]  And on the other hand, the attack against 163R1 was very modest in terms of computational
[42:46.670 --> 42:53.330]  complexity. And we can actually infer that the attack against this case is even feasible with
[42:54.010 --> 43:00.870]  an everyday laptop. And also, the input data complexity was much more modest compared to the
[43:00.870 --> 43:10.410]  prior work. Actually, we improved the data complexity by a factor of 1000. And of course,
[43:10.410 --> 43:18.790]  the attack works against both the samples with errors and without errors. And once you recover
[43:18.790 --> 43:25.570]  the top bits of the secret key, recovering the remaining bits of the secret key is much cheaper
[43:25.570 --> 43:33.510]  in Bly-Hendel's framework. And based on this empirical result, we can infer that the attacks
[43:33.510 --> 43:45.830]  against P224 with 1-bit bias or P256 with 2-bit bias are also tractable. Okay, so to conclude,
[43:45.830 --> 43:51.730]  in this work, we show that even less than 1-bit of nodes leakage becomes a practical concern.
[43:51.730 --> 43:57.770]  And we draw the interesting connection between two different cryptographic problems,
[43:58.470 --> 44:05.490]  which appear in the different contexts usually. And after the analysis, we got multiple open
[44:05.490 --> 44:13.630]  questions. Of course, the first one is the least-sum algorithm. Because we only analyzed
[44:13.630 --> 44:21.490]  particular instances of the k-least-sum algorithms, we are interested in exploring
[44:21.730 --> 44:27.800]  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:07.720]  So, in the future, if there are more sources of small leakage in the ECGSA nodes,
[45:07.720 --> 45:15.160]  in particular, according to our analysis, if two or three bits of leakage of bias are available,
[45:15.160 --> 45:23.000]  then the tactic attack is much more efficient, and our analysis in principle applies.
[45:23.500 --> 45:29.080]  Also, we are interested in analyzing the behavior of bias function for more
[45:29.080 --> 45:36.260]  general patterns of noise indication. Okay, so that's it for me. Thank you for listening.
[45:36.620 --> 45:44.020]  If you have any questions, I will be happy to answer. And if you are interested in more details,
[45:44.020 --> 46:04.880]  you can find our paper in this address. Welcome back, everybody. You were just listening to
[46:04.880 --> 46:11.700]  ladder-leak, breaking ECGSA with less than one bit of non-sleekage. I have Diego and Akira right here
[46:11.700 --> 46:17.500]  with me. Welcome back, everybody. Hello, hope you enjoyed the talk.
[46:18.560 --> 46:23.120]  So, we have two questions. I'll start with the easy one first, because you answered in the
[46:23.120 --> 46:28.560]  Discord chat. Again, we take questions in the Discord chat. So, would the speakers be able to
[46:28.560 --> 46:33.400]  share their software on GitHub or so that we can rerun the research on the newer libraries?
[46:33.400 --> 46:38.120]  Obviously, you're participating in the Discord chat. It's over there. Anything you want to add to that?
[46:39.380 --> 46:47.540]  Yeah. So, yes. So, we already published a code in our repository. However, if you want to reproduce
[46:47.540 --> 46:55.300]  our result, probably it's a bit difficult because we didn't document our code very well.
[46:55.300 --> 47:04.560]  So, certainly, after we revise our paper, we'd like to also revise the documentation. And then,
[47:04.560 --> 47:11.600]  hopefully, you can rerun the attack. And also, of course, if you have any questions about the setup
[47:11.600 --> 47:18.380]  or dependencies to rerun attack, I would be happy to answer the question.
[47:19.200 --> 47:25.620]  Okay. Next question. When attack is discovered in ECs, is there a way to know about which
[47:25.620 --> 47:29.140]  curves will be affected by properties, or is it a guessing game?
[47:30.380 --> 47:35.360]  So, I think you can classify roughly attacks against elliptic curves in two types. They could
[47:35.360 --> 47:40.540]  be algebraic attacks against some specific class of curves that rely on the mathematical properties
[47:40.540 --> 47:45.080]  of those curves to be effective. And usually, they destroy that class of curves from the
[47:45.080 --> 47:49.920]  cryptographic perspective. So, you can think of supersingular curves as a prime example of that
[47:50.740 --> 47:55.300]  by transferring the discrete log to another statement where tools are more powerful for
[47:55.300 --> 48:00.860]  the attacker. This basically kills supersingular curves for ACC. In this case, we have implementation
[48:00.860 --> 48:06.760]  artifacts that allow an attacker to be effective against an implementation. And then, what's
[48:06.760 --> 48:12.660]  common about this is you have some creative step to think of an attack, and then you need to find
[48:12.840 --> 48:18.380]  a matching scenario for it to be relevant. And then, it's about rigorously maximizing properties
[48:18.380 --> 48:23.480]  of interesting curves that are standardized or maybe used in practice to see where they apply.
[48:23.480 --> 48:29.100]  So, there is a creative part and just a follow-up rigorous part of maximizing
[48:29.100 --> 48:32.420]  what's the real impact by looking at curves that are interesting.
[48:34.500 --> 48:39.260]  Well, thank you. That was a fascinating talk. Let's just... we're going to say goodbye. So,
[48:39.260 --> 48:45.180]  thanks again, Diego and Akira. Goodbye. Thank you. Enjoy the rest of the conference.