Subject: Re: Compressed data type for S/MIME

From: [email-masked] (Peter Gutmann)
Date: Thu, 29 Jul 1999 07:55:44 (NZST)

Paul Hoffman / IMC <[email-masked]> writes:

>I think it is something that would be good to address if we are honest
>about how long it will take to get into products. It doesn't need any MUST
>or SHOULD. Wording to the effect of "future revisions to CMS SHOULD include
>this extension" is appropriate.

OK... hmm, shouldn't it be "Future implementations of CMS SHOULD include this
extension"?  The intent is to specify the behaviour of implementations, not
standards authors (if the latter is actually the case then gimme a minute to
crank out draft-ietf-smime-buy-peter-dinner-00.txt: "Pizzas compliant with 
this document shall include one or more of the following: ...").

>I think that your initial draft should also describe an option in 
>sMIMECapabilities that says "receiver can handle compression types a, b,
>and c" so that S/MIME implementations can add this in in an orderly fashion.

Fairly easy, just include the compression AlgorithmIdentifier as a capability.
I strongly suspect that there'll never be anything other than zlib defined (at
least in the foreseeable future) so having to handle a single new OID 
shouldn't be much of a problem:

-- Snip --

Implementations SHOULD use the SMIMECapabilities attribute to indicate their
ability to process compressed content types.  A compression SMIMECapability
consists of the AlgorithmIdentifier for the supported compression algorithm, in
the case of the algorithm specified in this document this is is-alg-zlib with
parameters NULL.  Alternatively, the use of compression may be handled by prior
arrangement (for example as part of an interoperability profile).

-- Snip --

Peter.

---

From: "Bob Jueneman" <[email-masked]>
Date: Wed, 28 Jul 1999 15:34:56 -0600

Peter, 

I don't know zlib from a zebra, but way back in the PEM days I argued for the 
same sort of thing.  The use of encryption obviously makes the use of statistical
modems, and other bandwidth-efficiency devices essentially impossible, and
so it is essential to compress the plaintext before encrypting it.

But a question. Rather than inventing a new CMS data type, couldn't this be
 implemented as a new encryption algorithm, such as zlib-with-triple-DES?

I certainly understand that an independent wrapping mechanism would provide 
more generality, but I am a little concerned that CMS may not be as widely adopted
as some might hope, whereas implementing it within a crypto algorithm would allow
SSL, TLS, PSEC, etc., etc., to implement it within their suite of supported algorithms.  
Just a thought.

Also, don't some/most compression algorithms make use of previously calculated
symbol tables?  Couldn't those tables be transferred and referred to independently, 
rather than being sent with the text, assuming they are reasonably constant?

This might argue that some parameters to the compression algorithm wold be nice to have.

Bob

>>> Peter Gutmann <[email-masked]> 07/28/99 11:16AM >>>
From the "Why on earth hasn't anyone done this before?" department: I've just
spent the last hour or so adding zlib-based compression to an existing S/MIME 
implementation.  All this needs to work is a new content type, CompressedData.
Compressing data before processing has so many advantages (eliminates known
plaintext, speeds up processing by slow crypto algorithms, and reduces message
size, especially for the sorts of things you'd typically want to protect
(spreadsheets, documents, etc)) and implementing it with zlib is such a no-
brainer that I don't know why noone's looked at this before.  What do people 
think of the following as a new S/MIME draft?

Peter.

-- Snip --

Internet Draft                                      Editor: Peter Gutmann
draft-ietf-smime-compression-00.txt                 University of Auckland
July 20, 1999
Expires January 2000

                   Compressed Data Content Type for S/MIME

Status of this memo

This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.

Internet-Drafts are working documents of the Internet Engineering Task Force
(IETF), its areas, and its working groups.  Note that other groups may also
distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and may
be updated, replaced, or obsoleted by other documents at any time.  It is
inappropriate to use Internet- Drafts as reference material or to cite them
other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt 

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

Abstract

The Cryptographic Message Syntax data format doesn't currently contain any
provisions for compressing data before processing it.  Compressing data before
transmission provides a number of advantages including the elimination of data
redundancy which could help an attacker, speeding up processing by reducing the
amount of data to be processed by later steps such as signing or encryption,
and reducing overall message size.  This document defines a format for using
compressed data as a CMS content type.

This draft is being discussed on the "ietf-smime" mailing list.  To join the
list, send a message to <[email-masked]> with the single word
"subscribe" in the body of the message.  Also, there is a Web site for the
mailing list at <http://www.imc.org/ietf-smime>.

