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. The paper was recently accepted in CCS, but a full version is already
available in ePrint. 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. In the talk, I will describe new
attacks based on randomness leakage against ECDSA Schnorr-type signature schemes. 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. In the first part,
I will talk about how to acquire side-channel information from the vulnerable implementations.
In the second part, Akira will discuss how to exploit this side-channel information to
recover the secret key by solving the agent P. Let's start with some background material
on attacking ECDSA analysis. So as you know, ECDSA and Schnorr signatures are the most
popular schemes relying on the hardness of the discrete log problem. In modern implementations,
of course, we instantiate this assumption using elliptic curve proofs. 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. Otherwise, it
has an impact on the security of the signature scheme. Let's assume a scenario where Alice
and Bob want to exchange signatures. So Alice generates a secret key and sends the matching
public key to Bob. 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. 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. This means that if the nonce is exposed somehow, this allows one to immediately compute
the private key. So in practice, the nonce can never be reused or exposed. Otherwise,
the trivial amount of computation gives the private key. But this is an extreme case.
What happens if the nonce is slightly biased? For example, an implementation error or randomness
failure fix the top bits of the nonce. Or maybe side-channel leakage in the implementation
reveals some of these top bits. 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.
This class of attacks is not just of academic interest.
Actually, they manifest in practice in many different ways. 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. 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.
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. 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. 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. 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. 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.
So it's not vulnerable to the same attacks we found in the rest of the code base. 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. It's hard to
tell exactly what products are affected by this vulnerability because the versions of OpenSSL
we target are already deprecated. 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. These products include the Photon lightweight
operating system by VMware, the Chef remote maintenance tool, and the Wikr messaging app.
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. 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. 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. 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. The attack was mounted in a laptop
with the latter, it was mounted using help of cloud computing.
Now let's move to some curve-based cryptography. 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. The point at infinity serves as the identity element for
group law defined over these points. When the field has a large prime characteristic,
the curve can actually be simplified as e1 on the left. And when the curve is defined over a
binary field, the equation can be simplified as e2 on the right. 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. For efficiency, points are represented not in
affine coordinates during intermediate operations, but in projective coordinates to save
computation of expensive field inversions. And I can give some arithmetic intuition behind that
by looking at the group law. 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.
This line becomes a tangent when the point is being doubled. So, computing the slope of this
line requires a division, which of course implies the computation of a field inversion that's
expensive. 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. All elliptic curve cryptosystems rely on the scalar multiplication operation both for
performance and security. 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. 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. 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. The x-coordinate of the resulting point is used in the remaining
of the computation to obtain the signature over the input message. 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. In particular, if we worry about timing attacks, this operation must be
implemented in constant time. 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. For example, when two programs share a library in memory, a flush and
reload attack is possible. 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. The flush phase of the attack is actually flushing a set of
addresses from the cache. 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. If a certain address was read meanwhile, this means that the
reload phase will be shorter and a cache hit was actually observed. The time it takes between the
flush and reload parts of the attack is called the slot and this will be relevant later on.
This is not a completely deterministic attack. 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.
So that's why we don't have a 100% precision side channel attack in our work.
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. 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. Then it scans the bits of the exponent from left to right
and computes the same number of group operations per iteration. What changes per iteration is the
inputs of the group operations and the outputs. And this depends on the key bits. If you try to
implement this algorithm in constant time, there are several things to be taken care of. For
example, the number of iterations must be fixed, otherwise the magnitude of k would be revealed.
The accumulators must be read and written in the same order, independently of the key bits.
And the group law, of course, must be implemented in constant time as well.
Let's see how this can be done in typical implementations.
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'. 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. This will be relevant later on. Now k' has a fixed
length, so the main loop runs for a fixed number of iterations. 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. 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. And this is exactly
the point where our attack becomes relevant. 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. This observation also applies to point addition.
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. 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. 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. 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. That's how the hidden number problem is
used to recover the signing key. 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. 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. 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. 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. Now let's examine how we mounted
these attacks against implementations of both prime and binary curves. In the case of prime
curves, the attacker can detect if r1 is stored in affine coordinates inside the point doubling
operation. 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.
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. It's much faster than actually performing a complete
field multiplication operation. 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. 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. And we can see this behavior in the
traces. 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. Any memory access that's faster than the red line counts as a cache hit, because it's,
memory address... memory access. 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. And then we see another set of cache hits here that amount to the point
doubling the first iteration of the loop. If the bnCopy function is called, it takes a bit longer
around three slots for the operation to finish, which makes it visible here. 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. A similar attack was mounted against binary curve implementations. In this case,
the attacker finds out if r1 was stored in protective coordinates during point addition.
The formula for point addition, the first field multiplication multiplies the x-coordinate of
r0 by the z-coordinate of r1. 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. By using performance degradation, we penalize calls to the modular reduction code
to make this field multiplication take much longer than necessary. 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. By looking at the traces, we see
similar pattern. 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.
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.
There are at least three possible fixes for these vulnerabilities. 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. 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.
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. 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.
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. From this point on, Akira continues
with the part two of the presentation. Thanks for your attention so far.
Hello everyone, my name is Akira. I'm from OSU University in Denmark. 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. So here is the overview. 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. And our approach follows the Fourier analysis-based attack
originally devised by Blahenbacher. And here, our main contributions can be summarized as follows.
First, we established a unified time-space data trade-off formula to solve the hidden number
problem. 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.
Also, the techniques devised in this part, in principle, apply to other sources of
bias or leakage, independent of the ladder-leak vulnerability. 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.
So first, let's define the problem we tackle. So we are interested in solving the hidden number
problem with most significant bit leakage. So here, h and z are public information,
which can be computed from the ECGSA signature. And the sample h and the nonce k
follows the uniform distribution over z cube, and then satisfy this equation.
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. However, as we observed during the side-channel
attack phase, the most significant bit information doesn't come with probability 1.
That's why we have to slightly generalize the hidden number problem by incorporating the erroneous
most significant bit leakage information. And this is exactly what we call less than
1-bit nonce leakage. 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. And this error rate models attacker's misdetection
during the side-channel acquisition phase. If epsilon is 0, then this is same as the original
hidden number problem. If epsilon is 1.5, then essentially the attacker doesn't know anything
about the nonce bit. So this is the problem we'd like to solve.
So how do we attack the hidden number problem? There are basically two approaches.
The first one is more famous, which is called the lattice attack. So lattice attack usually works
very efficiently, even with fewer number of signatures. However, lattice attack only works
if you have a relatively large bias or leakage information about nonce. 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. So here, the Fourier analysis-based
attack comes into play. So the nice feature of the Fourier analysis-based attack is that
it can attack less bias or less leakage information. However, usually this approach
requires much more signatures as input. So in this context, we set the new attack records
for the hidden number problem. So here's the comparison with the previous attack records
of the hidden number problem. The green ones are based on Fourier analysis,
while the purple ones are based on lattices. And we basically solved these four cases.
For a 160-bit HNP with 1-bit leak, compared to prior records, we required fewer input signatures
to attack. 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. So we set some new attack records
in these attack parameters. Okay, so before describing our technique, let me briefly go
over the fundamentals of the Fourier analysis-based attack. So what is the Fourier analysis-based
attack? So this was originally proposed by Brian Bacher already 20 years ago. And in the last
decade, this was revisited by Demaldo et al., and also two other works, including some of us
as authors. 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.
And another great feature is that it can handle the erroneous input out of the box, so to speak.
However, as I mentioned, the large data complexity is the major bottleneck of this approach.
In particular, for instance, if you attack a 160-bit HNP, the prior attack required
billions of signatures to attack 1-bit leakage. So of course, the natural question is,
can we reduce the data complexity? I'm going to answer this question later.
But first, let's see how Brian Bacher's attack works. So here's a high-level overview.
So the step one is to quantify the modular bias of randomness k.
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. Then, using this bias function, we'd like to find a candidate secret key,
which leads to the peak of this bias function. And then there's an important optimization step,
which is called collision search of integers h, where h is a part of the signature.
And this optimization step is very important to detect the bias peak correctly and efficiently.
Okay, so that's the overview. So first, what is the bias function? So the bias function can be
essentially defined in the form of discrete Fourier transform. So in order to interpret
this definition, it is useful to imagine the complex plane and the unit circle on it.
For instance, if the noise k is uniformly distributed in ZQ, then we can imagine that
each vector is directed to different directions. 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.
On the other hand, what if the nonce bit is biased? 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. 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.
So this is the intuitive way to interpret the bias function.
So we can actually concretely calculate the output of the bias function. So here's the
useful lemma. 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.
So using this form, we can indeed calculate the value of the bias function. And as you can see
here, if the biased bits are larger, then the resulting bias gets closer to one.
So this is the concrete behavior of the bias function. But in order to model the error-nearest
input, we have to give more analysis of the bias function. So this is what is given in the paper.
So in our case, we are particularly interested in the one-bit bias case. 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. So this is how
the bias value decays depending on the noise to epsilon. 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. So we are going to use
this bias function under the randomness input in the complete analysis.
So now, using this bias function, we'd like to detect the bias peak. Here's a naive approach.
So first, we are given m samples of signatures satisfying this module equation.
Then, we pick a secret key candidate and compute the corresponding randomness.
Then, using the set of corresponding randomness candidates, we compute the bias function
with a suitable FFT algorithm.
And finally, if the guess is correct, we can detect a significant non-zero sample bias.
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. But of course, this naive approach is inefficient
because the peak only appears if you hit the exact solution.
And so this approach is of course clearly invisible if the modulus Q is large.
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.
So, how do we circumvent this issue?
So, Gleichenbacher gave a very clever observation to reduce the complexity of the FFT algorithm.
So, this is the most important step called collision search space.
So, this is useful to broaden the peak of the bias.
So, Gleichenbacher's observation is as follows.
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.
And by taking the linear combinations h samples,
peak width actually broadens to approximately Q over l.
However, as a negative side effect, the peak height actually decays.
But anyway, thanks to the broadened peak, it is sufficient to check only l candidates
of the secret key.
And now the complexity of FFT is much smaller if you choose the l appropriately.
And by checking the l candidates, at least you can expect that you hit somewhere in this model.
So, this is the overall idea of the collision search space.
So, more formally, collision search problem in Gleichenbacher's framework can be stated as follows.
So again, we are given m signature pairs and we set the memory budget for FFT.
Then we'd like to find sufficiently many linear combinations,
such that the resulting linear combination is smaller than the memory budget for FFT.
Also, we have to make sure that the coefficients of the linear combination is sparse.
And this is important because otherwise the bias peak decays a lot.
So, we have to make sure that the decayed bias peak is at least larger than the noise floor.
So, we have to find some good balance between the smallness of the linear combination
and the sparsity of the coefficients.
So actually, this problem looks really like a subset sum problem.
However, there's a subtle difference.
In our context, we need many linear combinations instead of a single exact solution.
So, we have to use some appropriate algorithm to solve this collision search problem.
So, in our work, we apply Cayley's sum algorithm,
which was usually applied to attack the generalized first step problem.
So, here's the very high-level overview of the Cayley's sum algorithm for generalized first step
problem. So, in Cayley's sum algorithm, you are usually given multiple lists of the samples.
And then, if the number of the list is four, for instance,
you first take the linear combinations of two between two lists.
Then, you find some linear combinations such that the top bit corresponds to a certain value.
Then, you construct the intermediate lists.
Then, by taking the difference between those two lists,
we find some small linear combinations, four.
And thanks to the intermediate collision found in the prior phase,
we can expect that the resulting difference is somewhat small.
So, that's the very high-level idea of this algorithm.
And in particular, we apply Howard Graham Joe's Cayley's sum algorithm.
There are many variants, but this version of the Cayley's sum algorithm has two great advantages.
First, it has configurable time-memory trade-offs.
Also, it is highly parallelizable, and this is important when we implement a typing practice.
So, the question we asked earlier can be elaborated as follows, because
now it is not sufficient to consider time-memory trade-offs.
We have to introduce the third parameter, that is, input data complexity.
So, our question is as follows. 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?
We answer this question in the paper.
So, again, here's the high-level description of the unifying time-memory data trade-off
that we derived based on the prior work. 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.
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. On the other hand, if you have to find many bit collisions,
then probably we get less number of samples. So, that's the intuition.
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.
So, here's the result. So, we calculated the trade-off curves
for each HNAP instances. 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.
And if you can spend much less time, then you need more data as input. And the same analysis
applies to the other NIST curves. 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.
So, to show the usefulness of our analysis, we implemented the entire attack.
Here's the experimental results on the full-key recovery for the OpenSSL.
First, when we attacked P192, our highly optimized parallel implementation helped a lot.
So, we executed our attack using AWS EC2 instances, and we used 24 instances
here. And in the end, we were able to recover the many most significant bits of the secret key.
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.
And on the other hand, the attack against 163R1 was very modest in terms of computational
complexity. And we can actually infer that the attack against this case is even feasible with
an everyday laptop. And also, the input data complexity was much more modest compared to the
prior work. Actually, we improved the data complexity by a factor of 1000. And of course,
the attack works against both the samples with errors and without errors. 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. 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. Okay, so to conclude,
in this work, we show that even less than 1-bit of nodes leakage becomes a practical concern.
And we draw the interesting connection between two different cryptographic problems,
which appear in the different contexts usually. And after the analysis, we got multiple open
questions. Of course, the first one is the least-sum algorithm. 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.
Also, in the FFT computation part, we basically used the existing library as black box.
So, of course, there's probably some room for improvement for the FFT computation phase.
And as I mentioned earlier, this analysis is not restricted to ladder-leak vulnerability.
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.
Also, we are interested in analyzing the behavior of bias function for more
general patterns of noise indication. Okay, so that's it for me. Thank you for listening.
If you have any questions, I will be happy to answer. And if you are interested in more details,
you can find our paper in this address. Welcome back, everybody. You were just listening to
ladder-leak, breaking ECGSA with less than one bit of non-sleekage. I have Diego and Akira right here
with me. Welcome back, everybody. Hello, hope you enjoyed the talk.
So, we have two questions. I'll start with the easy one first, because you answered in the
Discord chat. Again, we take questions in the Discord chat. So, would the speakers be able to
share their software on GitHub or so that we can rerun the research on the newer libraries?
Obviously, you're participating in the Discord chat. It's over there. Anything you want to add to that?
Yeah. So, yes. So, we already published a code in our repository. However, if you want to reproduce
our result, probably it's a bit difficult because we didn't document our code very well.
So, certainly, after we revise our paper, we'd like to also revise the documentation. And then,
hopefully, you can rerun the attack. 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.
Okay. Next question. 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?
So, I think you can classify roughly attacks against elliptic curves in two types. They could
be algebraic attacks against some specific class of curves that rely on the mathematical properties
of those curves to be effective. And usually, they destroy that class of curves from the
cryptographic perspective. 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. This basically kills supersingular curves for ACC. In this case, we have implementation
artifacts that allow an attacker to be effective against an implementation. 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. And then, it's about rigorously maximizing properties
of interesting curves that are standardized or maybe used in practice to see where they apply.
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.
Well, thank you. That was a fascinating talk. Let's just... we're going to say goodbye. So,
thanks again, Diego and Akira. Goodbye. Thank you. Enjoy the rest of the conference.