Messages in public SSH RSA keys
I thought it'd be kind of groovy to have a public SSH RSA key that contains a readable message and not only random-looking ASCII, if only to confuse the next guy putting his key on some machine at work...
SSH RSA keys
Let's create a vanilla unencrypted (no passphrase) RSA key pair for SSH:
~/> ssh-keygen -b 1024 -t rsa Generating public/private rsa key pair. Enter file in which to save the key: ./vanilla Enter passphrase (empty for no passphrase): Enter same passphrase again: Your identification has been saved in ./vanilla. Your public key has been saved in ./vanilla.pub. The key fingerprint is: c7:50:7c:60:83:d6:fb:71:90:da:52:ec:f1:45:59:74 firstname.lastname@example.org The key's randomart image is: +--[ RSA 1024]----+ | +=o . oE| | ooo.B .o| | .. B + . | | o+ + o | | S oo o | | . . | | | | | | | +-----------------+
Splendid. Of course now we have the files vanilla and vanilla.pub, which contain the private and public keys respectively. This particular public key looks like this:
ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAIEAztjiJrTBHEH497zGFynVJsCIF ofVEx0kavgBdY+88RbkHVklqKiV2oTKDMRU6JpQW7dcoJUT6zRIAjtimSbReK AlpGD+g42k6CLXyg+1bnuY2ytX20n4uKjbTnYGFZsNDy2qVFjXZ4nPRdE19rH dugpYZG0xUaWK87ZCZp+kFkc= email@example.com
(line breaks added for readability, it's one line)
And we can now put that line into some authorized_keys files on some machines for password-less authentication when we login remotely via SSH.
What to do?
Read the public key
The public key file contains the encryption algorithm as first word: ssh-rsa, the last word is your name and the host the key belongs to: firstname.lastname@example.org, and the middle is the interesting bit.
The middle is a base64 representation of a binary data structure that looks something like this:
4 bytes - unsigned int: length X of string to come X bytes - string: this will be 'ssh-rsa' (7 chars) 4 bytes - unsigned int: length Y of byte array Y bytes - bigint of 'e' 4 bytes - unsigned int: length Z of byte array Z bytes - bigint of 'n'
So this is easily parsed. See wikipedia RSA link above for details of what exactly e and n are for. For now we only need to know that both are relatively large numbers and together (e, n) forms our public key.
Read the private key
We'll also need the private key, because it contains p and q such that pq = n and a key pair can only be generated if we know p and q (at least to our knowledge).
For reading and writing that DER structure I used a Python library called pyasn1, which worked very well.
Generate new public key
Since e comes first and can actually be quite freely chosen, we just have to find some e that together with the other binary data will produce some readable message in the base64 encoded part of the public key.
We do that by first building the beginning of the binary data up to the 4 bytes for the length of the e chunk, which we'll assume to be 0 for now, as we only need the bytes there and don't care what the length will be later. Then we fill up that string with 0 bytes until the total length is a multiple of 6, because every chunk of 6 bytes is encoded to exactly 8 base64 bytes without any padding. Now we encode that string in base64 and in our special case of SSH RSA keys will always get this:
Now we take our message, which will be ++++thialfihar+org++++ in our case (keep in mind the limited base64 charset, so we have to replace spaces), and concatenate it to our base64 beginning:
In order to make this a valid base64 string without padding again we need to get it to a length divisible by 8. We do this by adding more +s, and to get some separation from the rest of the key, let's add 8 +s even if the length is already a multiple of 8. In this case the length is 46, so we only need 2:
Now we have valid base64 encoded data, which we can decode, so we can read the binary data e must start with at the appropriate offset.
We also have to make sure our constructed e will work for our purpose, for which it must suffice gcd(e, phi(n)) == 1, where phi is Euler's totient function. We also should make sure e is a good one. See RSA encryption for details on that, I'll ignore that for now, as I think it is incredibly improbable that the e we just generated is an insecure one. see Security
Now (e, n) forms our new public key.
Find matching private key
Of course we now need to build a new private key as well, so things will actually work. For this we just need to find a d such that ed == 1 mod phi(n). This can easily be done with the extended Euclidean algorithm. Afterwards (d, n) forms our new private key. We also adjust some exponents needed for the DER structure.
Write new keys
Now we just pack everything back into an SSH-readable format. Generating vanilla.new.pub for the public key and vanilla.new for the private one.
vanilla.new looks something like this:
-----BEGIN RSA PRIVATE KEY----- ... Sfi4qNtOdgYVmw0PLapUWNdnic9F0TX2sd26ClhkbTFRpYrztkJmn6QWRwIWAQAA ++++thialfihar+org++++++5wKBgHztCABqupzX2es0+HjbBPe4roRCFeAE8CsV IqYsVuKxz+WeHyE6BL+mDLVueYqOggx5IHYla95Z5WGiBruXBKN+yfR9V+rRDn7b ... -----END RSA PRIVATE KEY-----
and more importantly our public key:
ssh-rsa AAAAB3NzaC1yc2EAAAAWAQAA++++thialfihar+org++++++5wAAA IEAztjiJrTBHEH497zGFynVJsCIFofVEx0kavgBdY+88RbkHVklqKiV2oTKDM RU6JpQW7dcoJUT6zRIAjtimSbReKAlpGD+g42k6CLXyg+1bnuY2ytX20n4uKj bTnYGFZsNDy2qVFjXZ4nPRdE19rHdugpYZG0xUaWK87ZCZp+kFkc= email@example.com
And there we have our message. Interestingly it also shows in the private key file. I haven't looked into that, but I think that'll be due to certain key lengths and isn't always the case, as it'll only happen if our binary data of e starts at an offset divisible by 6 in the DER structure for the private key.
The message could have any length, really, as e could grow as much as you like. I haven't actually tried it with a very long message, mind you. And SSH might very well complain if e > n, even tho that'd work mathematically. Either way, you could make a larger key pair with n having a size of 16KB or more, which would allow a message of roughly 21KB (due to base64 encoding) even if SSH requires e < n.
I'm pretty sure the strength of the new key pair is the same as the strength of the key pair it is based on.
The modulus n is never changed, so it is still as secure a modulus as it was when your initial key was generated.
However, I haven't investigated much what special properties e should have for maximal security. I guess it should be checked whether m^e == m mod n for awkwardly many m, but I think that's a very improbable case.
The fancy keys might be slightly slower for identification or even encryption purposes, as e is used as an exponent in RSA encryption and is usually small. The vanilla keys will often have a one-byte integer, for instance e = 35. Since we build a very large e, any computation using it as an exponent will slow down a little. However, for SSH purposes this shouldn't really be noticible, as the growth is linear in the number of bits of e.
I wrote a Python script to generate a partly semantic key for any SSH RSA key, see page attachments. Syntax for the example is as follows:
/> ./fancy_ssh_rsa_key.py ./vanilla '++++thialfihar+org++++'
All spaces will be replaced by +s and all other non-base64 chars will become /s.
NOTE: the source key pair must be unencrypted, as the script can't read private key files with a passphrase.