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

[Nick Mathewson]

On Thu, Oct 18, 2012 at 6:10 PM, Mike Perry <mikeperry at torproject.org> wrote:
 [...]
>> 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..

ABC or IGE wouldn't help us much on their own without a wide-block
cipher, and IGE is just plain broken. (See explanation below.)

Remember, in the document I originally sent, I was talking about using
ABC or some other corruption-propagation mode at a block level.  That
requires a wide-block cipher, though.  And it turns out we can do
better if the corruption-propagation is part of the wide-block idea.

We'd also burn our performance on platforms without AES acceleration, I think.

> 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..

That _is_ a kind of authentication, or an analogue to it.  And the
point is that an adversary can repair a hole in the stream, and *stop*
the plaintext corruption.  So IGE does not deliver the property we
would want for it, even if we could use it.

Check out this thread, and the stuff it references:
   http://www.mail-archive.com/cryptography@metzdowd.com/msg06599.html

> 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...

So long as there is a block's worth of known or guessed plaintext, IGE
fails to ensure that changes propagate forward.  Like, 16 bytes worth
of guessable HTTP in a payload (if you're thinking about this in a
non-wide-block scenario).

Two general process thoughts:

* I may be saying this from an overabundance of caution, but: I don't
think we should use cryptographic primitives and constructions with
known flaws, even if we can't see a way for them to hurt us right now,
and even if we can come up with a solid-seeming argument for how those
flaws can't hurt us..  That's how we got into our AES-CTR mess in the
first place.

* I know everybody wants our crypto problems to get solved, but it's
critical to get this stuff right.  I think that the way to do right by
our users is by taking the time we will need to design the right thing
properly, rather than jumping into something halfcocked.  We all
acknowledge that it's easy for people and organizations to screw this
stuff up: so let's take our time and actually come up with something
solid.  Against the current pain and badness of our current system, we
must weigh the potential harm of jumping precipitously into something
that turns out to be broken because we didn't think about it hard
enough.

And a more general observation:

* I think the only thing we could get designed & analyzed enough to
include in Tor 0.2.4 would be hmac-and-pad, which nobody actually
likes much.  I think that by the time we get anything good here well
designed and discussed enough to reach a sensible consensus about it,
it will be 2013, and time to start adding features to 0.2.5 (at the
earliest).


So here's to getting it right!


yrs,
-- 
Nick