In 2022, I wrote about my plan to build end-to-end encryption for the Fediverse. The goals were simple:

1. Provide secure encryption of message content and media attachments between Fediverse users, as a new type of Direct Message which is encrypted between participants.
2. Do not pretend to be a Signal competitor.

The primary concern at the time was “honest but curious” Fediverse instance admins who might snoop on another user’s private conversations.

After I finally was happy with the client-side secret key management piece, I had moved on to figure out how to exchange public keys. And that’s where things got complicated, and work stalled for 2 years.

Art: AJ

I wrote a series of blog posts on this complication, what I’m doing about it, and some other cool stuff in the draft specification.

• Towards Federated Key Transparency introduced the Public Key Directory project
• Federated Key Transparency Project Update talked about some of the trade-offs I made in this design
  
  • Not supporting ECDSA at all, since FIPS 186-5 supports Ed25519
  • Adding an account recovery feature, which power users can opt out of, that allows instance admins to help a user recover from losing all their keys
  • Building a Key Transparency system that can tolerate GDPR Right To Be Forgotten takedown requests without invalidating history

  
  

• Introducing Alacrity to Federated Cryptography discussed how I plan to ensure that independent third-party clients stay up-to-date or lose the ability to decrypt messages

Recently, NIST published the new Federal Information Protection Standards documents for three post-quantum cryptography algorithms:

• FIPS-203 (ML-KEM, formerly known as CRYSTALS-Kyber),
• FIPS-204 (ML-DSA, formerly known as CRYSTALS-Dilithium)
• FIPS-205 (SLH-DSA, formerly known as SPHINCS+)

The race is now on to implement and begin migrating the Internet to use post-quantum KEMs. (Post-quantum signatures are less urgent.) If you’re curious why, this CloudFlare blog post explains the situation quite well.

Since I’m proposing a new protocol and implementation at the dawn of the era of post-quantum cryptography, I’ve decided to migrate the asymmetric primitives used in my proposals towards post-quantum algorithms where it makes sense to do so.

Art: AJ

The rest of this blog post is going to talk about technical specifics and the decisions I intend to make in both projects, as well as some other topics I’ve been thinking about related to this work.

Which Algorithms, Where?

I’ll discuss these choices in detail, but for the impatient:

• Public Key Directory
  
  • Still just Ed25519 for now

  
  

• End-to-End Encryption
  
  • KEMs: X-Wing (Hybrid X25519 and ML-KEM-768)
  • Signatures: Still just Ed25519 for now

  
  

Virtually all other uses of cryptography is symmetric-key or keyless (i.e., hash functions), so this isn’t a significant change to the design I have in mind.

Post-Quantum Algorithm Selection Criteria

While I am personally skeptical if we will see a practical cryptography-relevant quantum computer in the next 30 years, due to various engineering challenges and a glacial pace of progress on solving them, post-quantum cryptography is still a damn good idea even if a quantum computer doesn’t emerge.

Post-Quantum Cryptography comes in two flavors:

1. Key Encapsulation Mechanisms (KEMs), which I wrote about previously.
2. Digital Signature Algorithms (DSAs).

Originally, my proposals were going to use Elliptic Curve Diffie-Hellman (ECDH) in order to establish a symmetric key over an untrusted channel. Unfortunately, ECDH falls apart in the wake of a crypto-relevant quantum computer. ECDH is the component that will be replaced by post-quantum KEMs.

Additionally, my proposals make heavy use of Edwards Curve Digital Signatures (EdDSA) over the edwards25519 elliptic curve group (thus, Ed25519). This could be replaced with a post-quantum DSA (e.g., ML-DSA) and function just the same, albeit with bandwidth and/or performance trade-offs.

But isn’t post-quantum cryptography somewhat new?

Lattice-based cryptography has been around almost as long as elliptic curve cryptography. One of the first designs, NTRU, was developed in 1996.

Meanwhile, ECDSA was published in 1992 by Dr. Scott Vanstone (although it was not made a standard until 1999). Lattice cryptography is pretty well-understood by experts.

However, before the post-quantum cryptography project, there hasn’t been a lot of incentive for attackers to study lattices (unless they wanted to muck with homomorphic encryption).

So, naturally, there is some risk of a cryptanalysis renaissance after the first post-quantum cryptography algorithms are widely deployed to the Internet.

However, this risk is mostly a concern for KEMs, due to the output of a KEM being the key used to encrypt sensitive data. Thus, when selecting KEMs for post-quantum security, I will choose a Hybrid construction.

Hybrid what?

We’re not talking folfs, sonny!

Hybrid isn’t just a thing that furries do with their fursonas. It’s also a term that comes up a lot in cryptography.

Unfortunately, it comes up a little too much.
I made this dumb meme with imgflip
When I say we use Hybrid constructions, what I really mean is we use a post-quantum KEM and a classical KEM (such as HPKE‘s DHKEM), then combine them securely using a KDF.

Post-quantum KEMs

For the post-quantum KEM, we only really have one choice: ML-KEM. But this choice is actually three choices: ML-KEM-512, ML-KEM-768, or ML-KEM-1024.

The security margin on ML-KEM-512 is a little tight, so most cryptographers I’ve talked with recommend ML-KEM-768 instead.

Meanwhile, the NSA wants the US government to use ML-KEM-1024 for everything.

How will you hybridize your post-quantum KEM?

Originally, I was looking to use DHKEM with X25519, as part of the HPKE specification. After switching to post-quantum cryptography, I would need to combine it with ML-KEM-768 in such a way that the whole shebang is secure if either component is secure.

But then, why reinvent the wheel here? X-Wing already does that, and has some nice binding properties that a naive combination might not.

So let’s use X-Wing for our KEM.

Notably, OpenMLS is already doing this in their next release.

Art: CMYKat

Post-quantum signatures

So our KEM choice seems pretty straightforward. What about post-quantum signatures?

Do we even need post-quantum signatures?

Well, the situation here is not nearly as straightforward as KEMs.

For starters, NIST chose to standardize two post-quantum digital signature algorithms (with a third coming later this year). They are as follows:

• ML-DSA (formerly CRYSTALS-Dilithium), that comes in three flavors:
  
  • ML-DSA-44
  • ML-DSA-65
  • ML-DSA-87

  
  

• SLH-DSA (formerly SPHINCS+), that comes in 24 flavors
• FN-DSA (formerly FALCON), that comes in two flavors but may be excruciating to implement in constant-time (this one isn’t standardized yet)

Since we’re working at the application layer, we’re less worried about a few kilobytes of bandwidth than the networking or X.509 folks are. Relatively speaking, we care about security first, performance second, and message size last.

After all, people ship Electron, React Native, and NextJS apps that load megabytes of JavaScript code to print, “hello world,” and no one bats an eye. A few kilobytes in this context is easily digestible for us.

(As I said, this isn’t true for all layers of the stack. WebPKI in particular feels a lot of pain with large public keys and/or signatures.)

Eliminating post-quantum signature candidates

Performance considerations would eliminate SLH-DSA, which is the most conservative choice. Even with the fastest parameter set (SLH-DSA-128f), this family of algorithms is about 550x slower than Ed25519. (If we prioritize bandwidth, it becomes 8000x slower.)

Adopted from CloudFlare’s blog post on post-quantum cryptography.

Between the other two, FN-DSA is a tempting option. Although it’s difficult to implement in constant-time, it offers smaller public key and signature sizes.

However, FN-DSA is not standardized yet, and it’s only known to be safe on specific hardware architectures. (It might be safe on others, but that’s not proven yet.)

In order to allow Fediverse users be secure on a wider range of hardware, this uncertainty would limit our choice of post-quantum signature algorithms to some flavor of ML-DSA–whether stand-alone or in a hybrid construction.

Unlike KEMs, hybrid signature constructions may be problematic in subtle ways that I don’t want to deal with. So if we were to do anything, we would probably choose a pure post-quantum signature algorithm.

Against the Early Adoption of Post-Quantum Signatures

There isn’t an immediate benefit to adopting a post-quantum signature algorithm, as David Adrian explains.

