Subject: ChaCha20-Poly1305 for SSH

From: Simon Josefsson <[email-masked]>
Date: Thu, 26 Nov 2015 11:08:59 +0100

Hi.  I've taken Damien writeup on Damien/Markus's
[email-masked] and put that into an IETF draft:

https://tools.ietf.org/html/draft-josefsson-ssh-chacha20-poly1305-openssh-00

There have been some offlist conversation about how to move forward with
this in the IETF.  The challenge is that the construct differs from the
ChaCha20-Poly1305 construct used in RFC 7539.

To have something to start IETF discussions, I thought it would be
useful to have the OpenSSH-specific construct described in a draft.

We could turn this into an IETF blessed approach by stripping
"@openssh.com" and register that with IANA, similar to what is done for
curve25519.

We could also describe a new SSH encryption algorithm that is based on
the RFC 7539 construct.  Still using ChaCha20-Poly1305, of course, but
it would work differently.

As far as I understand, the critical technical difference between these
approaches is whether encrypting the length field is useful or not.  I'm
told that encryption the field is of limited use because traffic
analysis would see the packet lengths anyway.

Regardless of whether it is useful to do this, I believe it would be a
bad idea to push something in IETF that SSH implementers aren't
interested in implementing.  So if we do something other than stripping
@openssh.com I believe we will need to build consensus for doing that
among implementers first.

For consistency and simplicity of algorithm description, I do want to
see a RFC 7539 based approach explored though, and we may end up writing
a different draft on that.

If you are an SSH implementer that supports
[email-masked], are you interested in implementing
support for a more streamlined variant that would lack encryption of the
length field?

Does anyone see a strong need for encrypting the length field?

/Simon

---

From: [email-masked] (Niels Möller)
Date: Thu, 26 Nov 2015 16:44:17 +0100

Simon Josefsson <[email-masked]> writes:

> approaches is whether encrypting the length field is useful or not.

It also uses a different formatting of the poly1305 input, which aligns
the poly1305 blocks with the chacha blocks. Which should be beneficial
in particular for hardware implementations.

> I'm told that encryption the field is of limited use because traffic

I don't think that analysis is correct. (See below).

Nevertheless, I think it makes sense to use the rfc 7539 construction.

So my suggestion is to go with rfc 7539, and in addition, encrypt the
length field by something lietk

   encrypt_length(key, nonce, length)
         counter = 0
         block = chacha20_block(key,counter,nonce)
         return block[32..35] ^ length
         end

using the same key and nonce as input as with poly1305_key_gen in RFC
7539. (It's then possible, but not at all necessary, to generate the
poly1305 key and encrypt the length key using a single call to
chacha20_block. In contrast to [email-masked], which,
iirc, uses a separate chacha key just for encrypting the lengths).

Care is needed to specify the negotiation of aead algorithms, and
the details of what goes into the associated data.

> Does anyone see a strong need for encrypting the length field?

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.

I won't argue that it is easy to make traffic analysis impossible, but I
believe it's still valuable to make traffic analysis harder.

Best regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: [email-masked] (Niels Möller)
Date: Thu, 26 Nov 2015 21:42:17 +0100

Simon Tatham <[email-masked]> writes:

> 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?

I think it's interesting to explore, but I'm not sure it's possible to
get it much better than the ssh protocol with careful use of IGNORE
packets.

The problem is the interactivity. Let's consider the simplest example
(but I'm not saying this example captures all essentials of the
problem). Say I let my shell connection idle for some time, then I type
a couple of characters, and I want a timely response before I type the
next command. Then my typing has to correspond to a TCP segment that can
be decrypted and authenticated and passed on to the remote shell. With
the current ssh protocol, that TCP segment will carry a single
CHANNEL_DATA packet, possibly in combination with fragments of IGNORE
messages and possibly other piggybacking messages, e.g., WINDOW_ADJUST.

To hide the user's typing from traffic analysis is a tradeoff, with
varying amounts of cover traffic (preferably including responses;
there's maybe some use for an IGNORE_CONTENTS_BUT_PLEASE_REPLY message
type). It's highly desirable to hide details of the user's typing; some
reasonable counter measures are to collect keystrokes for a few 100 ms
before generating any packet, and use padding to hide the number of
keystrokes included in each packet.

> 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.

This is a good point which is easy to overlook. The lesson here is that
it is better to add the padding data at the start of the TCP segment
rather than at the end; the boundary between initial padding and the
start of the message is *not* revealed by the dribbel attack. And we
should also keep in mind that there are relevant attackers which are
only passive eavesdroppers, so a defense which is effective only against
passive adverseries but fails with an active adversary still has value.

