17 ms·

Did Schnorr destroy RSA? Show me the factors

287 points by sweis 6y ago

jagger27 6y ago
That's really all there is to it. Pudding, proof, etc.
natch 6y ago
> the provenance of the paper has been confirmed: it is indeed Schnorr. What I read is that someone contacted Schnorr over email to get this confirmation. I’m not saying the confirmation is wrong. And I’m not saying email cannot convey information.
- ornxka 6y ago
  Well, it's definitely suspect now that RSA is broken.
  - xiphias2 6y ago
    So somebody cracked RSA and took over gmail.com domain just to fake him being Schnorr.
  - natch 6y ago
    Beautifully done.
- AnimalMuppet 6y ago
  "Email cannot convey information"? Baloney. It does all the time. You seem to mean something different from what your words say...
  - natch 6y ago
    “I’m not saying...” see?
    - AnimalMuppet 6y ago
      Did you edit that, or did I misread it?
      - natch 6y ago
        Actually come to think of it that’s a good question. Didn’t edit it adversarially if you know what I mean, nor long after posting, but there may have been a race condition as I was tweaking wording immediately after first saving. I see the edit indicator is there but I don’t recall if that exact portion was changed in the moment.
sodality2 6y ago
Factors or gtfo
- StavrosK 6y ago
  Get the factors out
tyingq 6y ago
Isn't it typical to release the paper first, for peer vetting, ahead of any actual working proof? It seems like the only reason for the "put up or shut up" reactions is that "destroys RSA" comment in the submitted abstract...which isn't in the actual paper.
- chrisseaton 6y ago
  > is that "destroys RSA" comment in the submitted abstract...which isn't in the actual paper I think it is - https://eprint.iacr.org/2021/232.pdf https://eprint.iacr.org/2021/232.pdf
  - tyingq 6y ago
    Ah, I see. It's been removed in a newer revision of the paper. https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
    - deleted 6y ago
      [deleted]
    - m4lvin 6y ago
      That times out for me, I guess www.math.uni-frankfurt.de is now getting more attention than usual ;-) Here is a version in the Google cache, it has an old date on it "work in progress 04.03.2020" and does not contain the "destroys RSA" sentence: https://webcache.googleusercontent.com/search?q=cache:E0L-S3UfRxUJ:https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://webcache.googleusercontent.com/search?q=cache:E0L-S3...
    - bhaney 6y ago
      Other way around I think. Your link is an old version of the paper. The one on eprint was just updated today with a version of the paper that adds the "destroys RSA" line and removes the "work in progress" line (put it in the wayback machine to see the version that was there yesterday without the claim of destroying RSA)
chrisco255 6y ago
For those of us less familiar with cryptography and RSA in general: what are the implications if RSA is broken? What are the mitigations that would need to occur in its place?
- aaomidi 6y ago
  1. We kinda knew RSA has an expiration date due to quantum computers. Assuming the paper is true, this just brought the expiration date far closer to us. 2. Major issue is going to be webpki and replaying govt captured encrypted communications. 3. There are a lot of abandoned servers out there that use RSA. There is a lot of code signing that uses RSA. There is just a lot of identity proven on the web that uses RSA to prove the identity. It's going to be a clusterfuck of identity. Again, assuming the paper means RSA is just completely broken.
  - dataflow 6y ago
    > 1. We kinda knew RSA has an expiration date due to quantum computers. Only if you somehow "know" quantum computing is ever going to be practically realized. It may never be.
    - deleted 6y ago
      [deleted]
    - freeone3000 6y ago
      There's no real big theoretical problems in the quantum computer building space. There's problems of scale, and funding, and usual growing pains of a new industry, but scale went from 7 to 24 fairly quickly and all it took was more money. If I gave IBM $10T dollars, they could build me a 1024-qbit computer. Once it gets cheaper, which is the current problem, I don't see any reason why Azure Quantum (ex) wouldn't simply decrease in price to where it can be used practically.
      - Laakeri 6y ago
        >There's no real big theoretical problems in the quantum computer building space The current quantum computers are just on the edge of what we can simulate classically, so we can't yet rule out the possibility that realizing a quantum computation requires an exponential amount of energy in the number of qubits. (Though it should be noted that quantum mechanics predicts that this will not happen.)
anonisko 6y ago
Reminiscent of Craig Wright's claim to be Satoshi. It doesn't matter what you claim with words if you can't back it up with cryptographic evidence. Shut up and prove you've done (or can do) the work.
- biolurker1 6y ago
  Are you really comparing a con artist with one of the most famous cryptographers?
  - anonisko 6y ago
    Dear lord no. I can see how it might come across like that. More drawing attention to the wider theme that we generally should not take people at their word when we have the option to demand proof of work that can't be faked or mistaken. Don't trust. Verify.
    - Ar-Curunir 6y ago
      These are not trivial algorithms to implement, and the other factorization records require months of work from implementation experts. It's not an easy task, and theory work stands independently of implementation effort.
      - wtallis 6y ago
        The claimed number of operations is low enough that demonstrating the algorithm in practice does not require a highly optimized implementation.
      - michaelt 6y ago
        Still, if this new algorithm could threaten 1024 bit RSA using 10,000 computers for 10,000 days after a 10,000x speed up from optimisation, it should be able to solve the RSA-896 factoring challenge with a single computer for a single day without optimisation, shouldn't it? After all, 2^896 is 38 orders of magnitude smaller than 2^1024.
