SSH key file formats

File: key-formats.txt/md/pdf

You may work in groups of size 1-3 for this assignment.

Goals

• Learn some ways cryptographic keys are stored in practice
• Learn a little about ASN.1, DER, PEM, and the PKCS standards documents.

Rubric

Background

When we first talk about public-key encryption and key exchange protocols, we talk in abstract mathematical terms. For RSA, for example, we talk about prime integers p and q, least common multiples, modular exponentiation, etc. But if you want to use these mathematical ideas in a practical encryption system, you need to deal with concrete questions like "how are we going to store private and public keys?"

In this assignment, you're going to look at the various standards specifications that are used to store keys for use in the SSH protocol.

Do a little reading first

• Start learning about ASN.1 and DER by studying the Example section of the ASN.1 Wikipedia page.
• Read this brief description of the Distinguished Encoding Rules (DER)
• Skim the Wikipedia page about PEM
• Open a tab to (RFC 4716) The Secure Shell (SSH) Public Key File Format
• Open a tab to (RFC 8017) PKCS #1: RSA Cryptography Specifications Version 2.2. You'll probably want to scroll down to Appendix A.1.
• You might find this intro to ASN.1 and DER from Let's Encrypt handy.

Your job

In your key-formats.* file, include the following.

1. Create an RSA public/private key pair that you will use throughout the rest of this assignment.

   ssh-keygen -t rsa -m pem

   When you are asked to pick a file name, use "id_rsa_homework" so you can remember to delete these files when you're done with the assignment. (You're going to be posting your observations in a public GitHub repo, so you're not going to ever actually use this key pair for anything.)

   Copy the contents of id_rsa_homework and id_rsa_homework.pub into your key-formats.* file.

2. Put a heading in your report: "Private Key"

3. For your private key file (id_rsa_homework), list the items you expect to be contained in the file. (Hint: the Appendix of RFC 8017 should help.)

4. Use one or more of the following tools (findable by searching the internet for "web asn.1 decoder") to decode your private key file.

   • Lapo Luchini's ASN.1 decoder
   • OSS Nokalva's ASN.1 Playground
   • Michael Holtstrom's ASN.1 decoder

   Explain briefly the steps you took to decode the private key file.

5. For each integer in your decoded private key file, tell me:

   • What is the meaning/name of the integer? This should correspond to one of the items in your answer to the previous question, articulated as an ASN.1 name from the specification in RFC 8017.
   • What is the value of the integer? Write the integer in either decimal or hexadecimal, whichever is more convenient. If hexadecimal, prepend the integer with "0x".

6. Next, we're moving on to the public key file id_rsa_homework.pub, so put a heading in your report: "Public Key"

7. Do the same things you did for the private key: write down what you expect to find in id_rsa_homework.pub and why; explain how you decoded the file; for each integer in the file, provide its name, value, and any other relevant details. Unlike with the private key, I'm not telling you exactly where to look in the specifications to figure out this key's file format. (Though you might find this blog post by Leonardo Giordano handy. Aren't I nice?)

8. Put one last heading in your report: "Sanity check"

9. Demonstrate that the integers you found in these two files work as you expect from an RSA key pair. For example, does e*d mod lambda(n) = 1? There are various relationships that you would expect these numbers to have, so show me that they do in fact have those relationships.

Late-breaking advice

Let me try to clarify some of what's going on with the public key file.

First, the ssh-keygen command is part of a larger software package called OpenSSH. The OpenSSH people, in their wisdom, designed some file formats that are different from the private-key format you're looking at in this assignment. That's why if you leave out the -m pem part of the command shown above, you'll get an OpenSSH-specific private-key file format, which is not what I wanted you to study for this assignment.

But it turns out that even if you use the -m pem flag, the public key file you get is in an OpenSSH-specific format. That's cool, but it makes dealing with this public key a little harder than the private key for this assignment.

Choice #1: convert your id_rsa.pub file to PKCS#1 PEM form

I'm assuming your public key file is named id_rsa.pub. You can convert it from OpenSSH form to the more generic PKCS#1 PEM file format like so:

The Michael Holtstrom decoder linked above can handle this, but now that I say that, it turns out he has a 2022 note at the top of his page that says he has a newer, better version of his decoder, and he's absolutely right. So you can paste your id_rsa.pub.pem file into this newer decoder and get the decoded version of the RSAPublicKey object in question.

Choice #2: work directly with the OpenSSH public key

Roughly, I did this:

• Read this helpful, short blog post
• Make a copy of the id_rsa.pub file to pub.base64, and then delete all the non-base64 crap from the pub.base64 file (so, delete the "ssh-rsa " from the beginning of the file, and the computer name or other comment from the end of the file).

• Use this command

  cat pub.base64 | base64 -d > pub.binary

  That should give you the raw version of this key in pub.binary.

• Look at the section of the blog post linked above that starts with the words "For an ssh-rsa key, the PEM-encoded data is...". If you do hexdump -C pub.binary, you can see that the first 4 bytes are a length, the next N bytes are the "ssh-rsa" string, the 4 bytes after that are another length, etc. Your (n,e) are right there for the taking.

I'm happy with either choice. I hope this helps.