1 files changed, 142 insertions, 0 deletions
diff --git a/spec/tor-spec/preliminaries.md b/spec/tor-spec/preliminaries.md
new file mode 100644
index 0000000..15cacf3
--- /dev/null
+++ b/spec/tor-spec/preliminaries.md
@@ -0,0 +1,142 @@
+<a id="tor-spec.txt-0"></a>
+
+# Preliminaries
+
+<a id="tor-spec.txt-0.1"></a>
+
+## Notation and encoding{#notation-and-encoding}
+
+```text
+   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.
+
+```text
+   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 {#msg-len}
+
+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`.
+
+| Name | Length in bytes | Meaning |
+| ---- | --------------- | ------- |
+| `CELL_BODY_LEN` | 509 | The body length for a [fixed-length cell](./cell-packet-format.md#fixed-length-cell). |
+| `CIRCID_LEN(v)`, `v` < 4 | 2 | The length of a [circuit ID](./cell-packet-format.md#circid) |
+| `CIRCID_LEN(v)`, `v` ≥ 4 | 4 |  |
+| `CELL_LEN(v)`, `v` < 4 | 512 | The length of a [fixed-length cell](./cell-packet-format.md). |
+| `CELL_LEN(v)`, `v` ≥ 4 | 514 |  |
+
+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`.
+
+<a id="tor-spec.txt-0.3"></a>
+
+## Ciphers{#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:
+
+```text
+     "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).
+
+<span id="random-values">
+All "random" values MUST be generated with a cryptographically
+strong pseudorandom number generator seeded from a strong entropy
+source, unless otherwise noted.
+All "random" values MUST selected uniformly at random from the
+universe of possible values, unless otherwise noted.
+</span>
+
+<a id="tor-spec.txt-0.4"></a>
+
+## A bad hybrid encryption algorithm, for legacy purposes {#legacy-hybrid-encryption}
+
+Some specifications will refer to the "legacy hybrid encryption" of a
+byte sequence M with a public key KP.  It is computed as follows:
+
+```text
+      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.