Is Tor traffic using the TAP handshake vulnerable to retroactive decryption?

Question

Assume an attacker with a record of Tor traffic between a client and guard has precomputed the 1024-bit Oakley group for Diffie-Hellman used in the TAP protocol. This would allow them to rapidly decrypt any recorded DH key exchange done over that group after an expensive but feasible (millions of dollars of equipment and a year of time) one-time computation. If I recall, the legacy TAP protocol used 1024-bit DH. Combined with the suspicion that the "breakthrough cryptanalytic capabilities" mentioned in the Snowden leaks refer to precomputation attacks against 1024-bit Diffie-Hellman parameters as pointed out in the WeakDH paper, would an adversary with these capabilities be able to decrypt old Tor traffic?

Answer 1

To answer my own question after rereading the spec, it is not. There are two things that make it difficult to attack broken DH groups in the old TAP protocol: the RSA hybrid handshake, and link encryption.

RSA hybrid handshake

The protocol uses the 1024-bit safe prime from RFC 2409 section 6.2 with the hex representation:

FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08
8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B
302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9
A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE6
49286651ECE65381FFFFFFFFFFFFFFFF

While this is small enough for a powerful adversary to attack, TAP uses a hybrid handshake where the DH data is encrypted using static RSA. In particular, RSA with OAEP-MGF1 padding is used to encrypt a 128-bit symmetric key as well as the first part of the DH data (specifically g^x, where g is the generator and x is the DH private key). The symmetric key is then used to encrypt the second part of the DH data which is too large to encrypt using RSA. The Tor specification defines this as follows:

The payload for a CREATE cell is an 'onion skin', which consists of
the first step of the DH handshake data (also known as g^x).  This
value is encrypted using the "legacy hybrid encryption" algorithm
(see 0.4 above) to the server's onion key, giving a client handshake:

    PK-encrypted:
      Padding                       [PK_PAD_LEN bytes]
      Symmetric key                 [KEY_LEN bytes]
      First part of g^x             [PK_ENC_LEN-PK_PAD_LEN-KEY_LEN bytes]
    Symmetrically encrypted:
      Second part of g^x            [DH_LEN-(PK_ENC_LEN-PK_PAD_LEN-KEY_LEN)
                                        bytes]

Breaking the Diffie-Hellman handshake now requires breaking the RSA key. While the RSA key is only 1024 bits and RSA is generally slightly easier to break than a DH key of equivalent size, precomputation attacks are not useful against it. While breaking pure DH (for any given group) requires a one-time expensive precomputation, breaking RSA requires performing an expensive computation each time. While the TAP protocol does use static RSA keys, they are regenerated periodically (once every 1 to 90 days, but 28 days by default, according to dir-spec.txt).

It would absolutely be possible to decrypt an entire circuit by first breaking the 1024-bit RSA and then breaking the DH exchange underneath it, but this would have to be done for each relay in a circuit, and the end result would be only around 10 minutes of plaintext (or however long that individual circuit lived). Millions of dollars and a year of computation to break a single circuit is very unlikely to be worth it.

Link encryption

In addition to the above RSA hybrid handshake, another obstacle exists which makes mass decryption difficult even if the DH handshake can be broken. Tor not only uses layered encryption for each relay using its native protocol, it also encapsulates each link to another relay using standard TLS. That is, before any circuits are created or extended, two relays or a client and relay that wish to communicate first establish a connection using TLS. Breaking the inner circuit encryption thus requires also breaking the outer TLS layer. The parameters used by this TLS session depend on the version of OpenSSL that the Tor binary is linked with. Forward secrecy and sufficiently large keys are mandatory.

The only way to attack the inner onion circuit is if this TLS can be broken, or if the adversary is in control of the relay (since TLS is naturally not end-to-end, but only protecting data between each individual relay). This means that a malicious ISP or datacenter which passively logs the traffic of a Tor relay cannot strip this TLS unless it also controls the relay itself. While it is absolutely possible to run malicious relays, the traffic visibility would be much lower than it would be if their ISP could passively break the TLS.