Friday 29 November 2013

ChaCha20 and Poly1305 in OpenSSH

Recently, I committed support for a new authenticated encryption cipher for OpenSSH, chacha20-poly1305@openssh.com. This cipher combines two primitives from Daniel J. Bernstein: the ChaCha20 cipher and the Poly1305 MAC (Message Authentication Code) and was inspired by Adam Langley's similar proposal for TLS.

Why another cipher and MAC? A few reasons... First, we would like a high-performance cipher to replace RC4 since it is pretty close to broken now, we'd also like an authenticated encryption mode to complement AES-GCM - which is great if your hardware supports it, but takes significant voodoo to make run in constant time and, finally, having an authenticated encryption mode that is based on a stream cipher allows us to encrypt the packet lengths again.

Wait, what do you mean by "encrypt the packet lengths again"? (last rhetorical question, I promise) Well, it's a long story that requires a little background:

Back in the dark ages of the SSH2 protocol's design, there wasn't consensus among cryptographers on the best order to apply encryption and authentication in protocols - in fact, the three main cryptographic protocols to emerge from the 1990s - SSL, SSH and IPsec - all use different choices: SSL calculated a MAC over the packet's plaintext, appended it to the plaintext packet and encrypted and sent the lot - a construction now called "MAC then Encrypt" or "MtE". IPsec encrypted the plaintext, calculated the MAC over the ciphertext and appended it - this is now called "Encrypt then MAC" (EtM). SSH calculated the MAC over the plaintext, encrypted it and then appended the MAC - this is called "Encrypt and MAC" (EaM).

Of these, only "Encrypt then MAC" is now considered safe and in retrospect it's pretty easy to see why: for MtE and EaM, it's necessary to decrypt and process the packet before checking the MAC. Doing this allows an active attacker (i.e. one who is happy to forge or modify messages) the chance to peek behind the veil of the encryption before the MAC check detects their mischief. This has resulted in attacks on both SSL/TLS and SSH that wouldn't otherwise have been possible.

Recent versions of OpenSSH have offered some solutions to the problems caused by the original Encrypt-and-MAC design: AES-GCM cipher modes and Encrypt-then-MAC MAC modes. The AES-GCM ciphers aes128-gcm@openssh.com and aes256-gcm@openssh.com replace the usual cipher+MAC combination with a combined authenticated encryption mode the provides confidentiality and integrity in a single cryptographic algorithm. The Encrypt-then-MAC MAC modes alter the SSH packet format to be more IPsec-like: performing encryption first and then authenticating the ciphertext.

Both AES-GCM and the EtM MAC modes have a small downside though: because we no longer desire to decrypt the packet as we go, the packet length must be transmitted in plaintext. This unfortunately makes some forms of traffic analysis easier as the attacker can just read the packet lengths directly. OpenSSH takes some countermeasures to obscure the lengths of obvious secrets like passwords used for login or typed into an active session, but I haven't felt entirely comfortable with the protocol revealing the length of every packet sent on the wire.

The new chacha20-poly1305@openssh.com avoids this though. In addition to providing authenticated encryption with integrity-checking performed before unwrapping encrypted data, this mode uses a second stream cipher instance to separately encrypt the packet lengths to obscure them from eavesdroppers. An active attacker can still play games by fiddling with the packet lengths, but doing so will reveal nothing about the packet payloads themselves - they can make the receiving end read a smaller or larger packet than intended, but the MAC will be checked (and the check will fail) before anything is decrypted or used. Fortunately ChaCha20 is very fast and has quite small keys, so maintaining a separate instance is very cheap.

We're not done yet though - an attacker may still observe the encrypted packets on the network to try to ascertain their length, and right now they are likely to be successful. I hope to add some features to frustrate this sort of traffic analysis some time next year.

Full details on the new mode are in the PROTOCOL.chacha20poly1305 file in OpenSSH and the source code for the cipher itself. If there is anything that these don't explain, then feel free to contact me.

8 comments:

  1. 'for EtM and EaM, it's necessary to decrypt...' should be 'for MtE and EaM, it's necessary to decrypt...'

    ReplyDelete
  2. Hi Damien, thanks for the entry, and two things:

    - The "PROTOCOL.chacha20poly1305 file" link prepends "http://blog.djm.net.au/2013/11/" to it so it's not working.
    - Do you know if chacha20poly1305 could be used in iked/isakmpd in OpenBSD?


    Regards.

    ReplyDelete
  3. Hi Pablo,

    I fixed the link - thanks for pointing it out.

    Re: iked/isakmpd, Markus was considering implementing something along these lines. It isn't too tricky, but without publishing a RFC there would be no interoperability with non-OpenBSD implementation (unless we convinced other vendors to use the same numbers).

    ReplyDelete
  4. I'm curious, what kind of measures can be implemented to make the length more difficult to guess ?

    ReplyDelete
  5. We can do a few things: hiding keystroke timings by sending packets only on a pre-defined schedule (e.g. every 10ms), hiding the quantity of keystrokes by sending chaff packets for a period after the initial one and hiding the result from the server by more aggressively padding out replies and replying to chaff as well as real packets.

    All of these are made more complex by our crappy select-based mainloop unfortunately.

    ReplyDelete
  6. Quantizing to 10ms could put latency over the 100ms barrier some percentage of the time. Chaff and padding will increase bandwidth which could affect mobile significantly. Are these only to occur during password entry? Could you combine compression with random padding to mask the effects of BEAST/CRIME-based attacks, which could affect VPN? And when can we convince NetworkManager to support SSH VPN? :-)

    ReplyDelete
    Replies
    1. Too many questions there:

      > Quantizing to 10ms could put latency over the 100ms barrier some percentage of the time

      how? and why is 100ms a barrier?

      > Chaff and padding will increase bandwidth which could affect mobile significantly.

      it depends on what gets implemented. quantisation, chaff and padding matter most for interactive keystrokes where the bandwidths are lowest. A 2x increase data for single keystrokes would probably be completely unnoticeable even on cellular radio connections.

      Chaffing only activates when there are no real keystroke events to send, so its effect on interactive use would be minimal. In fact, it might even help: http://gamedev.stackexchange.com/questions/18686/optimal-data-size-for-a-3g-client-server-game

      > Are these only to occur during password entry?

      Dunno. Nothing has been implemented yet and it would probably be optional anyway.

      > Could you combine compression with random padding to mask the effects of BEAST/CRIME-based attacks, which could affect VPN?

      compression-related attacks are much harder for SSH than HTTP as the adversary can't usually cause a client to make zillions of connections to a server. That being said, I don't think anyone has properly investigated what attacks compression does open in the SSH protocol. OpenSSH's default of no compression until after authentication completes helps with the most obvious one though :)

      > And when can we convince NetworkManager to support SSH VPN?

      Good luck with that - AFAIK the GNOME developers gave up on implementing advanced features over a decade ago with the release of Gnome 2. See also http://www.isittheyearofthelinuxdesktop.com

      Delete