For design of a cryptographic transport protocol, interactivity implies
that there has to be some kind of flush/sync mechanism. The input can't
be just a cleartext byte stream, it has to be a byte stream with
syncronization points. A syncronization point means that data up to that
point must be delivered without waiting for further input. So the
cryptographic transport protocol must encrypt it, send it out on the
wire in a timely manner, and attach an authentication tag and any other
signalling needed for the receiver to decrypt, authenticate, and process
the data. Which breaks a pure separation between layers.

And those synchronization points are going to be revealed by the dribble
attack.

One possible design would be to make the block of the crypto layer a
fixed size, say around 200 bytes, and then to get a synchronization
point, just insert an ignore message of at least 200 bytes (possibly
with randomized larger size). Probably not a good idea for a general
purpose crypto protocol, though.

> 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.

It's long time since I looked into the details of TLS, but doesn't it
have more of this kind of separation? How does it handle the
syncronization issue?

> Is this an idea that appeals to anyone else?

I definitely see the appeal, but I'm a bit skeptic that it can work out.

Regards,
/Niels

---

From: Simon Tatham <[email-masked]>
Date: Thu, 26 Nov 2015 16:41:26 +0000

> 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.

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)]) # <[email-masked]>

-- 
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)]) # <[email-masked]>

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 27 Nov 2015 09:54:22 +0100

[email-masked] (Niels Möller) writes:

> type).

In libssh2 there is a keepalive message that can be sent regulary.  It
is a SSH_MSG_GLOBAL_REQUEST with the want-reply bit set.  It should be
replied to (typically with a SSH_MSG_REQUEST_FAILURE message).

That said, I'm also skeptic whether this is an effort that will pan out.
I don't see the problem statement sufficiently strong to motivate work.
In general that may be because the idea is too weak, but can also be
that the problem statement is not fleshed out well enough.  Right now it
is hard to tell which case applies, but the end result is the same
(=nothing will happen).

/Simon

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 27 Nov 2015 10:48:02 +0000

Simon Tatham <[email-masked]> writes:

>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?

I've asked for this in the past too.  SSL/TLS have used unencrypted lengths
for twenty years without there being any (known) attack or weakness based on
this.  OTOH SSH has used encrypted lengths for nearly the same period, and
there have been several attacks/weaknesses based on that.  Security-wise, it
has the opposite effect of the one intended, it makes the protocol weaker, not
stronger.

My real issue with it though is that, as you've pointed out, it makes it
impossible to create an efficient streaming implementation.  With TLS you read
the length at the start, stream the rest into the target memory location, and
decrypt in place.  With SSH you have to read a single block, decrypt it, make
sure you're not providing an oracle for the attacker, copy what's left around,
read more encrypted data onto the end, decrypt the remainder, ugh.

I would really like to see a protocol that:

1) Doesn't encrypt the length so you can create an efficient streaming
   implementation.

2) Uses encrypt-then-MAC for security rather than MAC-then-encrypt.

This would solve several problems with the current format all at once.

Peter.

---

From: Damien Miller <[email-masked]>
Date: Sun, 29 Nov 2015 22:32:21 +1100 (AEDT)

> has the opposite effect of the one intended, it makes the protocol weaker, not

There have been quite a few fingerprinting attack against websites
using object sizes, e.g. Vincent Berg's work.

> 2) Uses encrypt-then-MAC for security rather than MAC-then-encrypt.

OpenSSH has had this for some time in our *-etm MAC modes.

https://anongit.mindrot.org/openssh.git/tree/PROTOCOL?id=b1d6b397#n54

-d

---

From: Damien Miller <[email-masked]>
Date: Sun, 29 Nov 2015 22:42:10 +1100 (AEDT)

> iirc, uses a separate chacha key just for encrypting the lengths).

IMO if you're going to the trouble of preserving packet length
privacy then you should do it properly and use a separate cipher
instance to do it. In the case of chacha20, it's ridiculously cheap
to do so; the cipher has negligible state.

-d

---

From: Damien Miller <[email-masked]>
Date: Sun, 29 Nov 2015 22:48:48 +1100 (AEDT)

While we're dropping wishlist items for SSH v.3, here's one of mine:

Key exchange negotiates an AEAD rather than a cipher and a MAC
separately, and does so from a greatly trimmed set of options. E.g.
AES-GCM, chacha20+poly1305 and an AES-CTR+HMAC mode.

