Hacker News Reader

Comment by tyingq | Hacker News Reader

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.

View on HN

The sum-of-three cubes announcement was tweeted pretty easily.

https://twitter.com/robinhouston/status/1169877007045296128

Its easier to drum up support for your paper when you have a quick way to prove to the community of mathematicians that your results are golden.

EDIT: The original webpage: http://math.mit.edu/~drew/sumsofcubes.html

As you can see, the sum-of-cubes announcements are very terse. Ultimately pointing to the following link: https://share.cocalc.com/share/900eec7e-0710-4e2f-a03a-dba01...

That kind of website / tweet is a "drop the mic" moment. It really makes people pay attention.

That's not how science works. Yes, if your algorithm is simple enough and you can create an implementation, then it is good that you produce a working version. But it may be more complicated to implement the algorithm than writing a paper. This doesn't mean that the implementation is impossible.

> That's not how science works.

This isn't science, it's math. As the article mentions, there is an 862-bit RSA challenge that hasn't been factored yet. Factoring it should be possible on commodity hardware if the claims in the paper are true. So why not just do it? The test of success is simple: either you win the challenge or you don't.

For a skilled researcher it may be an order of magnitude easier to write the whitepapar than to code the implementation.

There are example factorizations around page 11 if I'm reading this correctly. Haven't run them through yet because I'm refreshing my atrophied linear algebra knowledge and walking through some of the source papers, so some work is in there.

That's exactly how maths works, specifically in the cases where where the claim is easily backed by a demonstration. A famous example:

https://en.wikipedia.org/wiki/Frank_Nelson_Cole

If you 'destroyed RSA' through better factorization, all you have to do is start publishing factors of RSA challenge numbers.

Matthew Green has a fun thread about other ways to approach this along with an interesting "real talk about factoring" sidebar by Nadia Heninger:

https://twitter.com/matthew_d_green/status/13669500931784990...

> But it may be more complicated to implement the algorithm than writing a paper

Then why would I trust it? You don't need to write code, you need to write an example

As Linus Torvalds says: talk is cheap, show me the code

Academia is full of "paper scientists" that put out papers but produce nothing of value.

They are also full of postgraduate students as well that would be more than willing to work together and put a proof-of-concept code with the paper.

So this is why I’ve suddenly been getting new interaction on that old tweet! I’m glad I saw this comment, because I was quite confused.

If you really think your paper destroys RSA, I think there are ethical questions the authors must decide before publishing it.

In particular, I think the right process would be:

1. Give some brief description of the result (eg factoring numbers in O(...)), and some proof (eg a factorisation of the next rsa semiprime, possibly more) that convinces people that your claims are true

2. Wait a while for people to have the chance to not be burned

3. Publish the paper

Instead, the authors seem to be going for:

1. Publish the paper with a provocative abstract.

2. Wait to see who implements the algorithm first.

It doesn’t seem the best idea to me, but what do I know?

Unlike a zero day, there still remain a number of important factors (haha) to actually break a large number. But crypto systems are special because they rely on trust. The mere sign of weakness is sufficient to kill that trust. A sufficiently resourced state actor may even be ahead.. we don’t know

The pursuit of knowledge should not be subject to any annoying effects said knowledge may have on people hedged against such knowledge becoming available. That’s an anti-liberal recipe for a rather dark society. I don't see the point in tone policing people generating knowledge just to remind them that sometimes knowledge is inconvenient.

"tone policing"? What do you think that phrase means? Who was talking about "tone"?

Do you believe in "responsible disclosure" [1] of security vulnerabilities? How does your stated philosophy apply or not apply to ethics around disclosure of discovered software security vulnerabilities? Is that different?

[1] https://cheatsheetseries.owasp.org/cheatsheets/Vulnerability...

Technically, the poster the poster you replied to could be said to have been tone policing with the assertion of releasing a deliberately "provocative" abstract.

I mean, I get it, it's not the most straightforward mental leap, but I can understand the sentiment.

And as far as responsible disclosure goes, no, the responsible thing to do is to notify everyone at once. Keep in mind if it is right, this means that nation state actors have just been equipped with a roadmap to potentially cracking a lot of banked ciphertext, probably faster than anyone else.