- deleted 6y ago
tandr 6y ago
What does "36 bits of work" mean, sorry?
- bawolff 6y ago
  My naive assumption would be, takes 2^36 cpu operations
  - ISL 6y ago
    If so, 2^36 ~ 7 x 10^10, so a few seconds on GHz processors.
  - wtallis 6y ago
    2^36 arithmetic operations is what is claimed. That's not quite the same as CPU operations, because we only have 64-bit CPUs with up to 512-bit vector instructions, but we're talking about factoring 800-bit numbers. So we need to allow for several CPU instructions to implement each of the required arithmetic operations.
- jtsiskin 6y ago
  Yeah I would be great if they could translate that into core-years to match the references they listed
- aDfbrtVt 6y ago
  I'm guessing it's a shorthand for the order of units of work. log2(8.4E10) = 36.3 bits of operations
tgsovlerkhgsel 6y ago
Devil's advocate: Posting the factors requires implementation work, then optimization, then a manageable but possibly still not trivial amount of resources and time - and likely a lot of trial and error. It is perfectly conceivable that a paper would be published before the implementation is actually better than a slower but heavily optimized approach. (I don't even try to understand the paper, but I've seen a mention that it's a storage tradeoff, which may make it a very different kind of optimization problem.) Do we know that the paper is definitely from Schnorr? (Edit: The article claims its provenance is confirmed). The "destroys the RSA cryptosystem" claim is now part of the paper. While anyone can make mistakes, I would expect such claims to be at least somewhat carefully checked before releasing them. Either way, I expect that we'll see either a retraction/correction or factors within weeks.
jMyles 6y ago
I'm skeptical. The paper is too tough for me to digest without spending days/weeks/lifetimes focusing on it (and there are many who can do it much faster obviously). But I think that if RSA is materially broken, we'll know it from movements in the ground (eg, sudden mysterious forged signatures) by the time a paper is published. I don't think that such a secret can be kept for more than a few minutes with immediately proceeding to runtime weaponization.
NoKnowledge 6y ago
This take is rather naive. Those RSA factoring records were done by a large international team of researchers, using well established algorithms and decades of work on implementing those methods as fast as possible. The blog post says the paper mentions 8.4e10 operations for factoring, but I can't find that number in the paper anywhere. The post then states: "The 800-bit claims would be 36 bits of work." I don't know what that means. [edit]: the numbers are in the new version (https://eprint.iacr.org/2021/232 https://eprint.iacr.org/2021/232). I was looking at the old version uploaded yesterday.
- contravariant 6y ago
  It's in the abstract: >Our accelerated strongprimal-dual reduction of [GN08] factors integers N≈2^400 and N≈2^800 by 4.2·10^9 and 8.4·10^10 arithmetic operations.
  - AnimalMuppet 6y ago
    Increasing the length by a factor of 2^400 only increased the amount of work by a factor of 20? Staggering, if true in general.
    - vitus 6y ago
      Actually, you're only increasing the length of the number by a factor of 2, since 2^400 is a 400-bit number. If true, it's still leaps and bounds ahead of anything we have today, though.
      - AnimalMuppet 6y ago
        Fair point. "Increasing the key [not the length of the key] by a factor of 2^400".
    - ajarmst 6y ago
      Yeah, that's what got me. Doubling the length of the key only requires a single order of magnitude more work?. If that turns out to be true, I'm going to need to revise my beliefs about how the universe works. In particular, information theory and thermodynamics, because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. (Caveat: if the values of primes turn out to have a predictable pattern, that could provide the needed information. However, that would mean that the Riemann Hypothesis is false, and that'd be an even more astounding result.)
hn_throwaway_99 6y ago
This was my exact argument: https://news.ycombinator.com/item?id=26323951 https://news.ycombinator.com/item?id=26323951 Should be trivial to show a working proof on a smaller-than-usual RSA number if "this really destroys RSA".
racecar789 6y ago
I know a lot of programming languages, but I have never wrapped my head around math notation. Question for someone who is familiar math notation...was the abstract of this article easy to understand? For me, the abstract seems like code but no commentary explaining what each bloc does. But I could be mistaken.
- woah 6y ago
  You will not be able to understand the notation if you do not understand the math
- nightcracker 6y ago
  For context: I'm a computer science MSc student. The notation is easy to understand (and as far as mathematical notation goes, really quite tame). I don't know what a nearly shortest vector of a lattice is in this context, but I do understand everything else. Note that means I have no idea how the actual method works, but I can understand what's being claimed.
  - sterlind 6y ago
    Not an expert at all, but you can think of lattices as evenly-spaced grid points in a vector space. Given a set of basis vectors b0..bn, and arbitrary integers a0..an, a0b0 + ... + anbn are points on the lattice b. You can have a "good basis" where the norms for b are low, or an equivalent "bad basis" with the same lattice points but with high norms. That's one hard problem (lattice reduction), but there are polynomial-time approximations. The shortest vector problem, iirc, is to find the vector with the smallest norm in the best possible basis of that lattice.
- wtallis 6y ago
  The first half of the abstract is more akin to declaring the data types and structures used, and the second half is mostly a very high level summary of the overall method and results. It's not supposed to be interpreted like code. It's just setting up the context you need to start interpreting the meat of the paper, and giving you a heads-up about what background topics to Google if anything in the abstract sounds unfamiliar.
gojomo 6y ago
I can imagine a certain pure-theorist mindset being confident enough in their reasoning, but not yet their coding, to report this first. Or, strategically holding definitive proof back as a hammer to deploy once the doubters reveal themselves. Why not let others do the rote reduction-to-practice? Why not create an example where your theory was correct, & your reputation was on the line, that took a little while to resolve – but when it does, it does so definitively in your favor, so you are more trusted in future pre-definitive-verification pronouncements? (I don't know enough about Schnorr-the-person to know if this fits his personality, but I can imagine such personalities.)
dang 6y ago
This was heavily discussed yesterday. (Edit: this next bit was out of date:) It seems the provenance of the paper and the 'destroy' claim are unclear. “This destroys the RSA cryptosystem” - https://news.ycombinator.com/item?id=26321962 https://news.ycombinator.com/item?id=26321962 - March 2021 (140 comments)
- john_alan 6y ago
  Nah it’s confirmed as from Schnorr. He even reiterated his belief it leaves RSA rekt. All that’s left is the veracity of the attack.
  - dang 6y ago
    Ok thanks! I was out of date.
abetusk 6y ago
OK, here is a brief overview for people: To factor a number N (assumed to essentially be the product of two very large primes), find a 'short' lattice vector [0] using LLL [1] (and BKZ reduction? [2]) that finds many relations of the form: (u_i) = p_i,0 * p_{i,1} * ... * p_{i,n-1} (u_i - v_i * N) = q_{i,0} * q_{i,1} * ... * q_{i,n-1} where p,q are small primes. Numbers that have all their factors less than some prime, B, are said to be "B-smooth". In the above, both (u_i) and (u_i - v_i * N) are p_{i,n-1}-smooth and q_{i,n-1}-smooth, respectively. Construct many u_i and (u_i - v_i * N), so much so that you can create a product of primes, r_i, of the form: r_0^{2 b_0} * r_1^{2 b_1} * ... * r_{n-1}^{2 b_{n-1}} = 1 mod N where each b_i are integers. Since all exponents (2b_i) are even, we have the potential to find the square root of 1 which has the potential to resolve to two different numbers since N is composite. One of those is the product of r_i^{b_i} and the other is -1. Since y^2 = 1 mod N, we get (y-1)(y+1) = 0 mod N. If (y-1) or (y+1) are not 0, then then must share a factor of N and we've successfully factored. The trick is, of course, finding the smooth numbers. To do this, a lattice basis is made such that you find a short integer relation of the form a_0 ln(p_0) + a_1 ln(p_1) + ... + a_{n-1} ln(p_{n-1}) ~= ln(N) where ~= means "approximately equal to". u is chosen as the product of primes of all a_i > 0 and v is chosen to be the product of all primes where a_i < 0. The hope is that (u - v*N) is also p_{n-1}-smooth, which, as far as I understand, most of the math in the paper is trying to justify. The main innovation here, as far as I can tell, is that Schnorr is fiddling with the 'weighting' of the main diagonal when constructing the lattice basis. I interpret this as basically trying to randomize the initial lattice basis so that the chances of getting a different integer relation (for eventual construction of u,v) is more probable. I've been confused about this for over a decade as variants of this algorithm, and Schnorr's work in general, have been well published. For example, there's a paper from 2010 on "A Note on Integer Factorization Using Lattices" by Antonio Vera which discusses Schnorr's [3] construction. Is Schnorr trying to shout louder so people will listen or is there something else fundamentally flawed with this type of algorithm? Just a word of warning, LLL solves polynomial factorization in polynomial time (given a polynomial with integer coefficients, find it's factor polynomials also with integer coefficients) [4] and has been used to break other (now very old) cryptosystems [5]. If there's a candidate algorithm to solve integer factoring, lattice reduction (LLL, PSLQ, etc.) are it. I know of fplll that's a stand alone (FOSS) implementation of LLL and some extensions (BKZ, etc.) [6]. [0] https://en.wikipedia.org/wiki/Lattice_reduction https://en.wikipedia.org/wiki/Lattice_reduction [1] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%... [2] https://www.newton.ac.uk/files/seminar/20140509093009501-202978.pdf https://www.newton.ac.uk/files/seminar/20140509093009501-202... [3] https://arxiv.org/pdf/1003.5461.pdf https://arxiv.org/pdf/1003.5461.pdf [4] https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers https://en.wikipedia.org/wiki/Factorization_of_polynomials#F... [5] https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf [6] https://github.com/fplll/fplll https://github.com/fplll/fplll
TacticalCoder 6y ago
I am no cryptographer. I did implement, from the paper, Yao's "socialist millionaire" cryptographic protocol but... It was only a few lines of code and a very simple (to understand, not to come up with) paper. Now I just looked at that Schnorr paper and, well, I can tell you that I'm not going to be the one implementing it : (
bhouston 6y ago
The first thing this will be used for is stealing Bitcoin and other cryptocurrency I predict. So watch out for your wallets.
- kinghajj 6y ago
  Bitcoin wallets don't use RSA, but ECDSA.
  - bhouston 6y ago
    I was referring to the possibility of man in the middle attacks on Bitcoin applications.
- postalrat 6y ago
  Once people figure out the math to break bitcoin then they can transfer bitcoin from any address. I don't know why people don't bring this up more often. It will likely happen long before quantum computers make it possible.
  - kinghajj 6y ago
    Because, simply, it's not true. I'm curious though what attack vector you're thinking of, especially one that's not related to quantum computers. Are you worried that the ECDSA public-key cryptosystem employed by Bitcoin will be broken, such that the private keys could somehow get derived easily from the public ones? If so, that still wouldn't let an attacker "transfer bitcoin from any address," since the addresses themselves are hashes of the public keys. So people would have to stop re-using addresses to receive bitcoin multiple times, since once an address has been the sender in a transaction, and its public key revealed, it would become vulnerable.
hertzrat 6y ago
If someone wasn’t a cryptographer, but does occasional security tasks at work, what is the takeaway? RSA needs to be 4096 or higher now, or that similar techniques in the future might make RSA a bad choice altogether?
- owenmarshall 6y ago
  Don’t worry - yet. This is either a nothingburger, or it’s going to be a nightmare for everyone, all at once (ever dealt with web PKI? you will get a chance if this is true) But there’s no real current takeaway until we know if this approach works, and if so how extensible it is to RSA, especially 2048 bit RSA.
- marcosdumay 6y ago
  There are plenty of techniques in the past that make RSA a bad choice altogether. If you are going with it anyway, yeah, 4k bits is a safe choice for making it reasonably secure right now (2k being a bare minimum), but remember, attacks always get better, never worse, and RSA has a fair share of possible attacks.
senderista 6y ago
I wonder if Schnorr is going senile like Atiyah.
shashasha2 6y ago
Is prime factorisation used in SHA256 ? Would I be able to solo mine from my CPU again ?
- runeks 6y ago
  No. Prime factorization is used for public key cryptography, not hashing.
- unnouinceput 6y ago
  No, to both questions. Implementing SHA256 is actually quite easy, no more than 50 lines of code. My current implementation that I use for my personal use is under 100 lines of code including variable declarations (not just executable lines of code). https://en.wikipedia.org/wiki/SHA-2 https://en.wikipedia.org/wiki/SHA-2
unnouinceput 6y ago
An example, by hand, from the paper author, where he is using this algorithm to factor a number would be great. Even a small number that's easy to factor by brute force would be enough to actually proof that his claims are true. We'll do code implementation and run it against RSA challenge numbers, and see if this is a prank or the real deal.
yipbub 6y ago
Crypto noob question: Wouldn't it be prudent to switch to something like ECDSA(heardsay that it is stronger) if there was even a hint that it was possible? If a major government got wind that such work was going on, wouldn't it be prudent to publish before you are disappeared? I assume high-profile crypto research people are spied on.
paob 6y ago
Here we have Léo Ducas testing Schnorr's new method in Sage: https://github.com/lducas/SchnorrGate https://github.com/lducas/SchnorrGate Apparently, "[t]his suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21]."
- ianbooker 6y ago
  CP Schnorr is emeritus professor from Frankfurt university. He is respected for his work in cryptography. He has, pun intended, nothing to prove but still works and furthers research. Yes, claiming that "this breaks RSA" is bold, but this implementation shows that there is some advance in doing so in the paper. Therefore signaling that this is a "scandal" via the postfix "gate" seems just inappropriate. Apart from that kudos for the implementation to Ducas! Calling it the "Schnorr attack" would imply that the outcome of it is still uncertain. And it also would sound way cooler ;)
  - paob 6y ago
    I recommend you contact Ducas to tell him about your concerns directly. I do not know him personally as I first heard about this from his public Twitter account: https://twitter.com/DucasLeo https://twitter.com/DucasLeo Just to make sure you get Ducas's main argument, I quote him here again: "Personal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well." So it seems like the conclusion is clear-cut contrary to what you were suggesting. Also wouldn't the name "Schnorr attack" lead to people thinking of attacks on Schnorr signatures instead?
    - ianbooker 6y ago
      Good point on the signatures.
deleted 6y ago
[deleted]

287 points by sweis 6y ago

That's really all there is to it. Pudding, proof, etc.

> the provenance of the paper has been confirmed: it is indeed Schnorr. What I read is that someone contacted Schnorr over email to get this confirmation. I’m not saying the confirmation is wrong. And I’m not saying email cannot convey information.

ornxka 6y ago
Well, it's definitely suspect now that RSA is broken.
- xiphias2 6y ago
  So somebody cracked RSA and took over gmail.com domain just to fake him being Schnorr.
- natch 6y ago
  Beautifully done.
AnimalMuppet 6y ago
"Email cannot convey information"? Baloney. It does all the time. You seem to mean something different from what your words say...
- natch 6y ago
  “I’m not saying...” see?
  - AnimalMuppet 6y ago
    Did you edit that, or did I misread it?
    - natch 6y ago
      Actually come to think of it that’s a good question. Didn’t edit it adversarially if you know what I mean, nor long after posting, but there may have been a race condition as I was tweaking wording immediately after first saving. I see the edit indicator is there but I don’t recall if that exact portion was changed in the moment.

sodality2 6y ago

Factors or gtfo

StavrosK 6y ago
Get the factors out

tyingq 6y ago

Isn't it typical to release the paper first, for peer vetting, ahead of any actual working proof? It seems like the only reason for the "put up or shut up" reactions is that "destroys RSA" comment in the submitted abstract...which isn't in the actual paper.

chrisseaton 6y ago
> is that "destroys RSA" comment in the submitted abstract...which isn't in the actual paper I think it is - https://eprint.iacr.org/2021/232.pdf https://eprint.iacr.org/2021/232.pdf
- tyingq 6y ago
  Ah, I see. It's been removed in a newer revision of the paper. https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
  - deleted 6y ago
    [deleted]
  - m4lvin 6y ago
    That times out for me, I guess www.math.uni-frankfurt.de is now getting more attention than usual ;-) Here is a version in the Google cache, it has an old date on it "work in progress 04.03.2020" and does not contain the "destroys RSA" sentence: https://webcache.googleusercontent.com/search?q=cache:E0L-S3UfRxUJ:https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://webcache.googleusercontent.com/search?q=cache:E0L-S3...
  - bhaney 6y ago
    Other way around I think. Your link is an old version of the paper. The one on eprint was just updated today with a version of the paper that adds the "destroys RSA" line and removes the "work in progress" line (put it in the wayback machine to see the version that was there yesterday without the claim of destroying RSA)

chrisco255 6y ago

For those of us less familiar with cryptography and RSA in general: what are the implications if RSA is broken? What are the mitigations that would need to occur in its place?

aaomidi 6y ago
1. We kinda knew RSA has an expiration date due to quantum computers. Assuming the paper is true, this just brought the expiration date far closer to us. 2. Major issue is going to be webpki and replaying govt captured encrypted communications. 3. There are a lot of abandoned servers out there that use RSA. There is a lot of code signing that uses RSA. There is just a lot of identity proven on the web that uses RSA to prove the identity. It's going to be a clusterfuck of identity. Again, assuming the paper means RSA is just completely broken.
- dataflow 6y ago
  > 1. We kinda knew RSA has an expiration date due to quantum computers. Only if you somehow "know" quantum computing is ever going to be practically realized. It may never be.
  - deleted 6y ago
    [deleted]
  - freeone3000 6y ago
    There's no real big theoretical problems in the quantum computer building space. There's problems of scale, and funding, and usual growing pains of a new industry, but scale went from 7 to 24 fairly quickly and all it took was more money. If I gave IBM $10T dollars, they could build me a 1024-qbit computer. Once it gets cheaper, which is the current problem, I don't see any reason why Azure Quantum (ex) wouldn't simply decrease in price to where it can be used practically.
    - Laakeri 6y ago
      >There's no real big theoretical problems in the quantum computer building space The current quantum computers are just on the edge of what we can simulate classically, so we can't yet rule out the possibility that realizing a quantum computation requires an exponential amount of energy in the number of qubits. (Though it should be noted that quantum mechanics predicts that this will not happen.)

anonisko 6y ago

Reminiscent of Craig Wright's claim to be Satoshi. It doesn't matter what you claim with words if you can't back it up with cryptographic evidence. Shut up and prove you've done (or can do) the work.

biolurker1 6y ago
Are you really comparing a con artist with one of the most famous cryptographers?
- anonisko 6y ago
  Dear lord no. I can see how it might come across like that. More drawing attention to the wider theme that we generally should not take people at their word when we have the option to demand proof of work that can't be faked or mistaken. Don't trust. Verify.
  - Ar-Curunir 6y ago
    These are not trivial algorithms to implement, and the other factorization records require months of work from implementation experts. It's not an easy task, and theory work stands independently of implementation effort.
    - wtallis 6y ago
      The claimed number of operations is low enough that demonstrating the algorithm in practice does not require a highly optimized implementation.
    - michaelt 6y ago
      Still, if this new algorithm could threaten 1024 bit RSA using 10,000 computers for 10,000 days after a 10,000x speed up from optimisation, it should be able to solve the RSA-896 factoring challenge with a single computer for a single day without optimisation, shouldn't it? After all, 2^896 is 38 orders of magnitude smaller than 2^1024.
deleted 6y ago

tandr 6y ago

What does "36 bits of work" mean, sorry?

bawolff 6y ago
My naive assumption would be, takes 2^36 cpu operations
- ISL 6y ago
  If so, 2^36 ~ 7 x 10^10, so a few seconds on GHz processors.
- wtallis 6y ago
  2^36 arithmetic operations is what is claimed. That's not quite the same as CPU operations, because we only have 64-bit CPUs with up to 512-bit vector instructions, but we're talking about factoring 800-bit numbers. So we need to allow for several CPU instructions to implement each of the required arithmetic operations.
jtsiskin 6y ago
Yeah I would be great if they could translate that into core-years to match the references they listed
aDfbrtVt 6y ago
I'm guessing it's a shorthand for the order of units of work. log2(8.4E10) = 36.3 bits of operations

tgsovlerkhgsel 6y ago

Devil's advocate: Posting the factors requires implementation work, then optimization, then a manageable but possibly still not trivial amount of resources and time - and likely a lot of trial and error. It is perfectly conceivable that a paper would be published before the implementation is actually better than a slower but heavily optimized approach. (I don't even try to understand the paper, but I've seen a mention that it's a storage tradeoff, which may make it a very different kind of optimization problem.) Do we know that the paper is definitely from Schnorr? (Edit: The article claims its provenance is confirmed). The "destroys the RSA cryptosystem" claim is now part of the paper. While anyone can make mistakes, I would expect such claims to be at least somewhat carefully checked before releasing them. Either way, I expect that we'll see either a retraction/correction or factors within weeks.