The migration to post-quantum cryptography will be a long and difficult road, which is all the more reason to make sure we learn from past efforts, and take advantage of the fact the risk is not imminent. Specifically, we should avoid:

• Standardizing without real-world experimentation
• Standardizing solutions that match how things work currently, but have significant negative externalities (increased bandwidth usage and latency), instead of designing new things to mitigate the externalities
• Deploying algorithms pre-standardization in ways that can’t be easily rolled back
• Adding algorithms that are pre-standardization or have severe shortcomings to compliance frameworks

We are not in the middle of a post-quantum emergency, and nothing points to a surprise “Q-Day” within the next decade. We have time to do this right, and we have time for an iterative feedback loop between implementors, cryptographers, standards bodies, and policymakers.

The situation may change. It may become clear that quantum computers are coming in the next few years. If that happens, the risk calculus changes and we can try to shove post-quantum cryptography into our existing protocols as quickly as possible. Thankfully, that’s not where we are.

David Adrian, Lack of post-quantum security is not plaintext.

Furthermore, there isn’t currently any commitment from the Sigsum developers to adopt a post-quantum signature scheme in the immediate future. They hard-code Ed25519 for the current iteration of the specification.

The verdict on digital signature algorithms?

Given all of the above, I’m going to opt to simply not adopt post-quantum signatures until a later date.

Version 1 of our design will continue to use Ed25519 despite it not being secure after quantum computers emerge (“Q-Day”).

When the security industry begins to see warning signs of Q-Day being realistically within a decade, we will prioritize migrating to use post-quantum signature algorithms in a new version of our design.

Should something drastic happen that would force us to decide on a post-quantum algorithm today, we would choose ML-DSA-44. However, that’s unlikely for at least several years.

Remember, Store Now, Decrypt Later doesn’t really break signatures the way it would break public-key encryption.

Art: Harubaki

Miscellaneous Technical Matters

Okay, that’s enough about post-quantum for now. I worry that if I keep talking about key encapsulation, some of my regular readers will start a shitty garage band called My KEMical Romance before the end of the year.

CMYKat

Let’s talk about some other technical topics related to end-to-end encryption for the Fediverse!

Federated MLS

MLS was implicitly designed with the idea of having one central service for passing messages around. This makes sense if you’re building a product like Signal, WhatsApp, or Facebook Messenger.

It’s not so great for federated environments where your Delivery Service may be, in fact, more than one service (i.e., the Fediverse). An expired Internet Draft for Federated MLS talks about these challenges.

If we wanted to build atop MLS for group key agreement (like has been suggested before), we’d need to tackle this in a way that doesn’t cede control of MLS epochs to any server that gets compromised.

CMYKat

How to Make MLS Tolerate Federation

First, the Authentication Service component can be replaced by client-side protocols, where public keys are sourced from the Public Key Directory (PKD) services.

That is to say, from the PKD, you can fetch a valid list of Ed25519 public keys for each participant in the group.

When a group is created, the creator’s Ed25519 public key is known. Everyone they invite, their software necessarily has to know their Ed25519 public key in order to invite them.

In order for a group action to be performed, it must be signed by one of the public keys enrolled into the group list. Additionally, some actions may be limited by permissions attached at the time of the invite (or elevated by a more privileged user; which necessitates another group action).

By requiring a valid signature from an existing group member, we remove the capability of the Fediverse instance that’s hosting the discussion group to meddle with it in any way (unless, for some reason, the server is somehow also a participant that was invited).

But therein lies the other change we need to make: In many cases, groups will span multiple Fediverse servers, so groups shouldn’t be dependent on a single instance.

Spreading The Load Across Instances

Put simply, we need a consensus algorithm to determine which instance hosts messages. We could look to Raft as a starting point, but whatever we land on should be fair, fault-tolerant, and deterministic to all participants who can agree on the same symmetric keying material at some point in time.

To that end, I propose using an additional HKDF output from the Group Key Agreement protocol to select a “leader” for all instances involved in the group, weighted by the number of participants on each instance.

Then, every N messages (where N >= 1), a new leader is elected by the same deterministic protocol. This will be performed entirely client-side, and clients will choose N. I will refer to this as a sub-epoch, since it doesn’t coincide with a new MLS epoch.

Since the agreed-upon group key always ratchets forward when a group action occurs (i.e., whenever there’s a new epoch), getting another KDF output to elect the next leader is straightforward.

This isn’t a fully fleshed out idea. Building consensus protocols that can handle real-world operational issues is heavily specialized work and there’s a high risk of falling to the illusion of safety until it’s too late. I will probably need help with this component.

That said, we aren’t building an anonymity network, so the cost of getting a detail wrong isn’t measurable in blood.

We aren’t really concerned with Sybil attacks. Winning the election just means you’re responsible for being a dumb pipe for ciphertext. Client software should trust the instance software as little as possible.

We also probably don’t need to worry about availability too much. Since we’re building atop ActivityPub, when a server goes down, the other instances can hold encrypted messages in the outbox for the host instance to pick up when it’s back online.

If that’s not satisfactory, we could also select both a primary and secondary leader for each epoch (and sub-epoch), to have built-in fail-over when more than one instance is involved in a group conversation.

If messages aren’t being delivered for an unacceptable period of time, client software can forcefully initiate a new leader election by expiring the current MLS epoch (i.e. by rotating their own public key and sending the relevant bundle to all other participants).

Art: Kyume

Those are just some thoughts. I plan to talk it over with people who have more expertise in the relevant systems.

And, as with the rest of this project, I will write a formal specification for this feature before I write a single line of production code.

Abuse Reporting

I could’ve swore I talked about this already, but I can’t find it in any of my previous ramblings, so here’s a good place as any.

The intent for end-to-end encryption is privacy, not secrecy.

What does this mean exactly? From the opening of Eric Hughes’ A Cypherpunk’s Manifesto:

Privacy is necessary for an open society in the electronic age. Privacy is not secrecy.

A private matter is something one doesn’t want the whole world to know, but a secret matter is something one doesn’t want anybody to know.

Privacy is the power to selectively reveal oneself to the world.

Eric Hughes (with whitespace and emphasis added)

Unrelated: This is one reason why I use “secret key” when discussing asymmetric cryptography, rather than “private key”. It also lends towards sk and pk as abbreviations, whereas “private” and “public” both start with the letter P, which is annoying.

With this distinction in mind, abuse reporting is not inherently incompatible with end-to-end encryption or any other privacy technology.

In fact, it’s impossible to create useful social technology without the ability for people to mitigate abuse.

So, content warning: This is going to necessarily discuss some gross topics, albeit not in any significant detail. If you’d rather not read about them at all, feel free to skip this section.

Art: CMYKat

When thinking about the sorts of problems that call for an abuse reporting mechanism, you really need to consider the most extreme cases, such as someone joining group chats to spam unsuspecting users with unsolicited child sexual abuse material (CSAM), flashing imagery designed to trigger seizures, or graphic depictions of violence.

That’s gross and unfortunate, but the reality of the Internet.

However, end-to-end encryption also needs to prioritize privacy over appeasing lazy cops who would rather everyone’s devices include a mandatory little cop that watches all your conversations and snitches on you if you do anything that might be illegal, or against the interest of your government and/or corporate masters. You know the type of cop. They find privacy and encryption to be rather inconvenient. After all, why bother doing their jobs (i.e., actual detective work) when you can just criminalize end-to-end encryption and use dragnet surveillance instead?

Whatever we do, we will need to strike a balance that protects users’ privacy, without any backdoors or privileged access for lazy cops, with community safety.

Thus, the following mechanisms must be in place:

1. Groups must have the concept of an “admin” role, who can delete messages on behalf of all users and remove users from the group. (Signal currently doesn’t have this.)
2. Users must be able to delete messages on their own device and block users that send abusive content. (The Fediverse already has this sort of mechanism, so we don’t need to be inventive here.)
3. Users should have the ability to report individual messages to the instance moderators.

I’m going to focus on item 3, because that’s where the technically and legally thorny issues arise.

Keep in mind, this is just a core-dump of thoughts about this topic, and I’m not committing to anything right now.

Technical Issues With Abuse Reporting

