[tor-dev] Even more notes on relay-crypto constructions

[Mike Perry]

Thus spake Nick Mathewson (nickm at 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/Ferguson2.pdf
> 
> [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-spec.pdf
>       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-spec.pdf
> 
> [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/136034_1.pdf
> 
> [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 at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

-- 
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20121018/5bc89de4/attachment.pgp>