I'd like to get feedback on the clarity of this draft describing the Mixmaster protocol. I'll post the proposed extensions for version 3 later. Mixmaster Protocol ================== Abstract Most e-mail security protocols only protect the message body, leaving useful information such as the the identities of the conversing parties, sizes of messages and frequency of message exchange open to adversaries. This document describes Mixmaster, a mail transfer protocol designed to protect electronic mail against traffic analysis. Table of Contents 1. Introduction 2. The Mix-Net Protocol 2.1 Message Creation 2.2 Remailing 3. Message Format 3.1 Cryptographic Algorithms 3.2 Packet Format 3.2.1 Header Chart Format 3.2.2 Body Format 3.3 Mail Transfer Encoding 3.5 Transfer through Socket Connections 4. Key Format 5. References 1. Introduction This document describes a mail transfer protocol designed to protect electronic mail against traffic analysis. Most e-mail security protocols only protect the message body, leaving useful information such as the the identities of the conversing parties, sizes of messages and frequency of message exchange open to adversaries. Message transmission can be protected against traffic analysis by the mix-net protocol. A mix (remailer) is a service that forwards messages, using public key cryptography to hide the correlation between its inputs and outputs. If a message is sent through a sequence of mixes, one trusted mix is sufficient to provide anonymity and unobserveability of communications against a powerful adversary. Mixmaster is a mix-net implementation for electronic mail. This document describes version 2 of the Mixmaster message format. 2. The Mix-Net Protocol The mix-net protocol [Chaum] allows to send messages while hiding the relation of sender and recipient from observers (unobserveability). It also provides the sender of a message with the ability to remain anonymous to the recipient (sender anonymity). If anonymity is not desired, authenticity and unobserveability can be achieved in the same time by transmitting digitally signed messages. This section gives an overview over the protocol used in Mixmaster. The message format is specified in section 3. 2.1 Message Creation To send a message, the user agent splits into parts of fixed size, which form the bodies of Mixmaster packets. If sender anonymity is desired, care should be taken not to include identifying information in the message. The message may be compressed. The sender choses a sequence of up to 20 remailers for each packet. The final remailer must be identical for all parts of the message. The packet header consists of 20 charts. For a sequence of n remailers, header charts n+1, ... , 20 are filled with random data. For all charts i := n down to 1, the sender generates a symmetric encryption key, which is used to encrypt the body and all following header charts. This key, together with other control information for the remailer, is included in the i-th header chart, which is then encrypted with the remailer's public key. The message is sent to the first remailer in an appropriate transport encoding. To increase reliability, multiple copies of message may be sent through different paths. The final remailer must be identical for all paths, so that duplicates can be detected and the message is delivered only once. 2.2 Remailing When a remailer receives a message, it decrypts the first header chart with its private key. By keeping track of a packet ID, the remailer verifies that the packet has not been processed before. The integrity of the message is verified by checking the packet length and verifying message digests included in the packet. Then the first header chart is removed, the others are shifted up by one, and the last chart is filled with random padding. All header charts and the message body are decrypted with the symmetric key found in the header. This reveals a public key-encrypted header chart for the next remailer at the top, and obscures the old top header chart. Transfer encoding is applied to the resulting message. The remailer collects several encrypted messages before sending the resulting messages in random order. Thus the relation between the incoming and outgoing messages is obscured to outside adversaries even if the adversary can observe all messages sent. The message is effectively anonymized by sending it through a chain of independently operated remailers. 2.3 Message Reassembly When a packet is sent to the final remailer, it contains a flag indicating that the chain ends at that remailer, and whether the packet contains a complete message or part of a multi-part message. If the packet contains the entire message, the body is decrypted and after reordering messages the plain text is delivered to the recipient. For partial messages, a packet ID is used to identify the other parts as they arrive. When all parts have arrived, the message is reassembled and delivered. If the parts do not arrive within a time limit, the message is discarded. Only the last remailer in the chain can determine whether packets are part of a certain message. To all the others, they are completely independent. If necessary, the reassembled message is decompressed before sending it to the recipient. When anonymous messages are forwarded to third parties, the final remailer should ensure that the sender cannot supply header lines that indicate a false identity or send Usenet control messages that may have security implications. Appropriate information about the origin of the message should be inserted in the Comments: header line of the message. If the recipient does not wish to receive anonymous messages, the remailer can ensure authenticity be verifying that the message is cryptographically signed [RFC 1991, RFC 2311] by a known sender. 3. Message Format 3.1 Cryptographic Algorithms The asymmetric encryption operation in Mixmaster version 2 uses RSA with 1024 bit RSA keys and PKCS #1 padding [RFC 2313]. The symmetric encryption uses EDE 3DES with cipher block chaining (24 byte key, 8 byte initialization vector) [Schneier]. MD5 [RFC 1321] is used as the message digest algorithm. 3.2 Packet Format A Mixmaster packet consists of a header containing information for the remailers, and a body containing the payload. To ensure that packets are undistinguishable, the size of these encrypted data fields is fixed. The packet header consists of 20 header charts (specified in section A.2) of 512 bytes each, resulting in a total size of 10240 bytes. The header charts and the body are encrypted with symmetric session keys specified in the first header chart. 3.2.1 Header Chart Format Public key ID [ 16 bytes] Encrypted session key length [ 1 byte ] RSA-encrypted session key [ 128 bytes] Initialization vector [ 8 bytes] Encrypted header section [ 328 bytes] Padding [ 31 bytes] Total size: 512 bytes A random 24 bit Triple-DES key is encrypted with RSA, resulting in 1024 bit of encrypted data. The header section encrypted with this session key is: Packet ID [ 16 bytes] Triple-DES key [ 24 bytes] Packet type identifier [ 1 byte ] Packet type 0: 19 Initialization vectors [152 bytes] Remailer address [ 80 bytes] Packet type 1: Message ID [ 16 bytes] Initialization vector [ 8 bytes] Packet type 2: Packet number [ 1 byte ] Number of packets [ 1 byte ] Message ID [ 16 bytes] Initialization vector [ 8 bytes] Timestamp [ 7 bytes] (optional) Message digest [ 16 bytes] Total size: Type 0: 297 bytes (+ 7 if timestamp is used) Type 1: 81 bytes (+ 7 if timestamp is used) Type 2: 83 bytes (+ 7 if timestamp is used) This data structure is padded to 328 bytes. Packet ID: randomly generated packet identifier. Key: symmetric key used to encrypt the following header charts and the body. Packet type identifier: Intermediate hop 0 Final hop 1 Final hop, partial message 2 Initialization vectors: For packet type 1 and 2, the IV is used to symmetrically encrypt the body. For packet type 0, there is one IV for each of the 19 following header charts. The IV for 19th header chart is also used for the body. Remailer address: address of next hop. Message ID: randomly generated identifier unique to (all packets of) this message. Packet number: Sequence number used in multi-packet messages. Number of packets: Total number of packets. Timestamp: A timestamp is introduced with the byte sequence (48, 48, 48, 48, 0). The following two bytes specify the number of days since Jan 1, 1970, given in little-endian byte order. A random number of up to 3 may be substracted from the number of days in order to obscure the origin of the message. Digest: MD5 digest computed over the preceding elements of the encrypted header section. Header charts 2 .. 20 and the body each are decrypted separately using the respective initialization vectors. 3.2.2 Body Format Number of destinations [ 1 byte] Destination addresses [ 80 bytes each] Number of header lines [ 1 byte] Header lines [ 80 bytes each] Payload [ any size] Destination addresses are Internet mail addresses. Additionally, the following special destinations are defined: null: Dummy message, will be discarded by the final mix. post: newsgroup Message will be posted to Usenet. The payload may be compressed using GZIP [RFC 1952] if the capabilities attribute of the final remailer contains the flag "C". When compressing the message, the operating system field must be set to Unix, and file names must not be given. The remailer treats messages beginning with the GZIP identification header (31, 139) as compressed. The resulting message is split into chunks of 10236 bytes. To each chunk, its length is prepended as a 4 byte little-endian number to form the body of a Mixmaster packet. 3.3 Mail Transfer Encoding Mixmaster packets are sent as text messages [RFC 822]. The body has the following format: :: Remailer-Type: Mixmaster [version number] -----BEGIN REMAILER MESSAGE----- [message length] [message digest] [encoded message] -----END REMAILER MESSAGE----- The length field always contains the decimal number "20480", since the size of Mixmaster messages is constant. The MD5 message digest [RFC 1321] of the message is encoded as a hexadecimal string. The message itself is encoded in base 64 encoding [RFC 1421] and broken into lines of 40 characters. 4. Key Format Remailer public key files consist of a list of attributes and a public RSA key: [attributes list] -----Begin Mix Key----- [key ID] [length] [encoded key] -----End Mix Key----- The attributes are listed in one line separated by spaces: identifier: a human readable alphabetical string identifiying the remailer address: the remailer's Internet mail address key ID: public key ID version: the Mixmaster version number capabilities: flags indicating additional capabilites of the remailers The identifier consists of alphanumeric characters, begining with an alphabetic character. It must not contain whitespace. The encoded key packet consists of two bytes specfying the key length (1024 bits) in little-endian byte order, and of the RSA modulus and the public exponent in big-endian form using 128 bytes each, with preceding null bytes where necessary. The packet is encoded in base 64, and broken into lines of 40 characters each. Its length (258 bytes) is given as a decimal number. The key ID is the MD5 message digest of the reprentation of the RSA public key (not including the length bytes). It is encoded as a hexadecimal string. The capabilities field is optional. Clients should ignore unknown flags. The following flags are used in version 2.0.4: C accepts compressed messages. M will forward messages to another mix, when used as the final hop. Nm supports posting to Usenet throught a mail-to-news gateway. Np supports direct posting to Usenet. Digital signatures [RFC 1991] should be used to ensure the authenticity of the key files. 5. References [Chaum] Chaum, D., "Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms", Communications of the ACM 24 (1981) 2. [RFC 822] Crocker, D., "Standard for the Format of ARPA Internet Text Messages", STD 11, RFC 822, August 1982. [RFC 1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. [RFC 1421] Linn, J., "Privacy Enhancement for Internet Electronic Mail: Part I -- Message Encryption and Authentication Procedures", RFC 1421, February 1993. [RFC 1952] Deutsch, P., "GZIP file format specification version 4.3", RFC 1951, May 1996. [RFC 1991] Atkins, D., Stallings, W. and Zimmermann, P., "PGP Message Exchange Formats", RFC 1991, August 1996. [RFC 2311] Dusse, S., Hoffman, P, Ramsdell, B, Lundblade, L. and Repka, L., "S/MIME Version 2 Message Specification", RFC 2311, March 1998. [RFC 2313] Kaliski, B., "PKCS #1: RSA Encryption, Version 1.5", RFC 2313, March 1998. [Schneier] Schneier, B., "Applied Cryptography", 2nd Edition, Wiley, 1996.