Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

https://twitter.com/FredericJacobs/status/1367115794363088897

by EthanHeilman • 5 years ago

236 72 5 years ago

j_walter2• 5 years ago

It doesn't destroy it...at best it weakens the lower RSA bit keys. If it destroys it...why not prove it with a PoC on one of the RSA numbers that hasn't been factored yet. RSA-260 is still open...

EthanHeilman3• 5 years ago

On one hand I am skeptical about strong claims especially in the early stage of the claim. On the other hand Schnorr is the person claiming it and no one has refuted it yet. I wonder how long until we will know for certain.

j_walter2• 5 years ago

The paper seems to be built off of the work of a lot of previous research. It will take some time to prove it, but again if Schnorr is so adamant that this is true he should have no problem with a PoC...even a simple one.

marcinzm• 5 years ago

Refuting it puts a massive burden on other people since finding the fault in complicated proofs can be very involved. Providing a PoC puts a burden on the person making the claim. So at a minimum not providing a PoC is a very selfish approach.

pfortuny3• 5 years ago

Hironaka has claimed to have a proof of reduction of singularities in positive characteristic for years (he got the Fields Medal for the same result in characteristic 0).

Nobody has read the manuscript though...

tantalor• 5 years ago

Pffh, that's for lowly applied mathematicians. This is theory! /s

TacticalCoder• 5 years ago

Ron Rivest explains himself that once in a while he gets an email from someone saying basically "I broke RSA": not everyday but it's a semi-regular occurrence. And he always nicely answers by asking the person claiming to have broken it to solve a challenge (and it's not even a crazy high number of RSA bit keys he gives).

Theory is nice but if you can find the solution to something, just do it and then brag once it's done : )

hinkley2• 5 years ago

Way back when dinosaurs roamed the earth and comp.compression on Usenet was a place to be, usually we went beyond the pigeonhole principle by asking people to grab a megabyte from random.org, compress it, and then get back to us.

Nobody ever did.

plankers• 5 years ago

Isn't this a bit disingenuous though? If somebody had designed an algorithm capable of breaking RSA given supercomputer-level resources, that's still breaking RSA even if they may not be able to provide ironclad proof.

raverbashing• 5 years ago

Agreed. Typical mathematician mentality

People would be more convinced by presenting a factorization of a challenge RSA number

klyrs• 5 years ago

As a computational mathematician, I must object. The world is large enough for multiple deep specializations. I can't think at this level of abstraction (hence, I quit number theory after bashing at it for a few years). I can, however, read a math paper and put together an implementation as long as I'm familiar with the notation and the axiom of choice hasn't been used in a nontrivial matter. But then, my implementation would probably piss off software engineers who like to castigate research software that doesn't meet their standards (rather than, say, helping out).

Expecting everybody to have mastery of every specialization that their work touches is toxic and unproductive. I look forward to a team of motivated undergrad number theorists to tear into this and hack up an implementation.

klmadfejno2• 5 years ago

From the look of it, he hasn't really claimed this yet in public. This link is someone on twitter saying he did in private. I would just wait

pfortuny3• 5 years ago

It is in the ePrints abstract, which is essentially public.

EthanHeilman3• 5 years ago

He claimed it in the paper he posted on eprint.

"This destroys the RSA cryptosystem" - Claus Peter Schnorr[0]

[0] https://eprint.iacr.org/2021/232.pdf

tyingq• 5 years ago

The two links to the paper...had to navigate twitter a bit to find them:

https://eprint.iacr.org/2021/232.pdf (older)

https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9... (newer)

Edit: And the abstract with the "destroyes the RSA..." blurb: https://eprint.iacr.org/2021/232

KMag5• 5 years ago

Quick summary, he's found a faster way to factor numbers. He hasn't found a way to break RSA that isn't equivalent to factoring the modulus.

(As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. RSA always uses odd exponents. The Rabin cryptosystem is similar to RSA except that it always uses 2 as the public exponent and is provably as difficult as factoring, but if the modulus has 2 prime factors p and q, then by the Chinese remainder theorem, the output will always be a quadratic residue modulo p and also a quadratic residue modulo q. In other words, the number of possible plaintexts is 4 times the number of possible ciphertexts, so decryption gives you back 4 possibilities and you need some convention that only one of those was a legal message.)

Unfortunately, this is a faster factoring method, so it also applies to the Rabin cryptosystem, the Blum-Blum-Shub pseudorandom number generator, and Rivest's time lock puzzles (repeated squaring modulo a large composite).

