Binary packet protocol rethink (was: Re: ChaCha20-Poly1305 for SSH)

[Simon Tatham <anakin%pobox.com@localhost>]

> Simon Josefsson <simon%josefsson.org@localhost> writes:
>> Does anyone see a strong need for encrypting the length field?

Niels Möller <nisse%lysator.liu.se@localhost> wrote:
> Yes. I think it's valuable defence-in-depth to hide packet lengths and
> message boundaries. Note that in the ssh protocol, the boundaries of the
> TCP segments need not match the SSH message boundaries at all. It's not
> too difficult to arrange that most or all segment boundaries are in the
> middle of an ssh message, using SSH_MSG_IGNORE packets when needed.

On that subject, perhaps this is a good moment to re-raise a thing I've
been wondering about for ages. Not for immediate consideration as part
of any of the current set of RFCs-in-progress, but as a thought for the
further future.

Is there any possible way - and would people be interested in pursuing
it if there were - to invent a replacement binary packet protocol for
SSH which decouples the unit of encryption and the unit of protocol
semantics into completely separate layers?

Handling of packet length fields in SSH has always been tricky, and
we've got it wrong several times. The cleartext _unpadded_ lengths in
SSH-1 had very obvious flaws; the switch to encrypting the length field
as part of the first cipher block in SSH-2 caused an accidental
decryption oracle. And even if you encrypt the length field in a way
that avoids that mistake, you still don't reliably hide your _padded_
packet lengths anyway, in the face of an active attacker who can proxy
the TCP stream, dribble it out a byte at a time, and wait to see which
byte triggers a response. I suspect some defensive uses of
SSH_MSG_IGNORE may still have this issue.

I think all of these problems ultimately arise from the fact that the
SSH protocol messages and the encrypted packets are the same thing, so
that the lengths of the former (being at least somewhat sensitive data)
are at constant risk of being exposed by design flaws in the latter. So
I've always thought a good way to solve this _in principle_ would be to
replace our current all-in-one message/packet structure with two
independent layers.

The outer layer would interpret the incoming TCP stream as a series of
what I'll refer to as 'encrypted chunks', each consisting of a length,
some encrypted data, and a MAC. The validated and decrypted contents of
those chunks would be concatenated into a single byte stream, with no
remaining trace of the chunk boundaries, and passed on to the inner
layer which would break that byte stream up into 'SSH protocol
messages'. The inner layer would need no cryptography at all; it could
be something very close to SFTP's bare (length,type,data) tuples, except
that you'd probably want to make it easy to insert N bytes of padding in
between messages for a wide variety of N (perhaps even all N).

Then you really could have the length fields of the encrypted chunks be
in cleartext, because they wouldn't be telling an attacker anything they
couldn't have inferred from the TCP segment boundaries anyway. And at
the same time, that would tell you nothing about the SSH message
boundaries inside those chunks; you could have one chunk containing many
messages, or one message split across many chunks, or chunks ending in
mid-message, however the sending implementation saw fit.

For concealing the length of a critical message (see past attempts at
traffic-analysis defences relating to SSH_MSG_PASSWORD in particular),
this would be much better than just squashing two successive messages
into the same TCP segment, because now the dribbling attack completely
stops working - a receiver isn't going to be replying anyway until the
whole encrypted chunk is received, and the proxying attacker already
knows when _that_ will happen. There would be no possible way to find
out how much of a large chunk corresponded to a particular message
without actually breaking the cryptography. Furthermore, by inserting
padding at random between messages, it would be trivial to make the
starting points of messages within a chunk unpredictable, so that you
could make it impossible for an attacker to reliably identify (say) a
cipher block containing part of a password.

Is this an idea that appeals to anyone else? I've never been entirely
sure whether there's any remaining space to introduce it in the current
protocol while keeping intercompatibility with existing implementations;
but it's only worth trying to solve that problem if anyone else would be
interested in pursuing the idea anyway.

Cheers,
Simon
-- 
for k in [pow(x,37,0x1a1298d262b49c895d47f) for x in [0x50deb914257022de7fff,
0x213558f2215127d5a2d1, 0x90c99e86d08b91218630, 0x109f3d0cfbf640c0beee7,
0xc83e01379a5fbec5fdd1, 0x19d3d70a8d567e388600e, 0x534e2f6e8a4a33155123]]:
 print "".join([chr(32+3*((k>>x)&1))for x in range(79)]) # <anakin%pobox.com@localhost>

-- 
for k in [pow(x,37,0x1a1298d262b49c895d47f) for x in [0x50deb914257022de7fff,
0x213558f2215127d5a2d1, 0x90c99e86d08b91218630, 0x109f3d0cfbf640c0beee7,
0xc83e01379a5fbec5fdd1, 0x19d3d70a8d567e388600e, 0x534e2f6e8a4a33155123]]:
 print "".join([chr(32+3*((k>>x)&1))for x in range(79)]) # <anakin%pobox.com@localhost>