Subject: Re: Some questions about "SSH Transport Layer Encryption Modes"

From: [email-masked] (Peter Gutmann)
Date: Sun, 19 Oct 2003 01:56:28 +1300

Markus Friedl <[email-masked]> writes:
>On Sat, Oct 18, 2003 at 06:56:35PM +1300, Peter Gutmann wrote:
>>Markus Friedl <[email-masked]> writes:
>>>i think this has been discussed before.
>>
>>Hmm, I think "debated without clear resolution" might be a better description,
>>if you're referring to the debate from about two years ago.  Specifically, the
>>exact message/data flow was never totally resolved.
>
>Hm, AFAIK we agreed, that after sending KEXINIT you MUST NOT send messages of
>type > 49 (i.e. only transport layer messages are allowed) until you send
>NEWKEYS.

I was under the impression that the debate had simply fizzled out.  The
specification certainly hasn't been clarified (it's remained unchanged since
the -02 draft of late 1997), and that would be the definitive reference.

Peter.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Sat, 18 Oct 2003 18:23:25 -0400

On Sunday, October 19, 2003 01:56:28 +1300 Peter Gutmann 
<[email-masked]> wrote:

>>> Hmm, I think "debated without clear resolution" might be a better
>>> description, if you're referring to the debate from about two years
>>> ago.  Specifically, the exact message/data flow was never totally
>>> resolved.
>>
>> Hm, AFAIK we agreed, that after sending KEXINIT you MUST NOT send
>> messages of type > 49 (i.e. only transport layer messages are allowed)
>> until you send NEWKEYS.
>
> specification certainly hasn't been clarified (it's remained unchanged
> since the -02 draft of late 1997), and that would be the definitive
> reference.

The document does seem a little murky in this area.  Section 5.3 clearly 
states:

      Implementations MUST NOT accept any other messages after key
      exchange before receiving SSH_MSG_NEWKEYS.

But it's unclear whether we're talking about all key exchanges, or just 
_initial_ key exchange.  However, section 7, discussing rekey, says:

      Re-exchange is processed identically to the initial key exchange,
      except for the session identifier that will remain unchanged.
...
      More application data may be sent after the SSH_MSG_NEWKEYS packet
      has been sent; key exchange does not affect the protocols that lie
      above the SSH transport layer.

That last sentence is _extremely_ ambiguous.  It could be read to mean the 
behaviour which Markus described, in which application data (and, in fact, 
anything above the transport layer) is simply suspended until rekeying is 
complete.  Or, it could be read to mean that application data continues to 
flow during the rekey.  I think if I were a new SSH implementor, working in 
a vacuum, I'd read it to mean that higher-layer protocols are _not_ 
suspended.  So if that's not what we mean, then maybe this needs to be 
clarified.  Bleah.

-- Jeff

---

From: Markus Friedl <[email-masked]>
Date: Sun, 19 Oct 2003 12:31:12 +0200

> suspended.  So if that's not what we mean, then maybe this needs to be 

but that could result in the higher layer using the
old keying material forever.

I wrote earlier:

> Date: Wed, 4 Apr 2001 12:00:54 +0200
> From: Markus Friedl <[email-masked]>
> To: [email-masked]
> Cc: Mats Andersson <[email-masked]>
> Subject: Re: Key Re-Exchange
> Message-ID: <[email-masked]>
> References: <[email-masked]> <[email-masked]>
> In-Reply-To: <[email-masked]>; from [email-masked] on Wed, Apr 04, 2001 at 11:55:40AM +0200
>
>
> I think that the draft should point out that a sender MUST NOT send
> non-KEX messages after he _sent_ a KEXINIT message. he has to delay all
> non-KEX messages until he has sent the NEWKEYS message.
>

I remember a mail from Tatu about this issue, but I
cannot find this right now...

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Sun, 19 Oct 2003 12:35:50 -0400

On Sunday, October 19, 2003 12:31:12 +0200 Markus Friedl 
<[email-masked]> wrote:

