Katzenpost threat model document

Here we present a draft of the Katzenpost mixnet threat model document. We regard the threat model document as a living document which is frequently edited and in need of ongoing maintenance as we continue to develop newer mixnet protocols. Currently it is being organized by mixnet attack category and we have arranged attacks in a table with corresponding attacker capabilities. Later sections of the document present a deep dive into the core cryptographic protocols that comprise Katzenpost, namely these three:

  1. Katzenpost Directory Authority PKI protocol
  2. PQ Noise based wire protocol (on top of TCP or QUIC)
  3. Sphinx nested encrypted packet routing protocol

Those are the basics necessary for point to point communications through the mix network. However mixnet protocols will then add their own cryptographic protocols which simply make use of the above three protocols in service to their goals of message transportation.

We thank Wau Holland Stiftung for funding this work.

Threat Model Doc

Mixnet Literature Overview

Foundational work

We are presenting our overview of existing Mixnet literature. It takes some liberties with what is included or not. It proposes new ways to talk about some issues, and provides a critical analysis of some of the existing papers. It also endeavors to introduce the reader to the language of anonymity systems, while maintaining mathematical rigor.

This doc, in particular, does not talk about the Katzenpost design. It does introduce the reader to some of the reasons why we’ve been making certain design decisions, and a keen eye might be led to some of the similar conclusions. But here we focus on already published research. We also stick to theory and don’t focus on any practical systems being built today.

The specific networking decisions implemented in Katzenpost so far, and the threats they mitigate and don’t, will be addressed in an upcoming, detailed threat model document.

We thank Wau Holland Stiftung for funding this work.

Lit Review Doc

Note form Eva: I understand that the tone of some of this analysis may come across as harsh. I personally take full responsibility for this tone and critique in particular.

At the same time, the point of this doc is not to present original research. Some exploitable mistakes in existing research were withheld from this version, and original contributions are included if I, personally, feel like they are merely reinventing the wheel in bridging some of the gaps between Mixnets and Mathematics. Some of the other original research is mentioned, but will be expanded on elsewhere.

hpqc - hybrid post quantum cryptography library

The Katzenpost developement team has recently released a new golang cryptography library known as hpqc. The theme of the library is hybrid post quantum cryptographic constructions, namely:

  • hybrid KEMs (key encapsulation mechanism)
  • hybrid NIKEs (non-interactive key exchange)
  • hybrid signature schemes

In each of the three main subdirectories, “kem”, “nike” and “sign” there exists interface definitions for Scheme, PrivateKey and PublicKey. For signature schemes and KEMs we’re borrowing the interface sets from cloudflare’s circl library.

And each of these subdirectories has a schemes package where all the imeplementations are registered and can be referenced by unique string name, take for examples the KEM schemes documentation. However the implementations that are registered don’t show up in the API docs but we can see them in the source code.

hpqc gives you the power to compose an arbitrary number of KEMs and NIKEs, for example the above source file defines many KEMs in composition like this one:

	combiner.New(
		"X25519-mlkem768-ctidh512",
		[]kem.Scheme{
			adapter.FromNIKE(x25519.Scheme(rand.Reader)),
			mlkem768.Scheme(),
			adapter.FromNIKE(ctidh512.Scheme()),
		},
	),

This library makes seven unique contributions in golang:

  1. a set of generic NIKE interfaces for NIKE scheme, public key and private key types

NIKE interfaces documentation source code

These are useful for making your cryptographic protocol not rely on a specific NIKE such as an elliptic curve diffiehellman function like x25519 or x448.

  1. generic hybrid NIKE, combines any two NIKEs into one

NIKE hybrid scheme documentation source code

Many cryptographic protocols can use a hybrid post quantum NIKE in place of a NIKE. Here the NIKE interfaces are satisfied by this hybrid scheme type.

  1. security preserving KEM combiner

security preserving KEM combiner documentation source code

Our security preserving KEM combiner can combine an arbitrary number of KEMs althought it’s usually useful enough to combine just two KEMs. We get our design from the KEM Combiners paper which makes the observation that if a KEM combiner is not security preserving then the resulting hybrid KEM will not have IND-CCA2 security if one of the composing KEMs does not have IND-CCA2 security. Likewise the paper points out that when using a security preserving KEM combiner, if only one of the composing KEMs has IND-CCA2 security then the resulting hybrid KEM will have IND-CCA2 security.