phkahler2• 5 years ago

> As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring.

No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one.

Edit: oh maybe you mean that it's possible to break RSA faster without factoring... Its been too long since I looked at that.

airhead9693• 5 years ago

Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated.

Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.

thaumasiotes2• 5 years ago

the number of possible plaintexts is 4 times the number of possible ciphertexts, so decryption gives you back 4 possibilities and you need some convention that only one of those was a legal message.

This condition is satisfied by ~100% of all communications, including stuff like software downloads. (If I send you a file, then yes, any message is legal, but as soon as you try to do anything with it, you'll know whether the message was correct or not.)

wging• 5 years ago

See previous discussion for context: https://news.ycombinator.com/item?id=26321962

rfoo• 5 years ago

I really hope this is not just another Atiyah moment. Sigh.

srockets• 5 years ago

It is an Atiyah moment in the our response to this: both men earned the right to have those publications silently ignored, not being made into an attraction.

mizaru• 5 years ago

*according to someone on twitter.

slowmovintarget• 5 years ago

This is mildly important. It's someone that claims to have communicated with Schnorr.

tptacek• 5 years ago

If Frederic Jacobs says he communicated with Schnorr, then that's what happened.

cperciva• 5 years ago

If Frederic Jacobs says he communicated with Schnorr, he thinks he communicated with Schnorr. It's possible that someone is impersonating Schnorr.

isaacg• 5 years ago

Here's an expert saying that this paper should be considered unsubstantiated at best: https://crypto.stackexchange.com/a/88590

bcaa7f3a8bbc4• 5 years ago

If my understanding is correct, Schnorr converts the integer factorization problem to lattice problems: SVP and CVP. Then he claims he had an efficient algorithm to solve this particular instance of SVP and CVP, thus RSA is destroyed. But, the hardness assumption of SVP and CVP in general is the very foundation that another branch of public-key cryptosystems - lattice-based cryptography - is built upon. So, if Schnorr's claims are true (uncertain and still to be determined), I can't stop to think about its impact on lattice cryptosystems: Can we use the same technique to attack them? I think it's a more important question than RSA [0] - lattice cryptosystems are the candidate for Post-Quantum Cryptography, meant to replace all of the existing public-key cryptosystems of today (e.g. RSA and ECC). Even if the attack is purely theoretical, if it can solve other instances of SVP and CVP, it'll certainly affect the security assessment of lattice-based PQC (e.g. NTRU, also LWE).

Of course, I don't know what I'm talking about.

[0] Factorization had a history of speedups, both theoretical and practical. It doesn't really affect the practical security but always comes at a cost of either decreasing confidence or constantly increasing the keysize, so I won't be too surprised if Schnorr really has new insights to speed it up further. In fact, "We need something with a better security record than RSA" was one of the main arguments for transitioning to ECC - which has already completed at large on today's Internet, RSA is only used for digital signature, almost all key exchanges are ECC now. You can't decrypt post-2016 web traffic by breaking RSA.

pbsd• 5 years ago

Schnorr got close to making such a claim in a previous version of the paper [1, Section 6]. Namely, that NTRU is close to being broken if a sufficiently short vector (it is not specified how short) is found.

The main claim of Schnorr's, as far as I can gather, is that for lattices where the shortest vector(s) are much shorter than the maximum shortest vector(s) for the same dimension, i.e., low-density lattices, those vectors can be found in heuristic polynomial time with his enumeration approach.

Now, low-density lattices are fairly common in cryptographic settings, where the solution, discoverable by finding shortest vectors, is unusually short/close relatively to what one would expect in a random lattice.

As such, if true, I would expect Schnorr's idea to lead to more breaks than just RSA. But I don't personally think it's true. At the same time, I'm not a lattice expert, so make of that what you will.

[1] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP2...

JoblessWonder• 5 years ago

Of course, I don't know what I'm talking about.

I would honestly have no way of knowing either way. It is always fun to get a peek into people working out ideas in fields I have no experience in.

k3liutZu• 5 years ago

It is always fun to get a peek into people working out ideas in fields I have no experience in.

Phew. I'm not alone.

I understood _some_ of the words used in the HN comments in this thread.

bcaa7f3a8bbc4• 5 years ago

I noticed HN user fractionalhare has made a comprehensive reply to my questions, but it wasn't posted as a reply to me, so now it has fallen to the bottom of the page. You can see it here: https://news.ycombinator.com/item?id=26331747

YoungWeb• 5 years ago

Would love a "what's going on here for dummies" summary if possible. From what I gather someone is claiming they broke RSA encryption?

bcaa7f3a8bbc4• 5 years ago

1. Claus-Peter Schnorr, a well-established and reputable cryptographer, publishes a paper and claims he found a new algorithm for integer factorization, which is faster than the best known algorithm today (Number Field Sieve).

2. If it's all the paper says, it probably won't attract that much attention, at best it leads to a new wave of RSA keysize upgrade (or transition to ECC). But today, this paper appeared on the Cryptology ePrint Archive, and its abstract reads "This destroys the RSA cryptosystem", the use of strong language is extraordinary, a reader may interpret it as "the speedup is significant and all RSA keys can be broken." Researchers usually don't make such claims.

3. Meanwhile, it's also very suspicious for two reasons. First, this claim didn't appear in the actual paper, only the ePrint Archive web page, and it also includes an embarrassing typo. Also, the submitted paper wasn't even the latest version, which is available at Schnorr's web page, but an old version from 2019. Many people suspected that the paper was submitted by someone else, who happened to see an earlier version on the web and got too excited about it, and added the "destroys RSA" claim.

4. But now, personal communication with Schnorr confirmed the paper was indeed submitted by him, and he indeed makes the "destroys RSA" claim. Schnorr also said he uploaded the wrong file.

5. About 10 minutes ago, an updated preprint was published, that includes the sentence, "This destroys the RSA cryptosystem".

fractionalhare• 5 years ago

I wrote my thesis on post-quantum public key cryptosystems, though I'm not currently a practitioner and haven't been academically active since ~2017 or so. With those provisos in mind, I'll try to give the summary as I see it. As a basic tl;dr I'm skeptical of the paper. Crypto-twitter is lit up about this right now and as far as I can tell, harbors the same skepticism.

- For context and background: yes, there are well-established links between factoring problems and lattice problems. These links have been known from at least the early 90s. There are many complexity theoretic reductions between specific factoring problems and specific lattice problems, and the approximate variants of the latter. There hasn't been an arbitrary reduction yet, it's mostly on a problem by problem basis.

- That first bullet point means that this research is at least structurally built on, and engages with, prior work in the academic community. Schnorr in particular has been pursuing this since the 90s. Schnorr is an accomplished and established cryptographer.

- I consider the context of that second bullet point unfortunate, because it means the research gets outsized attention even though it is otherwise, as of now, unsubstantiated. It gives the paper a lot more charity than it would ordinarily receive.

- Critically: Schnorr has not empirically demonstrated a break in RSA. He has demonstrated - in theory - faster factoring methods using SVP and CVP solving techniques which rely on a reduction of the factoring problem.

- The paper may not be worthless even if it doesn't break RSA. If he has indeed found a polynomial time way to solve a subset of lattice (and factoring) problems, that will be impressive. I'll have to read the paper a few more times to come to a belief on this point though.

Many comparisons are being drawn online between Schnorr and Atiyah, because the latter kept insisting he found a proof of the Riemann Hypothesis towards the end of his life. It would be sad if this is the case for Schnorr, but it's personally what I believe at this time pending an empirical demonstration of his work and/or critical substantiation from the rest of the academic community. I'm skeptical of this result the same way I'm skeptical when highly established mathematicians publish purported proofs of long standing open problems.

cleansingfire• 5 years ago

Assuming it works, I'm interested in its limitations. At various complexity levels, there are subsets of problems that yield easily, like unsafe primes in RSA, or trivially, how I can instantly get one factor of an even composite.

Schnorr's main novel claim here seems to be a speedup in finding the SVP and CVP in some cases (he explicitly acknowledges limitations.) A Proof Of Concept seems like it would be great to test for edge cases, and that's where I think the interesting bits are likely to be. Disclaimer: Not a mathematician or complexity theorist. Just here to learn, and glad to be corrected any time.

llarsson• 5 years ago

What if it's actually someone else that discovered this and is just publicly posting and acting as Schnorr, in an attempt to prove their point? ;)

olliej• 5 years ago

.. this is literally a post confirming that it was schnorr

phigcch• 5 years ago

Without experimental data to back it up (e.g. implementation and benchmarks), I'd consider this claim veeeery dubious - regardless of who it came from.

Extraordinary claims need extraordinary evidence, and in this case it would be easy to provide such evidence - by cracking appropriately-sized challenge primes in a transparent way that can be independently verified.

On the other hand, the theoretical approach in the paper is quite complex and hard to follow - even for professional cryptographers.

coliveira• 5 years ago

There are some approaches that seem difficult to implement at first view, but that can be improved when more people work on the difficult pieces. The most important thing in a paper like this is the general strategy. Even if there are small issues or if the implementation is too complex, if the general ideas are right we can find a better way to solve these problems over time.

the_svd_doctor• 5 years ago

Depends of the claim. For the theoretical result, the evidence is the paper. (I have no clue whether it’s correct.) Nothing else is needed. For “RSA is broken”, it depends what broken means. If it would rely on a claim that is now provably false, it is indeed broken. If we are talking about the claim of breaking RSA in the real world, I agree with you. But it all depends on the claim.

Lammy• 5 years ago

"This giant prime number will keep your information totally unreadable to anyone who doesn't have this other giant prime number" is no less of an extraordinary claim, just one that we all believe in (myself included).

pfortuny3• 5 years ago

In the 2020 preprint:

"These new algorithms factor integers N ≈ 2^400 and N ≈ 2^800 using 7x10^10 and 4.3x10^12 arithmetic operations".

He does not specify how many it uses for 2^1024 or 2^2048. This is clearly nonlinear. Assume (nevertheless) that you multiply x100 every 400 binary digits, then for

2^2048, you get

(2048-800) equiv 1200/400 equiv 3, so you would need approx. 10^12*10^6 operations. Assuming you can do 10^6 ops , you need 10^12 seconds (like 30000 years).

BUT those are very very rough assumptions (an "arithmetic op" might probably take more than 1 microsec).

EDIT: sorry, this link is pretty interesting. Factor RSA-260, which only has 862 bits. Should be feasible in about 2 hours. The link: https://crypto.stackexchange.com/questions/88582/does-schnor...

EDIT2: sorry again: Schnorr is 78 years old. I am not gerontophobic (being 50 I am approaching that age) but: Atiyah claimed the Riemann Hypothesis, Hironaka has claimed full resolution of singularities in any characteristic... And I am speaking of Fields medalists.

So: you do really need peer-review for strong arguments.

fallingknife2• 5 years ago

I'm getting 1e9 multiplication (2.5e8 div) ops per second in Node on a 2018 Macbook pro. So that would be 30 - 120 years. Not sure how well this algorithm can be parallelized, but since it's factoring, I think it can. So I would think that a dedicated attacker could get at least another 1000x on that, which gives 11-44 days. Note that I am pretty much guessing here but this is my test code:

    function test(opp, n) {
      const start = Date.now();
      let i = 1;
      if (opp === '*') {
        let prod = 1;
        while (i < n) {
          i++;
          prod *= i;
        }
      } else if (opp === '/') {
        let quot = 100000000000000;
        while (i < n) {
          i++;
          quot /= i;
        }
      } else if (opp === '+') {
        let sum = 0;
        while (i < n) {
          i++;
          sum += i;
        }
      } else if (opp == '-') {
        let sum = 100000000000000;
        while (i < n) {
          i++;
          sum -= i;
        }
      }
      const end = Date.now();
      console.log(`${n} ${opp} ops in ${end - start} ms`);
    }

waterhouse2• 5 years ago

Guess: The "multiplications" we're talking about are those of 400-bit or 800-bit numbers (and, in general, would be the size of the number you're trying to factor), which are much more expensive than 64-bit x 64-bit or float x float multiplications. If you want to test the cost of that, I recommend GMPlib's bignums (or possibly just your favorite language that has built-in bignum support, although if it's not built on GMPlib it might not be using the most efficient algorithms).

stefan_• 5 years ago

I take it someone finally put down the smartphone and picked up the telephone? It turns out retired 70+ year old math legends don't frequent Twitter, so of course the chances of the "crypto community" hashing this out through ever increasing frantic Tweets weren't great.

Flockster• 5 years ago

It seems a wrong version was uploaded.

https://twitter.com/FredericJacobs/status/136717279911944601...

blintz• 5 years ago

About 10 minutes ago an updated preprint was published with a much more succinct and understandable abstract, that includes the sentence, "This destroys the RSA cryptosystem".

https://eprint.iacr.org/2021/232.pdf

Version history here: https://eprint.iacr.org/eprint-bin/versions.pl?entry=2021/23...

forty• 5 years ago

I found this thread interesting https://twitter.com/SchmiegSophie/status/1367197192172179456

CryptoLeo• 5 years ago

Debunked : https://github.com/lducas/SchnorrGate

Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

Related Stories