First, the end-to-end encryption must be immune to Invisible Salamanders attacks. If it’s not, go back to the drawing board.

Every instance will need to have a moderator account, who can receive abuse reports from users. This can be a shared account for moderators or a list of moderators maintained by the server.

When an abuse report is sent to the moderation team, what needs to happen is that the encryption keys for those specific messages are re-wrapped and sent to the moderators.

So long as you’re using a forward-secure ratcheting protocol, this doesn’t imply access to the encryption keys for other messages, so the information disclosed is limited to the messages that a participant in the group consents to disclosing. This preserves privacy for the rest of the group chat.

When receiving a message, moderators should not only be able to see the reported message’s contents (in the order that they were sent), but also how many messages were omitted in the transcript, to prevent a type of attack I colloquially refer to as “trolling through omission”. This old meme illustrates the concept nicely:
Trolling through omission.
And this all seems pretty straightforward, right? Let users protect themselves and report abuse in such a way that doesn’t invalidate the privacy of unrelated messages or give unfettered access to the group chats. “Did Captain Obvious write this section?”

But things aren’t so clean when you consider the legal ramifications.

Harubaki

Potential Legal Issues With Abuse Reporting

Suppose Alice, Bob, and Troy start an encrypted group conversation. Alice is the group admin and delete messages or boot people from the chat.

One day, Troy decides to send illegal imagery (e.g., CSAM) to the group chat.

Bob immediately, disgusted, reports it to his instance moderator (Dave) as well as Troy’s instance moderator (Evelyn). Alice then deletes the messages for her and Bob and kicks Troy from the chat.

Here’s where the legal questions come in.

If Dave and Evelyn are able to confirm that Troy did send CSAM to Alice and Bob, did Bob’s act of reporting the material to them count as an act of distribution (i.e., to Dave and/or Evelyn, who would not be able to decrypt the media otherwise)?

If they aren’t able to confirm the reports, does Alice’s erasure count as destruction of evidence (i.e., because they cannot be forwarded to law enforcement)?

Are Bob and Alice legally culpable for possession? What about Dave and Evelyn, whose servers are hosting the (albeit encrypted) material?

It’s not abundantly clear how the law will intersect with technology here, nor what specific technical mechanisms would need to be in place to protect Alice, Bob, Dave, and Evelyn from a particularly malicious user like Troy.

Obviously, I am not a lawyer. I have an understanding with my lawyer friends that I will not try to interpret law or write my own contracts if they don’t roll their own crypto.

That said, I do have some vague ideas for mitigating the risk.

Ideas For Risk Mitigation

To contend with this issue, one thing we could do is separate the abuse reporting feature from the “fetch and decrypt the attached media” feature, so that while instance moderators will be capable of fetching the reported abuse material, it doesn’t happen automatically.

When the “reason” attached to an abuse report signals CSAM in any capacity, the client software used by moderators could also wholesale block the download of said media.

Whether that would be sufficient mitigate the legal matters raised previously, I can’t say.

And there’s still a lot of other legal uncertainty to figure out here.

• Do instance moderators actually have a duty to forward CSAM reports to law enforcement?
  
  • If so, how should abuse forwarding to be implemented?
  • How do we train law enforcement personnel to receive and investigate these reports WITHOUT frivolously arresting the wrong people or seizing innocent Fediverse servers?
  • How do we ensure instance admins are broadly trained to handle this?
  • How do we deal with international law?

  
  

• How do we prevent scope creep?
  
  • While there is public interest in minimizing the spread of CSAM, which is basically legally radioactive, I’m not interested in ever building a “snitch on women seeking reproductive health care in a state where abortion is illegal” capability.

  
  

• Does Section 230 matter for any of these questions?

We may not know the answers to these questions until the courts make specific decisions that establish relevant case law, or our governments pass legislation that clarifies everyone’s rights and responsibilities for such cases.

Until then, the best answer may simply to do nothing.

That is to say, let admins delete messages for the whole group, let users delete messages they don’t want on their own hardware, and let admins receive abuse reports from their users… but don’t do anything further.

Okay, we should definitely require an explicit separate action to download and decrypt the media attached to a reported message, rather than have it be automatic, but that’s it.

Harubaki

What’s Next?

For the immediate future, I plan on continuing to develop the Federated Public Key Directory component until I’m happy with its design. Then, I will begin developing the reference implementations for both client and server software.

Once that’s in a good state, I will move onto finishing the E2EE specification. Then, I will begin building the client software and relevant server patches for Mastodon, and spinning up a testing instance for folks to play with.

Timeline-wise, I would expect most of this to happen in 2025.

I wish I could promise something sooner, but I’m not fond of moving fast and breaking things, and I do have a full time job unrelated to this project.

Hopefully, by the next time I pen an update for this project, we’ll be closer to launching. (And maybe I’ll have answers to some of the legal concerns surrounding abuse reporting, if we’re lucky.)

CMYKat

https://soatok.blog/2024/09/13/e2ee-for-the-fediverse-update-were-going-post-quantum/

#E2EE #endToEndEncryption #fediverse #FIPS #Mastodon #postQuantumCryptography

Dhole Moments

2022-11-22 10:57:46

Update (2024-06-06): There is an update on this project.

---

As Twitter’s new management continues to nosedive the platform directly into the ground, many people are migrating to what seem like drop-in alternatives; i.e. Cohost and Mastodon. Some are even considering new platforms that none of us have heard of before (one is called “Hive”).

Needless to say, these are somewhat chaotic times.

One topic that has come up several times in the past few days, to the astonishment of many new Mastodon users, is that Direct Messages between users aren’t end-to-end encrypted.

And while that fact makes Mastodon DMs no less safe than Twitter DMs have been this whole time, there is clearly a lot of value and demand in deploying end-to-end encryption for ActivityPub (the protocol that Mastodon and other Fediverse software uses to communicate).

However, given that Melon Husk apparently wants to hurriedly ship end-to-end encryption (E2EE) in Twitter, in some vain attempt to compete with Signal, I took it upon myself to kickstart the E2EE effort for the Fediverse.

https://twitter.com/elonmusk/status/1519469891455234048

So I’d like to share my thoughts about E2EE, how to design such a system from the ground up, and why the direction Twitter is heading looks to be security theater rather than serious cryptographic engineering.

If you’re not interested in those things, but are interested in what I’m proposing for the Fediverse, head on over to the GitHub repository hosting my work-in-progress proposal draft as I continue to develop it.

How to Quickly Build E2EE

If one were feeling particularly cavalier about your E2EE designs, they could just generate then dump public keys through a server they control, pass between users, and have them encrypt client-side. Over and done. Check that box.

Every public key would be ephemeral and implicitly trusted, and the threat model would mostly be, “I don’t want to deal with law enforcement data requests.”

Hell, I’ve previously written an incremental blog post to teach developers about E2EE that begins with this sort of design. Encrypt first, ratchet second, manage trust relationships on public keys last.

If you’re catering to a slightly tech-savvy audience, you might throw in SHA256(pk1 + pk2) -> hex2dec() and call it a fingerprint / safety number / “conversation key” and not think further about this problem.

Look, technical users can verify out-of-band that they’re not being machine-in-the-middle attacked by our service.

An absolute fool who thinks most people will ever do this

From what I’ve gathered, this appears to be the direction that Twitter is going.

https://twitter.com/wongmjane/status/1592831263182028800

Now, if you’re building E2EE into a small hobby app that you developed for fun (say: a World of Warcraft addon for erotic roleplay chat), this is probably good enough.

If you’re building a private messaging feature that is intended to “superset Signal” for hundreds of millions of people, this is woefully inadequate.

https://twitter.com/elonmusk/status/1590426255018848256

Art: LvJ

If this is, indeed, the direction Musk is pushing what’s left of Twitter’s engineering staff, here is a brief list of problems with what they’re doing.

1. Twitter Web. How do you access your E2EE DMs after opening Twitter in your web browser on a desktop computer?
   
   • If you can, how do you know twitter.com isn’t including malicious JavaScript to snarf up your secret keys on behalf of law enforcement or a nation state with a poor human rights record?
   • If you can, how are secret keys managed across devices?
   • If you use a password to derive a secret key, how do you prevent weak, guessable, or reused passwords from weakening the security of the users’ keys?
   • If you cannot, how do users decide which is their primary device? What if that device gets lost, stolen, or damaged?

   
   

