How to Interchange Ed25519 Keys

https://www.tbray.org/ongoing/When/202x/2021/04/19/PKI-Detective

by tmfi • 5 years ago

69 66 5 years ago

agwa4• 5 years ago

This is unnecessarily complicated. The beautiful thing about Ed25519 keys (private and public) is that they are simply opaque byte strings. Indeed, here is Go's definition of ed25519.PublicKey:

  type PublicKey []byte

So if your application uses exclusively Ed25519, you can just pass around the raw bytes (encoded as base64 as desired). There is no need to muck around with ASN.1.

And if you do need to transmit keys in ASN.1 structures, Go's standard library has functions for that:

https://golang.org/pkg/crypto/x509/#MarshalPKIXPublicKey

https://golang.org/pkg/crypto/x509/#ParsePKIXPublicKey

The author has just written worse versions of those functions.

psanford• 5 years ago

Came here to say that the example code in the docs for ParsePKIXPublicKey seems to be exactly what the author was looking for.

userbinator• 5 years ago

All keys are just opaque strings of bytes.

agwa4• 5 years ago

They actually aren't. RSA keys, for instance, are defined as a pair of integers (modulus and exponent)[1] and the algorithms are specified as taking these integers as input. ECDSA is similar. Therefore, to interchange RSA and ECDSA keys, you need some other specification that tells you how to serialize those integers.

It's true that internally Ed25519 keys are also integers, but the encoding/decoding is encapsulated in the Ed25519 algorithm so to users of Ed25519 they are just byte strings. This is quite a bit nicer in practice than the approach taken by RSA and ECDSA.

[1] https://tools.ietf.org/html/rfc8017#section-3

jnwatson• 5 years ago

If you're going there, all information can be opaque strings of bytes.

runeks• 5 years ago

Indeed, here is Go's definition of ed25519.PublicKey […]

Wouldn’t you need some sort of length restriction on that? Or are all byte sequences valid Ed25519 keys — e.g. the empty byte sequence and the byte sequence that comprises this[1] cat GIF?

https://i.pinimg.com/originals/c3/2b/fa/c32bfa16bcf864e478d3...

lawl• 5 years ago

Wouldn’t you need some sort of length restriction on that?

https://github.com/golang/go/blob/master/src/crypto/ed25519/...

It seems it would indeed panic with an invalid size.

madars• 5 years ago

Yup! From https://cr.yp.to/ecdh.html

How do I validate Curve25519 public keys? Don't. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys. (minor exceptions follow)

agwa4• 5 years ago

Public keys are 32 bytes long, and private keys are 64 bytes long. The Ed25519 functions check to make sure the key is the correct length before using them:

https://github.com/golang/go/blob/d4bfe006155ea0d9c2970e22fc...

The types would ideally use fixed-length arrays, but at the time the API was designed, Go didn't allow conversions between slices and array pointers, which would have made the API annoying to use:

https://github.com/golang/go/issues/24376#issuecomment-37278...

Go is now adding support for such conversions, but the Ed25519 API can't be changed due to backwards compatibility guarantees.

timbray10• 5 years ago

Fair enough, thanks, will adopt those. An interesting question is why heavy googling and stackoverflow diving looking for "how to publish ed25519" and related things failed to turn this up.

nabla93• 5 years ago

Call me old fashioned, but I browse and search the documentation first. Starting from the index page. "pkix - Package pkix contains shared, low level structures used for ASN.1 parsing and serialization of X.509 certificates, CRL and OCSP."

agwa4• 5 years ago

A fair question. I've opened an issue in Go suggesting some documentation improvements: https://github.com/golang/go/issues/45726

ComodoHacker• 5 years ago

opaque byte strings

The point was to have something you (an average Joe) can share on the Internet, and that's definitely not byte string.

But the whole PKI thing is indeed very complicated. After such thorough analysis I was expecting some novel and simple solution like memorizable passphrase or QR code to scan.

evanelias2• 5 years ago

As a non-crypto person who coincidentally just spent a couple days mucking with this in Go earlier this week, I absolutely agree with the author's assertion that it's very hard to find complete examples, and even articles that don't assume a decent baseline of domain expertise.

fwiw my own thought/research path, after choosing Ed25519, looked something like this:

