Network Working Group                           Tatu Ylonen <ylo@ssh.fi>
INTERNET-DRAFT                               SSH Communications Security
draft-ietf-secsh-transport-01.txt                          July 30, 1997
Expires in six months


                      SSH Transport Layer Protocol

Status of This memo

This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.''

To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the Internet-Drafts
Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast),
or ftp.isi.edu (US West Coast).

Abstract

This document describes the SSH transport layer protocol.  The protocol
can be used as a basis for a number of secure network services.  It pro-
vides strong encryption, server authentication, and integrity protec-
tion.

























Tatu Ylonen <ylo@ssh.fi>                                        [page 1]


INTERNET-DRAFT                                             July 30, 1997

Table of Contents

1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . .  2
2.  Data Type Representations Used in the Protocol  . . . . . . . . .  3
  2.1.  byte  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
  2.2.  boolean   . . . . . . . . . . . . . . . . . . . . . . . . . .  3
  2.3.  uint32  . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
  2.4.  string  . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
  2.5.  mpint   . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
3.  Algorithm Naming  . . . . . . . . . . . . . . . . . . . . . . . .  4
4.  Connection Setup  . . . . . . . . . . . . . . . . . . . . . . . .  4
  4.1.  Use over TCP/IP   . . . . . . . . . . . . . . . . . . . . . .  4
  4.2.  Protocol Version Exchange   . . . . . . . . . . . . . . . . .  4
  4.3.  Compatibility with Old SSH Versions   . . . . . . . . . . . .  5
    4.3.1.  Old Client, New Server  . . . . . . . . . . . . . . . . .  5
    4.3.2.  New Client, Old Server  . . . . . . . . . . . . . . . . .  5
5.  Binary Packet Protocol  . . . . . . . . . . . . . . . . . . . . .  5
  5.1.  Maximum Packet Length   . . . . . . . . . . . . . . . . . . .  6
  5.2.  Compression   . . . . . . . . . . . . . . . . . . . . . . . .  6
  5.3.  Encryption  . . . . . . . . . . . . . . . . . . . . . . . . .  7
  5.4.  Data Integrity  . . . . . . . . . . . . . . . . . . . . . . .  8
6.  Key Exchange  . . . . . . . . . . . . . . . . . . . . . . . . . .  9
  6.1.  Algorithm Negotiation   . . . . . . . . . . . . . . . . . . .  9
  6.2.  Diffie-Hellman Key Exchange   . . . . . . . . . . . . . . . . 12
  6.3.  Double-Encrypting Key Exchange  . . . . . . . . . . . . . . . 14
    6.3.1.  Server Sends Host Key   . . . . . . . . . . . . . . . . . 14
    6.3.2.  Deriving Exchange Hash and Session Identifier   . . . . . 15
    6.3.3.  Client Sends Double-Encrypted Session Key   . . . . . . . 15
    6.3.4.  Deriving Encryption and Integrity Keys  . . . . . . . . . 16
  6.4.  Taking Keys into Use  . . . . . . . . . . . . . . . . . . . . 16
7.  Key Re-Exchange   . . . . . . . . . . . . . . . . . . . . . . . . 17
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
9.  Additional Messages   . . . . . . . . . . . . . . . . . . . . . . 18
  9.1.  Disconnection Message   . . . . . . . . . . . . . . . . . . . 18
  9.2.  Ignored Data Message  . . . . . . . . . . . . . . . . . . . . 19
  9.3.  Debug Message   . . . . . . . . . . . . . . . . . . . . . . . 19
  9.4.  Reserved Messages   . . . . . . . . . . . . . . . . . . . . . 19
10.  Summary of Message Numbers   . . . . . . . . . . . . . . . . . . 20
11.  Public Keys and Public Key Infrastructure  . . . . . . . . . . . 20
  11.1.  x509   . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
  11.2.  spki   . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
  11.3.  ssh-rsa-pkcs1  . . . . . . . . . . . . . . . . . . . . . . . 21
12.  Security Considerations  . . . . . . . . . . . . . . . . . . . . 22
13.  Address of Author  . . . . . . . . . . . . . . . . . . . . . . . 22



1.  Introduction

The SSH protocol is a secure transport layer protocol.  It provides
strong encryption, cryptographic host autentication, and integrity
protection.



Tatu Ylonen <ylo@ssh.fi>                                        [page 2]


INTERNET-DRAFT                                             July 30, 1997

Authentication in this protocol level is host-based; this protocol does
not perform user authentication.  It is expected that a higher level
protocol will be defined on top of this protocol that will perform user
authentication for those services that need it.

The protocol has been designed to be simple, flexible, allow parameter
negotiation, and minimize the number of round-trips.  Key exchange
method, public key algorithm, symmetric encryption algorithm, message
authentication algorithm, and hash algorithm are all negotiated.  It is
expected that in most environments, only 1.5 round-trips will be needed
for full key exchange, server authentication, service request, and
acceptance notification of service request.  The worst case is 2.5
round-trips.

2.  Data Type Representations Used in the Protocol

2.1.  byte

A byte represents an arbitrary 8-bit value.  Fixed length data is
sometimes represented as an array of bytes, written byte[n], where n is
the number of bytes in the array.

2.2.  boolean

A boolean value is represented as a single byte.  The value 0 represents
false, and the value 1 represents true.  All non-zero values are
interpreted as true, but applications should not store values other than
0 and 1.

2.3.  uint32

A 32-bit unsigned integer, represented as four bytes, MSB first.

2.4.  string

A string here means an arbitrary length binary string.  Strings are
allowed to contain arbitrary binary data, including null characters and
8-bit characters.