Our KEM combiner uses the split PRF design for an arbitrary number of KEMs, here shown with only three, in pseudo code:

func SplitPRF(ss1, ss2, ss3, cct1, cct2, cct3 []byte) []byte {
    cct := cct1 || cct2 || cct3
    return PRF(ss1 || cct) XOR PRF(ss2 || cct) XOR PRF(ss3 || cct)
}
  1. a “NIKE to KEM adapter” which uses an ad hoc hashed elgamal construction

NIKE to KEM adapter documentation source code

It is very common in modern hybrid post quantum cryptographic protocol constructions to see a NIKE adapted into a KEM and then combined with a post quantum KEM.

Our ad hoc hashed elgamal construction for adapting any NIKE to a KEM is, in pseudo code:

func ENCAPSULATE(their_pubkey publickey) ([]byte, []byte) {
    my_privkey, my_pubkey = GEN_KEYPAIR(RNG)
    ss = DH(my_privkey, their_pubkey)
    ss2 = PRF(ss || their_pubkey || my_pubkey)
    return my_pubkey, ss2
}

func DECAPSULATE(my_privkey, their_pubkey) []byte {
    s = DH(my_privkey, their_pubkey)
    shared_key = PRF(ss || my_pubkey || their_pubkey)
    return shared_key
}
  1. cgo bindings for the Sphincs+ C reference source

Our Sphincs+ wrapper conforms to the signature scheme interfaces:

Sphincs+ signature scheme documentation source code

We maintain our Sphincs+ C reference fork and golang bindings in this git repo: https://github.com/katzenpost/sphincsplus/

Here’s the cgo bindings source code: https://github.com/katzenpost/sphincsplus/blob/main/ref/binding.go

  1. cgo bindings for the CTIDH C source

Our CTIDH golang bindings have been much improved through collaboration and are now maintained by the Vula project in this git repo:

https://codeberg.org/vula/highctidh

hpqc currently has a wrapper type for each CTIDH key size, as documented here:

https://pkg.go.dev/github.com/katzenpost/hpqc@v0.0.17/nike/ctidh/ctidh511 https://pkg.go.dev/github.com/katzenpost/hpqc@v0.0.17/nike/ctidh/ctidh512 https://pkg.go.dev/github.com/katzenpost/hpqc@v0.0.17/nike/ctidh/ctidh1024 https://pkg.go.dev/github.com/katzenpost/hpqc@v0.0.17/nike/ctidh/ctidh2048

  1. generic hybrid signature scheme, combines any two signature schemes into one

It is useful to combine a classical signature scheme such as ed25519 with a post quantum signature scheme such as Sphincs+.

hybrid signature scheme documentation source code

Katzenpost at 37C3

The session we held at Chaos Communication Congress

Dr. Eva Infeld and surveillance expert and developer Leif Ryge held a session at the Chaos Communication Congress about the current state of the project, some of the things we’re working on, and some of the pitfalls many anonymity systems fall into. Building an anonymity system fit for our dystopian age is a hard problem, but we’re doing it.

Katzenpost talk on YouTube

Audio Engineering Considerations for a Modern Mixnet

Original research into audio engineering considerations for apps on low latency mixnetworks

Modern Mixnets have a unique set of requirements when it comes to processing audio. The bandwidth is scarce, but we expect to use modern devices and have ample processing power. We aim to secure the communication against even sophisticated attacks that come from capturing the metadata, and prioritize tools that are free, open source and written with security in mind. In this unique setting, we present a set of recommendations for implementing codecs, DSPs, and sophisticated noise reduction tools, to deliver either impressive quality at low bandwidth or good quality at impressively low bandwidth.

Read Research Paper

Audio Engineering Considerations for a Modern Mixnet
PDF / 295K

Website Relaunch and migration to Hugo

To match all the code development in Katzenpost in the last year, it was time for a website relaunch. Our site was a migration from Sphincs to Hugo and utilizes the well crafted and maintained Docsy theme.

