Signing data and verifying signatures with ssh keys (and Ruby)

Edward Speyer, March 2011

This page shows you how to sign and verify data using the Digital Signature Standard (DSS) and OpenSSH SSH2 Digital Signature Algorithm keys. Forgive the patronising wikipedia links.

By far the easiest way to all of this is with the net-ssh and sshkeyauth gems, but it's also possible to do everything you need in just a few lines of ruby code instead of having to have a working Gem install and the whopping 500kB of disk space that the two gems require.

Why?

I use duplicity to create backups of a shared Debian host called zubin. The encrypted backup files are stored locally on the same host in a directory that is also a valid chroot (containing rbash and rsync). I have shell access to some remote hosts (under someone else's control). I've configured my accounts on these hosts with passphraseless ssh credentials to log back in to zubin (but as a special user, not as me). They connect to a non-standard instance of OpenSSH 5.8 running on a user port, and the sshd logs this user into the chroot.

This lets these third-party untrusted hosts pull backups from zubin without needing a passphrase, but without giving the admins of thoses hosts any other access to zubin.

To keep track of which hosts have which files and from when, I configure them to list their versions of my duplicity backup files, sign the that list with their ssh keys, and mail the list to me. The lists are verified to be genuine, and parsed into a database.

Academic crypto bit

According to the wikipedia pages and my faded computer science memory, DSA cryptographic data consists of five pieces of data:

a prime q,
a prime modulus p,
some other number g = 2^p-1/q mod p,
a public key computed from these parameters, and
a private key similary computed by using all of the above.

The OpenSSH jargon for these keys (DSA keys that conform to the DSS) calls for them to be referred to as ssh-dss keys.

The private key data

All the above parameters (including the public key) are stored one-per-file in files wrapped with BEGIN and END markers (e.g. ~/.ssh/id_dsa):

The numbers are stored using the ancient data serialisation standard ASN1 -- the data is an ASN1 Sequence of ASN1 Integers.

I don't know the history of ASN1, but I'm sure it was a cool hip technology at about the same time SGML and Emacs were, when you had to dial phone numbers by turning a dial on a grey version of Commisioner Gordon's batman phone.

OpenSSL does all the parsing of private keys for you:

      require 'openssl'
      require 'base64'

      # decode
      key = OpenSSL::PKey::DSA.new(File.read("id_dsa"))

      # encode
      puts key

The public key

OpenSSH stores all the public key data (p, q, g, public-key) on one 8-bit ascii line. The file ~/.ssh/id_dsa.pub usually has one line in it containing your public key on that host, and the file ~/.ssh/authorized_keys contains the public keys of everyone you've authorized to log in as you on that host. Both files can contain comments (# blah blah) and blank lines.

      # Hi.  Welcome to my public key.
      ssh-dss AAAAB3NzaC1kc3MAAACBALVRLP/7bb2nEKkOJsEke2D7Bt+Fjd1OzNlaM..
      ..pzWb8TeDBb76EIBsjW8wdmT959lw9BWn+OyW3SXBQpxEtpw9LtcAvksNkb4T7XW..
      ..mY9NwxWwzukK9owMPJpNzuBP1R8tro4sPv4Zc9IXZYB9n3zWBUk9ODGC6KcOHwH..
      ..dfbet5UilAAAAFQDQP8RpVbO8g5w7ZLjiEin9RxcD5QAAAIANHIT288/9P7N/L+..
      ..ieevUKiCrWfDgIO2HUs4DrbUp5kG2zzwJgquANQ1gM9Qk/mjIgjWytciLkTxNVQ..
      ..7CrRUb7luUrL82iKOo5gGl6tWEEdi4+8fvwyGXUSyHZDb9n/lFUpk3HbJF0wQwt..
      ..HWl1cFvZfgOTbR4C+HjiX6PHTSSm4wAAAIEAocGZEom50vrcZwPl/BtkilfOawp..
      ..t9LQMvAU4xyf94/qPWFOdNsHxQOnCjYn/tpfxas9IK1NCxwA9upYT1Wd4177GN+..
      ..0EX9wXH9BR5hKLCBC0Q5yFszablB5v5jc7gml7sOEnJRoAZlNXqO6h+KXPXqCYO..
      ..uYohGIKJh7OZMZnRaM= edward@lol

The format here is (key-type, base64-key-data, key-comment) and is specific to OpenSSH (ie: OpenSSL won't help you parse this).

Once you've base64 decoded it, the key-data is an OpenSSH "buffer" if (length, data) pairs listing:

key-type as an ascii string, (repeated inside the key-data, even though it's present in the original public key file); and
p,
q,
g, and
public-key as arbitrary length integers

It's easy enough to parse this data in Ruby:

      string = File.read('id_dsa.pub')
      type, blob64, comment = *string.strip.split
      blob = Base64.decode64(blob64)
      raise "unsupported key type: #{type}" unless type == 'ssh-dss'
      values = []
      5.times do
        length = blob.slice!(0, 4).unpack('N').first
        data = blob.slice!(0, length)
        values << data
      end
      blob_key_type, *ns = *values
      bns = ns.map{ |i| OpenSSL::BN.new(i, 2) }
      key2 = OpenSSL::PKey::DSA.new
      key2.p, key2.q, key2.g, key2.pub_key = *bns
      puts key2
      #=> -----BEGIN DSA PUBLIC KEY-----
      #   MIIBogKBgQChwZkSibnS+txnA+X8G2SKV85rCm30tAy8BTjHJ/3j+o9YU502wfFA
      #   6cKNif+2l/Fqz0grU0LHAD26lhPVZ3jXvsY37QRf3Bcf0FHmEosIELRDnIWzNpuU
      #   Hm/mNzuCaXuw4SclGgBmU1eo7qH4pc9eoJg65iiEYgomHs5kxmdFowKBgQC1USz/
      #   +229pxCpDibBJHtg+wbfhY3dTszZWjKc1m/E3gwW++hCAbI1vMHZk/efZcPQVp/j
      #   slt0lwUKcRLacPS7XAL5LDZG+E+11pmPTcMVsM7pCvaMDDyaTc7gT9UfLa6OLD7+
      #   GXPSF2WAfZ981gVJPTgxguinDh8B3X23reVIpQIVANA/xGlVs7yDnDtkuOISKf1H
      #   FwPlAoGADRyE9vPP/T+zfy/onnr1Cogq1nw4CDth1LOA621KeZBts88CYKrgDUNY
      #   DPUJP5oyII1srXIi5E8TVUOwq0VG+5blKy/NoijqOYBperVhBHYuPvH78Mhl1Esh
      #   2Q2/Z/5RVKZNx2yRdMEMLR1pdXBb2X4Dk20eAvh44l+jx00kpuM=
      #   -----END DSA PUBLIC KEY-----

Signing and verifying

With the keys parsed, signing and verifying data is trivial:

      data = 'hello world'
      signature = key.sign(OpenSSL::Digest::DSS1.new, data)
      puts signature.length #=> 46
      p key.verify(OpenSSL::Digest::DSS1.new, signature, data) #=> true

Picking apart the private key data by hand

The ASN1 bit stream is base64 encoded. You can decode the base64 and parse the ASN1 structure easily with the Ruby OpenSSL bindings, which is interesting as an exercise in playing with the libraries:

      string = File.read("id_dsa")
      base64_encoded_part = string.split("\n")[1..-2].join
      asn1_encoded = Base64.decode64(base64_encoded_part)
      asn1_sequence = OpenSSL::ASN1.decode(asn1_encoded)
        #=> #<OpenSSL::ASN1::Sequence ...@value=[#<OpenSSL::ASN1::Integer ... ]>
      _, p, q, g, pub_key, priv_key = asn1_sequence.map{ |o| o.value }
      puts p #=> 1273251926287241494902257614820055664023213260667623398816185911875586477501983403699
             #   8229414714403336520774043623742477462084231474618077195514573556623910620366692991284
             #   4769474211292161016887554365806220530172045315856876480400528309205257761494568025182
             #   899703112679601976441936212592094667131907114474490021

You can turn the OpenSSL::ASN1::Integers into OpenSSL::BN instances (BNs are big-numbers, constructed from strings) and assign them to a new key.

      key = OpenSSL::PKey::DSA.new
      bn_ar = asn1_sequence.map{ |i| OpenSSL::BN.new(i.value.to_s, 10) }
      _, key.p, key.q, key.g, key.pub_key, key.priv_key = *bn_ar

For extra fun, you can then pick the key apart and encode it again in the original format.

      seq = OpenSSL::ASN1::Sequence([
        OpenSSL::ASN1::Integer(0),    # a passphrase field?
        OpenSSL::ASN1::Integer(key.p),
        OpenSSL::ASN1::Integer(key.q),
        OpenSSL::ASN1::Integer(key.g),
        OpenSSL::ASN1::Integer(key.pub_key),
        OpenSSL::ASN1::Integer(key.priv_key)
      ])

      # Ruby wraps at 60 characters instead of 64, but OpenSSH doesn't care
      key_string =
        "-----BEGIN DSA PRIVATE KEY-----\n" +
        Base64::encode64(seq.to_der) +
        "-----END DSA PRIVATE KEY-----\n"

      puts key_string