Subject: Re: ChaCha20-Poly1305 for SSH

From: Stefan Bühler <[email-masked]>
Date: Wed, 20 Apr 2016 10:18:38 +0200

Hi,

some time ago I tried implementing ssh-chacha20-poly1305@openssh on my
own and was rather disappointed by the state of the documentation in
openssh (in the end the source code told me what I needed to know).

Seeing draft-josefsson-ssh-chacha20-poly1305-openssh-00 I hoped there
would be some improvement... but well, it is just a copy of the openssh
file :)

So I started to work on it, and also read some of the following
discussion on ietf-ssh.

A large part of the discussion spun off discussing a whish list for a
new binary packet protocol; changing the binary packet protocol probably
requires rewriting core logic in many SSH implementations, so this
should be done very carefully and not just for one cipher, and I somehow
doubt it will happen soon.

So I propose defining "chacha20-poly1305" as either the existing
"[email-masked]" or as a slightly modified variant:

- using AEAD_CHACHA20_POLY1305 from RFC7539
- encrypt the packet length with otherwise discarded bytes from the
  first Chacha20 block, i.e. only a single Chacha20 instance
- pad the nonce to 12 bytes with zeroes on the left side, so one can
  simply reuse the original Poly1305 implementation with a 8-byte nonce.
- openssh patch:
  https://github.com/rus-cert/openssh-portable/tree/feature-chacha20-poly1305

The "full" documents can be found here:
https://github.com/rus-cert/ssh-chacha20-poly1305-drafts

It would be nice to get some feedback on whether there is interest in
getting "chacha20-poly1305" out before a protocol redesign and which
variant to go for.

If there is no interest in getting an RFC for this maybe at least the
openssh devs are interested in fixing their documentation :)

---

As far as I could see the following questions were raised in the context
of the original draft announcement and some later AEAD discussions. My
comments on them should explain why I think the openssh variant is
basically ok, and why I wouldn't pull more changes into a modified
version than I did above.

- Whether to use the Poly1305 data construction from RFC7539:

  At first I thought the Poly1305 usage in
  "[email-masked]" is vulnerable to some length
  modifications; but then I remembered that Poly1305 uses an explicit
  termination in the padding.

  As the length of the AAD is fixed I see no security gain changing to
  the method described in RFC7539.

- Whether it is necesary to encrypt the packet length field:

  Some voiced a strong preference for this as a requirement to prevent
  traffic analysis.

  It was pointed out the encrypted could lead to some extra attack
  surface (or has done so in other protocols in the past), but I think
  it is safe in the context of Chacha20. I see nothing an attacker could
  gain here compared to not encrypting the length.

- Encrypting the packet length using otherwise discarded bytes from the
  Chacha20 block used for the Poly1305 key:

  It is a nice idea which can be used to optimize both performance and
  memory usage.

- Binary packet protocol rethink:

  This is certainly worth exploring, but I don't think this needs to be
  completed before "chacha20-poly1305" becomes official.

  I think a new family of algorithms could be started with a different
  binary packet protocol, or even a new SSH protocol version.

  (My idea for a new protocol: separate encryption framing and inner
  message framing. No need to hide the outer packet length anymore.)

- Changing padding requirements, authentication of the encrypted length:

  I see no need to change this in the context of a single algorithm.
  Belongs into a more generic protocol redesign.

Cheers,
Stefan

---

From: [email-masked] (Niels Möller)
Date: Thu, 21 Apr 2016 21:15:55 +0200

> would be some improvement... but well, it is just a copy of the openssh

I think Simon's intention was percisely to document what openssh does.

I hope you've also seen draft-nisse-secsh-aead-00. I'm replying looking
for ways to improve that and move forward. 

> new binary packet protocol; [...] and I somehow

Agreed.

>   simply reuse the original Poly1305 implementation with a 8-byte nonce.

I'm not following you here. And I'm not sure what you mean by "original poly1305".
Poly1305-AES as defined in http://cr.yp.to/mac/poly1305-20050329.pdf?
Or the salsa20-poly1305 described in
http://cr.yp.to/highspeed/naclcrypto-20090310.pdf, which I think is what
chacha-poly1305 evolved from? I don't think either uses an 8-byte nonce.