A string is represented as a uint32 containing its length, followed by
zero or more characters that are the value of the string.  No
terminating null character is normally included in the string.

2.5.  mpint

Multiple precision integers are represented by the mpint type.

  uint32         number of bits
  byte[n]        value, MSB first, n = floor((bits + 7) / 8)

The number of bits is exact (e.g., value 5 has 3 bits).  Any unused bits
are in the first value byte (MSB) and must be zero.  The value zero has
zero bits and zero data bytes.  (The exact format is important if as the


Tatu Ylonen <ylo@ssh.fi>                                        [page 3]


INTERNET-DRAFT                                             July 30, 1997

data may sometimes be signed.)

3.  Algorithm Naming

This protocol refers to particular hash, encryption, integrity,
compression, and key exchange algorithms in various places.  There are
some standard algorithms that all implementations are required to
support.  There are also algorithms that are defined in the protocol
specification but are optional.  Furthermore, it is expected that some
organizations will want to use their own algorithms whenever possible.
This leads to the problem of how algorithm identifiers are allocated.

In this protocols, all algorithm identifiers are represented as strings.
Names are case-sensitive.  Algorithm lists are comma-separated lists of
these identifiers, without spaces.  There are two formats for algorithm
identifiers:
o  Algorithms defined in the base protocol are simple strings, such as
   "3des-cbc", "sha-1", "hmac-sha", or "zip" (the quotes are not part of
   the name).  Defined algorithms may be mandatory or optional.  All
   interoperable implementations should implement mandatory algorithms
   and offer them as a possibility in key exchanges.  Optional
   algorithms are not crucial for interoperability, but may provide
   better performance or other advantages.  It is up to an
   implementation to decide which of these are supported and which are
   offered in key exchanges by default.

o  Anyone can define additional algorithms by using names in the format
   name@domainname, e.g. "ourcipher-cbc@ssh.fi".  The format of the part
   preceding the at sign is not specified; it may contain any non-
   control characters except at signs and commas.  The part following
   the at sign should be a valid internet domain name for the
   organization defining the name.  It is up to the each organization
   how they manage its locally defined names.

4.  Connection Setup

SSH works over any 8-bit clean, binary-transparent transport.  The
client initiates the connection, and sets up the binary-transparent
transport.

4.1.  Use over TCP/IP

When used over TCP/IP, the server normally listens for connections on
port 22.  This port number has been registered with the IANA (Internet
Assigned Numbers Authority), and has been officially assigned for SSH.

4.2.  Protocol Version Exchange

When the connection has been established, both sides send an
identification string of the form "SSH-protoversion-softwareversion
comments", followed by carriage return and newline (ascii 13 and 10,
respectively).  No null character is sent.  The maximum length of the
string is 255 characters, including the cr and newline.  The protocol


Tatu Ylonen <ylo@ssh.fi>                                        [page 4]


INTERNET-DRAFT                                             July 30, 1997

version described in this document is 2.0.  Version strings should only
contain printable characters, not including space or '-'.  The string is
used in debugging outputs to ease debugging; the protocol version is
also used to trigger compatible extensions.  It is recommended that the
strings be as descriptive as possible.  The comment string could include
information such as the platform type which might be useful in solving
user problems.

Key exchange will begin immediately after sending this identifier
(normally without waiting for the identifier from the other side -- see
the next section for compatibility issues).  All packets following the
identification string will use the binary packet protocol, to be
described below.

4.3.  Compatibility with Old SSH Versions

During a transition period, it is important to be able to work
compatibly with installed SSH clients and servers using an older version
of the protocol.  Information in this section is only relevant for
implementations supporting compatibility with old versions.

4.3.1.  Old Client, New Server

Server implementations should support a configurable "compatibility"
flag that enables compatibility with old versions.  When this flag is
on, the server will not send any further data after its initialization
string until it has received an identification string from the client.
The server can then determine whether the client is using an old
protocol, and can revert to the old protocol if desired.

When compatibility with old clients is not needed, the server should
send its initial key exchange data immediately after the identification
string.  This saves a round-trip.

4.3.2.  New Client, Old Server

Since the new client will immediately send additional data after its
identification string (before receiving server's identification), the
old protocol has already been corrupted when the client learns that the
server is old.  When this happens, the client should close the
connection to the server, and reconnect using the old protocol this
time.

5.  Binary Packet Protocol

Each packet consists of the following fields:

    Length
      The length of the packet (bytes).  This represents the number of
      bytes that follow this value, not including the optional MAC.  The
      length is represented as a uint32.

    Padding length


Tatu Ylonen <ylo@ssh.fi>                                        [page 5]


INTERNET-DRAFT                                             July 30, 1997

      Length of padding (bytes).  This field is represented as a byte.

    Payload
      The useful contents of the packet.  This field is optionally
      compressed.

    Padding
      Arbitrary-length padding, such that the total length of
      length+paddinglength+payload+padding is a multiple of the cipher
      block size or 8, whichever is larger.  It is recommended that at
      least four bytes of random padding be always used.  The maximum
      amount of padding is 255 bytes.

    MAC
      Message authentication code.  This field is optional, and its
      length depends on the algorithm in use.

Note that length of the concatenation of packet length, padding length,
payload, and padding must be a multiple of the cipher block size or 8,
whichever is larger.  This constraint is enforced even when using stream
ciphers.  Note that the packet length field is also encrypted, and
processing it requires special care when sending/receiving packets.  In
particular, one has to be extra careful when computing the amount of
padding, as changing the amount of padding can also change the size of
the length fields.  The minimum size of a packet is 8 (or cipher block
size, whichever is larger) characters (plus MAC); implementations should
decrypt the length after receiving the first 8 (or cipher block size,
whichever is larger) bytes of a packet.

When the protocol starts, no encryption is in effect, no compression is
used, and no MAC is in use.  During key exchange, an encryption method,
compression method, and a MAC method are selected.  Any further messages
will use the negotiated algorithms.

5.1.  Maximum Packet Length

All implementations are required to be able to process packets with
uncompressed payload length of at least 32768 bytes with total packet
size up to 35000 bytes (including length, padding length, payload,
padding, and MAC).  The motivation for this limit is to keep the
protocol easy to implement on 16-bit machines.  Implementations are,
however, encouraged to support longer packets, as they might be needed
e.g. if an implementation wants to send a very large number of
certificates.

5.2.  Compression

If compression has been negotiated, the payload field (and only it) will
be compressed using the negotiated algorithm.  The length field will
contain the compressed length (i.e., that transmitted on the wire).

Compressed packets must not exceed the total packet size limit; the
compression algorithm must guarantee that it does not expand the packet


Tatu Ylonen <ylo@ssh.fi>                                        [page 6]


INTERNET-DRAFT                                             July 30, 1997

too much.  The uncompressed payload size must not exceed the maximum
payload size (the compressed payload, however, may be bigger than the
maximum payload size, as long as the packet size limit is not exceeded).

The following compression methods are currently defined:

          none     mandatory       no compression
          zlib     optional        GNU ZLIB compression at level 6

The "zlib" compression is described in RFC1950.

The compression context is initialized after key exchange, and is passed
from one packet to the next with only a partial flush being performed at
the end of each packet.  A partial flush means that all data will be
output, but the next packet will continue using compression tables from
the end of the previous packet.

Compression is independent in each direction, and the different
compression methods may be used for each direction.

5.3.  Encryption

An encryption algorithm and a key will be negotiated during the key
exchange.  When encryption is in effect, the length, padding length,
payload and padding fields of each packet will be encrypted with the
given algorithm.

The encrypted data in all packets sent in one direction will be
considered a single data stream.  For example, initialization vectors
will be passed from the end of one packet to the beginning of the next
packet.

The ciphers in each direction will run independently of each other.
They will typically use a different key, and different ciphers can be
used in each direction.

The following ciphers are currently defined:

none             optional          no encryption
3des-cbc         mandatory         three-key 3DES in CBC mode
idea-cbc         optional          IDEA in CBC mode
arcfour          optional          ARCFOUR stream cipher
blowfish-cbc     optional          Blowfish in CBC mode

The 3des-cbc encryption is three-key triple-DES (encrypt-decrypt-
encrypt), where the first 8 bytes of the key are used for the first
encryption, the next 8 bytes for the decryption, and the following 8
bytes for the final encryption.  This requires 24 bytes of key data (of
which the parity bits are not actually used).  To implement CBC mode,
there is only one initialization vector.

For ciphers with variable-length keys, 128 bit keys are used.



Tatu Ylonen <ylo@ssh.fi>                                        [page 7]


INTERNET-DRAFT                                             July 30, 1997

The ARCFOUR cipher is compatible with the RC4 cipher; RC4 is a trademark
of RSA Data Security, Inc.

Descriptions of all of these ciphers can be found e.g. from Bruce
Schneier: Applied Cryptography, 2nd ed., John Wiley and Sons, 1996.

5.4.  Data Integrity

Data integrity is protected by including with each packet a message
authentication code (MAC) that is computed from a shared secret, packet
sequence number, and the contents of the packet.

The message authentication algorithm and key are negotiated during key
exchange.  Initially, no MAC will be in effect, and its length will be
zero.  After key exchange, the selected MAC will be computed before
encryption from the concatenation of packet data (lengths, payload, and
padding) and a packet sequence number (stored as a 32-bit integer, MSB
first).  The integrity key is also used in the computation of the MAC,
but the way it is used depends on the MAC algorithm in use.  Note that
the MAC algorithm may be different for each direction.

The packet sequence number is only used for integrity checking.  It is
never explicitly transmitted, but it is included in MAC computation to
ensure that no packets are lost or received out of sequence.  The
sequence number of the first packet sent is zero; from there on the
sequence number is incremented by one for every packet sent (separately
for each direction).  The packet number is 32 bits and wraps around if
32 bits is not enough for representing it.  The sequence number is
incremented also for packets that are not encrypted or MACed, and is not
reset even if keys are renegotiated later.

The check bytes resulting from the MAC algorithm are transmitted without
encryption as the last part of the packet.  The number of check bytes
depends on the algorithm chosen.

The following MAC algorithms are currently defined:

          none        optional         no MAC
          hmac-md5    optional         HMAC-MD5 (length = 16)
          hmac-sha    optional         HMAC-SHA (length = 20)
          md5-8       optional         first 8 bytes MD5 key+data+key
          sha-8       optional         first 8 bytes SHA-1 key+data+key
          sha         mandatory        SHA of key+data+key (20 bytes)

The HMAC methods are described in RFC 2104.

The "md5-8" method returns the first 8 bytes of MD5 of the concatenation
of the key, authenticated data, and the key again.  The "sha-8" method
is the same but using the SHA hash.

Even though only the "sha" method is mandatory, it is recommended that
implementations support and prefer the other methods.  (This method
exists only as a fallback should unexpected patent problems surface.)


Tatu Ylonen <ylo@ssh.fi>                                        [page 8]


INTERNET-DRAFT                                             July 30, 1997

6.  Key Exchange

Key exchange begins by each side sending lists of supported algorithms.
Each side has a preferred algorithm, and it is assumed that most
implementations at any given time will use the same preferred algorithm.
Each side will make the guess that the other side is using the same
algorithm, and may send an initial key exchange packet according to the
algorithm if appropriate for the preferred method.  If the guess is
wrong, they'll ignore the guessed packet, select a common algorithm, and
send the initial key exchange packet again, this time for the same
algorithm.

Currently, the following key exchange methods have been defined:

          double-encrypting-sha        mandatory

The implementation of these methods is described later in this section.

One should note that server authentication in the double-encrypting key
exchange is implicit, and the client doesn't really know the identity of
the server until it receives a message from the server using the correct
MAC and encryption.  This means that an attacker could fool the client
into using no encryption (if the client is willing to accept no
encryption), and the client might in some cases send sensitive data,
such as a password, before it notices that the server isn't responding
properly.  For this reason, it is recommended that clients should not
accept "none" encryption unless explicitly requested by the user.
Alternatively, they should wait for the server's response to the service
request before sending anything else.

6.1.  Algorithm Negotiation

Each side sends the following packet (this is the part that goes inside
the payload):

            byte      SSH_MSG_KEXINIT
            byte[16]  cookie (random bytes)
            string    kex_algorithms
            string    server_host_key_algorithms
            string    encryption_algorithms_client_to_server
            string    encryption_algorithms_server_to_client
            string    mac_algorithms_client_to_server
            string    mac_algorithms_server_to_client
            string    compression_algorithms_client_to_server
            string    compression_algorithms_server_to_client
            string    hash_algorithms
            boolean   first_kex_packet_follows
            byte[4]   0 (reserved for future extension)

Each of the algorithms strings are comma-separated lists of algorithm
names.  Each supported (allowed) algorithm should be listed, in order of
preference.  The preferred (guessed) algorithm should be listed first.
Each string must contain at least one algorithm name.  The value "none"


Tatu Ylonen <ylo@ssh.fi>                                        [page 9]


INTERNET-DRAFT                                             July 30, 1997

is not automatically allowed; if a party permits connections with "none"
as one of the algorithms, it should list that as an algorithm.

    cookie
      The cookies are random values generated by each side.  Their
      purpose is to make it impossible for either side to fully
      determine the keys (which might open possibilities for passing
      certain signatures/authentications to third parties).

    kex_algorithms
      Key exchange algorithms were defined above.  The first algorithm
      is the preferred (and guessed) algorithm.  If both sides make the
      same guess, that algorithm is used.  Otherwise, the following
      algorithm is used to choose a key exchange method: iterate over
      client's kex algorithms, one at a time.  Choose the first
      algorithm that satisfies the following conditions: 1) the server
      also supports the algorithm 2) if the algorithm requires an
      encryption-capable host key, there is an encryption-capable
      algorithm on the server's  server_host_key_algorithms  that is
      also supported by the client 3) if the algorithm requires a
      signature-capable host key, there is a signature-capable algorithm
      on the server's  server_host_key_algorithms  that is also
      supported by the client.  If no algorithm satisfying all these
      conditions can be found, connection fails.

      The kex algorithm names were listed above.

    server_host_key_algorithms
      Lists the algorithms supported for the server host key.  The
      server lists the algorithms for which it has host keys; the client
      lists the algorithms that it is willing to accept.  (There can be
      multiple host keys for a host, possibly with different
      algorithms.)

      Some host keys may not support both signatures and encryption
      (this can be determined from the algorithm), and thus not all host
      keys are valid for all key exchange methods.

      Algorithm selection depends on whether the chosen kex algorithm
      requires a signature- or encryption capable host key.  The first
      algorithm on the client's list that satisfies the requirements and
      is also supported by the server is chosen.

      Section ``Public Key Formats'' lists the available algorithm
      names.

    encryption_algorithms
      Lists the acceptable symmetric encryption algorithms in order of
      preference.  The chosen encryption algorithm will be the first
      algorithm on the client's list that is also on the server's list.
      If there is no such algorithm, connection fails.

      Note that "none" must be explicitly listed if it is to be


Tatu Ylonen <ylo@ssh.fi>                                       [page 10]


INTERNET-DRAFT                                             July 30, 1997

      acceptable.  The defined algorithm names are listed in Section
      ``Encryption''.

      The algorithm to use is negotiated separately for each direction,
      and different algorithms may be chosen.

    mac_algorithms
      Lists the acceptable MAC algorithms in order of preference.  The
      chosen MAC algorithm will be the first algorithm on the client's
      list that is also on the server's list.  If there is no such
      algorithm, connection fails.

      Note that "none" must be explicitly listed if it is to be
      acceptable.  The MAC algorithm names are listed in Section ``Data
      Integrity''.

      The algorithm to use is negotiated separately for each direction,
      and different algorithms may be chosen.

    compression_algorithms
      Lists the acceptable compression algorithms in order of
      preference.  The chosen compression algorithm will be the first
      algorithm on the client's list that is also on the server's list.
      If there is no such algorithm, connection fails.

      Note that "none" must be explicitly listed if it is to be
      acceptable.  The compression algorithm names are listed in Section
      ``Compression''.

      The algorithm to use is negotiated separately for each direction,
      and different algorithms may be chosen.

    hash_algorithms
      Lists the acceptable hash algorithms in order of preference.  The
      chosen hash algorithm will be the first algorithm on the client's
      list that is also on the server's list.  If there is no such
      algorithm, connection fails.

      Implementations should only permit algorithms that they consider
      to be fairly secure, as the hash function will be used e.g. for
      deriving various keys from the shared secret.  All hash algorithms
      must produce at least 16 bytes of output.

      Currently, the following hash functions are defined.

             md5          optional      MD5 algorithm (16 byte output)
             sha          mandatory     SHA-1 algorithm (20 byte output)

    first_kex_packet_follows
      Each side makes a guess of the negotiated key exchange method.
      This is based on the assumption that at any particular time there
      will be a single key exchange method and algorithm combination
      that dominates the installed base.  Making a guess about the


Tatu Ylonen <ylo@ssh.fi>                                       [page 11]


INTERNET-DRAFT                                             July 30, 1997

      algorithm will save a round-trip in the typical case, and will
      incur little extra cost in the other cases.

      Each side will determine if they are supposed to send an initial
      packet in their guessed key exchange method.  If they are, they
      will set this field to true and follow this packet by the first
      key exchange packet.

      The guessed method is the one listed first on the kex_algorithms,
      server_host_key_algorithms, and hash_algorithms lists.  If the
      negotiated values for any of these algorithms differs from the
      first value on either side, the guess is taken to be wrong, and
      the packet sent based on the guess is ignored.  Whether the
      packets based on the guess are actually wrong is not a factor in
      this decision (the information may not be available to make this
      decision).

      After receiving the SSH_MSG_KEXINIT packet from the other side,
      each party will know whether their guess was right.  If the guess
      was wrong, and this field is true, the next packet will be
      silently ignored, and each side will then act as determined by the
      negotiated key exchange method.  If the guess was right, key
      exchange will immediately continue.

6.2.  Diffie-Hellman Key Exchange

The Diffie-Hellman key exchange is based on performing a diffie-hellman
exchange followed by the server sending a hash of the exchange to the
client.  It works as follows (A is client, B is server; p is a prime, g
is a generator for the prime, and q is the order of the generator; K_B
is B's public host key; I_A is A's KEXINIT message and I_B B's KEXINIT
message which have been exchanged before this part begins):

1. A generates a random number a (0 < a < q) and computes e = g^a mod p.
   A sends "e" to B.

2. B generates a random number b (0 < b < q) and computes f = g^b mod p.
   B receives "e".  It K = e^b mod p, H = hash(I_A || I_B || K_B || K),
   and computes signature s with its private host key on H.  B sends
   "K_B || f || s" to A.

3. A verifies that K_B really is the host key for B (e.g. using
   certificates or a local database).  A is also allowed to accept the
   key without verification; however, doing so will render the protocol
   insecure against active attacks (but may be desirable for practical
   reasons in the short term in many environments).  A then computes K =
   f^a mod p, H = hash(I_A || I_B || K_B || K), and verifies the
   signature s on H.

This is implemented with the following messages.  The hash algorithm is
fixed to be SHA-1.  The public key algorithm for signing is negotiated
with the KEXINIT messages.



Tatu Ylonen <ylo@ssh.fi>                                       [page 12]


INTERNET-DRAFT                                             July 30, 1997

First, the client sends:

            byte      SSH_MSG_KEXDH_INIT
            mpint     e

The server responds with:

            byte      SSH_MSG_KEXDH_REPLY
            string    server public host key and certificates (K_B)
            mpint     f
            string    signature

The hash H is computed as the SHA-1 hash of the concatenation of the
following (in this order):
o  the length of the payload of the client's SSH_MSG_KEXINIT message as
   4 bytes, MSB first,

o  the payload of the client's SSH_MSG_KEXINIT message,

o  the length of the payload of the server's SSH_MSG_KEXINIT message as
   4 bytes, MSB first,

o  the payload of the server's SSH_MSG_KEXINIT message,

o  K_B, represented as a string.

o  K, represented as an mpint.

This value is called the exchange hash, and it is used to authenticate
the key exchange.

The values of p and g are fixed.  The following values are used: XXX To
be defined!  (Take the 1024 bit field based on decimals of PI from one
of the other existing drafts.)

Encryption keys are computed as HASH of a known value and $K$ as
follows:

o  Initial IV client to server: HASH(K || "A" || K) ("A" means the
   single character A).

o  Initial IV server to client: HASH(K || "B" || K)

o  Encryption key client to server: HASH(K || "C" || K)

o  Encryption key server to client: HASH(K || "D" || K)

o  Integrity key client to server: HASH(K || "E" || K)

o  Integrity key server to client: HASH(K || "F" || K)

Key data is taken from the beginning of the hash output.  128 bits (16
bytes) will be used for algorithms with variable-length keys.  For other


Tatu Ylonen <ylo@ssh.fi>                                       [page 13]


INTERNET-DRAFT                                             July 30, 1997

algorithms, as many bytes as are needed are taken from the beginning of
the hash value.  If a longer key is needed for some algorithm than is
the output of the hash, the key is extended by computing HASH of the
concatenation of K and the entire key so far, and appending the
resulting bytes (as many as HASH outputs) to the key.  This process is
repeated until enough key material is available; the key is taken from
the beginning of this value.  In other words,

  K1 = HASH(K || X || K)   (X is e.g. "A")
  K2 = HASH(K || K1)
  K3 = HASH(K || K1 || K2)
  ...
  key = K1 || K2 || K3 || ...

6.3.  Double-Encrypting Key Exchange

The double-encrypting key exchange requires that the server host key
supports encryption.  The idea is that the server sends its public host
key and a periodically changing key (called the server key).  The client
then verifies that it is the correct key for the server, generates a
session key, encrypts the session key using both a time-variant server
key and the server host key, and sends the encrypted session key to the
server.

The server key and host keys must both support encryption, and their
sizes must be such that the server key can encrypt at least 48 bytes,
and the server host key can encrypt the result of the first encryption.
Note that padding is normally added at each encryption, depending on the
public key method, so the actual size difference of the keys is bigger.
Both keys must use the same public key algorithm.

6.3.1.  Server Sends Host Key

First, the server sends its public host and server keys in the following
packet:

            byte      SSH_MSG_KEXDE_HOSTKEY
            string    public host key
            string    public server key

The host key and server key are stored in binary representation as
described in Section ``Public Key Formats''.  Both keys are of the type
negotiated for the server host key.

After receiving the public keys, the client validates that the host key
really belongs to the intended server.  How this verification happens is
not specified in this protocol.  Currently it may be checked against a
database of known name-key mappings; in future it will be validated
using an Internet public key infrastructure.  The key may contain
certificates to facilitate this.

If the client is not willing to trust the server host key, it should
send an SSH_MSG_DISCONNECT packet and close the connection.


Tatu Ylonen <ylo@ssh.fi>                                       [page 14]


INTERNET-DRAFT                                             July 30, 1997

The client then generates a 256 bit random session key (shared secret).

6.3.2.  Deriving Exchange Hash and Session Identifier

To authenticate that no-one has been manipulating the key exchange with
the server, the client computes an SHA-1 hash of the concatenation of
the following (in this order):

1. the length of the payload of the client's SSH_MSG_KEXINIT message as
   4 bytes, MSB first,

2. the payload of the client's SSH_MSG_KEXINIT message,

3. the length of the payload of the server's SSH_MSG_KEXINIT message as
   4 bytes, MSB first,

4. the payload of the server's SSH_MSG_KEXINIT message,

5. the length of the payload of the server's SSH_MSG_KEXDE_HOSTKEY
   message as 4 bytes, MSB first,

6. the payload of the server's SSH_MSG_KEXDE_HOSTKEY message, and

7. the 32 bytes of the session key.

   This value is called the exchange hash, and it is used to
   authenticate the key exchange.

Note that the use of SHA-1 was hard-coded here.  This is used to
authenticate the key exchange, and using HASH here would lead to all
sorts of potential problems in verifying the security of the protocol.
Using a fixed hash short-circuits verification to the properties of
SHA-1.  Should the need ever arise, the only way to switch to another
algorithm here is to define a new key exchange algorithm (which, in
fact, is not very difficult).

The exchange hash from the first key exchange in a connection is called
the session identifier.  It is used in host authentication and other
authentication methods as data that is signed to prove possession of a
private key.

Once computed, the session identifier is not changed or recomputed even
if keys are later re-exchanged.  The exchange hash, on the other hand,
is computed separately for each key exchange.

6.3.3.  Client Sends Double-Encrypted Session Key

The client forms a message to send to the server by concatenating the
following (in this order): six zero bytes (reserved for future
extension), first 10 bytes of the exchange hash, and the 32 bytes of the
shared secret.  This results in a total of 48 bytes of data to be passed
to the server.  Note that the negotiated algorithms are not explicitly
passed, as the algorithms given in Section ``Algorithm Negotiation''


Tatu Ylonen <ylo@ssh.fi>                                       [page 15]


INTERNET-DRAFT                                             July 30, 1997

fully determine the algorithms.

The resulting data is encrypted first with the time-variant server key,
and the result then with the server host key.  The resulting double-
encrypted value is then sent to the server.  Note that public-key
encryption probably involves padding, depending on the algorithm.

            byte      SSH_MSG_KEXDE_SESSIONKEY
            string    double-encrypted session key

Upon receiving this message, the server uses its private host and server
keys to decrypt the session key.  It computes a corresponding SHA hash,
and compares the hash values.  If the hash does not match, the server
disconnects with the appropriate message.  If the hash matches, the
server responds with an SSH_MSG_NEWKEYS message and takes the keys into
use.

6.3.4.  Deriving Encryption and Integrity Keys

As a result of the key exchange, the parties have a 256-bit shared
secret.  Various keys are computed from this secret and the exchange
hash.  The session identifier is used to make it impossible for either
party to alone determine the keys.

Each key is computed as HASH of the concatenation of the session
identifier and 16 bytes of secret data.  The secret data is different
for each key, and is taken from the 32-byte shared secret as follows:

o  Initial IV client to server: bytes 0-15

o  Initial IV server to client: bytes 1-16

o  Encryption key client to server: bytes 5-20

o  Encryption key server to client: bytes 8-23

o  Integrity key client to server: bytes 13-28

o  Integrity key server to client: bytes 16-31

Key data is taken from the beginning of the hash output.  128 bits (16
bytes) will be used for algorithms with variable-length keys.  For other
algorithms, as many bytes as needed are taken from the beginning of the
hash value.  If a longer key is needed for some algorithm than is the
output of the hash, the key is extended by computing HASH of the entire
key so far, and appending the resulting bytes (as many as HASH outputs)
to the key.  This process is repeated until enough key material is
available; the key is taken from the beginning of this value.  (Note
that extending the key does not increase its strength or entropy;
however, 128 bits already provides enough entropy.)

6.4.  Taking Keys into Use



Tatu Ylonen <ylo@ssh.fi>                                       [page 16]


INTERNET-DRAFT                                             July 30, 1997

Key exchange ends by each side sending an SSH_MSG_NEWKEYS message.  This
message is sent with the old keys and algorithms.  All messages sent
after this message use the new keys and algorithms.
When this message is received, the new keys and algorithms are taken
into use for receiving.

This message is the only valid message after key exchange, in addition
to SSH_MSG_DISCONNECT and SSH_MSG_IGNORE messages.  The purpose of this
message is to ensure that a party is able to respond with a disconnect
message that the other party can understand if something goes wrong with
the key exchange.

            byte      SSH_MSG_NEWKEYS

7.  Key Re-Exchange

Either side may request re-exchange of keys at any time after the
service request has been accepted (and outside other key exchanges).
The re-exchange is not visible to the service.

Key re-exchange is started by sending a SSH_MSG_KEXINIT packet
(described in Section ``Algorithm Negotiation'').  When this message is
received, a party must respond with its own SSH_MSG_KEXINIT message.
Either party may initiate the re-exchange, but roles are not changed
(i.e., the server remains the server, and the client remains the
client).

Key re-exchange is performed under whatever encryption was in effect
when the exchange was started.  Encryption, compression, and MAC methods
are changed when SSH_MSG_NEWKEYS is sent after the key exchange (as in
the initial key exchange).  Re-exchange is processed identically to the
initial key exchange.  It is permissible to change any or all of the
algorithms during the re-exchange.  Host keys can also change.  All keys
and initialization vectors are recomputed after the exchange.
Compression and encryption contexts are reset.  The packet sequence
number is not reset.  The session identifier is not changed.

It is recommended that keys be changed after each gigabyte of
transmitted data or after each hour of connection time, whichever comes
sooner.

It is also possible to use the key re-exchange mechanism to switch to
faster algorithms after authentication, or to avoid double processing
for pre-encrypted or pre-authenticated data.  However, since the re-
exchange is a public key operation, it requires a fair amount of
processing power and should not be performed too often.

More application data may be sent after the SSH_MSG_NEWKEYS packet has
been sent.


After the various authentications, the client requests a service.  The
service is identified by a name.  Service names can contain any non-


Tatu Ylonen <ylo@ssh.fi>                                       [page 17]


INTERNET-DRAFT                                             July 30, 1997

control characters.  The name must not be longer than 64 characters.
Service names are case-sensitive.

            byte      SSH_MSG_SERVICE_REQUEST
            string    service name

Most server implementations will have a table of services that are
supported, specifying what to do for each service.

If the server rejects the service request, it should send a
SSH_MSG_DISCONNECT message.

When the service starts, it will have access to the session identifier
generated during key exchange.

If the server supports the service (and permits the client to use it),
it responds with

            byte      SSH_MSG_SERVICE_ACCEPT

The client is permitted to send further packets without waiting for the
this message; those packets will go to the selected service if the
server accepts the service request.  Message numbers used by services
should be in the area reserved for services (see Section ``Summary of
Message Numbers'').  The transport level will continue to process its
own messages.

The service name is not considered confidential information.  An active
network-level attacker may discover the service name by a man-in-the-
middle attack.  Successful reception of the service accept message will
confirm to the client that the server successfully received the session
key and that the key exchange was not tampered with.

If the negotiated cipher is "none", the client must wait until the
service accept message has been successfully received before sending any
more data.  Otherwise, an attacker could learn this data by modifying
negotiation parameters in such a way that the "none" cipher gets
selected.

9.  Additional Messages

Either party may send any of the following messages at any time.

9.1.  Disconnection Message

            byte      SSH_MSG_DISCONNECT
            uint32    reason code
            string    description

This message causes immediate termination of the connection.  The
description field gives the reason for disconnecting in human-readable
form in English.  The error code gives the reason in a machine-readable
format (suitable for localization), and can have the following values:


Tatu Ylonen <ylo@ssh.fi>                                       [page 18]


INTERNET-DRAFT                                             July 30, 1997

          #define SSH_DISCONNECT_HOST_NOT_ALLOWED_TO_CONNECT      1
          #define SSH_DISCONNECT_PROTOCOL_ERROR                   2
          #define SSH_DISCONNECT_KEY_EXCHANGE_FAILED              3
          #define SSH_DISCONNECT_HOST_AUTHENTICATION_FAILED       4
          #define SSH_DISCONNECT_MAC_ERROR                        5
          #define SSH_DISCONNECT_COMPRESSION_ERROR                6
          #define SSH_DISCONNECT_SERVICE_NOT_AVAILABLE            7
          #define SSH_DISCONNECT_PROTOCOL_VERSION_NOT_SUPPORTED   8
          #define SSH_DISCONNECT_HOST_KEY_NOT_VERIFIABLE          9
          #define SSH_DISCONNECT_CONNECTION_LOST                 10
          #define SSH_DISCONNECT_BY_APPLICATION                  11

9.2.  Ignored Data Message

            byte      SSH_MSG_IGNORE
            string    data

All implementations must understand (and ignore) this message at any
time (after receiving the protocol version).  No implementation is
required to ever send them.

9.3.  Debug Message

            byte      SSH_MSG_DEBUG
            uint32    type
            string    message

All implementations must understand this message, but they are allowed
to ignore it.  This message is used to pass information to the other
side which may help debugging problems.  The type may have any of the
following values:

    0 SSH_DEBUG_DEBUG
      The message contains information that may be useful for debugging
      problems; however, it should not normally be shown to the user.
      It is recommended that the data be available to the user for
      debugging purposes if explicitly requested.

    1 SSH_DEBUG_DISPLAY
      The message contains information that should preferably be shown
      to the user regardless of whether debugging information has been
      requested.

The message need not contain a newline.  It is, however, allowed to
consist of multiple lines separated by newlines.

9.4.  Reserved Messages

An implementation must respond to all unrecognized messages with an
SSH_MSG_UNIMPLEMENTED message in the order in which they were received.
Later protocol versions may define other meanings for these message
types.



