SSH is a great tool but it can also be pretty complex. Therefore it is often misunderstood, misused or underutilized. In this short series of two articles we’ll go into what SSH is, how exactly it works and how we can use it most effectively and securely, avoiding common pitfalls. Warning, there will be math, but based on simple concepts from school and really useful later on.

Many developers use SSH daily, for tasks like remote administration, deployment, tunneling, firewalls. An essential part of all these are SSH keys, which allow passwordless logins. But for most of us, these are opaque binary blobs of cryptographic material, which we’re told to store securely and don’t hand out left and right. Let’s look inside, to see what are they made of.

Generating a key

Most commonly done by invoking ssh-keygen -t rsa, and often the only thing we use this program for. It can do much more, in fact it is a rich tool for key file management, something outside of the scope of this article. Let’s look at how the key, in the algorithmic sense only, is constructed:

Choose two¹ large primes: $p, q \in \mathbb{P}$.
Calculate modulus $n = p \cdot q$.

Its length (position of leftmost 1 bit) is commonly referred to as key size. If we want to generate a modulus of 2048 bits, then both primes should be 1024 bits long, or about 300 decimal digits.
Calculate totient: $\phi(n) = (p - 1)(q - 1)$.

Euler’s totient $\phi(n)$ is the count of numbers less than or equal to $n$, which have no common divisors with it: $gcd(a, n) = 1$.

By definition then, for a prime $p$ it is equal to $p-1$. For a prime power $\phi(p^k) = p^{k-1}(p-1)$, because there are exactly $(k-1)$ multiples of $p$ that are less then $p^k$, and these do have a common divisor with it (which is $p$). And finally, totient is a multiplicative function $\phi(m\cdot n) = \phi(m) \cdot \phi(n)$ when its arguments are prime, giving us the formula above.

In actual RSA implementations, Carmichael’s totient is used instead: $\lambda(p \cdot q) = {\rm lcm}(\lambda(p), \lambda(q)) = {\rm lcm}(p - 1, q - 1)$ when both are prime. Both totients can be used, but Carmichael’s has additional useful properties, which we’ll discuss further on. ${\rm lcm}(p, q)$ is the least common multiple of given two numbers. $\lambda(n)$ always divides $\phi(n)$.
Pick a public exponent $\mathbf{e} = 65537$

Any number that is coprime to $\lambda(n)$ can be used, and if it happens that 65537 is not coprime, then another one must be chosen. The smallest number that could be used here is 3.

It is more efficient to choose numbers with small Hamming weights (number of ones in their binary representation), as the fast exponentiation methods used in encryption benefit from that. This is why 65537 is commonly chosen, as it’s equal to $2^{16}+1$, so has two one bits set.
Find its multiplicative inverse: a number $\mathbf{d}$ such that $e \cdot d = 1 \bmod \phi(n)$

For example, if our primes were $p = 11, q = 13$, and we used Euler’s totient, then $n=143$ and $\phi(n)=10 \cdot 12 = 120$. We cannot use $e=3$, as $3 \vert 120$, and the next smallest number we can use is $e=7$. Then its inverse is $103$, because $7 \cdot 103 = 721 = 7 \cdot 120 + 1 \equiv 1 \bmod 120$.

Under Carmichael’s totient, we have $\lambda(n) = {\rm lcm}(\lambda(10), \lambda(12)) = \ldots = 60$, which does divide $\phi(n)$ as expected. Then for $e=7$ again, the inverse (modulo $\lambda(n)$) is $43$. Note that $103$ is also an inverse, and is congruent to the other inverse modulo $\lambda(n)$ which is not an accident. Carmichael’s totient tends to produce smaller exponents, which improves encryption performance.

This is the private exponent.

As you can see, the numbers are chosen very deliberately. This is so that the pair of $e$ and $d$ have an important property: that for any $m$,

$(m^e)^d \bmod n = m \bmod n$.

That equation is the core of RSA encryption. Doctrina offers a very readable proof of why that works.

By the way, if you ever need a long prime number, openssl can generate one for you:

openssl prime generate -bits 1024

Distributing keys

