Not long after the previous article on ssh-keygen, OpenSSH released a whole new version of SSH and related tools. This version came with many changes, the most notable one being the support of FIDO/U2F keys. In this post we summarize these changes, and try to explain some of the inner workings. We’ll focus on ssh-keygen here, and mention other tools when necessary.

Group moduli generation demoted

Quick reminder: moduli (plural of modulus¹) are the parameters of the Diffie-Hellman exchange, a key step of establishing symmetric encryption in the SSH transport protocol. OpenSSH allows users to generate their own set (instead of using a fixed one) and there is also a primality testing step involved. Previously, the two were done with dedicated options -G and -T (to Generate and Test, respectively), plus a couple of flags to control their behavior. Now both are hidden behind -M generate and -M test (with M standing, presumably, for Moduli), and -O for their options. The latter now does double duty: both for its original purpose of specifying options for certificate signing, and for moduli generation and testing.

New operations: signing and verification

…with -Y sign and -Y verify, respectively. This operation is similar to GPG signing and verification, but performed using SSH keys. Portable OpenSSH has a concise document describing how the signing works. Briefly: data is prepended with a preamble SSHSIG, followed by a namespace string and the hash algorithm’s name; then hashed. This is then fed to the signature algorithm². The output is a short companion file to the input named on the command line, suffixed with .sig. Mandatory parameters are only the key -f key_file, and we can optionally specify the -n namespace.

To verify, we first need an authorized signers file. It’s similar to the authorized_keys file, where each line must contain:

principals - a comma-separated list of user@domain identifiers
options, currently either cert-authority or namespaces="namespace-list" – the first one tells ssh-keygen to accept signatures from any key that is signed with this certificate³, and the latter restricts possible namespaces for which the key is valid; this field can be omitted
key type (e.g. ssh-rsa)
public key, in the same format as for authorized_keys

This must be then provided with -f signers_file, together with -n namespace and -I identity (identity is used to locate the proper public key in the allowed signers file). The signature file itself is provided with -s filename.sig. We can also optionally add -r revoked_keys with a KRL or public-key list revocation file. Finally, the file to be verified is fed on stdin.

There are two more related operations. The first one is -Y find-principals, which checks if we have an entry for the signer. If we provide -s filename.sig and -f signers_file then the public key used in the signature will be matched against each entry, and if found, the principals will be printed on stdout. The other one is -Y check-novalidate, which verifies that the signature file isn’t corrupted, but performs no other validation. Give it the namespace with -n, signature file with -s and feed data on stdin.

It appears that this kind of signing hasn’t gained popularity yet. Notably, it won’t currently work for Git signatures. While Git does allow replacing the program used for signing, it must still behave exactly like GPG. There is also a concern that using the same keys for both login and signing weakens their security model – something that the namespace parameter addresses to some degree.

FIDO/U2F tokens

SSH can now use (mostly cheap) FIDO/U2F tokens similarly to (more expensive) PIV tokens, as a required step in authentication. An announcement from late 2019, on the openbsd-tech mailing list, explains the big picture:

You’ll get a public/private keypair back as usual, except in this case, the private key file does not contain a highly-sensitive private key but instead holds a “key handle” that is used by the security key to derive the real private key at signing time.

In other words: stealing your private key file is no longer sufficient. The attacker also needs to possess the physical U2F token.

Currently, two types are supported: ecdsa-sk and ed25519-sk (pass the type to ssh-keygen with -t as usual), the latter only on some hardware. SoloKey SOMU does not support it, and neither does my YubiKey 4. It appears that YubiKeys with firmware version 5.2.3 or higher do support it – however, for security reasons, there is no way to upgrade a YubiKey’s firmware, so I’m stuck.

During key creation you’ll be asked to perform the user presence confirmation. In the case of USB tokens, this requires you to touch the designated contact area. If the token has LEDs, they should also be flashing. The U2F spec describes alternative methods that devices may support, including biometrics such as fingerprints; and more complex displays than just a single LED.

In the end you get two files as usual: the public and private key. As noted, the private key actually contains only the key handle – the real private key is derived from that plus the device’s baked-in key. This allows producing and verifying an unlimited number of keys from a single device with no storage requirements. For an attacker, this key handle is useless without the physical device.

Not widespread yet

Install the public key on your servers (with ssh-copy-id, of course), but check that their sshd is new enough to support the new key type. Linux distributions usually support it in their latest releases.

Distribution	Supported	Notes
Ubuntu	since 20.04	not in 18.04 LTS; all flavors and derivatives as per their upstream version
Fedora	since F32
Debian	only in sid	not in stable (buster)
Arch	yes	rolling release model; also applies to derivatives like Manjaro
RHEL8, CentOS	no	all versions too old
OpenSUSE	yes	in Leap 15.3 and in rolling (tumbleweed)
Amazon Linux 2	no	too old

Support in popular services is poor at the moment (February 2021): neither GitHub nor Bitbucket accept a sk-ecdsa key. Support for GitLab is incoming. Gitea merged support in late 2020. Also, no support in alternative open-source SSH server implementations: Dropbear and wolfSSH. This is not really surprising, since it’s brand new (only about a year since its initial release), and FIDO tokens are also quite a recent thing.

Peeking inside

Let’s use Ruby and BinData again to see the innards of these new key types. We can’t use the previous code directly, since it was specific to RSA keys. But we can reuse most of it, especially the encryption parts, while replacing the rest.

class PlainSSHKey < BinData::Record
  endian :big

  bn32 # ignore kdf_data
  # Using bindata's built-in assertions
  uint32 :num_keys, assert: 1
  uint32 :pubkeys_len
  array :pubkeys, type: :ecdsa_pubkey, initial_length: :num_keys
  uint32 :privkey_len
  ecdsa_privkey :privkey
  string32 :comment
  # Plus some padding
end

Very little changed here: we declared types for public and private keys (and no longer decode the latter as a nested struct).

The public key contains a single EC Point, plus some metadata:

class ECDSAPubkey < BinData::Record
  endian :big
  string32 :key_type
  string32 :curve
  ec_point :q, curve: :curve, assert: -> { q.on_curve? }
  # Changed with -O application= at key creation time
  string32 :application, assert: 'ssh:'
end

EC Point

An elliptic curve point is, well, a point on a known elliptic curve. We’ll not delve into the maths in this post; suffice to say it’s usually⁴ a pair of values \((x, y)\) that satisfy the curve’s equation \(y^2 = x^3 + ax + b\), and all the values – including the \(a\) and \(b\) coefficients – belong to a finite field of numbers. In our case that field is the set of numbers smaller than \(2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\).

OpenSSL – or rather its Ruby binding – doesn’t give us an easy way to check the exact values of \(x\) and \(y\). We’ll treat this as a primitive data type⁵. BinData will also check whether the point is valid (i.e., actually lies on the curve) during parsing.

class ECPoint < BinData::Primitive
  mandatory_parameter :curve
  string32 :q

  def group
    curve = eval_parameter(:curve).to_s
    ec = OpenSSL::PKey::EC.new(CURVES[curve])
    ec.group
  end

  def get
    OpenSSL::PKey::EC::Point.new(group, q.to_s)
  end
end

The elliptic curve used in the process is actually stored twice: in the key type string [email protected], and in the curve name field: nistp256. Unfortunately the naming used by OpenSSH doesn’t match that of OpenSSL. We’ll use a mapping between the two.

CURVES = {'nistp256' => 'prime256v1'}

Private key

It contains the same data as the public key, plus the key handle string discussed above.

class ECDSAPrivkey < BinData::Record
  endian :big
  uint32 :check_a
  uint32 :check_b
  string32 :key_type
  string32 :curve
  ec_point :q, curve: :curve, assert: -> { q.on_curve? }
  string32 :application, assert: 'ssh:'
  int8 :flags
  string32 :key_handle
  string32 :reserved
end

The values check_a and check_b are the decryption guards, explained in an appendix to a previous post. The EC point \(q\) is just the public key. The flags contain some options for key usage.

If this was an ecdsa (and not an sk-ecdsa) key, it’d contain the actual private key: a bignum that can be used to calculate the public key given the curve parameters (but not vice versa). Instead, it contains only the key handle, and it’s the token hardware that will recompute the private key and perform cryptographic operations – never revealing it to the host machine. The public key is also derived from that handle, but kept in the key file for convenience.

Encrypted keys

Again, very little change is needed, only the types of public and private key blocks need updating.

class EncryptedSSHKey < BinData::Record
  mandatory_parameter :cipher
  endian :big

  bcrypt_data :kdf_data
  uint32 :num_keys, assert: 1
  uint32 :pubkeys_len
  array :pubkeys, type: :ecdsa_pubkey, initial_length: :num_keys

  uint32 :enc_len
  virtual :assert_blocklen, assert: -> { enc_len % CIPHERS[cipher.to_s].block_size == 0 }
  string :enc_privkey, read_length: :enc_len

  def privkey
    decoder = OpenSSL::Cipher.new(cipher_params.name).decrypt
    decoder.key, decoder.iv = key_and_iv
    data = decoder.update(enc_privkey.to_s)
    ECDSAPrivkey.read(data)
  end

Now, running the program on an encrypted sk-ecdsa key displays the inner bits:

# Passing the passphrase on command line
$ grep -v -- --- id_sk_enc | base64 -d | ruby ~/ecdsa_pkey.rb 123456
{:kdf_data=> {:salt=>"\xB9\x05\xFA\x1D\xCC3B}V\xA0$V\x10\x01R\x88", :rounds=>16},
:num_keys=>1, :pubkeys_len=>127,
:pubkeys=>
  [{:key_type=>"[email protected]",
    :curve=>"nistp256",
    :q=> #<OpenSSL::PKey::EC::Point:0x000055d3ef59ca40 @group=#<OpenSSL::PKey::EC::Group:0x000055d3ef59cb30>>,
    :application=>"ssh:"}],
:enc_len=>240,
:enc_privkey=>
  "\x1A\xC7Q\x12\xE5\...[truncated]"}
# And the private key
{:check_a=>2135720368,
:check_b=>2135720368,
:key_type=>"[email protected]",
:curve=>"nistp256",
:q=> #<OpenSSL::PKey::EC::Point:0x0000562cad526068 @group=#<OpenSSL::PKey::EC::Group:0x0000562cad526130>>,
:application=>"ssh:",
:flags=>1,
:key_handle=>
  "\x9B\xB0\xA0U\x1Ds\xCAu\x7F[truncated]",
:reserved=>""}

The full code is available for download.

Some other words with this declension: cumulus (a cloud), annulus (a torus or donut shape), and of course calculus. ↩
Which computes another hash function, and encrypts the result with your private key. ↩
See the previous article for a primer on certificates. ↩
\(y\) can be omitted and calculated from \(x\). FIDO mandates using the uncompressed form, with both values. ↩
The full code includes a workaround for BinData, because EC::Point resents being compared to nil. ↩

Rebased Team writing about tech we use.

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

SSH Keygen: a 2021 update

Krzysztof Zych