To match all the code development in Katzenpost in the last year, it was time for a website relaunch. Our site was a migration from Sphinx, which is primarily for documentation, to Hugo which is wildly configurable for all sorts of websites. Given the technical nature and need for nice documentation interface, we used the well crafted and maintained Docsy theme.

Website Dependencies

Monthly News Update (May 2019)

Greetings,

The last few weeks have been very busy. I now have the basic working prototype implementation of a new Katzenpost messaging system. This new system has mutual location hiding properties for communication partners because recipients retreive their messages from a remote spool using a Sphinx SURB based protocol. SPHINX SPHINXSPEC

Naming things is tricky. I had to call it something:

This messaging system is inspired by agl’s pond, obviously. See agl’s pond.

I forked agl’s Double Ratchet from pond:

Also forked agl’s PANDA:

Communication partners use a remote spool service which is now, memspool but later it will be a replicating CRDT:

In order to exchange double ratchet keys and spool identities to form a bidirectional cryptographic channel, clients make use of the PANDA service. That is to say, PANDA (Phrase Automated Nym Discovery Authentication) is just another mixnet service like the memspool service mentioned above.

The user interface I wrote is a CLI terminal interface and it really kind of sucks. I’m feeling rather inspired by Special’s golang Ricochet. The UI and the backend are two separate processes and communicate by unix domain socket. Cool. Maybe I should do a similar construction that way someone else can later write a crazy C++ Gtk UI for this thing. Although I suspect this strategy doesn’t work well with Android. Unclear. At any rate, catshadow is crash fault tolerant, I hope. It is also internally way more simple than mailproxy and doesn’t use database transactions or anything like that. State is persisted to disk in an encrypted statefile… passphrase, argon2, nacl secretbox of course.

Anyway describing this whole thing is basically a paper worth of words which I shall attempt to articulate later. The overall strategy for Katzenpost should be for this client to merely serve as a demonstration. Whereas it would be far better to help another software project integrate with Katzenpost. Projects such as Briar and Wire come to mind. That having been said, I’d like to soon start a volunteer operated Katzenpost mix network so that we have some real infrastructure that allows us to start using catshadow to send each other encrypted messages. The amount of metadata we leak onto the network will depend on how many people use the system, number of mixes and of course how it is tuned. Since tuning is currently an unsolved problem, it’s all just a fun game anyway.

OK folks that’s all for now. I am not sure exactly what the next steps should be and I’m planning on deliberating while I discuss it with my colleagues and advisors. Either I will start a demo mixnet all on one machine that we can use to try out catshadow or I will attempt to instigate a volunteer operated mixnet. Things will get very cool once we have multiple applications that can use the mixnet. :)

Cheers,

David

Monthly News Update (April 2019)

Greetings,

The Panoramix grant project funded by the European Commission has officially ended but the Katzenpost free software project lives on. Masala and I continue to work on Katzenpost for grant money given to us by Samsung.

We recently learned a few things about mixnet design in a series of design meetings. The conclusions from our learnings is too much information and detail for this here post. However I will summarize some of our conclusions below. Our discussions usually revolved around mixnet CRDT applications, client reliability, message spool server design, client decoy traffic and, preventing attacks: statistical disclosure and active confirmation attacks.

Although far from complete, we added some design considerations to the following draft specification documents:

https://github.com/katzenpost/docs/blob/master/drafts/client.rst https://github.com/katzenpost/docs/blob/master/drafts/deaddrop.rst https://github.com/katzenpost/docs/blob/master/drafts/decoy_traffic.rst

The new Katzenpost mixnet design will work as follows:

  • Clients will NOT send each other messages directly to each other’s Provider. A client’s Provider and spool ID is kept secret while clients share remote spool identities and remote spool Providers with each other instead. This allows a threat model of mutual distrust between clients. This design can help prevent clients from leaking more metadata such as geographical location.

  • Messages are encrypted as follows: Firstly, the higher layer communications channel mechanism will use a modern cryptographic ratchet for forward secrecy and post compromise security properties. However, this ciphertext will be encapsulated by the Noise X oneway handshake. The nonce used by Noise X ensures that even if the client transmits the ratchet ciphertext, the Noise X ciphertext will always look different. This accomplishes our goal of not leaking retransmissions to spool Providers.

  • Spool servers are now kept outside of the Katzenpost mix server source repository. That is to say, we make use of a plugin system for our mix server so that Providers can add arbitrary services to the mix network. We intend to use an iterative approach to designing and implementing remote message spools. The basic messaging use case as described above can be improved in the future by implementing the message spools as CRDT’s. This will allow spools to be replicated and this eliminates single points of failure in the network. In contrast the original Loopix design, each client has a single message spool on their Provider. If this Provider has an outage then that client will be unable to access their message spool.

  • Clients and mixnet plugin services will together optionally make use of a publish subscribe protocol.

  • Clients will send normal and decoy traffic in accordance with the timing provided by the original Loopix tuning parameters: λP, λL, λD, λM.

