Previous parts: 1, 2. 3. survey.
As you may see, SSH server and client usually offers a lot of different algorithms. Why not using a single one, just the best one? This is because shit happens. SHA1 was once broken ('SHAttered') and it can be expected that this can happen with any other algorithm. Even a renowned world-class expert like Ron Rivest ('R' in RSA) has produced an algorithm later broken: MD5. In such a case of emergency, sysadmins can just disable offending algorithm in SSH server config and switch to other.
So if a server has a list of algorithms to offer: A, B, C, D, and a client has its own list: D, B, X, Y, first common will be tacitly picked, but with priority left to client. In this case: D.
Pythonesque pseudocode:
for client_algo in client_supported_algorithms:
for server_algo in server_supported_algorithms:
if client_algo==server_algo:
return client_algo
# no common algorithm found.
# we can't go any further, report error and shutdown.
In my previous parts, I started with diffie-hellman-group-exchange-sha256. Which was probably a bad idea. This method is slightly more complex than others -- a SSH server first negotiate about DH group (g/p). But SSH have other DH algorithms, with hardcoded g/p DH parameters, taken from RFC, such as: diffie-hellman-group14-sha1, diffie-hellman-group16-sha512, diffie-hellman-group1-sha1. Parameters are known to everyone, but this is OK.
What if a DH algorithm produces only 160 bits (SHA1's digest), but encryption algorithm requires 512 bits (SHA-2-512)? And encryption algorithm requires 256 bits (AES-256)?
Naive solution is just to copy key several times so to fill inputs of SHA-2-512 and AES-256.
But the official SSH standard is more complex and considered more secure:
If the key length needed is longer than the output of the HASH, the
key is extended by computing HASH of the concatenation of K and H and
the entire key so far, and appending the resulting bytes (as many as
HASH generates) 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 || H || X || session_id) (X is e.g., "A")
K2 = HASH(K || H || K1)
K3 = HASH(K || H || K1 || K2)
...
key = K1 || K2 || K3 || ...
This process will lose entropy if the amount of entropy in K is
larger than the internal state size of HASH.
( RFC 4253 7.2 )
What is the difference? DSA is the algorithm and DSS is the NIST standard.
First, there was ElGamal in mid-1980s: 1, 2.
Then there was Claus P. Schnorr with his own scheme, that was kind of upgrade to ElGamal, and worked faster. But it was patented. Patent expired in 2008, and now it can be used even in Bitcoin. To circumvent this patent, NIST published modified scheme, named DSA. So Schnorr's scheme and DSA are very similar. For more information.
Also:
In 1991, NIST proposed the Digital Signature Algorithm (DSA) as an attempt to avoid the patents on Schnorr signatures. For this reason, DSA is a weird variant of Schnorr signatures, published without a proof of security (although no attacks have been found so far). The algorithm was adopted by many but was quickly replaced with an elliptic curve version called ECDSA (for Elliptic Curve Digital Signature Algorithm), the same way Elliptic Curve Diffie-Hellman (ECDH) replaced Diffie-Hellman (DH), thanks to its smaller keys (see chapter 5). ECDSA is the second signature algorithm I will talk about in this section. After the patents on Schnorr signatures expired in 2008, Daniel J. Bernstein, the inventor of ChaCha20-Poly1305 (covered in chapter 4) and X25519 (covered in chap- ter 5), introduced a new signature scheme called EdDSA (for Edwards-curve Digital Signature Algorithm), based on Schnorr signatures. Since its invention, EdDSA has quickly gained adoption and is nowadays considered state-of-the-art in terms of a digi- tal signature for real-world applications. EdDSA is the third and last signature algo- rithm I will talk about in this section.
( David Wong -- Real-World Cryptography )
DSA was used in OpenSSH till version 7.0 (not inclusive), then dropped. No one really knows why. DSA is still secure and can be used with keys larger than 1024 bits (but SSH used only keys with this length).
So far, we should know these facts about DSA:
DSS algorithms is defined in FIPS 186-3. DSA proof and more details are published in FIPS 186-1.
I implemented it with test vectors, as an exercise.
And then I implemented it in my toy SSH client. Works with clients which still support it. DSA key can still be generated by OpenSSH: ssh-keygen -t dsa. Resulting files: id_dsa, id_dsa.pub. As in case of RSA SSH keys, id_dsa.pub is also base64-encoded blob, containing p, q, g, y.
Download latest version: ~1600 SLOC.
UPD 20240529 13:34:05 EEST: Next part: SSH protocol dissected, part V: toy SSH client with ECC in ~2k SLOC of Python
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.