jMyles 6y ago

I'm skeptical. The paper is too tough for me to digest without spending days/weeks/lifetimes focusing on it (and there are many who can do it much faster obviously). But I think that if RSA is materially broken, we'll know it from movements in the ground (eg, sudden mysterious forged signatures) by the time a paper is published. I don't think that such a secret can be kept for more than a few minutes with immediately proceeding to runtime weaponization.

NoKnowledge 6y ago

This take is rather naive. Those RSA factoring records were done by a large international team of researchers, using well established algorithms and decades of work on implementing those methods as fast as possible. The blog post says the paper mentions 8.4e10 operations for factoring, but I can't find that number in the paper anywhere. The post then states: "The 800-bit claims would be 36 bits of work." I don't know what that means. [edit]: the numbers are in the new version (https://eprint.iacr.org/2021/232 https://eprint.iacr.org/2021/232). I was looking at the old version uploaded yesterday.

contravariant 6y ago
It's in the abstract: >Our accelerated strongprimal-dual reduction of [GN08] factors integers N≈2^400 and N≈2^800 by 4.2·10^9 and 8.4·10^10 arithmetic operations.
- AnimalMuppet 6y ago
  Increasing the length by a factor of 2^400 only increased the amount of work by a factor of 20? Staggering, if true in general.
  - vitus 6y ago
    Actually, you're only increasing the length of the number by a factor of 2, since 2^400 is a 400-bit number. If true, it's still leaps and bounds ahead of anything we have today, though.
    - AnimalMuppet 6y ago
      Fair point. "Increasing the key [not the length of the key] by a factor of 2^400".
  - ajarmst 6y ago
    Yeah, that's what got me. Doubling the length of the key only requires a single order of magnitude more work?. If that turns out to be true, I'm going to need to revise my beliefs about how the universe works. In particular, information theory and thermodynamics, because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. (Caveat: if the values of primes turn out to have a predictable pattern, that could provide the needed information. However, that would mean that the Riemann Hypothesis is false, and that'd be an even more astounding result.)

hn_throwaway_99 6y ago

This was my exact argument: https://news.ycombinator.com/item?id=26323951 https://news.ycombinator.com/item?id=26323951 Should be trivial to show a working proof on a smaller-than-usual RSA number if "this really destroys RSA".

racecar789 6y ago

I know a lot of programming languages, but I have never wrapped my head around math notation. Question for someone who is familiar math notation...was the abstract of this article easy to understand? For me, the abstract seems like code but no commentary explaining what each bloc does. But I could be mistaken.

woah 6y ago
You will not be able to understand the notation if you do not understand the math
nightcracker 6y ago
For context: I'm a computer science MSc student. The notation is easy to understand (and as far as mathematical notation goes, really quite tame). I don't know what a nearly shortest vector of a lattice is in this context, but I do understand everything else. Note that means I have no idea how the actual method works, but I can understand what's being claimed.
- sterlind 6y ago
  Not an expert at all, but you can think of lattices as evenly-spaced grid points in a vector space. Given a set of basis vectors b0..bn, and arbitrary integers a0..an, a0b0 + ... + anbn are points on the lattice b. You can have a "good basis" where the norms for b are low, or an equivalent "bad basis" with the same lattice points but with high norms. That's one hard problem (lattice reduction), but there are polynomial-time approximations. The shortest vector problem, iirc, is to find the vector with the smallest norm in the best possible basis of that lattice.
wtallis 6y ago
The first half of the abstract is more akin to declaring the data types and structures used, and the second half is mostly a very high level summary of the overall method and results. It's not supposed to be interpreted like code. It's just setting up the context you need to start interpreting the meat of the paper, and giving you a heads-up about what background topics to Google if anything in the abstract sounds unfamiliar.

gojomo 6y ago

I can imagine a certain pure-theorist mindset being confident enough in their reasoning, but not yet their coding, to report this first. Or, strategically holding definitive proof back as a hammer to deploy once the doubters reveal themselves. Why not let others do the rote reduction-to-practice? Why not create an example where your theory was correct, & your reputation was on the line, that took a little while to resolve – but when it does, it does so definitively in your favor, so you are more trusted in future pre-definitive-verification pronouncements? (I don't know enough about Schnorr-the-person to know if this fits his personality, but I can imagine such personalities.)

dang 6y ago

This was heavily discussed yesterday. (Edit: this next bit was out of date:) It seems the provenance of the paper and the 'destroy' claim are unclear. “This destroys the RSA cryptosystem” - https://news.ycombinator.com/item?id=26321962 https://news.ycombinator.com/item?id=26321962 - March 2021 (140 comments)

john_alan 6y ago
Nah it’s confirmed as from Schnorr. He even reiterated his belief it leaves RSA rekt. All that’s left is the veracity of the attack.
- dang 6y ago
  Ok thanks! I was out of date.

abetusk 6y ago

OK, here is a brief overview for people: To factor a number N (assumed to essentially be the product of two very large primes), find a 'short' lattice vector [0] using LLL [1] (and BKZ reduction? [2]) that finds many relations of the form: (u_i) = p_i,0 * p_{i,1} * ... * p_{i,n-1} (u_i - v_i * N) = q_{i,0} * q_{i,1} * ... * q_{i,n-1} where p,q are small primes. Numbers that have all their factors less than some prime, B, are said to be "B-smooth". In the above, both (u_i) and (u_i - v_i * N) are p_{i,n-1}-smooth and q_{i,n-1}-smooth, respectively. Construct many u_i and (u_i - v_i * N), so much so that you can create a product of primes, r_i, of the form: r_0^{2 b_0} * r_1^{2 b_1} * ... * r_{n-1}^{2 b_{n-1}} = 1 mod N where each b_i are integers. Since all exponents (2b_i) are even, we have the potential to find the square root of 1 which has the potential to resolve to two different numbers since N is composite. One of those is the product of r_i^{b_i} and the other is -1. Since y^2 = 1 mod N, we get (y-1)(y+1) = 0 mod N. If (y-1) or (y+1) are not 0, then then must share a factor of N and we've successfully factored. The trick is, of course, finding the smooth numbers. To do this, a lattice basis is made such that you find a short integer relation of the form a_0 ln(p_0) + a_1 ln(p_1) + ... + a_{n-1} ln(p_{n-1}) ~= ln(N) where ~= means "approximately equal to". u is chosen as the product of primes of all a_i > 0 and v is chosen to be the product of all primes where a_i < 0. The hope is that (u - v*N) is also p_{n-1}-smooth, which, as far as I understand, most of the math in the paper is trying to justify. The main innovation here, as far as I can tell, is that Schnorr is fiddling with the 'weighting' of the main diagonal when constructing the lattice basis. I interpret this as basically trying to randomize the initial lattice basis so that the chances of getting a different integer relation (for eventual construction of u,v) is more probable. I've been confused about this for over a decade as variants of this algorithm, and Schnorr's work in general, have been well published. For example, there's a paper from 2010 on "A Note on Integer Factorization Using Lattices" by Antonio Vera which discusses Schnorr's [3] construction. Is Schnorr trying to shout louder so people will listen or is there something else fundamentally flawed with this type of algorithm? Just a word of warning, LLL solves polynomial factorization in polynomial time (given a polynomial with integer coefficients, find it's factor polynomials also with integer coefficients) [4] and has been used to break other (now very old) cryptosystems [5]. If there's a candidate algorithm to solve integer factoring, lattice reduction (LLL, PSLQ, etc.) are it. I know of fplll that's a stand alone (FOSS) implementation of LLL and some extensions (BKZ, etc.) [6]. [0] https://en.wikipedia.org/wiki/Lattice_reduction https://en.wikipedia.org/wiki/Lattice_reduction [1] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%... [2] https://www.newton.ac.uk/files/seminar/20140509093009501-202978.pdf https://www.newton.ac.uk/files/seminar/20140509093009501-202... [3] https://arxiv.org/pdf/1003.5461.pdf https://arxiv.org/pdf/1003.5461.pdf [4] https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers https://en.wikipedia.org/wiki/Factorization_of_polynomials#F... [5] https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf [6] https://github.com/fplll/fplll https://github.com/fplll/fplll

TacticalCoder 6y ago

I am no cryptographer. I did implement, from the paper, Yao's "socialist millionaire" cryptographic protocol but... It was only a few lines of code and a very simple (to understand, not to come up with) paper. Now I just looked at that Schnorr paper and, well, I can tell you that I'm not going to be the one implementing it : (

bhouston 6y ago

The first thing this will be used for is stealing Bitcoin and other cryptocurrency I predict. So watch out for your wallets.

kinghajj 6y ago
Bitcoin wallets don't use RSA, but ECDSA.
- bhouston 6y ago
  I was referring to the possibility of man in the middle attacks on Bitcoin applications.
postalrat 6y ago
Once people figure out the math to break bitcoin then they can transfer bitcoin from any address. I don't know why people don't bring this up more often. It will likely happen long before quantum computers make it possible.
- kinghajj 6y ago
  Because, simply, it's not true. I'm curious though what attack vector you're thinking of, especially one that's not related to quantum computers. Are you worried that the ECDSA public-key cryptosystem employed by Bitcoin will be broken, such that the private keys could somehow get derived easily from the public ones? If so, that still wouldn't let an attacker "transfer bitcoin from any address," since the addresses themselves are hashes of the public keys. So people would have to stop re-using addresses to receive bitcoin multiple times, since once an address has been the sender in a transaction, and its public key revealed, it would become vulnerable.

hertzrat 6y ago

If someone wasn’t a cryptographer, but does occasional security tasks at work, what is the takeaway? RSA needs to be 4096 or higher now, or that similar techniques in the future might make RSA a bad choice altogether?

owenmarshall 6y ago
Don’t worry - yet. This is either a nothingburger, or it’s going to be a nightmare for everyone, all at once (ever dealt with web PKI? you will get a chance if this is true) But there’s no real current takeaway until we know if this approach works, and if so how extensible it is to RSA, especially 2048 bit RSA.
marcosdumay 6y ago
There are plenty of techniques in the past that make RSA a bad choice altogether. If you are going with it anyway, yeah, 4k bits is a safe choice for making it reasonably secure right now (2k being a bare minimum), but remember, attacks always get better, never worse, and RSA has a fair share of possible attacks.

senderista 6y ago

I wonder if Schnorr is going senile like Atiyah.

shashasha2 6y ago

Is prime factorisation used in SHA256 ? Would I be able to solo mine from my CPU again ?

runeks 6y ago
No. Prime factorization is used for public key cryptography, not hashing.
unnouinceput 6y ago
No, to both questions. Implementing SHA256 is actually quite easy, no more than 50 lines of code. My current implementation that I use for my personal use is under 100 lines of code including variable declarations (not just executable lines of code). https://en.wikipedia.org/wiki/SHA-2 https://en.wikipedia.org/wiki/SHA-2

unnouinceput 6y ago

An example, by hand, from the paper author, where he is using this algorithm to factor a number would be great. Even a small number that's easy to factor by brute force would be enough to actually proof that his claims are true. We'll do code implementation and run it against RSA challenge numbers, and see if this is a prank or the real deal.

yipbub 6y ago

Crypto noob question: Wouldn't it be prudent to switch to something like ECDSA(heardsay that it is stronger) if there was even a hint that it was possible? If a major government got wind that such work was going on, wouldn't it be prudent to publish before you are disappeared? I assume high-profile crypto research people are spied on.

paob 6y ago

Here we have Léo Ducas testing Schnorr's new method in Sage: https://github.com/lducas/SchnorrGate https://github.com/lducas/SchnorrGate Apparently, "[t]his suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21]."

ianbooker 6y ago
CP Schnorr is emeritus professor from Frankfurt university. He is respected for his work in cryptography. He has, pun intended, nothing to prove but still works and furthers research. Yes, claiming that "this breaks RSA" is bold, but this implementation shows that there is some advance in doing so in the paper. Therefore signaling that this is a "scandal" via the postfix "gate" seems just inappropriate. Apart from that kudos for the implementation to Ducas! Calling it the "Schnorr attack" would imply that the outcome of it is still uncertain. And it also would sound way cooler ;)
- paob 6y ago
  I recommend you contact Ducas to tell him about your concerns directly. I do not know him personally as I first heard about this from his public Twitter account: https://twitter.com/DucasLeo https://twitter.com/DucasLeo Just to make sure you get Ducas's main argument, I quote him here again: "Personal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well." So it seems like the conclusion is clear-cut contrary to what you were suggesting. Also wouldn't the name "Schnorr attack" lead to people thinking of attacks on Schnorr signatures instead?
  - ianbooker 6y ago
    Good point on the signatures.

deleted 6y ago

[deleted]