Our mission is to enable other communications software projects to use mix networks to reduce their metadata leakage. To that end we have been working on mixnet client libraries that can be used by anyone. Although in the future we are planning to write a generic client daemon which you can interact with using a Unix domain socket. We hope that this will be an effective combination for enabling other projects to use a Katzenpost mix network.

Although we are still in an unstable and rapid development phase we made some recent improvements to the Katzenpost mix server:

  • Made it support running in networked environments with NAT devices.

  • Added a new plugin system which is hopefully less annoying to use than our existing gRPC based plugin system. The new plugin system uses CBOR over HTTP over Unix domain sockets. Katzenpost mix server plugins allow you to add arbitrary query/response services to your mix network. That is, you send a SURB and a query payload to a service and it can send one reponse using that SURB.

I’ve provided some “echo” service plugins as examples of how to write plugins for Katzenpost in our server_plugins repo:

https://github.com/katzenpost/server_plugins

HOWEVER, we have for over a year supported BTC and Zcash cryptocurrency submitions via the “currency” plugin, here:

https://github.com/katzenpost/server_plugins/tree/master/grpc_plugins/currency

Other areas of improvement include fixing some bugs in the Voting Authority server and changing our PKI document to include all the Loopix tuning parameters: λP, λL, λD, λM. Thanks to Masala and Moritz we made recent progress in implementing a continuous integration system that runs kimchi based integration tests.

Yes, Katzenpost is a general purpose transport for message oriented applications. All client applications using the mix network look the same. My “elite dark mixnet wallet” for Zcash will have a traffic profile of λP, λL, λD just like mixnet chat client. Just as soon as we stabilize our client library we will actively seek collaborations with application developers.

I’ve made a few screencasts to explain about mix networks and Katzenpost:

Cheers,

David Stainton

Rustification

Hi,

I wrote some notes about making mixnet components in Rust that are binary compatible with existing Katzenpost components

Rustification

The goal should be binary compatibility with the golang implementation of Katzenpost such that the existing golang components can interoperate with the new Rust components. Perhaps the biggest advantage of using Rust would be for writing mixnet clients as opposed to mix servers. A Rust mixnet client could easily present a FFI that could be used by user interfaces written in Java for Android and Swift for iOS.

I wrote several relavant rust crates:

Sphinx binary compatibility

The rust Sphinx uses the exact same cryptographic primitives as the golang implementation. Therefore it should be fairly easy to make them binary compatible. They should share test vectors.

Currently this mix link layer crate uses Noise_XX_25519_ChaChaPoly_BLAKE2b however if the Katzenpost link layer were to upgrade to Kyber then the task of making this crate binary compatibility would be greatly simplified.

Here’s an implementation of Kyber:

This mix_link crate uses the snow Noise protocol library implementation:

However we SHOULD patch snow with Kyber PQ KEM hybrid forward secrecy. Here’s the snow github ticket for this task:

Mix server

Current work in progress rust mix server:

Development progress has halted due to not being able to interoperate with the existing Katzenpost Directory Authority system.

Monthly News Update (Nov 2018)

Greetings!

This is our second edition of katzenpost news. There’s been a lot of progress since the last report I posted many months ago.

Firstly I’d like to mention our future development plans:

  • mix and directory authority key agility
  • generative testing for the voting Directory Authority system
  • generative testing for all of the things where appropriate
  • load and performance testing the mix server
  • design and development of an application agnostic mixnet client message oriented protocol library
  • design and development of one or more applications that use our new mixnet protocol client library
  • potentially assist in integration with other software projects that want to use a mixnet transport protocol