2. Authenticity. How do you reason about the person you’re talking with?
3. Forward Secrecy. If your secret key is compromised today, can you recover from this situation? How will your conversation participants reason about your new Conversation Key?
4. Multi-Party E2EE. If a user wants to have a three-way E2EE DM with the other members of their long-distance polycule, does Twitter enable that?
   
   • How are media files encrypted in a group setting? If you fuck this up, you end up like Threema.
   • Is your group key agreement protocol vulnerable to insider attacks?

   
   

5. Cryptography Implementations.
   
   • What does the KEM look like? If you’re using ECC, which curve? Is a common library being used in all devices?
   • How are you deriving keys? Are you just using the result of an elliptic curve (scalar x point) multiplication directly without hashing first?

   
   

6. Independent Third-Party Review.
   
   • Who is reviewing your protocol designs?
   • Who is reviewing your cryptographic primitives?
   • Who is reviewing the code that interacts with E2EE?
   • Is there even a penetration test before the feature launches?

   
   

As more details about Twitter’s approach to E2EE DMs come out, I’m sure the above list will be expanded with even more questions and concerns.

My hunch is that they’ll reuse liblithium (which uses Curve25519 and Gimli) for Twitter DMs, since the only expert I’m aware of in Musk’s employ is the engineer that developed that library for Tesla Motors. Whether they’ll port it to JavaScript or just compile to WebAssembly is hard to say.

How To Safely Build E2EE

You first need to decompose the E2EE problem into five separate but interconnected problems.

1. Client-Side Secret Key Management.
   
   • Multi-device support
   • Protect the secret key from being pilfered (i.e. by in-browser JavaScript delivered from the server)

   
   

2. Public Key Infrastructure and Trust Models.
   
   • TOFU (the SSH model)
   • X.509 Certificate Authorities
   • Certificate/Key/etc. Transparency
   • SigStore
   • PGP’s Web Of Trust

   
   

3. Key Agreement.
   
   • While this is important for 1:1 conversations, it gets combinatorially complex when you start supporting group conversations.

   
   

4. On-the-Wire Encryption.
   
   • Direct Messages
   • Media Attachments
   • Abuse-resistance (i.e. message franking for abuse reporting)

   
   

5. The Construction of the Previous Four.
   
   • The vulnerability of most cryptographic protocols exists in the joinery between the pieces, not the pieces themselves. For example, Matrix.

   
   

This might not be obvious to someone who isn’t a cryptography engineer, but each of those five problems is still really hard.

To wit: The latest IETF RFC draft for Message Layer Security, which tackles the Key Agreement problem above, clocks in at 137 pages.

Additionally, the order I specified these problems matters; it represents my opinion of which problem is relatively harder than the others.

When Twitter’s CISO, Lea Kissner, resigned, they lost a cryptography expert who was keenly aware of the relative difficulty of the first problem.

https://twitter.com/LeaKissner/status/1592937764684980224

You may also notice the order largely mirrors my previous guide on the subject, in reverse. This is because teaching a subject, you start with the simplest and most familiar component. When you’re solving problems, you generally want the opposite: Solve the hardest problems first, then work towards the easier ones.

This is precisely what I’m doing with my E2EE proposal for the Fediverse.

The Journey of a Thousand Miles Begins With A First Step

Before you write any code, you need specifications.

Before you write any specifications, you need a threat model.

Before you write any threat models, you need both a clear mental model of the system you’re working with and how the pieces interact, and a list of security goals you want to achieve.

Less obviously, you need a specific list of non-goals for your design: Properties that you will not prioritize. A lot of security engineering involves trade-offs. For example: elliptic curve choice for digital signatures is largely a trade-off between speed, theoretical security, and real-world implementation security.

If you do not clearly specify your non-goals, they still exist implicitly. However, you may find yourself contradicting them as you change your mind over the course of development.

Being wishy-washy about your security goals is a good way to compromise the security of your overall design.

In my Mastodon E2EE proposal document, I have a section called Design Tenets, which states the priorities used to make trade-off decisions. I chose Usability as the highest priority, because of AviD’s Rule of Usability.

Security at the expense of usability comes at the expense of security.

Avi Douglen, Security StackExchange

Underneath Tenets, I wrote Anti-Tenets. These are things I explicitly and emphatically do not want to prioritize. Interoperability with any incumbent designs (OpenPGP, Matrix, etc.) is the most important anti-tenet when it comes to making decisions. If our end-state happens to interop with someone else’s design, cool. I’m not striving for it though!

Finally, this section concludes with a more formal list of Security Goals for the whole project.

Art: LvJ

Every component (from the above list of five) in my design will have an additional dedicated Security Goals section and Threat Model. For example: Client-Side Secret Key Management.

You will then need to tackle each component independently. The threat model for secret-key management is probably the trickiest. The actual encryption of plaintext messages and media attachments is comparatively simple.

Finally, once all of the pieces are laid out, you have the monumental (dare I say, mammoth) task of stitching them together into a coherent, meaningful design.

If you did your job well at the outset, and correctly understand the architecture of the distributed system you’re working with, this will mostly be straightforward.

Making Progress

At every step of the way, you do need to stop and ask yourself, “If I was an absolute chaos gremlin, how could I fuck with this piece of my design?” The more pieces your design has, the longer the list of ways to attack it will grow.

It’s also helpful to occasionally consider formal methods and security proofs. This can have surprising implications for how you use some algorithms.

You should also be familiar enough with the cryptographic primitives you’re working with before you begin such a journey; because even once you’ve solved the key management story (problems 1, 2 and 3 from the above list of 5), cryptographic expertise is still necessary.

• If you’re feeding data into a hash function, you should also be thinking about domain separation. More information.
• If you’re feeding data into a MAC or signature algorithm, you should also be thinking about canonicalization attacks. More information.
• If you’re encrypting data, you should be thinking about multi-key attacks and confused deputy attacks. Also, the cryptographic doom principle if you’re not using IND-CCA3 algorithms.
• At a higher-level, you should proactively defend against algorithm confusion attacks.

How Do You Measure Success?

It’s tempting to call the project “done” once you’ve completed your specifications and built a prototype, and maybe even published a formal proof of your design, but you should first collect data on every important metric:

1. How easy is it to use your solution?
2. How hard is it to misuse your solution?
3. How easy is it to attack your solution? Which attackers have the highest advantage?
4. How stable is your solution?
5. How performant is your solution? Are the slow pieces the deliberate result of a trade-off? How do you know the balance was struck corectly?

Where We Stand Today

I’ve only begun writing my proposal, and I don’t expect it to be truly ready for cryptographers or security experts to review until early 2023.

However, my clearly specified tenets and anti-tenets were already useful in discussing my proposal on the Fediverse.

@soatok @fasterthanlime Should probably embed the algo used for encryption in the data used for storing the encrypted blob, to support multiples and future changes.

@fabienpenso@hachyderm.io proposes in-band protocol negotiation instead of versioned protocols

The main things I wanted to share today are:

1. The direction Twitter appears to be heading with their E2EE work, and why I think it’s a flawed approach
2. Designing E2EE requires a great deal of time, care, and expertise; getting to market quicker at the expense of a clear and careful design is almost never the right call

Mastodon? ActivityPub? Fediverse? OMGWTFBBQ!

In case anyone is confused about Mastodon vs ActivityPub vs Fediverse lingo:

The end goal of my proposal is that I want to be able to send DMs to queer furries that use Mastodon such that only my recipient can read them.

Achieving this end goal almost exclusively requires building for ActivityPub broadly, not Mastodon specifically.

However, I only want to be responsible for delivering this design into the software I use, not for every single possible platform that uses ActivityPub, nor all the programming languages they’re written in.

I am going to be aggressive about preventing scope creep, since I’m doing all this work for free. (I do have a Ko-Fi, but I won’t link to it from here. Send your donations to the people managing the Mastodon instance that hosts your account instead.)

