Cell header changes / solving malleability

[Roger Dingledine <arma@mit.edu>]

Right now tor traffic is vulnerable to a malleability attack: because we
don't do any integrity checking, an adversary could guess some of the
plaintext of a cell, xor it out, and xor in his own plaintext. Even an
external adversary can do this, and even through our link encryption (!).

Some examples of this attack might be to change a create cell to a destroy
cell, or to change the destination address in a 'begin' relay cell to
the adversary's webserver, or to change a user on an ftp connection from
typing "dir" to typing "delete *". Any node or observer along the path
can introduce such corruption in a stream.

This proposal fixes the malleability problem while reducing header size
overhead, and without increasing cpu overhead much. Please break it. :)

Currently a cell looks like:

        ACI (anonymous circuit identifier)    [2 bytes]
        Command                               [1 byte]
        Length                                [1 byte]
        Sequence number (unused, set to 0)    [4 bytes]
        Payload (padded with 0 bytes)         [248 bytes]
                                         [Total size: 256 bytes]

And the payload of a relay cell looks like:

         Relay command           [1 byte]
         Stream ID               [7 bytes]
         Relay payload           [240 bytes]

So right now relay cells have 16 bytes overhead and 240 bytes actual
payload.

First of all, note that 'length' is variable only for relay cells: if
it's not a relay cell, I can already tell you what length is supposed to
be. Let's move length into the relay header. Secondly, note that sequence
number (4 bytes) is unused. Let's use that. Thirdly, note that 7 bytes
for stream ID is more than we really need. If we're willing to handle
some more complexity (see below), we can cut that down to 2 bytes.

We fix the malleability problem by introducing randomness and redundancy
inside the encrypted cell: we add 3 bytes of pseudorandomness in the
space saved by reducing stream ID size, and we add 4 bytes (1/5 of a SHA1)
where the sequence number used to be.

        ACI (anonymous circuit identifier)   [2 bytes]  \__outer header
        Command                              [1 byte]   /
        Pseudorandomness                     [3 bytes]  \__integrity header
        Checksum (1/5 of a SHA-1)            [4 bytes]  /
        Relay command                        [1 byte]   \
        Length                               [1 byte]    == relay header
        Stream ID                            [2 bytes]  /
        Relay payload                        [242 bytes]

gives 14 bytes overhead and 242 bytes usable per relay cell. For relay
cells, the outer header is rewritten at each hop, and the rest of the
packet does the layered-encryption thing. Non-relay cells have the outer
header and integrity header, followed by whatever is specific to that
cell type (eg an onionskin).

This means that relay cell integrity is only checked end-to-end. With 3
bytes of randomness, it's pretty darn unlikely that the adversary could
spoof a cell. The chance that he'll be able to keep up the spoofing for
multiple cells is even lower.

Note that *all cells* need to have this randomness in them. For example,
if we decided padding cells can just use all zeros, then the adversary
would be able to mutate padding cells into anything he wants.

We should also recognize that an observer could mutate a non-relay cell
into a relay cell, and then since relay cells don't immediately check
their integrity, it would propagate to the end of the circuit.

The computational overhead isn't so bad. The pseudorandomness is just
a couple bytes of AES, and we're already doing 256 of them for the
link encryption, and twice that for relay crypts. Making or receiving
a non-relay cell or a non-intermediate relay cell requires a SHA-1,
but that's not so bad either.

Is there any real problem with AES'ing an odd number of bytes, rather
than the block size? I would hope the AES implementation sticks the
unused bytes in a buffer and gives them to me first when I ask for more,
so amortized it's just like doing it by the block size.

We could instead back off on our threat model, and only concern ourselves
with evil nodes in the middle of the circuit, rather than evil ISPs who
own links. In that case non-relay nodes could skip the integrity header.

Reducing stream ID to 2 bytes increases the chance of collisions for
crypted relay packets, but also improves general throughput. Consider
4 hops to a path and 3 exit connections per hop. 16 bits of stream ID,
minus 4 bits from collisions (lg 4*4), plus 8 bits because cells are
256 bytes, means we expect a collision roughly every 2^20 bytes (one
megabyte) of data flowing from the OP. The OP must examine outgoing
relay cells as it crypts them, and if there will be a collision, it
must send that cell instead as a relay-padding cell to the node where
the collision will happen. One cell in 4096 needs to be sent twice (256
byte overhead, .02%), compared to 4096 cells with the extra five bytes
(20480 byte overhead, 2% overhead -- plus all the saved space in relay
cells coming toward the OP, arguably the bulk of relay cells, that don't
need to be checked for collisions).

Did I miss anything?
--Roger