1. Introduction

This document describes a compressed data content encryption type for S/MIME.
This is implemented as a new ContentInfo type and is an extension to the types
currently defined in CMS [CMS].

The format of the messages are described in ASN.1:1994 [ASN1].

The key words "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT",
"RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as
described in [RFC2119].

1.1 Compressed Data Content Type

The compressed-data content type consists of content of any type compressed
using a specified algorithm.  The following object identifier identifies the
compressed-data content type:

  id-ct-compressedData OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840)
    rsadsi(113549) pkcs(1) pkcs-9(9) smime(16) ct(1) 3 }

The compressed-data content type shall have ASN.1 type CompressedData:

  CompressedData ::= SEQUENCE {
    version CMSVersion,
    compressionAlgorithm CompressionAlgorithmIdentifier,
    encapContentInfo EncapsulatedContentInfo
    }

The fields of type CompressedData have the following meanings:

    version is the syntax version number.  It shall be 0.

    compressionAlgorithm is a compression algorithm identifier, as defined in
    section 2.

    encapContentInfo is the content which is compressed.

2. Compression Types

CMS implementations should include ZLIB [RFC 1950] [RFC 1951], which is free of
any intellectual property restrictions and has a freely-available, portable and
efficient reference implementation.  The following object identifier identifies
ZLIB:

  id-alg-zlib OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840)
    rsadsi(113549) pkcs(1) pkcs-9(9) smime(16) alg(3) 8 }

The parameters for this algorithm are NULL.

3. Security Considerations

This RFC is not concerned with security, except for the fact that compressing
data before encryption can enhance the security provided by other processing
steps by reducing the quantity of known plaintext available to an attacker.

Author Address

Peter Gutmann
University of Auckland
Private Bag 92019
Auckland, New Zealand
[email-masked] 

References

  ASN1  Recommendation X.680: Specification of Abstract Syntax Notation
        One (ASN.1), 1994.

  CMS   Cryptographic Message Syntax, draft-ietf-smime-cms-11.txt, Russ
        Housley, April 1999.

  RFC2119 Key Words for Use in RFC's to Indicate Requirement Levels,
        S.Bradner, March 1997.

  RFC1950 ZLIB Compressed Data Format Specification version 3.3, P.Deutsch and
        J-L Gailly, May 1996.

  RFC1951 DEFLATE Compressed Data Format Specification version 1.3, P.Deutsch,
        May 1996.

Appendix A: ASN.1 Module

PasswordRecipientInfo
  { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-9(9) smime(16)
    modules(0) compression(n+1) }

DEFINITIONS IMPLICIT TAGS ::=
BEGIN

CompressedData ::= SEQUENCE {
  version CMSVersion,       -- Always set to 0
  compressionAlgorithm CompressionAlgorithmIdentifier,
  encapContentInfo EncapsulatedContentInfo
  }

CompressionAlgorithmIdentifer ALGORITHM-IDENTIFIER ::= {
  { SYNTAX NULL IDENTIFIED BY id-alg-ZLIB },
  ...
  }

END

Full Copyright Statement

[etc]

---

From: [email-masked] (Peter Gutmann)
Date: Thu, 29 Jul 1999 10:41:33 (NZST)

>more generality, but I am a little concerned that CMS may not be as widely 
>adopted as some might hope, whereas implementing it within a crypto algorithm
>would allow SSL, TLS, PSEC, etc., etc., to implement it within their suite of
>supported algorithms.

I think this one's already been addressed in a previous message.

>Also, don't some/most compression algorithms make use of previously 
>calculated symbol tables?  Couldn't those tables be transferred and referred 
>to independently, rather than being sent with the text, assuming they are 
>reasonably constant?
>

zlib uses semi-adaptive Huffman coding for statistical compression and LZ77
for dictionary compression, the codeword tables[0] are stored in a compressed
format[1] at the start of the data.  They're built by scanning the data and
building a fixed tree for each data block with more or less fixed statistics,
so there are no pre-calculated tables.  zlib does contain provisions for pre-
computed dictionaries (you can seed the model used by the compressor with data
you know will appear in the data to be compressed), but it's complex to manage
and doesn't have much effect unless you're sending very small messages.  I 
don't know of anything which uses it, it isn't worth the effort and 
complexity.

Peter.

[0] Strictly speaking the Huffman tree.
[1] Actually the tables aren't stored in any kind of form, what's stored is 
    the information required to reconstruct a canonical Huffman tree by the
    decoder.

---