Pack together $(e, n)$ and ship it freely, this is your public key.
Keep $(d, n)$ secret, this is your private key.

For performance, other derived values are often stored with the private key. Performant implementations don’t use simple module exponentiation, but rather an optimized method based on the Chinese Remainder Theorem, which uses some values computed from $p, q$ and $d$.

Exposing the public key does not harm your security: an attacker that knows your $(e, n)$ pair would have to spend lots of computing resources to factorize $n$ into $p \cdot q$ to find the totient, and then your decryption key. By keeping $n$ large (thousands of bits in length), the scheme can be tuned to resist newer and faster computers, simply by making it impractically expensive to compute. On the other hand, the encryption and decryption operations are comparatively very cheap!

And all that is inside key files?

Let’s generate one and look inside, again with openssl tools that you most likely already have. However, we need to choose a key format they can read, and the default SSH2 internal format isn’t one. Let’s use PEM:

$ ssh-keygen -q -t rsa -m PEM -f example_key

And look inside the private key:

$ openssl pkey -in example_key -text -noout

RSA Private-Key: (3072 bit, 2 primes)
modulus:
    00:b4:06:c1:1e:d2:e9:10:03:d3:2a:e5:f8:3e:c0:
    b9:65:87:84:3f:96:7c:dd:26:c5:45:00:f7:f3:ee:
    1b:89:81:4b:32:4f:a0:5c:8a:26:0e:ec:ec:fe:c7:
    [snip]
publicExponent: 65537 (0x10001)
privateExponent:
    00:90:23:38:4c:6d:a1:9c:e8:f3:11:cd:be:cc:bf:
    91:b0:f0:a7:ba:21:cb:27:65:fb:5c:1c:42:6a:53:
    [snip]
prime1:
    00:df:ed:5c:5e:ac:75:3a:c2:15:04:3e:b0:8a:2f:
    9c:bd:55:02:7a:c8:5d:30:a9:26:c0:76:e9:db:20:
    [snip]
prime2:
    00:cd:cf:b3:be:2e:4e:1f:53:7e:23:d4:71:1c:da:
    15:a2:41:7c:38:7d:51:0b:05:23:f8:b3:97:7f:c4:
    [snip]
exponent1:
    00:b0:9a:bc:19:f2:bb:b6:2e:b1:72:9a:9a:93:31:
    7f:d5:96:c1:10:e3:0b:14:40:a3:ce:71:3a:78:d6:
    [snip]
exponent2:
    00:88:a2:8c:cd:04:c6:de:ab:3a:82:25:06:d7:45:
    bd:b9:13:ca:99:62:31:0c:a4:e4:05:b7:8d:2b:c8:
    [snip]
coefficient:
    [snip]
    00:a8:e9:c7:92:a8:90:30:d4:92:c0:cb:a9:5b:b2:
    49:38:78:4b:5b:88:09:a3:a6:99:a4:3a:11:5c:f5:

Look at the public exponent - it is 65537, as described. prime1 and prime2 are $p$ and $q$ respectively, and the other three entries are precomputed values for the Chinese Remainder Theorem exponentiation algorithm.

Another look at this file can be obtained with asn1parse. ASN.1 is the data stream format these are stored in, then base64-encoded and wrapped in terminator markers as specified by PEM.

$ openssl asn1parse -in example_key
# depth, header len, length, primitive/constructed, type, data
    0:d=0  hl=4 l=1766 cons: SEQUENCE          
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=4 l= 385 prim: INTEGER           :B406C11ED2E91003D32AE5F83EC0B96587843F967CDD26C54500F7F3EE1B89814B324FA05C8A260EECECFEC7[snip]
  396:d=1  hl=2 l=   3 prim: INTEGER           :010001 # or 65537 in decimal
  401:d=1  hl=4 l= 385 prim: INTEGER           :9023384C6DA19CE8F311CDBECCBF91B0F0A7BA21CB2765FB5C1C426A53[snip]
  790:d=1  hl=3 l= 193 prim: INTEGER           :DFED5C5EAC753AC215043EB08A2F9CBD55027AC85D30A926C076E9DB20[snip]
  986:d=1  hl=3 l= 193 prim: INTEGER           :CDCFB3BE2E4E1F537E23D4711CDA15A2417C387D510B0523F8B3977FC4[snip]
 1182:d=1  hl=3 l= 193 prim: INTEGER           :B09ABC19F2BBB62EB1729A9A93317FD596C110E30B1440A3CE713A78D6[snip]
 1378:d=1  hl=3 l= 193 prim: INTEGER           :88A28CCD04C6DEAB3A822506D745BDB913CA9962310CA4E405B78D2BC8[snip]
 1574:d=1  hl=3 l= 193 prim: INTEGER           :A8E9C792A89030D492C0CBA95BB24938784B5B8809A3A699A43A115CF5[snip]

