Subject: applying AES-GCM to secure shell: proposed "tweak"

From: Tim Polk <[email-masked]>
Date: Wed, 8 Apr 2009 09:02:00 -0400

Folks,

The IESG is currently considering publication of draft-igoe-secsh-aes-
gcm-01, "AES Galois Counter Mode for the Secure Shell Transport Layer
Protocol", as an Informational RFC.  The draft specifies the
application of the Authenticated Encryption with Associated Data
(AEAD) block cipher mode AES Galois/Counter Mode to provide both
confidentiality and data integrity for SSH.  (See RFC 5116, "An
Interface and Algorithms for Authenticated Encryption", for a general
look at AEAD algorithms and NIST Special Publication 800-38D for the
specification of the GCM mode; see URLs below.)

The draft was designed to minimize the changes to RFC 4253 (the SSH
Transport Layer Protocol), so it encrypts the whole SSH binary packet,
including the packet_length field.

However, AEAD decryption as defined in both RFC 5116 and SP 800-38D
takes the ciphertext as input, and returns either (1) the plaintext if
the authentication succeeds or (2) failure. The ciphertext here is an
octet string of known length, not an ubounded stream.

Since the packet_length field is also encrypted, SSH cannot determine
the ciphertext boundary before passing the data to AEAD decryption.
(This differs from current SSH encryption modes where the data is
first decrypted, then the packet length field is parsed, and finally
the MAC is verified.)

Two solutions have been proposed: (1) explicitly allowing "partial
decryption" so that an implementation can recover the packet_length
without authenticating the data; or (2) sending the packet_length
unencrypted so that it is always available.

The first solution requires less security analysis about SSH, but more
analysis about the AEAD algorithm. The exposure of intermediate values
in AES GCM would require review, and it is inconsistent with RFC
5116. Even if this solution is determined to be secure for AES GCM,
this might not apply to other AEAD algorithms (where returning
plaintext fragments before authentication may not be even possible, or
may not be secure). In a more parochial concern, inconsistency with SP
800-38D means that current validation processes (i.e. NIST's FIPS
140-based Cryptographic Module Validation Program [CMVP]) would need
to be revised, as well as SP 800-38D, to permit use of this protocol
with validated modules.

The second solution (sending packet_length unencrypted) has a number
of desirable properties: it conforms to RFC 5116 so the design should
apply to any AEAD algorithm, and it is consistent with the algorithm
specification (NIST SP 800-38D).  It does require a change to the
padding calculations: since the plaintext for encryption excludes the
packet_length, the concatenation of the 'padding length', 'payload',
and 'random padding' MUST be a multiple of the cipher block size.
(This modifies a requirement from Section 6 of RFC 4253.)  Since this
calculation is algorithm specific anyway, it is hoped this would not
be an issue. As you might have guessed, I strongly prefer this
solution.  However, we are concerned about making such a change
without ensuring that the security implications have been thoroughly
reviewed.

The SSHv1 protocol revealed the exact plaintext length, which is
clearly undesirable in many situations (see e.g. link below).  In
SSHv2, the packet length includes the random padding, so sending it
unencrypted does not reveal the exact the plaintext length. Also, in
many cases the packet length can be inferred from the data stream
(e.g. TCP segment lengths). In applications where there is some fear
that the packet lengths might reveal sensitive information, the use of
random padding probably provides a much more effective countermeasure
than encrypting the packet_length.

So, it seems that encryption of the packet_length field would be of
little practical use, and might lead to a false sense of security.  As
a consequence, we hypothesize that sending packet_length in the clear
would not negatively impact the security of the protocol.

Before moving forward with this protocol using either of the proposed
solutions, we would appreciate feedback from this mailing list.
Questions to consider:

(1) does the exposure of the ssh packet length have significant
security implications for ssh itself?

(2) were applications that rely on ssh for security designed to take
advantage of the encrypted packet length?

(3) does the change in padding length calculation (caused by excluding
the packet_length from the ciphertext) impose a significant impediment
to migrating existing implementations?

Thanks,

Tim Polk
(Security co-AD and document sponsor)

P.S. I've tried to contact as many of the usual suspects as possible,  
but I am sure I have
missed some folks.   Please forward this to anyone I've left off  
distribution that might
have an interest!]

References:

http://tools.ietf.org/html/rfc5116
http://tools.ietf.org/html/draft-igoe-secsh-aes-gcm-01
http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
http://www.openwall.com/advisories/OW-003-ssh-traffic-analysis/

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 03:20:33 +1200

[Followups trimmed somewhat]

Tim Polk <[email-masked]> writes:

>(1) does the exposure of the ssh packet length have significant security
>implications for ssh itself?

Given the recent weakness discovered in OpenSSH (allowing recovery of limited
amounts of plaintext due to the length being encrypted), the only effect I can
think of is that'd it'd make it more secure, not less.

>advantage of the encrypted packet length?

Not in my case.  In fact it's actually a considerable pain since it messes up 
the stream processing, you can't read and decrypt the entire packet in one 
clean operation like SSL but have to read and decrypt a bit of it, extract 
metadata from the start, buffer the rest that was decrypted, read and decrypt 
the remainder, and then reattach the prevously-decrypted data to the start.

>(3) does the change in padding length calculation (caused by excluding the
>packet_length from the ciphertext) impose a significant impediment to
>migrating existing implementations?

Nope.  In fact it significantly simplifies them, for the reason given above.

Peter.

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 8 Apr 2009 11:03:38 -0500

> including the packet_length field.

As you know encrypting the SSH packet length has caused us nothing but
trouble.  I recommend sending it in the clear.

> unencrypted so that it is always available.

(1) may be impossible to implement with some existing AEAD crypto APIs.
Adding AEAD crypto APIs that allow for "partial decryption" is possible,
but would add a significant wrinkle in getting this deployed.

I strongly recommend (2).  It's what all other protocols do.

There's also (3): specify two variants of this ssh cipher, one that does
not encrypt the packet length (this one would be REQUIRED) and one that
does (OPTIONAL).

We should do (3) IFF there are implementors who really need to defeat
traffic analysis and are up to the task of ensuring that, for example,
TCP window changes don't give away SSH message boundaries, and that they
use random padding and ignore messages in a way that does hide actual
ssh traffic patterns.

> to be revised, as well as SP 800-38D, to permit use of this protocol

Indeed, (1) is just too painful.

> without ensuring that the security implications have been thoroughly

The fact that SSHv2 encrypts the packet length has been a cause of a
significant protocol security vulnerability.  Let's kill this encrypt-
the-packet-length notion.

> would not negatively impact the security of the protocol.

Agreed.

> security implications for ssh itself?

Not negative ones.  As you say, one may want to ensure the use of random
padding to avoid revealing, e.g., password lengths.

> advantage of the encrypted packet length?

Not that I know of.

> to migrating existing implementations?

The changes would all be localized to the SSHv2 implementation.  There
would be more changes to make to an SSHv2 implementation if we go with
(2), but (1) requires changes to parts of the system that an SSHv2
implementor may not be in a position to make, thus from a political
point of view (2) is clearly easier than (1).

Nico
--

---

From: Simon Tatham <[email-masked]>
Date: Wed, 08 Apr 2009 17:43:24 +0100

> to migrating existing implementations?

I was thinking about this when the recent vulnerability (CERT
VU#958563) was announced. I started thinking about what sort of a
binary packet protocol would have been intrinsically immune to
problems of that type, and came to similar conclusions: that the
problems with SSH-1's cleartext packet lengths arose from having
them correspond to the exact semantic size of an SSH message, and
it's not the case that cleartext lengths are _inherently_ harmful.

I came up with a design for a replacement BPP in two layers: the
outer layer divides the wire data stream into blocks each of which
is encrypted and MACed as a unit, and then the inner layer
conceptually glues the plaintext of all those blocks back together
and divides the resulting stream up into SSH messages by means of
separate markings within that stream. Then it's safe to send the
outer layer's block lengths in cleartext, (a) because they tell a
passive listener nothing that they couldn't have deduced from the
TCP segment boundaries anyway, and (b) an active attacker cannot
replace any block without having to forge a correct MAC for that
block. (Naturally the MAC also includes sequence numbers to prevent
block-rearrangement attacks.)

The division between semantic SSH messages in layer 2 is thus
decoupled from the division between blocks in layer 1, meaning that
you can transmit several messages in a block (saving space overall!)
or split one large message across several blocks if you like.

And finally, the MAC is applied to the ciphertext rather than the
plaintext, so you end up with a hard guarantee against leakage
attacks of the sort described in VU#958563: you cannot trick an
implementation into decrypting ciphertext of your choosing and
acting as an oracle, because nothing is even _shown_ to the
decryption code until it's passed its MAC, so first you would have
to forge a correct MAC for your chosen ciphertext.

I never quite got round to writing it up and posting it to this
list, mostly because I feared the general reaction would be that
nobody wanted to go right back to the start of the SSH protocol
design process at this stage :-) Would there be interest in seeing
it?
-- 
Simon Tatham         "A cynic is a person who smells flowers and
<[email-masked]>    immediately looks around for a coffin."

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 08 Apr 2009 13:22:35 -0400

> without ensuring that the security implications have been thoroughly

On first glance, this seems reasonable from a security standpoint; as 
previously noted, we've seen problems resulting from the length being 
encrypted, and as you've discovered, treating the encryped length as part 
of the same plaintext it describes leads to some interesting problems 
trying to read the encrypted packet off of the TCP stream.

I am concerned about the implications of an encryption algorithm spec 
changing parts of the base protocol.  The protocol is designed such that 
there is an abstraction between the transport protocol and the individual 
compression, encryption, integrity, key exchange, and public key 
algorithms.  You propose introducing an encryption algorithm which requires 
that the transport protocol itself behave differently when that algorithm 
is in use, not only in not encrypting the length, but in changing the 
generation of padding on outgoing messages.

I'd rather see an extension to move the length out of the encrypted part of 
the packet (and makes the required padding changes), which is negotiated 
separately and can be used with any encryption algorithm.  It would then be 
reasonable to for AEAD encryption algorithms to require support for and use 
of the new extension.

-- Jeff

---

From: der Mouse <[email-masked]>
Date: Wed, 8 Apr 2009 16:30:21 -0400 (EDT)

> changing parts of the base protocol.

I'm not sure that's really what's going on here.  I really need to find
the time to go read the spec, but from what I've gathered from the
list, this could, as far as the core protocol is concerned, be seen as
an encryption algorithm that happens to produce ciphertext identical to
the plaintext for certain parts of the data stream.

Does that weaken the security assurances provided by the protocol?  I
don't know.  My feeling is that it doesn't, but there's lots of
counterintuitive stuff running around crypto, and I'd need to think
about it a lot more to have any degree of confidence that's right.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 08 Apr 2009 17:05:16 -0400

> the plaintext for certain parts of the data stream.

I wouldn't have a problem with that, but it's not actually the case.  The 
base protocol spec assumes that encryption algorithms have a block size, 
and requires that the amount of padding be chosen such that the combined 
size of the length, padding length, padding, and payload be a multiple of 
the block size.  Moving the length out of the encrypted part requires 
changing this behavior.

Separately, I'd like to see an unencrypted-length option so we can 
negotiate its use even when not using an AEAD encryption algorithm.

> about it a lot more to have any degree of confidence that's right.

Agreed.  We know about problems with encrypting the length as we do now, 
but I think we need to consider the implications of leaving it unencrypted 
fairly carefully.

-- Jeff

---

From: der Mouse <[email-masked]>
Date: Wed, 8 Apr 2009 19:28:45 -0400 (EDT)

>> [F]rom what I've gathered from the list, this could, as far as the
>> core protocol is concerned, be seen as an encryption algorithm that
>> happens to produce ciphertext identical to the plaintext for certain
>> parts of the data stream.
> I wouldn't have a problem with that, but it's not actually the case.
> The base protocol spec assumes that encryption algorithms have a
> block size, and requires that the amount of padding be chosen such
> that the combined size of the length, padding length, padding, and
> payload be a multiple of the block size.

Right - with an artificial block size imposed for stream ciphers.
(Actually, the wording in RFC4253 is not very good; consider what an
implementer reading the "Note that the..." paragraph beginning ten or
so lines into page 8 would do with a cipher using 7-byte blocks.)

> Moving the length out of the encrypted part requires changing this
> behavior.

Why?  As far as I can see, this is so only if (a) the underlying cipher
has a block size that's not a divisor of 4 bytes and (b) you insist on
naïvely treating all the sent-encrypted data as a single data stream
for the encryption engine.

It would be very easy, for example, to use arcfour (or any other stream
cipher) to encrypt all but the length.  Also, I just reread section 6
of 4253, and I can't find anything that says the ciphertext from an
encryption algorithm has to be the same size as the plaintext, so you
could always just save the length, replace it with four random bytes,
encrypt as normal, and prepend the saved length.  (Decryption, of
course, just throws away the four random bytes.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 8 Apr 2009 17:39:15 -0500

> generation of padding on outgoing messages.

What would the negotiation look like?  Would it apply to existing
ciphers as well?

[So far the only extensibility mechanisms that we have at that point in
the protocol are: new protocol version number (not going to happen) and
magic algorithm names (which have been used successfully).]

Nico
--

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 15:27:30 +1200

Nicolas Williams <[email-masked]> writes:

>significant protocol security vulnerability.  Let's kill this encrypt- the-
>packet-length notion.

If we're going to make this change, could we also consider moving *all*
ciphers to nonencrypted lengths?  This currently requires horribly complex
code to process, and it's the very first thing an attacker will hit (that is,
the first bit of client/server code an incoming, possibly hostile packet, will
encounter is the complex encrypted-length processing).  It'd be really nice to
be able to switch this off to reduce the attack surface, subject to
negotiation that the other side supports it, obviously.  There's a 32-bit
flags field in the handshake that's currently unused, one bit could be used to
indicate unencrypted lengths.

Peter.

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 8 Apr 2009 23:00:55 -0500

> ciphers to nonencrypted lengths?  This currently requires horribly complex

Not with a flag day.  Implementors will have to keep implementing the
old thing for a long time.

Nico
--

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 15:51:35 +1200

Nicolas Williams <[email-masked]> writes:

>[So far the only extensibility mechanisms that we have at that point in the
>protocol are: new protocol version number (not going to happen) and magic
>algorithm names (which have been used successfully).]

... and the completely unused 32-bit flags field in the first message, which I
mentioned previously :-).

Peter.

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 8 Apr 2009 22:57:49 -0500

> mentioned previously :-).

This:

      uint32       0 (reserved for future extension)

?

Yes, that could be used too.

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 8 Apr 2009 23:00:01 -0500

> Yes, that could be used too.

Er, actually, I'm not sure.  It depends on what implementations do with
it now when it's not set to 0.  Hmmm, what does the spec say to do about
that field?  Sadly: nothing, at least not in section 7.1.

That probably means that we can't use that field.

---

From: Damien Miller <[email-masked]>
Date: Thu, 9 Apr 2009 13:25:50 +1000 (EST)

> unencrypted so that it is always available.

another option, would be encrypting the length field with an
independently-keyed cipher, but I doubt that it is worth it.

I'd agree that simply leaving the length fields unencrypted would
be best, but the security considerations should mention the need to
use padding to avoid revealing secrets, especially for password
userauth.

Some general comments on the draft:

First, why GCM? Some rationale would be nice.

4.1 Key exchange implies modification to the matching rules, but doesn't
IMO sufficiently spell out exactly how matching should occur when the
GCM method appears in various positions of the client and server's lists.

5.1/5.2 - The suggested algorithm names are structurally different to
the other algorithm identifiers used in SSH. In particular, I don't see
any need for the "-ssh" to appear in the algorithm name as the cipher
has not been modified in any substantial way. Why not just "aes128-gcm"
or "aes128-gcm-aead" if you wanted to be particularly verbose?

-d

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 17:10:13 +1200

Nicolas Williams <[email-masked]> writes:

>Er, actually, I'm not sure.  It depends on what implementations do with it
>now when it's not set to 0.  Hmmm, what does the spec say to do about that
>field?  Sadly: nothing, at least not in section 7.1.

Well if it's RFU then it's implied that you ignore it, which has been the 
practice for RFU fields since at least the 1970s (in things like status flags 
registers), and probably even earlier but I wasn't playing with computer 
hardware back then.

How about a quick straw poll, since we've probably got a good number of
implemeters here.  If your implementation sees a non-zero value in the RFU
field, will it:

  1. Ignore it and continue, since it's RFU.
  2. Run Nethack, and failing that, emacs in Towers-of-Hanoi mode.
  3. Reformat the hard drive.
  4. ???
  5. Profit.

Peter.

---

From: der Mouse <[email-masked]>
Date: Wed, 8 Apr 2009 23:44:09 -0400 (EDT)

> If we're going to make this change, could we also consider moving
> *all* ciphers to nonencrypted lengths?  This currently requires
> horribly complex code to process,

That wasn't my experience as an implementor.  Perhaps you're trying to
(ab)use cryptosystem interfaces not designed for that style of use?

> There's a 32-bit flags field in the handshake that's currently
> unused, one bit could be used to indicate unencrypted lengths.