From: Graham Klyne <[email-masked]>
Date: Thu, 29 Jul 1999 10:49:53 +0100

At 09:40 29/07/99 +0100, Darren Harter wrote:

>I think my bottom line questions here are: how important is processing
speed compared to network bandwidth? and how much time does this aspect of
the processing take compared with all those cert/crl processes going on in
S/MIME and/or CMS?

FWIW, for the foreseeable future I think network bandwidth will usually be
a greater bottleneck than processing speed.

#g

------------
Graham Klyne
([email-masked])

---

From: "Linn, John" <[email-masked]>
Date: Thu, 29 Jul 1999 09:04:56 -0400

Network bandwidth is one relevant consideration, but storage consumption may
be even more strongly motivating for messaging-oriented protocols like CMS.
It's quite possible that some CMS-encapsulated objects (including, but not
limited to, S/MIME messages) will be stored for long-term reference by
recipients.  It could be convenient for them to be sent and received in a
compressed form, to avoid the need to reprocess them for efficient storage.

--jl

> -----Original Message-----
> From: Darren Harter [mailto:[email-masked]]
> Sent: Thursday, July 29, 1999 4:41 AM
> To: [email-masked]
> Subject: RE: Compressed data type for S/MIME
> 
> 
> All,
> 
> I've been watching this thread with interest and I'd like to 
> raise a few observations/questions/issues.  I'd like to make 
> the point first though that what follows is not intended to 
> contradict or counter any of the messages that proceed this 
> one - I'd just like to widen the debate a little and firm up 
> my understanding of the relative merits of performing 
> compression or not.
> 
> 1. Are we really concerned with saving network bandwidth 
> these days?  If we are then clearly compression is essential. 
>  If we're not, why are we discussing it at all?
> 
> 2. If we need compression, how does the algorithm complexity 
> of zlib compression algorithm compare with 3DES encryption?  
> What's its average compression rate?
> 
> e.g. How does the time to process the data compare in the following:
> 
> 	a. Encrypt 10Mb of plaintext with 3DES
> 	b. Compress 10Mb to (say) 5Mb using zlib and then 
> encrypt using 3DES.
> 
> 3. If b. takes longer than a. and we're not that concerned 
> with network bandwidth why bother compressing?  
> 
> I think my bottom line questions here are: how important is 
> processing speed compared to network bandwidth? and how much 
> time does this aspect of the processing take compared with 
> all those cert/crl processes going on in S/MIME and/or CMS?
> 
> Regards,
> 
> Darren
> 
> --------------------------------------------------------------
> ----------
> Darren Harter B.Sc (Hons) CEng MBCS
> Application Development Group, UK
> Entegrity Solutions Corp.
> Tel: +44 1452 371383
> Fax: +44 1452 371384
> Cell: +44 7801 812850
> Email: mailto:[email-masked]
> http://www.entegrity.com
> http://www.entegrity.co.uk
>

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 29 Jul 1999 09:29:24 -0400

>a greater bottleneck than processing speed.

Bandwidth or latency?

---

From: "Pawling, John" <[email-masked]>
Date: Thu, 29 Jul 1999 10:21:47 -0400

All,

Compression is not a security service, so it should not be included in the
S/MIME specs.  Developing an Internet standard for compressing data is an
issue that is related to Internet data communications, in general, not just
S/MIME.  There may be folks who are not participating in the S/MIME WG that
would greatly benefit from an Internet compression standard.  In summary, I
believe that this discussion should take place in a more general data
communications group, not the S/MIME WG.

============================================
John Pawling, Director - Systems Engineering
J.G. Van Dyke & Associates, Inc.
[email-masked]
============================================

---

From: "David P. Kemp" <[email-masked]>
Date: Thu, 29 Jul 1999 11:08:07 -0400 (EDT)

> From: "Pawling, John" <[email-masked]>
> 
> All,
> 

Unfortunately, as Peter pointed out, the discussion hasn't happened,
and isn't likely to happen, at the MIME level.  And if a compressed
MIME-type did exist, it would not cover non-S/MIME applications of
CMS.  Perhaps CMS itself should be owned by a "more general data
communications group" such as WTS or CAT, but it isn't.  As long as
CMS is S/MIME-related, compression within CMS is S/MIME-related.

The philosophy adopted by other Security Area WGs is that if security
breaks something, security should ameliorate the damage to the extent
possible.  Thus PPP includes compression because PPP encryption breaks
modem compression.  IPsec includes it because IPsec breaks PPP
compression.  TLS includes it because TLS breaks IPsec compression.  As
long as CMS will be used with compressible data and with
compression-enabled lower layers (a network stack, or disk-doubler),
CMS should address the problem it causes.

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 30 Jul 1999 07:10:03 (NZST)

