SSH Cryptography

This part of the implementation will be following RFC 4253 and RFC 4252, which document the key negotiation and credential exchange processes.

The previous post established a connection and determined the cryptographic capabilities of the remote server. Several of these can be implemented using just the SHA1 and AES implementations from earlier posts, so I'll start there.

First up is a procedure to negotiate a session key. All of the Diffie-Hellman group key-exchanges are just two modpow invocations from the previous big number library, so that's a simple choice for key exchange.

⌨572 c ⌨122 a ⌨92 r ⌨116 g ⌨91 o ⌨113   ⌨189 r ⌨75 u ⌨82 n ⌨157   ⌨168 b ⌨90 e ⌨97 l ⌨187 a ⌨215 f ⌨84 o ⌨175 n ⌨97 t ⌨234 e ⌨635 : ⌨171 2 ⌨123 2 ⌨188 ⏎
			␤ ⎙60   ⎙0    Finished dev [unoptimized + debuginfo] target(s) in 0.01s⏎
			␤ ⎙1   ⎙0     Running `target\debug\main.exe 'belafonte:22'` ⎙0 ⏎
			␤ ⎙110 ⏎
			␤ ⎙0 ▲ SSH-2.0-WhyHelloThere Its_SSH_Time!⏎
			␤ ⎙47 ▼ SSH-2.0-OpenSSH_7.6p1 Ubuntu-4ubuntu0.3⏎
			␤ ⎙0 ▲ Capabilities⏎
			␤ ⎙115 ▼ Capabilities⏎
			␤ ⎙332 ▲ Key contribution: [159, 125, ..., 147, 212] (2048 bits)⏎
			␤ ⎙86 ▼ Key contribution: [74, 91, ..., 117, 99] (2048 bits)⏎
			␤ ⎙310   Shared key: [156, 52, ..., 184, 71] (2048 bits)⏎
			␤ ␃
		

The key exchange was pretty straightforward, as I basically implemented it as one of the tests for the big number library. Each side selects a number and modpows it with some pre-defined values, then sends the result to the other side. Both sides then modpow their selected value and received value together, producing the shared key without sending it over the network.

The next step simply validates that everything was exchanged correctly with the expected server. The server hashes the handshake payloads up to this point — initial hellos, capabilities lists, and shared key negotiation — signs this hash, then sends the signature and public key to the client for verification.

RSA signing is essentially just RSA encrypting a hash of the content being signed. RSA signature verification is the reverse: RSA decrypt the signature and ensure the result matches the hash of the content. This may sound complicated, but it's really just a few more calls to the already-implemented libraries:

1. Compute the content to be signed (the handshake hash): a call to the SHA1 library.
2. Compute the hash of the content to be signed (the hash of the handshake hash): a second call to the SHA1 library.
3. RSA decrypt the signature: just another modpow from the big number library.
4. Compare the decrypted hash to the expected hash: this is just ==.

So far I'm getting great use from the basic libraries from the past few posts. The only unusual bit about this is SSH's choice to sign a hash of the handshake data, rather than just signing the handshake data. This adds a bit of confusion because the first step of the signing process is hashing the content, so implementations will ultimately hash twice before RSA encrypting. The SSH documentation recognizes this and helpfully points it out so readers don't trip over it:

The signature algorithm MUST be applied over H, not the original data. Most signature algorithms include hashing and additional padding (e.g., "ssh-dss" specifies SHA-1 hashing). In that case, the data is first hashed with HASH to compute H, and H is then hashed with SHA-1 as part of the signing operation.

Although I now have a session key, activating the secrecy and integrity layers requires much more data: an encryption key for each transmission direction, an encryption initialization vector for each direction, and an authenticity key for each direction. These are generated by hashing some pre-determined values with the session key and handshake hash, so it's just a few more calls to the old SHA1 library.