I suspect that will not interoperate well with implementations not
supporting plaintext lengths.  I see no guidance in 4253 as to what
protocol speakers should do if that flags field is nonzero (or, more
generally, has non-understood bits set) in an incoming packet, and
suspect I'm not the only implementor who's simply ignored it (which
won't interoperate) or checked it and errored if it's nonzero (which
won't interoperate either).  That flags field was ill-thought-out, and
I wish I'd noticed it before the drafts were turned into RFCs.

I would suggest creating new packet type for negotiating options like
this.  As a strawman:

      byte         SSH_MSG_OPTION (value = 7)
      string       option name
      ...          option-specific data

The option name uses the DNS-based extensibility mechanism (4251
section 6); all data after the option name, including types and values,
is option-specific and is described in the definition of the option.
SSH_MSG_OPTION may be sent at any time, except that specific option
definitions may impose additional restrictions for packets naming that
option.  Implementations that do not understand SSH_MSG_OPTION MUST
respond to it with SSH_MSG_UNIMPLEMENTED, as specifeid in 4253 11.4.
The option name "unimplemented" is reserved; it is used to indicate
that SSH_MSG_OPTION is implemented but that a particular option is not
implemented (or is disabled for the connection in question by a
configuration mechanism).  Its additional data consists of a single
string, which contains the unimplemented option name from the request
that provoked the packet.  SSH_MSG_OPTION packets with "unimplemented"
as the option name MUST NOT be sent under any other circumstances.
Option definitions MUST indicate what semantics SSH_MSG_UNIMPLEMENTED
and "unimplemented" responses have for the options they define.

As a further strawman:

I propose the option name "cleartext-packet-lengths".

Option-specific data is a single string, which MUST be "on", "off",
"ack", "nak", or "mark".  Packets for this option with other than
exactly one string of additional data, or with other than one of those
five strings as the additional data string, are reserved for future
standardization; an implementation of this spec MUST respond with a
"nak" message to any such packet it recieves.

Cleartext packet length use is negotiated separately in each direction.
There are two states (in each direction): the negotiated state and the
live state.  The negotiated state is used to negotiate the option; the
live state controls whether packet generation is affected.  Both states
are "off" at connection startup.

Negotiation for each direction is initiated by the peer sending packets
in that direction; the sender sends an "on" or "off" packet, indicating
whether it proposes to turn the option on or off, to which the receiver
MUST respond with an "ack" or "nak" packet, indicating acceptance or
rejection of the request.  A sender MUST change its record of the
negotiated state to match the corresponding "on" or "off" packet, upon
receiving an "ack" response; it MUST NOT make any such change upon
receiving a "nak" response.  A sender may also send a "mark" packet;
when it does so, it MUST, between sending that packet and the packet
immediately following, copy the negotiated state to the live state.  A
sender MUST NOT change its live state under any other circumstances.
(To avoid indeterminate behaviour, a sender MUST NOT send a "mark" when
an "on" or "off" packet has been sent but no corresponding "ack" or
"nak" has been received, unless the resulting negotiated state would be
the same regardless of which response is received.)

A sender MAY choose to delay, or not send at all, a "mark" after a
negotiation, even one that changes the negotiated state.

There also is no requirement that any change to the negotiated state,
nor indeed any negotiation at all, take place before sending a "mark"
(though the "mark" will, of course, not correspond to a change in the
live state in such a case).

An SSH_MSG_UNIMPLEMENTED packet or an "unimplemented" SSH_MSG_OPTION
packet (collectively, an "error packet") must always be handled so as
to disable the option - that is, when it is in response to an "on", it
is to be treated as a "nak"; in response to "off", as an "ack".
Implementations MUST NOT generate error packets in response to packets
for this option after responding in any other way to any packet for
this option on the same connection (but MAY switch in the other
direction, responding with a non-error packet after responding with an
error packet).  This means that an error packet in response to a "mark"
can be ignored, since the "mark" must not mark any actual change in the
live state, and that an error packet in response to an "ack" or "nak"
indicates a broken implementation.

When the live state is "off", the connection operates as it would if
this option were not implemented.  When the live state is "on", the
binary packet protocol described in 4253 section 6 is modified.  The
definition of the value in the packet_length field is unchanged, but
that field is not part of the encryption data stream; it is effectively
removed from the packet for purposes of computing padding amounts and
encryption.  It is sent in the data stream, unencrypted, before (the
encryption of) the rest of the packet.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 16:26:24 +1200

Nicolas Williams <[email-masked]> writes:

>Not with a flag day.  Implementors will have to keep implementing the old
>thing for a long time.

I meant with a bit-flag day, not a flag day.  In other words if the uint32 at
the end of the SSH_MSG_KEXINIT contains a 1-bit (say in the LSB) for both
sides' KEXINIT then things proceed with unencrypted lengths.

(This isn't entirely satisfactory because encryption is turned on before MITM
detection occurs so you're vulnerable for at least one message, but at least
it massively constrains the attack surface from "any message" to "one fixed
message during the handshake").

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 18:03:29 +1200

der Mouse <[email-masked]> writes:

>That wasn't my experience as an implementor.  Perhaps you're trying to (ab)
>use cryptosystem interfaces not designed for that style of use?

No, just doing it properly.

>I would suggest creating new packet type for negotiating options like this.
>As a strawman:
>

Actually that would have been my preference as well, at the moment SSH has no
facility for interoperable extensibility beyond defining entire new message
types via (presumably) standards-track RFCs.  Having an extension mechanism
like TLS would greatly assist in introducing new features, or enhancing
existing ones.

>option.

Ugh, I would restrict this to specific places, e.g. right after the KEXINIT
and and couple of other well-defined redezvous points, not at any time.  If
you allow either side to set protocol behaviour-changing options at any point
you're going to end up with a huge interop headache.

>[Multi-page description of incredibly complex negotiation snipped]

Again, this is never going to work if you expect different implementations to
interoperate cleanly.  What's wrong with "if both sides send 'cleartext-
packet-lengths' then you continue with unencrypted lengths, otherwise you
don't"?

Peter.

---

From: Damien Miller <[email-masked]>
Date: Thu, 9 Apr 2009 16:33:44 +1000 (EST)

> mentioned previously :-).

I think it would be much safer to define new cipher names for this.

-d

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 02:16:34 -0400 (EDT)

>> definitions may impose additional restrictions for packets naming
>> that option.
> Ugh, I would restrict this to specific places, e.g. right after the
> KEXINIT and and couple of other well-defined redezvous points, not at
> any time.  If you allow either side to set protocol
> behaviour-changing options at any point you're going to end up with a
> huge interop headache.

That was my first thought, to restrict it to (for this case) use during
kex.  I was unable to come up with a way to do that that I was sure
didn't have nasty races or deadlocks - especially since the number of
packets required for kex is variable.

Anyway, SSH_MSG_OPTION as I defined it is not restricted to things
suitable for use during kex.  But if you have an option that you want
to negotiate there, you can define it to be an error at any other time.

>> I propose the option name "cleartext-packet-lengths".  [...]
> Again, this is never going to work if you expect different
> implementations to interoperate cleanly.  What's wrong with "if both
> sides send 'cleartext-packet-lengths' then you continue with
> unencrypted lengths, otherwise you don't"?

First, it rqeuires that it be done in both directions or neither, which
is very un-ssh.  Everything else about the connection (encryption, MAC,
etc) is negotiated separately in each direction.

Second, it doesn't define the point at which these messages are sent,
nor the point at which unencrypted packet lengths come into use.  That
can't work.

Third, if one side tries to turn it on and the other doesn't, the
connection is left in an uncertain half-done state, where the other
side may finally mention it and clarify everything, but what happens if
that never happens?

If you have something better to suggest, go ahead.  Just make sure it's
precise enough to implement; most of the verbiage that put you off was
precision and error handling, not the core of the spec.  I was just
scribbling something down; it's possible, even likely, it could be done
much better.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Damien Miller <[email-masked]>
Date: Thu, 9 Apr 2009 16:50:50 +1000 (EST)

>       byte         SSH_MSG_OPTION (value = 7)

I think any option that changes the binary packet format would need
to be included in the kex hash to prevent downgrade/upgrade attacks.
This is somewhat annoying implementation-wise if it is a separate packet.

-d

---

From: [email-masked] (Niels Möller)
Date: Thu, 09 Apr 2009 09:22:27 +0200

> independently-keyed cipher, but I doubt that it is worth it.

Actually, I think that's clever! It's natural to use somewhat
different mechanisms for data that's fixed size, and data that is of
variable size.

The length field must still be properly autenticted together with the
data, but maybe that is done implicitly with AEAD?

/Niels

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 9 Apr 2009 12:01:05 +0300

> That probably means that we can't use that field.

Not sure about the Secure shell implementations, but on the IKEv1
implementations I have seen that security people have usually not been
very liberal what they accept unless that is explicitly spelled out in
the RFC, i.e. I would expect there are implementations which will fail
negotiation if the reserved field is not zero (yes, those could be
considered as broken implementations).

Another possibility to negotiate this per cipher is to encode it as
part of the cipher name, i.e. define in this AES-GCM document (or make
it separate document, so other AEAD ciphers can refer it independently
to the AES-GCM) that if the cipher name for example starts with "*"
(ASCII-character 052, 42, 0x2a) then cipher uses clear text length
field.

In that case implementations can either just check the name
completely, i.e. know that "*aead-aes-128-gcm" and "*aead-aes-256-gcm"
ciphes use this format, or they can simply see that if first character
of the cipher is "*" then it uses this new format and check if the
rest of the cipher name is valid, and use that as real cipher. That
would allow implementations ability to propose cipher lists like
"aes256-cbc,*aes256-cbc,*aead-aes-256-gcm" if needed.

The question is do people really want to use old ciphers also with
clear text length field?

If so then this would allow easy configuration to support those for
even old implementations with minimal changes, and backward
compatibility with old versions (I do not think we can find a secure
shell implementation which breaks when it sees unknown cipher name in
cipher lists).

Anyways if we go to the clear text packet length, the security
considerations section of the document describing it needs to give
more information, as RFC4251 (SSH-Arch) does not cover that case.
-- 
[email-masked]

---

From: [email-masked] (Niels Möller)
Date: Thu, 09 Apr 2009 09:14:21 +0200

> security implications for ssh itself?

I don't think so.

> advantage of the encrypted packet length?

My gut feeling is that it's a good thing to be able to hide message
boundaries. I do my best to take advantage of this, and try to stick
to one or a few fix sizes of TCP segments, with the boundaries between
TCP-segments typically in the middle of the payload of an
SSH_MSG_IGNORE message.

> to migrating existing implementations?

Supporting two different modes for the transport protocol of course
iplies some additional complexity.

My experience with handling of encrypted length fields is that it's
not very complicated, it's about the same complexity or less as the
handling of padding.

I admit that I haven't done any deep thinking of attacks based on
partial decryption. We're comparing these two processes:

1. Read first block, decrypt, get length field, read rest of message
   (if larger than one block) and mac, decrypt, check MAC. (It's of
   course imperative to not act on anything in the message beyond the
   length field until the mac is properly verified)

2. Get unencrypted length field, get rest of message, decrypt, check
   MAC.

In the first scenario, the attacker could mount the following attack:
Send a first chosen ciphertext block, then slowly send more data. Then
the attacker can then find out what the first four bytes of the
decrypted block are, by obserrving how much data it can send before
the ssh implementation in the othher end disconnects. Actually, with
high probability, it will disconnect immediately, because a length
field exceeding the maximum size is a protocol error; at least that's
how my implementation behave. So the setup is somewhat liek on oracle
telling thhe attacker whether or not the first two bytes of the
decrypted block are zero.

But since (1) this is an attack only on the session key, and (2) it
can be mounted only once per connection, I doubt the attacker can
derive any useful information (useful would meen: Sufficient to get a
little information about cleartext previously sent over the same
session). And any decent block-cipher should have reasonable resistant
also to a general chosen-ciphertext attack, right?

Are there any other relevant attacks? Anything that's specific to AEAD
(which I'm not familiar with)?

Regards,
/Niels

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 22:37:57 +1200

Damien Miller <[email-masked]> writes:

>I think any option that changes the binary packet format would need to be
>included in the kex hash to prevent downgrade/upgrade attacks. This is
>somewhat annoying implementation-wise if it is a separate packet.

Is there any way of doing some sort of pre-auth to prevent tampering with the
options packets?  A problem with the rather late handling of MITM detection is
that if you negotiate more secure options via SSH_MSG_OPTION and a MITM
subjects you to a downgrade attack then by the time you've detected the MITM
it's too late.

What I mean here is that let's say there's some attack on step N of the
protocol, either the protocol itself or the complexity of the implementation
of certain steps.  So you send an SSH_MSG_OPTION telling the peer to switch to
a limited-attack-surface version of the handshake, with the exchange being:

Step 1: KEYEX
Step 2: OPTION
...
Step N: Vulnerable part
...
Step M: Detection of manipulation by MITM

Since a MITM can remove the OPTION message, they leave you vulnerable at step
N because you can't detect the modification until step M.

I can think of a pile of Rube Goldberg hacks for this, but I'm wondering if
there's a clean way to handle it.

Peter.

---

From: Damien Miller <[email-masked]>
Date: Thu, 9 Apr 2009 20:44:35 +1000 (EST)

On Thu, 9 Apr 2009, Peter Gutmann wrote:

> Since a MITM can remove the OPTION message, they leave you vulnerable
> at step N because you can't detect the modification until step M.

A post-KEX OPTION packet could work* and I don't think it could be
trivially elided by an on-path attacker - the MAC takes in the sequence
number, which would be off unless the attacker had some way of replacing
the packet (implying a total protocol break) and it would also desynchronise
any cipher state.

* except that it won't - OpenSSH just had to switch off a few channel and
global extensions for all but other OpenSSH peers because some other
implementations will disconnect as soon as they see an extension message
that they do not recognise. So we really are quite constrained in how we
can practically extend the protocol.

> there's a clean way to handle it.

Represent binary packet protocol changes though new cipher names.

-d

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 09 Apr 2009 22:52:33 +1200

[email-masked] (Niels =?iso-8859-1?Q?M=F6ller?=) writes:

>I admit that I haven't done any deep thinking of attacks based on partial
>decryption.

I have, and if you want to do it properly it makes the header read incredibly
complicated.  I've just had a look and it's about 700 lines of code to safely
process the packet header with appropriate checking and whatnot, with a lot of
awkward length-checking and data handling.  For TLS it's maybe 150 lines of
quite straightforward code (read length, check validity, read data, decrypt).
I'm still not sure I trust the equivalent SSH code, despite spending way more
time on it than the TLS code, because of its complexity.

>Are there any other relevant attacks?

I wouldn't even bother looking for a crypto weakness, I'd exploit the
complexity of the code required to handle this and look for overflows, off-by-
one errors, bounds checking, all the usual stuff.  For that the answer is
"yes, many", although it'd depend on the implementation you're going after.

Peter.

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 14:38:14 -0400 (EDT)

> I agree.  I see no reason to deviate from using alg names for this
> sort of negotiation.

For this particular case?

If you're proposing to use it with all, or even a large subset of,
existing ciphers, I do: it avoids the cross-product problem.  One
option like this doubles the number of ciphers offered  Each additional
such binary option doubles the list size again, and an option with more
than two settings multiplies it more; pretty soon you're up to offering
dozens of names for each cipher supported.  THe cross product problem
is bad enough already with things like operating modes (_cbc, _ctr) and
key sizes (aes{128,192,256}_*).

If you're proposing it as a particular encryption algorithm which
happens to "encrypt" the length trivially, I agree, it should be just
another encryption algorithm as far as the protocol goes.

In general?  I disagree.  There are many things which could reasonably
be negotiated as options using a mechanism like this, and they don't
all make sense as GLOBAL_REQUESTs.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 9 Apr 2009 12:49:20 -0500

> This is somewhat annoying implementation-wise if it is a separate packet.

I agree.  I see no reason to deviate from using alg names for this sort
of negotiation.

---

From: [email-masked] (Niels Möller)
Date: Thu, 09 Apr 2009 13:59:30 +0200

Peter Gutmann <[email-masked]> writes:

> complicated.

What I do is basically that I check that the length doesn't exceed the
maximum message size, and that the padding length abides the rules in
the spec (these checks examine the first 5 bytes of the decrypted
first block). I'd do the same checks if length and/or padding were
unencrypted. Besides this, nothing interesting is done to the packet
data until the complete packet is read.

If this is not the "proper" way of doing it, I'd appreciate a hint of
what other checks are needed and why. I may well be missing something.

> I've just had a look and it's about 700 lines of code to safely
> awkward length-checking and data handling.

I simply don't get this. I'm now looking at the corresponding
functions in (the development version of) lsh. There's one function
that handles the reading of transport packets, including processing of
the message header in the first block, and it is 165 lines (including
some i/o and some debugging code), and a second function that applies
the current crypto, mac and decompression algorithms to a complete
packet, which is 64 lines more. Code in question is the functions
decode_packet and transport_read_packet in
http://cvs.lysator.liu.se/viewcvs/viewcvs.cgi/*checkout*/lsh/src/transport_read.c?content-type=text%2Fplain&root=lsh

Sure, there's some extra book-keeping for handling the first block,
but I don't understand how that could amount to many hundreds of lines
of code.

Regards,
/Niels

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 12:22:22 -0400 (EDT)

>> * except that it won't - OpenSSH just had to switch off a few
>> channel and global extensions for all but other OpenSSH peers
>> because some other implementations will disconnect as soon as they
>> see an extension message that they do not recognise.

> This is really unfortunate, given that RFC4253 is quite clear on how
> unrecognized extensions must be handled.  I would propose that we
> solve this problem once and for all by using a _single_ "magic"
> cipher name, or possibly a magic cookie in the version banner
> comments, to indicate that unrecognized messages are handled
> correctly and/or that option negotiation is supported.

That's a good one, right up there with RFC 3514.

(For those who don't get Jeff's humour: what's to prevent buggy
implementations of the "yes I get this right" claim?)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 12:01:06 -0400 (EDT)

> With regard to the negotiation itself, I think it might be cleaner to
> have three separate messages: [...]

That would work too.  I was trying to conserve (scarce) message number
space by using a single message number with the distinction conveyed by
your three messages being part of the option negotiation, but this
looks sufficiently general it'd be OK too.  (And options which really
need more elaborate negotiation can always make REQUEST and REPLY
rubber-stamps and do the real work with DATA.)

One thing is not clear from this: is option support negotiated
separately in each direction?  If not, what happens if two REQUEST
packets for the same option, one in each direction, cross in flight?
(It seems to me most ssh-like to negotiate separately in each
direction.  This means two packets each way instead of one, but they
are streamable packets, so I don't see that as a big deal.)

Oh, the spec also needs to define what SSH_MSG_UNIMPLEMENTED means in
response to these.  Presumably this counts as a nak reply when in
response to _REQUEST and a protocol error for the other two, but it
needs to be stated.

> In the case of the cleartext-packet-lengths option, the option data
> in the _REQUEST must be empty, and any implemention supporting the
> option MUST respond to the _REQUEST with an ack; that is, the nak
> response may not be sent for this option.  [...] The side sending the
> _REPLY message may begin using cleartext lengths immediately by
> including option data of "on" in the _REPLY packet.

This makes it sound as though you're assuming option support is not
negotiated separately in each direction.

> Once the option has been negotiated, either side may switch between
> sending cleartext and encrypted lengths whenever it wants, by sending
> SSH_MSG_OPTION_DATA with option "cleartext-packet-lengths" and data
> "on" to indicate lengths will be cleartext starting with the next
> packet, or "off" to indicate they will be encrypted (when encryption
> is in effect).

> I think this is cleaner than the approach der Mouse suggested,

Yes, I think I agree.  It's certainly simpler; since I think it's also
sufficient for the task, that makes it cleaner. :)

> because it allows either side to switch modes at any time and makes
> it clear what the new mode will be on every switch.  It does this at
> the expense of eliminating the ability of the peer to accept or
> reject any mode change, instead requiring that once the option has
> been negotiated, each peer be willing to accept either encrypted or
> unencrypted lengths at any time (though an encryption algorithm may
> require the option be enabled).

What happens if such an encryption algorithm is in use and the
implementation receives a _DATA/"off" packet?  (Yes, it would be a
strange thing for an implementation to send, but I think it needs to be
addressed, even if only with a "this is a protocol error from which no
recovery is specified" remark in the encryption algorithm definition.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 11:38:39 -0400 (EDT)

>> Also, I just reread section 6 of 4253, and I can't find anything
>> that says the ciphertext from an encryption algorithm has to be the
>> same size as the plaintext, so you could always just save the
>> length, replace it with four random bytes, encrypt as normal, and
>> prepend the saved length.  (Decryption, of course, just throws away
>> the four random bytes.)
> I think what you're effectively suggesting here is that the transport
> layer pad to the "wrong" size (since the length is included but will
> not be encrypted), and then the encryption algorithm add extra
> "hidden" padding to pad it to the right length.

Yes, I think that's a fair rephrasing of my suggestion.

> I think that could work, but note that the number of bytes of
> ciphertext must be exactly equal to four plus the "decrypted" length
> value, since the latter is the only indication of how many bytes the
> transport layer should read out of the TCP stream.

Putting it that way reveals, perhaps, part of the problem.  There is no
particular reason why the code that reads data from the wire data
stream (usually but not necessarily TCP) has to know where packet
boundaries are.  As long as every packet boundary falls at a place such
that the data->encryption->decryption->data pipeline can deliver the
whole packet without needing more input data (which is the point of
padding to a multiple of the blocksize), the protocol can work.  This
does mean that implementations which expect to issue wire data stream
reads for exactly the right amount of data early in packet processing
will be constrained in what encryption algorithms they implement,
though as far as I know no algorithms which would make that a practical
constraint are implemented for ssh (and my suggestion above is not one,
since the encryption algorithm layer can provide the wire length early).

At the very worst, implementations may need internal rework if they
want to implement the new stuff.

> There are likely implementations which expect the "decrypted" length
> to also be the length of the plaintext packet (not counting the
> packet_length and mac), which would have to change.

> OTOH, I would expect support for AEAD-mode ciphers to make it
> necessary for the plaintext and ciphertext to be different sizes
> anyway, so this shouldn't be a major change.

Yes, there are doubtless implementations which assume that encrypted
and cleartext are the same size.  They will need internal rework if
they are to implement any of this stuff, but I don't see that as a
reason to twist the design uncomfortably; it just means implementing it
for them, if done at all, will be more work.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 10:54:36 -0400 (EDT)

>> partial decryption.
> I have, and if you want to do it properly it makes the header read
> incredibly complicated.  I've just had a look and it's about 700
> lines of code to safely process the packet header with appropriate
> checking and whatnot, with a lot of awkward length-checking and data
> handling.  For TLS it's maybe 150 lines of quite straightforward code
> (read length, check validity, read data, decrypt).

Oddly enough, "read length, check validity, read data" is what moussh's
packet length handling looks like.  Perhaps the code you were reading
was so Byzantine because it was using an encryption interface that was
not well suited to the task?

My code for decrypting, reading packet length, checking, handling
compression and MAC, and passing off to the protocol stack, is about
131 lines[%].  It calls out to the encryption and compression
implementations, but the lower layers it calls are completely blind to
the binary packet format; they don't know anything about ssh's "length,
padding length, payload, padding, MAC" packet structure, so I don't
consider it unreasonable to not include their line count.  (Actually, I
get close to 700 lines if I _do_ include the next layer down - the
encryption algorithm glue layer runs from 94 (IDEA) to 265 (Rinjdael)
lines, and the zlib glue layer is 364 lines.)

[%] Lines 127 to 258 of
    ftp.rodents-montreal.org:/mouseware/local-src/moussh/moussh-20090319/bpp.c
    are the code in question.

> complexity of the code required to handle this and look for
> overflows, off-by-one errors, bounds checking, all the usual stuff.
> For that the answer is "yes, many", although it'd depend on the
> implementation you're going after.

Certainly.  But if the code is really 700 lines, either a lot of
unrelated stuff is getting caught up in the line count or someone is
doing something very wrong.  It does not need to be that elaborate.

Not that I claim my code is perfect - if you do happen to notice any
mistakes in it, I'd be interested to hear, of course.  But runs and
interoperates with other implementations, so I can't have left out any
really major pieces.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 10:33:52 -0400 (EDT)

> Is there any way of doing some sort of pre-auth to prevent tampering
> with the options packets?

You could simply decree that options packets for the option in question
are not acceptable if sent before the first kex completes.  (I'd
hesitate to do that for all options packets, but it may be necessary.)

> A problem with the rather late handling of MITM detection is that if
> you negotiate more secure options via SSH_MSG_OPTION and a MITM
> subjects you to a downgrade attack then by the time you've detected
> the MITM it's too late.

Too late for what?  You need to be careful to send nothing important
until after MitM detection, but if you are then what's the risk?

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 10:38:04 -0400 (EDT)

> A post-KEX OPTION packet could work* [...]

> * except that it won't - OpenSSH just had to switch off a few channel
> and global extensions for all but other OpenSSH peers because some
> other implementations will disconnect as soon as they see an
> extension message that they do not recognise.

OpenSSH didn't _have_ to.  It _chose_ to.  Broken implementations are
broken; if they can't be bothered to correctly respond to well-defined
and conformant protocol they don't happen to implement, that's their
problem.  If OpenSSH really wants to bend over backwards to avoid
showing up bugs in buggy implementations, surely the right way to do it
is by detecting the buggy ones and working around them, rather than
assuming everyone but themselves is buggy.

If I create and release an implementation that ungracefully disconnects
when offered anything but 3des-cbc as a cipher, will they then stop
offering everything else unless talking to themselves?  One that
crashes when offered a username containing a 'q', will they then reject
attempts to use such usernames?  They're basically the same thing, just
a little (first one) or a lot (second one) more extreme.  You can't
paper over everyone else's bugs, and trying only encourages the bugs to
persist.

> So we really are quite constrained in how we can practically extend
> the protocol.

Only if you really do believe in breaking interoperability with
non-broken implementations for the sake of interoperability with broken
implementations.  I don't.

I ran into an implementation apparently too broken to handle some one
of the extensions moussh uses (I don't know which extension - it was
the embedded ssh server on a switch, and the tradeoffs were wrong for
trying to probe the envelope of the bug).  But what I did was to
suppress all use of DNS-based extension names when given a command-line
flag saying to do so, not to do so by default!

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Joseph Galbraith <[email-masked]>
Date: Thu, 09 Apr 2009 13:50:57 -0600

>   3. Reformat the hard drive.

And as for our implementation, it will ASSERT() for debug
builds (which we don't ship so it isn't a big deal) and
ignore the value in release builds.

Thanks,

Joseph

---

From: "Timo J. Rinne" <[email-masked]>
Date: Thu, 09 Apr 2009 20:20:32 +0300

> I think it would be much safer to define new cipher names for this.

I agree.  I think that most straightforward idea would be to allocate 
cipher names to selected gcm ciphers so that if such cipher gets 
selected, it will have side-effects to packet format that will be in 
effect after the subsequent NEWKEYS packet.

I don't support an idea to add some kind of "*" magic in order to offer 
gcm functionality over the existing algorithms (proposed by Kivinen).

I also think that using an independent cipher to encrypt packet lengths 
is not worth impelemting.  Replacing cipher+mac with gcmcipher+cipher is 
just not worth it.

Actualy quite a few problems have arisen earlier from the fact that 
SecSh has encrypted packet length fields (which TLS doesn't have). 
However simply omitting packet length encryption would also require very 
careful consideration, because of various potential authentication 
related issues (password length snooping etc.).

I will think about this in more detail next week and try to think some 
way around the obvious caveats.

-- 
Timo J. Rinne <[email-masked]>        Valimotie 17       +358 20 500 7000 T
Chief Technology Officer           FIN-00380 Helsinki +358 20 500 7397 F
SSH Communications Security Corp.  Finland            http://www.ssh.com

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Apr 2009 20:47:08 -0400 (EDT)

> How about a quick straw poll, since we've probably got a good number
> of implemeters here.  If your implementation sees a non-zero value in
> the RFU field, will it:

Ignore it.  (I've been considering warning and disconnecting as other
possible reactions, but haven't seen any compelling reason to prefer
one over another.  Perhaps it's time for another configuration
parameter - a little difficult to test, though.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 09 Apr 2009 11:14:27 -0400

> so lines into page 8 would do with a cipher using 7-byte blocks.)

I read that paragraph as normative, and having the effect that SSH cannot 
operate with ciphers having a block size of 3, 5, 6, or 7 bytes.  If you 
really wanted to use such a cipher, the document describing its use with 
SSH would have to artificially increase the "block size" to something 
larger than 8 bytes.

> for the encryption engine.

OK, I'll grant that it's not necessary when using a stream cipher, or a 
block cipher with a block size of 1, 2, or 4 bytes.  But I don't think 
there are any of the latter.

> course, just throws away the four random bytes.)

I think what you're effectively suggesting here is that the transport layer 
pad to the "wrong" size (since the length is included but will not be 
encrypted), and then the encryption algorithm add extra "hidden" padding to 
pad it to the right length.

I think that could work, but note that the number of bytes of ciphertext 
must be exactly equal to four plus the "decrypted" length value, since the 
latter is the only indication of how many bytes the transport layer should 
read out of the TCP stream.  There are likely implementations which expect 
the "decrypted" length to also be the length of the plaintext packet (not 
counting the packet_length and mac), which would have to change.

OTOH, I would expect support for AEAD-mode ciphers to make it necessary for 
the plaintext and ciphertext to be different sizes anyway, so this 
shouldn't be a major change.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 09 Apr 2009 11:42:55 -0400

--On Thursday, April 09, 2009 06:03:29 PM +1200 Peter Gutmann 
<[email-masked]> wrote:

> KEXINIT and and couple of other well-defined redezvous points, not at any
> time.  If you allow either side to set protocol behaviour-changing
> options at any point you're going to end up with a huge interop headache.

No, I think the right thing is for the SSH_MSG_OPTION message itself to be 
permitted at any time, and leave it to the definitions of individual 
options to specify when an option may be negotiated and when the results of 
that negotiation take effect.

FWIW, while there's nothing wrong protocol-wise with negotiating the 
cleartext-packet-lengths option immediately after KEXINIT, I think it's 
cleaner (and probably easier for some implementations) to do it just 
_before_ KEXINIT.  After all, you probably don't want to renegotiate the 
option every time a new key exchange happens, but it does have to be 
negotiated before NEWKEYS, since some encryption algorithms will only work 
with plaintext lengths.

With regard to the negotiation itself, I think it might be cleaner to have 
three separate messages:

	byte		SSH_MSG_OPTION_REQUEST (value = 7)
	string		option name
	...		option-specific data

	byte		SSH_MSG_OPTION_REPLY (value = 8)
	string		option name
	string 		response
	...		option-specific data

	byte		SSH_MSG_OPTION_DATA (value = 9)
	string		option name
	...		option-specific data

_REQUEST is used to request support for an option, with optional 
option-specific data.

_REPLY is sent in response to _REQUEST; it identifies the option in 
question and gives one of the following responses:

"ack" - The option is supported and has now been successfully negotiated. 
Its features may be used immeiately, by the sender of the _REPLY starting 
with its next packet, and by the receiver of the _REPLY as soon as it has 
seen the ack.  Note that an option like cleartext-packet-lengths makes a 
non-self-describing change to the packet format and so will still require 
an indicator.

"nak" - The option is supported but negotiation failed, presumably because 
option-specific parameters proposed by the requestor are not acceptable. 
The option-specific data may carry information that would help a later 
attempt succeed.

"unimplemented" - The option is unrecognized or not supported.

Once an option has been successfully negotiated (i.e. _REPLY with ack), 
additional option-specific data may be sent in either direction according 
to the _DATA message; this is basically a mechanism to allow options to 
define new packet types without allocating message numbers.

The above may still be slightly too complex, but I'm not sure how to 
simplify it without losing too much generality.  Suggestions welcome.

In the case of the cleartext-packet-lengths option, the option data in the 
_REQUEST must be empty, and any implemention supporting the option MUST 
respond to the _REQUEST with an ack; that is, the nak response may not be 
sent for this option.  Once the option has been negotiated, either side may 
switch between sending cleartext and encrypted lengths whenever it wants, 
by sending SSH_MSG_OPTION_DATA with option "cleartext-packet-lengths" and 
data "on" to indicate lengths will be cleartext starting with the next 
packet, or "off" to indicate they will be encrypted (when encryption is in 
effect).  The side sending the _REPLY message may begin using cleartext 
lengths immediately by including option data of "on" in the _REPLY packet.

I think this is cleaner than the approach der Mouse suggested, because it 
allows either side to switch modes at any time and makes it clear what the 
new mode will be on every switch.  It does this at the expense of 
eliminating the ability of the peer to accept or reject any mode change, 
instead requiring that once the option has been negotiated, each peer be 
willing to accept either encrypted or unencrypted lengths at any time 
(though an encryption algorithm may require the option be enabled).  It 
does still allow cleartext lengths to be negotiated separately in each 
direction, which I think is appropriate given that SSH requires negotiation 
of encryption algorithms separately in each direction.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 09 Apr 2009 11:47:55 -0400

--On Thursday, April 09, 2009 08:44:35 PM +1000 Damien Miller 
<[email-masked]> wrote:

>> protocol, either the protocol itself or the complexity of the
>> implementation of certain steps.  So you send an SSH_MSG_OPTION telling
>> the peer to switch to a limited-attack-surface version of the handshake,
>> with the exchange being:
>>
>> Step 1: KEYEX
>> Step 2: OPTION
>> ...
>> Step N: Vulnerable part
>> ...
> the packet (implying a total protocol break) and it would also
> desynchronise any cipher state.
>

This is really unfortunate, given that RFC4253 is quite clear on how 
unrecognized extensions must be handled.  I would propose that we solve 
this problem once and for all by using a _single_ "magic" cipher name, or 
possibly a magic cookie in the version banner comments, to indicate that 
unrecognized messages are handled correctly and/or that option negotiation 
is supported.  I'm wary of using separate cipher names to negotiate every 
possible extension, because it has the potential to cause an explosion of 
cipher names and the length of the lists in the KEXINIT message is limited.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 09 Apr 2009 09:12:09 -0400

--On Wednesday, April 08, 2009 10:57:49 PM -0500 Nicolas Williams 
<[email-masked]> wrote:

>> > [So far the only extensibility mechanisms that we have at that point
>> > in the protocol are: new protocol version number (not going to happen)
>> > and magic algorithm names (which have been used successfully).]
>>
>> ... and the completely unused 32-bit flags field in the first message,
>> which I mentioned previously :-).
>
> This:
>

I admit we haven't left ourself much room for pre-keyex negotiation, but 
there is some.  In addition to the bits already mentioned, we can use magic 
token in the "comments" field of the version banner, and there are also 
several unused messages in both the transport-generic and 
algorithm-negotiation layers, which implementations are REQUIRED to ignore 
except for sending an SSH_MSG_UNIMPLEMENTED (see RFC4253 11.4)

-- Jeff

---

From: Joseph Galbraith <[email-masked]>
Date: Thu, 09 Apr 2009 13:49:24 -0600

>   3. Reformat the hard drive.
Last time we discussed this (extending the transport layer)
I'm pretty sure we had one implementor claiming that for
'paranoia', they were checking that the value was zero.

Can't remember who though.

Thanks,

Joseph

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 09 Apr 2009 22:14:42 -0400

> are streamable packets, so I don't see that as a big deal.)

Good question.  I was thinking originally in terms of an option either 
being supported or not, separately from the question of whether any of its 
optional effects are enabled.  An option being supported might mean 
something like "we can use cleartext lengths", with actually _doing_ so 
turned on separately for each direction, or "new packet type XXX is 
supported", with any interesting effects resulting from actually using the 
new packet type.  In which case, it doesn't need to be negotiated 
separately for each direction, and REQUESTS crossing in flight are harmless.

Of course, adding option-specific data in the REQUEST/REPLY messages 
complicates that, since the point of doing so is to allow negotiation of 
option parameters, and depending on the option that probably wants to be 
done separately for each direction.

> response to _REQUEST and a protocol error for the other two, but it

In response to _REQUEST, it means the same as an "unimplemented" _REPLY, 
but with the additional connotation that the requestor need not bother 
sending any further _REQUEST messages for any option.  Or, we could just 
declare it a protocol error in all three cases, on the grounds that we know 
things don't handle unimplemented messages correctly and thus we have to 
negotiate the presence of option negotiation. :-(

> negotiated separately in each direction.

Yes, that's what I'm assuming.  If you negotiate it separately for each 
direction, then only one side gains the ability to turn it on (either the 
sender of the REQUEST or of the REPLY, depending on whether the REQUEST 
means "I want to send cleartext lengths" or "I want you to send me 
cleartext lengths", and the reverse direction requires completing the 
negotiation in that direction.

> recovery is specified" remark in the encryption algorithm definition.)

I think it should be an error to advertise such an algorithm if the option 
has not already been negotiated.  Once the option has been negotiated, we 
can either make it an error for it to be off while such an algorithm is in 
use, or specify that negotiating such an algorithm automatically turns it 
on and silently prevents it being turned off, or that when such an 
algorithm is in use cleartext lengths are always sent even when the option 
is in the "off" state.  The advantage of the last is that when rekeying, 
one can select a new algorithm that does not require the option, turn the 
option off, and have the result be that the first message with an encrypted 
length is the first one after the NEWKEYS message.  Alternately, we could 
simply allow a "delayed-on" or "delayed-off" whose effect takes place with 
the first message after the next NEWKEYS, rather than immediately.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 09 Apr 2009 22:17:22 -0400

> hesitate to do that for all options packets, but it may be necessary.)

The problem with doing it for all option packets is that doing so precludes 
negotiating cleartext-packet-lengths before the first kex completes, which 
is necessary if the first kex selects an encryption algorithm requiring 
cleartext packet lengths.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 09 Apr 2009 22:27:38 -0400

> since the encryption algorithm layer can provide the wire length early).

Hm.  Yes, that's true.  And it's even a good idea; the recent problems with 
encrypted packet lengths would be much less serious if reading and 
decrypting the TCP stream were decoupled from processing the SSH packet 
stream.  Of course, that introduces some interesting buffering requirements 
to allow a NEWKEYS message to result in a pipeline flush, but it shouldn't 
be unreasonable.

Hrm, except the MAC is unencrypted, so they can't be completely decoupled. 
That doesn't make it unworkable, though, provided one defines an 
appropriate interface to the encryption code.

> for them, if done at all, will be more work.

Yes, that's probably true.

Interestingly, if we can agree that using plaintext lengths does _not_ 
require changing the way the size of the padding field is determined, then 
it becomes possible for an encryption algorithm to use plaintext lengths 
without changing the base protocol, the modularity argument goes away, and 
the need to enable negotiation of cleartext lengths independently of the 
encryption algorithm becomes less pressing (but possibly still desirable). 
It does mean that if we do both, we need to point out that implementations 
which support both such an algorithm and algorithm-independnet cleartext 
lengths not inadvertently send both the length and the _next_ 4 bytes in 
plaintext. :-)

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 9 Apr 2009 11:04:47 -0500

> I think it would be much safer to define new cipher names for this.

I agree.  That or magic alg names (e.g.,
"all-ciphers-have-plaintext-packet-length").

The reserved uint32 will be, at the very least, difficult to use.

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 9 Apr 2009 23:31:05 -0500

> parameter - a little difficult to test, though.)