You don't sit on that kind of thing, even if it does mean some corporate actors get burned.

If the only thing saving your rear was an RSA key... Take notice: the clock may have just been significantly advanced. Be you nation-state, corp, or someone who'd just prefer to remain in the shadows.

Suffer thee not information asymmetry to live lest you carry the blood of those you sacrifice on the altar of your limited disclosure. It also hedges against you getting disappeared and suppressing whatever other people you shared it with that remain to keep something so relied upon from being realistically entertained.

I mean, cmon, how long has everyone been joking they'd hate to be the person who discovered how to break RSA, because we all know it would lead t

<SIGNAL_LOST>

Sorry that is such a bullshit statement.

Can you explain?

Pursuit of knowledge can be noble, but it can also be horrific. Granted, this isn't horrific, but if RSA is literally "destroyed" then it has potential to do harm, even if we stop using it immediately (which is expensive by itself). Ethics governs good science, and math is no exception

>I don't see the point in tone policing people generating knowledge just to remind them that sometimes knowledge is inconvenient.

If you found a simple way to kill all of mankind, that could be mitigated by waiting a week to publish while safeguards were implemented, is it wiser to publish immediately and risk someone killing all of mankind or to notify proper groups and then publish later after it won't kill everyone?

Maybe there's some nuance in these things. Ignoring effects of knowledge is not wise.

You're going to be killed or kidnapped between steps 1 and 3.

For something of this magnitude, I think the expected behavior would be to delay the release of the paper until the ecosystem had time to adapt. To prove the paper is valid (and to assert precedence) you would offer to factor several "nothing up my sleeve" numbers -- like sha512("schnorr1") + sha512("schnorr2").

As it is, if the algorithm presented is valid then this potentially compromises currently operating systems.

I do not agree that so-called “responsible disclosure” would or should be the expected behavior. I do understand how someone accustomed to corporate bug bounties and private security mailing lists may think so, though. Full disclosure is a perfectly reasonable strategy especially when we’re operating in the academic realm. Industry always takes years to catch up to academia anyway.

If this paper allows to produce a working RSA cracker in a month, much of high-value IT infrastructure is under imminent threat.

Yes, you can replace your SSH keys with elliptic ones, and maybe adjust your TLS accepted algorithms. Even this is not always easy or cheap.

But other things that may rely on RSA (or triple RSA) may have trouble upgrading fast, and upgrading them at all is going to cost a lot.

Yeah, but also the industry knows for DECADES that RSA will likely be broken eventually. Not having reacted yet is not the researcher's fault.

We know that Quantum computers can break it too, yet nobody really acts on it with any urgency. If suddenly there is a breakthrough and we can reach this state within a year, then there will be no time to adapt as well.

It all boils down to the general corporate attitude of not fixing catastrophic problems without precedence. We see the same with climate change and once it hits hard, it will be too late to adapt.

>Yeah, but also the industry knows for DECADES that RSA will likely be broken eventually.

Interesting. Reference?

It's generally accepted for almost all crypto protocols that it's going to be broken eventually (a few rare cases are provably secure, one-time pads and not much else).

If nothing else, quantum computers should break RSA in particular (the algorithm is already known and just waiting for hardware) and the writing has been on the wall there for a long time.

> It's generally accepted for almost all crypto protocols that it's going to be broken eventually

Just like it was generally accepted that god exists. Those claims are of similar strength.

> If nothing else, quantum computers should break RSA in particular

Quantum computers with enough qubits do not exist and it's absolutely not obvious whether they will exist at all.

Cryptographically protocols have attacks designed against them all the time.

