za3k > protocols > ok-mixnet

I'm a human being, and sometimes I'd like to send someone a message. I don't want anyone other than me and whoever the message is for to read it--not strangers, not companies, and not governments. It's possible, and with computers, it should be easy and instant.

A proof of concept is on github. If you want to join, meail me--happy to add you.

OK-Mixnet

OK-Mixnet is my proposed sketch for a method to send small messages, slowly. It's designed for things like email, IRC-style slow chatrooms, or bulletin boards. In my experience, this is the same stuff I'd use GPG for.

OK-Mixnet sends

Here are the drawbacks:

Background:

I'll explain how it works iteratively.

One-Time Pads (Perfect Encryption)

One-Time MACs (Perfect Authentication)

The Perfect Message Protocol

The Perfect Message Protocol sends a message between person A and person B, who have exchanged some secret numbers ahead of time. The message stays private and can't be tampered with, but anyone can see the message being sent.

To send the message

  1. Our inputs are
  2. Calculate the 9688-bit ciphertext = (message) xor (OTPK)
  3. Calculate 9689-bit message authentication code = [(OTM-a) * (ciphertext) + (OTM-b)] modulo p. Notice that this is addition and multiplation of 9689-bit numbers, so this isn't automatically handled by your CPU. But it's not hard either.
  4. Send ciphertext and MAC to the recipient.

To receive the message:

  1. Our input is
  2. Calculate 9689-bit expected message authentication code = [(OTM-a) * (ciphertext) + (OTM-b)] modulo p.
  3. If expected and received authentication codes don't match, the message has been tampered with (or there was some other bug and you have bad data). Report a failure and exit immediately.
  4. Otherwise, calculate the 9688-bit (1211-byte) plaintext = (ciphertext) xor (OTPK)
  5. Return the plaintext (message), which has been received tamper-free.

The OK-Link Protocol

The OK-Link protocol sends short messages between person A and person B, who have exchanged some secret files filled with random bits ahead of time. The messages are private and can't be tampered with, and adversaries can't tell when messages are being sent.

There is a transmission size and period. The defaults are a 1K message (size) per 1 minute (period).

  1. First, two friends generate large files of random bits. 40GB of data is suggested. They exchange the bits with each other, for example by DVD-ROM or trusted USB sticks. Internally, the OK-Link xors the two 40GB files together to form a single 40GB one-time pad. The original files can be deleted.
  2. The friends also agree on a start time a little in the past--say midnight of the current date. They write down the date in a text file, which is stored along with the two pads.
  3. The file is then divided into a bunch of individual one-time pads, which are numbered--each one will be used for a different message. For the first minute after the start time, pad 1 is used, for the second minute pad 2 is used, and so on.
  4. Whenever you want to send a message, it gets added to a message queue.
  5. There is one modification from the Perfect Message protocol--a unix timestamp is put at the start of the message, before the encrypted bits. This is in case the sender and receiver clock are a little off, so they can agree on which one-time pad should be used.
  6. Once a minute, both A and B send each other a Perfect Message. There are two main kinds of perfect messages sent, C and not-C. All messages are zero-padded at the end to reach 1211 bytes.

Security:

At the default rates, a 40GB file of random data will work for 10 years (6K is used per message pair).

The OK-Mixnet Protocol

The OK-Mixnet protocol is almost the same as the OK-Link protocol. Let's say there are 100 people who want to communicate. This is the network size. Some of them are horrible spammers, some are your friends. What we essentially do is to open 99 OK-Link channels, one to each other person in OK-Mixnet, and transmit on all of them. BUt to make traffic less bursty, we stagger the transmissions, and transmit to each person in turn instead.

  1. Exchange large files of random bits with each of your friends, as in OK-Link, and form a one-time pad. This can be done after the network is already running, you just won't be able to decode messages until then.
  2. Get a list of the ID and IP address of everyone in the mixnet. This is done by a central authority for the proof-of-concept--I'll maintain a file by hand and email it to a mailing list. Your ID is a unique number between 0 and 99 (between 0 and N-1)
  3. You equip your machine with a good hardware random number generator. Every second, you transmit a Perfect Message to id [(unix timestamp in seconds) + (your ID)] modulo (network size) and receive a message.

If there are 100 people in OK-Mixnet, you contact your friend with a message every 99 seconds, or every 2 minutes. The total traffic sent over the network is 6K/second (15GB/month). The more people join OK-Mixnet, the slower it gets to send messages, but the bandwidth usage per person stays the same.

Security

Notes and Known Improvements

Background

Background: Perfect, or Information-Theoretic Security

I'll explain what perfect security is, as a motivator for why you would want to do this, even though you need to exchange keys in person. Feel free to skip ahead to "One-Time Pads" if this isn't your thing.

There are three levels of security you can get in the theoretical digital world.

Today, we don't know anything in the "compuationally difficult" class--humankind still hasn't figured out, fundamentally, whether any computationally difficult crypto problems exist (the existence of one-way-functions ). We suspect that some of the problems we know are practically difficult, might also be computationally difficult--we just can't prove it.

On the other hand, we do know a couple perfect security methods, which I'll cover. Given the choice to use provably perfect security any smart person can verify themselves, I would rather use perfect security. So why don't people?

Why people don't use perfect security

Problems that CAN be solved using perfect crypto:

Problems that CANNOT be solved using perfect crypto:

Problems where I'm not sure