IMO the AEAD primitive is the right metaphor for the security properties
of the SSH transport protocol. Removing the large cartesian product of
ciphers x MACs will make testing faster and binaries smaller too.

-d

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sun, 29 Nov 2015 08:57:14 -0800

> AES-GCM, chacha20+poly1305 and an AES-CTR+HMAC mode.

+1

This would be useful.

	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Sun, 29 Nov 2015 19:05:33 +0100

Damien Miller <[email-masked]> writes:

> instance to do it.

Does it matter if we xor it with some unused bytes in the same chacha
key stream used for the rest of the data, or use a separate instance
with a different key (but generated from the same key exchange secret)?

> In the case of chacha20, it's ridiculously cheap

It just seems nice to me to not have to produce yet another session key
just for this, when we have 32 perfectly good key stream bytes left
over. I agree the per-message overhead with an extra chacha instance is
very low, and it's no big deal, it's more about eliminating a little
book-keeping.

Or are you suggesting the even more proper thing to do, which would be
to encrypt the length field *and* add separate authentication tag for
it?

Off the top of my head, I think it would make sense with some
building-block which takes as input a per-session key, the 32-bit
length, and per-message nonce, and produces, e.g., 64 random looking
output bits, such that (1) the length can be recovered only by the
receiver, with whome we share the key, and (2) any malicious
modification of the 64 bits on the wire can be detected with probability
close to 1. Or just use a separate chacha-poly1305 on the length, with
it's larger tag.

Regards,
/Niels

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 30 Nov 2015 01:57:28 +0000

Damien Miller <[email-masked]> writes:

>There have been quite a few fingerprinting attack against websites using 
>object sizes, e.g. Vincent Berg's work.

Sure, I'm aware of just under three dozen, but encrypted vs.unencrypted
lengths don't play a major role, they're used because they're there, not
because they're critical to the success of the process.  You've got TCP
packet sizes (which generally make length-encryption irrelevant), packet
timing, message flows, everything that can be used will be used.  In
particular, "Timing Analysis of Keystrokes and Timing Attacks on SSH"
worked against SSH even though the lengths were encrypted.

More or less the same debate is currently occurring on the TLS list,
where I commented that:

  If you want to thwart traffic analysis, you need to do something
  like what's done by designs like Aqua ("Towards Efficient Traffic-
  analysis Resistant Anonymity Networks"), or ideas from any of the 
  other anti-traffic-analysis work that's emerged in the past decade 
  or two.  
  
  You get traffic analysis resistance by, for example, breaking data into 
  fixed-length packets, using cover traffic, and messing with packet 
  timings, not by encrypting TLS headers.

Peter.

---

From: [email-masked] (Niels Möller)
Date: Mon, 30 Nov 2015 09:01:49 +0100

>   timings, not by encrypting TLS headers.

One can do all of these with the current ssh wire protocol. It's even
straight-forward to do. But if we switch to clear text lengths (with no
other, deeper, changes to the protocol), it gets a lot more difficult.

So encrypted packet lengths aren't a solution, but they're a
*prerequisite* for the more serious counter measures.

Regards,
/Niels

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 30 Nov 2015 08:55:35 +0000

>other, deeper, changes to the protocol), it gets a lot more difficult.

Why?  The length just tells you how much to decrypt in one block, what you put
inside it is up to you.  At a lower level, the TCP headers already give length
information, and if you can deal with that then you can just as easily deal
with plaintext lengths.

Peter.

---

From: Simon Tatham <[email-masked]>
Date: Mon, 30 Nov 2015 09:11:13 +0000

Peter Gutmann <[email-masked]> wrote:
> Why? The length just tells you how much to decrypt in one block, what
> you put inside it is up to you. At a lower level, the TCP headers
> already give length information, and if you can deal with that then
> you can just as easily deal with plaintext lengths.

Exactly.

And, at the same time, it's precisely the encrypting of the 'how much to
decrypt' length field which gives rise to all the previous protocol
flaws: an attacker either guesses the true length by correlating to the
TCP headers, or probes it by means of the byte-at-a-time dribbling
attack, or actively corrupts the cipher block containing the length and
waits to see when the resulting MAC failure is reported, and all of
those attacks (unless carefully defended against) give rise to some kind
of data you can use to attack the underlying cipher, like a (plaintext,
ciphertext) pair, or a partial XOR of a plaintext block and the previous
block in the CBC stream, or whatever.

