Difference between theory and practice of security and cryptography? 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.
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.