[tor-dev] Proposal 202: Two improved relay encryption protocols for Tor cells

[Robert Ransom]

On 6/19/12, Nick Mathewson <nickm at 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!
>
>
> 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