So it simplifies matters enormously if you just don't try: accept that
the enemy _will_ be able to know the lengths of your encrypted blocks.
Then you can send them in clear to avoid all of those subtle
implementation goofs in trying to hide them, and instead, dedicate your
effort to arranging that it _doesn't matter_ if the enemy knows those
lengths, by making sure that the encrypted block boundaries do not also
reveal the length or position of any actually important data, such as a
particular SSH_MSG_anything. Hence, my original suggestion of separating
the two conceptual halves of the current monolithic BPP.

But it's looking so far as if there's not enough interest to pursue it.
Ah well.

Cheers,
Simon

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 30 Nov 2015 11:54:23 +0100

> IMO the AEAD primitive is the right metaphor for the security
> properties of the SSH transport protocol. Removing the large
> cartesian product of ciphers x MACs will make testing faster and
> binaries smaller too.

I agree.  I believe there is opportunity to deprecate all pre-AEAD
modes, if there is interest on doing that.  I believe the experience
with TLS is that no non-AEAD mode has the properties that we desire.
Generally, I believe the experience is that you cannot negotiate cipher
and MAC separately, it has to be done together.  Maybe we can draft
something together, and bring it to the curdle IETF WG, it would be in
scope of that process.

Looking at these registries:
http://www.iana.org/assignments/ssh-parameters/ssh-parameters.xhtml#ssh-parameters-17
http://www.iana.org/assignments/ssh-parameters/ssh-parameters.xhtml#ssh-parameters-18

I believe it would be possible to mark all as obsolete/historic, except
for a list of a few known good combinations that we can actually
recommend. As far as I can tell that list would include:

aes128-ctr
aes256-ctr
chacha20-poly1305 (whatever that turns out to be)
umac-* (same here..)
hmac-sha1 (for older ciphers only?)
hmac-sha2-256 (for older ciphers only?)

Any others?

I'm not sure what to make of the RFC 5647 AES-GCM mode.  Nobody seems
to implement that.

/Simon

---

From: [email-masked] (Niels Möller)
Date: Mon, 30 Nov 2015 12:25:19 +0100

Peter Gutmann <[email-masked]> writes:

> inside it is up to you.

With the current protocol, I must encrypt exactly one SSH message, hence
cleartext lengths reveal number of SSH messages, and their lengths. TCP
headers need *not* be so correlated.

> At a lower level, the TCP headers already give length information, and
> if you can deal with that then you can just as easily deal with
> plaintext lengths.

The ssh implementation generates a sequence of cleartext messages to be
transported across the network.

The ssh transport machinery can encrypt these, then split them into
fixed size blocks and send off with pre-determined intervals, and
whatever else you think is a useful counter measure to traffic analysis.
When an input message or message fragment is too short, insert ignore
messages (preferable in *front* of the real data, for the byte-by-byte
dribble attack).

I'm happy to discuss the tradeoffs here, but it seems that you keep
repeating that the attacker gets as much useful info from observing tcp
segment boundaries as from observing ssh message boundaries. I don't
think that is correct description of the current protocol, and it seems
our disagreement on this point kind-of blocks useful discussion.

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Mon, 30 Nov 2015 12:34:26 +0100

Simon Tatham <[email-masked]> writes:

> an attacker either guesses the true length by correlating to the
> waits to see when the resulting MAC failure is reported, 

Would you be happier if the length field were independently
authenticated? I'm not sure how strong an authenticator we need, it
seems a bit silly to use an authentication tag which is much larger than
the message, but maybe it's really needed.

> by making sure that the encrypted block boundaries do not also
> particular SSH_MSG_anything.

Can we do that with the current protocol? If so, guidance is
appreciated. What I object to is removing a feature (encrypted message
lengths) which enables known counter measures to traffic analysis, and
replace it by nothing.

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Mon, 30 Nov 2015 13:10:47 +0100

Simon Josefsson <[email-masked]> writes:

> modes, if there is interest on doing that.

I agree this makes a lot of sense. AEAD is exactly what the protocol
needs, it just wasn't well established at the time.

I'd like to see some discussion on how to do it within the ssh algorithm
negotiation, since it doesn't quite fit in the original design. Maybe we
can just do what openssh does, I'm not sure?

I know that completely dropping support for "first_kex_packet_follows"
has been suggested. Maybe that's appropriate, but I'd strongly prefer if
we could keep that a separate issue, and for now just make sure that the
key exchange details stay sane and unambiguous when we add AEAD.