Our recent accomplishments include:

  • Eradication of our usage of JOSE/JWS and usage of the golang Jose library. We no longer use JOSE/JWS for signing mix descriptors and directory authority documents. Instead we use the “cert” library I wrote which gives us certificate format agility AND cryptographic algorithmic agility.

specification: https://github.com/katzenpost/docs/blob/master/specs/certificate.rst

golang implementation: https://github.com/katzenpost/core/tree/master/crypto/cert

  • Our mix server now has a language agnostic plugin system for adding mixnet services. We have a modular API that allows you to write new services in golang and staticly compile them into the binary, however this new plugin system allows you to add services using external programs as plugins. These external plugins use gRPC over Unix domain socket to talk to the mix server (Provider). Using these plugins we can make new mixnet protocols that are either one way or strict call and response protocols that use SURBs to send the replies.

Here’s the mix server documentation for this new feature: https://github.com/katzenpost/docs/blob/master/handbook/mix_server.rst#external-kaetzchen-plugin-configuration

Here’s the Kaetzchen specification document which explains a bit how this plugin system works although it doesn’t discuss implementation details: https://github.com/katzenpost/docs/blob/master/specs/kaetzchen.rst

This repository contains an “echo service” written in Rust, Golang and Python. Also it contains a plugin to perform crypto currency submissions, the idea being that mixnets can be used to transport a transaction blob to a Provider service which then submits the transaction to the database, the blockchain or whatever:

https://github.com/katzenpost/server_plugins

  • we now have a set of incomplete Katzenpost Handbook documents:

https://github.com/katzenpost/docs/blob/master/handbook/index.rst

Mailproxy Client Daemon https://github.com/katzenpost/docs/blob/master/handbook/mailproxy.rst

Katzenpost Mix Server Infrastructure https://github.com/katzenpost/docs/blob/master/handbook/mix_server.rst

Katzenpost Mix Network Public Key Infrastructure https://github.com/katzenpost/docs/blob/master/handbook/nonvoting_pki.rst

Torification of Katzenpost https://github.com/katzenpost/docs/blob/master/handbook/tor.rst

Katzenpost Voting Directory Authority https://github.com/katzenpost/docs/blob/master/handbook/voting_pki.rst

  • we now have a HACKING guide for new Katzenpost developers:

https://github.com/katzenpost/docs/blob/master/HACKING/index.rst

  • we now have a release process and some binary releases:

https://github.com/katzenpost/docs/blob/master/release_checklist.rst https://github.com/katzenpost/docs/blob/master/releases.rst https://github.com/katzenpost/daemons/releases

  • We have released the voting Directory Authority (mixnet PKI) implementation since it is known to work properly as far as we were able to test thus far. This was more work and more difficult than we originally anticipated for both design and programming the implementation.

The design of this PKI was not fully supported by the Panoramix grant project because our academic collaborators were not under official obligation to work on this given that our three month period of design work officially ended. Thus, we were fortunate to receive their advice anyway.

Our specification document is rather still rather incomplete unfortunately:

https://github.com/katzenpost/docs/blob/master/specs/pki.rst

Masala has done most of the development work and together we fixed some bugs in the implementation. The design of our PKI is a synthesis of design ideas that come from some brilliant minds and we’d like to thank Yawning Angel, Claudia Diaz, Ania Piotrowska and Nick Mathewson.

Our PKI uses a Shared Random Value to seed the randomization of our topology. We’d like to thank George Kandianakis for answering our questions about Tor’s hash based commit and reveal shared random value protocol.

What does randomizing our topology mean? Loopix and Katzenpost use the stratified topology which means that the client’s path selection must select a mix from each layer. This topology is enforced by our mix link layer protocol. The PKI generates and publishes a network consensus document\ and this specifies which mixes belong in which topology layer.

When one or more mix network layers change such that they only contain mixes operated by a single operators or contain only one mix that is what we mean by imbalanced. “Too few security domains” gives too much control over path selection to one or more mix operators.

