On 6/19/12, Nick Mathewson <[email protected]> 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! > > > 2. 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). > 3. 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 _______________________________________________ tor-dev mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