Given that key exchange is not retriable I think the best thing to do is
to ignore this field and always place a zero there until we define its
meaning.  That will allow us to use it to negotiate new features when
both the client and server advertise them (non-zero values).

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 9 Apr 2009 23:17:08 -0500

On Thu, Apr 09, 2009 at 11:42:55AM -0400, Jeffrey Hutzelman wrote:
> [...]

Surely you jest.  Why get so complicated when the much simpler
negotiation through alg names will do?  What value is there in this
complication?

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 10 Apr 2009 00:58:56 -0400

--On Thursday, April 09, 2009 11:17:08 PM -0500 Nicolas Williams 
<[email-masked]> wrote:

>> No, I think the right thing is for the SSH_MSG_OPTION message itself to
>> be  permitted at any time, and leave it to the definitions of individual
>> options to specify when an option may be negotiated and when the results
>> of  that negotiation take effect.
>>
>> [...]
>>
>> have  three separate messages:
>

- generality
- allowing the feature to be negotiated for any algorithm, not just
  a particular gcm algorithm, without a cross product explosion

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 10 Apr 2009 01:26:42 -0400

--On Friday, April 10, 2009 12:03:31 AM -0500 Nicolas Williams 
<[email-masked]> wrote:

> On Fri, Apr 10, 2009 at 12:02:35AM -0500, Nicolas Williams wrote:
>> On Fri, Apr 10, 2009 at 12:58:56AM -0400, Jeffrey Hutzelman wrote:
>> > - generality
>> I'd rather have a magic alg name that does this.  It's less code, a lot
>> less code.  We don't need no stinking generality here :) given that we
>> weren't given it to begin with :)
>>
>> BTW, I would love to use the reserved field of KEXINIT to negotiate
>> retriable key exchagne (a big deal for gss keyex).
>
> Sent to soon.  I meant to add that your scheme isn't general enough to
> give us retriable kexinit...

