In “Practical, Round-Optimal Lattice-Based Blind Signatures” by Shweta Agrawal, Elena Kirshanova, Damien Stehle and Anshu Yadav, the authors introduce a new candidate hard lattice problem. They introduce this problem to build blind signatures but in this blog post, I’ll ignore the application and only talk about the cryptanalytic target: One-more-ISIS.
Tag: cryptanalysis
A Fun Bug? Help Wanted!
Over at Low BDD Estimate · Issue #33 Ben reports a bug that, on first sight and unfortunately, does not stand out much. For some unusual parameters the Lattice Estimator reports wrong results. Given that we rely on a variety of heuristics to keep the running time down and given that the whole thing is mostly developed on the side, this is – again, unfortunately – not surprising.
Debugging “corner cases” can often do wonders to improve the robustness of a given piece of software. For example, back in the days when I worked a lot on M4RI, as much as I dreaded fixing bugs that only showed up on Solaris boxes, those bugs always revealed some shady assumptions in my code that were bound to produce problems elsewhere down the line.
Indeed, I think this bug puts the finger on the heuristics we rely upon and where they can go wrong. The parameter sets that Ben has in mind are quite unusual in that we have to pick quite a large dimension 
On the other hand, truth be told, between this, the estimator being “mostly developed on the side” and all the other stuff I have to do, I doubt I’ll sink significant time into fixing this bug anytime soon.
But, and this is point of this post, perhaps someone would like to take this bug as an invitation to help to improve the Lattice Estimator? While, the estimator is quite widely relied upon to, well, estimate the difficulty of solving LWE and related problems, its bus factor is uncomfortably low. I’d say attempting to fix this bug would take whoever attempts to fix it on a whirlwind tour through the code base; a good way to learn it and to improve it.
Interested? Get in touch.
Lattice Estimator, Rebooted
We have “rebooted” the LWE Estimator as the Lattice Estimator. This was born out of frustration with the limitations of the old codebase.
-
Here is how we had to express, e.g., NIST Round 1 Kyber-512 for the “Estimate all the {LWE, NTRU} schemes!” project:
n = 512 sd = 1.5811388300841898 q = 7681 alpha = sqrt(2*pi)*sd/RR(q) m = n secret_distribution = "normal" primal_usvp(n, alpha, q, secret_distribution=secret_distribution, m=m)
In contrast, here’s how we express NIST Round 3 Kyber-512 now:
from estimator import * Kyber512 = LWE.Parameters( n=2 * 256, q=3329, Xs=ND.CenteredBinomial(3), Xe=ND.CenteredBinomial(3), m=2 * 256, tag="Kyber 512", )
That is, the user should not have to pretend their input distributions are some sort of Gaussians, the estimator should be able to handle standard distributions used in cryptography. Hopefully this makes using the estimator less error-prone.
-
It is well-established by now that making the Geometric Series Assumption for “primal attacks” on the Learning with Errors problem can be somewhat off. It is more precise to use a simulator to predict the shape after lattice reduction but the old estimator did not support this. Now we do:
lwe.primal_usvp(Kyber512, red_shape_model="GSA")
rop: ≈2^141.2, red: ≈2^141.2, δ: 1.004111, β: 382, d: 973, tag: usvp
lwe.primal_usvp(Kyber512, red_shape_model="CN11")
rop: ≈2^144.0, red: ≈2^144.0, δ: 1.004038, β: 392, d: 976, tag: usvp
The design is (hopefully) modular enough that you can plug in your favourite simulator.
-
The algorithms we costed were getting outdated. For example, we had these (really slow) estimates for the “decoding attack” that was essentially equivalent to computing a BKZ-ϐ reduced basis followed by calling an SVP oracle in some dimension η. This is now implemented as
primal_bdd.lwe.primal_bdd(Kyber512, red_shape_model="CN11")
rop: ≈2^140.5, red: ≈2^139.3, svp: ≈2^139.6, β: 375, η: 409, d: 969, tag: bdd
Similarly, our estimates for dual and hybrid attacks hadn’t kept up with the state of the art. Michael and Ben (both now at Zama) contributed code to fix that and have blogged about it here.
lwe.dual_hybrid(Kyber512)
rop: ≈2^157.7, mem: ≈2^153.6, m: 512, red: ≈2^157.4, δ: 1.003726, β: 440, d: 1008, ↻: ≈2^116.5, ζ: 16, tag: dual_hybrid
lwe.primal_hybrid(Kyber512)
rop: ≈2^276.4, red: ≈2^276.4, svp: ≈2^155.3, β: 381, η: 2, ζ: 0, |S|: 1, d: 1007, prob: ≈2^-133.2, ↻: ≈2^135.4, tag: hybrid
We’re still not complete (e.g. BKW with sieving is missing), but the more modular design, e.g. the one-big-Python-file-to-rule-them-all is no more, should make it easier to update the code.
- The rename is motivated by our ambition to add estimation modules for attacks on NTRU (not just viewing it as LWE) and SIS, too.
For most users, the usage should be fairly simple, e.g.
params = LWE.Parameters(n=700, q=next_prime(2^13), Xs=ND.UniformMod(3), Xe=ND.CenteredBinomial(8), m=1400, tag="KewLWE") _ = LWE.estimate.rough(params)
usvp :: rop: ≈2^153.9, red: ≈2^153.9, δ: 1.003279, β: 527, d: 1295, tag: usvp dual_hybrid :: rop: ≈2^178.9, mem: ≈2^175.1, m: 691, red: ≈2^178.7, δ: 1.002943, β: 612, d: 1360, ↻: 1, ζ: 31, tag: dual_hybrid
_ = LWE.estimate(params)
bkw :: rop: ≈2^210.4, m: ≈2^198.0, mem: ≈2^199.0, b: 15, t1: 0, t2: 16, ℓ: 14, #cod: 603, #top: 0, #test: 98, tag: coded-bkw usvp :: rop: ≈2^182.3, red: ≈2^182.3, δ: 1.003279, β: 527, d: 1295, tag: usvp bdd :: rop: ≈2^178.7, red: ≈2^178.1, svp: ≈2^177.2, β: 512, η: 543, d: 1289, tag: bdd dual :: rop: ≈2^207.8, mem: ≈2^167.1, m: 695, red: ≈2^207.6, δ: 1.002926, β: 617, d: 1394, ↻: ≈2^165.5, tag: dual dual_hybrid :: rop: ≈2^201.3, mem: ≈2^197.4, m: 676, red: ≈2^201.1, δ: 1.003008, β: 594, d: 1341, ↻: ≈2^141.9, ζ: 35, tag: dual_hybrid
If you are an attack algorithm designer, we would appreciate if you would contribute estimates for your algorithm to the estimator. If we already have support for it implemented, we would appreciate if you could compare our results against what you expect. If you are a scheme designer, we would appreciate if you could check if our results match what you expect. If you find suspicious behaviour or bugs, please open an issue on GitHub.
You can read the documentation here and play with the new estimator in your browser here (beware that Binder has a pretty low time-out, though).
On BDD with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem
Nadia and I put our pre-print and our source code online for solving bounded distance decoding when augmented with some predicate 
Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short.
We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work.
Mesh Messaging in Large-scale Protests: Breaking Bridgefy
Together with Jorge Blasco, Rikke Bjerg Jensen and Lenka Marekova we have studied the security of the Bridgefy mesh messaging application. This work was motivated by (social) media reports that this application was or is used by participants in large-scale protests in anticipation of or in response to government-mandated Internet shutdowns (or simply because the network infrastructure cannot handle as many devices at the same time as there are during such large protests). The first reports were about Hong Kong, later reports were then about India, Iran, US, Zimbabwe, Belarus and Thailand (typically referencing Hong Kong as an inspiration). In such a situation, mesh networking seems promising: a network is spanned between participants’ phones to create an ad-hoc local network to route messages.
Now, Bridgefy wasn’t designed with this use-case in mind. Rather, its designers had large sports events or natural disasters in mind. Leaving aside the discussion here if those use-cases too warrant a secure-by-default design, we had reason to suspect that the security offered by Bridgefy might not match the expectation of those who might rely on it.
Indeed, we found a series of vulnerabilities in Bridgefy. Our results show that Bridgefy currently permits its users to be tracked, offers no authenticity, no effective confidentiality protections and lacks resilience against adversarially crafted messages. We verify these vulnerabilities by demonstrating a series of practical attacks on Bridgefy. Thus, if protesters rely on Bridgefy, an adversary can produce social graphs about them, read their messages, impersonate anyone to anyone and shut down the entire network with a single maliciously crafted message. For a good overview, see Dan Goodin’s article on our work at Ars Technica.
We disclosed these vulnerabilities to the Bridgefy developers in April 2020 and agreed on a public disclosure date of 20 August 2020. Starting from 1 June 2020, the Bridgefy team began warning their users that they should not expect confidentiality guarantees from the current version of the application.
Let me stress, however, that, as of 24 August, Bridgefy has not been patched to fix these vulnerabilities and thus that these vulnerabilities are present in the currently deployed version. The developers are currently implementing/testing a switch to the Signal protocol to provide cryptographic assurances in their SDK. This switch, if done correctly, would rule out many of the attacks described in our work. They hope to have this fix deployed soon.
Continue reading “Mesh Messaging in Large-scale Protests: Breaking Bridgefy”
Revisiting the Expected Cost of Solving uSVP and Applications to LWE
Our — together with Florian Göpfert, Fernando Virdia and Thomas Wunderer — paper Revisiting the Expected Cost of Solving uSVP and Applications to LWE is now available on ePrint. Here’s the abstract:
Reducing the Learning with Errors problem (LWE) to the Unique-SVP problem and then applying lattice reduction is a commonly relied-upon strategy for estimating the cost of solving LWE-based constructions. In the literature, two different conditions are formulated under which this strategy is successful. One, widely used, going back to Gama & Nguyen’s work on predicting lattice reduction (Eurocrypt 2008) and the other recently outlined by Alkim et al. (USENIX 2016). Since these two estimates predict significantly different costs for solving LWE parameter sets from the literature, we revisit the Unique-SVP strategy. We present empirical evidence from lattice-reduction experiments exhibiting a behaviour in line with the latter estimate. However, we also observe that in some situations lattice-reduction behaves somewhat better than expected from Alkim et al.’s work and explain this behaviour under standard assumptions. Finally, we show that the security estimates of some LWE-based constructions from the literature need to be revised and give refined expected solving costs.
Our work is essentially concerned with spelling out in more detail and experimentally verifying a prediction made in the New Hope paper on when lattice reduction successfully recovers an unusually short vector.
Denoting by 
under the assumption that the Geometric Series Assumption holds (until a projection of the unusually short vector is found).
The rationale is that this condition ensures that the projection of 
In our work, we spell out this argument in more detail (e.g. how
matches the observed behaviour, e.g.
Just like for the above plots, the general answer is a clear “yes”.
Pretty Pictures or GTFO
I forgot the most important bit. The behaviour of the BKZ algorithm on uSVP(-BDD) instances can be observed in this video.
You can observe the basis approaching the GSA until the SVP oracle finds the unusually short vector 
Lucky Microseconds: A Timing Attack on Amazon’s s2n Implementation of TLS
Over the summer, Kenny Paterson and me spent some time looking at Amazon’s (Amazon Web Services – Labs to be precise) implementation of TLS. This implementation — called s2n — was released in June with the intent of providing a clean, easy to read, small implementation of a core subset of the TLS protocol.
Continue reading “Lucky Microseconds: A Timing Attack on Amazon’s s2n Implementation of TLS”
Sage Code for GGH Cryptanalysis by Hu and Jia
Recently, Yupu Hu and Huiwen Jia put a paper on the Cryptology ePrint Archive which describes a successful attack of the GGH (and GGHLite) candidate multilinear map. The attack does not try to recover the secret 
Continue reading “Sage Code for GGH Cryptanalysis by Hu and Jia”
On the concrete hardness of Learning with Errors
Together with Rachel Player and Sam Scott (both also from the Information Security Group at Royal Holloway, University of London) we finally managed to put our survey on solving the Learning with Errors problem out. Here’s the abstract:
The Learning with Errors (LWE) problem has become a central building block of modern cryptographic constructions. This work collects and presents hardness results for concrete instances of LWE. In particular, we discuss algorithms proposed in the literature and give the expected resources required to run them. We consider both generic instances of LWE as well as small secret variants. Since for several methods of solving LWE we require a lattice reduction step, we also review lattice reduction algorithms and use a refined model for estimating their running times. We also give concrete estimates for various families of LWE instances, provide a Sage module for computing these estimates and highlight gaps in the knowledge about algorithms for solving the Learning with Errors problem.
Continue reading “On the concrete hardness of Learning with Errors”
Cryptanalysis of the FHE based on GACD?
Jintai Ding and Chengdong Tao published a new preprint on the IACR’s ePrint titled A New Algorithm for Solving the Approximate Common Divisor Problem and Cryptanalysis of the FHE based on GACD.
*Abstract. *In this paper, we propose a new algorithm for solving the approximate common divisors problems, which is based on LLL reduction algorithm of certain special lattice and linear equation solving algorithm over integers. Through both theoretical argument and experimental data, we show that our new algorithm is a polynomial time algorithm under reasonable assumptions on the parameters. We use our algorithm to solve concrete problems that no other algorithm could solve before. Further more, we show that our algorithm can break the fully homomorphic encryption schemes, which are based on the approximate common divisors problem, in polynomial time in terms of the system parameter λ.
It is worth emphasising that the Approximate GCD problem not only underpinsone of the few fully homomorphic encryption schemes we have but it is also somewhat related to one of two candidates for multilinear maps. So if it could be shown to be easy then this would be somewhat sad as the choice of problems for building fancy crypto schemes would have gotten a lot smaller. So what is the Approxmiate GCD problem?
Approximate Greatest Common Divisions Problem: Given polynomially many samples x_{i} = q_{i}· p + r_{i} where x_{i} = O(2^{γ}), r_{i} = O(2^{ρ}) and p = O(2^{η}), recover p.
The algorithm proceeds by using the LLL algorithm to find relations .
Note that if enough such relations can be found then this gives a linear system of equations in the r_{j} which we’d only need to solve. So how does the algorithm use LLL to recover the a_{ij}? It sets up a lattice basis of dimension (t+1) × (t+1) as follows:
Here, N is simply a random integer O(2^{γ}). Now, the authors claim that running LLL on the lattice spanned by B returns about t-2 of the desired relations. They are unable to rigorously argue why this should happen but offer the following intuition. Any vector in the lattice spanned by B has the form . Considering the last component = = they speculate that that LLL would focus on the left hand side of this expression as the right hand side would be rather small anyway. Making implies which in turn implies , if I understood correctly.
An implementation of the first step of this algorithm for Sage is given here (in a Sage cell). Indeed, if you plug in the parameters from the authors’ table on page 9, we do get our desired relations out.
Finally, let’s look at the application to parameters as they are used in cryptography. The authors consider the fully homomorphic encryption scheme due to Marten van Dijkm Craig Gentry, Shai Halevi, Vinod Vaikuntanathan which sets γ = λ^{5}, η = λ^{2} and ρ = λ for a security level of λ, i.e. 2^{λ} operations should be needed to break it. Here is what the authors write:
We apply our algorithm to the parameters in [ 6 ] and we could break all the cases where their parameter γ < 2^{20}.
It is not really clear to me if the authors actually ran their attack or not. On the one hand, we have that a choice of parameters where γ < 2^{20} would correspond to λ=16 as (2^{20})^{(1/5)} = 2^{4}. Hence, attacking such dimensions would not mean much. On the other hand, the estimates by the authors about LLL would mean their attack would cost 2^{135} operations.
However, as far as I can tell, it does not work for these kind of parameters. That is, LLL fails to find the desired relations once we choose parameters as they are suggested in the cryptographic literature (cf. the example in the Sage cell above).
There are two reasons why the algorithm might fail:
- The target vectors might not be among the shortest vectors in the lattice. For the parameters on page 9 it seems this condition holds. It is not clear that the condition holds in general. While on page 7 the authors argue for the existence of target vectors within the approximation radius of LLL, the algorithm on page 8 expects vectors which are smaller than suggested by the Gaussian heuristic, which seems to be what is needed to me.
- The target vectors are the shortest vectors in the lattice. However, LLL cannot find them. In such a case it seems the situation is somewhat similar to the situation discussed in this comment from [[http://eprint.iacr.org/2009/616.pdf%5D%5B%5B6]]]:
On the other hand, when t is large, ~v likely is the shortest vector in L, but known lattice reductions algorithms will not be able to find it efficiently. Specifically, as a rule of thumb, they require time roughly 2^{(t/k)} to output a 2^{k} approximation of the shortest vector. Since clearly there are exponentially (in t) many vectors in L of length at most |x_{0}|√(t + 1) < 2^{γ}√(t + 1), which is about 2^{(η−ρ)} times longer than ~v, we need better than a 2^{(η−ρ)} approximation. For t ≥ γ/η, the time needed to guarantee a 2^{η} approximation (which is not even good enough to recover ~v) is roughly 2γ/η^{2}. Thus setting γ/η^{2} = ω(log λ) foils this attack.
So if I understand this correctly, they should have a condition on t which implies that the target vectors are smaller than what the Gaussian heuristic suggests by the appropriate LLL Unique SVP factor. In particular, they ask if there are target vectors with
|μ_i| < 1/√(t +1) 2^{(γ/(t+1) + t/4)}
but it should be more like
|μ_i| < τ/√(t +1) 2^{(γ/(t+1) – t/4)}
i.e. within the LLL approximation radius there shouldn’t be any other vectors (where τ is the Unique-SVP factor ~0.5).
Update: Since the authors show that if a short vector exists it must satisfy their conditions, this argument is invalid. Still, the authors did not show that they are able to find short enough vectors for parameters as they are found in the literature.
Of course, I might have missed something.
malb::blog 