Preliminaries

Notation and encoding

   KP -- a public key for an asymmetric cipher.
   KS -- a private key for an asymmetric cipher.
   K  -- a key for a symmetric cipher.
   N  -- a "nonce", a random value, usually deterministically chosen
         from other inputs using hashing.

H(m) -- a cryptographic hash of m.

Security parameters

Tor uses a stream cipher, a public-key cipher, the Diffie-Hellman protocol, and a hash function.

KEY_LEN -- the length of the stream cipher's key, in bytes.

   KP_ENC_LEN -- the length of a public-key encrypted message, in bytes.
   KP_PAD_LEN -- the number of bytes added in padding for public-key
     encryption, in bytes. (The largest number of bytes that can be encrypted
     in a single public-key operation is therefore KP_ENC_LEN-KP_PAD_LEN.)

   DH_LEN -- the number of bytes used to represent a member of the
     Diffie-Hellman group.
   DH_SEC_LEN -- the number of bytes used in a Diffie-Hellman private key (x).

   HASH_LEN -- the length of the hash function's output, in bytes.

Message lengths

Some message lengths are fixed in the Tor protocol. We give them here. Some of these message lengths depend on the version of the Tor link protocol in use: for these, the link protocol is denoted in this table with v.

Note that for all v, CELL_LEN(v) = 1 + CIRCID_LEN(v) + CELL_BODY_LEN.

Formerly CELL_BODY_LEN was called sometimes called PAYLOAD_LEN.

Ciphers

These are the ciphers we use unless otherwise specified. Several of them are deprecated for new use.

For a stream cipher, unless otherwise specified, we use 128-bit AES in counter mode, with an IV of all 0 bytes. (We also require AES256.)

For a public-key cipher, unless otherwise specified, we use RSA with 1024-bit keys and a fixed exponent of 65537. We use OAEP-MGF1 padding, with SHA-1 as its digest function. We leave the optional "Label" parameter unset. (For OAEP padding, see ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf)

We also use the Curve25519 group and the Ed25519 signature format in several places.

For Diffie-Hellman, unless otherwise specified, we use a generator (g) of 2. For the modulus (p), we use the 1024-bit safe prime from rfc2409 section 6.2 whose hex representation is:

     "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08"
     "8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B"
     "302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9"
     "A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE6"
     "49286651ECE65381FFFFFFFFFFFFFFFF"

As an optimization, implementations SHOULD choose DH private keys (x) of 320 bits. Implementations that do this MUST never use any DH key more than once. [May other implementations reuse their DH keys?? -RD] [Probably not. Conceivably, you could get away with changing DH keys once per second, but there are too many oddball attacks for me to be comfortable that this is safe. -NM]

For a hash function, unless otherwise specified, we use SHA-1.

KEY_LEN=16. DH_LEN=128; DH_SEC_LEN=40. KP_ENC_LEN=128; KP_PAD_LEN=42. HASH_LEN=20.

We also use SHA256 and SHA3-256 in some places.

When we refer to "the hash of a public key", unless otherwise specified, we mean the SHA-1 hash of the DER encoding of an ASN.1 RSA public key (as specified in PKCS.1).

A bad hybrid encryption algorithm, for legacy purposes

Some specifications will refer to the "legacy hybrid encryption" of a byte sequence M with a public key KP. It is computed as follows:

      1. If the length of M is no more than KP_ENC_LEN-KP_PAD_LEN,
         pad and encrypt M with KP.
      2. Otherwise, generate a KEY_LEN byte random key K.
         Let M1 = the first KP_ENC_LEN-KP_PAD_LEN-KEY_LEN bytes of M,
         and let M2 = the rest of M.
         Pad and encrypt K|M1 with KP.  Encrypt M2 with our stream cipher,
         using the key K.  Concatenate these encrypted values.

Note that this "hybrid encryption" approach does not prevent an attacker from adding or removing bytes to the end of M. It also allows attackers to modify the bytes not covered by the OAEP -- see Goldberg's PET2006 paper for details. Do not use it as the basis for new protocols! Also note that as used in Tor's protocols, case 1 never occurs.