1. "How do I generate the key pair? I should probably use openssl since I trust that and have used it in the past." After googling, I see I can use `openssl genpkey -algorithm ed25519` for the private key.

2. "OK, that gave me a pem file. How do I deal with that in Go?" From here I found the same blainsmith.com article as OP, which is overall very helpful but unfortunately contains the unnecessary asn1.Unmarshal steps.

3. "Hmm, this looks overly complex." Luckily I took some extra time to look at other search results for "ed25519 pem golang" and found the crypto/x509 functions linked above.

In retrospect, if I had just used ed25519.GenerateKey(nil) for step 1, I would have saved a ton of time. But this really wasn't initially clear to me at all. Exactly as the OP said, "Because as I stumbled through the undergrowth figuring this stuff out in the usual way, via Google and StackOverflow, I did not convince myself that the path I was following was the right one." And in this case the OP is a highly respected software engineer with his own wikipedia page, so at least I'm in good company for tripping all over this process :)

chasil• 5 years ago

Since Microsoft strapped OpenSSH into Windows 10, we can assume ssh-keygen is the most ubiquitous ed25519 management tool; anything using OpenSSH format will be widely supported.

Does this run just about everywhere?

    ssh-keygen -t ed25519 -f testkey

timbray10• 5 years ago

Just committed changes to use those functions. Didn't remove all the ceremony but saved a few lines of code. Thanks. Credited @agwa in the commit.

FiloSottile4• 5 years ago

Came here to say this. Please don't use PKIX, ASN.1, and Base64-of-DER-without-PEM-headers for Ed25519. Those are all extra complexity from protocols that were misguidedly built with runtime agility, or from a different time in cryptography engineering in which we really felt the need to put dynamic types on everything. [0][1]

An Ed25519 public key is a 32 bytes sequence. An Ed25519 private key (called seed in crypto/ed25519 for unfortunate historical standardization reasons) is a 32 byte sequence. That's it.

Here they are encoded in Base64.

    public key: 5uW7anEGF1nIjGfp5pS2kiN0cn2mGYkuSa+TCBoFIbQ=
    private key: shhKyGTvTeLjXGDCjEQgHRA7ps3LRNNfoO5S714kinU=

age [2] similarly uses Curve25519 keys encoded with Bech32 to make them easier to copy-paste and read aloud. Look how nice they look compared to PKIX blobs!

    $ age-keygen
    # created: 2021-04-23T12:31:14-04:00
    # public key: age1gek0nrawzg9fhkrzcmt4ql7au0n6hwflz7lqqc8wwcvefn2vssgsa4uulp
    AGE-SECRET-KEY-19JFPFAY2DF3HJP5DFGVSY4A4G4YSRHG4ZCJMKNC5MFD9C9ZN5LCSG8VTDL

I'll think about how to make the crypto/ed25519 godoc point people in the right direction once Go 1.17 enters feature freeze.

[0] https://www.imperialviolet.org/2016/05/16/agility.html

[1] https://buttondown.email/cryptography-dispatches/archive/cry...

[2] https://github.com/FiloSottile/age

timbray10• 5 years ago

This makes sense, but if I'm handing these things around probably some of the code [gasp] isn't in Go. So someone should write an RFC for the case where you don't need algorithm agility, and then devs don't need to know or care in the slightest what 25519 keys actually are, they just need to call APIs to serialize & deserialize them.

tialaramex2• 5 years ago

Adam's post about agility is a good read, but it's worth remembering that it makes a prediction which did not in fact come true.

When we try to add a fourth (TLS 1.3) in the next year, we'll have to add back the workaround, no doubt.

Adam is talking about the unsafe downgrade fallback, traditionally done by web browsers, not so long ago even falling back to SSLv3 which was long obsolete.

But in fact today, if your web browser connects to a remote server proposing TLS 1.3 and the remote server just silently drops the connection because it can't conceive of such a thing, the browser goes "Huh, I guess TLS doesn't work on that server" not "Let's try again with TLS 1.2" because the design in TLS 1.3 actually works, even if getting there was a heroic effort. A compliant TLS 1.2 server will do TLS 1.2, and sufficiently non-compliant ones just break and are now presumably very rare.

rauhl2• 5 years ago

The trouble with using just a bag of (potentially Base64-encoded) bytes is that it flirts with cryptographic doom: one relies on users not to make mistakes.

For example, is 5uW7anEGF1nIjGfp5pS2kiN0cn2mGYkuSa+TCBoFIbQ= a Base64-encoded Ed25519 public key? Sure. Is it a Base64-encoded HMAC-SHA-256 key? Sure! It’s 256 bits, after all. Is it a valid AES-256 key? Yes again.

OTOH, (public-key (ed25519 |5uW7anEGF1nIjGfp5pS2kiN0cn2mGYkuSa+TCBoFIbQ=|)) is clearly not an HMAC private key. For that matter, (secret-key (hmac-sha-256 |5uW7anEGF1nIjGfp5pS2kiN0cn2mGYkuSa+TCBoFIbQ=|)) is clearly not an Ed25519 public key. And (secret-key (aes-256 |5uW7anEGF1nIjGfp5pS2kiN0cn2mGYkuSa+TCBoFIbQ=|)) is clearly neither a public Ed25519 key nor a private HMAC-SHA-256 key. Software expecting one and getting one of the other will break.

Why does this matter? Because using a public value such as a public key as an HMAC signing key means that anyone can generate a signature, and using a public value such as a public key as a secret encryption key means that anyone can decrypt the encrypted material.

Why use the unusual formats I suggested above? Because this:

    (public-key
      (ed25519 |5uW7anEGF1nIjGfp5pS2kiN0cn2mGYkuSa+TCBoFIbQ=|))

is clearly preferable to this:

    -----BEGIN PUBLIC KEY-----
    MDYwBQYDK2VwAy0ANXVXN2FuRUdGMW5JakdmcDVwUzJraU4wY24ybUdZa3VTYStUQ0JvRkliUT0
    -----END PUBLIC KEY-----

timbray10• 5 years ago

The conventional PKIX/PEM is logically equivalent to your s-expression there; I assume you're arguing for using the conventional packing rather than proposing a new s-expression based encoding?

1vuio0pswjnm7• 5 years ago

Wouldnt it make more sense to use base32 instead of base64.

Also whats wrong with simply using the hex string of the public key. It is not much longer than the base64/32 string. I thought the short length was an intentional part of djb's design. Small public keys, short hex strings. Easy to share.

formerly_proven2• 5 years ago

Why exactly would you do any of this instead of

a) just having a field of 32 bytes in the wire protocol (if binary)

b) just turning it into a hex string (if text is needed) or base64/85 if you don't want hex for some reason

viraptor2• 5 years ago

Why exactly would you do any of this

Because it's your first adventure in the land of crypto and you have no idea how to do things, which parts you need to learn about and which are not required. It seems trivial for me now, but there was a time I would end up on a similar journey.

I don't know of a source which would do a quick walk through all of these levels. And if there is one, I don't know how you'd find it without knowing the right keywords.

(Now I'm tempted to write up some "crypto and certificates and public keys and other things explained quickly and without depth so you can ask better questions next" post)

Aachen4• 5 years ago

Not the person you replied to, but

Because it's your first adventure in the land of crypto and you have no idea how to do things

is rather presumptuous. I do actually know how to do crypto things (I review and test such things for a living) and after reading their comment and skimming the post I'm left wondering the exact same thing.

artificialLimbs• 5 years ago

That would be the post I have been searching for the last 2 years of my life. I have to budget my time very strictly, and finding out how to learn about security is obscure at best.

formerly_proven2• 5 years ago

Fair enough, if you don't know "the customs" it's probably very easy to end up looking for "public key formats" and fall into the PKIX/X.509/ASN.1 rabbit hole.

est31• 5 years ago

ASN.1 and stuff were developed with crypto agility in mind [0]. Right now ed25519 is enough but maybe in the future we might be using quantum ready algorithms instead. Your 32 bytes in the wire protocol might not be enough for that. And how would it know when given a hex string whether it's an ed25519 key or a post quantum crypto key? If it's ASN.1 encoded, you can just check the OIDs.

Of course it all depends on your domain. Maybe you build an app that won't be used any more in 3 years. But if you feel like your protocol will be implemented by many vendors and you might want to allow vendors to use multiple algorithms so that support for alternatives is already present if a vulnerability is found in algorithm, it's better to have self describing key data instead.

[0] https://en.wikipedia.org/wiki/Cryptographic_agility

CameronNemo• 5 years ago

Well if you were using something like protobuf/gRPC, you could evolve the API.

timbray10• 5 years ago

Well, because it's not just Go. I want other languages to be able to use these. Other languages maybe don't regard ed25519 as a byte array. So I could tell the world "I invented a way to serialize keys, please use it" or I could say "I used the standard ASN.1/foobar to serialize them so you can use standard libraries to deserialize them."

FiloSottile4• 5 years ago

If there's a language that doesn't take 32 byte strings and give you an Ed25519 public key or private key, please do point me to it and I will message the maintainer. We're basically all on the same Slack :)

jetzzz• 5 years ago

You are not inventing new way of serializing them, byte arrays are what ed25519 keys are. In fact, by using ASN.1 you are making it more complicated to use and increase attack surface as one now needs an ASN.1 library in addition to an ed25519 library.

kodablah• 5 years ago

Why use ASN.1? Just base64 and send. Besides a few bytes at the end, a Tor v3 onion service address is just a base32'd ed25519 public key.

latortuga• 5 years ago

There's a typo in the HN title, it should be 25519, not 25119.

timbray10• 5 years ago

Fixed, thanks

dang• 5 years ago

Fixed, thanks :)

kfreds• 5 years ago

First of all, I enjoyed reading this article. Second, it inspired me to write the following, with curious beginners as the target audience.

It was meant to be about the importance of reducing the computing power of recognizers / parsers / interfaces / meaning-makers, as the author brings up PEM, ASN.1, and X.509. It grew a bit. Enjoy.

<rant>

In my opinion security exists to facilitate trust, and security has a lot to do with managing complexity.

One of the most powerful security technologies we have is math. Especially math that is easy to do in one direction and very difficult to do in the opposite direction. RSA, Ed25519, Diffie-Hellman, and SHA256 all rely on this concept.

Another power tool is combining these cryptographic primitives to build protocols that provide e.g. authentication, forward secrecy, confidentiality, and integrity-protection.

When using cryptographic primitives directly it is easy to make mistakes. For example, before Ed25519 there were other similar signature schemes that, in addition to a message to be signed, required a number that must not be repeated for different messages, called a nonce. If this number was repeated, an attacker could collect signatures and combine them to get the private key. Ed25519 removes this sharp corner by essentially using nonce=SHA512(message) internally.

When designing a protocol like TLS, SSH, Signal, or WireGuard, multiple primitives of different types are combined to get the desired security properties.

Cryptographers work hard to combine primitives such that the resulting construction is easy to reason about, and ideally prove that the construction will only break if one of the primitives break.

Unfortunately this key insight is often ignored further up the stack. Many protocols, file formats, etc are unnecessarily complex. This makes them harder to reason about, which makes it harder to build a safe recognizer / parser / interface / meaning-maker for them. Complex parsers lead to incorrect mental models, which lead to security vulnerabilities.

If you are ever tasked with building a protocol, file format, or API, consider making it only as complex as it must be. We will suffer for a long time with the complex beasts that have already been standardized. Let’s not make more of them.

Remember that security, trustworthiness, understanding, and managing complexity are intertwined. Don’t use more complexity than necessary.

</rant>

P.S. If anyone is curious about Ed25519 I can highly recommend the following article: https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/

ajrw• 5 years ago

JWK is a good option for representing public keys, for an Ed25519 key you would have something like this:

{ "kty":"OKP", "crv":"Ed25519", "x":"oF0a6lgwrJplzfs4RmDUl-NpfEa0Gc8s7IXei9JFRZ0" }

nemo1618• 5 years ago

I've always found PEM/ASN.1 to be rather ugly. I encode my ed25519 keys as "ed25519:<hex key>".

upofadown• 5 years ago

...if ed25519 fails, it’ll fail slowly and there’ll be time to migrate to something else.

Why would you assume that? The curve in question has been around for only something like 10 years....

wahern2• 5 years ago

Ed25519 isn't quite as simple as people make it out to be, at least in the sense that it's an answer to a problem that's been entirely elided in these discussions, whilst the problems with older alternatives are more familiar.

Both RSA and NIST-defined elliptic curves support both signatures and key exchange using the same public key. Not so with Curve25519. Ed25519 is just for signatures and X25519 for key exchange, and the "opaque" 32-byte public keys are actually different. You can convert Ed25519 public keys to X25519 public keys, but for a reverse transformation there are two incompatible methods, and so any protocol where you would like to keep a single public key association for parties--particularly offline protocols where a sender can't ask the recipient to generate an ephemeral key pair for confidential message reception--one is faced with a couple of choices. And the choices made by some existing protocols aren't always obvious. Indeed, the very fact that these differences exist isn't necessarily obvious until you're already knee-deep in the weeds.

At this point the solution is more-or-less settled--just publish Ed25519 keys. But it wasn't always that way considering that the Ed25519 signature scheme is much newer than Curve25519. And of course the legacy of this complexity will always be around to some extent.

Also left undiscussed is the different modes of Ed25519--regular and prehashed message digestion, a choice that is absent for older schemes. That's a whole 'nother can of worms.

Time and usage effect almost every new protocol and format--they don't stay pristine forever. The sheen has already dulled on Curve25519. If you want the fewest possible interoperability headaches Curve448 is the new hotness, if only because Curve448 has been standardized more times than actually deployed. It's also more secure--longer keys[1] and slightly better mathematical properties, AFAIU, of the type that originally made Curve25519 and DJB's SafeCurves initiative appealing.

[1] Arguably useful if there's an extended period of time between quantum computing scaling to threaten 128-bit classically equivalent but non-quantum-safe asymmetric schemes, and scaling to threaten ~256-bit equivalent schemes. You're probably better off with RSA in that case, though. Or just not worrying about it and sticking to Curve25519--one of the few times where "but 32 is such a nice, round, convenient string length" is perhaps a legitimate argument.

tialaramex2• 5 years ago

The trouble is that if you use my public signing key to do something else it wasn't intended for (here, X25519) I can't participate without also using my private key in this unconventional way.

Now, this looks safe which is more than can be said for the equivalent trick in RSA, which looks obviously dangerous and in practice has caused real problems, but it sure would be comforting if people did all the heavy lifting to prove it is safe rather than shrugging and doing it anyway (e.g. 'age')

Meanwhile it feels like the lesson we learned aeons ago in cryptography should apply, if we can't prove why it's safe, let's just assume it isn't safe.

wahern2• 5 years ago

AFAIU the only danger is in using your public signing key to initiate key exchange. In that case you always want to make sure you're generating a random ephemeral key pair to send. But in this case you're definitely not accidentally doing anything. Curve25519 schemes were designed to be robust to potential misuse.

But your point still stands--it's yet another question to be concerned with. And if you want to take a belt & suspenders approach then sticking with two different public keys is perfectly defensible, just as one might prefer Encrypt-then-HMAC rather than an AEAD scheme. (FWIW, I do.) And regardless of this hidden complexity, Curve25519 schemes don't harbor nearly the same potential risks as RSA schemes.

But I just saw a ton of discussion about the complexity of PEM and ASN.1 and how they seem to, to rephrase, sully or taint the elegance of Ed25519, and my first thought was the emphasis was mislaid. Not quite cargo culting--I can take either side of the text vs binary protocol debate, or appreciate why people may prefer some binary TLV encoding schemes more than others--but I thought it worthwhile to point out that there's hidden, much more consequential complexity just beneath the surface. If you're designing or implementing a protocol, using PKIX (ASN.1 DER) encoding for public keys isn't even blip on your complexity radar--or won't be after all is said and done if its your first time. Until recently most binary protocols I've ever seen adopted PKIX key encoding (either SubjectPublicKeyInfo or at least the inner RSA fields) even when they completely avoided PKIX certificates or other ASN.1 serialization schemes. And the extra step of PEM encoding is arguably a bonus--PEM encoded keys are a well known quantity, and have advantages like being easily text searchable to help catch key leaks. Relative to the broader complexity these things are normally not something worth pondering, at least not if you had already settled on a binary protocol.

How to Interchange Ed25519 Keys

Related Stories