My hope is that the design documents and technical specifications become clear enough that anyone can securely implement end-to-end encryption for the Fediverse–even if special attention needs to be given to the language-specific cryptographic libraries that you end up using.

Art: LvJ

Why Should We Trust You to Design E2EE?

This sort of question comes up inevitably, so I’d like to tackle it preemptively.

My answer to every question that begins with, “Why should I trust you” is the same: You shouldn’t.

There are certainly cryptography and cybersecurity experts that you will trust more than me. Ask them for their expert opinions of what I’m designing instead of blanketly trusting someone you don’t know.

I’m not interested in revealing my legal name, or my background with cryptography and computer security. Credentials shouldn’t matter here.

If my design is good, you should be able to trust it because it’s good, not because of who wrote it.

If my design is bad, then you should trust whoever proposes a better design instead. Part of why I’m developing it in the open is so that it may be forked by smarter engineers.

Knowing who I am, or what I’ve worked on before, shouldn’t enter your trust calculus at all. I’m a gay furry that works in the technology industry and this is what I’m proposing. Take it or leave it.

Why Not Simply Rubber-Stamp Matrix Instead?

(This section was added on 2022-11-29.)

There’s a temptation, most often found in the sort of person that comments on the /r/privacy subreddit, to ask why even do all of this work in the first place when Matrix already exists?

The answer is simple: I do not trust Megolm, the protocol designed for Matrix.

Megolm has benefited from amateur review for four years. Non-cryptographers will confuse this observation with the proposition that Matrix has benefited from peer review for four years. Those are two different propositions.

In fact, the first time someone with cryptography expertise bothered to look at Matrix for more than a glance, they found critical vulnerabilities in its design. These are the kinds of vulnerabilities that are not easily mitigated, and should be kept in mind when designing a new protocol.

You don’t have to take my word for it. Listen to the Security, Cryptography, Whatever podcast episode if you want cryptographic security experts’ takes on Matrix and these attacks.

From one of the authors of the attack paper:

So they kind of, after we disclosed to them, they shared with us their timeline. It’s not fixed yet. It’s a, it’s a bigger change because they need to change the protocol. But they always said like, Okay, fair enough, they’re gonna change it. And they also kind of announced a few days after kind of the public disclosure based on the public reaction that they should prioritize fixing that. So it seems kind of in the near future, I don’t have the timeline in front of me right now. They’re going to fix that in the sense of like the— because there’s, notions of admins and so on. So like, um, so authenticating such group membership requests is not something that is kind of completely outside of, kind of like the spec. They just kind of need to implement the appropriate authentication and cryptography.

Martin Albrecht, SCW podcast

From one of the podcast hosts:

I guess we can at the very least tell anyone who’s going forward going to try that, that like, yes indeed. You should have formal models and you should have proofs. And so there’s this, one of the reactions to kind of the kind of attacks that we presented and also to prior previous work where we kind of like broken some cryptographic protocols is then to say like, “Well crypto’s hard”, and “don’t roll your own crypto.” But in a way the thing is like, you know, we need some people to roll their own crypto because that’s how we have crypto. Someone needs to roll it. But we have developed techniques, we have developed formalisms, we have developed methods for making sure it doesn’t have to be hard, it’s not, it’s not a dark art kind of that only kind of a few, a select few can master, but it’s, you know, it’s a science and you can learn it. So, but you need to then indeed employ a cryptographer in kind of like forming, modeling your protocol and whenever you make changes, then, you know, they need to look over this and say like, Yes, my proof still goes through. Um, so like that is how you do this. And then, then true engineering is still hard and it will remain hard and you know, any science is hard, but then at least you have some confidence in what you’re doing. You might still then kind of on the space and say like, you know, the attack surface is too large and I’m not gonna to have an encrypted backup. Right. That’s then the problem of a different hard science, social science. Right. But then just use the techniques that we have, the methods that we have to establish what we need.

Thomas Ptacek, SCW podcast

It’s tempting to listen to these experts and say, “OK, you should use libsignal instead.”

But libsignal isn’t designed for federation and didn’t prioritize group messaging. The UX for Signal is like an IM application between two parties. It’s a replacement for SMS.

It’s tempting to say, “Okay, but you should use MLS then; never roll your own,” but MLS doesn’t answer the group membership issue that plagued Matrix. It punts on these implementation details.

Even if I use an incumbent protocol that privacy nerds think is good, I’ll still have to stitch it together in a novel manner. There is no getting around this.

Maybe wait until I’ve finished writing the specifications for my proposal before telling me I shouldn’t propose anything.

---

Credit for art used in header: LvJ, Harubaki

https://soatok.blog/2022/11/22/towards-end-to-end-encryption-for-direct-messages-in-the-fediverse/

#endToEndEncryption #Twitter

Let’s talk about digital signature algorithms.

Digital signature algorithms are one of the coolest ideas to come out of asymmetric (a.k.a. public-key) cryptography, but they’re so simple and straightforward that most cryptography nerds don’t spend a lot of time thinking about them.

Even though you are more likely to run into a digital signature as a building block (e.g. certificate signatures in TLS) than think about them in isolation (e.g. secure software releases), they’re still really cool and worth learning about.

What’s a Digital Signature?

A digital signature is some string that proves that a specific message was signed by some specific entity in possession of the secret half of an asymmetric key-pair. Digital Signature Algorithms define the process for securely signing and verifying messages with their associated signatures.

For example, if I have the following keypair:

• Secret key: 9080a2c7897faeb8526968161695da0f7b3afa2e8e7d8e8369a85547ab48ea05
• Public key: 482b8d3430445cdad6b5ce59778e09ab59d099120f32d316e881db1a6330390b

I can cryptographically sign the message “Dhole Moments: Never a dull moment!” with the above secret key, and it will generate the signature string: 63629779a31b623486145359c6f1d56602d8d9135e4b17fa2ae3667c8947397decd7ae01bfed08645a429f5dee906e87df4e18eefdfff9acb5b1488c9dec800f.

If you only have the message, signature string, and my public key, you can verify that I signed the message. But, very crucially, you cannot sign messages and convince someone else that they came from me. (With symmetric authentication schemes, such as HMAC, you can.)

A digital signature algorithm is considered secure if, in order for anyone else to pass off a different message as being signed by me, they would need my secret key to succeed. When this assumption holds true, we say the scheme is secure against existential forgery attacks.

How Do Digital Signatures Work?

Simple answer: They generally combine a cryptographic hash function (e.g. SHA-256) with some asymmetric operation, and the details beyond that are all magic.

More complicated answer: That depends entirely on the algorithm in question!

Art by Swizz

For example, with RSA signatures, you actually encrypt a hash of the message with your secret key to sign the message, and then you RSA-decrypt it with your public key to verify the signature. This is backwards from RSA encryption (where you do the totally sane thing: encrypt with public key, decrypt with secret key).

In contrast, with ECDSA signatures, you’re doing point arithmetic over an elliptic curve (with a per-signature random value).

Yet another class of digital signature algorithms are hash-based signatures, such as SPHINCS+ from the NIST Post-Quantum Cryptography Standardization effort, wherein your internals consist entirely of hash functions (and trees of hash functions, and stream ciphers built with other hash functions).

In all cases, the fundamental principle stays the same: You sign a message with a secret key, and can verify it with a public key.

In the interest of time, I’m not going to dive deep into how each signature algorithm works. That can be the subject of future blog posts (one for each of the algorithms in question).

Quick aside: Cryptographers who stumble across my blog might notice that I deviate from convention a bit. They typically refer to the sensitive half of an asymmetric key pair as a “private key”, but I instead call it a “secret key”.

The main reason for this is that “secret key” can be abbreviated as “sk” and public key can be abbreviated as “pk”, whereas private/public doesn’t share this convenience. If you ever come across their writings and wonder about this discrepancy, I’m breaking away from the norm and their way is more in line with the orthodoxy.

What Algorithms Should I Use?

What algorithm, indeed! (Art by circuitslime)

If you find yourself asking this question, you’re probably dangerously close to rolling your own crypto. If so, you’ll want to hire a cryptographer to make sure your designs aren’t insecure. (It’s extremely easy to design or implement otherwise-secure cryptography in an insecure way.)