Why not?

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 10 Apr 2009 00:02:35 -0500

Nico
--

---

From: der Mouse <[email-masked]>
Date: Fri, 10 Apr 2009 01:48:01 -0400 (EDT)

> Given that key exchange is not retriable I think the best thing to do
> is to ignore [the currently-0 last field of SSH_MSG_KEXNIIT] and
> always place a zero there until we define its meaning.  That will
> allow us to use it to negotiate new features when both the client and
> server advertise them (non-zero values).

Not without breaking interoperability with existing implementations
that check that the field is zero.

Or do you maintain that there are no such?  Or that interoperability
with them doesn't matter?  I find the latter severely busted and the
former unlikely, especially since the spec does not even suggest, much
less specify, behaviour for an implementation which encounters a value
for that field that it doesn't understand.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Fri, 10 Apr 2009 01:57:37 -0400 (EDT)

> I'd rather have a magic alg name that does this.  It's less code, a
> lot less code.

That's not the only metric that matters.

> We don't need no stinking generality here :) given that we weren't
> given it to begin with :)

That's why we're trying to design a clean mechanism that provides it,
rather than throwing in a kludge for this case, another kludge for next
case, and pretty soon you're shoehorning protocol version numbers into
the authentication username string or some such horror.

> retriable key exchagne (a big deal for gss keyex).

Why?  Why not just have the gss kex define its kex-method-specific
messages so as to permit multiple back-and-forths, retrying as much as
necessary to find something suitable?

Actually, perhaps the best way to answer that would be to sketch the
semantics for the retryable-kex bit you'd like to define; then I could
probably see what the issue is (or suggest a way that doesn't break
interoperability that badly, using existing facilities).

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 10 Apr 2009 00:03:31 -0500

---

From: der Mouse <[email-masked]>
Date: Fri, 10 Apr 2009 02:16:20 -0400 (EDT)

>> [...decoupling wire data reads from decryption...]
> Of course, that introduces some interesting buffering requirements to
> allow a NEWKEYS message to result in a pipeline flush, but it
> shouldn't be unreasonable.

Or, rather, a pipeline back-up-and-reprocess. :-/

> Hrm, except the MAC is unencrypted, so they can't be completely

That's true.  Hm, I wonder how I dealt with that in moussh; when I read
the packet reading code for an upthread message, they sure looked
pretty decoupled.

*rummage*  *read*

Ah.  My downcall to the cryptosystem implementation has semantics that
amount to "here's a buffer of input ciphertext, a ciphertext amount, a
buffer for cleartext, and a maximum amount of cleartext I want; if I'm
providing excess ciphertext, don't consume more than is necessary to
provide all the cleartext I'm asking for", addressing both the MAC
issue and the NEWKEYS issue.

> Interestingly, if we can agree that using plaintext lengths does
> _not_ require changing the way the size of the padding field is
> determined, then it becomes possible for an encryption algorithm to
> use plaintext lengths without changing the base protocol, the
> modularity argument goes away, and the need to enable negotiation of
> cleartext lengths independently of the encryption algorithm becomes
> less pressing (but possibly still desirable).

Agreed on all counts.

> It does mean that if we do both, we need to point out that
> implementations which support both such an algorithm and
> algorithm-independnet cleartext lengths not inadvertently send both
> the length and the _next_ 4 bytes in plaintext. :-)

Right - they may well end up sending the length (in the clear) twice if
they get careless, but I don't see any need to make it impossible to
negotiate wasteful combinations of settings.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: [email-masked] (Niels Möller)
Date: Wed, 15 Apr 2009 10:56:41 +0200

Tim Polk <[email-masked]> writes:

> specification (NIST SP 800-38D).

I have tried to review most of this lengthy discussion, and after some
thinking, my conclusion is that optionally having unencrypted length
fields is a bad idea.

There seem to be two arguments for clear-text lengths:

1. "I never liked the encrypted lengths, I think the TLS protocol
   design is better".

2. It causes additional complexity when implementing AEAD.

I don't find (1) convincing. I'd prefer not to make design changes of
this type at this time, unless there's some really, really good
reason. I'd not be surprised if there are some applications that rely
on the ssh protocol feature that message lengths are encrypted, and
are weakened if we change this. (I'd still appreciate to hear more
details on what security problems others see with encrypted length
fields, though).

I find (2) extremely unconvincing, since the proposed solutions are
additional levels of negotiation which adds a lot more complexity than
it removes. I strongly dislike having several options for how the
transport layer should work, I do *not* want to have that extra
complexity at this level. One of the options will inevitably be less
well-tested and more buggy than the other.

I'd like to propose the following guide-lines for using algorithms in
the AEAD-class with ssh:

1. The algorithm is specified as an encryption algorithm in the
   kexinit message. The mac should be set to "none" (or must? If we
   allow other values, that should mean that some other MAC is used in
   addition to the AEAD, which causes no big problem in principle but
   it seems to be of limited usefulness.

   (There are some details left to specify on exactly how this should
   interact with algorithm selection, since there are additional
   dependencies. You want to be able to ask for (aead, none) with a
   fallback to (3des-cbc, hmac), without risk of ending up with (3des-cbc,
   none). Maybe it's easier to say that if an AEAD-algorithm is chosen
   for encryption, the lists of mac algorithms (for that direction)
   are ignored).

2. The first block of each message is encrypted using a separately
   keyed cipher. For AES-GCM, this could be AES in counter mode. For
   proper authentication, the clear text for this block is included in
   the "associated data" for AEAD, together with the implicit sequence
   number, and any other context data that needs authentication. (A
   slight elaboration of Damien Miller's idea).

   The choice for the cipher for the first block should of course be
   chosen so that it reuses the same primitives as the AEAD-algorithm
   that is used.

3. The rest of the message (as determined by the length and padding
   fields contained in the first block) holds the AEAD ciphertext.

For me, it would probably work just fine to implement AEAD so that I
can get the result for the first block before reading the rest of the
data, but the above construction avoids this requirement on the AEAD
interface, so I suspect some of you will find it cleaner.

The primary objective of this proposal is to keep things simple and
minimalistic. Does it make sense? Am I missing some complication that
must be dealt with?

Regards,
/Niels

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 06:10:50 -0400 (EDT)

>    fallback to (3des-cbc, hmac), without risk of ending up with
>    (3des-cbc, none).

I believe that's not directly possible at present, given the way
algorithm negotiation works.

However, it is fairly easy to offer enc=aead,3des-cbc mac=hmac, and, if
that negotiation succeeds, immediately re-kex with enc=aead mac=none.

>    Maybe it's easier to say that if an AEAD-algorithm is chosen for
>    encryption, the lists of mac algorithms (for that direction) are
>    ignored).

That would be a rather unpleasant violation of the existing definition.
I'd much rather just re-kex if using a none MAC is that important.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: [email-masked] (Niels Möller)
Date: Wed, 15 Apr 2009 13:33:25 +0200

> that negotiation succeeds, immediately re-kex with enc=aead mac=none.

I'd consider it a spectacular failure of the ssh-with-aead
specification if use of AEAD in the intended way (as both encryption
and mac, with no additional mac) requires two rounds of keyexchange at
connection startup. This gives unnececssary costs in both roundtrips
and computation, as well as in the implementation complexity that
comes with an extra negotiation round.

> That would be a rather unpleasant violation of the existing definition.

Well, the current rules are based on the assumption that encryption
and mac are independent (and that all algorithms can be selected
independently, except for a somewhat vague dependency between
key-exchange algorithm and hostkey algorithm). With aead, this
assumption is not quite valid.

I can understand your concern, but I think it's quite natural to
require that if an implementation supports and advertises an aead
algorithm, then it is aware that selecting aead for encryption makes
the selection of mac algorithm moot.

We won't get into any real trouble for doing that until we also
specify that if a particular mac algorithm is used, the encryption
algorithm should be ignored. And we won't do that, if we agree that
any algorithms with intimate dependencies between encryption and mac
should go inte the encryption list rather than the mac list.

Analogously, if we specify a keyexchange algorithm with integrated
server authentication (say, using SRP or something like that for the
key exchange), we can say that the hostkey algorithm is moot and
ignored.

> I'd much rather just re-kex if using a none MAC is that important.

I also find it brittle to renegotiate with a subset of the previous
algorithms, in particular when you exclude one of the *selected*
algorithms. Imagine that both sides attempt renegotiation, and that
they do it slightly differently. Then the connection may fall apart.
And if you want to avoid such problems by specifying in more detail
what the policy behind the renegotiation should be, then I'd much
prefer to specify *explicitly* what it is you want to achieve, e.g.,
that no mac should be used together with AEAD, and then implement that
policy at both ends with no extra negotiation.

BTW, I'm also curious about the motivation for the GCM mode. I just
had a first reading of the spec
(http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf).
The structure is almost the same as CTR mode with a separate MAC. The
only way I can make sense of it is if (i) GHASH is significantly
faster than common macs such as hmac-sha1, and (ii) GHASH has
properties that make it usable for GCM, but not suited for use as an
independent MAC. Is that the case, or what's the point?

Regards,
/Niels

---

From: Damien Miller <[email-masked]>
Date: Wed, 15 Apr 2009 22:21:20 +1000 (EST)

> I'd much rather just re-kex if using a none MAC is that important.

Without offering a solution to the initial negotiation (all that I have
seen so far a ugly), I would observe that rekex is far to expensive to
be a good solution to this problem.

-d

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 05:51:24 -0700

Hello,

I can live with cleartext length field or encrypted length field.  I have implemented AES-GCM as the draft stands now, so I know it's technically possible.  It has been suggested that some AES-GCM implementations must process the message as a single block of data --- a black box.  I don't know what hardware offload (proprietary?) that is unable to process AES-GCM in a chunk manner; Cavium can process in chunks.  I suppose at some point in the future an AEAD-* method will not be able to process the message in chunks, but this draft is for AEAD-AES-GCM.  Are we trying to future proof something that may never happen?  Even so, I would imagine it could dealt with at that time --- there will be an inconsistency now or future.  

I do agree sending the length field in the clear will cause some headaches at a lowest level, since a new in/out method will need to be written and tested.  However, I don't see the issues around NEWKEY some have suggested, but perhaps that implementation specific.  The encrypted length field has been a pain in the past, especially for async implementations like mine, but I have lived with it fine for last few years.  

The only issue I have any energy around are suggestions for fallback approaches or no-MAC; similar approaches have been suggested for SSH-ECDSA.  These approaches create a great deal of work and break the current protocol model.  

Thank you,

James

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Niels Möller
Sent: Wednesday, April 15, 2009 1:57 AM
To: Tim Polk
Cc: [email-masked]; Tero Kivinen; Bill Sommerfeld; Chris Lonvick; [email-masked]; Igoe, Kevin M.; Jerome A. Solinas; <[email-masked]> Eronen
Subject: Re: applying AES-GCM to secure shell: proposed "tweak"

Regards,
/Niels

---

From: "denis bider \(Bitvise\)" <[email-masked]>
Date: Wed, 15 Apr 2009 09:29:27 -0400

I've been seeing this argument enough that I need to comment on it:

> The encrypted length field has been a pain in the past, especially
> for async implementations like mine, but I have lived with it fine for 
> last few years.

- We have TWO fully asynchronous SSH implementations, and the encrypted 
length field has not been an implementation problem for either of them.

- Introducing a new way of sending length unencrypted is not going to 
relieve programmers of the burden of implementing the encrypted length. If 
anything, it's going to add a NEW burden of having to support two ways of 
sending and receiving the length, encrypted and unencrypted.

- The one problem I know of with sending the length encrypted is that it has 
facilitated a plaintext discovery attack when used with CBC. The proper 
response to that is to (1) prefer CTR mode, and (2) implement length 
decoding in a way that defeats the attack.

That being said: I have no problem with the AEAD implementation doing 
whatever it wants, as long as implementations that don't want to use AEAD 
are unaffected. It sounds like AEAD is sufficiently different that it 
_requires_ modifying the transport layer for sensible implementation. At the 
very least, for example, it needs to introduce a dependency that will 
implicitly turn off the MAC algorithm when AEAD is used.

If I were implementing AEAD, however, I would also worry about any possible 
implementations that might be relying on the SSH packet boundary not being 
obviously disclosed, and would worry about AEAD's compatibility with such 
applications. This seems to gesture that continuing to implement an 
encrypted payload field may be a good idea even with AEAD.

denis

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 08:29:09 -0700

Hello,

> It sounds like AEAD is sufficiently different that it 
> _requires_ modifying the transport layer for sensible implementation.

This is true for the generic case of AEAD-*, but not true for AEAD-AES-GCM.  AEAD-AES-GCM works fine per draft.  I want to stress it can be made to work, including the MAC --- AEAD-AES-GMAC.  AEAD-AES-GCM using same cryptographic AES-GCM used by our TLS 1.2 implementation was reused with SSH.  The algorithm was quite simple to adopt.  I spent some extra effort to verify that message chunks were not an issue (mainly due to what I had read online this being an issue).  I was not the author of our AES-GCM implementation, and I didn't need to consult him --- it was fairly effortless to integrate.  

I'd like to see Suite B related drafts move forward.  IMO - We're down to one small issue on each that are blocking final consensus.  I am fine with adding support for clear text length field, if this means we can move to final RFC --- although I personally don't believe it's necessary work at this time to support AEAD-AES-GCM.  

Btw There has been a couple of important SSH drafts that have stalled, which is a shame.  And which I would like to pick up and resurrect.  

Thank you,

James

-----Original Message-----
From: denis bider (Bitvise) [mailto:[email-masked]] 
Sent: Wednesday, April 15, 2009 6:29 AM
To: James Blaisdell; Niels Möller; Tim Polk
Cc: [email-masked]; Tero Kivinen; Bill Sommerfeld; Chris Lonvick; [email-masked]; Igoe, Kevin M.; Jerome A. Solinas; [email-masked]
Subject: Re: applying AES-GCM to secure shell: proposed "tweak"

denis

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 11:10:57 -0400 (EDT)

>> However, it is fairly easy to offer enc=aead,3des-cbc mac=hmac, and,
>> if that negotiation succeeds, immediately re-kex with enc=aead
>> mac=none.
> and mac, with no additional mac) requires two rounds of keyexchange
> at connection startup.

There's not much choice, though, unless you either (a) break the
existing protocol design (eg, by having some encryption algorithms,
when chosen, magically rewrite the rules for MAC algortihm selection)
or (b) risk ending up with a bad match (like 3des-cbc/none).

> and mac are independent

Right.  This is a bad match for AEAD.

Experimental protocol redesign work (coming up with a good way to tie
algorithms together for negotiation) is a sane idea.  Trying to
shoehorn it into the existing protocol with magic level-violating
semantics for certain algorthm names is not.

IMO, of course.

If ssh starts going down that road, another dozen or so "special cases"
later it'll be a horrible mess of magic interdependencies, with
determining whether negotiation _can_ succeed bordering on NP-hard.

> (and that all algorithms can be selected independently, except for a
> somewhat vague dependency between key-exchange algorithm and hostkey
> algorithm).

What's vague about it?  kex may need signatures and/or encryption; host
key algorithms may provide signatures and/or encryption; host-key
algorithms that don't provide what the negotiated kex algorithm needs
are effectively removed from the algorithms lists.  (4253 7.1, p. 18.)

