Subject: Key Re-Exchange

From: Markus Friedl <[email-masked]>
Date: Wed, 4 Apr 2001 01:52:43 +0200

hi,

I have some questions regarding the 'Key Re-Exchange' (aka rekeying):

is it true that no application data may be sent during key re-exchange?

how is this 'during key re-exchange' defined?

i think that that the re-exchange starts when a KEXINIT message has
been both sent _and_ received.

so, if you initiate the re-exchange, you have to wait for the KEXINIT
from the peer, but since there might be some more packets one the
wire i might get these messages before i get the KEXINIT.

the problem here is that i cannot tell whether my KEXINIT message
did already arrive at the peer or whether the peer just ignores the
KEXINIT message and just keeps sending applications messages.

am i missing something?

what are other implementations doing?

i think that the paragraph about the re-exchange should to be extended
in the current transport-draft.

-markus

---

From: Mats Andersson <[email-masked]>
Date: Wed, 4 Apr 2001 10:53:09 +0200 (MEST)

Hi,

I agree that the draft might improve on clarity here.

> KEXINIT message and just keeps sending applications messages.

transport-draft says:
...
Key exchange ends by each side sending an SSH_MSG_NEWKEYS message.
...
This message is the only valid message after key exchange, in addition to
SSH_MSG_DEBUG, SSH_MSG_DISCONNECT and SSH_MSG_IGNORE messages. 
...
Implementations MUST NOT accept any other
messages after key exchange before receiving SSH_MSG_NEWKEYS.
...
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
Secure Shell transport layer.
...

This seems to imply that no other messages than the KEX messages should be
sent during the re-exchange (the state is not explicitly defined though,
or rather the definition is spread across several paragraphs).

> in the current transport-draft.

En exact definition of the state "key exchange" (valid for both "initial"
key exchange and later re-exchange) could be given in a short paragraph
like:

...
The transport layer enters key exchange state as soon as a KEXINIT message
is received. When this message is received, a party MUST respond with its
own SSH_MSG_KEXINIT message except when the received SSH_MSG_KEXINIT
already was a reply. During key exchange the only valid messages, both for
reception and transmission, are the KEX packets (range 30-49) and
SSH_MSG_DEBUG, SSH_MSG_DISCONNECT and SSH_MSG_IGNORE. Any other messages
SHOULD be considered a fatal protocol error. The key exchange state ends
by each side sending an SSH_MSG_NEWKEYS message.
...

This should probably go somewhere into paragraph 5.1. "Algorithm
Negotiation". And be explicitly referred in the paragraph 7 "Key
Re-Exchange".

> what are other implementations doing?

We disable and flush the transmitter queue directly when a KEXINIT is
received and then send a KEXINIT directly (if it was not a "reply" to our
own KEXINIT). The transmitter is re-enabled directly after the NEWKEYS has
been sent. It is the exact same code for "initial" key exchange as for
re-exchange (minus the session id). This seems to work well with SSH Inc's
implementation (which is the only one we have tried it with).

Cheers,

/Mats

---

From: Mats Andersson <[email-masked]>
Date: Wed, 4 Apr 2001 11:55:40 +0200 (MEST)

Ouch,

> I agree that the draft might improve on clarity here.

Shouldn't have said that when beeing ambigious myself! :-)

> by each side sending an SSH_MSG_NEWKEYS message.

Should be something like:

The transport layer receiver enters key exchange state when it has
received a KEXINIT. Symmetrically the transmitter enter key exchange state
when it has sent a KEXINIT message. When a KEXINIT message has been
received, a party MUST send a KEXINIT message if its transmitter isn't
already in key exchange state. During key exchange the only valid
messages, both for reception and transmission, are the KEX packets (range
30-49) and SSH_MSG_DEBUG, SSH_MSG_DISCONNECT and SSH_MSG_IGNORE. Any other
messages SHOULD be considered a fatal protocol error. The key exchange
state in the transmitter ends when a SSH_MSG_NEWKEYS is sent.
Symmetrically the key exchange state ends in the receiver when the
SSH_MSG_NEWKEYS is received.

(incidentally, this is how I described our implementation though I'm
better at writing code than definitions of what it does :-).

Cheers,

/Mats

---

From: Simon Tatham <[email-masked]>
Date: Wed, 04 Apr 2001 10:46:17 +0100

> KEXINIT message and just keeps sending applications messages.

Well, if _you_ stop sending application messages after sending your
own KEXINIT, then the peer can only ignore it for a limited time,
because you won't be sending WINDOW_ADJUST messages. So any data the
peer is still trying to transmit to you will eventually dry up as
the windows all go down to zero, and then the peer will _have_ to
pay attention to KEXINIT because it's the only thing left it can
usefully do.