Darren Harter <[email-masked]> writes:

>1. Are we really concerned with saving network bandwidth these days?  If we 
>are then clearly compression is essential.  If we're not, why are we 
>discussing it at all?

In the examples I cited (batch EDI), compression is absolutely essential.  I 
know of at least one nontrivial project where compression was ranked far above
any kind of security in terms of importance - you simply couldn't move the 
data over ISDN, X.25, or dialup links unless it was compressed.  Given that
even for more conventional business email use you're going to have bloatware
documents (150 copies of a 1.5MB Word memo reminding people not to forget the 
company picnic, 10MB spreadsheets with last month's sales figures, etc) 
typically going over modem (RAS) or ISDN links, and that the typical PC has
CPU cycles to burn, it doesn't make any sense *not* to include compression.

>2. If we need compression, how does the algorithm complexity of zlib 
>compression algorithm compare with 3DES encryption?  What's its average 
>compression rate?

Is it sufficient to say "b***y quick", or do I have to actually provide some 
figures:-)?  I really have no idea of the compression rate of something like 
zlib, it's hard to test by simply running zip because it's I/O bound, and a 
quick search hasn't located any details, but I can imagine that (especially 
in a speed-optimised mode like -1) it'd run circles around any crypto except 
RC4.  The only comparison figures I have are with LZO, which runs at about 
1/3 the speed of a memcpy().  zlib isn't nearly as fast, but it's much faster
than any crypto operation.  Also, don't forget that you're typically 
tripling[0] the speed not just of encryption and hashing but also the multiple
layers of base64 gunk which S/MIME wraps around every processing step.  If
nothing else, it'll stop the PGP crowd from laughing at S/MIME's 2:1 expansion
of everything you send with it while PGP gets 2:1 compression.

>I think my bottom line questions here are: how important is processing speed 
>compared to network bandwidth? and how much time does this aspect of the 
>processing take compared with all those cert/crl processes going on in 
>S/MIME and/or CMS?

You're winning on security, processing speed, and network bandwidth, at the 
cost of adding a new OID and about an hours programming time.

Peter.

[0] Based on 3:1 - 4:1 compression figures for a random collection of Word 
    documents, for EDI it's even higher.

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 30 Jul 1999 13:26:13 (NZST)

I've asked Gunther Schadow, one of the authors of draft-ietf-ediint-hl7.txt 
(covering secure EDI transactions for HL7, which is used for healthcare), for 
his thoughts on compressing messages and on adding compression to S/MIME.  
Note that HL7 use has particular requirements (small messages of a few K to a
few hundred K, nothing like the multimegabyte FEDI monsters, a generally text-
only environment (no easy ability to handle binary data), batch-style 
processing, etc etc) which are reflected in the EDIINT-HL7 draft and the 
comments below.  One thing I'll have to add to the compression draft is a 
comment on the relative merits of compress-before-sign vs sign-before-
compress.

Some of the EDIINT drafts have the following (or some variant thereof) to say 
about S/MIME compression:

>The digital envelope does not perform data compression prior to encryption.  
>There is yet no standard way to compress MIME-EDI entities before encryption, 
>however, the EDIINT working group suggests using a header field named 
>Content-Encoding as per HTTP [RFC 2068].

The recommendation for compression is either (1) use PGP, (2) use the above, 
piping the data through compress or gzip (it works in this case because it's 
batch processing typically done on Unix boxes).  I'm only aware of one 
situation where this type of processing is being used, although they're not 
following the above recommendation but just assuming the other side knows 
it's compressed (you don't want to know what sort of a hack this involves 
under Windows now that sites are moving towards using NT for this - it was 
an obvious and easy solution under Unix, but almost impossible to move to
Windows).  The more general solution is to use zlib and assume that the other
side knows that id-data is sometimes compressed data (it works in this case
because EDI messages are always fixed-format text while compressed data is
binary).  Having been exposed to these kludges is one of the reasons why I
really want to see a standard representation for compressed content in 
S/MIME.

I saw the first EDIINT draft some time in 1996 (although I don't know what it 
had to say about compression back then), so they may have been waiting for 
over three years, beating the 14-month record by a considerable margin.

Peter.

-- Snip --

Hi,

Interestingly PGP has had automatic compression of payload from the
beginning. The reason is not just size of the message itself, but
other aspects may make compression before encryption favorable:

