[Cryptography] Information. it's the real thing

[John Denker]

It is always important to think about the /information/ 
carried by our messages.  This includes the information
available to the intended recipient, as well as the info
available to the adversaries.  This is relevant to what 
John Young wrote on 02/16/2015 10:34 AM:
> "The very encryption used to secure transports is used to hide data 
> exfiltration."
... and relevant to a lot of other recent discussions,
and to crypto and security in general.

Information.  It's the real thing.

Regrettably, in dozens upon dozens of messages recently,
people have tossed around phrases like "indistinguishable
from random" (I-F-R).

Although I-F-R is "close" to the right idea, it is not
exactly the criterion we should be using.  To my astonishment, 
on 01/21/2015 09:17 PM, Jerry Leichter contradicted me on 
this point:

>> the first thing you need to get anywhere in formalization is precise
>> definitions.

>> A common strong definition of semantic security says [....]

The nice thing about formal definitions is that there
are so many to choose from.  Anyone is free to define 
terms however they like, but the result is a choice,
not a law of nature.  There is no guarantee that the 
results will apply to the real world.  Cryptology lives 
within the intersection of fancy math *and* down-to-earth 
engineering.  You need both.

I choose to formalize many things in terms of information.
Often it is appropriate to exclude information that would
be computationally infeasible to obtain.

I do not choose the I-F-R criterion, because it is not 
viable in the real world, and I can prove it.  An example 
suffices to make the point:

  _Message Length_ is one of the many things that can be
  used as a covert channel.  It has been used this way 
  for a long time.  It has been used by both teams, i.e.
  when the sender wants it to be used that way (for
  exfiltration) and when the sender doesn't (but the 
  opponent uses it anyway).

So .... does anybody really think that the message length
needs to be indistinguishable from random?  If so, we are
in big trouble, because message length could be anything
from zero on up, and there does not exist any uniform
random distribution on such a range.  The formal laws of 
probability forbid it.  This is an example of what formality 
can do for you.  Sometimes it tells you that your formalism
is broken.

In the real world, people sometimes do send traffic that
resists traffic analysis.  One option is to send a lot 
of messages, all with the same length.  Consider for 
example ATM cells.  Many trillions of them are sent, all 
with the same size.  You will not have much luck traffic-
analyzing those lengths!  Arguably the first one told 
you something, namely the length, but it didn't tell you 
anything you didn't already know, given that it was an
ATM cell to begin with.  Even if you didn't know a_priori
that it was an ATM cell, after a while the leakage (on a 
per-message basis) goes asymptotically to zero anyway.  
As long as the traffic is indistinguishable from business-
as-usual, the nobody gains any information from it.

There is an extensive literature on this, including
contributions from guys like Shannon, Kullback, and
Leiber, who were not exactly clueless about crypto.
If you think your formal methods are better than theirs, 
that's an extraordinary claim, and will require some
extraordinary proof.  My suggestion: if you want to 
formalize something, in all likelihood your time would
be well spent formulating it in terms of information 
gain and things like that, rather than some notion of
"indistinguishable from random" ... which is no more 
formal, and a lot less viable in the real world.

------------

Speaking of cover traffic:  If you look at the header
of this message, you will probably find a field called
"Quilt" which contains 64 symbols that could convey
6 bits apiece, for a total of 384 bits.  All of my 
outgoing mail has had such a header for a while now.
Maybe it's just random cover traffic ... or maybe it 
is a cleverly-encoded message.  By sending such fields,
I create a forest.  That's a good place to hide a tree,
if I ever need to.

If you are wondering about the name: There is such a
thing as a crazy quilt, in contrast to a patterned 
quilt:
  http://dictionary.reference.com/browse/crazy+quilt