[Cryptography] quantum computers & crypto

[Jerry Leichter]

>> A paper quite some time ago showed that encrypted, compressed speech could be
>> read with reasonable accuracy just by looking at the lengths of blocks in
>> streams of compressed packets.  Similarly, determining which of the top 1000,
>> say, most popular web sites is being browsed in an encrypted session has been
>> shown to be pretty easy - again based on the lengths of the messages being
>> exchanged.
> 
> There's a neverending series of papers on this, covering encrypted speech,
> video and other types of content, but they're really just traffic analysis
> papers rather than anything specific to compression use.
At least for the paper I recall, compression was very relevant, since the alternative was a steady 64Kbit signal, which doesn't carry any real length/timing information.  It was the compression that gave the game away.

>  Even when
> compression is used - and for a lot of the papers it isn't - it just changes
> the problem to a slightly different form of traffic analysis.
I'm not sure where the boundaries are.  The point of encryption is to hide the semantic content of the plaintext.  If you define the semantic content as just the bits of a single piece of plaintext in isolation - which is what we usually do - then traffic analysis doesn't enter and we can consider it a separate problem.  That's actually usually fine for data at rest; that's pretty much a solved problem these days.  But the most concern we have these days is with data in transit, and even more with ongoing exchanges.  The plaintext semantics then extends well beyond "just the bits" and something more is needed.

>> The fix for this is of course well known:  Padding.
> 
> That doesn't work either, there's an accompanying string of papers showing
> that all of the obvious traffic-hiding/morphing techniques don't really work.
That depends on the setting.  For a point-to-point connection, if you send a constant-rate stream of encrypted data - sending nulls when there's no actual message - then you're safe.  Since it's a point-to-point connection, you've effectively declared out of bounds the information about who is talking to whom - that's fixed outside of the system.  Rather an expensive approach, of course, though it's been used.

Things get more complex if you have multiple participants and you want to hide who's talking to whom.  There is a classic technique in which all encrypted messages are posted in public and all participants read all messages and discard any they can't decrypt.  Modify this so that everyone writes and reads at a constant rate and it should be secure - though impractically expensive in any likely scenario.

> In a nutshell, defence against traffic analysis is really, really hard.
Well, it is if you want an actual real-world implementation!  :-)

> More generally, the more interactive your traffic is - in the case of the CRIME
> attack I referenced the victim's browser is under the control of the attacker
> and does the attacker's bidding - the easier it is for at least some of your
> crypto guarantees to be bypassed.
I'm not sure that "interactive" as such is the right criterion.  What matters is (a) any non-randomness in the entire set of inputs - the plaintext, in the broadest sense - to the "security system"; (b) any correlations between non-randomness in the plaintext and non-randomness in the ciphertext.  Classically, we only consider the plain- and ciphertexts as strings of bits and look for correlations there.  But we can - and must - take a broader view.  Interactive systems have correlations in ciphertext length and timing between successive messages.  In conventional systems, these leak through in correlations with the length and timing of ciphertext messages.  You can decide these are side-channel attacks, just like correlations between bits and power draw, and declare them out of bounds of cryptography and Somone Else's Problem; or you can view cryptography more broadly.  Agencies like the NSA certainly laugh at the notion that "that's cheating"; they care about results, so look as broadly as they can.

                                                        -- Jerry