Question about SSH host key algorithms

Question

I'm currently writing a report for my Master's degree on the SSH protocol. Quite interesting! However I'm having trouble getting into the inner workings of the host key algorithms.

For example, according to RFC4253, "ssh-rsa" is a key format where the server generates an RSA keypair. So far, so good. However, I don't seem to understand where SHA-1 comes into the play.

RFC8332 says

"SSH originally defined the public key algorithms "ssh-rsa" for server and client authentication using RSA with SHA-1".

My understanding is that the server computes a hash of the public key using SHA-1 and when appropriate, sends both the public key part and its SHA-1 computed hash with to the client.

Am I correct?

This isn't in any way related to the fingerprint shown when we connect to an SSH server for the first time, is it? If not, how can I calculate it (without ssh-keygen)?

Many thanks!

Answer 1

For example, according to RFC4253, "ssh-rsa" is a key format where the server generates an RSA keypair. So far, so good. However, I don't seem to understand where SHA-1 comes into the play.

See section 6.6:

   Signing and verifying using this key format is performed according to
   the RSASSA-PKCS1-v1_5 scheme in [RFC3447] using the SHA-1 hash.

   The resulting signature is encoded as follows: [snipped]

As indicated by that reference RFC3447 section 8.2 defines how to do this signature scheme; in particular it uses EMSA-PKCS1-v1_5 in section 9.2 which starts by applying the selected hash, in this case SHA-1, to the data to be signed. Most other digital signature schemes, including DSA (called DSS in SSH) and ECDSA, also start by hashing the data, but you didn't ask about them.

RFC8332 says "SSH originally defined the public key algorithms "ssh-rsa" for server and client authentication using RSA with SHA-1".

That is correct, in section 1. Section 3 explains that the same keypairs used for ssh-rsa are reused for the new SHA-2 schemes, but:

   Signing and verifying using these algorithms is performed according
   to the RSASSA-PKCS1-v1_5 scheme in [RFC8017] using SHA-2 [SHS] as
   hash.

   For the algorithm "rsa-sha2-256", the hash used is SHA-256.
   For the algorithm "rsa-sha2-512", the hash used is SHA-512.

(RFC8017 is PKCS1v2.2, which is an update to RFC3447 PKCS1v1.1. The algorithms and schemes are the same, but some new hashes are added. SHS is FIPS 180-4, the current version of the NIST standard defining SHA-1 and SHA-2 including SHA-256 and SHA-512.)

My understanding is that the server computes a hash of the public key using SHA-1 and when appropriate, sends both the public key part and its SHA-1 computed hash with to the client.
Am I correct?

No. The server sends the actual publickey, encoded as shown in RFC4253 6.6 and unchanged in RFC8332 3. As quoted above, the hash (SHA-1, SHA-256, or SHA-512) is applied to the data as part of the signature scheme.

This isn't in any way related to the fingerprint shown when we connect to an SSH server for the first time, is it? If not, how can I calculate it (without ssh-keygen)?

No. If you do want to calculate the fingerprint used by OpenSSH (not necessarily other implementations), it is either MD5 in hex with colons (for older versions) or SHA256 in base64 (for newer versions) of the key encoding sent on the wire. OpenSSH also stores the key blob in base64 in the id_xxx.pub, known_hosts, and authorized_keys files, so rather than actually contructing the encoding you can just base64-decode and hash the appropriate field from one of those files.

If you want to generate or verify a signature in SSH2 protocol, you need the to-be-signed data which as described in RFC4253 section 8 is the 'exchange hash' which is computed over data including the DH shared secret known only to the two endpoints of a particular connection, and so this computation can be and is done only by a program making a particular connection/session like the ssh program.

Answer 2

The principle of SSH is to implement secure (i.e. confidential and authenticated) communication channels in a client–server session. The new release of SSH (known as SSH2) uses public-key infrastructures in order to authenticate servers. This is typically heavy stuff, but the user can easily bypass it: he just has to click “OK” anytime there is a security warning.

• SSH2 uses DSS for server authentication and Diffie-Hellman key agreement for setting up a symmetric session key (previous versions were entirely based on RSA). Both are based on some generator $g$ which generates a subgroup of $\mathbb{Z}^{∗}_p$ of prime order $q$.
• 1. The client picks a random ${x \in \{1,..., q − 1\}}$, computes ${e = g^x \mod p}$, and sends it to the server.
• 2. The server picks a random ${y \in \{1,..., q − 1\}}$, computes ${f = g^y \mod p}$ and ${K = e^y \mod p}$.
• Now server computes the Hash H using various other values and signs it, ${s=sig(H)}$.where ${K_S}$ is his public key, and sends ${K_S}$, $f$, and the signature $s$ to the client. This $H$ could be generated from SHA-1.
• Now, When you connect to a machine for the first time you will be told that the authenticity can't be established and presented with a key fingerprint to check.
• This fingerprint is generated from the server public key may be SHA1 or SHA256.
• you can use:- $ ssh-keygen -lf ~/.ssh/id_rsa.pub