1. removing redundancy improves robustness against certain (or all?)
   decipherment attacks.

2. the payload to encrypt is smaller which is why compression before
   encryption can be more efficient than after encryption. I tested it
   on a 300 kB text file that compresses to 16% of the size and the
   pipe gzip|bdes ran still 20% faster than bdes only.

3. since encryption increases entropy of the message, compression
   is less efficient after encryption. Actually it's not possible
   at all: gzipping a DES-CBC cryptogram will actually increase
   the size!

This is all said for encryption. For signatures it may be better not
to compress so as to have an immediately readable cleartext to store
with the signature. But hell, isn't S/MIME hiding the text behind a
blob of DER anyway? (I hate S/MIME for this)

Notably hashing (MD5) is far less expensive then DES-CBC so that
compressing before signature would not gain any significant
throughput, and the cost of multiple decompression for every access to
the authenticated archive would be too high.

So, consider an ideal world where we were using MOSS (the real
SECURE-MIME, nice MIME-based plain text), the most useful steps would
be:

1. sign
2. compress
3. encrypt

Actually the little test I did has such a persuasive outcome that I'll
just show the figures here:

$ ls -l A*

-rw-r--r--  1 schadow  bin  335803 Jul 29 15:34 A       plain text
-rw-r--r--  1 schadow  bin  335808 Jul 29 15:39 Ac      DES-CBC cryptogram
-rw-r--r--  1 schadow  bin  335884 Jul 29 15:36 Acz     compressed crypto
-rw-r--r--  1 schadow  bin   55786 Jul 29 15:35 Az      compressed plain
-rw-r--r--  1 schadow  bin   55792 Jul 29 15:39 Azc     crypted compress

$ time gzip -c A | bdes -k onekeytwokeyslongkeyshortkey > Azc

real    0m0.335s
user    0m0.289s
sys     0m1.030s

$ time bdes -k onekeytwokeyslongkeyshortkey <A > Ac

real    0m0.433s
user    0m0.334s
sys     0m0.032s

$ time bdes -k onekeytwokeyslongkeyshortkey <A |gzip -f >Acz

real    0m0.666s
user    0m1.606s
sys     0m0.019s

$ time gzip -f <A >Az

real    0m0.257s
user    0m0.222s
sys     0m0.016s

I am not sure how much this matters for EDI since as far as I know
compressing EDI streams is quite uncommon. But why would you not want
to do it if the additional compression step can speed up the entire
encryption process?  I's a win/win situation: where else can you save
both channel bandwidth and CPU load?

regards
-Gunther

Gunther Schadow ----------------------------------- http://aurora.rg.iupui.edu
Regenstrief Institute for Health Care
1001 W 10th Street RG5, Indianapolis IN 46202, Phone: (317) 630 7960
[email-masked] ---------------------- #include <usual/disclaimer>

---

From: Darren Harter <[email-masked]>
Date: Fri, 30 Jul 1999 09:26:15 +0100

Paul,

Thanks for this.
It's exactly the kind of thing I was looking for.
Looks like a WIN-WIN situation.

Regards,

Darren

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

-----Original Message-----
From:	Paul Hoffman / IMC [SMTP:[email-masked]]
Sent:	Thursday, July 29, 1999 5:42 PM
To:	Darren Harter; [email-masked]
Subject:	RE: Compressed data type for S/MIME

At 09:40 AM 7/29/1999 +0100, Darren Harter wrote:
>1. Are we really concerned with saving network bandwidth these days?  If 
>we are then clearly compression is essential.  If we're not, why are we 
>discussing it at all?

There is another aspect that is more relevant to non-S/MIME uses of CMS: 
speed of encrypting. Studies done by the IPsec folks found that the 
combination of compressing and encrypting with TripleDES is faster than 
encrypting uncompressed data. The fact that the resulting payload is 
smaller is obviously an additional advantage.

--Paul Hoffman, Director
--Internet Mail Consortium

---

From: "David P. Kemp" <[email-masked]>
Date: Fri, 30 Jul 1999 08:57:20 -0400 (EDT)

> From: [email-masked] (Peter Gutmann)
> 
>  [... quoting Gunther Schadow]
>
>  [...]

Nope, S/MIME signs the text and then blobs it.

CMS Section 5.4:

  "Specifically, the initial input [to the message digest calculation]
   is the ... eContent OCTET STRING to which the signing process is
   applied.  Only the octets comprising the value of the eContent
   OCTET STRING are input to the message digest algorithm, not the
   tag or length octets."