[Cryptography] BBC to deploy detection vans to snoop on internet users

[Jerry Leichter]

>> We define security for ciphers algorithms, and often for modes and even protocols, in a way that completely ignores leakage of message length and timing - assuming that it doesn't really matter very much (if you use a block cipher the length is only know mod 16 or maybe somewhat more, who cares) or, in the case of timing, that this is simply outside the domain of analysis.
> 
> No, cryptologists do not assume that it doesn’t really matter very much.
> 
> Cryptologists know very well that these issues can be very important for applications. What cryptologists also know is that crypto primitives usually cannot deal effectively with these issues, since crypto primitives must support many different application requirements....
It's reasoning like this which, while valid in its own way, undermines the real value in cryptographic research.

When modern era of cryptographic research started, not so long ago - as a graduate student, I gave a talk about Shannon's work on security and brought up RSA in a CS department theory seminar to a group that had no idea there was anything in the field in 1979 or so; a few years later, several people in the department were doing research on cryptography and a fellow grad student was doing his thesis on cryptographically secure voting algorithms - we really had no solid idea what cryptography was supposed to actually accomplish.  People would toss out such ideas as "well, if you use RSA, determining the plaintext is as hard as factoring" which we were to learn to our chagrin that this missed the point - e.g., given an oracle for the bottom bit of a RSA-encrypted message, you could decrypt the whole thing, and "obvious" protocols for using RSA made it easy to turn the legitimate recipient into such an oracle.  (Of course, even the statement itself is still not known to be true!)

Known plaintext attacks, chosen plaintext attacks, adaptive plaintext attacks - it wasn't at all clear how to fit these into a theory.  Suppose you had one encryption function E_k(P) that you could prove could not be broken (against some ill-defined set of attacks, but OK) better than by brute force.  Consider a new function, E1_k(P) = E_k(P) || P0, where || is concatenation and P0 is the bottom bit of P.  It's "within a factor of 2 as good" as E.  And yet you really don't want to use it!

Examples of this (and more subtle) sorts finally lead us to notions of semantic security.  Along with that emerged a goal:  The security of the system *could not depend on the data being exchanged!*.  After all, E1 is a perfectly good system if you just tell users to always set the bottom bit of every message to 0.

All that was fine for single blocks, but for multiple blocks, we need to look further - even a perfectly secure block cipher leaks information in ECB mode.  So we developed a theory - still not as solid as we'd really like - for encryption modes.

Symmetric systems proved to be a much tougher nut to crack - which is why we only use them to exchange random session keys for asymmetric systems.  And even so, there are issues to this day.

The goal of "just get the data securely from here to there, whatever the data is" *has to be* the goal of a science of cryptography.  Note that it's a science and and an associated engineering practice; it is *not* mathematics.  It *relies heavily on mathematical methods*, but it's something different.  As often happens in technical fields that use a great deal of mathematics, the tail can end up wagging the dog:  Much of the research ends up being pretty math that doesn't directly address the driving problems.  That's fine as far as it goes, but if it goes too far, the field risks disconnecting itself from those who rely on it.

What I'm pointing out is that cryptography as a science has chosen to rule out of bounds various "semantic leaks" that, early on, were considered (a) of minor importance; (b) too hard to address.  This is like the early work on system and network security, which declared DoS attacks out of bounds for the same reasons.  As we've learned, however, these are very much *in bounds* for real systems!  So we need to think about them and come up with some good solutions.

                                                        -- Jerry