OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
Crypto Archives: Re: 56 Bits?????

Re: 56 Bits?????

Peter Gutmann (pgut001cs.auckland.ac.nz)
Thu, 28 Oct 1999 04:43:28 (NZDT)

Robert Hettinga <rahshipwright.com> writes:

>Viz., what's this "ComCryption" stuff he's talking about below?

I assume it's ConCryption(tm), US patent 5,479,512:

  "A method and apparatus for the integrated compression and encryption
  (concryption) of clear data and for the deconcryption of concrypted data to
  obtain the clear data for utilization. For concryption, the clear data and
  an encryption key are obtained, at least one compression step is performed
  and at least one encryption step is performed utilizing the encryption key.
  The encryption step is performed on the final or intermediate result of a
  compression step, with compression being a multistep operation. For
  deconcryption, decompression and decryption steps are performed on concrypted
  data in essentially the reverse order for the performance of corresponding
  compression and encryption steps during the concryption operation."

The main claim:

  "1. A method for utilizing a data processor to change the form of data
  comprising the steps of:

    a) obtaining the data at the processor in clear form;

    b) obtaining an encryption key at the processor;

    c) the processor performing a multi-step compression operation
    on said clear-form data;

    d) the processor automatically utilizing said encryption key in
    conjunction with the results as directly generated by the
    processor for a selected step of said compression operation in
    performing an encryption operation, the compression steps of
    step (c) and the encryption step of sted (d) being integrated
    to be performed as parts of a single operation; and

    e) the processor outputting the resulting compressed and encrypted
    version of the clear-form data."

is identical to the method in the May 1988 Cryptologia article "A Redundancy
Reducing Cipher", but prior art has never stopped the USPTO from issuing a
patent before. The rest of the patent is also trivially obvious, but that
won't stop a US patent either.

I've seen a few variants of these schemes in the past, and even mentioned them
in passing in my thesis about a hundred years ago (there's more prior art for
you, dating back a century or more). The problem with all of them (and the
reason I never followed any of the ideas up) is that using the output of a
(cryptographically strong) RNG to manipulate a compression scheme is never
noticeably better than simply XOR-ing the RNG output into the compressed data
like a standard stream cipher. Consider the simplest case of a static Huffman
tree being used to compress data. To use it for encryption, you take the next
bit of RNG output and use it to adjust the decision over whether you follow the
left or right branch of the tree (in effect you XOR the RNG bit with the bit
which encodes the branch of the tree you follow). However this is equivalent
to just XOR'ing the output of the Huffman compressor with the RNG output, which
means you've just reinvented the stream cipher.

The main problem I see with these schemes is that there is to date little
research which shows that this strengthens security beyond the level of "throw
in enough mess to confuse them and they'll never figure it out" (something
which is very popular with amateur encryption algorithm designers). I posted
the results of some basic work I did in 1991 or 1992 to sci.crypt (a post now
lost AFAIK) which showed that it was possibly to perform a known-plaintext
attack on an arithmetic coder/encryptor even if several tens of initial random
symbols had been prepended to the data to compress in order to "randomize" the
initial state. The best I could find in my archives was the following posting
from April 1994:

>I looked at it a few years ago using arithmetic coding, wrote up a few pages
>on it, posted it either to sci.crypt or comp.compression, and have never
>been able to find it again since then. From what I remember, the end result
>was rather discouraging. Assuming an order-0 model, you needed to generate
>some hundreds of random symbols to obscure the initial probabilities of each
>symbol being compressed. When compressing a Markov source, you could make
>an estimate of what symbols were likely to occur, and use this as the basis
>for an attacld affect only symbols which don't appear in the text, resulting in
>"encryption" at all. For a random key and English text, I think you needed
>something like 50-odd random symbols before there was a noticeable effect on
>the compressed data (this was a while back, YMMV on the exact number).
>
>With a higher-order model, the problem is even worse - the skewing of
>probabilities is even less effective since most of the time you change the
>probabilities of symbols which *never* occur (this counts for most
>dictionary-based compressors as well, which are roughly equivalent to
>higher-order Markov models in an obscure way I won't bore you with here).
>
>There are other problems as well, such as the amount of compression achieved
>being a good indication of how well the initial seeding of the model fits
>the data being compressed - this leaks information on the key being used.
>
>In short, it's not worth it. Compress the data first, then use a proper
>encryption algorithm to encrypt it.

Sean Irvine from the University of Waikato did his PhD thesis, "Compression and
Cryptology", on this topic, he also had a paper "On the insecurity of
arithmetic coding" in Computers & Security in 1995 (which I haven't read).

>I leave discussion of the merit/irony/longevity/ubiquity, or lack thereof,
>of an Intel-Inside CryptoAPI on an Apple machine as an exercise for the
>reader.

Ah, CDSA, the emacs of crypto API's.

>Should you read the CDSA 2.0 spec, please talk to us about where you think
>the weaknesses are.

I used to have a copy here, but it started bending light in its vicinity
towards it. I eventually found half a dozen volunteers and we spent the
morning carrying it outside for shipment to the Caribbean. The last I heard
they were going to use it as an artificial island to build casinos and tax-
free banks on. I guess my main objection to CDSA is its ecological impact,
the fact that you need to deforest a small country for each copy printed is
somewhat upsetting.

Peter.

This archive was generated by hypermail 2.0b3 on Wed Oct 27 1999 - 13:57:00 CDT