Re-Deriving the edwards25519 Decoding Formulas
A lot of my job is implementing specifications, and sometimes in a crypto spec you’ll encounter something like this and what you do is nod, copy it into a comment, break it down into a sequence of operations, and check that the result matches a test case. However, the other day I was having a bit of an identity crisis because I could not remember basic algebra, so I went and re-derived the edwards25519 point decoding formulas as a sort of homework. It turned out to be pretty useful for understanding pieces of the implementation I had been just treating as black boxes. I’m going to try to take you along for the ride, to show that there is no dark magic involved, and that we can all get to the same result as the specification with step-by-step high-school algebra.
Reconstruct Instead of Validating
What I want to focus on is (2), because it’s a lesson we learned the hard way in cryptography and didn’t transfer effectively to the rest of security engineering.
One of my favorite cryptographic attacks is the Bleichenbacher‘06 signature forgery. I wrote up how it works when I found it in python-rsa, so again go read that, but here’s a tl;dr. When you verify an RSA PKCS#1 v1.5 signature, you get a ASN.1 DER structure wrapping the message hash that you need to check. If you don’t parse it strictly, for example by allowing extra fields or trailing bytes, an attacker can fake the signature. This was exploited countless times.
The lesson we learned was that instead of parsing the ASN.1 DER to extract the message hash, we should reconstruct the ASN.1 DER we’d expect to see, and then simply compare it byte-by-byte.
The same technique would have saved Vault.
Is X25519 Associative? Sometimes!
Making Illegal States Unrepresentable
It’s a concept I find very helpful. But if you look for examples online almost everything either “let’s prevent dividing-by-zero” or “let’s enumerate the cases in a data type”. We can more creative than that! Some examples of “illegal states unrepresentable” that I found useful but have not seen anyone else talk about online:
New Crypto in Go 1.14
Go 1.14 is out and with it come a few nice updates to crypto/tls!
Donald Knuth Was Framed
Knuth writes 8 pages and McIlroy writes six lines.
A damning counter. But neither of us had ever read the paper. And as you know, I’m all about primary sources. We pulled up the paper here and read through it together. And it left us with a very different understanding of literate programming, and the challenge, than the famous story gave.
The Linux CSPRNG Is Now Good!
Oceans of ink and hours on stage have been spent to convince the world that the best random number generator is /dev/urandom, the kernel one. And it is, and it’s always been. However, an uncomfortable truth was that the Linux CSPRNG really could have been better than it was. Userspace CSPRNGs couldn’t be better than the kernel one, so our advice was still valid, but that space for improvement always frustrated me.
Good news everyone! In recent years, the Linux CSPRNG got a number of great incremental improvements, and I can now say in good conscience that it’s not only the best, it’s also good.
Hello World, and OpenPGP Is Broken
This is the inaugural issue of Cryptography Dispatches, meant to be quick, frequent and lightly edited discussions of cryptographic topics. Longer form can be found at blog.filippo.io.
For my first round, I am writing about the recent attack on the PGP keyservers. The overall goal of the newsletter is to explain cryptography rather than to comment on the news, so we will cover context and mechanics, not the last minute updates. Issues about Ristretto, Ed25519 in Go, AES-GCM-SIV, and OPRF based contact discovery are still coming as promised!