>> That last sentence is _extremely_ ambiguous.  It could be read to mean
>> the  behaviour which Markus described, in which application data (and,
>> in fact,  anything above the transport layer) is simply suspended until
>> rekeying is  complete.  Or, it could be read to mean that application
>> data continues to  flow during the rekey.  I think if I were a new SSH
>> implementor, working in  a vacuum, I'd read it to mean that higher-layer
>> protocols are _not_  suspended.  So if that's not what we mean, then
>> maybe this needs to be
>

Yes, it does.  Of course, that would also happen if neither side decided to 
do a rekey.  Once one side starts a rekey, it could certainly _choose_ not 
to send any application data until it sends a SSH_MSG_NEWKEYS.  But as I 
read the document, it should be prepared to continue to receive application 
data using the old keys more or less indefinitely.  This isn't an interop 
problem; it just means that one side can choose never to take new keys into 
use and instead continue to use the old keys for "too long".

That said, I'm not actually advocating either behaviour over the other. 
However, I do think the document needs clarification in this regard.  I've 
been active in this working group for a while now; I've written the 
specification for a key exchange method, and reviewed a special-purpose 
host key algorithm which depends on behaviour during a rekey.  Until this 
discussion started, I believed the spec permitted higher-layer protocols to 
continue during a rekey.  If I made that mistake, I wonder how many 
implementors also did.

> I wrote earlier:

Yes, your mail was quite clear on what the behaviour should be.  But email 
isn't good enough; future implementors (and probably even some present 
ones) are going to work from the spec, not the mailing list discussion.

-- Jeff

---

From: Bill Sommerfeld <[email-masked]>
Date: Sun, 19 Oct 2003 19:51:58 -0400

So, it looks like the proper repair here is to clearly document what's
actually implemented and deployed -- implementations must suspend
transport of user data while rekey negotiation is in progress.

This is not optimal but it works.

For those still not satisfied, I invite anyone who wants
"seamless"/non-blocking rekeying to write and submit a draft
documenting how to negotiate the use of a different key cutover
strategy with a consenting peer.

						- Bill

---

From: Derek Fawcus <[email-masked]>
Date: Mon, 20 Oct 2003 13:09:49 +0100

> strategy with a consenting peer.

Well one problem here is that I believe there is at least one
implementation, which does not respond with SSH_MSG_UNIMPLEMENTED
to unknown messages.

So the (obvious) approach of sending a new Transport Layer message to
negotiate it wouldn't work straight away.

So how about the following (would need fleshing out):

#define SSH_MSG_NONBLOCK_REKEY 22

SSH_MSG_NONBLOCK_REKEY
boolean response

Then at some point early in the connection,  this message is sent followed
by one which we expect to get a response to.  If we get an UNIMPLEMENTED,
fair enougth we know it's not supported.  If we get the response to the
subsequent packet,  again it's not supported.  If we get this packet
with the response flag,  it is supported.

I'd guess one convenient place to send the message (for a client) would
be between the initial NEWKEYS and the SERVICE_REQUEST.

So client sends:

NEWKEYS,  NONBLOCK_REKEY(response=FALSE),  SERVICE_REQUEST

and expects to get back one of:

NEWKEYS,  NONBLOCK_REKEY(response=TRUE),   SERVICE_ACCEPT
NEWKEYS,  UNIMPLEMENTED,   SERVICE_ACCEPT
NEWKEYS,  SERVICE_ACCEPT

There could also be a DISCONNECT in there as normal if the service was
unacceptable.

The question is would anyone DISCONNECT because they didn't understand
the NONBLOCK_REKEY packet?

Theoreticaly either end could send the NONBLOCK_REKEY message,   and
they could pass in transit,  so one would have to be willing to cope
with a request where one wanted a response.  However this could be
dealt with.

Actually,  thinking about it.  Sending the message before the KEXINIT
message may be better - then either end can announce it's support for
this.  So one would have:

NONBLOCK_REKEY(response=FALSE), KEXINIT, ...

and expect back one of:

NONBLOCK_REKEY(response=TRUE),  NEWKEYS, ...
UNIMPLEMENTED, NEWKEYS, ...
NEWKEYS, ...