>   termination in the padding.

As a crypto library author, I'd really prefer if there were a single
definition of chacha-poly1305 used in all applications. But that's maybe
not a very compelling argument for ssh protocol design. There may also
be reasons of ietf politics to stick to ietf's definition.

>   the method described in RFC7539.

I'm also unaware of any difference in security.

>   gain here compared to not encrypting the length.

My quite strong opinion is that we shouldn't force others to choose
between encrypted packet lengths, and using chacha-poly1305. And when
writing a specification which mentions this topic, I'd like to recommend
that other AEAD ciphers also encrypt the packet lengths, and give some
clear guidance on how to do it properly.

>   It is a nice idea which can be used to optimize both performance and

I agree it's a nice idea. I didn't go that way in my draft, because (i)
the optimization is minor, a single chacha_core operation and very small
state, and (2) because it's very algorithm specific, it doesn't
generalize to other AEAD ciphers. I'd be happy to change, if there is
support for this idea.

Also note that it's straightforward to this based on a pure
RFC5116-style interface to chacha-poly1305, which doesn't output the
additional bytes of the first block: simply run chacha20 one more time
to get the bytes used for length encryption. No less efficient than
using a separate chacha instance, like openssh is doing.

>   Belongs into a more generic protocol redesign.

I'm afraid some tweaks to the padding requirements are needed even if
you only think of chacha-poly1305, the original padding rules don't make
much sense when the length isn't encrypted in the same way as the rest
of the payload.

And I think it's desirable to have AEAD ciphers in ssh do things the
same way. It's a bit annoying, because the details aren't terribly
important, but it has to be nailed down, and I have difficulty finding a
way that isn't a bit ugly in one way or the other.

Regards,
/Niels

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

---

From: Stefan Bühler <[email-masked]>
Date: Fri, 22 Apr 2016 12:57:31 +0200

Hi Niels,

thanks for your feedback!

On Thu, 21 Apr 2016 21:15:55 +0200
[email-masked] (Niels Möller) wrote:

> [...] 
> I hope you've also seen draft-nisse-secsh-aead-00. I'm replying
> looking for ways to improve that and move forward. 

My feeling is that this document already is the "protocol rethink" (and
not just a "small algorithm family"), because:
- a "protocol rethink" would only allow AEAD anyway
- when core packet handling is changed it should be done right in the
  first place

So let me repeat my idea for a new protocol here: I'd separate the
cryptographic message framing from the SSH message framing.

That way one could really use "any" standard AEAD interface without the
need to specify how the packet length is encrypted with each single
AEAD, simpler nonce generation, ...

> [...]
> I'm not following you here. And I'm not sure what you mean by
> "original poly1305". Poly1305-AES as defined in
> http://cr.yp.to/mac/poly1305-20050329.pdf? Or the salsa20-poly1305
> described in http://cr.yp.to/highspeed/naclcrypto-20090310.pdf, which
> I think is what chacha-poly1305 evolved from? I don't think either
> uses an 8-byte nonce.

Oh my... sorry. I meant Chacha20 of course; DJBs original definition
uses a little-endian 64-bit block-counter and a 64-bit nonce (often the
packet counter). RFC7539 moves the trailing 4 bytes from the block
counter (which are almost always zero - no packet is that big) and
prepends them to the nonce in the interface (but does the same thing
internally) to get the "standard" 12-byte nonce interface.

(This also applies to how the Salsa20 streaming function in
naclcrypto-20090310.pdf is applied. Chacha20 copies the definition of
the 16-byte input from Salsa20.)

Also see how I didn't need to change the Chacha20 nonce or
implementation for the openssh patch.

> >   modifications; but then I remembered that Poly1305 uses an
> > explicit termination in the padding.  
> 
> definition of chacha-poly1305 used in all applications. But that's
> maybe not a very compelling argument for ssh protocol design. There
> may also be reasons of ietf politics to stick to ietf's definition.

Yes, I'd prefer that too. But is the preference important enough to
modify an already existing protocol?