Regards,
/Niels

---

From: Bryan Ford <[email-masked]>
Date: Mon, 30 Nov 2015 16:40:00 +0100

In followup to my own message…

On 30 Nov 2015, at 14:58, Bryan Ford <[email-masked]> wrote:
> On 30 Nov 2015, at 12:34, Niels Möller <[email-masked]> wrote:
> It’s hard for me to see how separately authenticating the length field would be a benefit; […]

Sorry, on further thought I *do* see now what might be gained in principle by authenticating the length field separately, and how that might be implemented securely.  So the SSH record stream might for example alternate between fixed-size “length records” and variable-size “payload records”, each with its own AEAD MAC.  To ensure no mix-and-match vulnerabilities this distinction must be encoded in the AEAD nonce: e.g., the least-significant bit might always be 0 for the length record and 1 for the corresponding payload record.  The cost is the space overhead of two MACs per “useful” payload record rather than just one, but the benefit is the receiver obtains certainty that an attacker can never trick the receiver into trying to read a different-length (e.g., longer) block than the sender intended.  That would indeed be nice, and I can see it potentially being worth the cost.

Just to brainstorm a bit further, here’s a different variant that might mitigate the space cost somewhat.  In every record, include a length field that indicates the length of the *next* record.  Then when the sender has a batch of records to transmit, it can just send them consecutively with one MAC per record.  But when the sender is about to go idle, i.e., is transmitting the last record in a batch for which the sender doesn’t “already” have a subsequent record immediately ready to go, the sender sets the next-record-length field to some standard minimum size.  The sender can then go idle; the receiver will wait for that minimum-size next record.  When the sender has something to send again, it sends the promised minimum-length record, which might contain no useful data but merely get the pipeline going again, with a next-record-length field appropriate for whatever the sender actually wants to send next.  So this way the protocol actually pays the bandwidth cost of extra MACs only when the stream goes idle, not on every record.

This design direction does seem attractive in some ways.

Bryan

---

From: Bryan Ford <[email-masked]>
Date: Mon, 30 Nov 2015 14:58:22 +0100

I learned about this discussion thread from Peter’s mention of it on the TLS list, where as he mentioned a parallel debate is going on…  (Thanks Peter; hope you don’t mind me stalk…er, following your hint over here. ;) )

> the message, but maybe it's really needed.

It’s hard for me to see how separately authenticating the length field would be a benefit; in fact I would worry about whether it could introduce a weakness, e.g., where an attacker could somehow contrive “mix-and-match” attacks that could get a receiver to use one (correctly-MAC’d) length field with a different (correctly but independently MAC’d) payload to cause Bad Things of whatever kind to happen.  I also don’t see any essential reason or even important advantage of doing so.

However, I do (think) I see the tension that might seem to suggest treating the length independently from the payload: in a protocol like SSH that encrypts both header and payload, you would like to read and decrypt the length first, then separately read and decrypt the payload (perhaps at a different location in memory).  Especially if the protocol moves to using AEAD ciphers, which has been suggested and I agree is probably generally a worthwhile idea, the standard AEAD API wants to assume the length is already known at decryption/integrity-check time, e.g., by being carried in the normally-unencrypted Additional Data (AD) field.

On the TLS list I posted a proposal for one way (of many) to resolve this seeming conflict between a desire to move to AEAD and a desire to continue encrypting headers (which I strongly support, whether in TLS or SSH or any other encrypted protocol).  A copy of my proposal is attached below, FWIW.  In summary, you still only need one MAC, and you integrity-check the header (including length) together with the payload in the “main” AEAD decryption, but you separately encrypt (without authentication) the header using either a stream cipher or an AEAD used as a stream cipher.  The fundamental argument for why the unauthenticated encryption of the header is safe is because it just changes the encoding of the header without affecting how the header is authenticated (separately, while authenticating the body).  Thus, changing the header encoding while leaving the authentication and body-encryption unchanged from standard AEAD practice cannot make security any worse than just transmitting the header (AD part) in cleartext, and can (sometimes) be a security benefit.

> lengths) which enables known counter measures to traffic analysis, and

Strongly agreed on this.  The fact that a particular security measure (like encrypting headers) isn’t by itself an end-all one-stop solution to all the world’s traffic analysis problems doesn’t make it not worthwhile.

Cheers
Bryan

————————————————(snip)————————————————

