Difference between theory and practice of security and cryptography?

Question

What interesting differences are there between theory and practice of security and cryptography?

Most interesting will of course be examples that suggest new avenues for theoretical research based on practical experience :).

Answers might include (but are not limited to):

• Examples where theory suggests something is possible but it never gets used in practice
• Examples where theory suggests that something is safe that is not safe in practice
• Examples of something in widespread practical use has little theory behind it.

...

Caveat

If your answer is essentially of the form "Theory is about asymptotics, but practice is not," then either the theory should be really central, or the answer should include specific examples where the practical experience on real-world instances differs from the expectations based on the theory.

---

One example I know of: secure circuit evaluation. Very powerful in theory, but too complicated to ever use in practice, because it would involve taking your code, unrolling it into a circuit, and then doing secure evaluation of each gate one at a time.

Answer 1

Oh boy, where to start.

The big one is definitely black boxes. Crypto researchers make a fuss about things like uninstantiability problem of the Random Oracle Model. Security researchers are at the other extreme and would like everything to be usable as a black box, not just hash functions. This is a constant source of tension.

To illustrate, if you look at the formal analysis of security protocols, for example BAN logic, you will see that symmetric encryption is treated as an "ideal block cipher." There is a subtle distinction here — BAN logic (and other protocol analysis techniques) don't claim to be security proofs; rather, they are techniques for finding flaws. Therefore it is not strictly true that the ideal cipher model is involved here. However, it is empirically true that most of the security analysis tends to be limited to the formal model, so the effect is the same.

We haven't even talked about practitioners yet. These guys typically don't even have a clue that crypto primitives are not intended to be black boxes, and I doubt this is ever going to change — decades of trying to beat this into their heads hasn't made a difference.

To see how bad the problem is, consider this security advisory relating to API signature forgeability. The bug is partly due to the length-extension attack in the Merkle-Damgard construction (which is something really really basic), and affects Flickr, DivShare, iContact, Mindmeister, Myxer, RememberTheMilk, Scribd, Vimeo, Voxel, Wizehhive and Zoomr. The authors note that this is not a complete list.

I do think practitioners deserve the lion's share of the blame for this sad state of affairs. On the other hand, perhaps crypto theorists need to rethink their position as well. Their line has been: "black-boxes are impossible to build; we're not even going to try." To which I say, since it is clear that your constructions are going to get (mis)used as black boxes anyway, why not at least try to make them as close to black boxes as possible?

The paper Merkle-Damgard Revisited is a great example of what I'm talking about. They study the security notion that "the arbitrary length hash function H must behave as a random oracle when the fixed-length building block is viewed as a random oracle or an ideal block-cipher." This kind of theoretical research has the potential to be hugely useful in practice.

Now let's get to your example of circuit evaluation. I beg to disagree with your reasoning. It's not like you would take a compiled binary and blindly turn it into a circuit. Rather, you'd apply circuit evaluation only to the underlying comparison function which is usually quite simple. Fairplay is an implementation of circuit evaluation. A colleague of mine who's worked with it tells me that it is surprisingly fast. While it is true that efficiency is a problem with circuit evaluation (and I do know of real-world instances where it was rejected for this reason), it is far from a showstopper.

The second reason I disagree with you is that if you think about some of the typical real-life scenarios in which you might conceivably want to carry out oblivious circuit evaluation — for example, when two companies are figuring out whether to merge — the computational costs involved are trivial compared to the overall human effort and budget.

So why then does no one use generic secure function evaluation in practice? Great question. This brings me to my second difference between theory and practice: trust actually exists in practice! Not everything needs to be done in the paranoid model. The set of problems that people actually want to solve using crypto is much, much smaller than what cryptographers imagine.

I know someone who started a company trying to sell secure multiparty computation services to enterprise clients. Guess what — no one wanted it. The way they approach these problems is to sign a contract specifying what you can and cannot do with the data, and that you will destroy the data after you're done using it for the intended purpose. Most of the time, this works just fine.

My final point of difference between theory and practice is about PKI. Crypto papers frequently stick a sentence somewhere saying "we assume a PKI." Unfortunately, digital certificates for end users (as opposed to websites or employees in a corporate context, where there is a natural hierarchy) never materialized. This classic paper describes the hilarity that ensues when you ask normal people to use PGP. I'm told that the software has improved a lot since then, but the underlying design and architectural issues and human limitations are not much different today.

I don't think cryptographers should be doing anything differently as a consequence of this lack of a real-world PKI, except to be aware of the fact that it limits the real-world applicability of cryptographic protocols. I threw it in because it's something I'm trying to fix.

Answer 2

Randomwalker's answer is very good. My favorite gap between theory and practice is the random oracle model. This seems a very secure heuristic in practice (assuming people don't do something stupid and at least do length extension propertly, see also randomwalker's answer) but we don't have any positive theoretical results about it. In fact, all theoretical results about this heuristic are negative. I think this is a great research question and hope some day some interesting positive results about this model will be proved.