> [...] 
> >   Some voiced a strong preference for this as a requirement to
> > prevent traffic analysis.
> >
> >   surface (or has done so in other protocols in the past), but I
> > think it is safe in the context of Chacha20. I see nothing an
> > attacker could gain here compared to not encrypting the length.  
> 
> writing a specification which mentions this topic, I'd like to
> recommend that other AEAD ciphers also encrypt the packet lengths,
> and give some clear guidance on how to do it properly.

Sounds good to me.

> > - Encrypting the packet length using otherwise discarded bytes from
> > the Chacha20 block used for the Poly1305 key:
> >
> >   It is a nice idea which can be used to optimize both performance
> > and memory usage.  
> 
> I agree it's a nice idea. I didn't go that way in my draft, because
> (i) the optimization is minor, a single chacha_core operation and
> very small state, and (2) because it's very algorithm specific, it
> doesn't generalize to other AEAD ciphers. I'd be happy to change, if
> there is support for this idea.

I also consider this optional in my "variant" proposal; I'd be also
fine with the current openssh implementation simply using a second key.

When encrypting the packet length is still required (see my comments
regarding "protocol rethink" above) I think using different nonces in a
generic AEAD specification is a good idea (although I don't think the
shift by one bit is a good idea. I'd rather shift by 32-bits, requiring
a >= 8-byte nonce instead of >= 5-byte).

Agreed.

> you only think of chacha-poly1305, the original padding rules don't
> make much sense when the length isn't encrypted in the same way as
> the rest of the payload.

Sorry :) I considered the EtM padding handling as done in openssh a
"standard"; I meant I'd rather avoid further changes in context of a
single algorithm: I'd keep the "at least four bytes" and "pad to
multiple of min(8, blocksize)" requirements (which results in a
minimum packet size of 12 bytes instead of 16 with MtE).

> important, but it has to be nailed down, and I have difficulty
> finding a way that isn't a bit ugly in one way or the other.

I agree that a better AEAD integration is needed, and that it should
be done in a consistent way.

The question remains: push "chacha20-poly1305" being identical or close
to the openssh one or wait for a generic AEAD / "protocol rethink"?

Cheers,
Stefan

---

From: [email-masked] (Niels Möller)
Date: Wed, 27 Apr 2016 15:49:48 +0200

> not just a "small algorithm family"),

That's not my intention. I want it to be general enough to guide
specification of other aead schemes, but otherwise keep changes close to
minimal.

(To really do minimal changes to the ssh protocol, one shouldn't do aead
at all, but specify chacha as a cipher, and some mac based on poly1305,
and use the old way of applying the mac to the plain text).

> internally) to get the "standard" 12-byte nonce interface.

To me, 64 bits sounds like a very reasonable size for both the counter
and the nonce. I haven't quite understood why RFC 5116 mandates
("SHOULD") a 12-byte nonce, or its separation into "fixed" and "counter"
part. 

For ssh, it doesn't matter, a 32-bit block counter is large enough, by a
large margin.

> a >= 8-byte nonce instead of >= 5-byte).

If we go with the 5116-style AEAD, I guess it would make some sense to
describe the distinct-nonce hack using the "fixed |
counter"-terminology, with a fixed part being different for length field
and the data. But then why not do it the same way for chacha-poly1305?

The reason why I ended up proposing the shift-by-one-bit construction
was that I think a reasonable AEAD API will have an auto-increment
function, incrementing the nonce by one for each message processed. With
the shift-by-one bit, the sequence in which nonces are used is simply
incrementing, with even ones for length encryption and odd ones for
data. With any other formatting, one would need two set_nonce calls per
message, or two separate state structs. So that seemed convenient to me,
but I guess I'm biased by how my crypto library works.

> I'd keep the "at least four bytes" and "pad to

Noted (I think some one else expressed a similar opinion). But precesily
what is padded changes, with aead, it has to be the data exluding the
length field. And I take it chacha should be viewed as a stream cipher
and hence pad to 8 bytes, not pad to 64 bytes?

> to the openssh one or wait for a generic AEAD / "protocol rethink"?

My preference would be

1. Do something close to openssh.

2. Specify use of chacha and poly1305 as separate cipher and mac.

3. Wait for ssh version 3, which isn't likely to happen.

Regards,
/Niels