Recommended Digital Signature Algorithms

(Update, 2022-05-19): I’ve published a more in-depth treatment of the Elliptic Curve Digital Signature Algorithms a few years after this post was created. A lot of the topics covered by EdDSA and ECDSA are focused on there.

EdDSA: Edwards Curve DSA

EdDSA comes in two variants: Ed25519 (widely supported in a lot of libraries and protocols) and Ed448 (higher security level, but not implemented or supported in as many places).

The IETF standardized EdDSA in RFC 8032, in an effort related to the standardization of RFC 7748 (titled: Elliptic Curves for Security).

Formally, EdDSA is derived from Schnorr signatures and defined over Edwards curves. EdDSA’s design was motivated by the real-world security failures of ECDSA:

1. Whereas ECDSA requires a per-signature secret number () to protect the secret key, EdDSA derives the per-signature nonce deterministically from a hash of the secret key and message.
2. ECDSA with biased nonces can also leak your secret key through lattice attacks. To side-step this, EdDSA uses a hash function twice the size as the prime (i.e. SHA-512 for Ed25519), which guarantees that the distribution of the output of the modular reduction is unbiased (assuming uniform random inputs).
3. ECDSA implemented over the NIST Curves is difficult to implement in constant-time: Complicated point arithmetic rules, point division, etc. EdDSA only uses operations that are easy to implement in constant-time.

For a real-world example of why EdDSA is better than ECDSA, look no further than the Minerva attacks, and the Ed25519 designer’s notes on why EdDSA stood up to the attacks.

The security benefits of EdDSA over ECDSA are so vast that FIPS 186-5 is going to include Ed25519 and Ed448.

Hooray for EdDSA adoption even in federal hellscapes.

This is kind of a big deal! The FIPS standards are notoriously slow-moving, and they’re deeply committed to a sunk cost fallacy on algorithms they previously deemed acceptable for real-world deployment.

RFC 6979: Deterministic ECDSA

Despite EdDSA being superior to ECDSA in virtually every way (performance, security, misuse-resistance), a lot of systems still require ECDSA support for the foreseeable future.

If ECDSA is here to stay, we might as well make it suck less in real-world deployments. And that’s exactly what Thomas Pornin did when he wrote RFC 6979: Deterministic Usage of DSA and ECDSA.

(Like EdDSA, Deterministic ECDSA is on its way to FIPS 186-5. Look for it in FIPS-compliant hardware 5 years from now when people actually bother to update their implementations.)

Acceptable Digital Signature Algorithms

ECDSA Signatures

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the incumbent design for signatures. Unlike EdDSA, ECDSA is a more flexible design that has been applied to many different types of curves.

This is more of a curse than a blessing, as Microsoft discovered with CVE-2020-0601: You could take an existing (signature, public key) pair with standard curve, explicitly set the generator point equal to the victim’s public key, and set your secret key to 1, and Windows’s cryptography library would think, “This is fine.”

For this reason, cryptographers were generally wary of proposals to add support for Koblitz curves (including secp256k1–the Bitcoin curve) or Brainpool curves into protocols that are totally fine with NIST P-256 (and maybe NIST P-384 if you need it for compliance reasons).

For that reason, if you can’t use EdDSA or RFC 6979, your fallback option is ECDSA with one of those two curves (secp256r1, secp384r1), and making sure that you have access to a reliable cryptographic random number generator.

RSA Signatures

It’s high time the world stopped using RSA.

Not just for the reasons that Trail of Bits is arguing (which I happen to agree with), but more importantly:

Replacing RSA with EdDSA (or Deterministic ECDSA) also gives teams an opportunity to practice migrating from one cryptography algorithm suite to another, which will probably be a much-needed experience when quantum computers come along and we’re all forced to migrate to post-quantum cryptography.

Encryption is a bigger risk of being broken by quantum computers than signature schemes: If you encrypt data today, a quantum computer 20 years down the line can decrypt it immediately. Conversely, messages that are signed today cannot be broken until after a quantum computer exists.

That being said, if you only need signatures and not encryption, RSA is still acceptable. If you also need encryption, don’t use RSA for that purpose.

If you can, use PSS padding rather than PKCS#1 v1.5 padding, with SHA-256 or SHA-384. But for signatures (i.e. not encryption), PKCS#1 v1.5 padding is fine.

Dishonorable Mention

DSA Signatures

There’s really no point in using classical DSA, when ECDSA is widely supported and has more ongoing attention from cryptography experts.

If you’re designing a system in 2020 that uses DSA, my only question for you is…

WHYYYYYY?! (Art by Khia)

Upcoming Signature Algorithms

Although it is far too early to consider adopting these yet, cryptographers are working on new designs that protect against wider ranges of real-world threats.

Let’s briefly look at some of them and speculate wildly about what the future looks like. For fun. Don’t use these yet, unless you have a very good reason to do so.

Digital Signature Research Topics

Hedged Signatures

Above, we concluded that EdDSA and Deterministic ECDSA were generally the best choice (and what I’d recommend for software developers). There is one important caveat: Fault attacks.

A fault attack is when you induce a hardware fault into a computer chip, and thereby interfere with the correct functioning of a cryptography algorithm. This is especially relevant to embedded devices and IoT.

The IETF’s CFRG is investigating the use of additional randomization of messages (rather than randomizing signatures) as a safeguard against leaking secret keys through fault injection.

Of course, the Dhole Cryptography Library (my libsodium wrapper for JavaScript and PHP) already provides a form of Hedged Signatures.

If this technique is proven successful at mitigating fault injection attacks, then libsodium users will be able to follow the technique outlined in Dhole Crypto to safeguard their own protocols against fault attacks. Until then, they’re at least as safe as deterministic EdDSA today.

Threshold ECDSA Signatures

Suppose you have a scenario where you want 3-or-more people to have to sign a message before it’s valid. That’s exactly what Threshold ECDSA with Fast Trustless Setup aspires to provide.

Although this is mostly being implemented in cryptocurrency projects today, the cryptography underpinnings are fascinating. At worst, this will be one good side-effect to come from blockchain mania.

Post-Quantum Digital Signatures

Hash-Based Signatures

The best hash-based signature schemes are based on the SPHINCS design for one simple reason: It’s stateless.

In earlier hash-based digital signatures, such as XMSS, you have to maintain a state of which keys you’ve already used, to prevent attacks. Google’s Adam Langley previously described this as a “huge foot-cannon” for security (although probably okay in some environments, such as an HSM).

Lattice-Based Signatures

There are a lot of post-quantum signature algorithm designs defined over lattice groups, but my favorite lattice-based design is called FALCON. FALCON stands for FAst-Fourier Lattice-based COmpact Signatures Over NTRU.

Sign Here, Please

Who knew there would be so much complexity involved with such a simple cryptographic operation? And we didn’t even dive deep on how any of them work.

That’s the problem with cryptography: It’s a fractal of complexity. The more you know about these topics, the deeper the complexity becomes.

But if you’re implementing a protocol today and need a digital signature algorithm, use (in order of preference):

1. Ed25519 or Ed448
2. ECDSA over NIST P-256 or P-384, with RFC 6979
3. ECDSA over NIST P-256 or P-384, without RFC 6979
4. RSA (as a last resort)

But most importantly: make sure you have a cryptographer audit your designs.

(Header art by Kyume.)

https://soatok.blog/2020/04/26/a-furrys-guide-to-digital-signature-algorithms/

#crypto #cryptography #DeterministicSignatures #digitalSignatureAlgorithm #ECDSA #Ed25519 #Ed448 #EdDSA #FIPS #FIPS186 #FIPSCompliance #RFC6979 #SecurityGuidance

Dhole Moments

2022-05-19 07:36:36

Earlier this year, Cendyne published A Deep Dive into Ed25519 Signatures, which covered some of the different types of digital signature algorithms, but mostly delved into the Ed25519 algorithm. Truth in advertising.

This got me thinking, “Why isn’t there a better comparison of different elliptic curve signature algorithms available online?”

Art: LvJ

Most people just defer to SafeCurves, but it’s a little dated: We have complete addition formulas for Weierstrass curves now, but SafeCurves doesn’t reflect that.

