Things I did randomly last week
I actually have like 3 post drafts queued before this, 2 reviews for the Hibike! Euphonium ending, and a note on how I rewrote shreds with ES2015, ractiveJS, and a bastardized Flux architecture.
But anyway, I kind of in the mood for writing about things I did last week.
So it just came to me that it’s probably about time to rotate my SSH keys, random public keys started to piled up at my GitHub and Bitbucket account and I decided to remove them all and start with the new one. Then I went to also removing old keys from some of my servers. Few days later apparently my DNS proxy refused to connect since I forgot to change its key. That when I realized that apparently Go implementation of SSH currently doesn’t have support for reading the new Ed25519 key.
After some digging, I found out that openssh also using new format for this key. Its ASCII layout is based on PEM format, but the base64 blob no longer using ASN.1’s DER encoding. The new Key protocol using simple length prefixed format and described at PROTOCOL.key file located in the root of openssh source folder.
The current Go’s SSH implementation actually supports Elliptic Curve crypto but only specific to ECDSA based keys. Adam Langley already wrote Ed25519 primitives for Go but seems not bothered to integrate it to SSH.
I started with looking at internal structure of the private key, using ruby oneliner:
adie@millefeuille:~ $ cat ~/.ssh/test_ed25519| egrep -v ^- | ruby -ne 'print $_.gsub("\n","").unpack("m").first' | xxd
00000000: 6f70 656e 7373 682d 6b65 792d 7631 0000 openssh-key-v1..
00000010: 0000 046e 6f6e 6500 0000 046e 6f6e 6500 ...none....none.
00000020: 0000 0000 0000 0100 0000 3300 0000 0b73 ..........3....s
00000030: 7368 2d65 4323 5353 1390 0000 0200 1238 sh-eC#SS.......8
00000040: b3c2 2fa8 3343 ae98 b80d 9576 9eca 95e9 ../.3C.....v....
00000050: 3ff0 d3ec 9121 d023 9f1e 25f3 a040 0000 ?....!.#..%..@..
00000060: 098c b71f eb4c b71f b400 0000 0b73 7368 .....L.......ssh
00000070: 2d65 6432 3535 3139 0000 0020 0123 8b3c -ed25519... .#.<
00000080: 22fa 8334 3ae9 8b80 d957 69ec a95e 93ff "..4:....Wi..^..
00000090: 0d3e c912 1d02 39f1 e25f 3a04 0000 040f .>....9.._:.....
000000a0: 3cd2 05ca aaea 21ef c577 bc56 b7f7 6250 <.....!..w.V..bP
000000b0: 61eb 6302 28c8 20b0 0abb 6e0c 83a3 a0e0 a.c.(. ...n.....
000000c0: 1238 b3c2 2fa8 3343 ae98 b80d 9576 9eca .8../.3C.....v..
000000d0: 5e93 ff0d 3ec9 121d 0239 f1e2 5f3a 0400 ^...>....9.._:..
000000e0: 0000 1161 6469 6540 6d69 6c6c 6566 6575 ...adie@millefeu
000000f0: 696c 6c65 0102 0304 ille....
It’s easy to read, the first 15 bytes is a C string (null-terminated byte array) purposed as file identifier (AUTH_MAGIC), then the next 4 bytes is a big-endian 32-bit integer representing the length of cipher name used to encrypt this key, it’s a none since I’m not using any encryption. The next 4 bytes is the length for key derivation function name, it’s also a none here. The default value for cipher name is aes256-cbc and for the kdfname it’s bcrypt if there’s encryption involved. This 4 bytes length and data pattern is repeated for the whole message. For example the next 4 bytes is the length of options for the key derivation function, the structure is nested, another length prefixed byte array. The fields is salt and rounds count. If encryption is used the salt length is 16 bytes by default and the round is 16. Above we have none of these so the kdf option length will be 0 (4-bytes zero). Next 4 bytes is the number of the key, It will be always 1. But I guess in the future there’s a plan for supporting multiple keys in a single file or something.
Next 4 bytes is the length of our public key structure. 0x33, 51 bytes, but wait it looks a bit strange, let’s compare it with the public key file first:
adie@millefeuille:~ $ cat ~/.ssh/test_ed25519.pub | ruby -ne 'print $_.split[1].unpack("m").first' | xxd
00000000: 0000 000b 7373 682d 6564 3235 3531 3900 ....ssh-ed25519.
00000010: 0000 2001 238b 3c22 fa83 343a e98b 80d9 .. .#.<"..4:....
00000020: 5769 eca9 5e93 ff0d 3ec9 121d 0239 f1e2 Wi..^...>....9..
00000030: 5f3a 04
Okay this is weird 1 nibble is actually missing from the private key representation above specifically in this line 00000030: 7368 2d65 4323 5353 1390 0000 0200 1238 sh-eC#SS.......8. This is really weird since things will totally broken if it’s really the case with openssh. But fortunately it’s not.
Now i just can’t believe in ruby, at least not to its builtin base64 decoding system. Not sure what happened here and when I test it with non binary base64 strings, it actually decode as expected. Anyway, let’s use saner implementation for now:
adie@millefeuille:~ $ cat ~/.ssh/test_ed25519| egrep -v ^- | ruby -ne 'print $_.gsub("\n","")' | base64 --decode | xxd
00000000: 6f70 656e 7373 682d 6b65 792d 7631 0000 openssh-key-v1..
00000010: 0000 046e 6f6e 6500 0000 046e 6f6e 6500 ...none....none.
00000020: 0000 0000 0000 0100 0000 3300 0000 0b73 ..........3....s
00000030: 7368 2d65 6432 3535 3139 0000 0020 0123 sh-ed25519... .#
00000040: 8b3c 22fa 8334 3ae9 8b80 d957 69ec a95e .<"..4:....Wi..^
00000050: 93ff 0d3e c912 1d02 39f1 e25f 3a04 0000 ...>....9.._:...
00000060: 0098 cb71 feb4 cb71 feb4 0000 000b 7373 ...q...q......ss
00000070: 682d 6564 3235 3531 3900 0000 2001 238b h-ed25519... .#.
00000080: 3c22 fa83 343a e98b 80d9 5769 eca9 5e93 <"..4:....Wi..^.
00000090: ff0d 3ec9 121d 0239 f1e2 5f3a 0400 0000 ..>....9.._:....
000000a0: 40f3 cd20 5caa aea2 1efc 577b c56b 7f76 @.. \.....W{.k.v
000000b0: 2506 1eb6 3022 8c82 0b00 abb6 e0c8 3a3a %...0"........::
000000c0: 0e01 238b 3c22 fa83 343a e98b 80d9 5769 ..#.<"..4:....Wi
000000d0: eca9 5e93 ff0d 3ec9 121d 0239 f1e2 5f3a ..^...>....9.._:
000000e0: 0400 0000 1161 6469 6540 6d69 6c6c 6566 .....adie@millef
000000f0: 6575 696c 6c65 0102 0304 euille....
That’s better. Now let’s continue with our public key structure, there’s a key type ssh-ed25519 and the public key itself. One of the interesting properties of Ed25519 is its key is simply byte array, it’s not a representation of big prime whatsoever. And I noticed that in a single private key above, the public key is actually stored 3 times. In the private key structure there’s a 2 check ints, a 32-bit integer repeated twice. a public key, and the 64 bytes private key, which actually contained public key as its last 32 bytes.
My implementation to decode and read the key is at GitHub. It’s on public domain, and doesn’t support encrypted private key for now. I also haven’t bothered to add tests. Probably later.