ritter.vg
A Tagging Attack on Mixmaster
05 Jan 2013 23:48:00 EST

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.

Mixmaster Intermediate Message, as it is on it's way to the Second Hop
Mix Headers
Mix Header 1Public Key ID (16 bytes) 0xABCDABCD 0xABCDABCD 0xABCDABCD 0xABCDABCD Length of RSA Enc-ed Data 0xF0 RSA Encrypted Session Key 0x12345678 0x12345678 0x12345678 0x12345678 (128 bytes) 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 Decrypts To: 0xDABCDABC 0xDABCDABC 0xDABCDABC Initialization Vector 0x09090909 0x09090909
Encrypted Header PartPacket ID (16 bytes) 0x87214365 0x87214365 0x87214365 0x87214365 TDES Key (24 bytes) 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 Packet Type Identifier 0x02 Packet Information Initialization Vector1 0x0A0A0A0A 0x0A0A0A0A Initialization Vector2 0x0B0A0A0A 0x0B0A0A0A Initialization Vector3 0x0C0A0A0A 0x0C0A0A0A Initialization Vector4 0x0D0A0A0A 0x0D0A0A0A Initialization Vector5 0x0E0A0A0A 0x0E0A0A0A Initialization Vector6 0x0F0A0A0A 0x0F0A0A0A Initialization Vector7 0x1A0A0A0A 0x1A0A0A0A Initialization Vector8 0x1B0A0A0A 0x1B0A0A0A Initialization Vector9 0x1C0A0A0A 0x1C0A0A0A Initialization Vector10 0x1D0A0A0A 0x1D0A0A0A Initialization Vector11 0x1F0A0A0A 0x1F0A0A0A Initialization Vector12 0x2A0A0A0A 0x2A0A0A0A Initialization Vector13 0x2B0A0A0A 0x2B0A0A0A Initialization Vector14 0x2C0A0A0A 0x2C0A0A0A Initialization Vector15 0x2D0A0A0A 0x2D0A0A0A Initialization Vector16 0x2E0A0A0A 0x2E0A0A0A Initialization Vector17 0x2F0A0A0A 0x2F0A0A0A Initialization Vector18 0x3A0A0A0A 0x3A0A0A0A Initialization Vector19 0x3B0A0A0A 0x3B0A0A0A Remailer Address exitremailer@exam.com 0x00 0x00 (Padded to 80 bytes) Timestamp 0x30303030 0x000506 Message Digest 0x11112222 0x11112222 0x11112222 0x11112222 Padding 0x01020304 0x05060708 (Fill to 328 Bytes..)
Mix Header 2 Public Key ID (16 bytes) 0xABCDABCD 0xABCDABCD 0xABCDABCD 0xABCDABCD Length of RSA Enc-ed Data 0xF0 RSA Encrypted Session Key 0x12345678 0x12345678 0x12345678 0x12345678 (128 bytes) 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 Initialization Vector 0x09090909 0x09090909
Encrypted Header Part Packet ID (16 bytes) 0x87214365 0x87214365 0x87214365 0x87214365 TDES Key (24 bytes) 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 Packet Type Identifier 0x01 Packet Information Message ID (16 bytes) 0x31537597 0x31537597 0x31537597 0x31537597 Initialization Vector 0x0A0A0A0A 0x0A0A0A0A Timestamp 0x30303030 0x000506 Message Digest 0x11112222 0x11112222 0x11112222 0x11112222 Padding 0x01020304 0x05060708 (Fill to 328 Bytes..)
Mix Headers 3-20Fake, Unimportant Data 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE 0xEEEEEEEE ....
Mix Payload
Indecipherable Data

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.

Mix Header 2Public Key ID (16 bytes) 0xABCDABCD 0xABCDABCD 0xABCDABCD 0xABCDABCD Length of RSA Enc-ed Data 0xF0 RSA Encrypted Session Key 0x12345678 0x12345678 0x12345678 0x12345678 (128 bytes) 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 Initialization Vector 0x09090909 0x09090909
Encrypted Header PartPacket ID (16 bytes) 0x87214365 0x87214365 0x87214365 0x87214365 TDES Key (24 bytes) 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 Packet Type Identifier 0x01 Packet Information Message ID (16 bytes) 0x31537597 0x31537597 0x31537597 0x31537597 Initialization Vector 0x0A0A0A0A 0x0A0A0A0A Timestamp 0x30303030 0x000506 Message Digest 0x11112222 0x11112222 0x11112222 0x11112222 Padding 0x01020304 0x05060708 0x01020304 0x05060708 (Fill to 328 Bytes..)

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.

