Dr. Dobb's Journal October 1997
At one time, the Internet was a reasonably safe place, judging by the protocols that are still in use today. Whenever you use Telnet, ftp, or almost any remote login protocol, your password is sent in the clear over the network. Unfortunately, the Internet is no longer safe. Even a novice can grab a sniffer and a root kit and use them to break most systems on the Internet today. The Secure Shell (SSH) protocol provides secure connections that are authenticated and encrypted using military-grade encryption. The technology is so secure that you actually can build a Virtual Private Network over the Internet. In this article, I'll focus on the transport layer protocol for secure remote connections.
SSH was designed to provide maximum security. The preferred symmetric cryptographic algorithms all use a key length of at least 128 bits, and the protocol can support longer keys. The preferred algorithms -- Blowfish, IDEA, and three-key 3DES -- have received extensive public scrutiny and are generally regarded as strong. Message integrity is assured using cryptographic message authentication codes (MACs) that make tampering with the connection virtually impossible.
One factor that has contributed significantly to the success of the protocol is ease of use. SSH programs are easy to install and use. On most platforms a typical installation might require as little as three commands and some system reconfiguration. SSH can transparently replace the rexec, rsh, and rcp commands with a much more secure system for users who do not bother to learn new commands. For more security-conscious users, advanced features add authentication and forwarding services, including X11 forwarding.
If you are familiar with cryptographic authentication, you may wonder how SSH handles key distribution. The somewhat surprising answer is that it doesn't. SSH assumes that the keys are distributed in some manner, but does not enforce any particular policy. One of my favorite features of SSH is the ability to connect to an unknown host and still get an encrypted session. If allowed, the SSH client will respond to an unknown host and host key by assuming the key is correct. This makes a man-in-the-middle attack possible for the first contact, but it is still better than connecting without any encryption whatsoever. Users can distribute their public keys as they wish, and once a public key infrastructure for the Internet is deployed, SSH can use it without protocol changes.
Finally, SSH is fast. The key exchange has been optimized to 1.5 round trips and the encryption algorithms typically surpass average Internet connection speeds, which means that there is little or no slowdown due to encryption. On congested links, SSH may even increase throughput, since data is compressed before transmission.
Encryption is straightforward, as it basically converts plain-text blocks into encrypted blocks and vice versa. The SSH protocol gets by using only three kinds of data: Booleans, integers, and strings.
Boolean values are 0 and 1. Any implementation should regard any nonzero value as true, but only write values 0 and 1.
The integer types are byte, vlint32, uint16, and uint32. The byte type is typically used to define fixed-length data as an array of bytes, byte[n]. The uint types are ordinary unsigned integers, with the MSB first. vlint32 is an arbitrary 32-bit unsigned integer that is encoded using one to five bytes. The first two bits (bits 6 and 7) show how many bytes follow the first byte according to Table 1. Bits 0-5 carry the first six bits of the integer, except if both bit 6 and bit 7 are set when bits 0-5 are zero.
An SSH string is a vlint32 followed by an arbitrary binary string that may contain any 8-bit characters. No terminating null character is used and a string may contain null characters. Strings are used for data transmission and parameter negotiation, typically in the form of comma separated lists without spaces.
For instance, algorithms are named using strings such as 3des-cbc, sha-1, or ourcipher-cbc@ssh.fi. A cipher list might then be 3des-cbc,ourcipher-cbc@ssh.fi. The last cipher name is an example of how a proprietary algorithm should be named, to avoid conflicting names. The last part of the name should be a valid Internet domain name, and each domain manages its own local ciphers as it wishes.
SSH packets consist of the following fields:
You should be particularly careful when you calculate the length of the padding, as the size of the Length field may change when you increase the amount of padding, which in turn affects the amount of padding needed. When receiving, you should decipher the length field once you have received at least eight bytes or the first cipher block, to determine how much more data must be read to decipher the entire packet.
The SSH protocol was designed to work over any 8-bit clean binary-transparent transport layer. Current implementations all use TCP/IP, but future implementations may work on other transports as well. The Internet Assigned Numbers Authority (IANA) has assigned port 22 for SSH over TCP/IP.
The SSH client initiates the session by setting up the transport layer connection. Both sides then independently send an identification string of the form "SSH-protoversion-softwareversion comments" followed by a newline. This string may not exceed 255 characters, counting the terminating newline, and the version parts should only include printable characters, excluding space and "-". The string is used for debugging purposes, and the protocol version is used to determine compatibility options. You should try to make the string as descriptive as possible to make debugging easier. Also note that this is not sent as an SSH string.
Immediately after the identification strings have been transmitted, without waiting for acknowledgment, key exchange commences using the binary packet protocol I just described. This way, the complete connection setup can be reduced to 1.5 round trips, with the worst case being 2.5 round trips. At this point no encryption or compression is used, and no MAC is calculated, since the appropriate algorithms are determined during key exchange.
Unfortunately, the connection setup of Version 2.0 is incompatible with the older protocol versions. If you implement a 2.0 server, you may want to delay sending the key exchange packet until you know the version of the connecting client. This will make the connection establishment slightly slower, but will allow old clients to connect during a transition period. A 2.0 client must detect old servers because the 2.0 protocol causes a protocol violation in old servers. When the client detects this situation, it should disconnect and reconnect using the earlier protocol.
Both compression and encryption run separately in each direction, and may actually use different algorithms and encryption keys for the different directions. Even if the algorithm is the same, there will typically be two separate encryption keys for the different directions. The data transmitted in one direction will be considered a single data stream; initialization vectors and compression tables will be carried from one packet to the next.
When compression is used, only the payload is compressed using the algorithm determined during key exchange. The payload may expand during compression, but the total packet length must not exceed the maximum. Currently, two compression methods are defined; see Table 2.
The encryption algorithm encrypts everything in the packet except the MAC. The packet length is defined to be a multiple of the block size, so a block cipher can work directly on the packets without extra padding. Stream ciphers and block ciphers with small block sizes must use packets that are a multiple of 8 bytes. Table 3 lists the ciphers currently supported. (For more information about these ciphers, see Bruce Schneier's Applied Cryptography, Second Edition, John Wiley & Sons, 1996.)
Encrypting the data only ensures that nobody can eavesdrop on the connection, but tampering with the data is still possible and in some cases even feasible. Each packet should be protected by a MAC that is calculated from a shared secret -- the packet sequence number and the packet contents before encryption. The MAC is appended to the encrypted packet, and its length may vary depending on the algorithm used.
The packet sequence number is never actually transmitted, but is included in the MAC calculation along with the integrity key. The sequence number for the first packet is zero, and the number is incremented for every packet sent and never reset. If this 32-bit number is not big enough, it simply wraps around to begin again from zero. If a packet was ever to be lost or received out of sequence, the MAC calculation would fail.
As with compression and encryption, the integrity key can be different for each direction and the sequence number always is. Table 4 lists the currently defined algorithms. Again, I refer you to the literature for more information on these algorithms. HMAC is defined in RFC 2104.
The key exchange begins with algorithm negotiation. Typically one specific algorithm is widely used and will be used to create a default key-exchange packet. If this guess was correct, the key exchange will proceed immediately, else the parties have to decide on which algorithm to use by comparing lists. Currently, only one key exchange algorithm, "double-encrypting-sha," is defined and mandatory.
Algorithm negotiation is done by sending a packet of type SSH_MSG_KEXINIT. The packet contains:
Four bytes at the end of the packet are reserved for future extensions.
Algorithms are listed in order of preference, with the preferred algorithm first on the list. Using no algorithm must be explicitly listed as the alternative "none" to be accepted. Typically, the selected algorithm is the first on the client's list that also occurs on the server's list. Occasionally, this may not be possible. For instance, the selected algorithm might require a host key that can be used for signatures, but no such key is available. In this case, the next alternative on the client's list is tried. If no suitable match is found, the connection fails.
In the double-encrypting key exchange, only two more messages are required to complete the key exchange: a SSH_MSG_ KEXRSA_HOSTKEY message from the server and a SSH_MSG_KEXRSA_SESSIONKEY from the client.
In the KEXRSA_HOSTKEY message, the server sends its public host key and the periodically changing server key to the client. The client then verifies the host key in some way that is not specified by the protocol definition. Currently, it is usually done by comparing the key with a known copy in a database, but any reliable approach will do.
Once the client has verified the host key, it generates a random 256-bit session key. It then calculates the session identifier to verify that nobody has tampered with the key exchange. The session identifier is an SHA-1 hash of the concatenated payloads of the client's KEXINIT, the server's KEXINIT, the KEXRSA_HOSTKEY messages, and the 32 bytes of the key. SHA-1 is specified explicitly to make verification of the algorithm easier.
The session identifier is never recalculated and is used for authentication in several cases. Signed, it provides proof of possession of a private key.
The client now concatenates six zero bytes, the first ten bytes of the session identifier, and the 32 bytes of the key. The result is first encrypted with the smaller of the host and server keys and then with the larger one. Finally this is sent in a KEXRSA_SESSIONKEY message to the server.
The server decrypts the message, calculates the same hash as the client and verifies that it is correct. If the hash is correct, the server replies with an SSH_MSG_ NEWKEYS message and waits for the client to acknowledge this with SSH_MSG_ NEWKEYS. Only then are the keys taken into use. The reason for this is that either party may send SSH_MSG_DISCONNECT at this point if something goes wrong. If the DISCONNECT message was encrypted with the new keys, the recipient would not be able to interpret it correctly. The DISCONNECT message also carries a reason code and a descriptive string for error tracking.
The different keys needed by the protocol are calculated using the selected hash function on the session identifier and 16 bytes of the shared secret. Using the session identifier makes it impossible for either party to calculate keys alone. Table 6 shows which bytes are used for which key.
The length of the key thus depends on the selected hash function. This key can then be extended to the required length by repeatedly concatenating the key and the hash of the key to form a new, longer key.
The key exchange may be redone at any time during the session. It is initiated with an SSH_MSG_KEXINIT message from either party, but the roles as client and server remain the same. The whole exchange is transparent and is done with the old keys and algorithms. You should change keys periodically, either after one hour of connection time or one gigabyte of data.
Once the key exchange has completed and the keys have been taken into use, the client proceeds to requests a service using the SSH_MSG_SERVICE_REQUEST message. The only parameter of this message is a string of up to 64 noncontrol characters identifying the required service. If the server provides this service and the client is allowed access to it, the server responds with a SSH_MSG_SERVICE_ACCEPT message; otherwise, it responds with SSH_MSG_DISCONNECT. You should note that service names are case sensitive.
The client does not have to wait for the SERVICE_ACCEPT message, and can proceed to transmit packets for the service immediately after the request.
The SSH protocol does not specify how applications pass data to the protocol, but defines a stream service that is used to forward a stream over the encrypted connection. Data is transmitted asynchronously using SSH_MSG_STREAM_DATA messages that contain the data as a string. Either party can close its data channel at the end of the stream using the SSH_ MSG_STREAM_ EOF message. No data can be transmitted after this message, but the other direction remains open.
Stream communication is terminated using a pair of SSH_MSG_STREAM_CLOSE messages. The party that wants to close the channel sends the STREAM_CLOSE message and then waits for the other party to respond before closing the channel. The other party should respond to the STREAM_CLOSE message immediately and then close the channel.
The Internet lacks a public-key infrastructure, and this is rapidly becoming a major problem. Cryptographic authentication and key exchange typically require access to the other party's public keys and a way to verify that the keys are reliable. The SSH protocol does not commit itself to any particular solution, although the SSH programs use a database of trusted keys.
I expect that a key infrastructure will evolve during the next few years, and that several similar solutions will coexist during the transition period. If you decide to implement the SSH protocol, you should take great care to make the implementation independent of any particular solution. Users should be allowed to decide for themselves which infrastructure they trust, and you should give them a choice of different security features and levels.
Data Fellows Ltd. "Secure Networking, Remote Login and Systems Administration," http://www.Europe.DataFellows.com/f-secure/fnetsys.htm, 1996.
Schneier, B. Applied Cryptography: Protocols, Algorithms and Source Code in C, Second Edition, John Wiley & Sons, 1996.
Krawczyk, H., Bellare, M., and Canetti, R. "HMAC: Keyed-Hashing for Message Authentication," RFC 2104, February, 1997.
Ylönen, T. "SSH Transport Layer Protocol," draft-ietf-tls-ssh-00.txt, 1996. (Officially expired September 1, 1997.)
The complete SSH protocol has been documented in an Internet Draft. Unfortunately, Internet drafts are, by nature, temporary, so it may be difficult to find a copy. There are a few Internet sites that keep older drafts, however.
DDJ