It seems to me that should be sufficient.

 - Send KEXINIT.
 - Process incoming non-KEXINIT messages. If any of them require
   replies, such as WINDOW_ADJUST, queue the reply messages
   unencrypted to be sent after the re-exchange.
 - When the peer sends KEXINIT, do the key exchange.
 - After you send NEWKEYS, encrypt and send your reply messages.

Does that make sense? Have I missed something? 

Cheers,
Simon
-- 
Simon Tatham         "I'm going to pull his head off. Ear by ear."
<[email-masked]>                          - a games teacher

---

From: [email-masked] (Niels M�ller)
Date: 04 Apr 2001 11:50:32 +0200

> is it true that no application data may be sent during key re-exchange?

I'd say not true (see below).

> been both sent _and_ received.

That sounds like the only reasonable definition. And the exchange ends
with the SSH_MSG_NEWKEYS message (which doesn't happen at the same
time for both directions).

> KEXINIT message and just keeps sending applications messages.

I think you must process the application messages as normal. The peer
should eventually respond to the KEXINIT. If it doesn't within some
resonable time (say between your key reexchange interval and a tenth
of that), you may consider it a protocol error and disconnect. 

> what are other implementations doing?

lsh currently never *initiates* re-exchange, but besides from that
there are four states:

  /* A KEX_INIT msg can be accepted. This is true, most of the time. */
  #define KEX_STATE_INIT 0

In this state, we may or have not sent an KEXINIT ourselves. Packets
other than KEXINIT are processed normally. On reception of KEXINIT, we
enter KEX_STATE_IGNORE or KEX_STATE_IN_PROGRESS.

  /* Ignore next packet */
  #define KEX_STATE_IGNORE 1

Special case to ignore a bad guess from the peer. Obviously, 
an application data packet doesn't make sense in this state.

  /* Key exchange is in progress. Neither KEX_INIT or NEWKEYS messages
   * can be received */
  #define KEX_STATE_IN_PROGRESS 2

In this state, application packets are processed normally. I believe
lsh also expects the peer to accept application data in this state. I
also think this is reasonable thing to do: it should be easy to handle
for an implementation, and if application data isn't allowed, the
connection will appear to the user to freeze. Key re-exchange should
be transparent to the user.

  /* Key exchange is finished. A NEWKEYS message should be received, and
   * nothing else. */
  #define KEX_STATE_NEWKEYS 3

Currently, lsh only accepts NEWKEYS and DISCONNECT in this state. It
ought to also accept IGNORE and DEBUG as well.

The code in question is in connection_handle_packet in
http://www.lysator.liu.se/~nisse/lsh/src/connection.c.

> in the current transport-draft.

Sounds like a good idea. I also believe application data should be
allowed during most of the key exchange. More precisely, at all times
except

  1. Between a KEXINIT message and any guessed packed.
  2. Between the final keyexchange message and NEWKEYS.

For the initial keyexchange, application data MUST not be sent before
NEWKEYS, but that is just because they wouldn't be properly encrypted;
from a pure protocol point of view, application data should be allowed
even then.

Finally, I don't think "application data" is a good term to use. It
sounds like SSL speak. The spec should say which messages, or ranges
of messages, that are allowed or disallowed at any time.

Regards,
/Niels

---

From: Markus Friedl <[email-masked]>
Date: Wed, 4 Apr 2001 12:00:54 +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.

---

From: [email-masked] (Niels M�ller)
Date: 05 Apr 2001 09:46:46 +0200

I wrote:

> I also believe application data should be allowed during most of the
> key exchange. More precisely, at all times except
> 

I have thought some more about this, and (2) is not quite consistent
with the way I'd like things to work.

The reason I want application data to be allowed is that I want an
implementation to be able to process events immediately when they
happen. For example, if I have some buffered data for some forwarded
socket, and then I happen to write some of it, I want to be able to
send a WINDOW_ADJUST message right away.

If messages like this can't be sent during key (re)exchange, I need
some extra packet queue besides my output buffer that contains raw
encrypted data, and to the user, the connection will appear to freeze
completely during the key exchange.

The restriction (1) causes no problem; if any guessed packet is to be
sent, it is known by the time the kexinit is sent, so it can be pushed
into the output buffer right away.

The restriction (2) works fine for the part sending the final
keyexchange message (for dh exchange, that's the server sending a
KEXDH_REPLY), at this time, session keys are known and NEWKEYS can be
sent right away. But it doesn't work for the client, whose last
keyexchange packet is KEXDH_INIT. When this is sent, session keys are
not yet known, so it doesn't make much senss to send NEWKEYS. Instead
the client must wait for the KEXDH_REPLY, and during that time, to
satisfy (2), any packets resulting from events on channels must be put
on hold.

This doesn't feel quite right. Is there any reason we can't relax (2),
and in general allow interleaving of keyexchange packets and other
packets?

/Niels