Subject: meaning of partial flush

From: Wei Dai <[email-masked]>
Date: Thu, 21 Sep 2000 21:36:14 -0700

> The "zlib" compression is described in [RFC-1950] and in [RFC-1951]. The
> compression context is initialized after each key exchange, and is
> passed from one packet to the next with only a partial flush being
> performed at the end of each packet. A partial flush means that all data
> will be output, but the next packet will continue using compression
> tables from the end of the previous packet.

I was unable to find the exact definition of "partial flush"
documented in either RFC 1950 or RFC 1951. After reading the ZLIB source
code for half a day, I finally figured out that it means ending the
current deflate block and adding one or two empty deflate blocks in order
to finish up the current byte in the compression stream.

While looking at the ZLIB source code, I also found this comment:

#define Z_PARTIAL_FLUSH 1 /* will be removed, use Z_SYNC_FLUSH instead */
#define Z_SYNC_FLUSH    2

The difference between sync flush and partial flush is that sync flush
would add an empty "store" block instead of the one or two empty deflate
blocks. The store block causes the next deflate block to start at a byte
boundary, but it uses up 4 more bytes than the empty deflate blocks.

I think the meaning of "partial flush" should be clarified in the SSH
standard, and also maybe we should consider using sync flush instead,
since partial flush seems to be deprecated by the ZLIB authors.

Another compression-related issue whether when a new compression stream
starts (via SSH_MSG_NEWKEYS), the previous compression stream needs to
end normally (which for ZLIB involves appending an ADLER32 checksum), or
whether it can just terminate in the middle of the stream.

---

From: [email-masked] (Niels M�ller)
Date: 22 Sep 2000 12:49:21 +0200

> to finish up the current byte in the compression stream.

I agree that it would be a good thing to make the spec clearer on this
point.

> boundary, but it uses up 4 more bytes than the empty deflate blocks.

LSH happens to use Z_SYNC_FLUSH, and I haven't heard about any
interoperability problems here, so I guess that is what everybody is
doing.

The relevant code is http://www.lysator.liu.se/~nisse/lsh/src/zlib.c.

> whether it can just terminate in the middle of the stream.

My immediate reaction is to *not* append any adler32 checksum, for two
reasons:

(i) The MAC should already provide adequate integrity protection.

(ii) I believe it would make the implementation more complicated, as
     you has to do something special for the last packet using the old
     compression context. It's probably not to painful to check for
     SSH_MSG_NEWKEYS (and SSH_MSG_DISCONNECT!) in the part of the code
     dealing with compression, but it is cleaner not to do that.

/Niels

---

From: Wei Dai <[email-masked]>
Date: Mon, 25 Sep 2000 09:33:25 -0700

> interoperability problems here, so I guess that is what everybody is

It turns out things are a bit more complicated than that. OpenSSH
seems to use Z_PARTIAL_FLUSH instead of Z_SYNC_FLUSH. I think this is
actually a good idea because it causes less overhead than Z_SYNC_FLUSH.
However even Z_PARTIAL_FLUSH sends more "filler" bits than is necessary
because of the way the ZLIB decompression code is written. See this
comment in trees.c:

/* ===========================================================================
 * Send one empty static block to give enough lookahead for inflate.
 * This takes 10 bits, of which 7 may remain in the bit buffer.
 * The current inflate code requires 9 bits of lookahead. If the
 * last two codes for the previous block (real code plus EOB) were coded
 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
 * the last real code. In this case we send two empty static blocks instead
 * of one. (There are no problems if the previous block is stored or fixed.)
 * To simplify the code, we assume the worst case of last real code encoded
 * on one bit only.
 */

Someone who did not know about this implementation detail in ZLIB
might think that sending just one empty static block would be sufficient
in all cases. It really needs to be documented in the SSH specification
that "partial flush" means either adding one empty store block, or two
empty static blocks, even though adding just one empty static block would
statisfy the purpose of flushing on the basis of RFC 1951.

>      dealing with compression, but it is cleaner not to do that.

I agree with you on this.

---

From: [email-masked] (Niels Möller)
Date: 25 Sep 2000 18:50:56 +0200

Wei Dai <[email-masked]> writes:

> It turns out things are a bit more complicated than that.

[ ... ]

> because of the way the ZLIB decompression code is written. See this

Hmm. It's kind of ugly to depend on "the current inflate code".

We're compressing sequences of blocks (octet strings of various
sizes). For interoperability, the important conditions are that

1. The block sequence is one zlib stream, i.e. compression state is
   kept between blocks.

2. On block boundaries, enough syncing frames are added so that the
   receiving end can inflate the blocks one at a time. If more syncing
   than absolutely necessary is added, that should not cause any
   harm.

But if I understand you correctly, (2) is not precise enough, one
needs to add enough syncing frames to make a particular
implementation happy. 

/Niels

---

From: Wei Dai <[email-masked]>
Date: Mon, 25 Sep 2000 10:05:35 -0700

> needs to add enough syncing frames to make a particular

Yes, exactly. It's unfortunate that up to now everyone has been using the
same inflate implementation so nobody noticed this issue. Is it too late
to ask the ZLIB maintainers to change their code, and just put (1) and
(2) into the SSH spec?