Tatu Ylonen <ylo@ssh.fi>                                       [page 19]


INTERNET-DRAFT                                             July 30, 1997

            byte      SSH_MSG_UNIMPLEMENTED
            uint32    packet sequence number of rejected message

10.  Summary of Message Numbers

The following message numbers have been defined in this protocol.

#define SSH_MSG_DISCONNECT             1
#define SSH_MSG_IGNORE                 2
#define SSH_MSG_UNIMPLEMENTED          3
#define SSH_MSG_DEBUG                  4
#define SSH_MSG_KEXINIT               10
#define SSH_MSG_NEWKEYS               11
#define SSH_MSG_SERVICE_REQUEST       12
#define SSH_MSG_SERVICE_ACCEPT        13

/* Numbers 15-19 for kex packets.
   Different kex methods may reuse message numbers in
   this range. */
#define SSH_MSG_KEXDE_HOSTKEY         15
#define SSH_MSG_KEXDE_SESSIONKEY      16

/* Numbers 20- are reserved for service types.
   Different service types may reuse the same messages.
   Messages for stream-based services.  Other service types
   may be defined in other documents. */
#define SSH_MSG_STREAM_DATA           20
#define SSH_MSG_STREAM_EOF            21
#define SSH_MSG_STREAM_CLOSE          22

11.  Public Keys and Public Key Infrastructure

This protocol has been designed to be able to operate with almost any
public key format, encoding, and algorithm.

There are several aspects that define a public key type:

o  Key format: how is the key encoded and how are certificates
   represented.  The key blobs in this protocol may (but are not
   required to) contain certificates in addition to keys.

o  Signature and/or encryption algorithms.  Some algorithms may not
   support both encryption and decryption.  Key usage may also be
   restricted by policy statements in e.g. certificates.

o  Encoding of signatures and encrypted data.  This includes but is not
   limited to padding, byte order, and data formats.

The following public key formats are currently defined:

          x509                    X.509 certificate
          spki                    IETF SPKI certificate
          ssh-rsa-pkcs1           RSA key with PKCS-1 encodings


Tatu Ylonen <ylo@ssh.fi>                                       [page 20]


INTERNET-DRAFT                                             July 30, 1997

Note that the key type is negotiated at the beginning of the key
exchange, and is not included in the key blob itself.

11.1.  x509

X.509 is the most widely used certificate format at the time of this
writing.  However, X.509 has many serious problems, both on a conceptual
and implementation level.  X.509v3 has addressed many of these problems,
and may be more usable than previous versions.

The key blob for an "x509" key blob is a X.509 (v3) certificate (or
certificates) in ASN.1 (DER) format.

11.2.  spki

SPKI (Simple Public Key Infrastructure) is based on the philosophy that
most applications actually require authorization, not identification.
SPKI also addresses naming and policy issues in an explicit and useful
way.

The key blob for an "spki" key blob contains a SPKI key and certificate
objects concatenated together.

11.3.  ssh-rsa-pkcs1

This key type defines an RSA public key, with (mostly) PKCS compatible
signature and encryption formats.  It supports both signatures and
encryption.

Public keys of this type are represented as follows:

            uint32        number of bits in the modulus
            uint32        number bits in the public exponent
            bytes[n]      exponent, MSB first, n = floor((bits+7)/8)
            uint32        number of bits in the modulus
            bytes[n]      modulus, MSB first, n = floor((bits+7)/8)

It is permissible that there be other data (e.g., certificates)
following this; however, such data is not yet defined.

Note that private key formats are not defined here, and are
implementation-specific.

An encrypted message is formed as follows (this follows PKCS-1 padding
rules).
o  The data to be encrypted is padded into a long integer of the same
   number of bits as the modulus as follows:

              MSB             .  .  .                LSB

               0   2   RND(n bytes)   0   encrypted_data

The RND bytes represent non-zero random bytes.


Tatu Ylonen <ylo@ssh.fi>                                       [page 21]


INTERNET-DRAFT                                             July 30, 1997

o  To encrypt, this integer is raised to the public exponent, modulo the
   modulus.

o  The result is converted to a byte string of floor((bits+7)/8) bytes
   (where bits is the number of bits in the modulus), MSB first.  This
   byte string (without any length or terminating characters) is the
   result of the encryption.

A signature is formed as follows.

o  The data to be signed (typically a message digest, but not required
   to be such) is padded into a long integer of the same number of bits
   as the modulus as follows:

              MSB             .  .  .             LSB

               0   1   FF (n bytes)   0   signed_data

o  To sign, this integer is raised to the private exponent, modulo the
   modulus.

o  The result is converted to a byte string of floor((bits+7)/8) bytes
   (where bits is the number of bits in the modulus), MSB first.  This
   byte string (without any length or terminating characters) is the
   signature.  Applications may add other data outside this value.

12.  Security Considerations

This protocol is responsible for providing a secure encrypted channel
over an unsecure network.  It performs server host authentication, key
exchange, encryption, and integrity protection.  It also derives a
unique session id that may be by higher-level protocols.

It is expected that this protocol will sometimes be used without always
insisting on reliable association between the server host key and the
server host name.  Such use is inherently insecure, but may be necessary
in non-security critical environments, and still provides protection
against passive attacks.  However, protocols running on top of this
protocol should keep this possibility in mind.

13.  Address of Author

              Tatu Ylonen
              SSH Communications Security Ltd.
              Tekniikantie 12
              FIN-02150 ESPOO
              Finland

              E-mail: ylo@ssh.fi





Tatu Ylonen <ylo@ssh.fi>                                       [page 22]