I asked a few years ago(I don't remember the specifics) what was the recommended post-quantum crypto, and basically the answer was that there wasn't any vetted and proven post-quantum crypto. So I don't think you can blame the industry here.

There are some promising experiments. All of them are much worse than the algorithms we use today (including RSA) in practical terms, except that Shor's algorithm doesn't apply to them, and so they specifically fulfil the criterion of post-quantum public key crypto.

[For symmetric encryption quantum computers would only matter if they were pretty fast/cheap and we didn't have ready-to-go 256-bit symmetric crypto, but we do]

OpenSSH actually has an implementation of a reasonable contender for SSH. Google have experimented (in Chrome builds) with some of these contenders for TLS too. What you would likely want to do - since by definition these are relatively untried algorithms and so might be unsafe against adversaries with an existing not-at-all-quantum computer - is combine with an existing algorithm, most likely elliptic curve based, but RSA would be possible, under a "swiss cheese" model where you're only dead if an adversary penetrates all the layers.

But like I said, much worse. Given that there aren't any suitably large quantum computers (and it's always possible that we'll eventually figure out we just can't build usefully large quantum computers, just like we eventually found out that while you can travel faster than sound you can't travel faster than light) it would make no sense to deploy this today, even though it continues to make sense to do research Just In Case.

Wouldn't surprise me if there are classified quantum computers crunching numbers as we speak tbh.

I would be very surprised. That would involve keeping some huge leaps in basic research under wraps.

Could you expand on "much worse?" Are they slower, are they harder to implement?

slower

larger messages

larger public keys

larger private keys

Just to expand the other answer you got.

Slower, in a different complexity class from the classical ones (AKA O(n^2) instead of O(n), but I don't know what exact complexities the top candidates have right now, as a function of key length).

Larger messages, in that a signature requires 100's or 10's of Mb instead of a few kb.

Larger public keys, as again 100's of Mb instead of a few kb.

Larger private keys, as in a few to 10's of Mb instead of 1/2 to a few kb.

But I guess the most relevant "much worse" is that people have much less confidence that those algorithms are secure, and they are complex enough to hide huge traps that make implement RSA look like a walk in the park.

You seem to be way outdated. A lot of work has been put on reducing key sizes. Dunno about signatures, but for key exchange SIKE (https://sike.org/) uses keys of a few hundred bytes, comparable in size to RSA.

Sure, SIKE is not so much bigger than existing approaches, but it is much slower than they are.

Some of the other choices aren't so much slower but are far bigger, for example McEliece systems.

There's lots of opportunities to make different trade-offs - at least if all of them survive a bit more scrutiny by smart motivated opponents - but they're all generally worse than what we have now - except that they resist Shor's algorithm.

That's true, a quick Google search tells me that an optimized SIKE implementation is ~30x slower than an optimized X25519 implementation. Still, according to this document, running time of SIKEp751 is ~25ms: https://sike.org/files/SIDH-spec.pdf

I don't think that's a problem for end users, you are not constantly generating keys. It will be a problem for servers handling thousands of connections per second, but I'm sure dedicated HSMs will appear if there is a need for them.

In any case, I'm not an expert in crypto, just a poor sysadmin-by-accident who likes reading about the latest security developments so the bad guys don't pwn my servers. And as you said, engineering is always full of trade-offs, let's see what the NIST PQC standardization process will decide.

Not only quantum computers. Every cryptographic method relies on fact that there is no easy way to decide NP problems. And we don't really know whether P!=NP (in fact, according to polls, about a quarter of researchers disagree), or, in case there actually is a polynomial algorithm, its exponent will make it untractable in practice.

So there might be DOOMSDAY in the future, where all cryptography will cease to work, because somebody just figures a way to decide NP problems quickly enough.

> triple RSA

Yeah, no. 3DES (Triple DES) is/ was a thing, but Triple RSA is not.

That was the joke.

> If this paper allows to produce a working RSA cracker in a month

The blog post claims that people have been trying to reproduce his results for two years, though.

If you find something that can break all cryptography in the world, then I think your best option (even for your personal security) is to release everything publicly.

A one time pad can not be broken.

I always enjoy the reaction when I tell students that we've had provably unbreakable encryption since the 19th century.

And yet any time someone proposes to actually implement it, the response is always negative: "don't roll your own encryption" or "sharing and storing the pads is infeasible" or some such.

Seems like we should have figured out a way by now to use one time pad encyption by default for critical paths, even if that requires new industries to distribute pads and guarantee their security.

Yeah. I take up the key exchange problem (and Diffie-Hellman) as well as difficulty of achieving true randomness.

I've made matlab scripts that pull true randomness out of the less-significant figures of the output of an audio microphone listening to static...it's not impossible.

If we were serious about it, sharing flash drives and even using couriers could make it work pretty well.

Quantum computing may eventually force us to move to OTPs. Of course it's going to be a pretty long time before we'll have quantum computers that can work across an 800-bit field.

It won‘t. Symmetric ciphers are holding up just fine against quantum computers.

Key exchanges would be annoying, but they are even more so for one-time pads.

But it will never come to even that: There are plenty quantum-safe asymmetric cryptosystems around.

OTP is perfectly secure, but (for many cases) perfectly useless. Transmitting the key safely is exactly as hard as transmitting the message safely.

They're useful in exactly one situation: when you have a temporary secure communication channel, and a long-term insecure channel. Then you can use the temporary channel to pre-share a lot of key material (say, a 1TB micro SD card carried covertly) and then use that for future messages. But that scenario is very rare.

The rarity of that scenario is dictated by there rarely being a need for the security it offers. But that, in turn, is a function of our knowledge of cryptography, and may change over time. Who knows; perhaps someday we'll see something like what Vinge described in AFutD:

"Our main cargo is a one-time cryptographic pad. The source is Commercial Security at Sjandra Kei; the destination is the certificants' High colony. It was the usual arrangement: We're carrying a one-third xor of the pad. Independent shippers are carrying the others. At the destination, the three parts would be xor'd together. The result could supply a dozen worlds' crypto needs on the Net for ..."

Yup, that bit from Fire Upon the Deep is exactly what I was thinking of when I mentioned that bit about industries to safely transmit OTP data.

I don't really think the parent comment understands that there are creative ways around the difficulty of sharing secure pads. We don't need it for all data; but I think Vinge does hint at a totally viable means of sharing, and scenario in which it's practical.

I haven't read the paper or anything, but if the expected adaptation is to drop support for RSA; no reasonable amount of time will make it a seamless transition.

There are so many devices and pieces of software that are stuck on RSA, a headsup of say 5 years would still result in a clossal mess; may as well have the mess now.

Note that (despite the ill-considered claim about RSA in the abstract) this isn't security research. It's a maths paper in a very important area of number theory. It doesn't disclose a patchable flaw in RSA---it claims that RSA is based on an unproven conjecture that turns out to be false. That RSA is vulnerable to fast prime factoring has been known since it was first implemented. That's not fixable, so delay serves little purpose, especially with a (if it turns out to be true) seminal result in number theory.

RSA has published the same set of "come and break me" keys for years, decades I think. Breaking those public (in both senses!) keys would be a good start.

You probably understand how serious this is, so many people are going to become very emotional as this strikes at the very foundations of the Internet and digital security as we know it. The reactions I've seen so far do seem very emotional and this will only become much, much worse if there's a PoC which is produced.

What does emotion have to do with it? For many years, every time someone claims to have broken RSA the response is the same: here is a test case you (the alleged RSA breaker) should be able to crack if your claims are correct. Put up or shut up. That seems like a fair, just-the-facts response.

Internet and digital security? This strikes at the very foundations of number theory.

Ehhhhhhh. I'm not sure I'm aware of anything in number theory that would substantially change if a fast factoring algorithm were discovered, outside of its applications to cryptography. It'd be very likely that a fast factoring algorithm exposed some unusual structure about the natural numbers, I guess?

I was exaggerating for effect, but yeah. The existence of a polynomial time prime factoring suggests the existence of a useful predictive pattern in the distribution of primes. That would break the Twin Prime Conjecture and possibly refute Riemann. Undermining those starts tearing the foundations apart. I’m almost certain that won’t have just happened.

We already know there is plenty of structure in the distribution of primes, so I don't see why finding some that can be exploited by a clever algorithm makes that much of a difference to foundational concerns. In fact, I'm pretty sure that even a proof of P=NP, which obviously subsumes fast factoring, wouldn't have any intrinsically interesting non-algorithmic consequences for proofs in number theory that don't directly assume factoring is hard (but this could just be ignorance on my part); all the supposedly absurd consequences people point to like the PH collapsing are more or less restricted to computer science.

> 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

Ah, I see. It's been removed in a newer revision of the paper. https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...

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-S3...

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)

The newer 12-page version on the preprint server has a PDF creation date of 3/3/2021, 11:32:56 AM, created with pdfeTeX-1.30.4.

https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2021/232...

The previous (reportedly wrongly uploaded) version is from 12/5/2019, 9:10:13 AM created with pdfeTeX-1.30.4.

https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2021/232...

The university website version is from 3/5/2020, 12:00:19 PM created with pdfTeX-1.40.15.

These dates & times are MM/DD/YYYY & CET.

A co-editor of the Cryptology ePrint Archive confirmed the submission on twitter:

https://twitter.com/Leptan/status/1367103240228261894

This is math. The working proof _is_ the paper. It just takes a long time to refute if there’s a subtle error. “Putting up” ISN’T proof but it will sure get a lot of important people to drop what they’re doing and check the paper faster.

I dunno, isn't a demonstration of a few factors proof that someone somewhere has broken RSA, or has a machine much more powerful than we'd expect to exist? It's not proof that any of the math in the paper is correct, but it doesn't have to be. Even if there's a subtle error in the proof-as-written it doesn't matter if the implementation actually works.

All that is true.

But if the author of the paper (or even someone else with a credible reputation) was to public factors and say they used this method then it's useful evidence.

"Putting up" isn't proof that an RSA decryption algorithm exists, but it is proof that someone has found a way to reverse RSA either way.

The latter is much more important.

I haven't looked into the details of the speed improvements... it's often the case that big-O improvements in complex problems come with bigger constant factors. It's entirely reasonable that this new algorithm is slower for factoring 384-bit numbers but faster for 4096-bit numbers.

I wouldn't be surprised if a demonstration that pushes the current publicly known record for largest factored RSA modulus costs hundreds of thousands or millions of dollars even with this new algorithm, and the algorithm is also slower than other methods for, say 384-bit RSA.

It may be difficult even for Peter Schnorr to get that kind of budget for a demonstration before his paper gets traction.

I'd agree with that if he had merely tweeted about RSA. However, he put the claim to "destroy RSA" in the abstract. Claims made in the abstract do need to be substantiated, but RSA isn't discussed in the main text at all.

This is math claiming an algorithm that is faster.

For an algorithm, asking for results is not that weird. It certainly fits within the purview of a paper. Moreover, it would be really strong evidence for the claims made in the paper. It is much easier to check than the proofs.

How broken does this claim RSA is? SHA-1 was known to be broken for a long time before actually pulling off a collision was performed for example.[1]

[1]https://en.wikipedia.org/wiki/SHA-1#Attacks

An attack is anything that makes it take less than a brute force effort (of 2^80 operations). A 2^63 effort is really expensive in 2007. But by 2015 computation was maybe 2^5 times cheaper and there was a 2^5 cheaper attack.

I believe that this breakthrough could be quite a bit bigger because it's changing the costs from exponential to polynomial and so speedup is likely a much bigger change.

The whole paper is linked, https://eprint.iacr.org/2021/232.pdf

And the article says it would take around a thousand CPU core years to break 800-bit RSA. Maybe Schnorr needs to publish first to get the budget for that.

> the article says it would take around a thousand CPU core years to break 800-bit RSA

That's for previous algorithms, not the one described in the paper.

He doesn't need to demonstrate it with an 800-bit number. Given the claims made about how much faster this is, the effect should show up even in fairly small numbers.

That can be solved within hours on a GPU cluster... Looking at a single core is usually not a great idea when you have billions of cores available.

Only if your algorithm is conducive to parallelism based speedup. Amdahl's law still applies.

The paper mentions some gains being possible through parallelism with one of the algorithms their work is based on, but also mentioned most prior art is not effectively parallelizable across discrete machines.

The factors could be included in the manuscript as an example..

It is in the actual paper.

Also, without that sentence nobody would be trying to read the paper, so props to Schnorr who understands how to create the buzz :P

Yep. A paper has to substantiate any claims made in the abstract, and this failure already undermines my confidence that the result is correct.

Reply on news.ycombinator.com