Comment by sdevlin | Hacker News Reader

Comment by sdevlin | Hacker News Reader

This is a pretty neat survey on the gulf between theory and practice, which is basically where practical cryptographic attacks live.

For example, RSA is based on the integer factoring problem, but they are not equivalent. Vanilla RSA does not offer what they call "chosen-ciphertext security"; in fact, a careful plaintext padding scheme† is needed to approximate this property.

PKCS#1v1.5 padding is not that scheme††: it formats the plaintext with a fixed leading byte (or two). This puts implementers in a tricky spot - what do you do if you decrypt a message and the prefix is wrong? If your answer was "throw an error", then congratulations! You've completely compromised the security of RSA.

They reference this attack briefly on page two of the linked article; grep for "Bleichenbacher". For more information, you can find Bleichenbacher's description of his padding oracle attack on PKCS#1 here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19..... I'll go further and say that implementing this attack is fun and enlightening - it's well worth your time.

† The scheme I'm alluding to is OAEP, but even it has implementation pitfalls that can sometimes be exploited.

†† But it is (bafflingly) the default padding scheme in every RSA library I can think of.

Well, all cryptography lies in practice, in the sense that there is no proof that P isn't = NP, with a small constant, theoretically. Indeed, public key cryptography might not be theoretically possible at all. Likewise, one-way functions (secure hashes) might simply not exist theoretically.

It is very important to remember that there is really next to no theoretical basis for the existence of cryptography at all. It's completely an applied field.

Likewise, if someone builds a physical architecture that solves prohibitively impractical cryptographic problems easily through a different means (e.g. quantum computing) then if it is cheap, nobody will care about the theoretical strength of the algorithm on classical computers.

"Theory and practice" was a poor choice of words on my part.

The point is simply that there are assumed-hard problems and cryptographic constructions based on them. If there is wiggle room between these things (as in RSA), it can severely undermine the strength of the system.

This is why proofs are valuable: if you can prove the cryptographic construct is reducible to the underlying problem†, you can focus your attention on the problem. I feel much better worrying about the practicality of quantum computers than whether there's a plaintext recovery attack that runs in a million queries.

† This isn't a panacea, unfortunately, as side channels are still a concern. Also: conformance of implementation to what has been proven.

That's quite possible. There are many problems which are said to be NP-hard, but are only NP-hard for the worst case. Linear programming, for example. Some cryptographic algorithms are much easier for some keys than others. There are known to be weak keys for some algorithms. Weak keys may be more common than generally assumed.

There's still no problem useful for public key encryption with a provable lower bound on solution work effort. Public-key encryption started with the knapsack problem, which turned out to have an efficient solution. Factoring is assumed to be hard because much mathematical effort has gone into studying factoring with only limited published success. It's not like there's a provable lower bound for it.

The only thing we really know works is a one-time pad, and even that can be screwed up by operational errors. A "one-time pad" used twice is easy to break. It's worth reconsidering one-time pads; in the era of the 64GB flash drive for $30, you could have enough one time pad for a thousand hours of voice calls on one USB stick.

Linear programming is not NP-hard, worst case or no. The interior point method [1] solves it in polynomial time.

[1] http://en.wikipedia.org/wiki/Interior_point_method

Reply on news.ycombinator.com