For the purpose of simplicity, I’m not going to focus on a general treatment of Elliptic Curve Cryptography (ECC), which includes pairing-based cryptography, Elliptic-Curve Diffie-Hellman, and (arguably) isogeny cryptography.

Instead, I’m going to focus entirely on elliptic curve digital signature algorithms.

Note: The content of this post is a bit lower-level than most programmers ever need to be concerned with. If you’re a programmer and interested in learning cryptography, start here. If you’re looking for library recommendations, libsodium is a good safe default.

Compliance Rules Everything Around Me

If you have to meet some arbitrary compliance requirements (i.e. FIPS 140-3, CNSA, etc.), your decision is already made for you, and you shouldn’t waste your time reading blogs like this that will only get your hopes up about the options available to you.

Choose the option your compliance officer demands, and hope it’s good enough.

“Sure, let me check that box.”
Art: LvJ

Elliptic Curves for Signature Algorithms

Let’s start with the same curve Cendyne analyzed: Ed25519.

Ed25519 (EdDSA, Curve25519)

Ed25519 is one of the two digital signature algorithms today that use the EdDSA algorithm framework. The other is Ed448, which targets a higher security level (224-bit vs 128-bit) but is also slower and uses SHAKE256 (which is overkill and not great for performance).

Ed25519 is a safe default choice for most applications where a digital signature is appropriate, for many reasons:

1. Ed25519 uses deterministic nonces, which means you’re severely unlikely to ever reproduce the Sony ECDSA k-reuse bug in your system.
   The deterministic nonce is calculated from the SHA512 hash of the secret key and message. Two invocations to crypto_sign_ed25519() with the same message and secret key will produce the same signature, but the intermediate nonce value is never revealed to an attacker.
2. Ed25519 includes the public key in the data hashed to produce the signature (more specifically s from the (R,s) pair). This offers a property that ECDSA lacks: Exclusive Ownership. I’ve written about this property before.
   Without Exclusive Ownership, it’s possible to create a single signature value that’s valid for multiple different (message, public key) pairs.

Years ago, there would have an additional list item: Ed25519 uses Edward Curves, which have complete addition formulas and are therefore safer to implement in constant-time than Weierstrass curves (i.e. the NIST curves). However, we now have complete addition formulas for Weierstrass curves, so this has become a moot point (assuming your implementation uses complete addition formulas).

Ed25519 targets the 128-bit security level.

Why Not Use Ed25519?

There is one minor pitfall of Ed25519 that makes it unsuitable for esoteric uses (say, Ring Signature Schemes or zero-knowledge proofs): Ed25519 is not a prime-order group; it has a cofactor h = 8. This detail famously created a double-spend vulnerability in all CryptoNote-based cryptocurrencies (including Monero).

For systems that want the security of Ed25519 and its various well-studied implementations, but still need a prime-order group for their protocol, cryptographers have developed the Ristretto Group to meet your needs.

If you’re working on embedded systems, the determinism inherent to EdDSA might be undesirable due to the possibility of fault attacks. You can use a hedged variant of Ed25519 to mitigate this risk.

Additionally, Ed25519 is not approved for many government applications, although it did make the latest draft revision of FIPS 186 in 2019. If you care about compliance (see above), you cannot use Ed25519. Yet.

A niche Internet meme for cryptography engineers

Guidance for Ed25519

Unless legally prohibited, Ed25519 should be your default choice, unless you need a prime-order group. In that case, build your desired protocol atop Ristretto255.

If you’re not sure if you need a prime-order group, you probably don’t. It’s a specialized requirement for uncommon use cases (ring signatures, password authenticated key exchange protocols, zero-knowledge proofs, etc.).

Art: LvJ

The Bitcoin Curve (ECDSA, secp256k1)

Secp256k1 is a Koblitz curve, which is a special case of Weierstrass curves that are more performant when used in binary fields, of the form, . This curve is almost exclusively used in cryptocurrency software.

There is no specified reason why Bitcoin chose secp256k1 over another elliptic curve at the time of its inception, but we can speculate:

The author was a pseudonymous contributor to the Metzdowd mailing list for cypherpunks, and probably didn’t trust the NIST curves. Since Ed25519 didn’t exist at the time, the only obvious choice for a hipster elliptic curve parameter selection was to rely on the SECG recommendations, which specify the NIST and Koblitz curves. If you cross the NIST curves off the list, only the Koblitz curves remained.

Therefore, the selection of secp256k1 is likely an artefact of computer history and not a compelling reason to select secp256k1 in new designs. Please look elsewhere.

Fact: Imgflip didn’t have a single secp256k1 meme until I made this one.

Secp256k1 targets the 128-bit security level.

Guidance for secp256k1

Don’t bother, there are better options. (i.e. Ed25519)

If you’re writing software for a cryptocurrency-related project, and you feel compelled to use secp256k1 for the sake of reducing your code footprint, please strongly consider the option of burning everything to the proverbial ground.

Cryptocurrency sucks!
Art: Swizz

Cryptocurrency Aside, Why Avoid Secp256k1?

As we noted above, secp256k1 isn’t widely used outside of cryptocurrency.

As a direct consequence of this (as we’ll discuss in the NIST P-256 section), most cryptography libraries don’t offer optimized, side-channel-resistant implementations of secp256k1; even if they do offer optimized implementations of NIST P-256.

(Meanwhile, Ed25519 is designed to be side-channel and misuse-resistant, partly due to its Schnorr construction and constant-time ladder for scalar multiplication, so any library that implements Ed25519 is overwhelmingly likely to be constant-time.)

Therefore, any secp256k1 library for most programming languages that isn’t an FFI wrapper for libsecp256k1 will have worse performance than the other 256-bit curves.

https://twitter.com/bascule/status/1320183684935290882

Additionally, secp256k1 implementations are often a source of exploitable side-channels that permit attackers to pilfer your secret keys.

The previously linked article was about BouncyCastle’s implementation (which covers Java and .NET), but there’s still plenty of secp256k1 implementations that don’t FFI libsecp256k1.

From a quick Google Search:

• Python (uses EEA rather than Binary GCD for modular inverse)
• Go (uses Numbers, which weren’t designed for cryptography)
• PHP (uses GMP, which isn’t constant-time)
• JavaScript (calls here, which uses bn.js, which isn’t constant-time)

If you’re using secp256k1, and you’re not basing your choice on cybercash-interop, you’re playing with fire at the implementation and ecosystem levels–even if there are no security problems with the Koblitz curve itself.

You are much better off choosing any different curve than secp256k1 if you don’t have a Bitcoin/Ethereum/etc. interoperability requirement.

“No thanks, I use Ed25519.”
Art: LvJ

NIST P-256 (ECDSA, secp256r1)

NIST P-256 is the go-to curve to use with ECDSA in the modern era. Unlike Ed25519, P-256 uses a prime-order group, and is an approved algorithm to use in FIPS-validated modules.

Most cryptography libraries offer optimized assembly implementations of NIST P-256, which makes it less likely that your signing operations will leak timing information or become a significant performance bottleneck.

P-256 targets the 128-bit security level.

Why Not Use P-256?

Once upon a time, P-256 was riskier than Ed25519 (for signatures) and X25519 (for Diffie-Hellman), due to the incomplete addition formulas that led to timing-leaky implementations.

If you’re running old software, you may still be vulnerable to timing attacks that can recover your ECDSA secret key. However, there is a good chance that you’re on a modern and secure implementation in 2022, especially if you’re outsourcing this to OpenSSL or its derivatives.

ECDSA requires a secure randomness source to sign data. If you don’t have one available, and you sign anything, you’re coughing up your secret key to any attacker capable of observing multiple signatures.

Guidance for P-256

P-256 is an acceptable choice, especially if you’re forced to cope with FIPS and/or the CNSA suite requirements when using cryptography.

Of course, if you can get away with Ed25519, use Ed25519 instead.

If you use P-256, make sure you’re using it with SHA-256. Some implementations may default to something weaker (e.g. SHA-1).

If you’re also going to be performing ECDH with P-256, make sure you use compressed points. There used to be a patent; it died in 2018.