Encrypted Header PartPacket ID (16 bytes) 0x87214365 0x87214365 0x87214365 0x87214365 TDES Key (24 bytes) 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 Packet Type Identifier 0x01 Packet Information Message ID (16 bytes) 0x31537597 0x31537597 0x31537597 0x31537597 Initialization Vector 0x0A0A0A0A 0x0A0A0A0A Timestamp 0x30303030 0x000506 Message Digest 0x11112222 0x11112222 0x11112222 0x11112222 Padding 0x01020304 0x05060708 0x01020304 0x05060708 (Fill to 328 Bytes..)

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:

Mix Header 2Public Key ID (16 bytes) 0xABCDABCD 0xABCDABCD 0xABCDABCD 0xABCDABCD Length of RSA Enc-ed Data 0xF0 RSA Encrypted Session Key 0x12345678 0x12345678 0x12345678 0x12345678 (128 bytes) 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 Initialization Vector 0x09090909 0x09090909
Encrypted Header PartPacket ID (16 bytes) 0x87214365 0x87214365 0x87214365 0x87214365 TDES Key (24 bytes) 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 Packet Type Identifier 0x01 Packet Information Message ID (16 bytes) 0x31537597 0x31537597 0x31537597 0x31537597 Initialization Vector 0x0A0A0A0A 0x0A0A0A0A Timestamp 0x30303030 0x000506 Message Digest 0x11112222 0x11112222 0x11112222 0x11112222 Padding 0x01020304 0x05060708 0x01020304 0x05060708 (Fill to 328 Bytes..)

On decryption this corrupts the entire block, and corrupts the appropriate byte in the subsequent block:

Mix Header 2Public Key ID (16 bytes) 0xABCDABCD 0xABCDABCD 0xABCDABCD 0xABCDABCD Length of RSA Enc-ed Data 0xF0 RSA Encrypted Session Key 0x12345678 0x12345678 0x12345678 0x12345678 (128 bytes) 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 0x12345678 Initialization Vector 0x09090909 0x09090909
Encrypted Header PartPacket ID (16 bytes) 0x87214365 0x87214365 0x87214365 0x87214365 TDES Key (24 bytes) 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 Packet Type Identifier 0x01 Packet Information Message ID (16 bytes) 0x31537597 0x31537597 0x31537597 0x31537597 Initialization Vector 0x0A0A0A0A 0x0A0A0A0A Timestamp 0x30303030 0x000506 Message Digest 0x11112222 0x11112222 0x11112222 0x11112222 Padding 0x01020304 0x05060708 0x01020304 0x05060708 (Fill to 328 Bytes..)

Which in turn corrupts all blocks containing one of those bytes at the inner layer, and alters the following block in an unpredictable fashion:

Encrypted Header PartPacket ID (16 bytes) 0x87214365 0x87214365 0x87214365 0x87214365 TDES Key (24 bytes) 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 0xFE45FE45 Packet Type Identifier 0x01 Packet Information Message ID (16 bytes) 0x31537597 0x31537597 0x31537597 0x31537597 Initialization Vector 0x0A0A0A0A 0x0A0A0A0A Timestamp 0x30303030 0x000506 Message Digest 0x11112222 0x11112222 0x11112222 0x11112222 Padding 0x01020304 0x05060708 0x01020304 0x05060708 (Fill to 328 Bytes..)

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.

Comments
Add a comment...
required
required, hidden, gravatared

required, markdown enabled (help)
you type:you see:
*italics*italics
**bold**bold
[stolen from reddit!](http://reddit.com)stolen from reddit!
* item 1
* item 2
* item 3
  • item 1
  • item 2
  • item 3
> quoted text
quoted text
Lines starting with four spaces
are treated like code:

    if 1 * 2 < 3:
        print "hello, world!"
Lines starting with four spaces
are treated like code:
if 1 * 2 < 3:
    print "hello, world!"