Subject: Re: ChaCha20-Poly1305 for SSH

From: Damien Miller <[email-masked]>
Date: Tue, 3 May 2016 00:47:55 +1000 (AEST)

On Wed, 20 Apr 2016, Stefan Bühler wrote:

> 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 :)

It would be helpful if you said what in the documentation was
insufficient so we can improve it.

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

It's already happened: chacha20-poly1305 is supported by several
SSH implementations and uses a similar packet construction to
RFC5647 AES-GCM (with the exception of encryting the packet length).
There's also the -etm MACs in OpenSSH as Niels observes.

> 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

I chose to use an independently-keyed instance of chacha20 for
length field encryption to be completely sure there could be
no possible decryption oracle between them. This was a deliberately
conservative choice that was fortunately cheap since chacha20 is so
fast.

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

I agree that if we are redoing the chacha20-poly1305 mode then it
should match the parameter lengths used in other IETF protocols.

> 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 :)

Like I said, it would be great if you let us know what in particular
was deficient in the documentation so we can fix it.

With regards to the future of the chacha20-poly1305, I'm hoping
to interest a researcher in looking into length-hiding as a
traffic-analysis countermeasure in the SSH protocol. The "Peek-a-boo"
paper considers fingerprinting websites in the web attack model, which
is very different to and in many ways more demanding than SSH's attack
model. It would be good to have more definitive research that targets
the SSH protocol and thread model passwords, keystroke timings, etc)
and make a decision based on that.

With that out of the way, and if it yields a recommendation to
pursue length-hiding then it's probably worth revisiting the exact
construction. E.g. your proposal to use the remaining bytes from
the first block, but I wasn't aware of [1] when I designed this mode.

-d

[1] http://www.iacr.org/archive/eurocrypt2012/72370677/72370677.pdf

---

From: Stefan Bühler <[email-masked]>
Date: Tue, 3 May 2016 11:18:10 +0200

Hi Damien,

On Tue, 3 May 2016 00:47:55 +1000 (AEST)
Damien Miller <[email-masked]> wrote:

> > 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 :)  
> 

Fair enough:
- "This forms two 256 bit keys (K_1 and K_2), used by two separate
  instances of chacha20.", and then K_1 is used to encrypt the length.
  But the keys are actually `K_2 || K_1` !
- There is no reference to EtM-modes and how they handle padding.
- By saying "no MAC is required" one might think that the MAC length is
  zero and Poly1305 tag is somehow part of the packet content, and that
  the length of it needs to be reflected in the length field.
  But the MAC length is actually 16 bytes.

I also feel the document is not structured very well, and a lot of
things could be said more explicitly.

But now I'm also curious: do you actually consider the document good
enough to be published as RFC?

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

I can't find it on
http://ssh-comparison.quendi.de/comparison/cipher.html, and I hope it
isn't actually named "chacha20-poly1305" without being listed in the
IANA registry. Can you give me any pointers?

Which Chacha20 nonce size does it use? Does it actually use "invocation
counters" instead of the sequence counter? Does it use an IV as fixed
part of the nonce, or just zero bytes?

> conservative choice that was fortunately cheap since chacha20 is so

I have no real preference here, I just found it could be a nice option
(I think Niels Möller presented it on the mailing list).

> should match the parameter lengths used in other IETF protocols.

So the question is (again) whether we should do it or not.

> [...]

I probably have to do some reading to even understand what this is
about :) But I don't think this should be considered only for
chacha20-poly1305 but for generic AEAD usage (if possible).

- Stefan

---

From: Damien Miller <[email-masked]>
Date: Tue, 3 May 2016 23:10:35 +1000 (AEST)

>   But the keys are actually `K_2 || K_1` !

Thanks, I'll add a note to clarify.

> - There is no reference to EtM-modes and how they handle padding.

Why should there be?  EtM is completely separate.

>   But the MAC length is actually 16 bytes.

But the document doesn't say this. It says, in a section that describes
the KEX negotiation, "no MAC is required to be negotiated". IMO that's
quite clear from context.

Perhaps you're referring to the "no separate MAC is required" statement
in the same paragraph. This immediately follows a sentence that
describes the AEAD as including authentication. IMO the context is clear
here too.

The rest of the document discusses at length how the in-AEAD MAC is
derived and should be checked so nobody who read the whole thing
could (again IMO) come away with the impression that the protocol
includes no MAC or that it isn't included in the packet.

> things could be said more explicitly.

Such as? I'm happy to act on specific suggestions. Vague statements
of displeasure aren't really actionably though.

> enough to be published as RFC?

I'd consider it good enough to publish as an I-D, but I don't intend
to for the reasons I've already outlined.

> IANA registry. Can you give me any pointers?

http://ssh-comparison.quendi.de/comparison/cipher.html search for
chacha20-poly1305, scroll right.

-d