Subject: Re: AEAD in SSH: Toss block alignment requirements

From: denis bider <[email-masked]>
Date: Tue, 1 Mar 2016 01:27:46 +0000

The problem is not that the sender applies padding. The sender definitely should. The problem is that block-aligned padding is enforced by the receiver, even when this is not optimal.

With AEAD, where the 4-byte length is separate from the alignment; this constrains the sender in its ability to mask things. (This is also the case with CTR and hmac-sha1.)

With block alignment requirements in place, it is not possible to hide whether you're sending this:

  SSH_MSG_LARGE_USEFUL_PACKET

Or this:

  SSH_MSG_SMALL_USEFUL_PACKET
  SSH_MSG_IGNORE
  
In the former case - one packet - AEAD transmission size is going to be:

    4 + 16*x + 16
  = (x+1)*16 + 4
  
In the second case - two packets - AEAD transmission size is going to be:

    4 + 16*x + 16
  + 4 + 16*y + 16
  = (x+y+2)*16 + 8

It is therefore trivially distinguishable whether you're sending one large packet, or two packets back-to-back. With one packet, transmission length is coerced to (N mod 16) == 4. With two packets, it's coerced to (N mod 16) == 8.

To work around this, to effectively mask what you're sending, you must always send either this:

  SSH_MSG_LARGE_USEFUL_PACKET
  SSH_MSG_IGNORE (small)
  
Or this:

  SSH_MSG_SMALL_USEFUL_PACKET
  SSH_MSG_IGNORE (large)

It could be argued that this loss of flexibility - the inability to hide the number of packets in a transmission - has the upside of forcing naive or negligent implementations to always pad outgoing packets. Such implementations might otherwise not pad at all, revealing the lengths of passwords.

That might be a compelling argument. I don't know.

Regardless - block alignment is our current reality. I have altered the "fixed-bandwidth" draft to take this into account - to always send two packets in a transmission, instead of sometimes two and sometimes one:

https://tools.ietf.org/html/draft-ssh-fixed-bandwidth-02

----- Original Message -----
denis bider <[email-masked]> writes:

> - For inclusion in Niels's draft with AEAD guidelines, discourage or
> prohibit unneeded block alignment for packet receivers.

In general, I'm thinking that padding is a useful complement to
SSH_MSG_IGNORE. In current use, one effect is that SSH_MSG_USERAUTH
"password" packets are close to fix size (in the absence of any other
traffic analysis countermeasures). If I count correctly, the payload of
a SSH_MSG_USERAUTH_REQUEST message requesting the "ssh-connection"
service and using password authentication is 40 bytes + the actual sizes
of username and password (and then it may be comprssed, I'm ignoring
that complication here, but I wouldn't expect it to change the size very
much).

With a 16 byte block size and minimum 4 bytes of padding, it doesn't fit
in three blocks, so it will be padded to 64 bytes + mac, with 19 bytes
of padding. So if len(username) + len(password) <= 15, we're getting a
cryptotext of 64 bytes, and if 16 <= len(username) + len(password) <=
31, we get 80 bytes. Which is a significant improvement over leaking the
exact length.

(There are related issues for other message types, in particular
SSH_MSG_CHANNEL data, where pad-to-block-size could help hiding the
number of keystrokes. Assuming an implementation is able to collect
quickly typed characters into a single data packet, e.g., by setting
VMIN and VTIME on a unix terminal).

For AEAD, I am tempted to drop all MUST requirements on padding lengths
and leave it up to the implementation. However, I won't do that unless I
see some additional support here. And if we go that way, I think we have
to include some SHOULD rule which provides at least as good hiding of
userauth passwords as the original spec.

> Optionally, we COULD also deprecate compulsory alignment for existing
> modes that don't need it, i.e. CTR.

I don't think it's a good idea to change the rules for non-AEAD ciphers.
We'll get incompatible versions for very little benefit.

And if you want to generate constant size TCP segments, you can do
arbitrary segment size regardless of padding rules, by sending TCP
segments which end with a partial SSH_MSG_IGNORE.

Regards,
/Niels

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

---

From: denis bider <[email-masked]>
Date: Tue, 1 Mar 2016 01:37:23 +0000

Also:

> And if you want to generate constant size TCP segments,
> you can do arbitrary segment size regardless of padding
> rules, by sending TCP segments which end with a partial
> SSH_MSG_IGNORE.

You're right, this is true. Generate an SSH_MSG_IGNORE that's just big enough, or slightly too large; then include any extra bytes as part of the next transmission.

I'm not sure that this has a decisive advantage compared to just always sending an SSH_MSG_USEFUL_PACKET + SSH_MSG_IGNORE, though.

denis bider <[email-masked]> , 3/1/2016 1:02 AM:
The problem is not that the sender applies padding. The sender definitely should. The problem is that block-aligned padding is enforced by the receiver, even when this is not optimal.

Or this:

    4 + 16*x + 16
  = (x+1)*16 + 4

    4 + 16*x + 16
  + 4 + 16*y + 16
  = (x+y+2)*16 + 8

  
Or this:

----- Original Message -----

Regards,
/Niels