Thoughts?

DF

---

From: Jon Bright <[email-masked]>
Date: Mon, 20 Oct 2003 14:43:02 +0200

> implementation, which does not respond with SSH_MSG_UNIMPLEMENTED

I've no direct opinion on the rekeying issue, but I don't believe it's 
unreasonable to treat such implementations as broken and exclude them 
from discussions about extensions.  There is, however, a second point 
against using SSH_MSG_UNIMPLEMENTED, namely that there's no indication 
within the message about *which* message was unimplemented.  Short of 
keeping buffers of what's been sent and working out which packet is a 
response to what, which is probably impractical and certainly 
unpleasant, it's not possible to use .._UNIMPLEMENTED for implementing 
extensions anyway.

-- 
Jon Bright
Silicon Circus Ltd.
http://www.siliconcircus.com

---

From: Derek Fawcus <[email-masked]>
Date: Mon, 20 Oct 2003 14:01:40 +0100

On Mon, Oct 20, 2003 at 02:43:02PM +0200, Jon Bright wrote:
> from discussions about extensions.

Well,  I'd have to rescan my mailbox to see who's implementation that was.
But as I recall,  he claimed it was done for security reasons...

I do consider that class of "bug" to be different to the bugs in some
implementations that require workarounds in other implementations.

> There is, however, a second point 
> within the message about *which* message was unimplemented.

Well - there is the sequence number...

> Short of 
> unpleasant,

Well at the point where I suggested sending it,  there would be a pause
anyway.  It's the initial key exchange.  So it would be relatively easy
to keep a record of which sequence number the unknown message was sent
with,  and hence match up the replay.  i.e. no long list of buffers.

However,  we're anticipating that _this_ message may get a response of
unimplemented.  So we record just the sequence numeber of _this_ message,
and if an unimplemented message comes back with this sequence number,
we know it's the one we were anticipating.

Moreover,  the initial key exchange would be done without allowing higher
layer messages between the KEXINIT and NEWKEYS.  Thereafter if this
negotiation (for this extension) worked,  one wouldn't have to track
the sequence numbers again.

> it's not possible to use .._UNIMPLEMENTED for implementing 
> extensions anyway.

Huh?  Why not?   I just sketched out one way to do it.  Or are you
stating that it's ugly to do so,  hence we shouldn't.

One has to ask what purpose UNIMPLEMENTED serves if not as an escape
for extensions.

DF

---

From: Bill Sommerfeld <[email-masked]>
Date: Thu, 23 Oct 2003 19:07:21 -0400

> So one would have:

Can this be done asynchronously, early during connection negotiation
(or perhaps well before the rekey is needed)?  That way, you won't
hang waiting for a response which might never arrive...

					- Bill

---

From: Derek Fawcus <[email-masked]>
Date: Fri, 24 Oct 2003 01:18:22 +0100

> hang waiting for a response which might never arrive...

Yes.  That was the idea.  Do it async before the _initial_ key exchange.
Actually the above does sort of imply any response to the NONBLOCK_REKEY
message would be delayed until the NEWKEYS is about to be sent.  That
wasn't my intention.  I intended that the messages would be replied to
in order,  or at least as soon as possible.