> the selection of mac algorithm moot.

That's reasonable.  The problem is, the protocol we have has no way to
express it.  I see three choices: (1) we can suffer an inefficiency
necessitated by this mismatch; (2) we can go back into experimental
protocol design to come up with a protocol that supports such
dependencies properly; (3) we can violate the existing protocol with a
magic interdependency and hope it doesn't break anything too badly.

(3) is what I wish to discourage.  It's just begging for trouble down
the line.

> algorithm should be ignored.

Or some other set of cross-linked magic dependencies end up requiring
something effectively similar.  If we do this, it won't be the last
such piece of negotiation magic, I'm sure of that.

> they do it slightly differently.  Then the connection may fall apart.

Yes; buggy code can break things.  This has always been true and always
will be.  I don't think requiring any implementation that supports
enc=aead to also support mac=none, at least when using enc=aead, is
unreasonable.  I certainly consider it less bad than violating the
existing algorithm negotiation protocol.

I think my preference for doing this within the existing protocol
framework would be a "suppress-mac" option (to dig out the
options-packets subthread), with AEAD-supporting implementations
expected to use it if AEAD is chosen for encryption.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 11:43:54 -0400 (EDT)

> Without offering a solution to the initial negotiation (all that I
> have seen so far a ugly), I would observe that rekex is far to
> expensive to be a good solution to this problem.

Agreed.  It's just the only solution I see that works within the
existing protocol.  (IMO the _right_ answer is to invent/design a
protocol that allows algorithms to be tied together for negotiation.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 10:36:08 -0500

> I'd much rather just re-kex if using a none MAC is that important.

AEAD cipher modes clearly combine the MAC into the cipher.  That
means that the MAC can no longer be negotiated separately from the
cipher.

Therefore I believe Niels is correct: when an AEAD cipher is selected
then the MAC negotiation MUST be ignored.

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 08:56:28 -0700

It doesn't need to be ignored, but the order does matter.  AEAD-* algorithms must appear first in the order list.  And AEAD-* algos must match cipher and MAC in order as well.  It's easy to detect, if there is a mismatch between cipher and hmac.

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 11:08:00 -0500

On Wed, Apr 15, 2009 at 08:56:28AM -0700, James Blaisdell wrote:
Nico> AEAD cipher modes clearly combine the MAC into the cipher.  That
Nico> means that the MAC can no longer be negotiated separately from the
Nico> cipher.

Nico> Therefore I believe Niels is correct: when an AEAD cipher is selected
Nico> then the MAC negotiation MUST be ignored.

James> It doesn't need to be ignored, but the order does matter.
James> AEAD-* algorithms must appear first in the order list.  And
James> AEAD-* algos must match cipher and MAC in order as well.  It's
James> easy to detect, if there is a mismatch between cipher and hmac.  

What I meant is that IF an AEAD mode cipher is selected THEN the MAC
algs negotiation is superfluous and thus to be ignored.  It would still
be the case that IF the chosen cipher is NOT an AEAD cipher THEN the MAC
alg nego would proceed as usual.

I see no point whatsoever in trying to force separate cipher mode and
MAC negotiation when using AEAD -- it's totally artificial and gains us
exactly nothing.

Nor should it be possible to use an AEAD cipher and an unrelated MAC --
what would be the point of that?

Just because SSHv2 algorithm negotiation made too many assumptions
doesn't mean we must beat everything new into the old mold.

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 11:31:38 -0500

> protocol that allows algorithms to be tied together for negotiation.)

IMO you're making things too hard.  To repeat myself:

IF an AEAD mode cipher is selected THEN the MAC algs negotiation is
superfluous and thus to be ignored.

That's really quite simple.

Similarly, IF an AEAD mode cipher is selected THEN the packet length
shall be sent unencrypted, with whatever other adjustments need to be
made.  Though here we can add support for the option that Niels proposed
(where the packet lengths are encrypted separately with a separately
keyed non-AEAD cipher that's associated with the AEAD cipher).

KISS.

Nico
--

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 09:43:31 -0700

I buy your argument, Nico.  

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Nicolas Williams
Sent: Wednesday, April 15, 2009 9:32 AM
To: der Mouse
Cc: [email-masked]
Subject: Re: applying AES-GCM to secure shell: proposed "tweak"

KISS.

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 10:59:41 -0500

> I don't find (1) convincing. I'd prefer not to make design changes of

There has been a security vulnerability that resulted from information
leaks that take place when the encrypted packet length is decrypted and
checked before the MAC is verified.  The leak was enormously compounded
by sending the decrypted packet length in a DISCONNECT packet, but also
by syslog()ing the decrypted packet length as well.

And it turns out that it's very difficult to hide the actual packet
length.  To do it properly you need to send IGNORE messages along with
all others, and you need to be very careful how the data is read so that
there can't be any TCP window adjustments that reflect the sizes of
read() calls.  i.e., you don't want to read() the packet length then
read() the rest, you want to read as much data as the lesser of max
packet size or the  amount of data that is in the receive buffers.  At
the very, very least we ought to document this.

> details on what security problems others see with encrypted length

I can't think of any such applications where random padding and random
IGNORE packets wouldn't suffice.  And keep in mind that all other
Internet protocols that encrypt traffic do not encrypt message lengths.

That isn't to say that I'm not concerned about a switch to cleartext
packet lengths.  There may be unexpected issues that arise from that.

> well-tested and more buggy than the other.

My proposal for negotiation is trivial.

Now that we think we know how to properly deal with encrypted packet
lengths one could argue that we should continue with that approach.  But
I would still prefer that we don't for the other reasons that we've
given, mostly that encrypted packet lengths with AEAD ciphers may
require changing APIs like, for example PKCS#11 (which, now has support
for GCM).

I've not looked at how PKCS#11 deals with AEAD, but I'm pretty sure that
it does not have any support for encrypted pacaket lengths.  And we want
to use PKCS#11 in SunSSH, and in fact, we do, though indirectly through
the OpenSSL PKCS#11 engine.  Forcing us to not be able to use PKCS#11
will severely impact future FIPS compliance projects.

>    chosen so that it reuses the same primitives as the AEAD-algorithm

I'm OK with (2) as an option, as the default option.  It does add more
overhead over AEAD w/ cleartext packet lengths.

Nico
--

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 10:26:16 -0700

I am okay with #2 as well.  Thanks!

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Nicolas Williams
Sent: Wednesday, April 15, 2009 9:00 AM
To: Niels Möller
Cc: Tim Polk; [email-masked]; Tero Kivinen; Bill Sommerfeld; Chris Lonvick; [email-masked]; Igoe, Kevin M.; Jerome A. Solinas; <[email-masked]> Eronen
Subject: Re: applying AES-GCM to secure shell: proposed "tweak"

Nico
--

---

From: [email-masked] (Niels Möller)
Date: Wed, 15 Apr 2009 20:06:07 +0200

der Mouse <[email-masked]> writes:

> What's vague about it?

Maybe it's not vague, it's long time since I thought about that. Maybe
that impression came from the fact that there's no widely supported
key exchange method that needs a public key encryption, so it's rarely
making a difference.

> such piece of negotiation magic, I'm sure of that.

Can you substantiate that feeling? We have one magic interdependency
already (keyexchange/hostkey), introduced in the original spec some
ten years ago. Now we're discussing another one, from the introduction
of algorithms with "simultaneous" encryption and authentication. I
doubt we'll have to do things like that very often. New cryptographic
primitives, useful for this kind of protocol, don't appear very often.
Do you see any other potential magic dependencies down the road?

And if there are any conflicts in the future, say, with the
introduction of foo-mac, which we can't handle in any better way, we
could handle it by specifying that an implementation MUST NOT
advertise both the deprecated aead algorithms and foo-mac, and maybe
also deprecate the aead stuff we're discussing now. But I honestly
don't find that scenario very likely.

So what I'm saying, is that I understand that you care to maintain a
clean and beautyful spec. My view is that I don't see much practical
or aestetical problems arising from this particular "magic"
dependency, which I think is similar in spirit to the key
exchange/hostkey dependency, and that the alternatives are worse
because they bring more complexity and hence more bugs.

I'm strongly against adding new general option or negotiation
frameworks just to support aead. That's simply not worth the effort.
If we can't come up with a reasonable way to "shoehorn" it into the
current algorithm selection precedures, I'd prefer to say "Sorry,
aead-style algorithms were not envisioned when the ssh protocols were
designed. It can't be supported. Maybe it'll be supported in ssh
protocol version 3 in the very distant future.".

/Niels

---

From: "denis bider \(Bitvise\)" <[email-masked]>
Date: Wed, 15 Apr 2009 14:24:21 -0400

> determining whether negotiation _can_ succeed bordering on NP-hard.

SSH is already down that road. GSSAPI key exchange requires ignoring the 
negotiated host key algorithm.

I think you're exaggerating the problem.

denis

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 13:25:04 -0500

> frameworks just to support aead. That's simply not worth the effort.

+1

For me that goes for Mouse's and Jeff's proposals both.

> protocol version 3 in the very distant future.".

I agree, but it won't come to that.  The reason is that we _can_
shoehorn AEAD into SSHv2.

We already have a number of things shoehorned into the SSHv2 kex, such
as:

 - GSS-API (which is not like the host authentication algorithms
   originally envisioned)

    - not only is there the whole GSS-API token exchange and the MIC
      sent by the server to authenticate the key exchange, but also

    - there's the need for a "null" or "none" host key alg to support
      re-keys without re-authentication, but only re-keys.

 - negotiation of compression only post-authentication (a very useful
   and awesome OpenSSH extension)

AEAD is trivial by comparison to the GSS-API: the MAC algs are
irrelevant when AEAD ciphers are negotiated, for the obvious reason that
the MAC is subsumed into the cipher mode.  There's no need to agonize
over "none".

What else might we shoehorn into kex?  Well:

 - Key transport instead of key agreement.  This one right and truly
   screws with the idea of separate key exchange and host auth algs.  So
   what?  It can still be shoehorned in in exactly the same way as AEAD:
   if you pick a key transport key exchange alg then the host auth alg
   negotiation becomes irrelevant.  (Oh, I suppose one could sign a key
   transport with a separate signature key, thus allowing one to
   separate key exchange and host auth even in the key transport case,
   but that just seems silly as it adds a public key op that should be
   unnecessary.)

 - Retriable initial kex, for example (this is so that GSS-API auth
   failure need not lead to the connection being closed).  For this I'd
   use the reserved unsigned 32-bit int in the KEXINIT as a flags field
   -- if both the client and the server have the flag set for re-triable
   kex then GSS-API failure should not lead to connection closure.

Nico
--

---

From: [email-masked] (Niels Möller)
Date: Wed, 15 Apr 2009 20:54:21 +0200

> by syslog()ing the decrypted packet length as well.

Thanks. Do you have a pointer to more details?

> it does not have any support for encrypted pacaket lengths.

I think it would be valuable if you could check that. Other APIs and toolkits
mentioned in the discussion seem to support it. The
specification, 
http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf,
says the following as the first item in the feature list (page 2):

  * The GCM functions are "online" in the sense that the lengths of
    the confidential data and the additional, non-confidential data
    are not required in advance; instead, the lengths can be
    calculated as the data arrives and is processed.
    
I'd expect that implementations allow processing the first block as
soon it it has arrived. (Yes, I realize the above sentence is not
normative in any way, and it might be interpreted differently, but at
least I think it's clear that block-by-block (or even byte-by-byte)
operations are considered reasonable).

(And the last time convenient use of some existing programming API had
a clear and visible impact on the design of the ssh protocols, we got
the "dss_signature_blob" (RFC 4253, section 6.6)...).

Regards,
/Niels

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 13:41:18 -0500

On Wed, Apr 15, 2009 at 05:51:24AM -0700, James Blaisdell wrote:
> I can live with cleartext length field or encrypted length field.  I
> have implemented AES-GCM as the draft stands now, so I know it's
> technically possible.  It has been suggested that some AES-GCM
> implementations must process the message as a single block of data ---
> a black box.  I don't know what hardware offload (proprietary?) that
> is unable to process AES-GCM in a chunk manner; Cavium can process in
> chunks.  I suppose at some point in the future an AEAD-* method will
> not be able to process the message in chunks, but this draft is for
> AEAD-AES-GCM.  Are we trying to future proof something that may never
> happen?  Even so, I would imagine it could dealt with at that time ---
> there will be an inconsistency now or future.  

It is entirely reasonable to construct AEAD APIs that require that the
caller provide the correct length up front.  Were it not for this
particular document that's exactly how I'd do it.

IN FACT, that's EXACTLY how PKCS#11 handles AEAD.  See:

http://mirror.switch.ch/ftp/doc/standard/pkcs/pkcs-11/v2-30/pkcs-11v2-20a5d1.pdf

"Set the message/data length ulDataLen in the parameter block. This
length should not include the length of the MAC that is appended to the
cipher text."

> I do agree sending the length field in the clear will cause some
> headaches at a lowest level, since a new in/out method will need to be
> written and tested.  However, I don't see the issues around NEWKEY
> some have suggested, but perhaps that implementation specific.  The
> encrypted length field has been a pain in the past, especially for
> async implementations like mine, but I have lived with it fine for
> last few years.  

Encrypted packet length will cause more headaches if it means changing
AEAD APIs.  If we really, really want encrypted packet lengths then
let's use Niels' proposal of using a separate and separately keyed
non-AEAD cipher to encrypt the packet length and then use the AEAD
cipher to encrypt the rest of the packet.  (Niels' proposal has to
involve padding the packet length if the non-AEAD cipher used to encrypt
the packet length is not a counter mode or stream cipher.)

> The only issue I have any energy around are suggestions for fallback
> approaches or no-MAC; similar approaches have been suggested for
> SSH-ECDSA.  These approaches create a great deal of work and break the
> current protocol model.  

Agreed, but no such suggestions are on the table.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 15 Apr 2009 15:52:46 -0400

> key exchange), we can say that the hostkey algorithm is moot and

Actually, we very nearly do this; see RFC4462.  What saves us with keyex 
and host key algorithms is that the base spec defines several properties of 
host key algorithms (can sign, can encrypt), and keyex methods specify 
which ones they depend on; the host key algorithm chosen is the first one 
that meets the requirements of the selected keyex algorithm.  This lets 
RFC4462 specify that the GSS keyex methods depend on neither signing nor 
encrypting.  Since the null host key algorithm (also defined in RFC4462) 
provides neither of those capabilities, we can list it (last).  This means 
we can negotiate (DH,RSA) or (GSS-KRB5,NULL) without having to worry about 
getting (DH,NULL).  However it also means we will get (GSS-KRB5,RSA) if 
both sides advertise both GSS-KRB5 and RSA.  That's actually desirable for 
the GSS keyex families.

We could do something analogous for encryption and host key algorithms, but 
I don't think it would get you what you want; in particular, it leads to 
negotiating a superfluous MAC.

What I'd suggest instead is defining a unique MAC alogrithm for each AEAD 
encryption algorithm, which has the same effects as null but is usable 
_only_ when the corresponding encryption algorithm is selected.  This is a 
simple and straightforward modification to the negotiation rules which 
allows the new MAC algorithms to be listed _first_ to ensure you don't do 
extra MAC's when an AEAD encryption algorithm is selected, but without 
adversely affecting the MAC negotiation when an AEAD encryption algorithm 
is _not_ selected -- even when one of the peers is not AEAD aware.

> policy at both ends with no extra negotiation.

Agree.

-- Jeff

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 12:53:16 -0700

Woah...  I agreed with you, that option #2 is the best approach.  Did you not see 2 hours ago.  As I said, it working for me now --- yes, I've implemented it.  I am happy to change it.  Thanks!

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 15 Apr 2009 16:01:46 -0400

> negotiated host key algorithm.

No, it most certainly does not.  GSS keyex depends on neither public key 
signature nor encryption, and so can be used with host key algorithms which 
provide neither, such as "null".  It does not _require_ use of such an 
algorithm; it works with any host key algorithm and in fact has the side 
effect of authenticating whatever host key is used.  It certainly does not 
require ignoring the results of host key algorithm negotiation and using 
some other host key instead.

-- Jeff

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 16:09:49 -0400 (EDT)

> It doesn't need to be ignored, but the order does matter.  AEAD-*
> algorithms must appear first in the order list.

That's completely unextendable; what happens when another algorithm is
added that also "must appear first"?

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 16:10:58 -0400 (EDT)

> doesn't mean we must beat everything new into the old mold.

Of course not.

But, conversely, you shouldn't be beating everything old into
compatability with the new, either, and that's what looks to be
happening here: people seem determined to find _some_ way to marry AEAD
and SSHv2.  I don't see why, given how poor a match they are.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 16:20:46 -0400 (EDT)

> There has been a security vulnerability that resulted from
> information leaks that take place when the encrypted packet length is
> decrypted and checked before the MAC is verified.

Which actually is mostly unavoidable, since the MAC can't be even
_located_ until the packet length is known.

> The leak was enormously compounded by sending the decrypted packet
> length in a DISCONNECT packet,

!!  It's hardly the fault of the protocol if implementations
gratuitously leak cribs for attacking the crypto!

