Earlier this year, I wrote about planned effort to design a federated Key Transparency proposal.

The end goal for this work was constrained to building end-to-end encryption into a new type of Direct Message on the Fediverse, with other protocols and services being a stretch goal rather than its primary purpose.

The ideal situation is to enable developers to write code that looks as simple as this:

async function initialize(message, recipient) { const bundle = await fediverse.getSignedPreKeyBundle(recipient); // This also checks the inclusion proof and witness cosigs: const pubKey = await directory.fetch(recipient, bundle.keyId); if (!await pubKey.verify(bundle)) { throw new Error('Invalid signature or bundle'); } const session = await e2ee.beginSession(bundle); return session.send(message);}initialize("OwO what's this?", "soatok@furry.engineer") .then(async (session) => { /* ... */ });

And then have secure end-to-end encryption such that only a trusted public key for the intended recipient can decrypt.

Work on the specification for the Public Key Directory component has recently started. A few things have changed since my last blog post on the topic. I’ve also gotten a lot of similar questions that wouldn’t be appropriate to try to answer within the specification itself.

Original art: CMYKat, poorly edited by myself

The Big Picture

This section is written mostly for anyone who hasn’t paid attention to my other writing on this project.

This is how I believe this project will develop in the immediate future.

1. Public Key Directory (PKD)
   
   • Specification (WIP)
   • Reference Implementation (Not Started)
   • Client-Side SDKs (Not Started)
     
     • Go
     • Ruby
     • PHP
     • TypeScript

     
     

   
   

2. End-to-End Encryption for the Fediverse (FediE2EE)
   
   • Specification (WIP)
     
     • Client-Side Secret Key Management
     • Federated Public Key Infrastructure (See: PKD)
     • Asynchronous Forward-Secure Ratcheting Protocol + Group Key Agreement
     • Symmetric-Key Authenticated Encryption

     
     

   • Reference Implementations (Not Started)
     
     • Go
     • Ruby
     • PHP
     • TypeScript

     
     

   
   

3. Fediverse Instance Patches to Support E2EE
   
   • Mastodon
   • ?????

   
   

4. Client-Side Software
   
   • ?????

   
   

5. PKD Extensions
   
   • age v1 public keys

   
   

Once the PKD complete is complete, there’s nothing stopping other people from defining their own PKD extensions and building on top of our design to add Key Transparency to their own protocols.

My focus, once we have a solid specification and reference implementation, is going to shift towards building FediE2EE.

I will not, however, be working on client-side software unless no one else expresses interest.

The reason for my tentative recusal is simple: I absolutely suck at user interface design, and you’ll probably hate whatever I can cobble together. I am many things, but an artist is not one of them.

You don’t want me designing UIs.
Art: CMYKat

To that end, my final deliverable in this project will be open source libraries (and accompanying guidance for using said libraries) than user experience experts can glue into their own clients.

That said, the only client-side software that should exist are browser extensions, desktop clients, and mobile apps.

I strongly discourage anyone from trying to deploy any code that touches secret keys to a traditional web application, or JavaScript running inside of a WebView.

I’m ambivalent on Electron. It’s better than redownloading the code from a server and running it blindly every page load, but it’s not highly regarded by security professionals.

Decisions Made

The most important topic to cover is design decisions I’ve made with my specification that will shape the evolution of this project.

Account Recovery

The current draft of the specification includes two Protocol Message types, BurnDown and Fireproof, which warrant further examination.

BurnDown is simple in concept: It revokes all of a particular user’s public keys and auxiliary data records. If you have no currently-trusted public keys, you are permitted to push a self-signed AddKey message.

A not-so-subtle detail of BurnDown that everyone should pay attention to is that the instance admin can issue them on behalf of other users hosted on that server.

CMYKat

If you aren’t comfortable with your admin being able to issue a BurnDown at any time, that’s where Fireproof comes in: It allows you to opt out of this capability entirely.

Fireproof is a double-edged sword. It protects you from malicious admins, but it prevents you from ever recovering your account if you lose access to all of your secret keys.

The most important decision I made here is: Fireproof is an opt-in protection, which (as of the current draft) has no “undo”. (I’m considering allowing an “undo” if it makes sense to ever do so. Tell me what you think!)

It’s often said that security at the expense of usability comes at the expense of security. Account recovery mechanisms are, necessarily, always some kind of a backdoor.

Conversely, defaults matter to security. Allowing BurnDown messages be issued by default, from a specification perspective, implies most users will not issue a Fireproof message. (Client software may counteract this by prompting users with a choice when they first enroll, without a default setting, but I digress.)

I believe this choice is the best of all possible options, but you’re certainly welcome to disagree. It’s important to me that I be very loudly transparent about this decision.

No ECDSA Support

I had floated the idea of supporting NIST P-384 in my initial blog post.

Ultimately, there is no real incentive to do so, considering Ed25519 is now in FIPS 186-5 (which has been a standard for 18 months now).

And since we’re already using Ed25519, that satisfies any hypothetical FIPS use-case, should any governments choose to use my design for anything.

Thus, there will be no NIST P-384 support in the Public Key Directory project.

Art: AJ

Right To Be Forgotten

Key Transparency involves creating a global, immutable history. The Right To Be Forgotten enshrined in the EU’s GDPR law is fundamentally incompatible with the security goals of key transparency.

What this means is that, if I just shrugged and plugged Actor IDs and Public Keys into a hash function and committed that hash to a Merkle tree, then, years later, a malicious troll demands their data be removed in accordance with the GDPR, it immediately becomes a catch-22.

Do you comply with the asserted right and break the history and provable security of your transparency ledger? Or do you risk legal peril for noncompliance?

When I first noodled over this, a few people said, “But you’re not in the EU. Why do you care?”

And, like, some of the people that will want to use this design one day are in the EU. Some of them may want to run their own Public Key Directory instances. I want them to have a good time with it. Is that so strange?

There is a way to get both properties without sacrificing the universal consistency of a single Merkle tree, but it relies on untested legal theory.

MarleyTanuki

In short, what you need to do is:

1. Client-side: Encrypt the sensitive fields, then send the ciphertext and the ephemeral key to the Directory.
2. The Directory will commit to the ciphertext, not the plaintext, and hold onto the keys in order to decrypt records on-the-fly.
3. When a data erasure request comes in by an EU citizen asserting their right to be forgotten, erase the key to render the data irrecoverable.

This constitutes a forceful BurnDown with amnesia.

Does This Introduce Any Specific Risks?

This works in principle, but a couple of things need to hold true in order to maintain the integrity of the transparency log.

1. You need to use a committing authenticated encryption mode.
   Without this property, it’s possible to swap one key for another (rather than simply erasing it) and get a valid plaintext for the (ciphertext, tag) committed in the ledger.

   This protects the Directory from a malicious user that later gets privileged access and manipulates stored keys.

2. You need a plaintext commitment that is independent of the key. In addition to key-independence, it needs to be difficult to brute force, and you can’t have additional randomness (i.e., salts) added that could be changed after-the-fact to produce a “valid” commitment for another plaintext.
   This protects users from a Directory that lies about which plaintext a particular ciphertext decrypts to.

This is currently specified as follows:

1. Encryption is AES-256-CTR then HMAC-SHA512, Encrypt-then-MAC.
2. The authentication tag covers a random value used for subkey derivation, as well as a Plaintext Commitment (Q).
3. The Plaintext Commitment (Q) is derived from Argon2id and HMAC of the plaintext. There are some subtle detains with how the Argon2id salt is derived, and why specific parameters were chosen the way they are, but this is covered in the specification document.

I had considered using Zero Knowledge Proofs here, but the current HMAC + Argon2 approach solves the problem securely without needing to study ZKDocs (and its supporting material) for hours.

Does This Give Us Compliance?

If we assume that “crypto shredding” is a valid technique for complying with data erasure demands, this lets us honor those requests while ensuring independent third parties can maintain a consistent view of the state of the transparency log.

It is worth repeating: This is not based on a tested legal theory. It is not legal advice. It is a best effort, good faith attempt to engineer a solution that would adhere to the “spirit of the law” as interpreted by an American furry with no academic or legal credentials from any country.

That being said, page 75 of this report about distributed ledgers and GDPR implies it’s not an entirely unfounded hypothesis.

Frequently Asked Questions

I’ve been asked a lot of similar questions since I started this project. This is a good a place as any to answer some of them.

Have you talked with ____?

Short answer: No, I haven’t.

Longer answer: My goal is simply to build a specification, then an implementation, that allows end-to-end encryption on the Fediverse.

No part of that sentence implies getting anyone else’s permission, or compromising on my security decisions in order to meet a competing concern.

For example, there’s always pressure from the open source community to support RSA keys, or to interoperate with other software (i.e., Matrix).

Those are non-goals of mine.

Should the ActivityPub authors or Mastodon developers decide differently from me, I wouldn’t want to sign off on their protocol design just because it appeases someone else.

I also don’t have any sort of requirement that what I specify and build becomes “standardized” in any meaningful way.

So, no, I haven’t talked with any of them yet. I also don’t plan to until the specifications and reference implementations are closer to maturity.

And even then, the message I have in mind for when that time comes looks something like this:

Hiya,

I’m building my own end-to-end encryption design for the Fediverse. Here’s the specification, here’s a reference implementation. (Links go here.)

[If applicable: I see you accepted a grant to build something similar.]

Please feel free to reuse whatever you deem useful (if anything) of my work in your own designs. I’m not interested in changing mine.

If you’d like to just adopt what I’ve already built, that’s fine too.

Soatok

I don’t want a deep involvement in anyone else’s political or social mess. I don’t want any of their grant money either, for that matter.

I just want to make security and privacy possible, to help queer people decide when, where, and how they selectively reveal themselves to others.

That said, if the W3C grant recipients want to look at the work I’m doing, they can consider it licensed under public domain, ISC, CC0, WTFPL, or whatever license is easiest for their lawyers to digest. I literally do not give a shit about intellectual property with this project. Go wild.

What if no one steps up to build client software?

Then, as a last resort, I will build something myself. Most likely, a browser extension.

It will probably be ugly, but lightweight, as I am deathly allergic to React Native, NextJS, and other front-end development frameworks.

How can I contribute?

The GitHub repository for the Public Key Directory spec is located here, if you’d like to read and/or suggest improvements to the specification.

As mentioned in my previous blog post on this topic, there is a Signal group for meta-discussion. If you are interested in writing code, that would be the best place to hang out.

What about money? Although my Ko-Fi isn’t difficult to locate, nor hard to guess, I’m not soliciting any financial contributions for this project. It isn’t costing me anything to design or build, presently.

If you represent a company that focuses on cryptography development or software assurance consulting, I may be interested in talking at some point about getting the designs reviewed and implementations audited by professionals. However, we’re a long way from that right now.

Do you have a timeline in mind?

Somewhat, yeah.

I’d like to have version 0.1 of the specification tagged by the end of September 2024.

If I have the time to stick to that timeline, I intend to start working on the reference implementation and client SDKs in a few languages. This is when software developers’ contributions will begin to be the most welcomed.

I can’t really project a timeline beyond that, today.

In addition to building a reference implementation, I would like to pursue formal verification for my protocol design. This allows us to be confident in the correctness and security of the protocol as specified. I cannot provide even a rough estimate for how long that will take to complete.

Once this Public Key Directory project is in a good place, however, my focus will be shifting back towards specifying end-to-end encryption for the Fediverse. Because that’s why I’m doing all this in the first place.

AJ

https://soatok.blog/2024/08/21/federated-key-transparency-project-update/

#crypto #cryptography #OnlinePrivacy #symmetricCryptography

Dhole Moments

2024-06-06 05:37:50

In late 2022, I blogged about the work needed to develop a specification for end-to-end encryption for the fediverse. I sketched out some of the key management components on GitHub, and then the public work abruptly stalled.

A few of you have wondered what’s the deal with that.

This post covers why this effort stalled, what I’m proposing we do next.

What’s The Hold Up?

The “easy” (relatively speaking) parts of the problem are as follows:

1. Secret key management. (This is sketched out already, and provides multiple mechanisms for managing secret key material. Yay!)
2. Bulk encryption of messages and media. (I’ve done a lot of work in this space over the years, so it’s an area I’m deeply familiar with. When we get to this part, it will be almost trivial. I’m not worried about it at all.)
3. Forward-secure ratcheting / authenticated key exchange / group key agreement. (RFC 9420 is a great starting point.)

That is to say, managing secret keys, using secret keys, and deriving shared secret keys are all in the “easy” bucket.

The hard part? Public key management.

CMYKat made this

Why is Public Key Management Hard?

In a centralized service (think: Twitter, Facebook, etc.), this is actually much easier to build: Shove your public keys into a database, and design your client-side software to trust whatever public key your server gives them. Bob’s your uncle, pack it up and go home.

Unfortunately, it’s kind of stupid to build anything that way.

If you explicitly trust the server, the server could provide the wrong public key (i.e., one for which the server knows the corresponding secret key) and you’ll be none the wiser. This makes it trivial for the server to intercept and read your messages.

If your users are trusting you regardless, they’re probably just as happy if you don’t encrypt at the endpoint at all (beyond using TLS, but transport encryption is table stakes for any online service so nevermind that).

But let’s say you wanted to encrypt between peers anyway, because you’re feeling generous (or don’t want to field a bunch of questionably legal demands for user data by law enforcement; a.k.a. the Snapchat threat model).

You could improve endpoint trust by shoving all of your users’ public keys into an append-only data structure; i.e. key transparency, like WhatsApp proposed in 2023:

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

And, to be perfectly clear, key transparency is a damn good idea.

Key transparency keeps everyone honest and makes it difficult for criminals to secretly replace a victim’s public key, because the act of doing so is unavoidably published to an append-only log.

The primary challenge is scaling a transparency feature to serve a public, federated system.

AJ

Federated Key Transparency?

Despite appearances, I haven’t been sitting on my thumbs for the past year or so. I’ve been talking with cryptography experts about their projects and papers in the same space.

Truthfully, I had been hoping to piggyback off one of those upcoming projects (which is focused more on public key discovery for SAML- and OAuth-like protocols) to build the Federated PKI piece for E2EE for the Fediverse.

Unfortunately, that project keeps getting delayed and pushed back, and I’ve just about run out of patience for it.

Additionally, there are some engineering challenges that I would need to tackle to build atop it, so it’s not as simple as “let’s just use that protocol”, either.

So let’s do something else instead:

Art: ScruffKerfluff

Fediverse Public Key Directories

Orthogonal to the overall Fediverse E2EE specification project, let’s build a Public Key Directory for the Fediverse.

This will not only be useful for building a coherent specification for E2EE (as it provides the “Federated PKI” component we’d need to build it securely), but it would also be extremely useful for software developers the whole world over.

Imagine this:

• If you want to fetch a user’s SSH public key, you can just query for their username and get a list of non-expired, non-revoked public keys to choose from.
• If you wanted public key pinning and key rotation for OAuth2 and/or OpenID Connect identity providers without having to update configurations or re-deploy any applications, you can do that.
• If you want to encrypt a message to a complete stranger, such that only they can decrypt it, without any sort of interaction (i.e., they could be offline for a holiday and still decrypt it when they get back), you could do that.

Oh, and best of all? You can get all these wins without propping up any cryptocurrency bullshit either.

From simple abstractions, great power may bloom.

Mark Miller

How Will This Work?

We need to design a specific kind of server that speaks a limited set of the ActivityPub protocol.

I say “limited” because it will only not support editing or deleting messages provided by another instance. It will only append data.

To understand the full picture, let’s first look at the message types, public key types, and how the message types will be interpreted.

Message Types

Under the ActivityPub layer, we will need to specify a distinct set of Directory Message Types. An opening offer would look like this:

1. [b]AddKey[/b] — contains an Asymmetric Public Key, a number mapped to the user, and instance that hosts it, and some other metadata (i.e., time)
2. [b]RevokeKey[/b] — marks an existing public key as revoked
3. [b]MoveIdentity[/b] — moves all of the public keys from identity A to identity B. This can be used for username changes or instance migrations.

We may choose to allow more message types at the front-end if need be, but that’s enough for our purposes.

Public Key Types

We are not interested in backwards compatibility with every existing cryptosystem. We will only tolerate a limited set of public key types.

At the outset, only Ed25519 will be supported.

In the future, we will include post-quantum digital signature algorithms on this list, but not before the current designs have had time to mature.

RSA will never be included in the set.

ECDSA over NIST P-384 may be included at some point, if there’s sufficient interest in supporting e.g., US government users.

If ECDSA is ever allowed, RFC 6979 is mandatory.

Message Processing

When an instance sends a message to a Directory Server, it will need to contain a specific marker for our protocol. Otherwise, it will be rejected.

Each message will have its own processing rules.

After the processing rules are applied, the message will be stored in the Directory Server, and a hash of the message will be published to a SigSum transparency ledger. The Merkle root and inclusion proofs will be stored in an associated record, attached to the record for the new message.

Every message will have its hash published in SigSum. No exceptions.

We will also need a mechanism for witness co-signatures to be published and attached to the record.

Additionally, all messages defined here are generated by the users, client-side. Servers are not trusted, generally, as part of the overall E2EE threat model.

AddKey

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "AddKey", "message": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfMessage"}

The first AddKey for any given identity will need to be self-signed by the key being added (in addition to ActivityPub messages being signed by the instance).

After an identity exists in the directory, every subsequent public key MUST be signed by a non-revoked keypair.

RevokeKey

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "RevokeKey", "message": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfMessage"}

This marks the public key as untrusted, and effectively “deletes” it from the list that users will fetch.

Important: RevokeKey will fail unless there is at least one more trusted public key for this user. Otherwise, a denial of service would be possible.

Replaying an AddKey for a previously-revoked key MUST fail.

MoveIdentity

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "MoveIdentity", "message": { "time": "2024-12-31T23:59:59Z", "old-identity": "foo@mastodon.example.com", "new-identity": "bar@akko.example.net" }, "signature": "SignatureOfMessage"}

This exists to facilitate migrations and username changes.

Other Message Types

The above list is not exhaustive. We may need other message types depending on the exact feature set needed by the final specification.

Fetching Public Keys

