SSH public keys

A while ago I added some basic SSH public key checking to Mango. This for two reasons:

  • Avoid email back and forth in case of copy/paste error
  • To ensure the key is long enough

The key length checking was mostly a hack. I did that by checking if the number of bytes was larger than the number of bytes in a test SSH public key. I never actually knew how many bits the key had. The added benefit was that I figured out how the fingerprint is generated. I always wanted to determine the key length, but couldn’t be bothered. Of course, I could’ve used ssh-keygen, but I don’t like to start another process. It doesn’t actually matter to do a full check. This as the person providing the key wants it to work. We’ll probably get a mail when the public key was broken on purpose. Exception being the key length, as we don’t want too short keys (security issue).

Today I figured out how to determine the key length for RSA and DSA public keys. I’ll start with an example public key (wrapped for readability):

ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAP8zwqYE675bpnYzui0pLNd2XyoB+
v4RtlK2QJ6+42w3VWREbDfeeUmvenLBzdcffs602WOuWB1DrbhjEv4CbABH/u
O89IMlC4h62wel7BfiQqEq6yKW0B+yqQxIsBQPhu8ID0gXrt0uhlPaHkqD1XR
WM9ywr5UP1K51cTPRZu8xQVtpCDMgppa/FwZTKY/+l3HXvu01/NAaNGMPOD3y
neIturzKi3x4f5Id65V1KD70B5YiCiJxFSevOcPx3yYYy+NQN52EBGLf76a78
1S2MiPcHxhoQtG8EPfAhWN3MmOnEd4iuy2IzHdyAK+LCp5Qtyy3mbKTBKSKQb
vrsm8jrjE= olav@bkor.dhs.org

The ssh-rsa is the key type; ssh-rsa for RSA and ssh-dss for DSA. After that there is a space and then the data (easily recognizable as base64 encoded). After the base64 data there is another space followed by a comment (contents doesn’t matter for SSH, you can change it with a text editor). The fingerprint of a key is nothing more than the MD5 hash of the base64 decoded data. The md5 hash of the example public key is 6f8c83c826ee51535a813756ff1bc9b5. The ssh-keygen program shows this with colons.

If you’ve compared a few public SSH keys, you probably noticed that the start of the base64 data is always the same (for the same key type). This is because the data itself again contains the key type (‘ssh-rsa’). The data is encoded using a big endian number (4 bytes) providing the number of bytes of the string that follows. A hex editor will show 00 00 00 07 for the first 4 bytes. After these 4 bytes follows either ‘ssh-rsa’ or ‘ssh-dsa’. The rest of the data is key type specific.
For RSA, the key type is followed by 2 strings encoded using the same method. These strings actually represent ‘bignum’s. However, I don’t care about that. For DSA, 4 strings (bignums) follow after the key type, also encoded using the same method. For RSA you’ll want the 2nd bignum. For DSA the 1st bignum.

When you have such a bignum you’re very close to determine the key length. It is mostly just determining the number of bits needed for the bignum. You could do this by determining the number of bytes used by the bignum and multiplying it by 8. However, you have to deduct a few bits. This as the first byte causes the bignum to use more bits than it actually needs. For example, if the following are the first two bytes (shown as binary) out of the total 255 bytes used for the bignum:

00110011 11000010

You’ll note that the first two 0′s aren’t actually needed. So instead of calculating 255*8 (2040), you should subtract it by 2 bits. Resulting in a key length of 2038. This is what ssh-keygen will give you if you try the example public ssh keyfile shown above (make sure to unwrap the lines and remove the spaces in the base64 encoded data). Looking back, it actually is pretty easy.

Oh, and the reason why I want to know the exact key length is to add a check against blacklisted keys. For this I need to know the actual length of a key. I figured above out partly myself, partly by reading python-paramiko source (unfortunately I overlooked the public key reading part) and partly by trying to understand the openssh code. Running ssh-keygen would’ve been loads easier, but IMO nasty (especially when someone has multiple keys) and also not as interesting. Further, if you use Python instead of PHP (blergh!), just use python-paramiko.