The last step in the negotiation is for both sides to announce they have all the necessary keys and are ready to enable the outer layers:

			⌨610 c ⌨99 a ⌨141 r ⌨57 g ⌨81 o ⌨239   ⌨200 r ⌨142 u ⌨314 n ⌨203   ⌨181 b ⌨158 e ⌨79 l ⌨119 a ⌨115 f ⌨74 o ⌨132 n ⌨118 t ⌨201 e ⌨331 : ⌨195 2 ⌨132 2 ⌨239 ⏎
			␤ ⎙52   ⎙0    Finished dev [unoptimized + debuginfo] target(s) in 0.01s⏎
			␤ ⎙1   ⎙0     Running `target\debug\main.exe 'belafonte:22'`⏎
			␤ ⎙67 ⏎
			␤ ⎙0 ▲ SSH-2.0-WhyHelloThere Its_SSH_Time!⏎
			␤ ⎙75 ▼ SSH-2.0-OpenSSH_7.6p1 Ubuntu-4ubuntu0.3⏎
			␤ ⎙0 ▲ Capabilities⏎
			␤ ⎙96 ▼ Capabilities⏎
			␤ ⎙331 ▲ Key contribution: [131, 18, ..., 77, 117] (2048 bits)⏎
			␤ ⎙119 ▼ Key contribution: [169, ..., 121, 227] (2048 bits)⏎
			␤ ⎙0        Signing method: ssh-rsa⏎
			␤         Exponent: [1, 0, 1] (24 bits)⏎
			␤         Modulus: [220, 240, ..., 135, 110] (2048 bits)⏎
			␤ ⎙331   Shared key: [45, 150, ..., 39, 15] (2048 bits)⏎
			␤ ⎙0   Handshake hash: [175, 15, ..., 89, 37] (160 bits)⏎
			␤ ⎙0   Handshake hash hash: [160, 2, ..., 96, 181] (160 bits)⏎
			␤  Signed hash: [160, 2, ..., 96, 181] (160 bits)⏎
			␤ ⎙6 ▲ Start using new keys⏎
			␤ ⎙0 ▼ Start using new keys⏎
			␤ ␃
		

The secrecy and integrity layers are activated from this point on. All subsequent packets are encrypted using the cipher key and initialization vector generated from the shared key. Encryption and decryption make use of the stream-based wrapper from the AES library created earlier, ensuring no more than a single block of data is buffered.

Each encrypted packet is followed by an integrity code — the MAC. This code is formed by hashing the ciphertext with the authenticity key that was also generated form the shared key. As usual, the hashing is yet another call to the SHA1 library.

The final step in securing the connection is authentication. The authentication service is not active by default and must be requested. Once active, authentication requires just a single message providing the user's name, public key, and a signature of the message to prove the user possesses the private key. As mentioned earlier, the signing is simply a call to the SHA1 library to hash the content, followed by a call to modpow in the big numbers library to RSA encrypt the hash.

				⌨842 c ⌨92 a ⌨122 r ⌨107 g ⌨87 o ⌨97   ⌨161 r ⌨117 u ⌨111 n ⌨168   ⌨377 b ⌨121 e ⌨83 l ⌨108 a ⌨236 f ⌨95 o ⌨131 n ⌨237 t ⌨79 e ⌨182 : ⌨160 2 ⌨133 2 ⌨297   ⌨176 r ⌨99 u ⌨108 s ⌨54 t ⌨128   ⌨213 . ⌨74 / ⌨205 k ⌨78 e ⌨48 y ⌨468 . ⌨269 k ⌨102 e ⌨28 y ⌨306 ⏎
				␤ ⎙69   ⎙0    Finished dev [unoptimized + debuginfo] target(s) in 0.01s⏎
				␤ ⎙1   ⎙0     Running `target\debug\main.exe 'belafonte:22' rust ⏎
				␤              ./key.key`⏎
				␤ ⎙126 ⏎
				␤ ⎙0 ▲ SSH-2.0-WhyHelloThere Its_SSH_Time!⏎
				␤ ⎙130 ▼ SSH-2.0-OpenSSH_7.6p1 Ubuntu-4ubuntu0.3⏎
				␤ ⎙0 ▲ Capabilities⏎
				␤ ⎙102 ▼ Capabilities⏎
				␤ ⎙316 ▲ Key contribution: [182, 212, ..., 147, 212] (2048 bits)⏎
				␤ ⎙751 ▼ Key contribution: [191, 85, ..., 7, 190] (2048 bits)⏎
				␤ ⎙313    Shared key: [242, 123, ..., 208, 71] (2048 bits)⏎
				␤ ⎙0        Signing method: ssh-rsa⏎
				␤         Exponent: [1, 0, 1] (24 bits)⏎
				␤         Modulus: [220, 240, ..., 135, 110] (2048 bits)⏎
				␤ ⎙0   Handshake hash: [63, 74, ..., 98, 181] (160 bits)⏎
				␤ ⎙0   Handshake hash hash: [30, 226, ..., 76, 248] (160 bits)⏎
				␤ ⎙0   Signed hash: [30, 226, ..., 76, 248] (160 bits)⏎
				␤ ⎙6 ▲ Start using new keys⏎
				␤ ⎙0 ▼ Start using new keys⏎
				␤ ⎙0 ▲ Requesting service: ssh-userauth⏎
				␤ ⎙1273 ▼ Activated service: ssh-userauth⏎
				␤ ⎙0 ▲ Authenticating user: rust⏎
				␤ ⎙144 ▼ Authenticated⏎
				␤ ␃
			

And we're in! All of the outer layers are now active:

The next post will implement the final two layers, allowing multiplexed, windowed application data to flow.