Some information leakage is unavoidable; if nothing else, the placement
of error detection by the receiver can act as an oracle for whether the
decrypted length falls into certain ranges.  But that's a far cry from
blatantly leaking 32 of the cleartext bits for attacher-chosen
ciphertext.  (Though, even then, it's just a flavour of
chosen-ciphertext attack, and a relatively expensive one - got a
reference to the weakness in question?  Even though I'm just a
dilettante as a cryptographer, I'd like to have a look for myself.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 13:38:26 -0700

Hey Mouse,

The discussions have been fiery goodness.  I think a good conclusions are being reached.  

You are correct --- the order will likely be a pain, if there are higher prio algos that are not AEAD --- I rationalized the solution as I coded it up (my mistake).  I think having AEAD-* algos ignore hmac algos is likely a good thing.  

I think AES-CTR for the length field is a good least painful approach (option #2); details missing what key to use.  I am certain PKCS#11 will prove to be excruciatingly slow to implement 4-byte AES-CTR jobs, which then means software version needs to be FIPS --- sorry.  For makekey(), maybe same letter e.g. "d", but twice for sub algos?  I'd hate for us to pick just an incremental letter since that will not be future proof (collisions).  

Would AES-CTR be used as a stream cipher, so four lengths would be encipher/decipher per count, or not?  

There are still some open issues even with these alternative approaches.  I am going shut up now.  

Thanks,

James

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of der Mouse
Sent: Wednesday, April 15, 2009 1:10 PM
To: [email-masked]
Subject: Re: applying AES-GCM to secure shell: proposed "tweak"

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 15:34:26 -0500

> added that also "must appear first"?

James is wrong.  There's no need to put AEAD ciphers first, unless, of
course, one prefers them.

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 15:38:45 -0500

> gratuitously leak cribs for attacking the crypto!

Even without the DISCONNECT and syslogging you still leak quite a bit
IFF the packet length decodes to something less than max packet.  Yes,
it's unlikely for an active attacker to cause that, since max packet
will usually be on the order of 2^16 but the truly max packet length is
on the order of 2^32, but surely you see the point.

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 15:33:25 -0500

> Thanks. Do you have a pointer to more details?

http://www.cpni.gov.uk/Docs/Vulnerability_Advisory_SSH.txt

> I think it would be valuable if you could check that. Other APIs and toolkits

I did, and I posted on that a few hours ago.  And lo and behold, PKCS#11
does indeed require that the length be provided by the application at
decrypt time -- or at least that's my interpretation of the draft, but
I'll re-read it in case you're correct that it's online, that one could
call C_DecryptUpdate() once to get the length (and padding, ...) then
again to get the rest.

Nico
--

---

From: [email-masked] (Niels Möller)
Date: Wed, 15 Apr 2009 23:01:58 +0200

Jeffrey Hutzelman <[email-masked]> writes:

> What I'd suggest instead is defining a unique MAC alogrithm for each
> AEAD encryption algorithm, which has the same effects as null but is
> usable _only_ when the corresponding encryption algorithm is selected.

I'm not sure I follow precisely what you mean, but I think the
important structural change is that we say that should apply algorithm
selection to the encryption algorithm first, before selecting the mac
algorithm.

Then the result of the selection of the encryption algorithm may
trigger special behaviour when it comes to the MAC algorithm. The
naive rule "If an AEAD-algorithm is selected for encryption, no other
MAC is used, and it doesn't matter whatsoever what's on the MAC
algorithm lists" is simple and I think it should work, although I'm
open to other variations.

Implementations not supporting AEAD need of course not know or care
about this rule. A party that advertises only AEAD-algorithms for
encryption can safely list "none" as the only MAC algorithm (IIRC,
it's not allowed to send an empty list, and any value, not just
"none", will work just as well), negotiation with a party not
supporting AEAD will then fail in an orderly manner. A party that
lists AEAD and some non-AEAD encryption algorithm, will list the MACs
that it's willing to use together with non-AEAD encryption.

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Wed, 15 Apr 2009 23:05:52 +0200

> added that also "must appear first"?

Agreed. That's not acceptable.

And besides that, it should be possible to express old-fashioned
preferences, like "I really like triple-DES, but if you don't support
it, I'll go with AEAD as a fallback".

Regards,
/Niels

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 07:10:01 +1000 (EST)

On Wed, 15 Apr 2009, James Blaisdell wrote:

> algorithms must appear first in the order list. And AEAD-* algos must
> match cipher and MAC in order as well. It's easy to detect, if there
> is a mismatch between cipher and hmac.

-1

That has the nasty side effect of specifying Cipher/MAC policy to server
operators.

---

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

> the packet length is not a counter mode or stream cipher.)

Actually, I'm suggested that we encrypt the first *block*, not just
the length field, with an independent cipher. The full block is then
authenticated as additional data to AEAD. In the case of AES-GCM,
there's a natural block size, and a reasonable choice for this cipher
is AES-CTR. This way, there's nothing special to the padding.

What's actually done to the data is very similar to what you'd do if
you applied AES-GCM to the entire message including length field, and
extracted length field first when decrypting. (It would be nice in
some ways, but less general, if the details could be defined so that
the result is *identical*).

Encrypting only the length field (or length + padding) would cause
more complexity and more overhead, I think.

Regards,
/Niels

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 16:11:08 -0500

> on the order of 2^32, but surely you see the point.

The reason you leak if the packet length decodes to something less than
max packet is this:

   The attacker can modify what he thinks is encrypted ciphertext and
   hope it decrypts to a value less than max packet, then he can send
   garbage one block at a time until the peer responds by closing the
   connection when the MAC fails to validate.  The attacker then knows
   the decrupted packet size to within one block size.

If max packet size is much smaller than the max possible packet length
then most of the time all that's leaked is that the decrypted packet
size is larger than the negotiated max packet length and so this attack
is not worthwhile.  With HPN in the picture I'm not sure that that will
be the case, though one expects no active attackers in HPN cases, but
still.

With a cleartext packet length you don't have any of these problems.
Instead you get the normal traffic analysis problems, such as the
ability to recognize echo-off password prompts and count any
one-character packets and thus determine packet length.  However, these
problems can be addressed without cryptography.

Nico
--

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 16:28:47 -0400 (EDT)

>> Or some other set of cross-linked magic dependencies end up
>> requiring something effectively similar.  If we do this, it won't be
>> the last such piece of negotiation magic, I'm sure of that.
> Can you substantiate that feeling?

Of course not.  How can one substantiate a prediction about the future?

> We have one magic interdependency already (keyexchange/hostkey),

Hm, that's true.  Ugh.

I still don't like it, though; this argument feels like "we made this
mistake already in the past, so we might as well make it over again in
a different way here".  (Yes, I realize this phrasing of it is somewhat
question-begging, in that it assumes it _is_ a mistake.)

More generally, there are two aspects of this AEAD thing that are
relevant: there are compatability properties (eg, encryption using an
algorithm with a (notional) "aead" property means using a MAC algorithm
with a similar property (and only "none" has the "aead" property)), and
there are negotiation order dependencies (MAC negotiation depends on
encryption negotiation).

It's true that each of these is present in kex/hostkey (compatability,
in the form of "encrypt" and "sign" properties, and ordering, in the
form of "hostkey negotiation depends on the outcome of kex
negotiation").  But I don't see how that justifies introducing more of
either.

> My view is that I don't see much practical or aestetical problems
> arising from this particular "magic" dependency, which I think is
> similar in spirit to the key exchange/hostkey dependency, and that
> the alternatives are worse because they bring more complexity and
> hence more bugs.

I agree that this is similar in spirit to the kex/hostkey dependency.
But, as I said above, that doesn't justify it to me.

Are the alternatives worse?  I think this is true only if you restrict
yourself to a very small subset of the available alternatives - for
example, if you insist on doing it within an SSHv2 framework.  SSH is
not the be-all and end-all of secured communications, and it does not
mean there is anything wrong with either SSH or AEAD if the two don't
play nice together.

The more I think about this, the more I think what's really bugging me
about it is yet another form of the cross-product problem.  Algorithm
negotiation order can be dealt with; each partial order dependency can
be registered - separately - with dependency registrations rejected
when they would introduce dependency cycles.  But the algorithm
property problem is much harder.  We've got two properties ("sign" and
"encrypt") applicable to kex algorithms and host-key algorithms; this
AEAD thing introduces another property ("integrated-mac", say) which
applies to encryption and MAC algorithms.  To do this right (ie,
without ambiguities) requires that every new algorithm specify what
value it has for every previously-defined property, and every new
property specify its value for every previously-defined algorithm.
This becomse a huge - and fairly sparse - matrix, and a tremendous load
on proposers of new algorithms or properties, since they must
understand all propertyes (resp. algorithms) enough to figure out what
values to specify.  It also is a practical problem in the presence of
private algorithms and/or properties, or in the presence of multiple
people working on different algorithms and properties simultaneously.

> frameworks just to support aead.  That's simply not worth the effort.

The point is that they _aren't_ "just to support aead".  If they were,
yes, it would not be worth the bother.  They are to support aead _and_
whatever other now-unforeseen issues arise down the line -
future-proofing, if you will.  Trying to solve the immediate problem
right and thereby solve various future problems as well, rather than
solving the immediate problem with a kludge that doesn't help and quite
likely may actually hinder solving future problems.  Akin to the remark
in the jargon File that "[r]eal hackers [] generalize uninteresting
problems enough to make them interesting and solve them - thus solving
the original problem as a special case".

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 16:02:48 -0500

> simple and straightforward modification to the negotiation rules which 

But not simpler than my proposal:

   IF an AEAD cipher is selected THEN no MAC alg is selected (since the
   cipher provides integrity protection all by its lonesome).

We should pick the simplest solution that does the job.  I don't think
you'll find one simpler than the above.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 15 Apr 2009 17:27:40 -0400

> selection to the encryption algorithm first, before selecting the mac

Yes, we need to say this.  The base spec makes the corresponding assertion 
for keyex and host key algorithms, though with a bit of a twist:

- keyex negotiation comes first, but the only algorithms considered are
  those whose needs are met by at least one host key algorithm the two
  peers have in common
- host key negotiation comes next, and the only host key algorithms
  considered are those which meet the needs of the selected keyex

In the case of encryption and MAC algorithms, I don't think we should have 
this sort of bidirectional dependency.  Rather we should simply say that 
the encryption algorithm negotiation happens first, which then allows us to 
modify the MAC algorithm in ways that depend on knowing which encryption 
algorithm was selected.

> open to other variations.

I'd prefer not to have that particular rule.  I think it would be better
to explicitly describe a MAC algorithm which does nothing has no effect,
and do one of these:

a) Define a rule that allows a MAC algorithm to depend on a particular
   encryption algorithm (or a particular set of algorithms), such that
   that MAC algorithm can be considered only if the selected encryption
   algorithm is one of the ones it depends on.  Then define multiple
   do-nothing MAC algorithms, one per AEAD encryption algorithm, and
   make them depend on the corresponding AEAD algorithm.

b) Allow a MAC algorithm to depend on encrpytion algorithm properties,
   in the way that keyex algorithms depend on properties of host key
   algorithms.  This means that such an algorithm can be considered
   only if the selected encryption algorithm has whatever property it
   depends on.  Then specify a single do-nothing MAC algorithm which
   depends on AEAD encrpytion algorithm.

One of the advantages of either of these approaches is that one can choose 
to use a traditional MAC in addition to an AEAD encryption algorithm, if it 
is discovered that the integrity-protection properties of the AEAD 
algorithm are weaker than previously thought.  This would be a fix that 
could be quickly deployed by making configuration changes using existing 
MAC algorithms.  Approach (a) has the additional advantage that such a 
workaround can easily be applied only to specific AEAD algorithms.

> supporting AEAD will then fail in an orderly manner.

... unless someone decides to implement "none" and not AEAD.

-- Jeff

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 16:13:40 -0500

> it, I'll go with AEAD as a fallback".

Right.  My proposal (MAC algs nego irrelvant when AEAD cipher chosen)
allows that.

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 17:32:19 -0400 (EDT)

>    and awesome OpenSSH extension)

(a) What's so useful about it?  (I don't offhand see any reason why it
would be better than starting compression at kex time, and I'm
wondering what I've missed.)

(b) Got a pointer to the spec?  I'd like to read up on it and see if I
want to implement it.  (I would _hope_ that OpenSSH would be, well,
open with their extensions - but I was unable to find any spec for
[email-masked], so maybe not.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 07:36:14 +1000 (EST)

>    kex then GSS-API failure should not lead to connection closure.

That is a good idea IMO.

-d

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 16:30:20 -0500

> future-proofing, if you will.  Trying to solve the immediate problem

The original designers of the SSHv2 kex clearly didn't have the right
vision of the future, but, then again, their design mistakes haven't
stopped us.  I don't believe we can do much better now as, like them
then, we cannot necessarily predict the future.

Thus I'd rather do the simplest possible solution, which solution I
think I've stated something like four or five times today.

I'd also like us to clarify how implementors should deal with that
reserved uint32 field in KEXINIT today as a way of buying ourselves room
for future extensions.  For that I propose this:

    The reserved uint32 field in KEXINIT MUST be set to 0; future specs
    may specify the meaning of non-zero values and when they may be
    sent.

    When a KEXINIT is received that has a non-zero value in the KEXINIT
    reserved uint32 field, then the receiver MUST ignore both, the
    reserved uint32 field and any additional bytes in the packet beyond
    it.

    Future extensions might treat the reserved uint32 field as a flags
    field and might specify flags that, when set, indicate that
    additional data may be found between the reserved field and the end
    of the KEXINIT packet, and/or that additional new key exchange
    protocol packets may follow.

Nico
--

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 17:38:13 -0400 (EDT)

>>> There has been a security vulnerability [...]

Got a pointer to anything that actually describes the attack?  That
page describes only the effect of the attack, not the mechanism, and
makes claims that seem dubious to me ("an arbitrary, attacker-selected
block of ciphertext", claims that only CBC mode is affected, and the
claims here that it's due to encrypting packet lengths - these sound
unlikely to me to all be true - but of course that likely just means
I'm missing something, which is why I'm interested in more details).

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 07:51:12 +1000 (EST)

+1

This seems to be the least horrible solution to the problem. It is
certainly the easiest to implement, which makes me think that it won't
be stuffed up.

-d

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 07:56:00 +1000 (EST)

> wondering what I've missed.)

Avoiding the attack surface presented by compression libraries before
authentication of the user.

> want to implement it.

http://tools.ietf.org/html/draft-miller-secsh-compression-delayed-00

-d

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 16:21:22 -0500

> is AES-CTR. This way, there's nothing special to the padding.

Ah, clever.  I'm OK with that as an option.  I'd like the option to have
unencrypted packet lengths (meaning the first block of encryption starts
at byte #4 (zero-based numbering) of the packet.

But, actually, I think I was wrong about PKCS#11, it does seem to allow
online decryption with AEAD modes.

Nico
--

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 17:45:28 -0400 (EDT)

> IFF the packet length decodes to something less than max packet.

How?  If my response to an invalid packet length is to read the right
amount of data for a max-length packet and disconnect, and my response
to an invalid MAC is to read as much as necessary to pad to the amount
I would have read if the packet length were max-length and then
disconnect, I don't see how I'm leaking anything - unless you happen to
get the MAC right too, which reduces attack success probability
substantially.  (Admittedly, this does not describe the behaviour of
any implementation, as far as I know.)

Or, I suppose, unless you're doing precision timing attacks to
determine how much I'm feeding to my MAC computation before going into
read-and-discard mode.  To defeat that I'd probably have to decrypt the
extra garbage (and, ideally, feed it into whatever hashing the MAC
algorithm in question does).

> Yes, it's unlikely for an active attacker to cause that, since max
> packet will usually be on the order of 2^16 but the truly max packet
> length is on the order of 2^32, but surely you see the point.

Presumnably, the 2^-18, 2^-16, or 2^-14 probability of an attack being
successful I've seen cited is due to that: it works only when the
decrypted length has enough zero high-order bits that the attacker can
tell it from random garbage.  But I've been staring at CBC and haven't
been able to see how knowing that is useful to the attacker - except as
a partial crib for attacking the bulk crypto, which is not what the
descriptions sound like.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 16:58:22 -0500

> wondering what I've missed.)

Our implementation (SunSSH) has a different approach to PrivSep than
OpenSSH.  We recognize that doing privsep pre-authentication gets no
real privilege separation[*] for any components other than compression.
So SunSSH's sshd does privsep only post-authentication, which keeps its
montior protocol very very simple.  Therefore we'd like to defer
compression to post-authentication

[*] We noticed that the monitor protocol for supporting pre-auth privsep
    was not materially simpler than the pre-auth parts of SSHv2 (i.e.,
    the monitor protocol was quite complex).  Buffer overflow attacks on
    the crypto are not likely (until the recent SHA-3 submissions I was
    unaware of any such buffer overflows), but buffer overflow
    vulnerabilities against zlib are nothing new.  Therefore privilege
    separation for zlib would be nice, and the simplest way to do it is
    to defer it to post-authentication.  Besides, there's very little
    that can be compressed or is worth compressing between key exchange
    and authentication.  See:

    http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/cmd/ssh/README.altprivsep

> [email-masked], so maybe not.)

http://www.openbsd.org/cgi-bin/cvsweb/~checkout~/src/usr.bin/ssh/PROTOCOL?rev=1.12;content-type=text%2Fplain

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 17:05:15 -0500

> I'm missing something, which is why I'm interested in more details).

I don't recall where the attack is described.

Briefly: an active attacker replaces what he/she knows to be an
encrypted packet length with bytes that he/she knows correspond to an
encrypted password, then after that sends the remainder of the packet
(possibly garbage) one byte/block at a time.

The information leak about the incorrect packet length may reveal some
number of bits of the password.  That number depends on how much
information is leaked.  If the packet length decrypted to something >
max packet length and the length was not syslogged to a remote host and
not sent back to the client (which the user might then quote w/o privacy
protection to a helpdesk), then the attacker learns very little.  If the
packet length decrypted to something < max packet length and there's no
syslog/disconnect leak then the attacker recovers 16 - block size bits
of the password.  If the attacker recovers the decrypted packet length
from syslog or the disconnect sent to the user, then the attacker
recovers four bytes of the password.

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 08:36:00 +1000 (EST)

On Wed, 15 Apr 2009, Nicolas Williams wrote:

> Jeff Hutzelman objects that this violates the abstraction that the
> transport layer defines the binary packet encoding.  I don't give a
> damn.

I don't see how this objection works: KEX (inc. cipher/mac negotiation)
determines the parameters for the transport protocol. How does a KEX
change violate the transport abstraction?

-d

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 15 Apr 2009 17:06:02 -0500

---

From: Simon Tatham <[email-masked]>
Date: Wed, 15 Apr 2009 23:46:33 +0100

> a partial crib for attacking the bulk crypto, which is not what the

You don't use it to attack the bulk crypto: you use it to get a
partial decryption of a particular cipher block. So you start by
traffic-analysing the session to identify a block you'd like to know
the plaintext of (e.g. the one that occurs at the right point within
SSH_MSG_PASSWORD); then you inject that same cipher block in place
of the length-containing block of a later packet, in the hope of
finding out something about its contents. If you find out that the
block decrypts to some valid packet length in the latter context,
then you can XOR in the difference between the previous cipher
blocks in both contexts to determine part of what the same block
decrypted to the first time round.

(Since the attack can only be used against a block from the same
session and you expect to splatter 2^18 connections before getting a
result, you'd only want to use it against some data which reliably
occurs in lots of sessions and which you desperately want to know.
The password packet is probably the only practical target, in almost
all circumstances.)
-- 
Simon Tatham         "Imagine what the world would be like if
<[email-masked]>    there were no hypothetical situations..."

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 18:41:56 -0400 (EDT)