A simple JSON API (and/or an ActivityStream; haven’t decided) will be exposed to query for the currently trusted public keys for a given identity.

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "public-keys": [ { "data": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfData", "sigsum": { /* ... */ }, }, { "data": { /* ... */ }, /* ... */ }, /* ... */ ]}

Simple and easy.

CMYKat

Gossip Between Instances

Directory Servers should be configurable to mirror records from other instances.

Additionally, they should be configurable to serve as Witnesses for the SigSum protocol.

The communication layer here between Directory Servers will also be ActivityPub.

Preventing Abuse

The capability of learning a user’s public key doesn’t imply the ability to send messages or bypass their block list.

Additionally, Fediverse account usernames are (to my knowledge) generally not private, so I don’t anticipate there being any danger in publishing public keys to an append-only ledger.

That said, I am totally open to considering use cases where the actual identity is obfuscated (e.g., HMAC with a static key known only to the instance that hosts them instead of raw usernames).

What About GDPR / Right To Be Forgotten?

Others have previously suggested that usernames might be subject to the “right to be forgotten”, which would require breaking history for an append-only ledger.

After discussing a proposed workaround with a few people in the Signal group for this project, we realized complying necessarily introduced security issues by giving instance admins the capability of selectively remapping the user ID to different audiences, and detecting/mitigating this remapping is annoying.

However, we don’t need to do that in the first place.

According to this webpage about GDPR’s Right to be Forgotten:

However, an organization’s right to process someone’s data might override their right to be forgotten. Here are the reasons cited in the GDPR that trump the right to erasure:

• (…)
• The data is being used to perform a task that is being carried out in the public interest or when exercising an organization’s official authority.
• (…)
• The data represents important information that serves the public interest, scientific research, historical research, or statistical purposes and where erasure of the data would likely to impair or halt progress towards the achievement that was the goal of the processing.

Enabling private communication is in the public interest. The only information that will be stored in the ledger in relation to the username are cryptographic public keys, so it’s not like anything personal (e.g., email addresses or legal names) will be included.

However, we still need to be extremely up-front about this to ensure EU citizens are aware of the trade-off we’re making.

Account Recovery

In the event that a user loses access to all of their secret keys and wants to burn down the old account, they may want a way to start over with another fresh self-signed AddKey.

However, the existing policies I wrote above would make this challenging:

1. Since every subsequent AddKey must be signed by an incumbent key, if you don’t have access to these secret keys, you’re locked out.
2. Since RevokeKey requires one trusted keypair remains in the set, for normal operations, you can’t just burn the set down to zero even while you still had access to the secret keys.

There is an easy way out of this mess: Create a new verb; e.g. BurnDown that an instance can issue that resets all signing keys for a given identity.

The use of BurnDown should be a rare, exceptional event that makes a lot of noise:

• All existing E2EE sessions must break, loudly.
• All other participants must be alerted to the change, through the client software.
• Witnesses and watchdog nodes must take note of this change.

This comes with some trade-offs. Namely: Any account recovery mechanism is a backdoor, and giving the instance operators the capability of issuing BurnDown messages is a risk to their users.

Therefore, users who trust their own security posture and wish to opt out of this recovery feature should also be able to issue a Fireproof message at any point in the process, which permanent and irrevocably prevents any BurnDown from being accepted on their current instance.

If users opt out of recovery and then lose their signing keys, they’re locked out and need to start over with a new Fediverse identity. On the flipside, their instance operator cannot successfully issue a BurnDown for them, so they have to trust them less.

Notice

This is just a rough sketch of my initial ideas, going into this project. It is not comprehensive, nor complete.

There are probably big gaps that need to be filled in, esp. on the ActivityPub side of things. (I’m not as worried about the cryptography side of things.)

How Will This Be Used for E2EE Direct Messaging?

I anticipate that a small pool of Directory Servers will be necessary, due to only public keys and identities being stored.

Additional changes beyond just the existence of Directory Servers will need to be made to facilitate private messaging. Some of those changes include:

• Some endpoint for users to know which Directory Servers a given ActivityPub instance federates with (if any).
• Some mechanism for users to asynchronously exchange Signed Pre-Key bundles for initiating contact. (One for users to publish new bundles, another for users to retrieve a bundle.)
  
  • These will be Ed25519-signed payloads containing an ephemeral X25519 public key.

  
  

This is all outside the scope of the proposal I’m sketching out here today, but it’s worth knowing that I’m aware of the implementation complexity.

The important thing is: I (soatok@furry.engineer) should be able to query pawb.fun, find the Directory Server(s) they federate with, and then query that Directory server for Crashdoom@pawb.fun and get his currently trusted Ed25519 public keys.

From there, I can query pawb.fun for a SignedPreKey bundle, which will have been signed by one of those public keys.

And then we can return to the “easy” pile.

MarleyTanuki

Development Plan

Okay, so that was a lot of detail, and yet not enough detail, depending on who’s reading this blog post.

What I wrote here today is a very rough sketch. The devil is always in the details, especially with cryptography.

Goals and Non-Goals

We want Fediverse users to be able to publish a public key that is bound to their identity, which anyone else on the Internet can fetch and then use for various purposes.

We want to leverage the existing work into key transparency by the cryptography community.

We don’t want to focus on algorithm agility or protocol compatibility.

We don’t want to involve any government offices in the process. We don’t care about “real” identities, nor about codifying falsehoods about names.

We don’t want any X.509 or Web-of-Trust machinery involved in the process.

Tasks

The first thing we would need to do is write a formal specification for a Directory Server (whose job is only to vend Public Keys in an auditable, transparent manner).

Next, we need to actually build a reference implementation of this server, test it thoroughly, and then have security experts pound at the implementation for a while. Any security issues that can be mitigated by design will require a specification update.

We will NOT punt these down to implementors to be responsible for, unless we cannot avoid doing so.

Once these steps are done, we can start rolling the Directory Servers out. At this point, we can develop client-side libraries in various programming languages to make it easy for developers to adopt.

My continued work on the E2EE specification for the Fediverse can begin after we have an implementation of the Directory Server component ready to go.

Timeline

I have a very demanding couple of months ahead of me, professionally, so I don’t yet know when I can commit to starting the Fediverse Directory Server specification work.

Strictly speaking, it’s vaguely possible to get buy-in from work to focus on this project as part of my day-to-day responsibilities, since it has immediate and lasting value to the Internet.

However, I don’t want to propose it because that would be crossing the professional-personal streams in a way I’m not really comfortable with.

The last thing I need is angry Internet trolls harassing my coworkers to try to get under my fur, y’know?

If there is enough interest from the broader Fediverse community, I’m also happy to delegate this work to anyone interested.

Once the work can begin, I don’t anticipate it will take more than a week for me to write a specification that other crypto nerds will take seriously.

I am confident in this because most of the cryptography will be constrained to hash functions, preventing canonicalization and cross-protocol attacks, and signatures.

Y’know, the sort of thing I write about on my furry blog for fun!

Building a reference implementation will likely take a bit longer; if, for no other reason, than I believe it would be best to write it in Go (which has the strongest SigSum support, as of this writing).

This is a lot of words to say, as far as timelines go:

CMYKat

How to Get Involved

Regardless of whether my overall E2EE proposal gets adopted, the Directory Server component is something that should be universally useful to the Fediverse and to software developers around the world.

If you are interested in participating in any technical capacity, I have just created a Signal Group for discussing and coordinating efforts.

All of these efforts will also be coordinated on the fedi-e2ee GitHub organization.

The public key directory server’s specification will eventually exist in this GitHub repository.

Can I Contribute Non-Technically?

Yes, absolutely. In the immediate future, once it kicks off, the work is going to be technology-oriented.

However, we may need people with non-technical skills at some point, so feel free to dive in whenever you feel comfortable.

What About Financially?

If you really have money burning a hole in your pocket and want to toss a coin my way, I do have a Ko-Fi. Do not feel pressured at all to do so, however.

Because I only use Ko-Fi as a tip jar, rather than as a business, I’m not specifically tracking which transaction is tied to which project, so I can’t make any specific promises about how any of the money sent my way will be allocated.

What I will promise, however, is that any icons/logos/etc. created for this work will be done by an artist and they will be adequately compensated for their work. I will not use large-scale computing (a.k.a., “Generative AI”) for anything.

Closing Thoughts

What I’ve sketched here is much simpler (and more ActivityPub-centric) than the collaboration I was originally planning.

Thanks for being patient while I tried, in vain, to make that work.

As of today, I no longer think we need to wait for them. We can build this ourselves, for each other.

https://soatok.blog/2024/06/06/towards-federated-key-transparency/

#cryptography #endToEndEncryption #fediverse #KeyTransparency #Mastodon #MerkleTrees #PublicKeys

If you’re new to reading this blog, you might not already be aware of my efforts to develop end-to-end encryption for ActivityPub-based software. It’s worth being aware of before you continue to read this blog post.

To be very, very clear, this is work I’m doing independent of the W3C or any other standards organization and/or funding source (and they have their own ideas about how to approach it).

Really, I’m doing my own thing and releasing my designs under a public domain-equivalent license so anyone (including the W3C grant awardees) can pick it up and use it, if they see fit.

But the work I’m doing has no official standing and is not representative of anyone (except maybe a lot of other furries interested in technology). They have, emphatically, never endorsed anything I’m doing. I have not talked with any of them about my ideas, nor has my name come up in any of their meeting notes.

My background is in applied cryptography and software security assessments, so I have strong opinions about how such software should be developed.

I’m being very up-front about this because I don’t want anyone to mistake my ideas for anything “official”.

Why spend your time on that?

My end goal is pretty straightforward.

Before Musk took it over, Twitter was wonderful for queer people. I’ve even heard it described as the most successful dating platform for the LGBTQIA+ community.

These days, it’s full of Nazis and people who think the ideal version of “free speech” means not being allowed to say the word “cisgender.” But I repeat myself.

The typical threat model for Twitter was: You have to trust the person you’re talking with, and the Twitter corporation, to keep your conversations (or nudes, if we’re being frank about it) private.

With the Fediverse, things are a little more complicated. Instance operators also have access to the plaintext versions of any Direct Messages between you and other participants.

And maybe you trust your instance operator… but do you trust your friends’? And do they trust yours?

If implemented securely, end-to-end encryption saves you from having to care about this injection of additional threat actors to consider.

If not implemented securely, it’s little more than security theater and should be ridiculed loudly.

So it’s natural and obvious for a person with my particular interests and skills to want to solve this problem.

Technological Decisions

When I started this project, I separated the end goal into 4 separate components:

1. Client-side secret key management.
2. Federated public-key infrastructure.
3. Shared key agreement for group messaging.
4. The actual bulk encryption techniques.

A lot of hobbyist projects over-index on the fourth component, rather than the actual hard problems. This is why so many doomed projects start with PGP, or implement weird “cipher cascades” to hedge against AES getting broken.

In reality, every component matters for the security of the whole system, but the bulk encryption is boring. It’s the well-tread path of any cryptosystem. The significantly harder parts are key management.

Political Decisions

Let’s not mince words: How you implement key management is inherently a political decision.

If that sounds counter-intuitive, meditate on this bit of wisdom for a while:

Repeat after me: all technical problems of sufficient scope or impact are actually political problems first.

Eleanor Saitta

Many projects, when confronted with the complexity of key management, are perfectly happy with “just write private keys to disk” or “put blind trust in AWS KMS.”

Or, more directly: “YOLO.”

With my Fediverse E2EE project, I wanted to minimize the amount of trust you have to place in others. (Especially, minimize the trust needed in Soatok!)

How Decisions Flow

Client-side secrets are the most visible area of risk to end users. Backing up and managing their own credentials, recovering from failure modes, the Mud Puddle test, etc.

Once each participant has secret keys managed (1), they can provide public keys to each other.

Public-key infrastructure (2) is how you decide trust relationships between parties. We’re operating in a federated environment, and want to minimize the amount of unchecked “authority” anyone has, so that complicates matters. But, if it wasn’t challenging, it would already be solved.

Once you’ve figured out a trust mechanism to tie a public key to an identity, you can try to agree on a shared symmetric key securely, even over an untrusted channel.

Key agreement for group messaging (3) is how you decide which shared key to use, and when, and who has access to this key and for how long.

And from there, you can actually encrypt shit (4).

It doesn’t really matter how much you boil the ocean on mitigating hypothetical weaknesses in AES if an adversary can muck with your key management.

Thus, it should hopefully be reasonable to divide the work up in this fashion.

But there is a fifth component; one that I am not qualified to comment on:

User experience.

The final deliverable for my participation in this project will be software libraries (and any necessary patches to server software) to facilitate secure end-to-end encryption between Fediverse users.

As for what that experience looks like? How it’s presented visually? What accessibility features are used, and how? How elements are organized and in what order they are displayed? Any quality-of-life design decisions that delight users and avoid dark patterns?

Yeah, sorry, I’m totally out of my depth here. That’s not my domain.

I will do my damnedest to not make security decisions that are inherently onerous towards making usable software.

(After all, security at the cost of usability comes at the cost of security.)

But I can’t promise that the experience will be totally seamless for everyone, all the time.

Lacking Ambition?

One of the things that’s been bothering me, as I work on out the finer details about this end-to-end encryption project, is that it seems to lack ambition.

Sure, I can talk your ear off for hours about the ins and outs of implementing end-to-end encryption securely, but we already have end-to-end encryption apps. So many private messengers.

How does “you can now have encrypted DMs in Mastodon” help people who can already use Signal or WhatsApp? Why should the people who aren’t computer nerds care about it at all?

What’s actually new or exciting about this work?

CMYKat

And, honestly, the best answer I can come up with is that it’s the first step.

Tech Freedom and You

Before the Big Data and cloud computing crazes took the technology industry by storm (or any of the messes that followed), most software was designed to work offline. That is, without Internet access.

With the growing ubiquity of Internet access (and mobile networks), the Overton window shifted towards always-on devices, edge computing, and no longer owning anything. Instead, consumers rent licenses to software that a third party can revoke on a whim.

The Free Software movement, for all of the very pronounced personality quirks associated with it today, foresaw this problem long before the modern Internet existed. Technologists, lawyers, and activists spent thousands of person-years of effort on trying to protect end users’ rights from greedy monopolies.

Kyume
(I couldn’t not include this meme in this section.)

This isn’t a modern problem, by any stretch of the imagination.

Every year, our rights and digital freedoms are eroded by court decisions by corrupt judges, terrible legislature, and questionable leadership.

But the Electronic Frontier Foundation and its friends in other nations have been talking about this and fighting court battles since the 1990s.

Even if I somehow made some small innovation that benefited end users with allowing Fediverse users to message each other privately, that’s not really ambitious either.

From Sparks to Embers

As I was noodling over this, a friend of mine linked me to an article titled Rust Needs a Web Framework for Lazy Developers the other day.

It made me realize how much I miss the era when software was offline-first, even if it had online components. The past several years of Live Service Games has exhausted my tolerance more than anything else, but they’re not alone.

When I initially delineated my proposal into 4 components, my goal was to simplify the security analysis and make the threat models digestible.

But it occurred to me, recently, that by abstracting these components (especially the Federated Public Key Infrastructure design), a new era of cypherpunks and pirates could breathe new ambition into software projects that build atop the boring infrastructure I’m building.

Let’s Turn the Ambition Up To 11

Imagine peer-to-peer software that uses the Fediverse and/or onion routing technologies (similar to Tor) to establish peer-to-peer encrypted data tunnels between devices, with the Federated PKI as the source of truth for identity public keys so you always know you’re talking to the correct entity.

Now combine that with developer tools that make it easy for people to self-publish software (even if only through Tor Hidden Services), with an optional way to create a public portal (e.g., for a public-facing website).

You could even create a protocol for people with rack space and spare bandwidth to host said public portals, without biasing for a particular one.

This would allow technologists to build the tools for normal people to create an anti-corporate, decentralized network.

And you could do it without ever mentioning the word “blockchain” (though you may need to tolerate it if you want to prevent anti-porn groups like Exodus Cry from having any say in what we compute).

Finally, imagine that we build all of this in memory-safe languages.

Are you building this today?

In short: No, I’m not.

Ambitious ideas and cryptography should only intersect rarely. I’m focused on the cryptography.

Instead, I wanted to lay this rough sketch out there as a possibility that someone else–presumably more ambitious, charismatic, and/or resourceful–could easily pick up if they so choose.

More importantly, all of the hard parts of this would be solved problems by the time I finish with the end-to-end encryption project. (Most of them already exist, in fact!)

That’s what I meant above by “it’s the first step”.

Along the way to achieving my own goals, I’m building at least one useful building block. What the rest of the technology industry decides to do with it is up to the rest of us.

I can’t, and will not try, to do it alone.

There is a lot of potential for tech freedom that could benefit users beyond what they can get from the Fediverse today. I wanted to examine how some of these ideas could be useful for–

Rejected! What else you got?

Oh.

…

Okay, so y’know how a lot of video games (Undertale/Deltarune, Doki Doki Literature Club) try to make a highly immersive experience with many diegetic elements?

Let’s build an operating system, based on some flavor of Linux, that is in and of itself a game. People can write their own DLC by developing packages for that OS. The end deliverable will be a virtual machine, and in order to get it to work on Steam, we would install Docker or Kubernetes, but users will also be able to install it via VirtualBox.

Inevitably, someone will decide this OS is their new daily driver. Imagine the impact this would have on corporate IT the whole world over.

This is the worst idea in the history of bad ideas!

Oh, I can do worse. I can do so much worse.

I don’t know if I can top the various attempts to build a Message Authentication Code out of the insecure RC4 stream cipher, of course.

If you want ambition, you sacrifice wisdom.

If you want freedom, you sacrifice convenience.

If you want security, you sacrifice usability.

…

Or do you?

Harubaki

They Can’t All Be Winners

I have a lot of bad ideas, all the time. That’s the only reason I ever occasionally have moderately good ones.

My process of eliminating bad ideas is ruthless, and may cull some interesting or fun ones along the way. This is an unfortunate side-effect of being an effective security engineer.

I don’t actually think the ideas I’ve written above are that bad. I wrote them this way for comedic effect.

Rather, I’m just not actually sure they’re actually good, or worthwhile to invest time into.

CMYKat

Whether someone could build atop the work I’m doing to reclaim our Internet from the grip of massive technology corporations is, at best, difficult to classify.

I do not have the time, energy, or motivation to do the work already on my own plate and then explore these ideas fully.

Maybe someone reading this does?

If not, that’s cool. Ideas are allowed to just exist as idle curiosities. Not everything has to matter all the time.

The “ship a whole god damn OS as an indie
game” idea could be fun though.

https://soatok.blog/2024/10/12/ambition-the-fediverse-and-technology-freedom/

#endToEndEncryption #fediverse #FreeSoftware #OnlinePrivacy #Society #SoftwareFreedom #TechFreedom #Technology

Dhole Moments

2024-09-13 10:25:12

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

In 2015, a subreddit called /r/The_Donald was created. This has made a lot of people very angry and widely been regarded as a bad move.

Roughly 5 years after its inception, the Reddit staff banned /r/The_Donald because it was a cesspool of hateful content and harmful conspiracy theories. You can learn more about it here.

Why are we talking about this in 2021?

Well, a lot has happened in the first week of the new year. A lot of words have been written about the fascist insurrection that attempted a coup on the U.S. legislature, so I won’t belabor the point more than I have to.

But as it turns out: The shitty people who ran /r/The_Donald didn’t leave well enough alone when they got shit-canned.

Remember: You can’t recycle fash.
(Art by Khia.)

Instead, they spun up a Reddit clone under the domain thedonald.win and hid it behind CloudFlare.

Even worse: Without Reddit rules to keep them in check, they’ve gone all in on political violence and terrorism.

(Content Warning: Fascism, political violence, and a myriad of other nastiness in the Twitter thread below.)

https://twitter.com/Viking_Sec/status/1347758893976457217

If you remember last year, I published a blog post about identifying the real server IP address from email headers. This is far from a sophisticated technique, but if simple solutions work, why not use them?

(Related, I wrote a post in 2020 about more effectively deplatforming hate and harassment. This knowledge will come in handy if you find yourself needing to stop the spread of political violence, but is strictly speaking not relevant to the techniques discussed on this page.)

Unmasking TheDonald.win

The technique I outlined in my previous post doesn’t work on their Reddit clone software: Although it asks you for an (optional) email address at the time of account registration, it never actually emails you, and there is no account recovery feature (a.k.a. “I forgot my password”).

Foiled immediately! What’s a furry to do?
(Art by Khia.)

However, their software is still a Reddit clone!

Reddit has this feature where you can submit links and it will helpfully fetch the page title for you. It looks like this:

When I paste a URL into this form, it automatically fetches the title.

How this feature works is simple: They initiate an HTTP request server-side to fetch the web page, parse out the title tag, and return it.

So what happens if you control the server that their request is being routed to, and provide a unique URL?

Leaking TheDonald.win’s true IP address from behind CloudFlare.

Well, that was easy! To eliminate false positives, I performed all of this sampling with Tor Browser and manually rebuilt the Tor Circuit multiple times, and always got the same IP address: 167.114.145.140.

An Even Lazier Technique

Just use Shodan, lol

https://twitter.com/_rarecoil/status/1347768188017143808

Apparently chuds are really bad at OpSec, and their IP was exposed on Shodan this whole time.

You can’t help but laugh at their incompetence.
(Art by Khia.)

The Road to Accountability

Okay, so we have their real IP address. What can we do with it?

The easiest thing to do is find out who’s hosting their servers, with a simple WHOIS lookup on their IP address.

Hosted by OVH Canada, eh? After all, nothing screams “Proud American” like hosting your website with a French company in a Canadian datacenter.

Dunking on these fools for the inconsistencies in their worldview is self-care and I recommend it, even though I know they don’t care one iota about hypocrisy.

I immediately wondered if their ISP was aware they were hosting right-wing terrorists, so I filed an innocent abuse report with details about how I obtained their IP address and the kind of behavior they’re engaging in. Canada’s laws about hate speech and inciting violence are comparably strict, after all.

I’ll update this post later if OVH decides to take action.

Lessons to Learn

First, don’t tolerate violent political extremists, or you’ll end up with political violence on your hands. Deplatforming works.

https://twitter.com/witchiebunny/status/1347624481318166528

Second, and most important: Online privacy is hard. Hard enough that bigots, terrorists, and seditious insurrectionists can’t do it right.

This bears emphasizing: None of the techniques I’ve shared on the history of my blog are particularly clever or novel. But they work extremely well, and they’re useful for exposing shitty people.

Remember: Sunlight is the best disinfectant.

Conversely: Basic OSINT isn’t hard; merely tedious.

Other Techniques (from Twitter)

Subdomain leaks (via @z3dster):

https://twitter.com/z3dster/status/1347807318478639106

Exploiting CloudFlare workers (via @4dwins):

https://twitter.com/4dwins/status/1347809701291937792

DNS enumeration (via @JoshFarwell):

https://twitter.com/JoshFarwell/status/1347840751720304641

If the site in question is running WordPress, you can use Pingbacks to get WordPress to cough up the server IP address. If you aren’t sure if something runs WordPress, here’s the lazy way to detect that: view any page’s source code and see if the string /wp-content shows up in any URLs (especially for CSS). If it’s found, you’re probably dealing with WordPress.

Gab’s (another platform favored by right-wing extremists) IP address discovered through their Image Proxy feature to be 216.66.0.222 (via @kubeworm):

https://twitter.com/kubeworm/status/1348162193523675136

The Alt-Right Notices this Blog Post

Shortly after I posted this online, some users from thedonald.win noticed this blog post and hilarity ensued.

https://twitter.com/SoatokDhole/status/1348204577154326528

I want to make something clear in case anyone (especially members of toxic Trump-supporting communities) is confused:

What’s published on this page isn’t doxing, nor do I have any interest in doxing people. That’s the job of law enforcement, not furry bloggers who sometimes write about computer topics. And law enforcement definitely doesn’t need my help: When you create an account, you must solve a ReCAPTCHA challenge, which sends an HTTP request directly to Google servers–which means law enforcement could just subpoena Google for the IP address of the server, even if the above leaks were all patched.

This also isn’t the sort of thing I’d ever brag about, since the entire point I’ve been making is what I’ve done here isn’t technically challenging. If I wanted to /flex, I’d just talk more about my work on constant-time algorithm implementations.

If, in response to my abuse report, OVH Canada determines that their website isn’t violating OVH’s terms of service, then y’all have nothing to worry about.

But given the amount of rampant hate speech being hosted in Canadian jurisdiction, I wouldn’t make that bet.

Addendum (2021-01-19)

Additionally, this wasn’t as simple as running a WHOIS search on thedonald.win either, since that only coughs up the CloudFlare IP addresses. I went a step further and got the real IP address of the server behind CloudFlare, not just CloudFlare’s IP.

This isn’t rocket science, folks.

According to CBC Canada, they moved off OVH Canada the same day this blog post went live. I’m willing to bet a simple WHOIS query won’t yield their current, non-CloudFlare IP address. (To wit: If you think the steps taken in this blog post are so unimpressive to warrant mockery, why not discover the non-CloudFlare IP for yourselves? I’ll bet you can’t.)

There are a lot of ways to deflect criticism for your system administrators’ mistakes, but being overly reductionist and claiming I “just” ran a WHOIS query (which, as stated above, wouldn’t work because of CloudFlare) is only hurting your users by instilling in them a false sense of security.

Just admit it: You fucked up, and got outfoxed by a random furry blogger, and then moved hosting providers after patching the IP leak. How hard is that?

Also, if anyone from CloudFlare is reading this: You should really dump your violent extremist customers before they hurt more people. I’m a strong proponent of freedom of speech–especially for sex workers, the most censored group online–but they’re actively spreading hate and planning violent attacks like the Capitol Hill Riot of January 6, 2021. Pull the damn plug, man.

Finally, I highly recommend Innuendo Studios’ series, The Alt-Right Playbook, for anyone who’s trying to make sense of the surge in right-wing violence we’ve been seeing in America for the past few years.

How Do You Know This IP Wasn’t Bait?

After I published this article, the developers of their software hobbled the Get Suggested Title feature of their software, and the system administrators cancelled their OVH hosting account and moved to another ISP. (Source.)

You can independently verify that their software is hobbled: Try to fetch the page title for a random news website, or Wikipedia article, with the developer console open. It will stall for a while then return an empty string instead of the page title.

They also changed their domain name to patriots.win.

If the IP address I’d found was bait, why would they break a core piece of their software’s functionality and then hurriedly migrate their server elsewhere?

The very notion doesn’t stand up to common sense, let alone greater scrutiny. The whole point of bait is to catch people making a mistake–presumably so you can mock them while remaining totally unaffected–not so you can do these things in a hurry.

A much more likely story: Anyone who makes this claim is trying to downplay a mistake and save face.

Header art by Kyume

https://soatok.blog/2021/01/09/masks-off-for-thedonald-win/

#cloudflare #deanonymize #hateSpeech #OnlinePrivacy #Technology

Dhole Moments

2020-05-09 22:31:37

Update (2021-01-09): There’s a newer blog post that covers different CloudFlare deanonymization techniques (with a real world case study).

---

Furry Twitter is currently abuzz about a new site selling knock-off fursuits and illegally using photos from the owners of the actual fursuits without permission.

The website in question.

Understandably, the photographers and fursuiters whose work was ripped off by this website are upset and would like to exercise their legal recourse (i.e. DMCA takedown emails) of the scam site, but there’s a wrinkle:

Their contact info isn’t in DNS and their website is hosted behind CloudFlare.

CloudFlare.
Private DNS registration.

You might think this is a show-stopper, but I’m going to show you how to get their server’s real IP address in one easy step.

Ordering the Server’s IP Address by Mail

Most knock-off site operators will choose open source eCommerce platforms like Magento, WooCommerce, and OpenCart, which usually have a mechanism for customers to register for an account and login.

Usually this mechanism sends you an email when you authenticate.

(If it doesn’t, logout and use the “reset password” feature, which will almost certainly send you an email.)

Once you have an email from the scam site, you’re going to need to view the email headers.

With Gmail, can click the three dots on the right of an email then click “Show original”.

Account registration email.
Full email headers after clicking “Show original”.

And there you have it. The IP address of the server behind CloudFlare delivered piping hot to your inbox in 30 minutes or less, or your money back.

That’s a fairer deal than any of these knock-off fursuit sites will give you.

Black magic and piss-poor opsec.

What Can We Do With The Server IP?

You can identify who hosts their website. (In this case, it’s a company called Net Minders.)

With this knowledge in mind, you can send an email to their web hosting provider, citing the Digital Millennium Copyright Act.

One or two emails might get ignored, but discarding hundreds of distinct complaint emails from different people is bad for business. This (along with similar abuse complaints to the domain registrar, which isn’t obscured by DNS Privacy) should be enough to shut down these illicit websites.
The more you know!

Epilogue

https://twitter.com/Mochiroo/status/1259289385876373504

The technique is simple, effective, and portable. Use it whenever someone tries to prop up another website to peddle knock-off goods and tries to hide behind CloudFlare.

https://soatok.blog/2020/05/09/how-to-de-anonymize-scam-knock-off-sites-hiding-behind-cloudflare/

#cloudflare #deanonymize #DNS #fursuitScamSites #informationSecurity #OnlinePrivacy #opsec

Update (2021-01-09): There’s a newer blog post that covers different CloudFlare deanonymization techniques (with a real world case study).

Furry Twitter is currently abuzz about a new site selling knock-off fursuits and illegally using photos from the owners of the actual fursuits without permission.

The website in question.

Understandably, the photographers and fursuiters whose work was ripped off by this website are upset and would like to exercise their legal recourse (i.e. DMCA takedown emails) of the scam site, but there’s a wrinkle:

Their contact info isn’t in DNS and their website is hosted behind CloudFlare.

CloudFlare.
Private DNS registration.

You might think this is a show-stopper, but I’m going to show you how to get their server’s real IP address in one easy step.

Ordering the Server’s IP Address by Mail

Most knock-off site operators will choose open source eCommerce platforms like Magento, WooCommerce, and OpenCart, which usually have a mechanism for customers to register for an account and login.

Usually this mechanism sends you an email when you authenticate.

(If it doesn’t, logout and use the “reset password” feature, which will almost certainly send you an email.)

Once you have an email from the scam site, you’re going to need to view the email headers.

With Gmail, can click the three dots on the right of an email then click “Show original”.

Account registration email.
Full email headers after clicking “Show original”.

And there you have it. The IP address of the server behind CloudFlare delivered piping hot to your inbox in 30 minutes or less, or your money back.

That’s a fairer deal than any of these knock-off fursuit sites will give you.

Black magic and piss-poor opsec.

What Can We Do With The Server IP?

You can identify who hosts their website. (In this case, it’s a company called Net Minders.)

With this knowledge in mind, you can send an email to their web hosting provider, citing the Digital Millennium Copyright Act.

One or two emails might get ignored, but discarding hundreds of distinct complaint emails from different people is bad for business. This (along with similar abuse complaints to the domain registrar, which isn’t obscured by DNS Privacy) should be enough to shut down these illicit websites.
The more you know!

Epilogue

https://twitter.com/Mochiroo/status/1259289385876373504

The technique is simple, effective, and portable. Use it whenever someone tries to prop up another website to peddle knock-off goods and tries to hide behind CloudFlare.

https://soatok.blog/2020/05/09/how-to-de-anonymize-scam-knock-off-sites-hiding-behind-cloudflare/

#cloudflare #deanonymize #DNS #fursuitScamSites #informationSecurity #OnlinePrivacy #opsec

Dhole Moments

2021-01-09 12:59:50

In 2015, a subreddit called /r/The_Donald was created. This has made a lot of people very angry and widely been regarded as a bad move.

Roughly 5 years after its inception, the Reddit staff banned /r/The_Donald because it was a cesspool of hateful content and harmful conspiracy theories. You can learn more about it here.

Why are we talking about this in 2021?

Well, a lot has happened in the first week of the new year. A lot of words have been written about the fascist insurrection that attempted a coup on the U.S. legislature, so I won’t belabor the point more than I have to.

But as it turns out: The shitty people who ran /r/The_Donald didn’t leave well enough alone when they got shit-canned.

Remember: You can’t recycle fash.
(Art by Khia.)

Instead, they spun up a Reddit clone under the domain thedonald.win and hid it behind CloudFlare.

Even worse: Without Reddit rules to keep them in check, they’ve gone all in on political violence and terrorism.

(Content Warning: Fascism, political violence, and a myriad of other nastiness in the Twitter thread below.)

https://twitter.com/Viking_Sec/status/1347758893976457217

If you remember last year, I published a blog post about identifying the real server IP address from email headers. This is far from a sophisticated technique, but if simple solutions work, why not use them?

(Related, I wrote a post in 2020 about more effectively deplatforming hate and harassment. This knowledge will come in handy if you find yourself needing to stop the spread of political violence, but is strictly speaking not relevant to the techniques discussed on this page.)

Unmasking TheDonald.win

The technique I outlined in my previous post doesn’t work on their Reddit clone software: Although it asks you for an (optional) email address at the time of account registration, it never actually emails you, and there is no account recovery feature (a.k.a. “I forgot my password”).

Foiled immediately! What’s a furry to do?
(Art by Khia.)

However, their software is still a Reddit clone!

Reddit has this feature where you can submit links and it will helpfully fetch the page title for you. It looks like this:

When I paste a URL into this form, it automatically fetches the title.

How this feature works is simple: They initiate an HTTP request server-side to fetch the web page, parse out the title tag, and return it.

So what happens if you control the server that their request is being routed to, and provide a unique URL?

Leaking TheDonald.win’s true IP address from behind CloudFlare.

Well, that was easy! To eliminate false positives, I performed all of this sampling with Tor Browser and manually rebuilt the Tor Circuit multiple times, and always got the same IP address: 167.114.145.140.

An Even Lazier Technique

Just use Shodan, lol

https://twitter.com/_rarecoil/status/1347768188017143808

Apparently chuds are really bad at OpSec, and their IP was exposed on Shodan this whole time.

You can’t help but laugh at their incompetence.
(Art by Khia.)

The Road to Accountability

Okay, so we have their real IP address. What can we do with it?

The easiest thing to do is find out who’s hosting their servers, with a simple WHOIS lookup on their IP address.

Hosted by OVH Canada, eh? After all, nothing screams “Proud American” like hosting your website with a French company in a Canadian datacenter.

Dunking on these fools for the inconsistencies in their worldview is self-care and I recommend it, even though I know they don’t care one iota about hypocrisy.

I immediately wondered if their ISP was aware they were hosting right-wing terrorists, so I filed an innocent abuse report with details about how I obtained their IP address and the kind of behavior they’re engaging in. Canada’s laws about hate speech and inciting violence are comparably strict, after all.

I’ll update this post later if OVH decides to take action.

Lessons to Learn

First, don’t tolerate violent political extremists, or you’ll end up with political violence on your hands. Deplatforming works.

https://twitter.com/witchiebunny/status/1347624481318166528

Second, and most important: Online privacy is hard. Hard enough that bigots, terrorists, and seditious insurrectionists can’t do it right.

This bears emphasizing: None of the techniques I’ve shared on the history of my blog are particularly clever or novel. But they work extremely well, and they’re useful for exposing shitty people.

Remember: Sunlight is the best disinfectant.

Conversely: Basic OSINT isn’t hard; merely tedious.

Other Techniques (from Twitter)

Subdomain leaks (via @z3dster):

https://twitter.com/z3dster/status/1347807318478639106

Exploiting CloudFlare workers (via @4dwins):

https://twitter.com/4dwins/status/1347809701291937792

DNS enumeration (via @JoshFarwell):

https://twitter.com/JoshFarwell/status/1347840751720304641

If the site in question is running WordPress, you can use Pingbacks to get WordPress to cough up the server IP address. If you aren’t sure if something runs WordPress, here’s the lazy way to detect that: view any page’s source code and see if the string /wp-content shows up in any URLs (especially for CSS). If it’s found, you’re probably dealing with WordPress.

Gab’s (another platform favored by right-wing extremists) IP address discovered through their Image Proxy feature to be 216.66.0.222 (via @kubeworm):

https://twitter.com/kubeworm/status/1348162193523675136

The Alt-Right Notices this Blog Post

Shortly after I posted this online, some users from thedonald.win noticed this blog post and hilarity ensued.

https://twitter.com/SoatokDhole/status/1348204577154326528

I want to make something clear in case anyone (especially members of toxic Trump-supporting communities) is confused:

What’s published on this page isn’t doxing, nor do I have any interest in doxing people. That’s the job of law enforcement, not furry bloggers who sometimes write about computer topics. And law enforcement definitely doesn’t need my help: When you create an account, you must solve a ReCAPTCHA challenge, which sends an HTTP request directly to Google servers–which means law enforcement could just subpoena Google for the IP address of the server, even if the above leaks were all patched.

This also isn’t the sort of thing I’d ever brag about, since the entire point I’ve been making is what I’ve done here isn’t technically challenging. If I wanted to /flex, I’d just talk more about my work on constant-time algorithm implementations.

If, in response to my abuse report, OVH Canada determines that their website isn’t violating OVH’s terms of service, then y’all have nothing to worry about.

But given the amount of rampant hate speech being hosted in Canadian jurisdiction, I wouldn’t make that bet.

Addendum (2021-01-19)

Additionally, this wasn’t as simple as running a WHOIS search on thedonald.win either, since that only coughs up the CloudFlare IP addresses. I went a step further and got the real IP address of the server behind CloudFlare, not just CloudFlare’s IP.

This isn’t rocket science, folks.

According to CBC Canada, they moved off OVH Canada the same day this blog post went live. I’m willing to bet a simple WHOIS query won’t yield their current, non-CloudFlare IP address. (To wit: If you think the steps taken in this blog post are so unimpressive to warrant mockery, why not discover the non-CloudFlare IP for yourselves? I’ll bet you can’t.)

There are a lot of ways to deflect criticism for your system administrators’ mistakes, but being overly reductionist and claiming I “just” ran a WHOIS query (which, as stated above, wouldn’t work because of CloudFlare) is only hurting your users by instilling in them a false sense of security.

Just admit it: You fucked up, and got outfoxed by a random furry blogger, and then moved hosting providers after patching the IP leak. How hard is that?

Also, if anyone from CloudFlare is reading this: You should really dump your violent extremist customers before they hurt more people. I’m a strong proponent of freedom of speech–especially for sex workers, the most censored group online–but they’re actively spreading hate and planning violent attacks like the Capitol Hill Riot of January 6, 2021. Pull the damn plug, man.

Finally, I highly recommend Innuendo Studios’ series, The Alt-Right Playbook, for anyone who’s trying to make sense of the surge in right-wing violence we’ve been seeing in America for the past few years.

How Do You Know This IP Wasn’t Bait?

After I published this article, the developers of their software hobbled the Get Suggested Title feature of their software, and the system administrators cancelled their OVH hosting account and moved to another ISP. (Source.)

You can independently verify that their software is hobbled: Try to fetch the page title for a random news website, or Wikipedia article, with the developer console open. It will stall for a while then return an empty string instead of the page title.

They also changed their domain name to patriots.win.

If the IP address I’d found was bait, why would they break a core piece of their software’s functionality and then hurriedly migrate their server elsewhere?

The very notion doesn’t stand up to common sense, let alone greater scrutiny. The whole point of bait is to catch people making a mistake–presumably so you can mock them while remaining totally unaffected–not so you can do these things in a hurry.

A much more likely story: Anyone who makes this claim is trying to downplay a mistake and save face.

---

Header art by Kyume

https://soatok.blog/2021/01/09/masks-off-for-thedonald-win/

#cloudflare #deanonymize #hateSpeech #OnlinePrivacy #Technology

(If you aren’t interested in the background information, feel free to skip to the meat of this post. If you’re in a hurry, there’s a summary of results at the end.)

Around this time last year, I was writing Going Bark: A Furry’s Guide to End-to-End Encryption and the accompanying TypeScript implementation of the Extended 3-Way Diffie-Hellman authenticated key exchange (Rawr X3DH). In that blog post, I had said:

The goal of [writing] this is to increase the amount of end-to-end encryption deployed on the Internet that the service operator cannot decrypt (even if compelled by court order) and make E2EE normalized. The goal is NOT to compete with highly specialized and peer-reviewed privacy technology.

This effort had come on the heels of my analysis of bizarre choices in Zoom’s end-to-end encryption, and a brief foray into the discussion into the concept of cryptographic deniability.

I’m stating all this up-front because I want to re-emphasize that end-to-end encryption is important, and I don’t want to discourage the development of E2EE. Don’t let a critical post about someone else’s product discourage you from encrypting your users’ data.

Art: Swizz

Until recently, but especially at the time I wrote all of that, Threema had not been on my radar at all, for one simple reason: Until December 2020, Threema was not open source software.

In spite of this, Threema boasts over 1 million installs on the Google Play Store.

Partly as a result of being closed source for so long, but mostly the Threema team’s history of over-emphasizing the legal jurisdiction they operate from (Switzerland) in their claims about privacy and security, most of the cryptography experts I know had quietly put Threema in the “clown-shoes cryptography” bucket and moved on with their lives. After all, if your end-to-end encryption is well implemented and your engineers prioritized privacy with metadata collection, jurisdiction shouldn’t matter.

What changed for me was, recently, a well-meaning Twitter user mentioned Threema in response to a discussion about Signal.

https://twitter.com/KeijiCase/status/1455669171618914308

In response, I had casually glanced through their source code and pointed out a few obvious WTFs in the Twitter thread. I had planned on following up by conducting a thorough analysis of their code and reporting my findings to them privately (which is called coordinated disclosure, not “responsible disclosure”).

But then I read this bit of FUD on their Messenger Comparison page.

Signal requires users to disclose personally identifiable information. Threema, on the other hand, can be used anonymously: Users don’t have to provide their phone number or email address. The fact that Signal, being a US-based IT service provider, is subject to the CLOUD Act only makes this privacy deficit worse.

Threema – Messenger Comparison

Art: LvJ

Thus, because of their deliberate misinformation (something I’ve opposed for years), Threema has been disqualified from any such courtesy. They will see this blog post, and its contents, once it’s public and not a moment sooner.

How Are Threema’s Claims FUD?

Threema’s FUD comparison against Signal.

The quoted paragraph is deceptive, and was apparently designed to make their prospective customers distrustful of Signal.

The CLOUD Act isn’t black magic; it can only force Signal to turn over the data they actually possess. Which is, as demonstrated by a consistent paper trail of court records, almost nothing.

As usual, we couldn’t provide any of that. It’s impossible to turn over data that we never had access to in the first place. Signal doesn’t have access to your messages; your chat list; your groups; your contacts; your stickers; your profile name or avatar; or even the GIFs you search for. As a result, our response to the subpoena will look familiar. It’s the same set of “Account and Subscriber Information” that we can provide: Unix timestamps for when each account was created and the date that each account last connected to the Signal service.

That’s it.

The Signal blog

Additionally, their claim that “Threema […] can be used anonymously” is, at best, a significant stretch. At worst, they’re lying by omission.

Sure, it’s possible to purchase Threema with cryptocurrency rather than using the Google Play Store. And if you assume cryptocurrency is private (n.b., the blockchain is more like tweeting all your financial transactions, unless you use something like Zcash), that probably sounds like a sweet deal.

However, even if you skip the Google Play Store, you’re constantly beaconing a device identifier to their server (which is stored on your device) whenever a license key check is initiated.

Bear in mind, over 1 million of their installed base is through the Google Play Store. This means that, in practice, almost nobody actually takes advantage of this “possibility” of anonymity.

Additionally, their own whitepaper discusses the collection of users’ phone number and email addresses. Specifically, they store hashes (really HMAC with a static, publicly known key for domain separation, but they treat it as a hash) of identifiers (mobile numbers, email addresses) on their server.

Circling back to the possibility of anonymity issue: When it comes to security (and especially cryptography), the defaults matter a lot. That’s why well-written cryptographic tools prioritize both correctness and misuse resistance over shipping new features. The default configuration is the only configuration for all but your most savvy users, because it’s the path of least resistance. Trying to take credit for the mere existence of an alternate route (bypassing the Google Play Store, paying with cryptocurrency) that few people take is dishonest, and anyone in the cryptography space should know better. It’s fine to offer that option, but not fine to emphasize it in marketing.

The only correct criticism of Signal contained within their “comparison” is that, as of this writing, they still require a phone number to bootstrap an account. The phone number requirement makes it difficult for people to have multiple independent, compartmentalized identities; i.e. preventing your professional identity from intersecting with your personal identity–which is especially not great for LGBTQIA+ folks that aren’t out to their families (usually for valid safety reasons).

This obviously sucks, but fails to justify the other claims Threema made.

With all that out of the way, let’s look at Threema’s cryptography protocol and some of their software implementations.

Art: LvJ

Threema Issues and Design Flaws

To be up front: Some of the issues and design flaws discussed below are not security vulnerabilities. Some of them are.

Where possible, I’ve included a severity rating atop each section if I believe it’s a real vulnerability, and omitted this severity rating where I believe it is not. Ultimately, a lot of what’s written here is my opinion, and you’re free to disagree with it.

List of Issues and Vulnerabilities Discovered in Threema

• Issues With Threema’s Cryptographic Protocols
  
  1. No Forward Security
  2. Threema IDs Aren’t Scalable
  3. Peer Fingerprints Aren’t Collision-Resistant
  4. No Breadcrumb for Cryptography Migrations
  5. Inconsistency with Cryptographic Randomness
  6. Invisible Salamanders with Group Messaging

  
  

• Issues With Threema Android (Repository)
  
  1. Weak Encryption With Master Key (LocalCrypto)
  2. File Encryption Uses Unauthenticated CBC Mode
  3. Cache-Timing Leaks with Hex-Encoding (JNaCl)

  
  

• Issues With Threema Web (Repository)
  
  1. Insecure Password-Based Key Derivation

  
  

Issues With Threema’s Cryptography Protocols

This first discussion is about weaknesses in Threema’s cryptography protocol, irrespective of the underlying implementation.

At its core, Threema uses similar cryptography to Tox. This means that they’re using some version of NaCl (the library that libsodium is based on) in every implementation.

This would normally be a boring (n.b. obviously secure) choice, but the security bar for private messaging apps is very high–especially for a Signal competitor.

It isn’t sufficient for a secure messenger competing with Signal to just use NaCl. You also have to build well-designed protocols atop the APIs that NaCl gives you.

No Forward Secrecy

The goal of end-to-end encryption is to protect users from the service provider. Any security property guaranteed by transport-layer cryptography (i.e. HTTPS) are therefore irrelevant, since the cryptography is terminated on the server rather than your peer’s device.

The Threema team claims to provide forward secrecy, but only on the network connection.

Forward secrecy: Threema provides forward secrecy on the network connection (not on the end-to-end layer).

What makes Threema secure?

This is how Threema admits a weakness in their construction. “We offer it at a different [but irrelevant] layer.”

That’s not how any of this works.
Art: LvJ

Their whitepaper acknowledges this deficit.

As I’ve demonstrated previously, it’s not difficult to implement Signal’s X3DH AKE (which offers forward secrecy) using libsodium. Most of what I’ve done there can be done with NaCl (basically use SHA512 instead of BLAKE2b and you’re golden).

The X3DH handshake is essentially multiple Curve25519 ECDH handshakes (one long-term, one short-term e.g. biweekly, one totally ephemeral), which are mixed together using a secure key derivation function (i.e. HKDF).

To the state of the art for secure messaging that Threema claims, Forward Secrecy is table stakes. Threema’s end-to-end encryption completely lacks this property (and transport-layer doesn’t count). No amount of hand-waving on their part can make this not a weakness in Threema.

The specification for X3DH has been public for 5 years. My proof-of-concept TypeScript implementation that builds atop libsodium is nearly a year old.

If the Threema team wanted to fix this, it would not be hard for them to do so. Building a usable messaging app is much harder than building X3DH on top of a well-studied Curve25519 implementation.

Threema IDs Aren’t Scalable

Severity: Low
Impact: Denial of Service

Threema IDs are 8-digit alphanumeric unique identifiers, chosen randomly, that serve as a pseudonymous mapping to an asymmetric keypair.

This means there are possible Threema IDs (2.8 trillion). This is approximately , so we can say there’s about a 41-bit keyspace.

That may seem like a large number (more than 100,000 the human population), but they’re chosen randomly. Which means: The birthday problem rears its ugly head.

Threema will begin to experience collisions (with 50% probability) after (roughly 1.7 million) Threema IDs have been reserved.

At first, this won’t be a problem: If you collide with someone else’s Threema ID, you just have to generate another one. That’s just an extra round-trip for the Threema server to say “LOL NO try again”. In fact, given the Google Play Store estimates for the number of Threema installs, they’re probably in excess of the birthday bound today.

Quick aside: One known problem with Threema IDs is that users don’t know they’re supposed to back them up, so when they switch phones, they lose access to their old IDs and secret keys. Aside from the obvious social engineering risk that emerges from habitually tolerating new Threema IDs for all contacts (“I lost my old Threema ID, again, so blindly trust that it’s me and not a scammer”), there’s a bigger problem.

Since Threema IDs are used by each app to identify peers, it’s not possible for Threema to recycle expired IDs. In order to do so, Threema would need to be able to inspect the social graph to determine which Threema IDs can be freed, which would be a huge privacy violation and go against their marketing.

So what happens if someone maliciously reserve-then-discards billions of Threema IDs?

Due to the pigeonhole principle, this will eventually lead to an address space exhaustion and prevent more Threema users from being onboarded. However, trouble will begin before it gets this far: At a certain point, legitimate users’ attempts to register a new Threema ID will result in an unreasonable number of contentions with reserved IDs.

Neither the Threema website nor their whitepaper discusses how Threema can cope with this sort of network strain.

Art: LvJ

This problem could have been prevented if the Threema designers were more cognizant of the birthday bound.

Additionally, the fact that Threema IDs are generated server-side is not sufficient to mitigate this risk. As long as IDs are never recycled unless explicitly deleted by their owner, they will inevitably run head-first into this problem.

Peer Fingerprints Aren’t Collision-Resistant

Severity: Informational
Impact: None

From the Threema whitepaper:

Truncating a SHA-256 hash to 128 bits doesn’t give you 128 bits of security against collision attacks. It gives you 64 bits of security, which is about the same security that SHA-1 gives you against collision attacks.

This is, once again, attributable to the birthday bound problem that affects Threema IDs.

Art: Swizz

Related: I also find it interesting that they only hash the Curve25519 public key and not the combination of public key and Threema ID. The latter construction would frustrate batch attacks by committing both the public key (which is random and somewhat opaque to users) and the Threema ID (which users see and interact with) to a given fingerprint:

• Finding a collision against a 128-bit probability space, where the input is a public key, can be leveraged against any user.
• Finding a collision against a 128-bit probability space, where the input is a public key and a given Threema ID, can only be leveraged against a targeted user (i.e. that Threema ID).

Both situations still suck because of the 128-bit truncation, but Threema managed to choose the worse of two options, and opened the door to a multi-user attack.

Impact of the Peer Fingerprint Bypass

To begin with, let’s assume the attacker has compromised all of the Threema servers and is interested in attacking the security of the end-to-end encryption. (Assuming the server is evil is table stakes for the minimum threat model for any end-to-end encrypted messaging app.)

Imagine a situation with Alice, Bob, and Dave.

Alice pushes her Threema ID and public key to the server (A_id, A_pk), then chats with Bob legitimately (B_id, B_pk). Bob suggests that Alice talks to his drug dealer, Dave (D_id, D_pk).

The attacker can obtain knowledge of everyone’s public keys, and begin precomputing fingerprint collisions for any participants in the network. Their first collision will occur after keypairs are generated (with 50% probability), and then collisions will only become more frequent.

What happens when an attacker finds fingerprint collisions for people that are close on the social graph?

When Alice goes to talk with Dave, the attacker replaces her public key with one that collides with her fingerprint, but whose secret key is known to the attacker (M_pk1). The attacker does the same thing in the opposite direction (D_id, M_pk2).

When Alice, Bob, and Dave compare their fingerprints, they will think nothing is amiss. In reality, an attacker can silently intercept Alice’s private conversation with Dave.

The full range of key exchanges looks like this:

Alice -> Bob: (A_id, A_pk) Alice -> Dave: (A_id, M_pk1) Bob -> Alice: (B_id, B_pk) Bob -> Dave: (B_id, D_pk) Dave -> Bob: (D_id, D_pk) Dave -> Alice: (D_id, M_pk2) SHA256-128(A_pk) == SHA256-128(M_pk1), A_pk != M_pk1 SHA256-128(D_pk) == SHA256-128(M_pk2), D_pk != M_pk2

Alice will encrypt messages against M_pk2, rather than D_pk. But the fingerprints will match for both. Dave will respond by encrypting messages against M_pk1, instead of A_pk. The attacker can sit in the middle and re-encrypt messages on behalf of the recipient. Even if both Alice and Dave compare the fingerprints they see with what Bob sees, nobody will detect anything.

(Bob’s communications remain unaffected since he already downloaded everyone’s public keys. This only affects new conversations.)

This is why you only need a collision attack to violate the security of the peer fingerprint, and not a preimage attack.

To be clear, a targeted attack is much more expensive (roughly several trillion times the cost of a general attack; versus ).

This is a certificational weakness, and I’m only including it as further evidence of poor cryptographic engineering by Threema’s team rather than an overt vulnerability.

Update (2021-11-08): Remember, this is a list of issues I discovered, not specifically a list of vulnerabilities. People trying to argue in the comments, or my inbox, about whether this is “really” a vulnerability is getting a little tiring; hence, this reminder.

How to Fix Threema’s Fingerprints

First, you need to include both the Threema ID and curve25519 public key in the calculation. This will frustrate batch attacks. If they were to switch to something like X3DH, using the long-term identity key for fingerprints would also be reasonable.

Next, calculate a winder margin of truncation. here’s a handy formula to use: where is the expected population of users. If you set equal to , you end up with a fingerprint that truncates to 168 bits, rather than 128 bits.

This formula yields a probability space with a birthday bound of for collisions, and a preimage cost of (even with a trillion Threema IDs reserved), which plainly isn’t going to ever happen.

No Breadcrumb for Cryptography Migrations

Severity: Informational
Impact: Frustration of Engineering Efforts

There is no concept of versioning anywhere in Threema’s protocols or designs, which means that one day migrating to better cryptography, without introducing the risk of downgrade attacks, simply isn’t possible.

The lack of any cryptography migration breadcrumb also prevents Threema from effectively mitigating security weaknesses inherent to their protocols and designs. You’ll see why this is a problem when we start looking at the implementations.

Cryptography migrations are difficult in general, because:

1. Secure cryptography is not backwards compatible with insecure cryptography.
2. In any distributed system, if you upgrade writers to a new cryptography protocol before your readers are upgraded too, you’ll cause availability issues.

The asynchronous nature of mobile messaging apps makes this even more challenging.

Inconsistency with Cryptographic Randomness

Severity: None
Impact: Annoyed Cryptography Auditors

Threema commits the same sin as most PGP implementations in misunderstanding the difference between /dev/random and /dev/urandom on Linux.

See also: Myths about /dev/urandom and How to Safely Generate a Random Number. From the latter:

Doesn’t the man page say to use /dev/random?

You should ignore the man page. Don’t use /dev/random. The distinction between /dev/random and /dev/urandom is a Unix design wart. The man page doesn’t want to admit that, so it invents a security concern that doesn’t really exist. Consider the cryptographic advice in random(4) an urban legend and get on with your life.

Emphasis mine.

If you use /dev/random instead of urandom, your program will unpredictably (or, if you’re an attacker, very predictably) hang when Linux gets confused about how its own RNG works. Using /dev/random will make your programs less stable, but it won’t make them any more cryptographically safe.

Emphasis not mine.

This is an easy fix (/dev/random -> /dev/urandom), but it signals that the whitepaper’s author lacks awareness of cryptographic best practices.

And it turns out, they actually use /dev/urandom in their code. So this is just an inconsistency and an annoyance rather than a flaw.

Source: UNDERTALE

Update (2021-11-08): Yes, I’m aware that the Linux RNG changed in 5.6 to make /dev/random behave the way it always should have.

However, Linux 5.6 is extremely unlikely to help anyone affected by the old Android SecureRandom bug that Threema has implied as part of their threat model when they called it out in their Cryptography Whitepaper, so I didn’t originally deem it fit to mention.

Invisible Salamanders with Group Messaging

Severity: Medium
Impact: Covert channel through media messages due to multi-key attacks

Note: This was discovered after the initial blog post was published and added later the same day.

Threema doesn’t do anything special (e.g. TreeKEM) for Group Messaging. Instead, groups are handled by the client and messages are encrypted directly to all parties.

This provides no group messaging authentication whatsoever. A user with a malicious Threema client can trivially join a group then send different messages to different recipients.

Imagine a group of five stock traders (A, B, C, D, E). User A posts a message to the group such that B, C, and D see “HOLD” but user E sees “SELL”.

An attacker can have some real fun with that, and it’s probably the easiest attack to pull off that I’ll discuss in this post.

User E won’t have much recourse, either: Users B, C, and D will all see a different message than User E, and will think E is dishonest. Even if User E provides a screenshot, the rest of the users will trust their own experiences with their “private messaging app” and assume User E is spinning yarns to discredit User A. It would then be very easy for A to gaslight E. This is the sort of attack that us LGBTQIA+ folks and furries are often, sadly, all too familiar with (usually from our families).

Additionally, there’s an invisible salamanders attack with media files.

Invisible Salamanders is an attack technique in systems where traditional, fast AEAD modes are employed, but more than one key can be selected. The security modes of most AEAD modes assumed one fixed symmetric encryption key held by both parties in their security designs.

To exploit the Invisible Salamanders attack:

1. Generate two (or more) Xsalsa20-Poly1305 keys that will encrypt different media files to a given ciphertext + tag.
2. Send a different key to a different subset of group participants.

Both parties will download the same encrypted file, but will see a different plaintext. Threema cannot detect this attack server-side to mitigate impact, either.

Art: LvJ

Encrypting multiple plaintexts, each under a different key, that produce an identical ciphertext and authentication tag is possible with AES-GCM, AES-GCM-SIV, and even Xsalsa20-Poly1305 (NaCl secretbox, which is what Threema uses).

Preventing this kind of misuse was never a security goal of these modes, and is generally not recognized as a vulnerability in the algorithms. (It would only qualify as a vulnerability if the algorithm designers stated an assumption that this violated.) However, Invisible Salamanders absolutely is a vulnerability in the protocols that build atop the algorithms. Thus, it qualifies as a vulnerability in Threema.

Here’s a Black Hat talk by Paul Grubbs explaining how the Invisible Salamanders technique works in general:

https://www.youtube.com/watch?v=3M1jIO-jLHI

This isn’t a problem for i.e. Signal, because the Double Ratchet algorithm keeps the key synchronized for all group members. Each ciphertext is signed by the sender, but encrypted with a Double Ratchet key. There’s no opportunity to convince one partition of the Group to use a different key to decrypt a message. See also: Sesame for multi-device.

The reason the vulnerability exists is that Poly1305, GMAC, etc. are fast symmetric-key message authentication algorithms, but they are not collision-resistant hash functions (e.g. SHA-256).

When you use a collision-resistant hash function, instead of a polynomial evaluation MAC, you’re getting a property called message commitment. If you use a hash function over the encryption key (and, hopefully, some domain-separation constant)–or a key the encryption key is deterministically derived from–you obtain a property called key commitment.

In either case, you can claim your AEAD mode is also random-key robust. This turns out to be true of AES-CBC + HMAC-SHA2 (what Signal uses), due to HMAC-SHA2.

Art: Scruff

Invisible Salamanders Mitigation with NaCl

First, you’ll need to split the random per-media-file key into two keys:

1. A derived encryption key, which will take the place of what is currently the only key.
2. A derived authentication key, which will be used with crypto_auth and crypto_auth_verify to commit the ciphertext + tag.

It’s important that both keys are derived from the same input key, and that the key derivation relies on a strong pseudorandom function.

Pseudocode:

function encryptMediaV2(data: Buffer, fileKey: Buffer) { const encKey = HmacSha256('File Encryption Key', fileKey); const authKey = HmacSha256('Media Integrity Key', fileKey); const encrypted = NaCl.crypto_secretbox(data, nonce, encKey); const commitment = NaCl.crypto_auth(encrypted, authKey); return Buffer.concat([commitment, encrypted]);}function decryptMediaV2(downloaded: Buffer, fileKey: Buffer) { const tag = downloaded.slice(0, 32); const ciphertext = downloaded.slice(32); const authKey = HmacSha256('Media Integrity Key', fileKey); if (!NaCl.crypto_auth_verify(tag, ciphertext, authKey)) { throw new Exception("bad"); } const encKey = HmacSha256('File Encryption Key', fileKey); return NaCl.crypto_secretbox_open(ciphertext, nonce, encKey);}

This code does two things:

1. It derives two keys instead of only using the one. You could also just use a SHA512 hash, and then dedicate the left half to encryption and the right half to authentication. Both are fine.
2. It uses the second key (not for encryption) to commit the ciphertext (encrypted file). This provides both message- and key-encryption.

If you didn’t care about message-commitment, and only cared about key-commitment, you could just skip the crypto_auth entirely and just publish the authKey as a public commitment hash of the key.

This corresponds to Type I in the Key Committing AEADs paper (section 3.1), if you’re trying to build a security proof.

Of course, the migration story for encrypted media in Threema is going to be challenging even if they implement my suggestion.

Issues With Threema Android

Weak Encryption with Master Key (LocalCrypto)

Severity: Low/High
Impact: Weak KDF with Crib (default) / Loss of Confidentiality (no passphrase)

The on-device protection of your Master Key (which also protects your Curve25519 secret key) consists of the following:

1. A hard-coded obfuscation key (950d267a88ea77109c50e73f47e06972dac4397c99ea7e67affddd32da35f70c), which is XORed with the file’s contents.
2. (Optional) If the user sets a passphrase, calculate the PBKDF2-SHA1 of their passphrase (with only 10,000 iterations) and XOR the master key with this output.

If the user opts to not use a passphrase, if their phone is ever seized from a government agency, it might as well be stored as plaintext.

Art: LvJ

To be charitable, maybe that kind of attack is outside of their (unpublished) threat model.

Even if a user elects to store a passphrase, the low iteration count of PBKDF2 will allow for sophisticated adversaries to be able to launch offline attacks against the encrypted key file.

The 4-byte SHA1 verification checksum of the plaintext master key gives cracking code a crib for likely successful attempts (which, for weak passphrases, will almost certainly mean “you found the right key”). This is somehow worse than a typical textbook MAC-and-Encrypt design.

The checksum-as-crib is even more powerful if you’ve sent the target a photo before attempting a device seizure: Just keep trying to crack the Master Key then, after each time the checksum passes, decrypt the photo until you’ve successfully decrypted the known plaintext.

The verification checksum saves you from wasted decryption attempts; if the KDF output doesn’t produce a SHA1 hash that begins with the verification checksum, you can keep iterating until it does.

Once you’ve reproduced the file you sent in the first place, you also have their Curve25519 secret key, which means you can decrypt every message they’ve ever sent or received (especially if the Threema server operator colludes with their government).

Art: LvJ

Also, Array.equals() isn’t constant-time. Threema should know this by now thanks to their Cure53 audit finding other examples of it a year ago. It’s 2021, you can use MessageDigest.isEqual() for this.

Update: An Even Faster Attack Strategy

SHA1 can be expensive in a loop. A much faster technique is to do the XOR dance with the deobfuscated master key file, then see if you can decrypt the private_key file.

Because this file is AES-CBC encrypted using the Master Key, you can just verify that the decryption result ends in a valid padding block. Because Curve25519 secret keys are 32 bytes long, there should be a full 16-byte block of PKCS#7 padding bytes when you’ve guessed the correct key.

You can then use the 4-byte SHA-1 checksum and a scalarmult vs. the target’s public key to confirm you’ve guessed the correct password.

Thanks to @Sc00bzT for pointing this attack strategy out.

File Encryption Uses Unauthenticated CBC Mode

Severity: Low
Impact: Unauthenticated encryption (but local)

Threema’s MasterKey class has an API used elsewhere throughout the application that encrypts and decrypts files using AES/CBC/PKCS5Padding. This mode is widely known to be vulnerable to padding oracle attacks, and has a worse wear-out story than other AES modes.

Unlike the care taken with nonces for message encryption, Threema doesn’t bother trying to keep track of which IVs it has seen before, even though a CBC collision will happen much sooner than an Xsalsa20 collision. It also just uses SecureRandom despite the whitepaper claiming to avoid it due to weaknesses with that class on Android.

Additionally, there’s no domain separation or protection against type confusion in the methods that build atop this feature. They’re just AES-CBC-encrypted blobs that are decrypted and trusted to be the correct file format. So you can freely swap ciphertexts around and they’ll just get accepted in incorrect places.

Tangent: The Pure-Java NaCl implementation they use when JNI isn’t available also uses SecureRandom. If you’re going to include a narrative in your Cryptography Whitepaper, maybe check that you’re consistently adhering to it?

Cache-Timing Leaks with Hex-Encoding (JNaCl)

Severity: Low
Impact: Information disclosure through algorithm time

This isn’t a meaningfully practical risk, but it’s still disappointing to see in their pure-Java NaCl implementation. Briefly:

1. JNaCl definition for hex-encoding and decoding
2. OpenJDK definition for [url=https://github.com/openjdk/jdk/blob/739769c8fc4b496f08a92225a12d07414537b6c0/src/java.base/share/classes/java/lang/Character.java#L10660-L10662]Character.digit()[/url]
3. OpenJDK definition for [url=https://github.com/openjdk/jdk/blob/739769c8fc4b496f08a92225a12d07414537b6c0/make/data/characterdata/CharacterDataLatin1.java.template#L196]CharacterDataLatin1.digit()[/url]

Because this implementation uses table lookups, whenever a secret (plaintext or key) goes through one of the JNaCl hexadecimal functions, it will leak the contents of the secret through cache-timing.

For reference, here’s how libsodium implements hex-encoding and decoding.

Art: Swizz

Issues With Threema Web

I’m not going to spend a lot of time on the Threema Web project, since it’s been in maintenance-only mode since at least January.

Insecure Password-Based Key Derivation

Severity: High
Impact: Insecure cryptographic storage

While SHA512 is a good cryptographic hash function, it’s not a password hash function. Those aren’t the same thing.

Threema’s Web client derives the keystore encryption key from a password by using the leftmost 32 bytes of a SHA512 hash of the password.

/** * Convert a password string to a NaCl key. This is done by getting a * SHA512 hash and returning the first 32 bytes. */private pwToKey(password: string): Uint8Array { const bytes = this.stringToBytes(password); const hash = nacl.hash(bytes); return hash.slice(0, nacl.secretbox.keyLength);}

Once again, just because you’re using NaCl, doesn’t mean you’re using it well.

This code opens the door to dictionary attacks, rainbow tables, accelerated offline attacks, and all sorts of other nasty scenarios that would have been avoided if a password hashing algorithm was used instead of SHA512.

Also, this is another cache-timing leak in most JavaScript engines and the entire method that contains it could have been replaced by Uint8Array.from(password, 'utf-8').

Threema can’t claim they were avoiding the UInt8Array.from() method there because of compatibility concerns (e.g. with IE11) because they use it here.

Art: LvJ

Summary of Results

In the cryptography employed by Threema, I was able to quickly identify 5 6 issues, of which 2 3 directly negatively impact the security of their product (Threema IDs Aren’t Scalable can lead to address exhaustion and Denial-of-Service; Peer Fingerprints Aren’t Collision-Resistant allows moderately-funded adversaries to bypass fingerprint detection for a discount).

Both security issues in the Threema cryptography protocol were caused by a poor understanding of the birthday bound of a pseudorandom function–something that’s adequately covered by Dan Boneh’s Cryptography I course.

Additionally, the total lack of forward secrecy invalidates the Threema marketing claims of being more private or secure than Signal.

Update (3:45 PM): After initially publishing this, I realized there was a third security issue in the cryptography protocol, concerning Group Messaging: Invisible Salamanders.

In the Android app, I was able to identify 3 issues, of which 2 directly negatively impact the security of their product (Weak Encryption With Master Key (LocalCrypto) provides a very weak obfuscation or somewhat weak KDF (with a checksum) that, either way, makes leaking the key easier than it should be; File Encryption Uses Unauthenticated CBC Mode introduces all of the problems of CBC mode and unauthenticated encryption).

Finally, I only identified 1 security issue in the web client (Insecure Password-Based Key Derivation) before I saw the maintenance notice in the README on GitHub and decided it’s not worth my time to dive any deeper.

I did not study the iOS app at all. Who knows what dragons there be?

Art: LvJ

There were a few other issues that I thought existed, and later realized was false. For example: At first glance, it looked like they weren’t making sure received messages didn’t collide with an existing nonce (n.b. only on messages being sent)–which, since the same key is used in both directions, would be catastrophic. It turns out, they do store the nonces on received messages, so a very obvious attack isn’t possible.

The fact that Threema’s developers built atop NaCl probably prevented them from implementing higher-severity issues in their product. Given that Threema Web finding, I can’t help but ponder if they would have been better served by libsodium instead of NaCl.

Threema has been publicly audited (twice!) by vendors that they hired to perform code audits, and yet so many amateur cryptography mistakes persist in their designs and implementations years later. From their most recent audit:

Source

Cure53’s conclusion doesn’t jive with my observations. I don’t know if that says something about them, or something about me, or even something much more meta and existential about the nature of cryptographic work.

Art: Riley

Is Threema Vulnerable to Attack?

Unfortunately, yes. In only a few hours of review, I was able to identify 3 vulnerabilities in Threema’s cryptography, as well as 3 others affecting their Android and web apps.

How Severe Are These Issues?

While there are several fundamental flaws in Threema’s overall cryptography, they mostly put the service operators at risk and signal a lack of understanding of the basics of cryptography. (Namely: discrete probability and pseudorandom functions.)

The biggest and most immediate concern for Threema users is that a malicious user can send different media messages to different members of the same group, and no one can detect the deception. This is a much easier attack to pull off than anything else discussed above, and can directly be used to sew confusion and enable gaslighting.

For Threema Enterprise users, imagine someone posting a boring document in a group chat for work purposes, while also covertly leaking confidential and proprietary documents to someone that’s not supposed to have access to said documents. Even though you all see the same encrypted file, the version you decrypt is very different from what’s being fed to the leaker. Thus, Threema’s vulnerability offers a good way for insider threats to hide their espionage in plain sight.

The remaining issues discussed do not put anyone at risk, and are just uncomfortable design warts in Threema.

Recommendations for Threema Users

Basically, I don’t recommend Threema.

Art: LvJ

Most of what I shared here isn’t a game over vulnerability, provided you aren’t using Threema for group messaging, but my findings certainly debunk the claims made by Threema’s marketing copy.

If you are using Threema for group messaging–and especially for sharing files–you should be aware of the Invisible Salamanders attack discussed above.

When in doubt, just use Signal. It’s free, open source, private, and secure.

The reason you hear less about Signal on blogs like this is because, when people like me reviews their code, we don’t find these sorts of problems. I’ve tried to find problems before.

If you want a federated, desktop-first experience with your end-to-end encryption without a phone number, I don’t have any immediate replacement recommendations. Alternatives exist, but there’s no clear better option that’s production-ready today.

If you want all of the above and mobile support too, with Tor support as a first-class feature enabled by default, Open Privacy is developing Cwtch. It’s still beta software, though, and doesn’t support images or video yet. You also can’t install it through the Google Play Store (although that will probably change when they’re out of beta).

Looking forward, Signal recently announced the launch of anti-spam and spam-reporting features. This could indicate that the phone number requirement could be vanishing soon. (They already have a desktop client, after all.) If that happens, I implore everyone to ditch Threema immediately.

Disclosure Timeline

This is all zero-day. I did not notify Threema ahead of time with these findings.

Threema talks a big talk–calling themselves more private/secure than Signal and spreading FUD instead of an honest comparison.

If you’re going to engage in dishonest behavior, I’m going to treat you the same way I treat other charlatans. Especially when your dishonesty will deceive users into trusting an inferior product with their most sensitive and intimate conversations.

Threema also like to use the term “responsible disclosure” (which is a term mostly used by vendors to gaslight security researchers into thinking full disclosure is unethical) instead of the correct term (coordinated disclosure).

Additionally, in cryptography, immediate full disclosure is preferred over coordinated disclosure or non-disclosure. The responsibility of a security engineer is to protect the users, not the vendors, so in many cases, full disclosure is responsible disclosure.

https://twitter.com/ThreemaApp/status/1455960743002656776

That’s just a pet peeve of mine, though. Can we please dispense of this paleologism?

If you’re curious about the title, Threema’s three strikes were:

1. Arrogance (claiming to be more private than Signal)
2. Dishonesty (attempting to deceive their users about Signal’s privacy compared with Threema)
3. Making amateur mistakes in their custom cryptography designs (see: everything I wrote above this section)

https://soatok.blog/2021/11/05/threema-three-strikes-youre-out/

#cryptography #OnlinePrivacy #privacy #privateMessaging #symmetricCryptography #Threema #vuln #ZeroDay

Dhole Moments

2020-11-14 07:16:55

Governments are back on their anti-encryption bullshit again.

Between the U.S. Senate’s “EARN IT” Act, the E.U.’s slew of anti-encryption proposals, and Australia’s new anti-encryption law, it’s become clear that the authoritarians in office view online privacy as a threat to their existence.

Normally, when the governments increase their anti-privacy sabre-rattling, technologists start talking more loudly about Tor, Signal, and other privacy technologies (usually only to be drowned out by paranoid people who think Tor and Signal are government backdoors or something stupid; conspiracy theories ruin everything!).

I’m not going to do that.

Instead, I’m going to show you how to add end-to-end encryption to any communication software you’re developing. (Hopefully, I’ll avoid making any bizarre design decisions along the way.)

But first, some important disclaimers:

1. Yes, you should absolutely do this. I don’t care how banal your thing is; if you expect people to use it to communicate with each other, you should make it so that you can never decrypt their communications.
2. You should absolutely NOT bill the thing you’re developing as an alternative to Signal or WhatsApp.
3. The goal of doing this is to increase the amount of end-to-end encryption deployed on the Internet that the service operator cannot decrypt (even if compelled by court order) and make E2EE normalized. The goal is NOT to compete with highly specialized and peer-reviewed privacy technology.
4. I am not a lawyer, I’m some furry who works in cryptography. The contents of this blog post is not legal advice, nor is it endorsed by any company or organization. Ask the EFF for legal questions.

The organization of this blog post is as follows: First, I’ll explain how to encrypt and decrypt data between users, assuming you have a key. Next, I’ll explain how to build an authenticated key exchange and a ratcheting protocol to determine the keys used in the first step. Afterwards, I’ll explore techniques for binding authentication keys to identities and managing trust. Finally, I’ll discuss strategies for making it impractical to ever backdoor your software (and impossible to silently backdoor it), just to piss the creeps and tyrants of the world off even more.

You don’t have to implement the full stack of solutions to protect users, but the further you can afford to go, the safer your users will be from privacy-invasive policing.

(Art by Kyume.)

Preliminaries

Choosing a Cryptography Library

In the examples contained on this page, I will be using the Sodium cryptography library. Specifically, my example code will be written with the Sodium-Plus library for JavaScript, since it strikes a good balance between performance and being cross-platform.

const { SodiumPlus } = require('sodium-plus');(async function() { // Select a backend automatically const sodium = await SodiumPlus.auto(); // Do other stuff here})();

Libsodium is generally the correct choice for developing cryptography features in software, and is available in most programming languages,

If you’re prone to choose a different library, you should consult your cryptographer (and yes, you should have one on your payroll if you’re doing things different) about your design choices.

Threat Modelling

Remember above when I said, “You don’t have to implement the full stack of solutions to protect users, but the further you can afford to go, the safer your users will be from privacy-invasive policing”?

How far you go in implementing the steps outlined on this blog post should be informed by a threat model, not an ad hoc judgment.

For example, if you’re encrypting user data and storing it in the cloud, you probably want to pass the Mud Puddle Test:

1. First, drop your device(s) in a mud puddle.
2. Next, slip in said puddle and crack yourself on the head. When you regain consciousness you’ll be perfectly fine, but won’t for the life of you be able to recall your device passwords or keys.
3. Now try to get your cloud data back.

Did you succeed? If so, you’re screwed. Or to be a bit less dramatic, I should say: your cloud provider has access to your ‘encrypted’ data, as does the government if they want it, as does any rogue employee who knows their way around your provider’s internal policy checks.

Matthew Green describes the Mud Puddle Test, which Apple products definitely don’t pass.

If you must fail the Mud Puddle Test for your users, make sure you’re clear and transparent about this in the documentation for your product or service.

(Art by Swizz.)

I. Symmetric-Key Encryption

The easiest piece of this puzzle is to encrypt data in transit between both ends (thus, satisfying the loosest definition of end-to-end encryption).

At this layer, you already have some kind of symmetric key to use for encrypting data before you send it, and for decrypting it as you receive it.

For example, the following code will encrypt/decrypt strings and return hexadecimal strings with a version prefix.

const VERSION = "v1";/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function encryptData(message, key, assocData = null) { const nonce = await sodium.randombytes_buf(24); const aad = JSON.stringify({ 'version': VERSION, 'nonce': await sodium.sodium_bin2hex(nonce), 'extra': assocData }); const encrypted = await sodium.crypto_aead_xchacha20poly1305_ietf_encrypt( message, nonce, key, aad ); return ( VERSION + await sodium.sodium_bin2hex(nonce) + await sodium.sodium_bin2hex(encrypted) );}/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function decryptData(encrypted, key, assocData = null) { const ver = encrypted.slice(0, 2); if (!await sodium.sodium_memcmp(ver, VERSION)) { throw new Error("Incorrect version: " + ver); } const nonce = await sodium.sodium_hex2bin(encrypted.slice(2, 50)); const ciphertext = await sodium.sodium_hex2bin(encrypted.slice(50)); const aad = JSON.stringify({ 'version': ver, 'nonce': encrypted.slice(2, 50), 'extra': assocData }); const plaintext = await sodium.crypto_aead_xchacha20poly1305_ietf_decrypt( ciphertext, nonce, key, aad ); return plaintext.toString('utf-8');}

Under-the-hood, this is using XChaCha20-Poly1305, which is less sensitive to timing leaks than AES-GCM. However, like AES-GCM, this encryption mode doesn’t provide message- or key-commitment.

If you want key commitment, you should derive two keys from $key using a KDF based on hash functions: One for actual encryption, and the other as a key commitment value.

If you want message commitment, you can use AES-CTR + HMAC-SHA256 or XChaCha20 + BLAKE2b-MAC.

If you want both, ask Taylor Campbell about his BLAKE3-based design.

A modified version of the above code with key-commitment might look like this:

const VERSION = "v2";/** * Derive an encryption key and a commitment hash. * @param {CryptographyKey} key * @param {Uint8Array} nonce * @returns {{encKey: CryptographyKey, commitment: Uint8Array}} */async function deriveKeys(key, nonce) { const encKey = new CryptographyKey(await sodium.crypto_generichash( new Uint8Array([0x01].append(nonce)), key )); const commitment = await sodium.crypto_generichash( new Uint8Array([0x02].append(nonce)), key ); return {encKey, commitment};}/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function encryptData(message, key, assocData = null) { const nonce = await sodium.randombytes_buf(24); const aad = JSON.stringify({ 'version': VERSION, 'nonce': await sodium.sodium_bin2hex(nonce), 'extra': assocData }); const {encKey, commitment} = await deriveKeys(key, nonce); const encrypted = await sodium.crypto_aead_xchacha20poly1305_ietf_encrypt( message, nonce, encKey, aad ); return ( VERSION + await sodium.sodium_bin2hex(nonce) + await sodium.sodium_bin2hex(commitment) + await sodium.sodium_bin2hex(encrypted) );}/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function decryptData(encrypted, key, assocData = null) { const ver = encrypted.slice(0, 2); if (!await sodium.sodium_memcmp(ver, VERSION)) { throw new Error("Incorrect version: " + ver); } const nonce = await sodium.sodium_hex2bin(encrypted.slice(2, 50)); const ciphertext = await sodium.sodium_hex2bin(encrypted.slice(114)); const aad = JSON.stringify({ 'version': ver, 'nonce': encrypted.slice(2, 50), 'extra': assocData }); const storedCommitment = await sodium.sodium_hex2bin(encrypted.slice(50, 114)); const {encKey, commitment} = await deriveKeys(key, nonce); if (!(await sodium.sodium_memcmp(storedCommitment, commitment))) { throw new Error("Incorrect commitment value"); } const plaintext = await sodium.crypto_aead_xchacha20poly1305_ietf_decrypt( ciphertext, nonce, encKey, aad ); return plaintext.toString('utf-8');}

Another design choice you might make is to encode ciphertext with base64 instead of hexadecimal. That doesn’t significantly alter the design here, but it does mean your decoding logic has to accommodate this.

You SHOULD version your ciphertexts, and include this in the AAD provided to your AEAD encryption mode. I used “v1” and “v2” as a version string above, but you can use your software name for that too.

II. Key Agreement

If you’re not familiar with Elliptic Curve Diffie-Hellman or Authenticated Key Exhcanges, the two of the earliest posts on this blog were dedicated to those topics.

Key agreement in libsodium uses Elliptic Curve Diffie-Hellman over Curve25519, or X25519 for short.

There are many schools of thought for extending ECDH into an authenticated key exchange protocol.

We’re going to implement what the Signal Protocol calls X3DH instead of doing some interactive EdDSA + ECDH hybrid, because X3DH provides cryptographic deniability (see this section of the X3DH specification for more information).

For the moment, I’m going to assume a client-server model. That may or may not be appropriate for your design. You can substitute “the server” for “the other participant” in a peer-to-peer configuration.

Head’s up: This section of the blog post is code-heavy.

Update (November 23, 2020): I implemented this design in TypeScript, if you’d like something tangible to work with. I call my library, Rawr X3DH.

X3DH Pre-Key Bundles

Each participant will need to upload an Ed25519 identity key once (which is a detail covered in another section), which will be used to sign bundles of X25519 public keys to use for X3DH.

Your implementation will involve a fair bit of boilerplate, like so:

/** * Generate an X25519 keypair. * * @returns {{secretKey: X25519SecretKey, publicKey: X25519PublicKey}} */async function generateKeyPair() { const keypair = await sodium.crypto_box_keypair(); return { secretKey: await sodium.crypto_box_secretkey(keypair), publicKey: await sodium.crypto_box_publickey(keypair) };}/** * Generates some number of X25519 keypairs. * * @param {number} preKeyCount * @returns {{secretKey: X25519SecretKey, publicKey: X25519PublicKey}[]} */async function generateBundle(preKeyCount = 100) { const bundle = []; for (let i = 0; i < preKeyCount; i++) { bundle.push(await generateKeyPair()); } return bundle;}/** * BLAKE2b( len(PK) | PK_0, PK_1, ... PK_n ) * * @param {X25519PublicKey[]} publicKeys * @returns {Uint8Array} */async function prehashPublicKeysForSigning(publicKeys) { const hashState = await sodium.crypto_generichash_init(); // First, update the state with the number of public keys const pkLen = new Uint8Array([ (publicKeys.length >>> 24) & 0xff, (publicKeys.length >>> 16) & 0xff, (publicKeys.length >>> 8) & 0xff, publicKeys.length & 0xff ]); await sodium.crypto_generichash_update(hashState, pkLen); // Next, update the state with each public key for (let pk of publicKeys) { await sodium.crypto_generichash_update( hashState, pk.getBuffer() ); } // Return the finalized BLAKE2b hash return await sodium.crypto_generichash_final(hashState);}/** * Signs a bundle. Returns the signature. * * @param {Ed25519SecretKey} signingKey * @param {X25519PublicKey[]} publicKeys * @returns {Uint8Array} */async function signBundle(signingKey, publicKeys) { return sodium.crypto_sign_detached( await prehashPublicKeysForSigning(publicKeys), signingKey );}/** * This is just so you can see how verification looks. * * @param {Ed25519PublicKey} verificationKey * @param {X25519PublicKey[]} publicKeys * @param {Uint8Array} signature */async function verifyBundle(verificationKey, publicKeys, signature) { return sodium.crypto_sign_verify_detached( await prehashPublicKeysForSigning(publicKeys), verificationKey, signature );}

This boilerplate exists just so you can do something like this:

/** * Generate some number of X25519 keypairs. * Persist the bundle. * Sign the bundle of publickeys with the Ed25519 secret key. * Return the signed bundle (which can be transmitted to the server.) * * @param {Ed25519SecretKey} signingKey * @param {number} numKeys * @returns {{signature: string, bundle: string[]}} */async function x3dh_pre_key(signingKey, numKeys = 100) { const bundle = await generateBundle(numKeys); const publicKeys = bundle.map(x => x.publicKey); const signature = await signBundle(signingKey, publicKeys); // This is a stub; how you persist it is app-specific: persistBundleNotDefinedHere(signingKey, bundle); // Hex-encode all the public keys const encodedBundle = []; for (let pk of publicKeys) { encodedBundle.push(await sodium.sodium_bin2hex(pk.getBuffer())); } return { 'signature': await sodium.sodium_bin2hex(signature), 'bundle': encodedBundle };}

And then you can drop the output of x3dh_pre_key(secretKey) into a JSON-encoded HTTP request.

In accordance to Signal’s X3DH spec, you want to use x3dh_pre_key(secretKey, 1) to generate the “signed pre-key” bundle and x3dn_pre_key(secretKey, 100) when pushing 100 one-time keys to the server.

X3DH Initiation

This section conforms to the Sending the Initial Message section of the X3DH specification.

When you initiate a conversation, the server should provide you with a bundle containing:

• Your peer’s Identity key (an Ed25519 public key)
• Your peer’s current Signed Pre-Key (an X25519 public key)
• (If any remain unburned) One of your key’s One-Time Keys (an X25519 public key) — and then delete it

If we assume the structure of this response looks like this:

{ "IdentityKey": "...", "SignedPreKey": { "Signature": "..." "PreKey": "..." }, "OneTimeKey": "..." // or NULL}

Then we can write the initiation step of the handshake like so:

/** * Get SK for initializing an X3DH handshake * * @param {object} r -- See previous code block * @param {Ed25519SecretKey} senderKey */async function x3dh_initiate_send_get_sk(r, senderKey) { const identityKey = new Ed25519PublicKey( await sodium.sodium_hex2bin(r.IdentityKey) ); const signedPreKey = new X25519PublicKey( await sodium.sodium_hex2bin(r.SignedPreKey.PreKey) ); const signature = await sodium.sodium_hex2bin(r.SignedPreKey.Signature); // Check signature const valid = await verifyBundle(identityKey, [signedPreKey], signature); if (!valid) { throw new Error("Invalid signature"); } const ephemeral = await generateKeyPair(); const ephSecret = ephemeral.secretKey; const ephPublic = ephemeral.publicKey; // Turn the Ed25519 keys into X25519 keys for X3DH: const senderX = await sodium.crypto_sign_ed25519_sk_to_curve25519(senderKey); const recipientX = await sodium.crypto_sign_ed25519_pk_to_curve25519(identityKey); // See the X3DH specification to really understand this part: const DH1 = await sodium.crypto_scalarmult(senderX, signedPreKey); const DH2 = await sodium.crypto_scalarmult(ephSecret, recipientX); const DH3 = await sodium.crypto_scalarmult(ephSecret, signedPreKey); let SK; if (r.OneTimeKey) { let DH4 = await sodium.crypto_scalarmult( ephSecret, new X25519PublicKey(await sodium.sodium_hex2bin(r.OneTimeKey)) ); SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) .concat(DH4.getBuffer()) )); DH4.wipe(); } else { SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) )); } // Wipe keys DH1.wipe(); DH2.wipe(); DH3.wipe(); ephSecret.wipe(); senderX.wipe(); return { IK: identityKey, EK: ephPublic, SK: SK, OTK: r.OneTimeKey // might be NULL };}/** * Initialize an X3DH handshake * * @param {string} recipientIdentity - Some identifier for the user * @param {Ed25519SecretKey} secretKey - Sender's secret key * @param {Ed25519PublicKey} publicKey - Sender's public key * @param {string} message - The initial message to send * @returns {object} */async function x3dh_initiate_send(recipientIdentity, secretKey, publicKey, message) { const r = await get_server_response(recipientIdentity); const {IK, EK, SK, OTK} = await x3dh_initiate_send_get_sk(r, secretKey); const assocData = await sodium.sodium_bin2hex( new Uint8Array( [].concat(publicKey.getBuffer()) .concat(IK.getBuffer()) ) ); /* * We're going to set the session key for our recipient to SK. * This might invoke a ratchet. * * Either SK or the output of the ratchet derived from SK * will be returned by getEncryptionKey(). */ await setSessionKey(recipientIdentity, SK); const encrypted = await encryptData( message, await getEncryptionKey(recipientIdentity), assocData ); return { "Sender": my_identity_string, "IdentityKey": await sodium.sodium_bin2hex(publicKey), "EphemeralKey": await sodium.sodium_bin2hex(EK), "OneTimeKey": OTK, "CipherText": encrypted };}

We didn’t define setSessionKey() or getEncryptionKey() above. It will be covered later.

X3DH – Receiving an Initial Message

This section implements the Receiving the Initial Message section of the X3DH Specification.

We’re going to assume the structure of the request looks like this:

{ "Sender": "...", "IdentityKey": "...", "EphemeralKey": "...", "OneTimeKey": "...", "CipherText": "..."}

The code to handle this should look like this:

/** * Handle an X3DH initiation message as a receiver * * @param {object} r -- See previous code block * @param {Ed25519SecretKey} identitySecret * @param {Ed25519PublicKey} identityPublic * @param {Ed25519SecretKey} preKeySecret */async function x3dh_initiate_recv_get_sk( r, identitySecret, identityPublic, preKeySecret) { // Decode strings const senderIdentityKey = new Ed25519PublicKey( await sodium.sodium_hex2bin(r.IdentityKey), ); const ephemeral = new X25519PublicKey( await sodium.sodium_hex2bin(r.EphemeralKey), ); // Ed25519 -> X25519 const senderX = await sodium.crypto_sign_ed25519_pk_to_curve25519(senderIdentityKey); const recipientX = await sodium.crypto_sign_ed25519_sk_to_curve25519(identitySecret); // See the X3DH specification to really understand this part: const DH1 = await sodium.crypto_scalarmult(preKeySecret, senderX); const DH2 = await sodium.crypto_scalarmult(recipientX, ephemeral); const DH3 = await sodium.crypto_scalarmult(preKeySecret, ephemeral); let SK; if (r.OneTimeKey) { let DH4 = await sodium.crypto_scalarmult( await fetchAndWipeOneTimeSecretKey(r.OneTimeKey), ephemeral ); SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) .concat(DH4.getBuffer()) )); DH4.wipe(); } else { SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) )); } // Wipe keys DH1.wipe(); DH2.wipe(); DH3.wipe(); recipientX.wipe(); return { Sender: r.Sender, SK: SK, IK: senderIdentityKey };}/** * Initiate an X3DH handshake as a recipient * * @param {object} req - Request object * @returns {string} - The initial message */async function x3dh_initiate_recv(req) { const {identitySecret, identityPublic} = await getIdentityKeypair(); const {preKeySecret, preKeyPublic} = await getPreKeyPair(); const {Sender, SK, IK} = await x3dh_initiate_recv_get_sk( req, identitySecret, identityPublic, preKeySecret, preKeyPublic ); const assocData = await sodium.sodium_bin2hex( new Uint8Array( [].concat(IK.getBuffer()) .concat(identityPublic.getBuffer()) ) ); try { await setSessionKey(senderIdentity, SK); return decryptData( req.CipherText, await getEncryptionKey(senderIdentity), assocData ); } catch (e) { await destroySessionKey(senderIdentity); throw e; }}

And with that, you’ve successfully implemented X3DH and symmetric encryption in JavaScript.

We abstracted some of the details away (i.e. kdf(), the transport mechanisms, the session key management mechanisms, and a few others). Some of them will be highly specific to your application, so it doesn’t make a ton of sense to flesh them out.

One thing to keep in mind: According to the X3DH specification, participants should regularly (e.g. weekly) replace their Signed Pre-Key in the server with a fresh one. They should also publish more One-Time Keys when they start to run low.

If you’d like to see a complete reference implementation of X3DH, as I mentioned before, Rawr-X3DH implements it in TypeScript.

Session Key Management

Using X3DH to for every message is inefficient and unnecessary. Even the Signal Protocol doesn’t do that.

Instead, Signal specifies a Double Ratchet protocol that combines a Symmetric-Key Ratchet on subsequent messages, and a Diffie-Hellman-based ratcheting protocol.

Signal even specifies integration guidelines for the Double Ratchet with X3DH.

It’s worth reading through the specification to understand their usages of Key-Derivation Functions (KDFs) and KDF Chains.

Although it is recommended to use HKDF as the Signal protocol specifies, you can strictly speaking use any secure keyed PRF to accomplish the same goal.

What follows is an example of a symmetric KDF chain that uses BLAKE2b with 512-bit digests of the current session key; the leftmost half of the BLAKE2b digest becomes the new session key, while the rightmost half becomes the encryption key.

const SESSION_KEYS = {};/** * Note: In reality you'll want to have two separate sessions: * One for receiving data, one for sending data. * * @param {string} identity * @param {CryptographyKey} key */async function setSessionKey(identity, key) { SESSION_KEYS[identity] = key;}async function getEncryptionKey(identity) { if (!SESSION_KEYS[identity]) { throw new Error("No session key for " + identity"); } const blake2bMac = await sodium.crypto_generichash( SESSION_KEYS[identity], null, 64 ); SESSION_KEYS[identity] = new CryptographyKey(blake2bMac.slice(0, 32)); return new CryptographyKey(blake2bMac.slice(32, 64));}

In the interest of time, a full DHRatchet implementation is left as an exercise to the reader (since it’s mostly a state machine), but using the appropriate functions provided by sodium-plus (crypto_box_keypair(), crypto_scalarmult()) should be relatively straightforward.

Make sure your KDFs use domain separation, as per the Signal Protocol specifications.

Group Key Agreement

The Signal Protocol specified X3DH and the Double Ratchet for securely encrypting information between two parties.

Group conversations are trickier, because you have to be able to encrypt information that multiple recipients can decrypt, add/remove participants to the conversation, etc.

(The same complexity comes with multi-device support for end-to-end encryption.)

The best design I’ve read to date for tackling group key agreement is the IETF Messaging Layer Security RFC draft.

I am not going to implement the entire MLS RFC in this blog post. If you want to support multiple devices or group conversations, you’ll want a complete MLS implementation to work with.

Brief Recap

That was a lot of ground to cover, but we’re not done yet.

(Art by Khia.)

So far we’ve tackled encryption, initial key agreement, and session key management. However, we did not flesh out how Identity Keys (which are signing keys–Ed25519 specifically–rather than Diffie-Hellman keys) are managed. That detail was just sorta hand-waved until now.

So let’s talk about that.

III. Identity Key Management

There’s a meme among technology bloggers to write a post titled “Falsehoods Programmers Believe About _____”.

Fortunately for us, Identity is one of the topics that furries are positioned to understand better than most (due to fursonas): Identities have a many-to-many relationship with Humans.

In an end-to-end encryption protocol, each identity will consist of some identifier (phone number, email address, username and server hostname, etc.) and an Ed25519 keypair (for which the public key will be published).

But how do you know whether or not a given public key is correct for a given identity?

This is where we segue into one of the hard problems in cryptography, where the solutions available are entirely dependent on your threat model: Public Key Infrastructure (PKI).

Some common PKI designs include:

1. Certificate Authorities (CAs) — TLS does this
2. Web-of-Trust (WoT) — The PGP ecosystem does this
3. Trust On First Use (TOFU) — SSH does this
4. Key Transparency / Certificate Transparency (CT) — TLS also does this for ensuring CA-issued certificates are auditable (although it was originally meant to replace Certificate Authorities)

And you can sort of choose-your-own-adventure on this one, depending on what’s most appropriate for the type of software you’re building and who your customers are.

One design I’m particularly fond of is called Gossamer, which is a PKI design without Certificate Authorities, originally designed for making WordPress’s automatic updates more secure (i.e. so every developer can sign their theme and plugin updates).

Since we only need to maintain an up-to-date repository of Ed25519 identity keys for each participant in our end-to-end encryption protocol, this makes Gossamer a suitable starting point.

Gossamer specifies a limited grammar of Actions that can be performed: AppendKey, RevokeKey, AppendUpdate, RevokeUpdate, and AttestUpdate. These actions are signed and published to an append-only cryptographic ledger.

I would propose a sixth action: AttestKey, so you can have WoT-like assurances and key-signing parties. (If nothing else, you should be able to attest that the identity keys of other cryptographic ledgers in the network are authentic at a point in time.)

IV. Backdoor Resistance

In the previous section, I proposed the use of Gossamer as a PKI for Identity Keys. This would provide Ed25519 keypairs for use with X3DH and the Double Ratchet, which would in turn provide session keys to use for symmetric authenticated encryption.

If you’ve implemented everything preceding this section, you have a full-stack end-to-end encryption protocol. But let’s make intelligence agencies and surveillance capitalists even more mad by making it impractical to backdoor our software (and impossible to silently backdoor it).

How do we pull that off?

You want Binary Transparency.

For us, the implementation is simple: Use Gossamer as it was originally intended (i.e. to secure your software distribution channels).

Gossamer provides up-to-date verification keys and a commitment to a cryptographic ledger of every software update. You can learn more about its inspiration here.

It isn’t enough to merely use Gossamer to manage keys and update signatures. You need independent third parties to use the AttestUpdate action to assert one or more of the following:

1. That builds are reproducible from the source code.
2. That they have reviewed the source code and found no evidence of backdoors or exploitable vulnerabilities.

(And then you should let your users decide which of these independent third parties they trust to vet software updates.)

Closing Remarks

The U.S. Government cries and moans a lot about “criminals going dark” and wonders a lot about how to solve the “going dark problem”.

If more software developers implement end-to-end encryption in their communications software, then maybe one day they won’t be able to use dragnet surveillance to spy on citizens and they’ll be forced to do actual detective work to solve actual crimes.

Y’know, like their job description actually entails?

Let’s normalize end-to-end encryption. Let’s normalize backdoor-resistant software distribution.

Let’s collectively tell the intelligence community in every sophisticated nation state the one word they don’t hear often enough:

Especially if you’re a furry. Because we improve everything! :3

Questions You Might Have

What About Private Contact Discovery?

That’s one of the major reasons why the thing we’re building isn’t meant to compete with Signal (and it MUST NOT be advertised as such):

Signal is a privacy tool, and their servers have no way of identifying who can contact who.

What we’ve built here isn’t a complete privacy solution, it’s only providing end-to-end encryption (and possibly making NSA employees cry at their desk).

Does This Design Work with Federation?

Yes. Each identifier string can be [username] at [hostname].

What About Network Metadata?

If you want anonymity, you want to use Tor.

Why Are You Using Ed25519 Keys for X3DH?

If you only read the key agreement section of this blog post and the fact that I’m passing around Ed25519 public keys seems weird, you might have missed the identity section of this blog post where I suggested piggybacking on another protocol called Gossamer to handle the distribution of Ed25519 public keys. (Gossamer is also beneficial for backdoor resistance in software update distribution, as described in the subsequent section.)

Furthermore, we’re actually using birationally equivalent X25519 keys derived from the Ed25519 keypair for the X3DH step. This is a deviation from what Signal does (using X25519 keys everywhere, then inventing an EdDSA variant to support their usage).

const publicKeyX = await sodium.crypto_sign_ed25519_pk_to_curve25519(foxPublicKey);const secretKeyX = await sodium.crypto_sign_ed25519_sk_to_curve25519(wolfSecretKey);

(Using fox/wolf instead of Alice/Bob, because it’s cuter.)

This design pattern has a few advantages:

1. It makes Gossamer integration seamless, which means you can use Ed25519 for identities and still have a deniable X3DH handshake for 1:1 conversations while implementing the rest of the designs proposed.
2. This approach to X3DH can be implemented entirely with libsodium functions, without forcing you to write your own cryptography implementations (i.e. for XEdDSA).

The only disadvantages I’m aware of are:

1. It deviates from Signal’s core design in a subtle way that means you don’t get to claim the exact same advantages Signal does when it comes to peer review.
2. Some cryptographers are distrustful of the use of birationally equivalent X25519 keys from Ed25519 keys (although there isn’t a vulnerability any of them have been able to point me to that doesn’t involve torsion groups–which libsodium’s implementation already avoids).

If these concerns are valid enough to decide against my implementation above, I invite you to talk with cryptographers about your concerns and then propose alternatives.

Has Any of This Been Implemented Already?

You can find implementations for the designs discussed on this blog post below:

• Rawr-X3DH implements X3DH in TypeScript (added 2020-11-23)

I will update this section of the blog post as implementations surface.

https://soatok.blog/2020/11/14/going-bark-a-furrys-guide-to-end-to-end-encryption/

#authenticatedEncryption #authenticatedKeyExchange #crypto #cryptography #encryption #endToEndEncryption #libsodium #OnlinePrivacy #privacy #SecurityGuidance #symmetricEncryption

Governments are back on their anti-encryption bullshit again.

Between the U.S. Senate’s “EARN IT” Act, the E.U.’s slew of anti-encryption proposals, and Australia’s new anti-encryption law, it’s become clear that the authoritarians in office view online privacy as a threat to their existence.

Normally, when the governments increase their anti-privacy sabre-rattling, technologists start talking more loudly about Tor, Signal, and other privacy technologies (usually only to be drowned out by paranoid people who think Tor and Signal are government backdoors or something stupid; conspiracy theories ruin everything!).

I’m not going to do that.

Instead, I’m going to show you how to add end-to-end encryption to any communication software you’re developing. (Hopefully, I’ll avoid making any bizarre design decisions along the way.)

But first, some important disclaimers:

1. Yes, you should absolutely do this. I don’t care how banal your thing is; if you expect people to use it to communicate with each other, you should make it so that you can never decrypt their communications.
2. You should absolutely NOT bill the thing you’re developing as an alternative to Signal or WhatsApp.
3. The goal of doing this is to increase the amount of end-to-end encryption deployed on the Internet that the service operator cannot decrypt (even if compelled by court order) and make E2EE normalized. The goal is NOT to compete with highly specialized and peer-reviewed privacy technology.
4. I am not a lawyer, I’m some furry who works in cryptography. The contents of this blog post is not legal advice, nor is it endorsed by any company or organization. Ask the EFF for legal questions.

The organization of this blog post is as follows: First, I’ll explain how to encrypt and decrypt data between users, assuming you have a key. Next, I’ll explain how to build an authenticated key exchange and a ratcheting protocol to determine the keys used in the first step. Afterwards, I’ll explore techniques for binding authentication keys to identities and managing trust. Finally, I’ll discuss strategies for making it impractical to ever backdoor your software (and impossible to silently backdoor it), just to piss the creeps and tyrants of the world off even more.

You don’t have to implement the full stack of solutions to protect users, but the further you can afford to go, the safer your users will be from privacy-invasive policing.

(Art by Kyume.)

Preliminaries

Choosing a Cryptography Library

In the examples contained on this page, I will be using the Sodium cryptography library. Specifically, my example code will be written with the Sodium-Plus library for JavaScript, since it strikes a good balance between performance and being cross-platform.

const { SodiumPlus } = require('sodium-plus');(async function() { // Select a backend automatically const sodium = await SodiumPlus.auto(); // Do other stuff here})();

Libsodium is generally the correct choice for developing cryptography features in software, and is available in most programming languages,

If you’re prone to choose a different library, you should consult your cryptographer (and yes, you should have one on your payroll if you’re doing things different) about your design choices.

Threat Modelling

Remember above when I said, “You don’t have to implement the full stack of solutions to protect users, but the further you can afford to go, the safer your users will be from privacy-invasive policing”?

How far you go in implementing the steps outlined on this blog post should be informed by a threat model, not an ad hoc judgment.

For example, if you’re encrypting user data and storing it in the cloud, you probably want to pass the Mud Puddle Test:

1. First, drop your device(s) in a mud puddle.
2. Next, slip in said puddle and crack yourself on the head. When you regain consciousness you’ll be perfectly fine, but won’t for the life of you be able to recall your device passwords or keys.
3. Now try to get your cloud data back.

Did you succeed? If so, you’re screwed. Or to be a bit less dramatic, I should say: your cloud provider has access to your ‘encrypted’ data, as does the government if they want it, as does any rogue employee who knows their way around your provider’s internal policy checks.

Matthew Green describes the Mud Puddle Test, which Apple products definitely don’t pass.

If you must fail the Mud Puddle Test for your users, make sure you’re clear and transparent about this in the documentation for your product or service.

(Art by Swizz.)

I. Symmetric-Key Encryption

The easiest piece of this puzzle is to encrypt data in transit between both ends (thus, satisfying the loosest definition of end-to-end encryption).

At this layer, you already have some kind of symmetric key to use for encrypting data before you send it, and for decrypting it as you receive it.

For example, the following code will encrypt/decrypt strings and return hexadecimal strings with a version prefix.

const VERSION = "v1";/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function encryptData(message, key, assocData = null) { const nonce = await sodium.randombytes_buf(24); const aad = JSON.stringify({ 'version': VERSION, 'nonce': await sodium.sodium_bin2hex(nonce), 'extra': assocData }); const encrypted = await sodium.crypto_aead_xchacha20poly1305_ietf_encrypt( message, nonce, key, aad ); return ( VERSION + await sodium.sodium_bin2hex(nonce) + await sodium.sodium_bin2hex(encrypted) );}/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function decryptData(encrypted, key, assocData = null) { const ver = encrypted.slice(0, 2); if (!await sodium.sodium_memcmp(ver, VERSION)) { throw new Error("Incorrect version: " + ver); } const nonce = await sodium.sodium_hex2bin(encrypted.slice(2, 50)); const ciphertext = await sodium.sodium_hex2bin(encrypted.slice(50)); const aad = JSON.stringify({ 'version': ver, 'nonce': encrypted.slice(2, 50), 'extra': assocData }); const plaintext = await sodium.crypto_aead_xchacha20poly1305_ietf_decrypt( ciphertext, nonce, key, aad ); return plaintext.toString('utf-8');}

Under-the-hood, this is using XChaCha20-Poly1305, which is less sensitive to timing leaks than AES-GCM. However, like AES-GCM, this encryption mode doesn’t provide message- or key-commitment.

If you want key commitment, you should derive two keys from $key using a KDF based on hash functions: One for actual encryption, and the other as a key commitment value.

If you want message commitment, you can use AES-CTR + HMAC-SHA256 or XChaCha20 + BLAKE2b-MAC.

If you want both, ask Taylor Campbell about his BLAKE3-based design.

A modified version of the above code with key-commitment might look like this:

const VERSION = "v2";/** * Derive an encryption key and a commitment hash. * @param {CryptographyKey} key * @param {Uint8Array} nonce * @returns {{encKey: CryptographyKey, commitment: Uint8Array}} */async function deriveKeys(key, nonce) { const encKey = new CryptographyKey(await sodium.crypto_generichash( new Uint8Array([0x01].append(nonce)), key )); const commitment = await sodium.crypto_generichash( new Uint8Array([0x02].append(nonce)), key ); return {encKey, commitment};}/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function encryptData(message, key, assocData = null) { const nonce = await sodium.randombytes_buf(24); const aad = JSON.stringify({ 'version': VERSION, 'nonce': await sodium.sodium_bin2hex(nonce), 'extra': assocData }); const {encKey, commitment} = await deriveKeys(key, nonce); const encrypted = await sodium.crypto_aead_xchacha20poly1305_ietf_encrypt( message, nonce, encKey, aad ); return ( VERSION + await sodium.sodium_bin2hex(nonce) + await sodium.sodium_bin2hex(commitment) + await sodium.sodium_bin2hex(encrypted) );}/** * @param {string|Uint8Array} message * @param {Uint8Array} key * @param {string|null} assocData * @returns {string} */async function decryptData(encrypted, key, assocData = null) { const ver = encrypted.slice(0, 2); if (!await sodium.sodium_memcmp(ver, VERSION)) { throw new Error("Incorrect version: " + ver); } const nonce = await sodium.sodium_hex2bin(encrypted.slice(2, 50)); const ciphertext = await sodium.sodium_hex2bin(encrypted.slice(114)); const aad = JSON.stringify({ 'version': ver, 'nonce': encrypted.slice(2, 50), 'extra': assocData }); const storedCommitment = await sodium.sodium_hex2bin(encrypted.slice(50, 114)); const {encKey, commitment} = await deriveKeys(key, nonce); if (!(await sodium.sodium_memcmp(storedCommitment, commitment))) { throw new Error("Incorrect commitment value"); } const plaintext = await sodium.crypto_aead_xchacha20poly1305_ietf_decrypt( ciphertext, nonce, encKey, aad ); return plaintext.toString('utf-8');}

Another design choice you might make is to encode ciphertext with base64 instead of hexadecimal. That doesn’t significantly alter the design here, but it does mean your decoding logic has to accommodate this.

You SHOULD version your ciphertexts, and include this in the AAD provided to your AEAD encryption mode. I used “v1” and “v2” as a version string above, but you can use your software name for that too.

II. Key Agreement

If you’re not familiar with Elliptic Curve Diffie-Hellman or Authenticated Key Exhcanges, the two of the earliest posts on this blog were dedicated to those topics.

Key agreement in libsodium uses Elliptic Curve Diffie-Hellman over Curve25519, or X25519 for short.

There are many schools of thought for extending ECDH into an authenticated key exchange protocol.

We’re going to implement what the Signal Protocol calls X3DH instead of doing some interactive EdDSA + ECDH hybrid, because X3DH provides cryptographic deniability (see this section of the X3DH specification for more information).

For the moment, I’m going to assume a client-server model. That may or may not be appropriate for your design. You can substitute “the server” for “the other participant” in a peer-to-peer configuration.

Head’s up: This section of the blog post is code-heavy.

Update (November 23, 2020): I implemented this design in TypeScript, if you’d like something tangible to work with. I call my library, Rawr X3DH.

X3DH Pre-Key Bundles

Each participant will need to upload an Ed25519 identity key once (which is a detail covered in another section), which will be used to sign bundles of X25519 public keys to use for X3DH.

Your implementation will involve a fair bit of boilerplate, like so:

/** * Generate an X25519 keypair. * * @returns {{secretKey: X25519SecretKey, publicKey: X25519PublicKey}} */async function generateKeyPair() { const keypair = await sodium.crypto_box_keypair(); return { secretKey: await sodium.crypto_box_secretkey(keypair), publicKey: await sodium.crypto_box_publickey(keypair) };}/** * Generates some number of X25519 keypairs. * * @param {number} preKeyCount * @returns {{secretKey: X25519SecretKey, publicKey: X25519PublicKey}[]} */async function generateBundle(preKeyCount = 100) { const bundle = []; for (let i = 0; i < preKeyCount; i++) { bundle.push(await generateKeyPair()); } return bundle;}/** * BLAKE2b( len(PK) | PK_0, PK_1, ... PK_n ) * * @param {X25519PublicKey[]} publicKeys * @returns {Uint8Array} */async function prehashPublicKeysForSigning(publicKeys) { const hashState = await sodium.crypto_generichash_init(); // First, update the state with the number of public keys const pkLen = new Uint8Array([ (publicKeys.length >>> 24) & 0xff, (publicKeys.length >>> 16) & 0xff, (publicKeys.length >>> 8) & 0xff, publicKeys.length & 0xff ]); await sodium.crypto_generichash_update(hashState, pkLen); // Next, update the state with each public key for (let pk of publicKeys) { await sodium.crypto_generichash_update( hashState, pk.getBuffer() ); } // Return the finalized BLAKE2b hash return await sodium.crypto_generichash_final(hashState);}/** * Signs a bundle. Returns the signature. * * @param {Ed25519SecretKey} signingKey * @param {X25519PublicKey[]} publicKeys * @returns {Uint8Array} */async function signBundle(signingKey, publicKeys) { return sodium.crypto_sign_detached( await prehashPublicKeysForSigning(publicKeys), signingKey );}/** * This is just so you can see how verification looks. * * @param {Ed25519PublicKey} verificationKey * @param {X25519PublicKey[]} publicKeys * @param {Uint8Array} signature */async function verifyBundle(verificationKey, publicKeys, signature) { return sodium.crypto_sign_verify_detached( await prehashPublicKeysForSigning(publicKeys), verificationKey, signature );}

This boilerplate exists just so you can do something like this:

/** * Generate some number of X25519 keypairs. * Persist the bundle. * Sign the bundle of publickeys with the Ed25519 secret key. * Return the signed bundle (which can be transmitted to the server.) * * @param {Ed25519SecretKey} signingKey * @param {number} numKeys * @returns {{signature: string, bundle: string[]}} */async function x3dh_pre_key(signingKey, numKeys = 100) { const bundle = await generateBundle(numKeys); const publicKeys = bundle.map(x => x.publicKey); const signature = await signBundle(signingKey, publicKeys); // This is a stub; how you persist it is app-specific: persistBundleNotDefinedHere(signingKey, bundle); // Hex-encode all the public keys const encodedBundle = []; for (let pk of publicKeys) { encodedBundle.push(await sodium.sodium_bin2hex(pk.getBuffer())); } return { 'signature': await sodium.sodium_bin2hex(signature), 'bundle': encodedBundle };}

And then you can drop the output of x3dh_pre_key(secretKey) into a JSON-encoded HTTP request.

In accordance to Signal’s X3DH spec, you want to use x3dh_pre_key(secretKey, 1) to generate the “signed pre-key” bundle and x3dn_pre_key(secretKey, 100) when pushing 100 one-time keys to the server.

X3DH Initiation

This section conforms to the Sending the Initial Message section of the X3DH specification.

When you initiate a conversation, the server should provide you with a bundle containing:

• Your peer’s Identity key (an Ed25519 public key)
• Your peer’s current Signed Pre-Key (an X25519 public key)
• (If any remain unburned) One of your key’s One-Time Keys (an X25519 public key) — and then delete it

If we assume the structure of this response looks like this:

{ "IdentityKey": "...", "SignedPreKey": { "Signature": "..." "PreKey": "..." }, "OneTimeKey": "..." // or NULL}

Then we can write the initiation step of the handshake like so:

/** * Get SK for initializing an X3DH handshake * * @param {object} r -- See previous code block * @param {Ed25519SecretKey} senderKey */async function x3dh_initiate_send_get_sk(r, senderKey) { const identityKey = new Ed25519PublicKey( await sodium.sodium_hex2bin(r.IdentityKey) ); const signedPreKey = new X25519PublicKey( await sodium.sodium_hex2bin(r.SignedPreKey.PreKey) ); const signature = await sodium.sodium_hex2bin(r.SignedPreKey.Signature); // Check signature const valid = await verifyBundle(identityKey, [signedPreKey], signature); if (!valid) { throw new Error("Invalid signature"); } const ephemeral = await generateKeyPair(); const ephSecret = ephemeral.secretKey; const ephPublic = ephemeral.publicKey; // Turn the Ed25519 keys into X25519 keys for X3DH: const senderX = await sodium.crypto_sign_ed25519_sk_to_curve25519(senderKey); const recipientX = await sodium.crypto_sign_ed25519_pk_to_curve25519(identityKey); // See the X3DH specification to really understand this part: const DH1 = await sodium.crypto_scalarmult(senderX, signedPreKey); const DH2 = await sodium.crypto_scalarmult(ephSecret, recipientX); const DH3 = await sodium.crypto_scalarmult(ephSecret, signedPreKey); let SK; if (r.OneTimeKey) { let DH4 = await sodium.crypto_scalarmult( ephSecret, new X25519PublicKey(await sodium.sodium_hex2bin(r.OneTimeKey)) ); SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) .concat(DH4.getBuffer()) )); DH4.wipe(); } else { SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) )); } // Wipe keys DH1.wipe(); DH2.wipe(); DH3.wipe(); ephSecret.wipe(); senderX.wipe(); return { IK: identityKey, EK: ephPublic, SK: SK, OTK: r.OneTimeKey // might be NULL };}/** * Initialize an X3DH handshake * * @param {string} recipientIdentity - Some identifier for the user * @param {Ed25519SecretKey} secretKey - Sender's secret key * @param {Ed25519PublicKey} publicKey - Sender's public key * @param {string} message - The initial message to send * @returns {object} */async function x3dh_initiate_send(recipientIdentity, secretKey, publicKey, message) { const r = await get_server_response(recipientIdentity); const {IK, EK, SK, OTK} = await x3dh_initiate_send_get_sk(r, secretKey); const assocData = await sodium.sodium_bin2hex( new Uint8Array( [].concat(publicKey.getBuffer()) .concat(IK.getBuffer()) ) ); /* * We're going to set the session key for our recipient to SK. * This might invoke a ratchet. * * Either SK or the output of the ratchet derived from SK * will be returned by getEncryptionKey(). */ await setSessionKey(recipientIdentity, SK); const encrypted = await encryptData( message, await getEncryptionKey(recipientIdentity), assocData ); return { "Sender": my_identity_string, "IdentityKey": await sodium.sodium_bin2hex(publicKey), "EphemeralKey": await sodium.sodium_bin2hex(EK), "OneTimeKey": OTK, "CipherText": encrypted };}

We didn’t define setSessionKey() or getEncryptionKey() above. It will be covered later.

X3DH – Receiving an Initial Message

This section implements the Receiving the Initial Message section of the X3DH Specification.

We’re going to assume the structure of the request looks like this:

{ "Sender": "...", "IdentityKey": "...", "EphemeralKey": "...", "OneTimeKey": "...", "CipherText": "..."}

The code to handle this should look like this:

/** * Handle an X3DH initiation message as a receiver * * @param {object} r -- See previous code block * @param {Ed25519SecretKey} identitySecret * @param {Ed25519PublicKey} identityPublic * @param {Ed25519SecretKey} preKeySecret */async function x3dh_initiate_recv_get_sk( r, identitySecret, identityPublic, preKeySecret) { // Decode strings const senderIdentityKey = new Ed25519PublicKey( await sodium.sodium_hex2bin(r.IdentityKey), ); const ephemeral = new X25519PublicKey( await sodium.sodium_hex2bin(r.EphemeralKey), ); // Ed25519 -> X25519 const senderX = await sodium.crypto_sign_ed25519_pk_to_curve25519(senderIdentityKey); const recipientX = await sodium.crypto_sign_ed25519_sk_to_curve25519(identitySecret); // See the X3DH specification to really understand this part: const DH1 = await sodium.crypto_scalarmult(preKeySecret, senderX); const DH2 = await sodium.crypto_scalarmult(recipientX, ephemeral); const DH3 = await sodium.crypto_scalarmult(preKeySecret, ephemeral); let SK; if (r.OneTimeKey) { let DH4 = await sodium.crypto_scalarmult( await fetchAndWipeOneTimeSecretKey(r.OneTimeKey), ephemeral ); SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) .concat(DH4.getBuffer()) )); DH4.wipe(); } else { SK = kdf(new Uint8Array( [].concat(DH1.getBuffer()) .concat(DH2.getBuffer()) .concat(DH3.getBuffer()) )); } // Wipe keys DH1.wipe(); DH2.wipe(); DH3.wipe(); recipientX.wipe(); return { Sender: r.Sender, SK: SK, IK: senderIdentityKey };}/** * Initiate an X3DH handshake as a recipient * * @param {object} req - Request object * @returns {string} - The initial message */async function x3dh_initiate_recv(req) { const {identitySecret, identityPublic} = await getIdentityKeypair(); const {preKeySecret, preKeyPublic} = await getPreKeyPair(); const {Sender, SK, IK} = await x3dh_initiate_recv_get_sk( req, identitySecret, identityPublic, preKeySecret, preKeyPublic ); const assocData = await sodium.sodium_bin2hex( new Uint8Array( [].concat(IK.getBuffer()) .concat(identityPublic.getBuffer()) ) ); try { await setSessionKey(senderIdentity, SK); return decryptData( req.CipherText, await getEncryptionKey(senderIdentity), assocData ); } catch (e) { await destroySessionKey(senderIdentity); throw e; }}

And with that, you’ve successfully implemented X3DH and symmetric encryption in JavaScript.

We abstracted some of the details away (i.e. kdf(), the transport mechanisms, the session key management mechanisms, and a few others). Some of them will be highly specific to your application, so it doesn’t make a ton of sense to flesh them out.

One thing to keep in mind: According to the X3DH specification, participants should regularly (e.g. weekly) replace their Signed Pre-Key in the server with a fresh one. They should also publish more One-Time Keys when they start to run low.

If you’d like to see a complete reference implementation of X3DH, as I mentioned before, Rawr-X3DH implements it in TypeScript.

Session Key Management

Using X3DH to for every message is inefficient and unnecessary. Even the Signal Protocol doesn’t do that.

Instead, Signal specifies a Double Ratchet protocol that combines a Symmetric-Key Ratchet on subsequent messages, and a Diffie-Hellman-based ratcheting protocol.

Signal even specifies integration guidelines for the Double Ratchet with X3DH.

It’s worth reading through the specification to understand their usages of Key-Derivation Functions (KDFs) and KDF Chains.

Although it is recommended to use HKDF as the Signal protocol specifies, you can strictly speaking use any secure keyed PRF to accomplish the same goal.

What follows is an example of a symmetric KDF chain that uses BLAKE2b with 512-bit digests of the current session key; the leftmost half of the BLAKE2b digest becomes the new session key, while the rightmost half becomes the encryption key.

const SESSION_KEYS = {};/** * Note: In reality you'll want to have two separate sessions: * One for receiving data, one for sending data. * * @param {string} identity * @param {CryptographyKey} key */async function setSessionKey(identity, key) { SESSION_KEYS[identity] = key;}async function getEncryptionKey(identity) { if (!SESSION_KEYS[identity]) { throw new Error("No session key for " + identity"); } const blake2bMac = await sodium.crypto_generichash( SESSION_KEYS[identity], null, 64 ); SESSION_KEYS[identity] = new CryptographyKey(blake2bMac.slice(0, 32)); return new CryptographyKey(blake2bMac.slice(32, 64));}

In the interest of time, a full DHRatchet implementation is left as an exercise to the reader (since it’s mostly a state machine), but using the appropriate functions provided by sodium-plus (crypto_box_keypair(), crypto_scalarmult()) should be relatively straightforward.

Make sure your KDFs use domain separation, as per the Signal Protocol specifications.

Group Key Agreement

The Signal Protocol specified X3DH and the Double Ratchet for securely encrypting information between two parties.

Group conversations are trickier, because you have to be able to encrypt information that multiple recipients can decrypt, add/remove participants to the conversation, etc.

(The same complexity comes with multi-device support for end-to-end encryption.)

The best design I’ve read to date for tackling group key agreement is the IETF Messaging Layer Security RFC draft.

I am not going to implement the entire MLS RFC in this blog post. If you want to support multiple devices or group conversations, you’ll want a complete MLS implementation to work with.

Brief Recap

That was a lot of ground to cover, but we’re not done yet.

(Art by Khia.)

So far we’ve tackled encryption, initial key agreement, and session key management. However, we did not flesh out how Identity Keys (which are signing keys–Ed25519 specifically–rather than Diffie-Hellman keys) are managed. That detail was just sorta hand-waved until now.

So let’s talk about that.

III. Identity Key Management

There’s a meme among technology bloggers to write a post titled “Falsehoods Programmers Believe About _____”.

Fortunately for us, Identity is one of the topics that furries are positioned to understand better than most (due to fursonas): Identities have a many-to-many relationship with Humans.

In an end-to-end encryption protocol, each identity will consist of some identifier (phone number, email address, username and server hostname, etc.) and an Ed25519 keypair (for which the public key will be published).

But how do you know whether or not a given public key is correct for a given identity?

This is where we segue into one of the hard problems in cryptography, where the solutions available are entirely dependent on your threat model: Public Key Infrastructure (PKI).

Some common PKI designs include:

1. Certificate Authorities (CAs) — TLS does this
2. Web-of-Trust (WoT) — The PGP ecosystem does this
3. Trust On First Use (TOFU) — SSH does this
4. Key Transparency / Certificate Transparency (CT) — TLS also does this for ensuring CA-issued certificates are auditable (although it was originally meant to replace Certificate Authorities)

And you can sort of choose-your-own-adventure on this one, depending on what’s most appropriate for the type of software you’re building and who your customers are.

One design I’m particularly fond of is called Gossamer, which is a PKI design without Certificate Authorities, originally designed for making WordPress’s automatic updates more secure (i.e. so every developer can sign their theme and plugin updates).

Since we only need to maintain an up-to-date repository of Ed25519 identity keys for each participant in our end-to-end encryption protocol, this makes Gossamer a suitable starting point.

Gossamer specifies a limited grammar of Actions that can be performed: AppendKey, RevokeKey, AppendUpdate, RevokeUpdate, and AttestUpdate. These actions are signed and published to an append-only cryptographic ledger.

I would propose a sixth action: AttestKey, so you can have WoT-like assurances and key-signing parties. (If nothing else, you should be able to attest that the identity keys of other cryptographic ledgers in the network are authentic at a point in time.)

IV. Backdoor Resistance

In the previous section, I proposed the use of Gossamer as a PKI for Identity Keys. This would provide Ed25519 keypairs for use with X3DH and the Double Ratchet, which would in turn provide session keys to use for symmetric authenticated encryption.

If you’ve implemented everything preceding this section, you have a full-stack end-to-end encryption protocol. But let’s make intelligence agencies and surveillance capitalists even more mad by making it impractical to backdoor our software (and impossible to silently backdoor it).

How do we pull that off?

You want Binary Transparency.

For us, the implementation is simple: Use Gossamer as it was originally intended (i.e. to secure your software distribution channels).

Gossamer provides up-to-date verification keys and a commitment to a cryptographic ledger of every software update. You can learn more about its inspiration here.

It isn’t enough to merely use Gossamer to manage keys and update signatures. You need independent third parties to use the AttestUpdate action to assert one or more of the following:

1. That builds are reproducible from the source code.
2. That they have reviewed the source code and found no evidence of backdoors or exploitable vulnerabilities.

(And then you should let your users decide which of these independent third parties they trust to vet software updates.)

Closing Remarks

The U.S. Government cries and moans a lot about “criminals going dark” and wonders a lot about how to solve the “going dark problem”.

If more software developers implement end-to-end encryption in their communications software, then maybe one day they won’t be able to use dragnet surveillance to spy on citizens and they’ll be forced to do actual detective work to solve actual crimes.

Y’know, like their job description actually entails?

Let’s normalize end-to-end encryption. Let’s normalize backdoor-resistant software distribution.

Let’s collectively tell the intelligence community in every sophisticated nation state the one word they don’t hear often enough:

Especially if you’re a furry. Because we improve everything! :3

Questions You Might Have

What About Private Contact Discovery?

That’s one of the major reasons why the thing we’re building isn’t meant to compete with Signal (and it MUST NOT be advertised as such):

Signal is a privacy tool, and their servers have no way of identifying who can contact who.

What we’ve built here isn’t a complete privacy solution, it’s only providing end-to-end encryption (and possibly making NSA employees cry at their desk).

Does This Design Work with Federation?

Yes. Each identifier string can be [username] at [hostname].

What About Network Metadata?

If you want anonymity, you want to use Tor.

Why Are You Using Ed25519 Keys for X3DH?

If you only read the key agreement section of this blog post and the fact that I’m passing around Ed25519 public keys seems weird, you might have missed the identity section of this blog post where I suggested piggybacking on another protocol called Gossamer to handle the distribution of Ed25519 public keys. (Gossamer is also beneficial for backdoor resistance in software update distribution, as described in the subsequent section.)

Furthermore, we’re actually using birationally equivalent X25519 keys derived from the Ed25519 keypair for the X3DH step. This is a deviation from what Signal does (using X25519 keys everywhere, then inventing an EdDSA variant to support their usage).

const publicKeyX = await sodium.crypto_sign_ed25519_pk_to_curve25519(foxPublicKey);const secretKeyX = await sodium.crypto_sign_ed25519_sk_to_curve25519(wolfSecretKey);

(Using fox/wolf instead of Alice/Bob, because it’s cuter.)

This design pattern has a few advantages:

1. It makes Gossamer integration seamless, which means you can use Ed25519 for identities and still have a deniable X3DH handshake for 1:1 conversations while implementing the rest of the designs proposed.
2. This approach to X3DH can be implemented entirely with libsodium functions, without forcing you to write your own cryptography implementations (i.e. for XEdDSA).

The only disadvantages I’m aware of are:

1. It deviates from Signal’s core design in a subtle way that means you don’t get to claim the exact same advantages Signal does when it comes to peer review.
2. Some cryptographers are distrustful of the use of birationally equivalent X25519 keys from Ed25519 keys (although there isn’t a vulnerability any of them have been able to point me to that doesn’t involve torsion groups–which libsodium’s implementation already avoids).

If these concerns are valid enough to decide against my implementation above, I invite you to talk with cryptographers about your concerns and then propose alternatives.

Has Any of This Been Implemented Already?

You can find implementations for the designs discussed on this blog post below:

• Rawr-X3DH implements X3DH in TypeScript (added 2020-11-23)

I will update this section of the blog post as implementations surface.

https://soatok.blog/2020/11/14/going-bark-a-furrys-guide-to-end-to-end-encryption/

#authenticatedEncryption #authenticatedKeyExchange #crypto #cryptography #encryption #endToEndEncryption #libsodium #OnlinePrivacy #privacy #SecurityGuidance #symmetricEncryption

Dhole Moments

2020-10-28 15:44:22

Zoom recently announced that they were going to make end-to-end encryption available to all of their users–not just customers.

https://twitter.com/zoom_us/status/1320760108343652352

This is a good move, especially for people living in countries with inept leadership that failed to address the COVID-19 pandemic and therefore need to conduct their work and schooling remotely through software like Zoom. I enthusiastically applaud them for making this change.

End-to-end encryption, on by default, is a huge win for everyone who uses Zoom. (Art by Khia.)

The end-to-end encryption capability arrives on the heels of their acquisition of Keybase in earlier this year. Hiring a team of security experts and cryptography engineers seems like a good move overall.

Upon hearing this news, I decided to be a good neighbor and take a look at their source code, with the reasoning, “If so many people’s privacy is going to be dependent on Zoom’s security, I might as well make sure they’re not doing something ridiculously bad.”

Except I couldn’t find their source code anywhere online. But they did publish a white paper on Github…

(Art by Khia.)

Disclaimers

What follows is the opinion of some guy on the Internet with a fursona–so whether or not you choose to take it seriously should be informed by this context. It is not the opinion of anyone’s employer, nor is it endorsed by Zoom, etc. Tell your lawyers to calm their nips.

More importantly, I’m not here to hate on Zoom for doing a good thing, nor on the security experts that worked hard on making Zoom better for their users. The responsibility of security professionals is to the users, after all.

Also, these aren’t zero-days, so don’t try to lecture me about “responsible” disclosure. (That term is also problematic, by the way.)

Got it? Good. Let’s move on.

(Art by Swizz.)

Bizarre Design Choices in Version 2.3 of Zoom’s E2E White Paper

Note: I’ve altered the screenshots to be white text on a black background, since my blog’s color scheme is darker than a typical academic PDF. You can find the source here.

Cryptographic Algorithms

It’s a little weird that they’re calculating a signature over SHA256(Context) || SHA256(M), considering Ed25519 uses SHA512 internally.

It would make just as much sense to sign Context || M directly–or, if pre-hashing large streams is needed, SHA512(Context || M).

At the top of this section, it says it uses libsodium’s crypto_box interface. But then they go onto… not actually use it.

Instead, they wrote their own protocol using HKDF, two SHA256 hashes, and XChaCha20-Poly1305.

While secure, this isn’t really using the crypto_box interface.

The only part of the libsodium interface that’s being used is [url=https://github.com/jedisct1/libsodium/blob/927dfe8e2eaa86160d3ba12a7e3258fbc322909c/src/libsodium/crypto_box/curve25519xsalsa20poly1305/box_curve25519xsalsa20poly1305.c#L35-L46]crypto_box_beforenm()[/url], which could easily have been a call to crypto_scalarmult()instead (since they’re passing the output of the scalar multiplication to HKDF anyway).

(Art by Riley.)

Also, the SHA256(a) || SHA256(b) pattern returns. Zoom’s engineers must love SHA256 for some reason.

This time, it’s in the additional associated data for the XChaCha20-Poly1305.

Binding the ciphertext and the signature to the same context string is a sensible thing to do, it’s just the concatenation of SHA256 hashes is a bit weird when SHA512 exists.

Meeting Leader Security Code

Here we see Zoom using the a SHA256 of a constant string (“Zoombase-1-ClientOnly-MAC-SecurityCode“) in a construction that tries but fails to be HMAC.

And then they concatenate it with the SHA256 hash of the public key (which is already a 256-bit value), and then they hash the whole thing again.

It’s redundant SHA256 all the way down. The redundancy of “MAC” and “SecurityCode” in their constant string is, at least, consistent with the rest of their design philosophy.

It would be a real shame if double-hashing carried the risk of invalidating security proofs, or if the security proof for HMAC required a high Hamming distance of padding constants and this design decision also later saved HMAC from related-key attacks.

Hiding Personal Details

Wait, you’re telling me Zoom was aware of HMAC’s existence this whole time?

I give up!

Enough Pointless Dunking, What’s the Takeaway?

None of the design decisions Zoom made that I’ve criticized here are security vulnerabilities, but they do demonstrate an early lack of cryptography expertise in their product design.

After all, the weirdness is almost entirely contained in section 3 of their white paper, which describes the “Phase I” of their rollout. So what I’ve pointed out here appears to be mostly legacy cruft that wasn’t risky enough to bother changing in their final design.

The rest of their paper is pretty straightforward and pleasant to read. Their design makes sense in general, and each phase includes an “Areas to Improve” section.

All in all, if you’re worried about the security of Zoom’s E2EE feature, the only thing they can really do better is to publish the source code (and link to it from the whitepaper repository for ease-of-discovery) for this feature so independent experts can publicly review it.

However, they seem to be getting a lot of mileage out of the experts on their payroll, so I wouldn’t count on that happening.

https://soatok.blog/2020/10/28/bizarre-design-choices-in-zooms-end-to-end-encryption/

#encryption #endToEndEncryption #zoom

Earlier this week, security researcher Ryan Castellucci published a blog post with a somewhat provocative title: DKIM: Show Your Privates.

After reading the ensuing discussions on Hacker News and Reddit about their DKIM post, it seems clear that the importance of deniability in online communications seems to have been broadly overlooked.

Security Goals, Summarized

(Art by Swizz.)

When you design or implement any communications protocol, you typically have most or all of the following security goals:

• Confidentiality: Only the intended recipients can understand the contents of a message (almost always achieved through encryption).
• Integrity: The message will be delivered without alterations; and if it is, the recipient will know to reject it.
• Availability: Authorized users will have access to the resources they need (i.e. a medium they can communicate through).

However, you may also have one or more of the following security goals:

• Authenticity: In a group communication protocol, you want to ensure you can validate which participant sent each message. This is loosely related to, yet independent from, integrity.
• Non-Repudiation: An extension of authenticity, wherein you cannot deny that you sent a message after you sent it; it’s provable that you sent it.
• Deniability: The complement to non-repudiation, wherein you can prove that you sent a message to your recipient, and then at a future time make it possible for other participants to have forged the message.

It’s tempting to think of deniability as the opposite of non-repudiation, but in practice, you want messages to have authenticity for at least a brief period of time for both.

However, you cannot simultaneously have deniability and non-repudiation in a communication. They’re mutually exclusive concepts, even if they both build off authenticity. Hence, I call it a complement.

Off-The-Record messaging achieved deniability through publishing the signing key of the previous message with each additional message.

Security Properties of DKIM

Ryan Castellucci’s blog post correctly observed that the anti-spam protocol DKIM, as used by most mail providers in 2020, incidentally also offers non-repudiation…even if that’s not supposed to be a primary goal of DKIM.

Non-repudiation can be bolted onto any protocol with long-term asymmetric cryptographic keys used to generate digital signatures of messages–which is exactly what DKIM does.

Real World Case Study

A while ago, the New York Post published a DKIM-signed email from someone claiming to be named Vadym Pozharskyi to Hunter Biden–son of the presidential candidate and former Vice President Joe Biden.

Because the DKIM public keys used by Gmail during that time period are known–but not the private keys–it’s possible to authenticate that the emails came from Gmail and is a valid email. And someone did exactly this.

In a similar vein, if someone wanted to embarrass an executive at a large company, accessing their colleagues’ email and leaking messages would be sufficient, since DKIM could be used to verify that the emails are authentic.

Deniability in DKIM

Ryan’s proposal for introducing deniability in DKIM was to routinely rotate signing keys and publish fragments of their old DKIM private keys (which are RSA keys) so that anyone can reconstruct the private key after-the-fact.

This kind of deniability is mostly to mitigate against the harm of data leaks–such as your friend’s laptop getting stolen and someone trying to lambaste you on social media for an email you sent 10+ years ago–rather than provide a legal form of deniability. (We’re cryptography nerds, not lawyers.)

If the laptop theft scenario took place, with DKIM, someone can cryptographically prove you sent the email at a specific time to your friend with a specific body, because it’s signed by (presumably Gmail’s) DKIM keys.

Conversely, if you had used an email provider that practiced what Ryan proposed (rotating/publishing the private key at a regular interval), they couldn’t cryptographically prove anything. If the past private keys are public, anyone could have come along and forged the DKIM signature.

On Post-Compromise Security

The concept of Post-Compromise Security is somewhat related to deniability (but affects confidentiality rather than integrity or authenticity):

If someone successfully compromises one participant in a private discussion group, and their access is discovered, can the rest of the participants recover from this breach and continue to have privacy for future conversations?

It’s easy to see how the concepts are related.

• Deniability offers short-term authenticity followed by a long-term break in authenticity.
• Post-Compromise Security offers long-term confidentiality even if there’s a short-term break in confidentiality.

Robust private messaging protocols–such as what the IETF is trying to provide with Message Layer Security–would ideally offer both properties to their users.

Past attempts to build non-repudiation (through “message franking”) on top of cipher constructions like AES-GCM led to a class of attacks known affectionately as Invisible Salamanders, based on the title of the relevant research paper.

In Conclusion

https://twitter.com/matthew_d_green/status/1323011619069321216

It might seem really weird for cryptographers to want large-scale email providers to publish their expired DKIM secret keys, but when you understand the importance of deniability in past private communications, it’s a straightforward thing to want.

It’s worth noting: Some security experts will push back on this, because they work in computer forensics, and making DKIM deniable would theoretically make their job slightly more difficult.

Keep their self-interest in mind when they’re complaining about this notion, since the proposal is not to publish non-expired DKIM secret keys, and therefore it would not make spam more challenging to combat.

https://soatok.blog/2020/11/04/a-brief-introduction-to-deniability/

#cryptography #deniability #OnlinePrivacy #securityGoals #Technology

Dhole Moments

2020-05-13 10:00:22

If you’re reading this wondering if you should stop using AES-GCM in some standard protocol (TLS 1.3), the short answer is “No, you’re fine”.

I specialize in secure implementations of cryptography, and my years of experience in this field have led me to dislike AES-GCM.

This post is about why I dislike AES-GCM’s design, not “why AES-GCM is insecure and should be avoided”. AES-GCM is still miles above what most developers reach for when they want to encrypt (e.g. ECB mode or CBC mode). If you want a detailed comparison, read this.

To be clear: This is solely my opinion and not representative of any company or academic institution.

What is AES-GCM?

AES-GCM is an authenticated encryption mode that uses the AES block cipher in counter mode with a polynomial MAC based on Galois field multiplication.

In order to explain why AES-GCM sucks, I have to first explain what I dislike about the AES block cipher. Then, I can describe why I’m filled with sadness every time I see the AES-GCM construction used.

What is AES?

The Advanced Encryption Standard (AES) is a specific subset of a block cipher called Rijndael.

Rijndael’s design is based on a substitution-permutation network, which broke tradition from many block ciphers of its era (including its predecessor, DES) in not using a Feistel network.

AES only includes three flavors of Rijndael: AES-128, AES-192, and AES-256. The difference between these flavors is the size of the key and the number of rounds used, but–and this is often overlooked–not the block size.

As a block cipher, AES always operates on 128-bit (16 byte) blocks of plaintext, regardless of the key size.

This is generally considered acceptable because AES is a secure pseudorandom permutation (PRP), which means that every possible plaintext block maps directly to one ciphertext block, and thus birthday collisions are not possible. (A pseudorandom function (PRF), conversely, does have birthday bound problems.)

Why AES Sucks

Art by Khia.

Side-Channels

The biggest reason why AES sucks is that its design uses a lookup table (called an S-Box) indexed by secret data, which is inherently vulnerable to cache-timing attacks (PDF).

There are workarounds for this AES vulnerability, but they either require hardware acceleration (AES-NI) or a technique called bitslicing.

The short of it is: With AES, you’re either using hardware acceleration, or you have to choose between performance and security. You cannot get fast, constant-time AES without hardware support.

Block Size

AES-128 is considered by experts to have a security level of 128 bits.

Similarly, AES-192 gets certified at 192-bit security, and AES-256 gets 256-bit security.

However, the AES block size is only 128 bits!

That might not sound like a big deal, but it severely limits the constructions you can create out of AES.

Consider the case of AES-CBC, where the output of each block of encryption is combined with the next block of plaintext (using XOR). This is typically used with a random 128-bit block (called the initialization vector, or IV) for the first block.

This means you expect a collision after encrypting (at 50% probability) blocks.

When you start getting collisions, you can break CBC mode, as this video demonstrates:

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

This is significantly smaller than the you expect from AES.

Post-Quantum Security?

With respect to the number of attempts needed to find the correct key, cryptographers estimate that AES-128 will have a post-quantum security level of 64 bits, AES-192 will have a post-quantum security level of 96 bits, and AES-256 will have a post-quantum security level of 128 bits.

This is because Grover’s quantum search algorithm can search unsorted items in time, which can be used to reduce the total number of possible secrets from to . This effectively cuts the security level, expressed in bits, in half.

Note that this heuristic estimate is based on the number of guesses (a time factor), and doesn’t take circuit size into consideration. Grover’s algorithm also doesn’t parallelize well. The real-world security of AES may still be above 100 bits if you consider these nuances.

But remember, even AES-256 operates on 128-bit blocks.

Consequently, for AES-256, there should be approximately (plaintext, key) pairs that produce any given ciphertext block.

Furthermore, there will be many keys that, for a constant plaintext block, will produce the same ciphertext block despite being a different key entirely. (n.b. This doesn’t mean for all plaintext/ciphertext block pairings, just some arbitrary pairing.)

Concrete example: Encrypting a plaintext block consisting of sixteen NUL bytes will yield a specific 128-bit ciphertext exactly once for each given AES-128 key. However, there are times as many AES-256 keys as there are possible plaintext/ciphertexts. Keep this in mind for AES-GCM.

This means it’s conceivable to accidentally construct a protocol that, despite using AES-256 safely, has a post-quantum security level on par with AES-128, which is only 64 bits.

This would not be nearly as much of a problem if AES’s block size was 256 bits.

Real-World Example: Signal

The Signal messaging app is the state-of-the-art for private communications. If you were previously using PGP and email, you should use Signal instead.

Signal aims to provide private communications (text messaging, voice calls) between two mobile devices, piggybacking on your pre-existing contacts list.

Part of their operational requirements is that they must be user-friendly and secure on a wide range of Android devices, stretching all the way back to Android 4.4.

The Signal Protocol uses AES-CBC + HMAC-SHA256 for message encryption. Each message is encrypted with a different AES key (due to the Double Ratchet), which limits the practical blast radius of a cache-timing attack and makes practical exploitation difficult (since you can’t effectively replay decryption in order to leak bits about the key).

Thus, Signal’s message encryption is still secure even in the presence of vulnerable AES implementations.

Hooray for well-engineered protocols managing to actually protect users.
Art by Swizz.

However, the storage service in the Signal App uses AES-GCM, and this key has to be reused in order for the encrypted storage to operate.

This means, for older phones without dedicated hardware support for AES (i.e. low-priced phones from 2013, which Signal aims to support), the risk of cache-timing attacks is still present.

This is unacceptable!

What this means is, a malicious app that can flush the CPU cache and measure timing with sufficient precision can siphon the AES-GCM key used by Signal to encrypt your storage without ever violating the security boundaries enforced by the Android operating system.

As a result of the security boundaries never being crossed, these kind of side-channel attacks would likely evade forensic analysis, and would therefore be of interest to the malware developers working for nation states.

Of course, if you’re on newer hardware (i.e. Qualcomm Snapdragon 835), you have hardware-accelerated AES available, so it’s probably a moot point.

Why AES-GCM Sucks Even More

AES-GCM is an authenticated encryption mode that also supports additional authenticated data. Cryptographers call these modes AEAD.

AEAD modes are more flexible than simple block ciphers. Generally, your encryption API accepts the following:

1. The plaintext message.
2. The encryption key.
3. A nonce (: A number that must only be used once).
4. Optional additional data which will be authenticated but not encrypted.

The output of an AEAD function is both the ciphertext and an authentication tag, which is necessary (along with the key and nonce, and optional additional data) to decrypt the plaintext.

Cryptographers almost universally recommend using AEAD modes for symmetric-key data encryption.

That being said, AES-GCM is possibly my least favorite AEAD, and I’ve got good reasons to dislike it beyond simply, “It uses AES”.

The deeper you look into AES-GCM’s design, the harder you will feel this sticker.

GHASH Brittleness

The way AES-GCM is initialized is stupid: You encrypt an all-zero block with your AES key (in ECB mode) and store it in a variable called . This value is used for authenticating all messages authenticated under that AES key, rather than for a given (key, nonce) pair.
Diagram describing Galois/Counter Mode, taken from Wikipedia.
This is often sold as an advantage: Reusing allows for better performance. However, it makes GCM brittle: Reusing a nonce allows an attacker to recover H and then forge messages forever. This is called the “forbidden attack”, and led to real world practical breaks.

Let’s contrast AES-GCM with the other AEAD mode supported by TLS: ChaCha20-Poly1305, or ChaPoly for short.

ChaPoly uses one-time message authentication keys (derived from each key/nonce pair). If you manage to leak a Poly1305 key, the impact is limited to the messages encrypted under that (ChaCha20 key, nonce) pair.

While that’s still bad, it isn’t “decrypt all messages under that key forever” bad like with AES-GCM.

Note: “Message Authentication” here is symmetric, which only provides a property called message integrity, not sender authenticity. For the latter, you need asymmetric cryptography (wherein the ability to verify a message doesn’t imply the capability to generate a new signature), which is totally disparate from symmetric algorithms like AES or GHASH. You probably don’t need to care about this nuance right now, but it’s good to know in case you’re quizzed on it later.

H Reuse and Multi-User Security

If you recall, AES operates on 128-bit blocks even when 256-bit keys are used.

If we assume AES is well-behaved, we can deduce that there are approximately different 256-bit keys that will map a single plaintext block to a single ciphertext block.

This is trivial to calculate. Simply divide the number of possible keys () by the number of possible block states () to yield the number of keys that produce a given ciphertext for a single block of plaintext: .

Each key that will map an arbitrarily specific plaintext block to a specific ciphertext block is also separated in the keyspace by approximately .

This means there are approximately independent keys that will map a given all-zero plaintext block to an arbitrarily chosen value of (if we assume AES doesn’t have weird biases).

Credit: Harubaki

“Why Does This Matter?”

It means that, with keys larger than 128 bits, you can model the selection of as a 128-bit pseudorandom function, rather than a 128-bit permutation. As a result, you an expect a collision with 50% probability after only different keys are selected.

Note: Your 128-bit randomly generated AES keys already have this probability baked into their selection, but this specific analysis doesn’t really apply for 128-bit keys since AES is a PRP, not a PRF, so there is no “collision” risk. However, you end up at the same upper limit either way.

But 50% isn’t good enough for cryptographic security.

In most real-world systems, we target a collision risk. So that means our safety limit is actually different AES keys before you have to worry about reuse.

This isn’t the same thing as symmetric wear-out (where you need to re-key after a given number of encryptions to prevent nonce reuse). Rather, it means after your entire population has exhausted the safety limit of different AES keys, you have to either accept the risk or stop using AES-GCM.

If you have a billion users (), the safety limit is breached after AES keys per user (approximately 262,000).

“What Good is H Reuse for Attackers if HF differs?”

There are two numbers used in AES-GCM that are derived from the AES key. is used for block multiplication, and (the value of with a counter of 0 from the following diagram) is XORed with the final result to produce the authentication tag.

The arrow highlighted with green is HF.

It’s tempting to think that a reuse of isn’t a concern because will necessarily be randomized, which prevents an attacker from observing when collides. It’s certainly true that the single-block collision risk discussed previously for will almost certainly not also result in a collision for . And since isn’t reused unless a nonce is reused (which also leaks directly), this might seem like a non-issue.

Art by Khia.

However, it’s straightforward to go from a condition of reuse to an adaptive chosen-ciphertext attack.

1. Intercept multiple valid ciphertexts.
   
   • e.g. Multiple JWTs encrypted with {"alg":"A256GCM"}

   
   

2. Use your knowledge of , the ciphertext, and the AAD to calculate the GCM tag up to the final XOR. This, along with the existing authentication tag, will tell you the value of for a given nonce.
3. Calculate a new authentication tag for a chosen ciphertext using and your candidate value, then replay it into the target system.

While the blinding offered by XORing the final output with is sufficient to stop from being leaked directly, the protection is one-way.

Ergo, a collision in is not sufficiently thwarted by .

“How Could the Designers Have Prevented This?”

The core issue here is the AES block size, again.

If we were analyzing a 256-bit block variant of AES, and a congruent GCM construction built atop it, none of what I wrote in this section would apply.

However, the 128-bit block size was a design constraint enforced by NIST in the AES competition. This block size was during an era of 64-bit block ciphers (e.g. Triple-DES and Blowfish), so it was a significant improvement at the time.

NIST’s AES competition also inherited from the US government’s tradition of thinking in terms of “security levels”, which is why there are three different permitted key sizes (128, 192, or 256 bits).

“Why Isn’t This a Vulnerability?”

There’s always a significant gap in security, wherein something isn’t safe to recommend, but also isn’t susceptible to a known practical attack. This gap is important to keep systems secure, even when they aren’t on the bleeding edge of security.

Using 1024-bit RSA is a good example of this: No one has yet, to my knowledge, successfully factored a 1024-bit RSA public key. However, most systems have recommended a minimum 2048-bit for years (and many recommend 3072-bit or 4096-bit today).

With AES-GCM, the expected distance between collisions in is , and finding an untargeted collision requires being able to observe more than different sessions, and somehow distinguish when collides.

As a user, you know that after different keys, you’ve crossed the safety boundary for avoiding collisions. But as an attacker, you need bites at the apple, not . Additionally, you need some sort of oracle or distinguisher for when this happens.

We don’t have that kind of distinguisher available to us today. And even if we had one available, the amount of data you need to search in order for any two users in the population to reuse/collide is challenging to work with. You would need the computational and data storages of a major cloud service provider to even think about pulling the attack off.

Naturally, this isn’t a practical vulnerability. This is just another gripe I have with AES-GCM, as someone who has to work with cryptographic algorithms a lot.

Short Nonces

Although the AES block size is 16 bytes, AES-GCM nonces are only 12 bytes. The latter 4 bytes are dedicated to an internal counter, which is used with AES in Counter Mode to actually encrypt/decrypt messages.

(Yes, you can use arbitrary length nonces with AES-GCM, but if you use nonces longer than 12 bytes, they get hashed into 12 bytes anyway, so it’s not a detail most people should concern themselves with.)

If you ask a cryptographer, “How much can I encrypt safely with AES-GCM?” you’ll get two different answers.

1. Message Length Limit: AES-GCM can be used to encrypt messages up to bytes long, under a given (key, nonce) pair.
2. Number of Messages Limit: If you generate your nonces randomly, you have a 50% chance of a nonce collision after messages.
   However, 50% isn’t conservative enough for most systems, so the safety margin is usually much lower. Cryptographers generally set the key wear-out of AES-GCM at random nonces, which represents a collision probability of one in 4 billion.

These limits are acceptable for session keys for encryption-in-transit, but they impose serious operational limits on application-layer encryption with long-term keys.

Random Key Robustness

Before the advent of AEAD modes, cryptographers used to combine block cipher modes of operation (e.g. AES-CBC, AES-CTR) with a separate message authentication code algorithm (e.g. HMAC, CBC-MAC).

You had to be careful in how you composed your protocol, lest you invite Cryptographic Doom into your life. A lot of developers screwed this up. Standardized AEAD modes promised to make life easier.

Many developers gained their intuition for authenticated encryption modes from protocols like Signal’s (which combines AES-CBC with HMAC-SHA256), and would expect AES-GCM to be a drop-in replacement.

Unfortunately, GMAC doesn’t offer the same security benefits as HMAC: Finding a different (ciphertext, HMAC key) pair that produces the same authentication tag is a hard problem, due to HMAC’s reliance on cryptographic hash functions. This makes HMAC-based constructions “message committing”, which instills Random Key Robustness.

Critically, AES-GCM doesn’t have this property. You can calculate a random (ciphertext, key) pair that collides with a given authentication tag very easily.

This fact prohibits AES-GCM from being considered for use with OPAQUE (which requires RKR), one of the upcoming password-authenticated key exchange algorithms. (Read more about them here.)

Better-Designed Algorithms

You might be thinking, “Okay random furry, if you hate AES-GCM so much, what would you propose we use instead?”

I’m glad you asked!

XChaCha20-Poly1305

For encrypting messages under a long-term key, you can’t really beat XChaCha20-Poly1305.

• ChaCha is a stream cipher based on a 512-bit ARX hash function in counter mode. ChaCha doesn’t use S-Boxes. It’s fast and constant-time without hardware acceleration.
• ChaCha20 is ChaCha with 20 rounds.
• XChaCha nonces are 24 bytes, which allows you to generate them randomly and not worry about a birthday collision until about messages (for the same collision probability as AES-GCM).
• Poly1305 uses different 256-bit key for each (nonce, key) pair and is easier to implement in constant-time than AES-GCM.
• XChaCha20-Poly1305 uses the first 16 bytes of the nonce and the 256-bit key to generate a distinct subkey, and then employs the standard ChaCha20-Poly1305 construction used in TLS today.

For application-layer cryptography, XChaCha20-Poly1305 contains most of the properties you’d want from an authenticated mode.

However, like AES-GCM (and all other Polynomial MACs I’ve heard of), it is not message committing.

The Gimli Permutation

For lightweight cryptography (n.b. important for IoT), the Gimli permutation (e.g. employed in libhydrogen) is an attractive option.

Gimli is a Round 2 candidate in NIST’s Lightweight Cryptography project. The Gimli permutation offers a lot of applications: a hash function, message authentication, encryption, etc.

Critically, it’s possible to construct a message-committing protocol out of Gimli that will hit a lot of the performance goals important to embedded systems.

Closing Remarks

Despite my personal disdain for AES-GCM, if you’re using it as intended by cryptographers, it’s good enough.

Don’t throw AES-GCM out just because of my opinions. It’s very likely the best option you have.

Although I personally dislike AES and GCM, I’m still deeply appreciative of the brilliance and ingenuity that went into both designs.

My desire is for the industry to improve upon AES and GCM in future cipher designs so we can protect more people, from a wider range of threats, in more diverse protocols, at a cheaper CPU/memory/time cost.

We wouldn’t have a secure modern Internet without the work of Vincent Rijmen, Joan Daemen, John Viega, David A. McGrew, and the countless other cryptographers and security researchers who made AES-GCM possible.

Change Log

• 2021-10-26: Added section on H Reuse and Multi-User Security.

https://soatok.blog/2020/05/13/why-aes-gcm-sucks/

#AES #AESGCM #cryptography #GaloisCounterMode #opinion #SecurityGuidance #symmetricCryptography