compression & nulls in cryptosystems

[John Denker]

At 10:39 AM 5/29/01 -0400, Matt Blaze wrote:

>While I agree in principle that plaintext with a high information content
>probably makes it harder to mount a ciphertext-only attack against most
>(non-randomized, at least) secret-key cryptosystems, I'm not at all
>convinced that the security benefits outweigh even very small costs
>in practice.
>
>I've found that a great many complete communications systems (including the
>application layer) make it fairly easy, somewhere in the protocol stack,
>for an attacker to introduce chosen plaintext or use an endpoint
>as a chosen-ciphertext oracle, and I've never met a real system that
>doesn't make it easy to learn or guess known plaintext.

OK, I'll bite.

1) Do these remarks apply to the moats I've been building (little IPsec 
gateway boxes)?

2) What's a chosen-ciphertext oracle?  How might an attacker use a moat as 
such?

  3) I can imagine how an attacker could feed chosen plaintext through my 
moat.  For instance she could email me a chosen message and expect me to 
download it via the moat.  But getting back to the topic of compression and 
nulls:  It would seem that they would serve to convert the chosen text into 
a partially-chosen but partially-unknown (!) text.

So I don't get the point of the passage quoted above.

  *) If the point is that there's a lot of bad crypto out there, then of 
course I agree.  But that doesn't mean we can't try to improve it.

As I said in my previous note, there are cases where the system is so bad 
that small improvements don't matter, and there are cases where the system 
is so good that small improvements don't matter.  But in the middle there 
is a vast region where we get to discuss the costs and benefits of various 
proposed improvements.

  *) If the point is that a basically-good idea can be implemented so badly 
that it doesn't help, then yes, that goes without saying.  And I agree that 
many off-the-shelf compression algorithms may be in this category.  But 
that doesn't mean we should stop looking for good solutions.

  *) If the point is that compression and nulls have infinite cost or zero 
value, then I find this highly implausible.
  -- ISTM nulls would materially hinder differential cryptanalysis.
  -- ISTM nulls would materially hinder linear cryptanalysis.
  -- ISTM compression+nulls would materially hinder a key-search
     along the lines of the EFF DES cracker.
  -- Can somebody give examples of attacks that would not be hindered?

  *) If the point is that there is something else we should be doing with 
our bandwidth and computational resources, it would help to have a more 
explicit statement of what the alternatives are, and their relative costs 
and effectiveness.

================

Let me also remark that nulls in particular are conceptually related to
  -- salt, and
  -- session keys
which are pretty standard technology in appropriate situations.  It doesn't 
make sense to pooh-pooh such techniques.

I always scratch my head when somebody says that XX attack on YY algorithm 
requires a huge carefully-chosen plaintext, and ends the discussion there, 
when by adding nulls you can guarantee that no chosen plaintext ever gets 
processed as such.




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com