The idea of encrypting TLS record headers has come up before, the most
important purpose being to hide record lengths and boundaries and make
fingerprinting and traffic analysis harder.  I had convinced myself that
goal this would be "too hard" to accomplish in TLS 1.3, but after
further thought I'm not so sure.  So I would like to request comment on
one approach that strikes me as a practical and requires only a rather
minor change to the current spec.

The quick summary:

* To encrypt a record, we first AEAD-encrypt the record's payload,
protecting the header fields via the additional_data, exactly as
currently specified.  But then we XOR-encrypt the 5-byte TLS header just
before transmission, using a (separate) stream cipher indexed by a nonce
that depends on record sequence number and *_write_iv, in exactly the
same way the AEAD is already nonce-indexed.

* To decrypt a record, we simply do the reverse: first use the stream
cipher with the appropriate nonce to XOR-decrypt the 5-byte TLS header,
then sanity-check it as usual to determine its length, read the rest of
the record, and submit it to AEAD for decryption and full integrity
checking as before.

That's it, in a nutshell.  Two likely concerns immediately arise,
discussed below, but feel free to TL;DR the rest if you don't share
these concerns.

---

Concern #1: What if an active attacker messes with the TLS header,
especially the length field, since stream ciphers don't protect
integrity?  The simple answer is that *exactly* the same thing happens
as now: the AEAD decryption attempt fails, because the
(stream-decrypted) header is AEAD-protected as additional_data.  Nothing
is gained or lost.

SSH, which did something like this, ran into trouble with attackers
being able to twiddle the record length field to make the record length
look big, causing the receiver to try to receive a very large record,
and hence appear to the user to hang, instead of immediately detecting
the modification and terminating the connection.  But there are three
mitigating factors here: (1) TLS is not usually used for interactive
terminal traffic like SSH is; (2) TLS's 2-byte record length field
imposes a pretty reasonable upper-bound on the maximum size an attacker
could maliciously make a record appear to be; and (3) if this risk of
length-twiddling is at all a problem in this proposed encrypted-header
protocol, then it's already a problem for the current TLS 1.3 spec
without encrypted headers, because active attackers can twiddle the bits
of a cleartext length field just as easily (and even be *certain* they
are making the length appear large!).  So I can't see any way this
length-twiddling vulnerability becomes any worse, and maybe it gets a
bit better (because the attacker can no longer be entirely certain
whether he's setting a 1 bit to 0 or a 0 bit to 1).

---

Concern #2: Do we want to have to go to the trouble of adding a stream
cipher to every TLS 1.3-compatible ciphersuite?  Answer: maybe not, but
we don't necessarily need to.  We could instead just specify a generic
method of using the ciphersuite's main AEAD as a stream cipher for
header encryption/decryption purposes.

The conceptually simplest approach I can think of: In the specification
of how AEAD nonces are generated (section 5.2.2 of
draft-ietf-tls-tls13-07), reserve the least-significant bit of the
record sequence number, so that sequence numbers increment by 2 rather
than 1 each record.  Thus, we get two unique nonces per record from the
same set of symmetric keys.  We first use the nonce with a '0'
least-significant bit to perform the regular AEAD-encryption of the
record with the header info as additional_data.

Then for the same record we use the nonce with a '1' least-significant
to AEAD-encrypt a sequence of five zero bytes ("\0\0\0\0\0"), and use
the first five bytes of result as the cipherstream to XOR the 5-byte TLS
header with before transmitting.  The AEAD will of course uselessly
append some kind of authenticator to this ciphertext that we won't end
up using, but that's OK.  The receiver will just use AEAD-encrypt
(again) on the same five-zero-byte message to reproduce the 5
cipherstream bytes with which to decrypt the TLS header.  Thus, senders
perform two AEAD-encrypts per record, and receivers do one AEAD-encrypt
and one AEAD-decrypt per record.

This approach seems pretty conceptually clean and simple, but has the
performance downside that we always need to invoke the AEAD twice per
record rather than once, which might be (a bit) costly especially when
records are small.  So a simple refinement is to amortize this cost
across records: e.g., once every 256 records (every sequence number
ending in 0x00) we AEAD-encrypt a sequence of 5*256=1280 zero bytes, and
the result in 5-byte chunks as the cipherstream with which to encrypt
and decrypt 256 consecutive TLS record headers.  Thus, we're only adding
one additional AEAD-encryption of a "normal-packet-sized" 1280-byte blob
once every 256 records, which seems likely to be a pretty
inconsequential performance cost.

---

Comments?

Thanks
Bryan