On 6/19/12, Nick Mathewson nickm@freehaven.net wrote:
Filename: 202-improved-relay-crypto.txt
1.4. A note on algorithms
This document is deliberately agnostic concerning the choice of cryptographic primitives -- not because I have no opinions about good ciphers, MACs, and modes of operation -- but because experience has taught me that mentioning any particular cryptographic primitive will prevent discussion of anything else.
Not particularly agnostic, because you're specifying a different set of primitives than the protocol actually requires. See below.
Please DO NOT suggest algorithms to use in implementing these protocols yet. It will distract! There will be time later!
OK, fine. I won't prove that the cryptographic primitives which your protocols really require can be implemented in terms of existing low-level primitives and constructions.
If somebody _else_ suggests algorithms to use, for goodness' sake DON'T ARGUE WITH THEM! There will be time later!
Design 1: Large-block encryption
In this approach, we use a tweakable large-block cipher for encryption and decryption, and a tweak-chaining function TC.
2.1. Chained large-block what now?
We assume the existence of a primitive that provides the desired properties of a tweakable[Tweak] block cipher, taking blocks of any desired size. (In our case, the block size is 509 bytes[*].)
It also takes a Key, and a per-block "tweak" parameter that plays the same role that an IV plays in CBC, or that the counter plays in counter mode.
The Tweak-chaining function TC takes as input a previous tweak, a tweak chaining key, and a cell; it outputs a new tweak. Its purpose is to make future cells undecryptable unless you have received all previous cells. It could probably be something like a MAC of the old tweak and the cell using the tweak chaining key as the MAC key.
(If the initial tweak is secret, I am not sure that TC needs to be keyed.)
[*] Some large-block cipher constructions use blocks whose size is the multiple of some underlying cipher's block size. If we wind up having to use one of those, we can use 496-byte blocks instead at the cost of 2.5% wasted space.
You're talking about a particular cryptographic primitive here. (Some underlying ciphers (e.g. Skipjack) operate on 8-byte blocks, so you would only reduce the large-block block cipher to 504-byte blocks at the cost of about 1% wasted space.)
Since you've crossed the ‘mentioning specific primitives’ line by suggesting a kludge to support AES-biIGE, I might as well point out that large-block block cipher constructions can generally be modified to extract entropy from the message and key during encryption/decryption into an extra output (which may need to be kept secret). This extra output can be hashed with a longer-term ‘chaining key’ and/or the previous large-block block cipher key to produce a new large-block block cipher key (or to produce a new tweak for the large-block block cipher, if you insist on using underlying primitives (mumble *AES* mumble mumble) which are too inefficient to use without per-key precomputation).
Design 2: short-MAC-and-pad
In this design, we behave more similarly to a mix-net design (such as Mixmaster or Mixminion's headers). Each node checks a MAC, and then re-pads the cell to its chosen length before decoding the cell.
This design uses as a primitive a MAC and a stream cipher. It might also be possible to use an authenticating cipher mode, if we can find one that works like a stream cipher and allows us to efficiently output authenticators for the stream so far.
NOTE TO AE/AEAD FANS: The encrypt-and-MAC model here could be replaced with an authenticated encryption mode without too much loss of generality.
Here you are assuming that MAC(a | b) can be efficiently computed from PreMAC(a) and b for some function PreMAC, and that either the MAC does not require a per-message nonce or PreMAC is independent of the nonce. (In particular, you are assuming HMAC or a Poly1305-AES-like MAC, and forbidding some faster and/or safer polynomial-evaluation MACs.)
Many MACs (possibly not polynomial-evaluation MACs, though) can be used to authenticate the stream of cells: let p be the full output of the MAC for the preceding cell, and compute MAC(cell_index, p | cell_data) as the MAC for the current cell (then stick a possibly truncated copy of that on the cell for transmission). (And now, instead of specifying a particular authenticated encryption primitive as Nick did, I'm specifying a particular AEAD primitive with a(n extra) ‘chaining’ output. AE and AEAD are primitives themselves, not things that must be kludged up as cipher modes for a (small-block) block cipher (unless you're NSA and you're trying to force-feed everyone AES).)
Robert Ransom