Ciphers and constructions for use in a next-generation relay protocol


This is an attempt to list primitivies and constructions that we could use in our next-generation (0.2.4 or 0.2.5) reply encryption protocol. It

Nick is writing this. If you want to correct something where I am just plain wrong and you are sure I'll agree, that's cool. If you suspect that I might disagree with you, please instead write a comment with your name after it. If your comment is going to be "that's not true" or "no" or "that's stupid", please expect me to be annoyed unless you explain what you disagree with, what the truth is, and why you think so in enough detail to explain where I went wrong.

I'm going to be listing lots of constructions here, even ones we'd never use, just so XXXX


So far, I'm only hearing 3 recommendations for an underlying cipher: AES, Salsa20, and ChaCha.

Misc primitives

Many of the operations below require an algebraic field for evaluating polynomials over cipher blocks. The most common choice is GF(2128). This presents some trickiness. It's easy to add two elements, and to multiply by a primitive element of GF(2128), which is all that some of the constructions require, but multiplying two arbitrary elements is trickier. The fast implementations of multiplication in GF(2128) either use a specialized multiply-without-carry instruction from newer Intel CPUs, or use table lookups. But table lookups should make us worry about cache-related side-channel issues. There's an optimization you can use for a constant-time multiply of two elements, so long as you're willing to do precomputation on one of them to make a table. OpenSSL has other optimizations for this case, depending on what table size you like. Some could maybe be made constant-time.

Large-block constructions

There are a lot of these. The idea is to prXXXXX


These are unbalanced Fiestel networks using a multi-part key, a stream cipher, and a (in some cases keyed) hash function. They come from Anderson and Biham's Two Practical and Provably Secure Block Ciphers: BEAR and LIONESS . BEAR performs two hashes over most of the data, and one stream operation over most of the data; LION does two encryptions of most of the data, and two hashes over most of the data..

Neither BEAR nor LION are PRPs but not SPRPs: LIONESS is an SPRP. (The distinction as I understand it is that an SPRP resists an attacker who can choose ciphertexts.) I'm trying to find the relevant attack paper to see whether the deviation from ideal in BEAR and LIONESS matters to us, but we should probably assume it does.

Mixminion uses LIONESS.

Encrypt-mask-encrypt algorithms (CMC, EME)

These are CMC and EME. For these, there are two passes of encryption over the data, with a pass of masking in the middle where everything gets xored with something dependent on all the encrypted data. With CMC, the encryption step is CBC, which prevents parallelism while encrypting. With EME, the encryption step is ECB.

The efficiency isn't so great : they require two encryption passes over all the data. Also, EME is patented and CMC might be too, which kinda rules them out.


The biIGE construction uses a block cipher, and requires two encryption steps over the data: one forward, one backwards. These can't be parallelized. It needs 4 IVs for each block to be encrypted. It assumes that the plaintext is a multiple of the block size, and I can't find a way to fix that with ciphertext stealing.


Commonly used for disk encryption. Unsuitable because mangling a single block of ciphertext changes only a single block of the plaintext.


These are close to BEAR in their structure. (Find a link to "HCH: A New Tweakable Enciphering Scheme Using the Hash-Counter-Hash Approach". XXXXX) They involve doing a (possibly keyed) hash operation over most of the data, then doing a stream cipher, then another hash. Unlike BEAR, they involve more shenanigans when computing the stream cipher key and when encrypting the small part of the data in the unbalanced Feistel network. Also, they apparently involve a non-invertible universal hash function.

XCB is patented; the authors of the HCTR and HCH constructions seem hopeful but unsure concerning whether the XCB patent covers HCTR or HCH.

Universal-hash based approaches

For these, you apply an almost universal hash function* to the plaintext as a kind of cut-rate all-or-nothing transform, then encrypt with counter mode or ECB or something, and then apply the inverse of an almost universal hash function.

Variants include Naor-Reingold, PEP, TET, HEH, HCH, and so on. These can differ in the structure of the polynomial used for the universal hash, and in how the hash is constructed. The hash is usually built from GF(2128) elements, and requires either multiplications by a repeatedly used element, or arbitrary multiplications.

  • Most of these require different variants of universalness or almost-universalness. Remember, a universal hash is not the same thing as a cryptographic digest.

Because the XCB patent also involves a hash-encrypt-hash structure, it might not be a stupid idea to get a patent atty to see whether these are implicated, even though they're pretty different.

Ways to encrypt relay cells using large-block constructions

If all we have is an SPRP with no output suitable for chaining, the IGE construction seems like what the doctor ordered here. Maybe. Investigate the original IGE paper and its limitations, and other later constructions. (ABC? XXXX)

Authenticated encryption constructions

Last modified 5 years ago Last modified on Sep 29, 2012, 1:23:06 AM