This blog post originally appeared on crypto.is. We've since shut down that website, so I have copied the blog post back to my own for archival purposes.
We've laid the groundwork in the past two blog posts to explain a tagging attack on the Mixmaster remailer system. In our scenario, an attacker runs several remailer nodes in a system.
An attacker may get lucky and control the first and last nodes in a path.
This seems a hopeless scenario - but for a single message, a good remailer network can provide unlinkability in this situation. An attacker would know that Alice sent an email, and they would know that john@nytimes.com recieved an email, and its contents - but the attacker should not be able to link these two messages together. That unlinkability is supposed to be provided by the middle node. But the unlinkability is lost if the attacker can tag the message in a way for them to recognize later. This example also illustrates why you want a lot of people using an anonymity network - there are vastly more people in the crowd that could have sent the incoming message, and vastly outgoing messages Alice could have sent.
But where in the Mixmaster packet format can we create a tag that won't be rejected by the middle node, would allow us to recognize the tag when we see it, and not corrupt the Mix Message so much that we are unable to determine the ultimate destination of the message? Let's go back to the packet format (which we covered in a previous blog post) - we'll display the data we will see, and what we know, as it leaves the first (attacker-controlled) node.
The different layers of red represent the number of times it is encrypted. Light Red is encrypted once. Dark Red must be sent through two decryptions before the plaintext is ledgible. The ciphertext is encrypted in Cipher Block Chaining Mode, which allows us to made small modifications to ciphertext that have small modifications to the plaintext. It's not as precise as we'd like - flipping a single bit will entirely corrupt the 8 bytes of that data block, but it will flip the corresponding bit of the subsequant data block. Let's zero in on the second Mix Header, and illustrate the data blocks.
The blue block illustrate the blocks of data that will be encrypted in CBC mode. Flipping a bit in one of these will corrupt the entire block, and flip the resulting bit in the following block. However, remember we're dealing with multiple layers of encryption: the Encrypted Header Part is also encrypted, and its block offsets are different.
Any byte we manipulate in the second Mix Header will corrupt that blue block of data entirely, and the corresponding byte in the subsequent block. Every blue corrupted byte will corrupt any red blocks that contains the byte. And the final red block will corrupt the subsequent red block. And, we can't cause a corruption that renders the Encryption Key or IV irrecoverable - or we won't be able to decrypt the payload - we must choose carefully.
The Attack
Now to give in to the suspense ;) If we manipulate the last byte of the Message Digest we will perform a cascading corruption that does not affect the Key or IV. First we manipulate that byte:
On decryption this corrupts the entire block, and corrupts the appropriate byte in the subsequent block:
Which in turn corrupts all blocks containing one of those bytes at the inner layer, and alters the following block in an unpredictable fashion:
So after decryption, the third node will have a message digest that is half-valid and half-invalid. If the attacker recieves a message in that form, they are able to recognize it as a message they tagged in the first hop. They are still able to decrypt the Mix Payload because, crucially, we did not cause any corruption to the Triple DES key or Initialization Vector. It is also possible there was a legitimate corruption during transit, but lower layer checksums make that improbable.
If you'd like to follow this attack in greater detail, code demonstrating it is available on github. It makes heavy use of the unfinished Python Mixmaster implementation Mixfaster. Here's what it looks like when you run it (output minified a tad):
$ ./demo.py
Client sends message with a Path of Node1,Node2,Node3
by pure luck (or unluck) Nodes 1 and 3 are attacker-controlled
======================================================================
Received Message on Node 1, processing...
Message recieved by Node 1, decrypted, and decoded:
Packet Header ---------------------------
Public Key Id: 72f00ecf4f4e3af64d19772d4dd7d620
PacketType: IntermediateHop (0)
Timestamp: Sun Oct 21 20:00:00 2012
Remailer Address: node2@example.com
...
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Performing Tagging Attack
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Sending Message on to Node 2...
======================================================================
Received Message on Node 2, processing...
Message recieved by Node 2, decrypted, and decoded:
Packet Header ---------------------------
Public Key Id: 24a17d807994cffbe65fdc6ce13d3562
PacketType: IntermediateHop (0)
Timestamp: Tue Oct 23 20:00:00 2012
Remailer Address: node3@example.com
...
Sending Message on to Node 3...
======================================================================
Received Message on Node 3, processing...
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Caught a Decoding Exception! Continuing Anyway...
Actual Digest b496224032ec197aaa27ba3632e6f127
Included Digest b496224032ec197a925d5f463ffa7da8
|______________||______________|
Matches Corrupted
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Message recieved by Node 3, decrypted, and decoded:
Packet Header ---------------------------
Public Key Id: f3372c7effb5887858460b7ed2faab91
PacketType: FinalHop (1)
Timestamp: Sun Oct 21 20:00:00 2012
Packet Body -----------------------------
Data Length : 229
Destination Fields: 1
john@nytimes.com
Header Fields : 1
Subject: Confidential Information
User Data Type : Plain (3)
User Data:
This is a sample mixmaster message demonstrating tagging attacks.
Conclusion
The flaw in Mixmaster is that there is no integrity protection of the Mix Headers or Payload as they cross nodes. A node is able to verify that the Mix Header it processes has not been altered (at least up to the Padding) - but cannot make the same statement about the other Mix Headers or the Payload. So we modify a Header intended for Node 3 as the message leaves Node 1, Node 2 will pass it on (unaware it's been tampered), and Node 3 recognizes the tampering.
This blog post is licensed under Creative Commons Attribution 3.0 United States License and is inspired by, and makes heavy use of, the images produced by the EFF & Tor Project here.
required, hidden, gravatared
required, markdown enabled (help)
* item 2
* item 3
are treated like code:
if 1 * 2 < 3:
print "hello, world!"
are treated like code: