Bullying the Integers
So, the FBI allegedly arranged for a number of backdoors to be built into the OpenBSD IPSEC stack. I don’t really know how credible this claim is, but it sparked a discussion in my office about digital security, and encryption in general. One of my colleagues said something to the effect of it only being a matter of time before they found a way to easily break RSA.
It was at about this moment that time stopped.
I responded with something I thought was quite lucid, but there’s only so much lay interest that can be held in a sentence that includes the phrases “fact about all integers” and “solvable in polynomial time”. The basic thrust of my argument was that it wasn’t something he could just decide an answer to, but I don’t think he’ll be walking away any the more enlightened.
This got me wondering: do arguments that sit on cast-iron facts (or lack thereof) about number theory feel any different when you’re making them, compared to arguments that sit on facts about the world you’re just extremely confident about?
If I have a discussion with someone about taxation it has no more consequence than a discussion about cryptography, but the tax discussion feels more urgent. Someone walking around with wonky ideas about fiscal policy seems more distressing than someone walking around with wonky ideas about modular arithmetic. Modular arithmetic can look after itself, but fiscal policy is somehow more vulnerable to bad ideas.
Do your arguments feel different?
This is something people with only basic exposure to cryptography and security are confused about a lot.
To them “breaking RSA” and “breaking something using RSA” sound essentially the same.
Systems are only as strong as their weakest part.
Nobody bothers attacking basic cryptographic primitives like AES, or RSA, or SHA-1 in practice. These are standardized, simple, have extremely straightforward interfaces, very well researched, and with enormous level of public exposure. Even theoretical weaknesses found occasionally tend to have little practical relevance.
What gets attacked is everything else. Implementations bugs, protocol corner cases, differences between assumptions and actual requirements, side channels, human factors, and very few people looking at it ever. They are highly complicated, messy, with no clear boundaries, and every system starts essentially from scratch.
When P(system is secure) = P(system is secure|AES is secure) P(AES is secure)
You want to focus all your effort on P(system is secure|AES is secure). Both protection effort, and backdooring effort.
RSA is somewhat between the two. It’s somewhat more complex, and requirements for securely using RSA are a lot more complicated than for securely using AES. The entire public key crypto is built on far weaker foundations than private key crypto. There’s very little hard number theory involved.
When you say “nobody” you mean actual attackers—obviously researchers attack these things all the time. And you do get practical breaks as a result of breaks in cryptography—WEP is the most famous example.
But WEP is a perfect example. WEP is a protocol which uses RC4 for crypto.
RC4 was a really bad proprietary cipher to use, with well known weaknesses even back then, and with key sizes providing no security margin at all. It is essentially a horrible cipher, and they could have barely chosen a worse one while even pretending they tried.
And yet, even with all such horrible decisions about RC4, the primary problem was still not in RC4. WEP didn’t even use RC4 correctly. RC4 only tries to be secure if you don’t reuse IVs, otherwise all bets are off. WEP completely ignored that. Mishandling IVs/nonces is not even anything obscure—it’s one of the basics.
What then-known weaknesses in RC4 do you have in mind?
I don’t get your meaning about key sizes, could you be more specific?
WEP does not re-use IVs.
WEP uses 24-bit IVs. Birthday paradox guarantees IV reuse.
Original WEP uses 40-bit key. This is already borderline broken, so any extra weakness moves us into trivially broken in seconds territory WEP occupies now.
RC4 weak key schedule.
What about Shor’s algorithm? Is this not at least in theory a easy way to break RSA. Only the practical barrier of building a quantum computer capable of cracking practical encryption remains.
Shor’s algorithm was found/invented after RSA so for close for two decades there was no known theoretical solution. That did not mean that it was not possible however.
Many of the people who thought it was impossible to break RSA in polynomial time were arrogant, they thought they understood the world much better then they actual did. Many of the people who thought that it was obvious that RSA would one day be solved in polynomial time were also arrogant. You are right it is not possible to decide the answer one way or another, nature can not be bullied. It is however often necessary to take actions before you can not for sure one way or another. So your colleague probably internally transformed his best guess in to a ‘fact’ so he could act on it. Or maybe it transformed from guess in thought to an utterance of fact out of subconsciousness tendency because it sounds more convincing to most of the audiences he/she has talked to.
To my knowledge Shor’s algorithm is currently accepted as correct the exact requirements for a practical quantum computer that can solve today’s RSA encryption is still being explored.
Could you quote some of those people? I’m not aware of a lot of knowledgeable people making unwarrantedly strong assertions.
My assertion was also not specific to people knowledgeable in the field, just like the op’s colleague is not very knowledgable in RSA(at least I had assumed so). I consider the probability of a non-expert having said this to be to be close to 100%.
Be forewarned I am not an expert in the feild, but here are some interesting tidbits:
Then:
edit: Shor is suggesting that quantum computers break the Church thesis which implied that for any device it was impossible to solve RSA in poly time. end edit.
Both from quotes are from “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”—Peter W. Shor
Note that AFAIK Church did not state this “Quantitative Church’s thesis”—it’s hard to be sure because of the paywall, but I’d guess that this paper was the first to explicitly state it, and it did so in order to argue that it may not be true.
I could not tell which paper you are talking about. The paper I posted? It is not behind any pay wall for me. If not the paper I post which paper are you talking about I can try to look at it at work latter.
Don’t know what went wrong there—I have the paper now. Turns out I’m quite wrong, this idea is credited to:
P. van Emde Boas (1990), Machine models and simulations, in Handbook of Theoretical Computer Science, Vol. A, J. van Leeuwen, ed., Elsevier, Amsterdam, pp. 1–66.
Same reaction here. Since it is physically possible to break RSA, it seems obvious to me that RSA will be broken… eventually.
Barring collapse of technological civilization/technological stagnation/human extinction.
I wouldn’t be excessively surprised if someone found a regularity in a common pseudorandom generator algorithm that could be exploited to narrow down the search for the prime numbers used for RSA keys.
This would fall under “breaking some implementations of RSA” and not “breaking RSA”, but is close enough for practical purposes that your colleague might be right (or at least, not be in a seperate cast-iron category of “wrong”, especially if you also consider quantum computing arguments).
My quibble wasn’t whether he was right or wrong about the breakability of RSA. It was that the answer to the question sits on other notoriously open questions which can in principle be fundamentally solved one way or the other, and which you can’t just pull an answer out of your arse for.
If the question was whether prime factorisation was likely to become easy, then probably you’d be justified in saying, essentially, “you don’t get to have an opinion!”. But since RSA is only an implementation, not a pure essence of mathematics, it might be vulnerable in ways we don’t know about yet. It wouldn’t be the first time. (Of course your interlocutor might not have intended this interpretation.)
I think this is a good example of a common case, where our certainty concerning ideal objects like mathematics can blind us to the existence of uncertainty in the real world. If someone designs an AI tomorrow and provides a proof of its friendliness, should we implement it?
This question nicely straddles the dichotomy between taxation (which has policy consequences and is somewhat subjective) and modular arithmetic (which has no policy consequences, and “can look after itself”).
To clarify, in the discussion in question I was trying to distinguish between software implementations of encryption and the underlying mathematics of those implementations. I am in doubt as to whether my colleague appreciated that distinction.
I’m slightly confused here. RSA could be viewed as an implementation, but it could also be viewed as an entirely abstract, platonic algorithm. While I agree it wouldn’t have been discovered by someone only interested in pure maths rather than applications, it is a strictly pure mathematical object, so you can write proofs about it which are just as absolute as any other.
I believe RSA can only be cracked by prime factorisation with the same certainty that I believe the primes are infinite. The only scenario in which they are false is one in which I am insane.
EDIT: The second paragraph is innaccurate, it can be safely treated as what I would say if I had a proof, which I thought I did until 5 minutes ago, (I never bothered to check it closely before because I thought it was knwon to be trivially true). Thanks to CipherGoth for pointing this out.
WHAT? Why do you believe this? Rabin is known to be secure if integer factorization is hard, but the same is NOT true of RSA.
Can I have a source for this? I was under the impression RSA was provably secure. If it is not then I will edit my previous post.
See Wikipedia on the RSA problem and in particular Breaking RSA may not be equivalent to factoring—which actually shows it’s a lot less likely than you might think that anyone is going to prove breaking RSA equivalent to integer factorization.
No cryptosystem that can be cracked given unbounded computing power can currently be “proven secure” since we’re a long way from showing that any useful problem is computationally hard. The best you can do is show that it’s hard given some assumption.
Not wishing to be rude, but what caused such incredible overconfidence that you would say
without personally understanding a proof to that effect? I do personally understand a proof that certain Rabin-based cryptosystems are as hard as integer factorization to break, and I’m still less confident of their theoretical security than I am of the infinitude of primes.
EDITED TO ADD: I should put a massive caveat on my assertions about Rabin before anyone gets the wrong impression: the proof that the cryptosystem is as hard as factoring depend on what is known as the “random oracle model”, which is a very useful but unrealistically strong assumption about our hash functions.
The cause of my overconfidence was a combination of exaggeration, arrogance and thinking I had a proof to the effect. As I said above, I had read that the problem was easy and so when I found a ‘proof’ I assumed it to be correct.
It was, as you point out, a huge error. I will aim never to repeat it.
Fair enough, thanks for answering! If you’re interested in this stuff, the proof that integer factorization is reducible to finding square roots modulo the composite isn’t too hard to get into.
Thanks for pointing it out!
This may actually be an example of qualitative difference between maths arguments and fiscal policy arguments that the OP talked about. My error was mathematical, so once it was pointed I had no wiggle room to rationalize. If you had corrected me on a point of fiscal policy I’m not sure it would have been so easy for me to just say oops.
Will you also dramatically reduce your belief in your own sanity?
If extreme overconfidence counts as insanity then yes I will.
I am strongly reminded by this whole conversation of http://www.spaceandgames.com/?p=27 & http://lesswrong.com/lw/mo/infinite_certainty/
just edit it.
What about weak key classes (i.e. particular classes of key that can be factorized quickly, possibly by special-purpose algorithms rather than general-purpose ones)? I’ve turned up several papers on the subject, but I don’t really have the maths to understand them, other than the take-home message that key generation is a minefield.
I don’t think key generation for RSA/Rabin is a minefield. There used to be a big list of precautions you were supposed to take, but the state of the art in factorization doesn’t care about those precautions, so just separately generate two primes of approximately the right size and multiply them together.
FWIW if you have a free choice of public key primitive, RSA should never be your choice; Rabin strictly dominates it. For most applications I’d recommend ECC of some kind.
Fair point.
I don’t know all the specifics which is what I meant when I said it could only be cracked by prime factorisation, rather than saying it couldn’t be cracked at all within reasonable time.
In fact, I do not know of any proof forbidding the existence of a quick algorithm for prime factorisation, although I would be surprised if this were not the case. (If I’m wrong and the impossibility has been proven then please tell me!)
Proving that integer factorization could not be done in polynomial time would incidentally prove that P != NP.
This seems to be intuitionist.
For practical purposes the rejection of induction seems trivial. For all real problems I will only ever be concerned about a finite number of numbers. I can prove the numbers in the particular problem I am working on are all fitting whatever criteria I need them to fit without relying on induction. I only need induction if I want to think that infininity means something beyond just Really A Whole Lot, or Really Really Big.