Ssh "security hole": proposed fix

I am thinking about the following solution to the issues pointed out
by David Mazieres.

These changes propose solutions to the following problems:
  - replay of password-authenticated sessions
  - corrupt server can use RSA authentication to log into another server

When the client receives SSH_SMSG_PUBLIC_KEY, it computes a 128 bit
(16 byte) value by converting the modulus of the public key into a
stream of bytes, msb first.  The cookie sent by the server is appended
to this stream.  Both sides compute the MD5 of the resulting stream.
This value will be called the "session id".

In the SSH_CMSG_SESSION_KEY message, the first 16 bytes of the session
key (before encryption) are xored with the 16 bytes of the session id.
This does not reveal plain text from the RSA-encrypted part, but binds
the encrypted session key to a specific cookie and server.  This
should eliminate the possibility of replay, because the cookie is
unique for each connection.

In all SSH_CMSG_AUTH_RSA_RESPONSE messages (used both in user and
client host authentication), append the session id to the decrypted
challenge before computing MD5.  The MD5 is computed from the
resulting 48 bytes.  This makes the response bound to the server
cookie and the server key, and should elinate using the same response
for another server.  (Faking the server key is hard, because the
client verifies that it matches the one stored in its database.)

If a server supports this revision of the protocol, it reports its
protocol version as 1.1.  If the server protocol version is 1.0, the
client displays a warning (recommending to update server software) and
uses the old protocol for compatibility.  The client reports the
protocol version that it will use.  The compatibility code will be
removed in a later release.  (The changes are easy to implement
compatibly.)

I would like to receive comments on this.

    Tatu

Well, here is the proposed new ssh protocol as I understand it.

  A -> B: A
  
  B -> A: PKb, PKsb, Cb

    session_id := {PKb, PKsb, Cb}_MD5
  
  A -> B: Cb, {{session_id XOR Kab}_PKsb}_PKb        (*)
  A -> B: {A}_Kab
  A -> B: {PKa}_Kab
  
  B -> A: {{Nb}_PKa}_Kab
  
  A -> B: {{Nb, session_id}_MD5}_Kab

It does seem to solve the two problems I pointed out.  However, I am
troubled by how complicated the protocol is, and how much encryption
is going on.  One of the principles I have heard stated says that more
encryption does not mean more security.  A good example of that seems
be the session key PKsb above.

In line (*) of the protocol, you say the session key (or now I guess
really session_id XOR Kab) is encrypted first with whichever of Kb,
Ksb has the larger modulus.  Under normal circumstances (the ones
depicted above), the first encryption will be with PKsb.  However, if
ever PKb were to come first, then PKsb would be completely vulnerable
to a "man in the middle" attack, and thus would be completely useless.

Wouldn't it make sense to simplify the protocol significantly, so as
to make it easier to understand and easier for us to convince
ourselves of its robustness?  What about something like what follows
this message?

To come up with the protocol I appended, I took your protocol and
stuck the the full context of each message into the message itself, so
that none of the previous problems could occur.  Then I eliminated all
complications like double encryption and challenges that did not add
to the security of the protocol.  Now granted I'm no authentication
expert and could easily have made a mistake here, but at least it will
be easier to catch because the protocol is simpler.  Who know what the
implications of that XOR really are?

David


PREAMBLE:

(1)  A -> B: A

(2)  B -> A: Cb, PKsb, PKb

(3)  A -> B: {Kab}_PKsb, {A, B, Cb}_Kab

(4)  B -> A: {{A, B, Cb, Kab, PKsb}_SKb}_Kab


SSH_AUTH_RHOSTS:

(5)  A -> B:  0

SSH_AUTH_RHOSTS_RSA:
SSH_AUTH_RSA:

(5)  A -> B: {{A, B, Cb, Kab}_SKa, PKa}_Kab

SSH_AUTH_PASSWORD:

(5)  A -> B: {Ka}_Kab