Thus spake Nick Mathewson (nickm@torproject.org):
I should share with the list an update of where I am with a design for an improved relay crypto protocol. For background and motivation, please see the last thread on the topic [Prop202].
There are three main questions remaining for me in choosing among new relay crypto protocols. Basically, they are: "Am I comfortable with this system?", "Among systems I'm comfortable with, how good is this system?", and "Do I know how to implement this system?"
Unfortunately, the stuff I am currently comfortable with and know that I could implement is not nearly as good as the stuff that I'm _nearly_ comfortable enough to use and I don't know how to implement.
Let's talk about some designs in detail, using the same terminology as proposal 202.
[*snip*]
II. WIDE-BLOCK DESIGNS
[*snip*]
I am a little intimidated by the idea of trying to implement one of these ciphers.
I too am worried that trying to code and deploy relatively new constructions is likely risky, or at least very tricky.
Above, I haven't taken one of our requirements into account: that any change to a single cell must make all future cells unrecoverable.
Will UDP transports make this even more tricky?
There are modes that are supposed to prevent this, and applying them to a decent wide-block cipher might solve the issue. IGE is one of them [IGE], but it turns out to be broken by an attacker who knows some plaintext. The Accumulated Block Chaining [ABC] construction is supposed to fix that; I'm not too sure whether it's correct or efficient.
Am I crazy to think we might try to stop the bleeding of tagging attacks by figuring out a way to use ABC or IGE mode as a stopgap until people can code and evaluate new constructions for performance and timing side-channels? ABC/IGE would "only" involve a mode change, rather than an entire relay protocol upgrade and new cipher coding..
IGE might also actually exist in OpenSSL: http://www.links.org/?p=137
It also sounds like IGE is only broken if we try to use it for authentication.. We don't really need that property, do we? What we really want is the plaintext corruption property at the middle node upon ciphertext modification..
We could also remove a lot of known plaintext by replacing zero-fill with random fill in RELAY_RESOLVE, RELAY_BEGIN, and other short relay cells. That should only be expensive at the client...
VI. References
[Prop202] https://lists.torproject.org/pipermail/tor-dev/2012-June/003649.html
[Ferguson] Niels Ferguson, "Authentication weaknesses in GCM", 2005. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Fergus...
[DJB-Timing] Daniel J. Bernstein, "Cache-timing attacks on AES", 2004. http://cr.yp.to/papers.html#cachetiming
[DJB-Comm] Daniel J. Bernstein, personal communication
[Poly1305-Trunc] http://osdir.com/ml/encryption.poly1305/2005-09/msg00007.html
[ARMv8] "ARMv8 Instruction Set Overview", 2011, http://board.flatassembler.net/download.php?id=5698
[Bear-Lion] Ross Anderson and Eli Biham. "Two Practical and Provably Secure Block Ciphers: BEAR and LION". http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf
[Efficient-Tweakable] Palash Sarkar, "Efficient Tweakable Enciphering Schemes from (Block-Wise) Universal Hash Functions". 2008. http://eprint.iacr.org/2008/004.pdf
[IGE] Gligor and Donescu, "On Message Integrity in Symmetric Encryption" has the good IGE analysis: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ige/ige-s... The original IGE proposal was by Carl Campell in an old NIST publication that I can't find online; the paper above has a reference for it if you want to chase it more.
[ABC] Lars R. Knudsen, "Block Cipher Chaining Modes of Operation". http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/abc/abc-s...
[HCTR] Peng Wang, Dengguo Feng, and Wenling Wu. "HCTR: A variable-input-length enciphering mode." 2005. http://delta.cs.cinvestav.mx/~debrup/hctr.pdf
[HCH] Debrup Chakraborty and Palash Sarkar. "HCH: A new tweakable enciphering scheme using the hash-encrypt-hash approach." http://biblioteca.cinvestav.mx/indicadores/texto_completo/cinvestav/2006/136...
[TET] Shai Halevi. "Invertible universal hashing and the TET encryption mode." 2007. http://www.iacr.org/archive/crypto2007/46220405/46220405.pdf _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev