It’s a Cold Day in Developer Hell, So I Must Roll My Own Crypto

Original post written by Soatok

I have several projects in-flight, and I wanted to write a quick status update for them so that folks can find it easier to follow along.

Please bear in mind: This is in addition to, and totally separate from, my full-time employment.

Hell Frozen Over

A while ago, annoyed by the single point of failure in digital signature algorithms, I decided to build a tool to help developer teams use threshold cryptography.

The idea was: Wrap an existing implementation of FROST (RFC 9591) with a command line tool (and provide a corresponding HTTP Server to fulfill the coordinator role). Then you can give it to DevSecOps folks and say, “Now you need 3 out of 5 keys to be turned in order for a valid Ed25519 signature to be emitted.”

Unfortunately, while writing integration tests for the tool, I ran into concurrency issues: The keygen ceremony worked fine, but signing would either never start or would get into an invalid state for arcane reasons.

After wrestling with this for 40 or so hours (with very little sleep), and being ignored by the maintainers of the FROST library I was building upon, I decided that this was a stupid problem to have.

So I decided to roll my own FROST implementation.

Of course, there are some complications.

FROST Paper vs RFC 9591

The original FROST paper was published in 2020 by Chelsea Komlo and Ian Goldberg. Section 2.3 of the FROST paper discussed Distributed Key Generation (“DKG” for short).

The FROST library I was originally using had implemented a version of the DKG mentioned by the FROST paper.

Unfortunately, RFC 9591 does not specify a DKG algorithm. Instead, it says this:

This document does not specify how this information, including the signing key shares, are configured and distributed to participants. In general, two configuration mechanisms are possible: one that requires a single trusted dealer and one that requires performing a distributed key generation protocol. We highlight the key generation mechanism by a trusted dealer in Appendix C for reference.

RFC 9591: The Flexible Round-Optimized Schnorr Threshold (FROST) Protocol for Two‑Round Schnorr Signatures

Wonderful.
Art by CMYKat

Since the thing I’m building is intended for creating threshold signatures in a geographically distributed manner without ever reconstructing the secret key, a trusted dealer is out of the question since that would require us to, at some point, have a reconstructed secret key in the first place.

Enter, ChillDKG

After a bit of research (and talking with one of the FROST RFC authors), the direction the industry is moving towards is some kind of standardization of ChillDKG, a distributed key generation algorithm for FROST.

ChillDKG has some nice benefits: It establishes a minimal trusted channel between participants without the need for a trusted coordinator or separate encrypted layer.

(The need for a separate encryption layer for transport wasn’t a game over issue for my tool, because it was always intended to run over a VPN, but not having to require additional setup for security is nice.)

Unfortunately, ChillDKG exists as a Bitcoin Improvement Proposal. Consequently, the reference code only supports secp256k1.

Now, I have no love for cryptocurrency. Given that Ed25519 is in a lot of things, including FIPS 186-5, I can meet a lot of developers where they already are if I support Ed25519.

Consequently, I’m going to be implementing an Ed25519-only variant of ChillDKG in my FROST implementation. Along the way, I plan on writing a C2SP specification so that others may implement a compatible feature. This specification will vend Ed25519 public keys and operate on the Ristretto255 prime-order group, and my implementation will do the same.

On Ed25519 and Ristretto255

Many cryptography protocols assume a prime-order group in their construction.

Ed25519 is a digital signature algorithm based on Schnorr, defined over the edwards25519 elliptic curve.

Edwards25519 is not prime-order; it has a cofactor of 8. This nuance introduced a double-spend vulnerability in CryptoNote-based currencies (most notably, Monero).

In response to this and related issues, cryptographers worked on Ristretto, a prime-order group for Curve25519 and Curve448.

If you’re doing basic signatures, Ed25519 is fine.

But the moment you deviate from the crypto_sign() API for which Ed25519 was defined, you’re much better off using Ristretto255 and not having to worry about small torsion components.

My plan, therefore, is to define a ChillDKG variant over the Ristretto255 group and then convert the result to an Ed25519 public key.

You might be wondering, “What does that entail?”

Piercing the Ristretto255 Group Abstraction

Ristretto255 group elements do not necessarily map to a specific Edwards25519 point with a cleared cofactor. What you need to do is:

1. Multiply the Ristretto element by the cofactor (8).
2. Multiply by the modular inverse of the cofactor.

This will return a birationally equivalent point with a cleared cofactor.

In Go, an implementation of this algorithm might look like this:

import (
	"filippo.io/edwards25519"
	"github.com/gtank/ristretto255"
)

var eightInv, _ = edwards25519.NewScalar().SetCanonicalBytes([]byte{
	121, 47, 220, 226, 41, 229, 6, 97,
	208, 218, 28, 125, 179, 157, 211, 7,
	0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 6,
})

// Returns a birationally equivalent point on the edwards25519 curve.
//
// Since the element may not be of order 8, we cannot just return the bytes
// for the underlying point.
//
// However, [8^{-1}][8]P is guaranteed to have a cleared cofactor.
func ToEdwards25519Point(e *ristretto255.Element) *edwards25519.Point {
	p := edwards25519.NewIdentityPoint()
	// this is the byte representation of 8^{-1} mod q
	p.SetBytes(e.Bytes())
	p.MultByCofactor(p)
	p.ScalarMult(eightInv, p)
	return p
}

(I had previously offered this as a built-in feature in the Go Ristretto255 implementation, but Filippo isn’t a fan of piercing the abstraction, so I closed the pull request.)

What If An Honest Dealer is Fine?

Some folks might not be interested in ChillDKG, because an honest dealer is totally fine for their threat model. They just want to distribute the signing across multiple independently held shares after the key is established.

Or what if (bear with me, this is a bit bonkers) someone wants to participate in a Distributed Key Generation ceremony, but wants to further shard their own share of the larger threshold into multiple local shares?

CMYKat

To address the myriad use cases that might be possible, my FROST implementation will ultimately contain both a trusted dealer keygen module and a DKG module. Users can choose which they want to rely on, but FREON will only be using the DKG.

FREON / FROST Summary

My original timeline for making FREON generally available has been delayed by the need to re-implement FROST in Go.

My new FROST implementation is further delayed by the need to make distributed key generation a practical thing.

Implementing a FROST DKG that isn’t tethered to Bitcoin shouldn’t be too scary (thank you Ristretto), but will require a lot of time and peer review before it’s production ready.

CMYKat

Fediverse Key Transparency

A while ago, I started writing a proposed specification for key transparency for the Fediverse. I’ve blogged about this project as it evolved.

As I mentioned in my latest blog post, you kind of need something like key transparency to solve the authentication and trust issues that RFC 9420 punted on (and the founder of SimpleX (alt archive) wants to spread FUD about). That is to say: It’s not enough to just use MLS. You need a little more in order to have a complete solution for privacy in the face of malicious servers.

(The W3C’s ActivityPub-E2EE project is aware of my Key Transparency proposal, for what it’s worth.)

As things stand today, the specification is in a good place to begin actually writing code, so I plan to write a reference implementation for a Public Key Directory server in Go (for easy access to SigSum implementations) and then write client-side SDKs in various languages.

Every time I’ve tried to start on writing the reference implementation for the server software, my life got busy. I’ve been positively slammed by work since the beginning of January, and I haven’t been in the right mood to work on this sort of undertaking.

However, my workload is starting to become more sustainable, so I plan to begin development before the end of the year. I want to have something tangible that folks can hold in their hands and study carefully.

In the meantime, I implore security and cryptography experts to read the specification and share their feedback with me.

E2EE for Mastodon?

The whole reason I spent multiple years trying to tackle a federated approach to key transparency was because I wanted to define my own end-to-end encryption, so that folks can have a private alternative to Direct Messages.

I still want to do that, but it’s highly possible that the ActivityPub E2EE project will make sufficient correct decisions that I’ll roll my effort into what they’re doing.

For now, that project is on hiatus until I’m finished with shipping key transparency for the Fediverse.

Copper & Ember

Now for something totally different.

A few months ago, I started working on an RPG Maker MZ game called Copper & Ember.

This is mostly a for-fun project to occupy myself with while I’m decompressing from more serious endeavors.

The story begins in Westveil city, in the Calwyn Republic, although nations and governments have long since been subsumed under late-stage capitalism.

After the wealthy elite rejected their mortality, their conquest of humanity stalled. Their plot to use AI and nanomachines to turn the lower classes into an eternal unpaid workforce–one not even death can liberate them from–was foiled by their own ascension, as the suppressed history of magic is incompatible with their new biology.

Unperturbed by this setback, they engage in human trafficking to conscript aberrant individuals (those that the governments already surveil) that have the appropriate elemental affinities to practice necromancy in order to reverse-engineer the lost magical arts so it might be repurposed for the ruling class’s use.

You control Ash, a brilliant student who sacrificed her own academic career to provide for her younger brother after their parents’ death, as she navigates her life in one of Westveil’s street gangs, The Strays.

I was planning to blog about it more, but I’ll save that for once I have a demo ready to publicly release.

One of the plugins I’m using is a bit onerous to work with, due to limitations of RPG Maker MZ itself rather than the plugin developer’s fault, so I’m also developing an independent tool for adding/editing quest journal entries.

Wrapping Up

Expect rapid development on some or all of these projects in the coming months.

To be clear: I’ve taken the past few weeks since DEFCON off work and ended up not doing much. The decompression and relaxation have been invigorating, and I’m excited to knock some of these projects out.

Until then, happy hacking, nerds.

P.S. A few folks have asked me about starting a Patreon for my open source stuff. You may not remember this, but I actually deleted my account after Patreon fired their security team in 2022.

I do have a Ko-Fi, though.

Header art: CMYKat and AJ.