So one sends the sequence above (without waiting betwen the NONBLOCK_REKEY
and the KEXINIT.  At that stage one will do the normal KEXINIT algorithm,
including the specific key negotiation stuff.

So depending upon timing one could have:

C-->S  NB_RKY(FALSE),  KEXINIT,  KEXDH_INIT
C<--S  NB_RKY(TRUE), KEXINIT, KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

C-->S  NB_RKY(FALSE),  KEXINIT,  KEXDH_INIT
C<--S  UNIMP, KEXINIT, KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

C-->S  NB_RKY(FALSE),  KEXINIT,  KEXDH_INIT
C<--S  KEXINIT, KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

    (All of above are simple and distinguishable)

C<--S  KEXINIT
C-->S  NB_RKY(FALSE), KEXINIT,  KEXDH_INIT
       (pause)
C<--S  NB_RKY(TRUE), KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

C<--S  KEXINIT
C-->S  NB_RKY(FALSE), KEXINIT,  KEXDH_INIT
       (pause)
C<--S  UINMP, KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

C<--S  KEXINIT
C-->S  NB_RKY(FALSE), KEXINIT,  KEXDH_INIT
       (pause)
C<--S  KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

    (This is the same,  but generalised with the server optimising it's TX)

C<--S  NB_RKY(FALSE), KEXINIT
C-->S  NB_RKY(FALSE), KEXINIT,  KEXDH_INIT
C-->S  NB_RKY(TRUE)
       (pause)
C<--S  NB_RKY(TRUE), KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

    (Client and server both send it,  server optimised TX)

C-->S  KEXINIT,  KEXDH_INIT
C<--S  NB_RKY(FALSE), KEXINIT, KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NB_RKY(TRUE), NEWKEYS

C-->S  KEXINIT,  KEXDH_INIT
C<--S  NB_RKY(FALSE), KEXINIT, KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  UNIMP, NEWKEYS

C-->S  KEXINIT,  KEXDH_INIT
C<--S  NB_RKY(FALSE), KEXINIT, KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

    (Server initiates it)

C<--S  NB_RKY(FALSE), KEXINIT
C-->S  KEXINIT,  KEXDH_INIT
       (pause)
C<--S  KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NB_RKY(TRUE), NEWKEYS

C<--S  NB_RKY(FALSE), KEXINIT
C-->S  KEXINIT,  KEXDH_INIT
       (pause)
C<--S  KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  UINMP, NEWKEYS

C<--S  NB_RKY(FALSE), KEXINIT
C-->S  KEXINIT,  KEXDH_INIT
       (pause)
C<--S  KEXDH_REPLY, NEWKEYS
       (pause)
C-->S  NEWKEYS

    (Server initiates,  and optimising it's TX)

A similar analysis applies to dh-group-exchange,  since it ultimately boils
down to an INIT and REPLAY.  I've not looked at the GSS draft (I've no
interest in it),  but the same rules should apply.

A sender of the NONBLOCK_REKEY sends it before sending KEXINIT.  Thereafter
by the time he receives NEWKEYS he'll know from either the messages received,
or a lack of response to the message,  if his peer supports it.  Since in
general both ends have to consider the messages as pipelined rather than
strict command-stop-response,  this should always work.

In fact the response to the NONBLOCK_REKEY (if there is one) could appear
at any point in the messages received from the peer,  as long as it's
before the NEWKEYS message.

So the above sequence would be used during the initial keying session
(where the session id is created).  Either end seeing or sending a
NONBLOCK_REKEY(TRUE),  means that both ends support the facility.
Subsequent rekeys would not have to use the NONBLOCK_REKEY message,
as they already know if it's supported.  However there is no harm
in sending it subsequently,  it's just a waste of time to do so.

Also the above does not burden implementations that don't wish to support
this facility.  Only those that do (and initiate the negotiation),  have
to go to the effort of tracking which packet sequence number they sent 
the NONBLOCK_REKEY message in such that they can determing if the
UNIMPLEMENTED message matches it.

Also the fact that the NONBLOCK_REKEY is sent before encryption and/or
authentication are engaged does not cause any security problems (that
I can see).  The worst that could happen is the initial negotiation
was broken (DOS attack).  It would be possible to prevent this facility
from being used if a MiTM changed/deleted the KEXDH_REPLY(TRUE) message,
but that's just a performance loss,  not a security problem.

DF

---

From: Jacob Nevins <[email-masked]>
Date: Tue, 28 Oct 2003 17:40:40 +0000

> transport of user data while rekey negotiation is in progress.

There doesn't appear to be anything new for this in
draft-ietf-secsh-transport-17.

Should a ticket be raised on rt.psg.com so it's not lost again?

(Tangent: it seems unfortunate that this site requires installation of a
root CA certificate in a browser, and even after that still fails to
verify, at least in IE6.)