> If the packet length decrypted to something < max packet length and
> there's no syslog/disconnect leak then the attacker recovers 16 -
> block size bits of the password.

Hmm.  Thank you.

Even that much, though, depends on the server disconnecting as soon as
it discovers the wrong MAC, and thereby leaking the decrypted length to
within the cipher's block size, doesn't it?

Also, ISTM the attacker recovers more than 16 bits; if the attacker
knows the packet size as revealed by disconnect timing (which this
seems to be entirely predicated upon), that reveals the exact packet
length field (since the length includes all padding, and thus knowledge
of the number of cryptosystem blocks in the packet gives the exact
packet_length value).  Combined with the attacker's presumed knowledge
of the previous ciphertext block in CBC mode, this reveals a full 32
bits of data from the block of interest.  Is this analysis wrong?

I also note it works only on data at the beginnings of blocks - this is
useless to an attacker who wants something beyond the first four bytes
of a cryptosystem block.

Fortunately, it's fairly easy to frustrate.  The first technique that
comes to mind is one I sketched upthread, which the receiver can
implement: react to bad packet lengths or invalid MACs by reading data
out to the maximum valid packet length before disconnecting.  The
second is something the sender can implement: rather than pausing
transmission at packet boundaries, always pad with an IGNORE packet -
and write only part of (the encrypted version of) it.  This makes it
harder for the attacker to find the length field in the data stream.
(This one provides only a few more bits of protection, since the
attacker can just guess at how much of the IGNORE packet the sender is
holding queued, but every additional bit of difficulty is another
factor of two less practicality.  And when the line is idle is when you
least mind inserting largeish amounts of pad data.)

And, of course, not using CBC ciphers breaks it totally.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Wed, 15 Apr 2009 19:08:46 -0400 (EDT)

> reserved uint32 field in KEXINIT today as a way of buying ourselves
> room for future extensions.

That, I totally agree with.  The current situation doesn't really give
us any way to use that field for anything.

> For that I propose this:

>     The reserved uint32 field in KEXINIT MUST be set to 0; future
>     specs may specify the meaning of non-zero values and when they
>     may be sent.

>     When a KEXINIT is received that has a non-zero value in the
>     KEXINIT reserved uint32 field, then the receiver MUST ignore
>     both, the reserved uint32 field and any additional bytes in the
>     packet beyond it.

>     Future extensions might [...]

(I'd also make explicit the implied change to SSH_MSG_KEXINIT, adding
optional additional data of unspecified size after the uint32 in
question, with the restriction that if the value is zero there must be
no additional data.)

This sounds good to me.  I support this proposal, in case anyone cares
what I think.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: "denis bider \(Bitvise\)" <[email-masked]>
Date: Wed, 15 Apr 2009 19:51:43 -0400

> on the order of 2^32, but surely you see the point.

It is not necessary to leak anything. If decoded packet length is invalid or 
exceeds MaxPacketLength (e.g. 2^16), then:

1. Select a random valid packet length between MinPacketLength and 
MaxPacketLength.

2. Read the randomly selected amount of data.

3. Choke as if MAC is incorrect.

This prevents the attacker from knowing whether the info they're getting is 
useful or not, and the likelihood is 1 against 2^N that it's not.

denis

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 16 Apr 2009 16:07:47 +1200

>authentication of the user.

This is pretty much the main reason why I haven't implemented it so far.  zlib
has had quite a number of security holes, and (from looking at the code in the
past) there are no doubt lots still in there - it's a huge body of incredibly
complex and not entirely comprehensible code (do you want to analyse
inflate.c/inffast.c and check that there's no potential for
overflow/underflow/overwrite/whatever in there?).  Having all that exposed to
arbitrary remote attackers is too big a risk to take.

(I've never really understood why the compression starts where it does anyway,
what's being exchanged at that point is mostly random incompressible binary
gunk so it has little to no effect on data size anyway).

>http://tools.ietf.org/html/draft-miller-secsh-compression-delayed-00

Hmm, why not just apply it only to the data packets?  The random non-data-
related messages exchanged (again, mostly high-entropy binary blobs) aren't
going to compress much (if at all), and will only have the effect of messing
up the compression by polluting the source statistics.  With data-payload-only
compression it'd be much cleaner and easier to handle, just run the compressor
over the data-packet payload and leave everything else as is.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 16 Apr 2009 16:15:33 +1200

>I don't recall where the attack is described.

It's in a conference paper that hasn't been published yet, to appear at the
IEEE Oakland conference in... May, I think.

[Pause]

Yup, see http://oakland09.cs.virginia.edu/papers.html.

>Briefly: an active attacker replaces what he/she knows to be an encrypted
>packet length with bytes that he/she knows correspond to an encrypted
>password, then after that sends the remainder of the packet (possibly
>garbage) one byte/block at a time.

It's interesting to note here that there have been a number of attacks (of
which this is the latest) on encrypted lengths, but none on plaintext lengths
as used by TLS.  In other words the "more secure" option used by SSH is
actually less secure than the "less secure" option of not encrypting, the
cause being the unnecessary complexity of processing that this introduces (see
my earlier posts in this thread, and I still owe people some replies for one
or two of those, sorry).

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 16 Apr 2009 16:21:42 +1200

>    reserved uint32 field and any additional bytes in the packet beyond

I'm not sure that this length-extension will work.  The spec has always said
that the packet ends at the reserved field, but this would change it to say
that it can now continue more or less arbitrarily beyond this point.  What
will existing implementations do if they see garbage beyond this point? 

I'd also rephrase the above a bit to say:

    When a KEXINIT is received that has a non-zero value in the KEXINIT
	reserved uint32 field and the receiver can't process a non-zero value then
	it MUST ignore it.

The original text seems to say "this value must always be ignored", the new
text says "if you don't know what the significance of the flags are, ignore
them".  Well OK, it says it rather badly, I'm open to suggestions for better
phrasings.

Peter.

---

From: der Mouse <[email-masked]>
Date: Thu, 16 Apr 2009 03:39:15 -0400 (EDT)

>> Avoiding the attack surface presented by compression libraries
>> before authentication of the user.

That strikes me as a desirable end.

But the I-D I saw named upthread doesn't look like a good way to do it.
When the server starts compressing is well-defined, but the point in
the client->server data stream at which the client starts compressing
is, from the point of view of the server, ill-defined; the only way I
see to make it well-defined as the algorithm is defined is for the
client to never send anything, even IGNORE or other such messages,
between the time it sends a packet which could provoke a
USERAUTH_SUCCESS response and the time it receives some kind of
response to it.  However, the spec does not specify anything of the
sort - leaving, I believe, this ill-defined.

> Hmm, why not just apply it only to the data packets?

That makes sense to me (and seems well-defined, at least once you
specify precisely what "data packets" are, presumably
SSH_MSG_CHANNEL_DATA, maybe SSH_MSG_CHANNEL_EXTENDED_DATA, possibly a
few others such as SSH_MSG_CHANNEL_WINDOW_ADJUST).  I may try
implementing it.

> The random non-data-related messages exchanged (again, mostly
> high-entropy binary blobs) aren't going to compress much (if at all),

I disagree.  There are a lot of non-data messages that are full of
uint32 fields that typically have at least 3/4 of their bits zero.
Some even use a 32-bit field to carry one bit of information.
Compressing these is valuable from the point of view of providing
higher-entropy data as the cleartext to the encryption algorithm and
therefore making it harder to attack.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: [email-masked] (Niels Möller)
Date: Thu, 16 Apr 2009 10:07:18 +0200

[...]

>   depends on AEAD encrpytion algorithm.

This makes sense to me. I'd prefer this option, then. The name could
be "none-if-aead".

> ... unless someone decides to implement "none" and not AEAD.

In this scenario, the mac selection may end up with "none", but the
intersection of the encryption algorithm lists will be empty, and
hence negotiation fails. Right?

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Thu, 16 Apr 2009 10:22:03 +0200

>    cipher provides integrity protection all by its lonesome).

To be precise, does this mean that the mac-list is ignored, or that
the *result* of that selection is ignored? Consider the following
advertised lists:

  Client:   enc="aead", mac="hmac-sha1"
  Server:   enc="aead", mac="hmac-md5"

Should the algorithm selection succeed, settling on aead and no
additional mac, or fail because there's no common mac?

Or to make it more complicated, what should be the result of:

  Client:   enc="3des-cbc,aead", mac="hmac-sha1"
  Server:   enc="3des-cbc,aead", mac="hmac-md5"

We can either fail, since is 3des-cbc selected for encryption, but
there's no common mac, or succeed if we notice that there's no common
mac, and then filter out all non-AEAD options for encryption.

This kind-of contradicts Jeffrey Hutzelman's wish

: In the case of encryption and MAC algorithms, I don't think we should
: have this sort of bidirectional dependency.

and without thinking deeply, I suspect the situation is quite similar
to the keyexchange/hostkey dependency, and that we should make about
the same level of effort to find a working combination in both cases.
I don't implement any keyexchange method that requires encryption,
maybe someone that does and understands this better can enlighten me?

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Thu, 16 Apr 2009 10:43:31 +0200

> online decryption with AEAD modes.

Good to hear, thanks for checking. If this is indeed a feature that is
typical of aead implementations (as seems to be the case), is there
any remaining reason not to use it and handle the encrypted length
field in the same way as for other encryption algorithms?

Do you reduce possibilities for attacks if you use separate ciphers
for the first blocks and the rest of the data? IIRC, the attacks that
has been mentioned all rely on cbc, so they are not effective against
aes-gcm.

Ideally, I guess it would be best to send

  1. first block (encrypted and including length field),
  2. mac of first block
  3. rest of message (encrypted)
  4. mac of complete message

but this is probably not the right time to make changes like that.

Regards,
/Niels

---

From: "Timo J. Rinne" <[email-masked]>
Date: Thu, 16 Apr 2009 12:35:15 +0300

> This makes sense to me. I'd prefer this option, then. The name could

I must say I really hate this one.  Instead of one simply defined 
"magic" cipher algorithm name that would have, if selected, a side 
effect of abolishing MAC, we would have a "magic" MAC name with much 
more complicated interdependency to cipher list.

To make it even more clear, the cipher name for aead could me something 
like "aes128-aead-nomac".  Then if someone likes to implement aead with 
additional mac (I don't know why anyone would do that) then 
"[email-masked]" kind of name could be used.

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 20:27:01 +1000 (EST)

> mac, and then filter out all non-AEAD options for encryption.

Nice catch. Intuitively, the easiest way to avoid this is to specify
that symmetric cipher agreement must occur before MAC agreement.
Most implementations probably do this already.

-d

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 20:28:30 +1000 (EST)

On Thu, 16 Apr 2009, Timo J. Rinne wrote:

> Niels M?ller wrote:

Yes, I don't think this one either. It seems like more extensive
special-casing or more complex (read: brittle) selection rules would be
required to make this work reliably.

-d

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 20:30:18 +1000 (EST)

On Thu, 16 Apr 2009, Peter Gutmann wrote:

> Hmm, why not just apply it only to the data packets? The random
> non-data- related messages exchanged (again, mostly high-entropy
> binary blobs) aren't going to compress much (if at all), and will only
> have the effect of messing up the compression by polluting the source
> statistics. With data-payload-only compression it'd be much cleaner
> and easier to handle, just run the compressor over the data-packet
> payload and leave everything else as is.

Since we are expressing wishes for the transport protocol, mine is a
per-packet compression flag :)

-d

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 20:39:31 +1000 (EST)

> will existing implementations do if they see garbage beyond this point? 

OpenSSH will treat additional data at the end of a kex packet as
a fatal error. It ignores unknown values of the "reserved" field though,
so it could be used to signal that additional data follows in a different
packet, or that the failure of a kex method is non-terminating.

-d

---

From: Damien Miller <[email-masked]>
Date: Thu, 16 Apr 2009 20:41:32 +1000 (EST)

> sort - leaving, I believe, this ill-defined.

Yes, the timing of the first compressed packet is strictly indeterminate
from the view of the server. The PuTTY people mentioned this some time
back and suggested an extension mechanism to signal "the next packet
is the first compressed one" (among other things), but the discussion
fizzled.

-d

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 16 Apr 2009 22:51:03 +1200

der Mouse <[email-masked]> writes:

>That makes sense to me (and seems well-defined, at least once you specify
>precisely what "data packets" are, presumably SSH_MSG_CHANNEL_DATA, maybe
>SSH_MSG_CHANNEL_EXTENDED_DATA, possibly a few others such as
>SSH_MSG_CHANNEL_WINDOW_ADJUST).  I may try implementing it.

Yup, I was thinking specifically of CHANNEL_DATA and EXTENDED_DATA, and just
the payload, not the header.

>There are a lot of non-data messages that are full of uint32 fields that
>typically have at least 3/4 of their bits zero. Some even use a 32-bit field
>to carry one bit of information. Compressing these is valuable from the point
>of view of providing higher-entropy data as the cleartext to the encryption
>algorithm and therefore making it harder to attack.

Uhh, so breaking AES is going to be possible if the content is uncompressed
but not if it's compressed? :-).  That's a pretty theoretical objection...

In terms of compression, I'm not so sure that compressing the headers is a
good idea.  If you look at the Calgary compression corpus the least-
compressible file in there is 'geo', which consists of lots of 32-bit ints
with high bits zero.  The reason for this is that most context-based
compressors are really bad at modelling counting events (every n-th byte zero,
that sort of thing), there are some special-case ones like DMC that handle
this a bit better but that has some other problems that make it impractical,
and I'm sure everyone else on the list has gone to sleep by now.  Without
running some tests it's hard to say what the effect will be, but I suspect
it's not going to be quite as good as expected.  It could also be rather
situation-specific, for example if you're using SSH for secure logging then
having the nice compressible stream of text records periodically broken up by
binary blobs probably isn't a good idea.

Peter.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 16 Apr 2009 08:27:27 -0400

--On Thursday, April 16, 2009 12:35:15 PM +0300 "Timo J. Rinne" 
<[email-masked]> wrote:

> I must say I really hate this one.  Instead of one simply defined "magic"
> cipher algorithm name that would have, if selected, a side effect of
> abolishing MAC, we would have a "magic" MAC name with much more
> complicated interdependency to cipher list.
>

The problem is, it's not _one_ simply defined "magic" algorithm.  It's an 
arbitrarily large number of them.

But if we're going to go with Nico's "simpler" proposal, we need to address 
the question Niels brought up -- does selecting an AEAD type mean we don't 
do MAC selection at all, or does it mean we do MAC selection and then don't 
actually do anything with the resulting MAC?

The question is important because it controls what happens when an AEAD 
algorithm is selected but there is no mutually-supported MAC algorithm. 
One answer is simpler to implement, because it doesn't actually change the 
selection algorithm at all, but the other provides more interoperability. 
And, Niels brings up a third possibility of somehow noticing when only an 
AEAD encryption algorithm will work and filtering out all of the others, 
which seems really complicated to me.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 16 Apr 2009 10:20:46 -0400

--On Thursday, April 16, 2009 09:04:35 AM -0500 Nicolas Williams 
<[email-masked]> wrote:

> This is a separate issue.  Remove AEAD and you don't interop.  Add AEAD
> with my rule and you still don't interop.  To improve the situation we
> need to twist the KEXINIT abstraction a bit more (no objections from
> me): IF a non-AEAD cipher is chosen AND there was no common MAC AND
> there was a common AEAD cipher THEN re-compute the cipher selection
> ignoring all non-AEAD ciphers.

Ugh.  This is starting to get complicated.

---

From: "Timo J. Rinne" <[email-masked]>
Date: Thu, 16 Apr 2009 17:22:40 +0300

Jeffrey Hutzelman wrote:
> The problem is, it's not _one_ simply defined "magic" algorithm.  It's 
> an arbitrarily large number of them.
> 
> But if we're going to go with Nico's "simpler" proposal, we need to 
> address the question Niels brought up -- does selecting an AEAD type 
> mean we don't do MAC selection at all, or does it mean we do MAC 
> selection and then don't actually do anything with the resulting MAC?
> 
> One answer is simpler to implement, because it doesn't actually change 
> the selection algorithm at all, but the other provides more 
> interoperability. And, Niels brings up a third possibility of somehow 
> noticing when only an AEAD encryption algorithm will work and filtering 
> out all of the others, which seems really complicated to me.

I can live with both options 1 and 2.  I agree that changing kex 
algorithm selection logic would be more complicated than requiring 
common mac to be found even in the situations where it's eventually 
ignored.  I'd be inclined towards the simpler option.

Additional option might be introducing a mac name (could actually be 
used in ciphers and compressions too) that would be "fail-if-used". 
That would be put to the tail if mac list if aead modes are used as 
possible ciphers.  In case some other mac is selected with aead cipher, 
it's simply dropped, if "fail-if-used" is selected with aead, it's 
dropped as well.  In case "fail-if-used" mac gets selected with a 
traditional cipher it will fail in some implementation dependant way.

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 09:11:01 -0500

> Yup, see http://oakland09.cs.virginia.edu/papers.html.

Thanks.

> my earlier posts in this thread, and I still owe people some replies for one

Well, sortof.  TLS says it does not protect against traffic analysis,
therefore we consider traffic analysis attacks out of scope -- there are
no traffic analysis attacks against TLS by definition.  That's not
exactly a fair comparison.

That said, I think encrypted packet lengths are more trouble than
they're worth and don't actually suffice for protection against traffic
analysis, which makes you wonder what the heck was ever the point.

For example, say I'm prompted for a password, echo-off, in a pty
session, and my client sends keystrokes one at a time.  Well, any
eavesdropper can notice that pattern and determine the length of my
password.  The server can detect this and defeat this by adding IGNORE
messages to emulate echo-on, and the client can add random padding or
else gather more keystrokes before sending them -- but all of this is
not-crypto and if it's needed it's needed because encrypting the packet
length was insufficient.

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 09:04:35 -0500

> additional mac, or fail because there's no common mac?

The former.

Nico
--

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 16 Apr 2009 10:36:50 -0400

--On Thursday, April 16, 2009 05:22:40 PM +0300 "Timo J. Rinne" 
<[email-masked]> wrote:

> Additional option might be introducing a mac name (could actually be used
> in ciphers and compressions too) that would be "fail-if-used". That would
> be put to the tail if mac list if aead modes are used as possible
> ciphers.  In case some other mac is selected with aead cipher, it's
> simply dropped, if "fail-if-used" is selected with aead, it's dropped as
> well.  In case "fail-if-used" mac gets selected with a traditional cipher
> it will fail in some implementation dependant way.