Note that field numbers are not shown, as they are not encoded in this form, but only specified by the format (PKCS#1 RSA Private Key)). Choosing one of the other two formats produces a SSH-style private key file, because both RFC4716 and PKCS#8 specify a public key format. But asn1parse complains:

$ openssl asn1parse -in example_key
    0:d=0  hl=2 l= 112 cons: appl [ 15 ]
    2:d=1  hl=2 l= 110 cons: appl [ 5 ]
Error in encoding
140236147283136:error:0D07209B:asn1 encoding routines:ASN1_get_object:too long:../crypto/asn1/asn1_lib.c:91:

This key is not ASN.1 encoded. But it still resembles one, because it uses both base64 and PEM delimiter lines. Let’s strip them and look inside:

$ grep -v -- '---' example_key | base64 -d | hexdump -C | head -5
00000000  6f 70 65 6e 73 73 68 2d  6b 65 79 2d 76 31 00 00  |openssh-key-v1..|
00000010  00 00 04 6e 6f 6e 65 00  00 00 04 6e 6f 6e 65 00  |...none....none.|
00000020  00 00 00 00 00 00 01 00  00 01 97 00 00 00 07 73  |...............s|
00000030  73 68 2d 72 73 61 00 00  00 03 01 00 01 00 00 01  |sh-rsa..........|
00000040  81 00 a9 75 c5 14 dd 81  5f 81 19 3d 48 4f 87 8c  |...u...._..=HO..|

grep -v returns lines that don’t match the pattern, and since the pattern starts with dashes like an option, we needed to terminate option parsing with -- before it. The rest is fairly obvious. The format contains:

a null-terminated format id prefix openssh-key-v1
at 0F, a 32 bit length int, and at 13 content for the cipher name, none
length and content for KDF² name, offsets 17 and 1B, again none
length for KDF data, which is zero, followed by zero bytes of KDF data at 1F
32 bit number of keys at 23, fixed to one key per file, so 1
at 27 a 32 bit length of the public part: 00000197, which is 407 decimal
the public key:
1. length and bytes of key type, ssh-rsa at 2b and 2f
2. length and bytes of public exponent at 36 and 3a. Unsurprisingly, the exponent bytes are 010001, which is exactly 65537.
3. length and bytes of the modulus, starting at 3d. The modulus is 385 (hex 0181) bytes long, and starts with 00a975. This is not the same modulus as in previous examples, as the key was generated anew.
following, but not visible in this truncated example, is the actual private key

The public key structure is modeled after RFC4253, and the private part uses a similar scheme, with some padding added.

Prying the lid open

Let’s write a short program to read everything. We’ll use the excellent bindata gem for brevity.

require 'bindata'
require 'ostruct'

def decode_binary(data)
  return nil if data.empty?
  data.each_char.inject(0) { |a, b| (a << 8) | b.ord }
end

# A byte string prefixed by 32 bit length
class String32 < BinData::Primitive
  endian :big
  uint32 :len
  string :data, read_length: :len

  def get
    data
  end
end

# Bignum32, a variant of String32 that displays as a bignum.
class Bn32 < String32
  def get
    decode_binary(data)
  end
end

class SSHKeyFormat < BinData::Record
  endian :big

  stringz :format # "openssh-key-v1"
  string32 :cipher # "none" when key file is not encrypted
  string32 :kdf # also "none"
  bn32 :kdf_data # nil if not encrypted, which bindata omits from output

  uint32 :num_keys # hardcoded to 1
  uint32 :pubkeys_len # length of following pubkey block
  array :pubkeys, initial_length: :num_keys do
    struct :pubkey do
      string32 :key_type # "ssh-rsa"
      bn32 :e # public exponent
      bn32 :n # modulus
    end
  end
  uint32 :privkey_len # length of following privkey block
  struct :privkey do
    uint64 :checksum # padding or checksum, not important
    string32 :key_type # "ssh-rsa"
    bn32 :n # modulus
    bn32 :e # public exponent
    bn32 :d # private exponent
    bn32 :coeff # CRT helper value: q^(-1) mod p
    bn32 :p # prime 1
    bn32 :q # prime 2
    string32 :comment # user@host by default, can be edited through ssh-keygen
    # And some irrelevant padding
  end
end

key = SSHKeyFormat.read(STDIN)
# Validating the file
pub = OpenStruct.new(key[:pubkeys].first)
priv = OpenStruct.new(key[:privkey])
# NOTE: the `get`s are necessary, because the hash contains bindata wrapper types, not ruby types
fail "pubkey modulus different from privkey" unless priv.n.get == pub.n.get
fail "pubkey exponent different from privkey" unless priv.e.get == pub.e.get
fail "modulus is not a multiple of p and q" unless priv.p.get * priv.q.get == priv.n.get
enc = (42).pow(priv.e.get, priv.n.get) # RSA Encryption
dec = (enc).pow(priv.d.get, priv.n.get) # and decryption
fail "e and d are not public and private exponents mod n" unless dec == 42
fail "coeff is not inverse of q mod p" unless (priv.q.get * priv.coeff.get) % priv.p.get == 1

Run this with:

$ grep -v -- '---' example_key | base64 -d | ruby parsekey.rb

AJ O’Neal did some sleuthing on this topic, and offers some insight as well as links to relevant sourcecode in Portable SSH (which is not OpenSSH, but is very compatible).

Two-in-one

So the private key file actually contains both the public and private keys, with modulus and public exponent stored twice. Even if you lose your public key file, it is easy to regenerate it from that private key:

# Reads private key, outputs corresponding public key in OpenSSH format
$ ssh-keygen -y -f example_key > example_key.pub
# Alternatively: reads private or public key, exports public key in chosen format
$ ssh-keygen -e -m FORMAT -f example_key > example_key.pub

And the public key

OpenSSH accepts three public key formats: PKCS#8, RFC4716 and its internal oneliner. Starting with the last one:

$ ssh-keygen -y -f example_key
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABgQCpd[...] user@host

The last field is a comment, the first is obviously key type, but what’s the middle part? Looks like Base64 again.

$ ssh-keygen -y -f example_key | cut -d' ' -f2 | base64 -d | hexdump -C
00000000  00 00 00 07 73 73 68 2d  72 73 61 00 00 00 03 01  |....ssh-rsa.....|
00000010  00 01 00 00 01 81 00 a9  75 c5 14 dd 81 5f 81 19  |........u...._..|
00000020  3d 48 4f 87 8c fc 5b 05  90 05 bd 05 82 93 f4 0a  |=HO...[.........|
00000030  05 ca 5b f4 d6 cb 36 48  9a cc 43 33 b2 ec 59 b3  |..[...6H..C3..Y.|

Well, we’ve seen that before - it’s the public key part described previously (where it was placed at offset 2b). There’s key type, public exponent 010001, and the modulus starting with 00a975. And the whole body has length 407, or hex 197, which was also the length of public key part before.

PKCS#8 is processably by openssl tools again:

$ ssh-keygen -e -m PKCS8 -f example_key | openssl rsa -pubin -noout -text
RSA Public-Key: (3072 bit)
Modulus:
    00:a9:75:c5:14:dd:81:5f:81:19:3d:48:4f:87:8c:
    [snip]
Exponent: 65537 (0x10001)

$ ssh-keygen -e -m PKCS8 -f example_key | grep -v -- '---' | base64 -d | openssl asn1parse -inform DER
    0:d=0  hl=4 l= 418 cons: SEQUENCE
    4:d=1  hl=2 l=  13 cons: SEQUENCE
    6:d=2  hl=2 l=   9 prim: OBJECT            :rsaEncryption
   17:d=2  hl=2 l=   0 prim: NULL
   19:d=1  hl=4 l= 399 prim: BIT STRING

# Inspecting the BIT STRING above by using -strparse with an offset
$ ssh-keygen -e -m PKCS8 -f example_key | grep -v -- '---' | base64 -d | openssl asn1parse -inform der -strparse 19

    0:d=0  hl=4 l= 394 cons: SEQUENCE          
    4:d=1  hl=4 l= 385 prim: INTEGER           :A975C514DD815F81193D484F878CFC5B059005BD058293F40A05CA5BF4D6CB36489ACC[snip]
  393:d=1  hl=2 l=   3 prim: INTEGER           :010001

Which by this point we recognize as the modulus and public exponent. Finally, RFC4716 has a slightly different format:

$ ssh-keygen -e -m RFC4716 -f example_key | head               
---- BEGIN SSH2 PUBLIC KEY ----
Comment: "3072-bit RSA, converted by user@host from OpenSSH"
AAAAB3NzaC1yc2EAAAADAQABAAABgQCpdcUU3YFfgRk9SE+HjPxbBZAFvQWCk/QKBcpb9N

But the insides are still Base64, so let’s open them:

# Using grep -E to have a richer pattern stripping both delimiters and the comment
$ ssh-keygen -e -m RFC4716 -f example_key | grep -Ev -- '---|Comment' | base64 -d | hexdump -C
00000000  00 00 00 07 73 73 68 2d  72 73 61 00 00 00 03 01  |....ssh-rsa.....|
00000010  00 01 00 00 01 81 00 a9  75 c5 14 dd 81 5f 81 19  |........u...._..|
00000020  3d 48 4f 87 8c fc 5b 05  90 05 bd 05 82 93 f4 0a  |=HO...[.........|
00000030  05 ca 5b f4 d6 cb 36 48  9a cc 43 33 b2 ec 59 b3  |..[...6H..C3..Y.|

We’ve already seen this exact thing twice - it’s the RFC4253-style key. Same thing, different wrapper.

Not only RSA

However, OpenSSH can use keys in other formats - most notably, Elliptic Curve Cryptography (ECC keys), either ECDSA or ED25519. We’ll not delve into the algorithm this time, as it requires more complex mathematics. Key files for the latter use a basically identical structure, save for a different parameter set, as they don’t use moduli and exponents. ECDSA keys in PEM format can be inspected with openssl:

$ ssh-keygen -f example_ec -t ecdsa -m PEM 
$ openssl pkey -text -noout < example_ec
Private-Key: (256 bit)
priv:
    4d:4d:e3:44:78:48:fb:9f:01:26:21:fa:12:21:6a:
    55:1c:59:ff:e1:bd:d4:7a:63:e5:9a:c1:46:e5:04:
    79:b1
pub:
    04:ff:f1:f4:5c:41:66:53:9d:ee:cd:08:3a:0a:72:
    72:95:30:88:f3:81:d6:8f:47:21:72:21:9d:60:c2:
    3e:e8:4c:1f:af:88:fe:c1:c4:21:7a:93:2d:7c:6c:
    d5:45:21:3f:8b:39:2c:50:6e:a5:b7:e6:eb:04:59:
    1a:37:b6:e5:fb
ASN1 OID: prime256v1
NIST CURVE: P-256

To be continued

Now that we know (almost) everything about SSH keys, it’s time to put them into good use. We will go into that in second article, starting with key handling and security concerns worth knowing.

Multi-prime RSA is also a thing, although not commonly used. PKCS#1 specifies a format for multi-prime private keys. ↩
Key Derivation Function. As this key is not encrypted with a passphrase, there is no KDF involved. ↩

Rebased Team writing about tech we use.

Languages, frameworks, libraries, tools. Certified for 0% fluff.

SSH Key Internals

Krzysztof Zych