Regarding obfuscation as far as I know even in practice, although it's in widespread use, obfuscation is not considered as secure as encryption, and it's not considered prudent to use obfuscation to hide a long term and very sensitive secret. (As opposed to encryption using random oracle, which people are completely comfortable with using for this.) So in that sense, the gap there between theory and practice is not as large. (i.e., obfuscation is hugely interesting area which we are far from understanding both in theory and in practice.)

Answer 3

Homomorphic encryption and secure multiparty communication are two of the big, recent discoveries in cryptography that haven't been sufficiently studied to make practical yet: research efforts like PROCEED are moving in this direction to identify what kind of programming model we might use to write this sort of computation, as well as find optimizations to the core cryptographic algorithms that make them run in reasonable time. This is a fairly common occurrence in cryptography: we start off with (comparatively) simple algorithms that take a long time to run, and then cryptographers spend years using mathematics to optimize the algorithms further and further.

Answer 4

Examples where theory suggests something is possible but it never gets used in practice:

It is pretty easy to find examples of things that are solved in theory but either (1) are too inefficient to use in practice or (2) no one cares about. Examples: (1) (generic) zero-knowledge proofs, (2) undeniable signatures. In fact, look at any crypto conference and at least half of the papers will probably fall into one of these categories.

Examples where theory suggests that something is safe that is not safe in practice:

This question is a little vague, so I'm not sure if this answers it -- but there are plenty of examples of 'provably secure' schemes that get broken in practice because the security definition did not match the deployment scenario. In the last few years alone there were attacks on (provable variants of) SSH and IPSec, among others.

Examples of something in widespread practical use has little theory behind it:

I assume you mean in the crypto world, not in the general security world. A good example is DSS signatures, which have no proof of security.

Answer 5

Binary obfuscation is widely used today in a variety of applications (and is in fact even used in the MathJax.js file used on this website to render CSTheory's TeX typesetting system). The goal of binary obfuscation is to preserve semantics and disfigure syntax - i.e. to take an input Turing Machine $M$ and create an equivalent Turing Machine $M'$ such that $M'$ rejects a string $w \iff M$ rejects $w$, such that $M'$ accepts a string $w \iff M$ accepts $w$ and such that the run time complexity of $M'$ is the same as $M$ on all inputs. Finally, there is the additional stipulation that $M'$ must be difficult to both understand and to modify. Industry sees such obfuscation as a good trade off involving a sacrifice of slight (constant time) overhead for the benefit of increased difficulty for adversaries interested in understanding, breaking or stealing IP from $M$.

There are many commercial companies that offer binary obfuscation solutions, and there are also several open source solutions. Exact methods for obfuscation, of course, are kept secret; the obfuscation paradigm prevalent in industry is heuristic, so knowing the algorithms used to obfuscate a binary in this context will generally guarantee some advantage in deobfuscation. Obfuscation in industry is known as "security through obscurity."

There are theoretical approaches to the problem of obfuscation that formalize the desires of industry but rely on a strictly stronger notion of security based on computational intractability (imagine replacing integer and string equivalence tests with one way function equivalence tests). In particular, the study of composable point obfuscation has been advanced to try to solve the obfuscation problem interesting to industry. Unfortunately the most wide spread theoretical model for obfuscation based on a model inspired by tamper-proof hardware was given an impossibility result in 2001 by Barak et al in the paper "On the (im)possibility of obfuscating programs". (Several other models have since also been given impossibility results).

Right now the theory of program obfuscation is in a state of flux, requiring a new (likely less restrictive) model. In fact, the main problem with the theory is its lack of an agreed upon model (and therefore formal garuntees). The recent advent of Fully Homomorphic Encryption may provide such a basis (this is purely speculation on the part of this author).

To clarify, obfuscation matches your third example: "Examples of something in widespread practical use has little theory behind it." Obfuscation is used widely today by both the industry and by those with more nefarious purposes. Obfuscation in industry is not currently based on any rigorous theory despite attempts.

Answer 6

There is a significant gap even when it comes to basic primitives such as pseudorandom generators. Consider for example pseudorandom functions. In practice people use things like AES, which differ from theoretical candidates (Goldreich, Goldwasser, Micali; Naor, Reingold; etc.) along several dimensions: First, the parameters are completely different, e.g. AES can have key length which equals the input length, which is unheard of in theoretical constructions. Perhaps more importantly, AES (and many other block ciphers) follow the so-called substitution-permutation network paradigm which is quite different from the way theoretical constructions go (e.g. those mentioned above).

Most interesting will of course be examples that suggest new avenues for theoretical research based on practical experience :).

I think the above is such an example, see for example this paper with Eric Miles (from which essentially this answer is taken).