The voting Directory Authority servers detect these mix outages by the absense of a newly uploaded mix descriptors for the voting round. Upon detecting this threshold event the shared random value is used to seed topology randomization. Claudia and Ania rightly pointed out that we MUST try to avoid rerandomization, it is detrimental to the anonymity properties of the mix network because it splits each mix’s anonymity set into two. That is, incoming messages for each mix are either from layer X or from layer Y, this topology distinction in message source means that those two categories of messages will not be mixed together and this is what is meant by splitting the anonymity set into two.

  • Masala and I fixed a plethora of race conditions in client and server code for both the Directory authority and mix servers.

  • I added a prototype mixnet client and server for supporting Adam Langely’s PANDA protocol:

https://github.com/katzenpost/panda

PANDA was used in Pond, and Pond has sadly been abandoned by it’s creator. I would like there to be many useful mixnet clients, including a kind of “Pond replacement” that can perform key exchanges using PANDA.

During the last section of my mixnet talk at Bornhack 2018 I demonstrated the mixnet PANDA client and server working:

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

Sincerely, David Stainton

Monthly News Update (Feb 2018)

katzenpost monthly news

Greetings!

This is our first edition of katzenpost monthly news. I’ll be summarizing recent events from our first hackfest in Athens in early December 2017 to the present.

What we did in Athens:

  • setup a test mix network
  • remote collaboration with Yawning Angel to fix bugs and add features to the server side
  • wrote some basic installation documentation
  • Moritz created and deployed the katzenpost website with glossary and FAQ
  • explored technical issues related to python and java language bindings to golang libraries
  • discussed at length the possibilies for various kinds of mixnet clients
  • Vincent wrote a prototype android instant messenger client
  • met with the GrNet people and told them how to install a katzenpost mix network and answered their questions
  • meskio and kaliy added an external user db interface for Provider authentication
  • meskio wrote prototype python clients for testing purposes
  • we had many group discussion about mix network design
  • special guest visitor: George Kadianakis from Tor Project

Since that time we have been working on our PKI specification. Nick Mathewson sent us a six page review of our spec and Yawning sent a two page reply; both of these e-mails contain lots of design details and have been useful in our editing of the spec thus far:

https://github.com/katzenpost/docs/blob/master/specs/pki.txt

Additionally since the Athens hackfest I, masala and Yawning have made changes so that interaction with the nonvoting PKI to NOT use HTTP but instead uses our Noise based wire protocol (which incidentally uses a Post Quantum hybrid key exchange). The PKI spec has been updated with these new changes. If you are curious about our wire protocol you can read about it here:

https://github.com/katzenpost/docs/blob/master/specs/wire-protocol.txt

During the Brussels hackfest we:

Since the Brussels hackfest, Masala and I visited Claudia Diaz and Tariq Elahi at KU Leuven to discuss mix network designs. In particular we asked various questions about the AQMs used in the Katzenpost server side and later got clarification from Yawning. We also discussed mix network tuning and learned that the preferred method of tuning mixnets is to run lots of simulations and use different kinds of analysis to determine an appropriate set of tuning parameters.

During this discussion Tariq mentioned that their simulations are likely not using the exact same AQMs as Katzenpost server side. We decided that these simulations could be executed using our “mixnet emulator” which is called kimchi. It runs an entire katzenpost mix network and nonvoting authority in a single golang process.

We patiently await for a response to our query: “What features should the mixnet emulator/simulator have?”

Yawning recently implemented the keyserver:

https://github.com/katzenpost/server/blob/master/internal/provider/kaetzchen/keyserver.go

and the mailproxy client side for interacting with the keyserver:

https://github.com/katzenpost/mailproxy/blob/master/api_kaetzchen.go

Since then Yawning’s focus has been to improve server side stability and performance. You can see his task list here: https://github.com/orgs/katzenpost/projects/2

Masala and I have been working on writing a voting directory authority server.

Currently our test mixnet works because Yawning has not only written most of the code but he also wrote a nonvoting Directory Authority PKI. However, the nonvoting PKI is not suitable for production use where a decentralized design should be used to achieve the desired security properties.

Beyond our officially sanctioned work on this project, and in my free time, I’ve been exploring other use-cases for mixnets. I’ve been thinking about “strong location hiding properties”. What I came up with is a kind of kaetzchen dead drop service where you can retreive messages from a remote Provider. The client would never directly interact with the remote Provider but instead only uses the mixnet to retrieve messages.

https://github.com/katzenpost/docs/blob/master/drafts/deaddrop.txt

Cheers!

David