That's an interesting approach.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 16 Apr 2009 10:50:10 -0400

--On Thursday, April 16, 2009 09:30:30 AM -0500 Nicolas Williams 
<[email-masked]> wrote:

> On Thu, Apr 16, 2009 at 10:20:46AM -0400, Jeffrey Hutzelman wrote:
> No, it's not.  I'm perfectly happy to have the problem that Niels
> pointed out.

Yes, it is.  The twist you describe is complicated.  It's a funny special 
case.  What's going to happen when we have another funny special case?

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 09:30:30 -0500

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 09:51:12 -0500

> case.  What's going to happen when we have another funny special case?

Like I said: I'm happy to have that problem.  But also, we are not
likely to have a new funny special case soon enough that we can't, in
the interim work out a generic KEX extensibility scheme.

---

From: der Mouse <[email-masked]>
Date: Thu, 16 Apr 2009 11:13:01 -0400 (EDT)

>> To improve the situation we need to twist the KEXINIT abstraction a
>> bit more [...]  IF a non-AEAD cipher is chosen AND there was no
>> common MAC AND there was a common AEAD cipher THEN re-compute the
>> cipher selection ignoring all non-AEAD ciphers.

This rule interacts very badly with the implementation of
any other encryption algorithm that similarly wants to ignore MACs,
especially if it defines an analogous rule.

> Ugh.  This is starting to get complicated.

Indeed.  My "next special case" has shown up already and the first one
hasn't even been settled yet.  I stand by my stance that this approach
will rapidly turn kex into an incomprehensible (and, of course,
unmaintainable) mess of cross-linked dependencies.

For implementers who are determined to do it anyway - don't forget,
when deciding what to implement, to also think about interop with
implementations that haven't heard of, or decided not to implement,
whatever you settle on.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Thu, 16 Apr 2009 11:26:18 -0400 (EDT)

>> There are a lot of non-data messages that are full of uint32 fields
>> that typically have at least 3/4 of their bits zero.  Some even use
>> a 32-bit field to carry one bit of information.  Compressing these
>> is valuable from the point of view of providing higher-entropy data
>> as the cleartext to the encryption algorithm and therefore making it
>> harder to attack.
> Uhh, so breaking AES is going to be possible if the content is
> uncompressed but not if it's compressed? :-)

Perhaps.  As a cryptographer I'm strictly a dilettante, but even I know
that the lower the entropy of the plaintext, the easier it is to attack
an encryption algorithm.  Knowing that most of the bits are zero could
be the edge that makes the difference between working and failing for
some attack - especially since you mostly know which ones they are (the
high-order bits of most uint32s).

> That's a pretty theoretical objection...

At the moment, yes.  But attacks only get better....

> In terms of compression, I'm not so sure that compressing the headers
> is a good idea.

I'm not sure either.  I suspect the right thing to do is to implement
various alternatives, instrument them all, and see what happens in real
use.  (Actually, I'd be tempted to implement _all_ the alternatives and
record the results: that is, on the sending end, run all these
different compression algorithms and record the statistics - what
actually gets sent on the wire can be whichever one is most convenient,
since it's the statistics of the cleartext that are of interest.)  I
have my guesses, of course, and you clearly have some of your own, but
nothing beats actual measurements.

> It could also be rather situation-specific, for example if you're
> using SSH for secure logging then having the nice compressible stream
> of text records periodically broken up by binary blobs probably isn't
> a good idea.

Perhaps - but, since consecutive log records are usually mostly
independent, it probably won't do too much damage, either.

Yes, it could well be situation-specific.  If I do the "do them all and
instrument" thing, I may leave the instrumentation infrastructure in
place in the shipped version and provide a way for people to turn it on
and collect the data to figure otu which form of compression works best
for their particular application.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 10:45:50 -0500

> high-order bits of most uint32s).

Lossless compression does not alter the amount of entropy in a message.
Therefore deterministic use/non-use of compression ought to have no
impact on known-plaintext attacks.

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 10:58:11 -0500

> especially if it defines an analogous rule.

Surely such an encryption algorithm would be an AEAD algorithm,
therefore there is no such interaction (since the rule still applies).

You're making this more complicated than it has to be.

> unmaintainable) mess of cross-linked dependencies.

"Incomprehensible", no, "complex", yes.  But that's what we have to work
with.  I don't see Jeff's proposal for a KEX_OPTION packet type as
making any of this less complex now, but it is a way forward the next
time we need it.

Of course, Jeff's KEX_OPTION packet type needs negotiation too!  Jeff
proposed using the comment field of the SSH version message.  But I
think I will not be alone in rejecting that idea.  We can only really
use the reserved uint32 field for the KEX_OPTION packet type.  Which
means that we MUST first fix the handling of the reserved uint32 field.
Which means we can only really use alg names for AEAD negotiation right
now, and must also fix the reserved uint32 field now so we can use it
the next time around.

It's not how I'd design the protocol from scratch, y'know.  It's what
we've got to work with.

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 10:49:23 -0500

> This makes sense to me. I'd prefer this option, then. The name could

That's fine with me too.  Though I don't see how it solves this problem:

Client ciphers = des3-cbc, aes-gcm
       MACs    = hmac-md5, none-if-aead
Server ciphers = des3-cbc, aes-gcm
       MACs    = hmac-sha1, none-if-aead

I.e., we still have the problem you found.

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 10:52:43 -0500

> algorithm is selected but there is no mutually-supported MAC algorithm. 

No, the question is irrelevant since it's truly obvious what to do (if
AEAD cipher chosen -> no MAC negotiation takes place).  The real problem
is the unrelated problem that Niels found where the client and server
would choose a non-AEAD cipher but have no common MAC and could have
chosen an AEAD cipher.

> which seems really complicated to me.

See my other replies.

---

From: der Mouse <[email-masked]>
Date: Thu, 16 Apr 2009 11:59:37 -0400 (EDT)

>> Perhaps.  As a cryptographer I'm strictly a dilettante, but even I
>> know that the lower the entropy of the plaintext, the easier it is
>> to attack an encryption algorithm.

True, but it does alter the entropy density (entropy per encryption
block, per byte, per whatever), and that's what results in the effect I
mentioned.

> impact on known-plaintext attacks.

This isn't quite what I understand "known-plaintext" to refer to.  This
is partial and statistical knowledge of the plaintext, whereas
known-plaintext as I understand the term refers to complete knowledge.
Known-plaintext in the sense I understand it, you're right: if you know 
the input bits, it doen't matter whether they come directly from the
protocol engine or from a compression engine.  (Some particular sets of
cleartext bits may make some attacks easier than others, but then we're
heading towards the realm of chosen plaintext.)  But in the partial
sense we have here, it does matter: in the extreme, consider, say, a
block cipher with block size 64, and consider feeding it a stream of 64
uint32s each of which is 0 or 1, versus feeding it a single blob of 64
bits carrying the same information.  In the former case, if you think
maybe you know the key, it's fairly easy to check reliably, even
knowing nothing about the data bits; in the latter, it's theoretically
impossible to tell whether you have the right key if you don't know
anything about the cleartext.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: der Mouse <[email-masked]>
Date: Thu, 16 Apr 2009 14:13:42 -0400 (EDT)

>>>> IF a non-AEAD cipher is chosen AND there was no common MAC AND
>>>> there was a common AEAD cipher THEN re-compute the cipher
>>>> selection ignoring all non-AEAD ciphers.
>> This rule interacts very badly with the implementation of any other
>> encryption algorithm that similarly wants to ignore MACs, especially
>> if it defines an analogous rule.

You truly believe that, for the entire lifetime of SSHv2, nobody will
ever come up with another way to roll tamper-evident-ness in with
encryption (or at least won't want to use such a thing with SSHv2)?

I find that...dubious, at best.

> Of course, Jeff's KEX_OPTION packet type needs negotiation too!

I don't see why.  Send it and let it get handled or rejected.

(I do not favour mollycoddling implementations that can't be bothered
to implement the spec's mandate for handling packet types they don't
understand.  Such implementations are broken, and need to be widely
shown to be, and recognized as, broken.  Compatability hacks in
implementations are an implementation matter, but there's no need to
tie the hands of protocol design for the sake of tolerating
implementation bugs, especially ones this severe.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 13:20:12 -0500

> I find that...dubious, at best.

No, I'm saying that from where we stand such an algorithm would like
like any other AEAD algorithm.

> I don't see why.  Send it and let it get handled or rejected.

Hmmm, I have to re-read the spec.

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 16 Apr 2009 13:16:29 -0500

> per-packet compression flag :)

Oh!  I agree, that'd be nice.

---

From: der Mouse <[email-masked]>
Date: Thu, 16 Apr 2009 14:48:36 -0400 (EDT)

> Hmmm, I have to re-read the spec.

There's a spec?  Perhaps we're talking about two different things.  I
didn't see any mention of a KEX_OPTION packet upthread, so I took this
to be referring informally to an informally proposed new packet type.
If there's a real proposed spec and I was just unaware of it (perhaps I
missed it upthread?), then I may need to retract that, since I haven't
read the spec.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

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

Jeffrey Hutzelman <[email-masked]> writes:

> Yes, it is.  The twist you describe is complicated.  It's a funny
> special case.  What's going to happen when we have another funny
> special case?

We already have another one, which we may learn from: The rules for
the keyexchange algorithm! (Section 7.1, RFC 4253)

I have now reread these rules. Mirroring these rules for the current
situation, we get the following:

         The following algorithm MUST be used to choose a an
         encryption method (independently for each direction): Iterate
         over client's encryption algorithms, one at a time. Choose
         the first algorithm that satisfies the following conditions:

         +  the server also supports the algorithm,

         +  if the algorithm is not an aead algorithm (i.e., needs
            separate mac), there is a mac algorithm, different from
            "none-if-aead", on the server's list that is also
            supported by the client.

         When processing the mac algorithm lists, consider the client's
         mac algorithms, one at a time. Choose the first algorithm
         that satisfies the following conditions:

         +  the server also supports the algorithm,

         +  if the selected encryption algorithm is not of aead type,
            the algorithm must be different from "none-if-aead".

The final condition matters only if "none-if-aead" occurs on both the
client's and the server's lists, which is why implementations that
don't support aead need not know about the updated selection rules.

A different, more general, way to state the same selection rules would
be as follows:

  1. When an algorithm on a lists of type A has a requirement on the
     selection of algorithms of a different type B (current examples:
     A = key exchange, B = host key algorithm, or A = encryption, B =
     mac in the same direction), check if there is some common entry
     on the client's and server's type B list that satisfy the
     requirement. If it does not, delete the entry in question from
     list A and continue.

  2. If the type A algorithm that is selected has a requirement on the
     type B selection, delete all entries on the type B lists that
     don't satisfy the requirement. By (1), the remaining lists have
     at least one common element.
     
As long as we don't introduce any circular dependencies, this should
work just fine. (I haven't thought much about the case that A depends
on B which depends on C, but as long as there are no cycles, I'd
expect that should not cause any fundamental problems).

We could ignore the problem for AEAD, but I think there's a value in
consistency. The problem key exchange / host key is very similar, and
then it makes a lot of sense, at least to me, to reuse the same
solution.

Again, it would be nice to hear from someone who has actually
implemented the above logic if it works well in practice. (My
implementation uses only signature algorithms and only dh keyexchange,
so it's not an issue, so up to now, I haven't cared much about it).

Regards,
/Niels

---

From: der Mouse <[email-masked]>
Date: Thu, 16 Apr 2009 16:42:29 -0400 (EDT)

> A different, more general, way to state the same selection rules
> would be as follows: [...]

> [I]t would be nice to hear from someone who has actually implemented
> the above logic if it works well in practice.  (My implementation
> uses only signature algorithms and only dh keyexchange, so it's not
> an issue, so up to now, I haven't cared much about it).

Well, I too have not implemented algorithms that let me test it fully
(only signature-needing kex and signature-providing hostkey), but I
think I've implemented kex/hk selection in full generality, and found
it not _that_ big a deal.  (See recv_kexinit in transport.c in the
moussh source if you're curious.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 18 Apr 2009 23:30:00 +1200

der Mouse <[email-masked]> writes:

>If I do the "do them all and instrument" thing, I may leave the 
>instrumentation infrastructure in place in the shipped version and provide a 
>way for people to turn it on and collect the data to figure otu which form of 
>compression works best for their particular application.

That'd be interesting data to have.

(I think that if people really want to squeeze out every byte, and in 
particular if they're dealing with lots of small packets like the keystrokes 
for this email where the headers are much larger than the data, the best 
option is to use a protocol-aware compressor like PPP's header compression, 
where you can reduce most of the packet header to a single flag 'same as the 
last packet', except for the length field.  Without thinking about it too much 
you could probably get the entire header into about 32 bits, including a flag 
for piggybacked window-adjusts to get rid of those as well.  OTOH how many
bytes to you really want to save in exchange for this protocol redesign?).

Peter.

---

From: der Mouse <[email-masked]>
Date: Sat, 18 Apr 2009 09:36:14 -0400 (EDT)

>> instrumentation infrastructure in place in the shipped version and
>> provide a way for people to turn it on and collect the data to
>> figure out which form of compression works best for their particular
>> application.

My own opinion exactly.

> particular if they're dealing with lots of small packets like the
> keystrokes for this email where the headers are much larger than the
> data, the best option is to use a protocol-aware compressor like
> PPP's header compression, [...]

Agreed.  But that "target market", if you will, is not really what this
was aimed at.  I more had this in mind for bulk data transfer, where
the question is whether the data's statistics match the headers' well
enough for compressing them all together to win over compressing just
the data - or, hm, compressing the headers and data with two different
contexts, come to think of it.

> Without thinking about it too much you could probably get the entire
> header into about 32 bits, including a flag for piggybacked
> window-adjusts to get rid of those as well.

SSH doesn't have piggybacked window-adjusts.  Or were you thinking of
effectively adding them, by giving the compression code special
handling for the (probably common, especially for interactive use) case
of a window adjust with an immediately following small data packet?

> OTOH how many bytes to you really want to save in exchange for this
> protocol redesign?

What protocol redesign?  All this stuff can be done within existing
SSHv2, as compression algorithms.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: [email-masked] (Niels Möller)
Date: Sat, 18 Apr 2009 21:31:11 +0200

> arbitrary remote attackers is too big a risk to take.

Is it primarily the attack surface of inflate (uncompressing) untrusted
data that worries you, or also deflate (compressing)?

The reason I ask is that

* Inflate should be inherently less complex to implement than deflate,

* I'm awere of an alternative (but unfortunately proprietary)
  implementations of inflate that is claimed to be smaller and simpler
  than the original one in zlib.

Regards,
/Niels

---

From: "denis bider \(Bitvise\)" <[email-masked]>
Date: Sat, 18 Apr 2009 21:48:36 -0400

I'm kinda surprised by the attitude "there's only one zlib".

We use the Crypto++ implementation, which is independent of zlib, and is 
freely available.

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 19 Apr 2009 17:41:03 +1200

[email-masked] (Niels =?iso-8859-1?Q?M=F6ller?=) writes:

>Is it primarily the attack surface of inflate (uncompressing) untrusted data
>that worries you, or also deflate (compressing)?

Purely inflate.  I'd be kinda surprised if you could cause problems with input
data, at best you can cause O( n^2 ) behaviour until the hash chain truncation
takes effect.

>* Inflate should be inherently less complex to implement than deflate,

Have a look at the source code :-).

>* I'm awere of an alternative (but unfortunately proprietary) implementations
>of inflate that is claimed to be smaller and simpler than the original one in
>zlib.

Also less audited/less exposed to attack and scrutiny.  Insert standard open-
vs. closed-source argument here.  The real issue though isn't to try and
figure out which one is less risky, but a basic "don't do that, then".

Peter.

---

From: Nicolas Williams <[email-masked]>
Date: Sun, 19 Apr 2009 15:18:03 -0500

> figure out which one is less risky, but a basic "don't do that, then".

+1.

Don't compress/uncompress in privileged code.  By and large it's easy to
separate privilege post-authentication (since privilege will be needed
only for things like logout processing).  So postponing compression till
after authentication would be a good thing.  Besides, there's nothing
much worth compressing between version banner exchange, key exchange and
authentication (well, if we keep adding algs then KEXINIT may become
significantly compressible :)

Nico
--

---

From: [email-masked] (Niels Möller)
Date: Mon, 20 Apr 2009 09:45:24 +0200

> Have a look at the source code :-).

Summing line counts of inflate, inflate_fast and inflate_table, I get
some 1134 lines, of quite complex code.

> figure out which one is less risky, but a basic "don't do that, then".

I'm of course not seriously considering using a proprietary zlib
implementation. My thinking was rather that maybe, inflate can be
implemented with much less complexity? Either in general, or for the
context that matters for ssh and similar protocols (we can pass a full
ssh message to the decompressor, and we can pass an output buffer
matching the maximum message size. Then most of the state-machinery in
the zlib implementation is unnecessary).

Regards,
/Niels

---

From: Nicolas Williams <[email-masked]>
Date: Tue, 21 Apr 2009 11:42:42 -0500

I've confirmed with an expert who should know (Darren Moffat) that the
PKCS#11 AEAD interfaces DO NOT allow retrieval of any plaintext before
the authentication tag has been found and verified.

It makes sense even for AEAD modes which can be seen composed
generically with a MAC (and especially for those that can't be).
Suppose we do something like C_DecryptInit(), C_DecryptUpdate(), ...,
C_DecryptFinal(), and the first bit of input is just long enough to
contain an authentication tag, then the mechanism can't know whether it
is ciphertext or a tag until more of the message is provided via
C_DecryptUpdate().

Nico
--

---

From: [email-masked] (Niels Möller)
Date: Thu, 30 Apr 2009 13:41:30 +0200

"denis bider \(Bitvise\)" <[email-masked]> writes:

> We use the Crypto++ implementation, which is independent of zlib, and
> is freely available.

In order to figure out what complexity really is needed, I had to
write my own implementation. I'm not going to claim that it's less
buggy than zlib (it's the result of a few evenings work and not
thouroghly tested), but it's certainly a lot smaller than zlib and
(imo) well designed and fairly readable. See
http://www.lysator.liu.se/~nisse/archive/inflate-0.2.tar.gz. For now,
it's GPL:ed.

The interesting files, huffman.c and inflate.c, are in total 674
lines, or 490 excluding the comments (2015 and 1467 for the
corresponding files in zlib, inflate.c, inffast.c and inftrees.c).
Performance is a factor two slower than the ordinary zcat program.

Best regards,
/Niels