If you can afford it, make sure you use deterministic ECDSA (RFC 6979) or hedged signatures (if fault attacks are relevant to your threat model).

Art: LvJ

NIST P-384 (ECDSA, secp384r1)

NIST P-384 has a larger field than the curves we’ve previously examined, which allows P-384 to target the 192-bit security level. That’s the primary reason why anyone would choose P-384.

Naturally, elliptic curve security is more complicated than merely security against the Elliptic Curve Discrete Logarithm Problem (ECDLP).

P-384 is most often paired with SHA-384, which is the most widely used flavor of the SHA-2 family hash functions that isn’t susceptible to length-extension attacks. (There are also truncated SHA-512 variants specified later, but that’s also what SHA-384 is under-the-hood.)

If you’re aiming to build a “secure-by-default” tool for a system that the US government might one day become a customer of, with minimal cryptographic primitive choice, using NIST P-384 with SHA-384 makes for a reasonably minimalistic bundle.

Why Not Use P-384?

Unlike P-256, most P-384 implementations don’t use constant-time, optimized, and/or formally verified assembly code. (Notable counter-examples: AWS-LC and Go x/crypto.)

Like P-256, P-384 also requires a secure randomness source to sign data. If you aren’t providing one, expect your signing key to end up on fail0verflow one day.

Guidance for P-384

If you use P-384, make sure you’re using it with SHA-384.

The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.

Art: Kyume

NIST P-521 (ECDSA, secp521r1)

Biggest curve is best curve! — the clueless

https://www.youtube.com/watch?v=i_APoSfCYwU

Systems that choose P-521 often have an interesting threat model, even though said threat model is rarely formally specified.

It’s overwhelmingly likely that what eventually breaks the 256-bit elliptic curves will also break P-521 in short order: Cryptography Relevant Quantum Computers.

The only thing P-521 does against CRQCs that P-256 doesn’t is require more quantum memory. If you’re worried about QRQCs, you might want to look into hybrid post-quantum signature schemes.

If you’re choosing P-521 in your designs, you’re basically saying, “I want to have 256 bits of asymmetric cryptographic security, come hell or high water!” even though the 128-bit security level is likely just fine for your actual threats.

Aside: P-521 and 512-bit ECC Security

P-521 is not a typo, although people sometimes think it is. P-521 uses the Mersenne prime instead of a 512-bit near-Mersenne prime.

This has led to an unfortunate trend in cryptography media to map ECC key sizes to symmetric security levels that misleads people as to the relationship between the two. For example:

Source
Source

Regrettably, this is misleading, because plotting the ECC Key Size versus equivalent Symmetric Security isn’t a how ECDLP security works. The ratio of the exponents involved is totally linear; it doesn’t suddenly increase beyond 384-bit curves for a mysterious mathematical reason.

• 256-bit Curves target the 128-bit security level
• 384-bit Curves target the 192-bit security level
• 512-bit Curves target the 256-bit security level
• 521-bit Curves actually target the 260-bit security level, but that meets or exceeds the 256-bit security level, so that’s how the standards are interpreted

The reason for this boils down entirely to the best attack against the Elliptic Curve Discrete Logarithm Problem: Pollard’s Rho, which recovers the secret key from an -bit public key (which has a search space) in guesses.

Taking the square root of a number is the same as halving its exponent, so the security level is half: .

Takeaway: If someone tells you that you need a 521-bit curve to meet the 256-bit security level, they are mistaken and it’s not their fault.

Art: Harubaki

Why Not Use P-521?

It’s slow. Much slower than P-256 and Ed25519. Modestly slower than P-384.

Unlike P-384, you’re less likely to find an optimized, constant-time P-521 implementation.

Guidance for P-521

First, make a concerted effort to figure out the motivation for P-521 in your designs. Chances are, someone is putting too much emphasis on the wrong things for security.

If you use P-521, make sure you’re using it with SHA-512.

The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.

Art: LvJ

Ed448 (EdDSA, Curve448)

Ed448 is the P-521 of the Edwards curves: It mostly exists to give standards committees a psychological comfort for the unlikely event that 256-bit ECC is desperately broken but ECC larger than 384 bits is somehow still safe.

https://twitter.com/dchest/status/703017144053833728

The very concept of having multiple “security levels” for raw cryptography primitives is mostly an artefact of the historical military roots of cryptography, rather than a serious consideration in the modern world.

Unfortunately, this leads to implementations that prioritize runtime algorithm selection negotiation, which maximizes the risk of protocol-level vulnerabilities. See also: JWT.

Ed448 was specified to use SHAKE256, which is a needlessly conservative decision which leads to an unnecessary performance bottleneck.

Why Not Use Ed448?

Aside from the performance hit mentioned previously, there’s no compelling reason to avoid Ed448 that isn’t also true of either Ed25519 or P-384.

Guidance for Ed448

If you want more speed, go with Ed25519. In addition to being faster, Ed25519 is also very widely supported.

If you need a prime-order field, use Decaf with Ed448 or consider P-384.

The Brainpool Curves

The main motivation for the Brainpool curves is that the NIST curves were not generated in a “verifiable pseudo-random way”.

The only reasons you’d ever want to support the Brainpool curves include:

1. You think the NIST curves are somehow backdoored by the NSA
2. You don’t appreciate small attack surfaces in cryptography libraries
3. The German government told you to (see: compliance)

Most of the advice for the NIST Curves at each security level can be copy/pasted for the Brainpool curves, with one important caveat:

When considering real-world implementations, Brainpool curves are more likely to use the general purpose Big Number procedures (which aren’t always constant-time), rather than optimized assembly code, than the NIST curves are.

Therefore, my general guidance for the Brainpool curves is simply:

1. Proceed at your own peril
2. Consider hiring a cryptography engineer to study the implementation you’re relying on, especially with regard to timing attacks

Me when I hear “brainpool”
Art: LvJ

Re-Examining the SafeCurves Criteria

Here’s a 2022 refresh of the SafeCurves criteria for all of the curves considered by this blog post.

SafeCurve Criteria	Relevance to the Curves Listed Above
Fields	All relevant curves satisfy the requirements
Equations	All relevant curves satisfy the requirements
Base Points	All relevant curves satisfy the requirements
Rho	All relevant curves satisfy the requirements
Transfers	All relevant curves satisfy the requirements
Discriminants	Only secp256k1 doesn’t satisfy the requirements (out of the curves listed in this blog post)
Rigidity	The NIST curves do not meet this requirement. If you care about whether or not the standards were manipulated to insert a backdoor, rigidity matters to you. Otherwise, it’s not a deal-breaker.
Ladders	While a Montgomery ladder is beneficial for speed and implementation security, it isn’t strictly speaking required. This is an icing-on-the-cake consideration.
Twists	The only curve listed above that doesn’t meet the requirement is the 256-bit Brainpool curve (brainpoolp256t1).
Completeness	All relevant curves satisfy the requirements, as of 2015. SafeCurves is out of date here.
Indistinguishability	All relevant curves satisfy the requirements, as of 2014.

SafeCurves continues to be a useful resource, especially if you stray from the guidance on this page.

For example: You wouldn’t want to use pairing-friendly curves for general purpose ECC digital signatures, because they’re suitable for specialized problems. SafeCurves correctly recommends not using BN(2,254).

However, SafeCurves is showing its age in 2022. BN curves still end up in digital signature protocol standards even though BLS-12-381 is clearly a better choice.

The Internet would benefit greatly for an updated SafeCurves that focuses on newer elliptic curve algorithms.

Art: Scruff

TL;DR

Ed25519 is great. NIST P-256 and P-384 are okay (with caveats). Anything else is questionable, and their parameter selection should come with a clear justification.

https://soatok.blog/2022/05/19/guidance-for-choosing-an-elliptic-curve-signature-algorithm-in-2022/

#asymmetricCryptography #BrainpoolCurves #cryptography #digitalSignatureAlgorithm #ECDSA #Ed25519 #Ed448 #EdDSA #ellipticCurveCryptography #P256 #P384 #P521 #secp256k1 #secp256r1 #secp384r1 #secp521r1 #SecurityGuidance