The Factoring Cryptopocalypse
daemonology.net
The Factoring Cryptopocalypse
1–10 of 26 posts
Re: The Factoring Cryptopocalypse
#2Previous discussions on the presentation:
Re: The Factoring Cryptopocalypse
#3Previous discussions on the presentation: https://news.ycombinator.com/item?id=6191171 https://news.ycombinator.com/item?id=6155502
Thanks, I missed the first discussion and was inspired to write only by the second discussion.
Re: The Factoring Cryptopocalypse
#4I think Colin's bang on here. Now is the time for cryptographers and software developers to act to implement a mature alternative to RSA, but it's not the point for your average joe to switch to an as yet relatively untested/unproven ECC implementation.
For what it's worth, Tom Ritter recently posted his notes on de-anonymizing alt.anonymous.messages[1], something widely believed to be very anonymous and very secure. It's an interesting read and shows why you not only need the crypto to be sound, but the implementation and your own use of it to be right too.
Re: The Factoring Cryptopocalypse
#5I think Colin's bang on here. Now is the time for cryptographers and software developers to act to implement a mature alternative to RSA, but it's not the point for your average joe to switch to an as yet relatively untested/unproven ECC implementation. For what it's worth, Tom Ritter recently posted his notes on de-anonymizing alt.anonymous.messages[1], something widely believed to be very anonymous and very secure.…
How is EC “relatively untested/unproven”? It's been in OpenSSL for ages (by internet norms), is the subject of numerous national standards. It secures a billion dollar bitcoin economy.
Re: The Factoring Cryptopocalypse
#6For someone who is somewhat unfamiliar with cryptography, what is the obstacle in creating cryptography that is provably secure: in other words, cryptography that can be absolutely trusted within certain provided parameters.
Re: The Factoring Cryptopocalypse
#7Out of curiosity: If you were to design Tarsnap from scratch in 2013, would you still use RSA?
Re: The Factoring Cryptopocalypse
#8Out of curiosity: If you were to design Tarsnap from scratch in 2013, would you still use RSA?
I think so.
Re: The Factoring Cryptopocalypse
#9For someone who is somewhat unfamiliar with cryptography, what is the obstacle in creating cryptography that is provably secure: in other words, cryptography that can be absolutely trusted within certain provided parameters.
Heuristically speaking, this problem is at least as hard as the P != NP question, which is one of the millenium problems for which the Clay institute has awarded one million dollars to whoever resolves it.
From a theory point of view, breaking a crypto-system typically means something like being able to do the following fast (i.e., in polynomial time): Given two plaintexts and a ciphertext which is the encryption of one of those two plaintexts, decide which of the plaintexts it is. Of course you could flip a coin, so the essential condition is that your success probability must be larger than 1/2.
So to show that a crypto-system is secure, you have to show that the problem of breaking it cannot be solved in polynomial time. We simply do not know how to show that any useful problem cannot be solved in polynomial time (we do know that P != EXPTIME, but we don't know any problems in EXPTIME that would be useful for cryptography). Hence the lack of provable security.
Re: The Factoring Cryptopocalypse
#10For someone who is somewhat unfamiliar with cryptography, what is the obstacle in creating cryptography that is provably secure: in other words, cryptography that can be absolutely trusted within certain provided parameters.
I'm by no means a cryptography expert, but a few difficult bits from what I've gathered, observing from a different area of CS that also cares about hardness (AI):
1. At the base, we need a one-way function [1], something that's easy to compute in one direction but hard to reverse. For example, it is believed to be much easier to multiply two large primes than to factor the result back into the original two primes. However so far nobody has come up with a way of proving that a function is one-way for any plausible definition. This is often, in the popular press, thought to be the P=NP question, but that would only prove the negative: if P=NP, then there are no one-way functions (for a certain definition). But even if P!=NP were proven, it is still not necessarily the case that there are one-way functions. In particular, NP-complete problems are not automatically one-way functions, because that is only a worst-case hardness notion, and cryptosystems that are only unbreakable in the worst case for the attacker are not so useful [2] (and indeed none of the major cryptosystems currently used rely on NP-complete problems).
In short, the seemingly hard problems that have had practical cryptosystems built out of them, such as integer factorization (closed related to the RSA problem) and the discrete logarithm problem on elliptic curves (ECC) only seem hard, but are not proven hard in any rigorous sense. This is an interesting outstanding question mathematically, because it would be nice if we understood either why these are hard and be able to prove them hard for some definition, or else to discover why they in fact aren't.
2. At the practical level, it's hard to produce a security proof that takes into account an attack completely outside the conception of the original framework. For example, early security proofs were completely oblivious to the problem of side-channel attacks, since they were proving the security of certain mathematical procedures, in a framework that did not countenance things like "your mathematical procedure might be run on an EC2 instance where your attacker can also get a VM and collect some (noisy) data about what it's doing". This is arguably a quite different question from whether the fundamental cryptosystem's approach is flawed, but this kind of consideration is the source of many practical attacks.