BEAR reconsidered [was Re: some related work on tagging attacks]

[Nick Mathewson <nickm@alum.mit.edu>]

On Mon, 2002-08-12 at 14:04, Roger Dingledine wrote:
> Was just looking over Ian's thesis
> (http://www.isaac.cs.berkeley.edu/~iang/thesis.html), and page
> 133 describes basic forward tagging attacks. He proposes that
> they be fixed via Integrity-aware CBC mode, as described in
> http://alternic.net/drafts/drafts-j-k/draft-jutla-ietf-ipsec-esp-iapm-00.html
> 
> We'll probably want to mention this mode when describing how it doesn't
> help us. :}

(Notes on why this mode doesn't work for us: (1) The integrity checking
is discretionary. (1') It isn't all-or-nothing. (2) The ciphertext is
longer than the plaintext. (2') Thus, decryption can't be used as
encryption; D(x) is not defined for all X.)

BTW, benchmarking shows that a FWD step spends roughly 47% of its time
in LIONESS.  Message generation spends about 90% of its time in LIONESS.
(The asymmetry is because RSA encrypt is about 20x as fast as decrypt.)
BEAR is about 2x as fast as LIONESS.  How sure are we of BEAR's
insecurity?  

Looking at Pat Morin's paper on BEAR's weaknesses (check out
http://citeseer.nj.nec.com/124166.html ), it looks as if both of the
attacks he cites are unlikely to work on us:

(A bear key is a pair of subkeys, K1 and K2.)

	Attack 1) An attacker who knows only K2 can recover
		  all but the first 160 bits of the message.
	Attack 2) An attacker can launch a meet-in-the-middle attack
                  on the two halves of a BEAR key.

Against attack 1: Right now, we're generating our subkeys as
	K1 = SHA1('key matter' || "nonce 1") 
    and K2 = SHA1('key matter' || "nonce 2").

    If an attacker can get either one, we're in trouble.

Against attack 2: The complexity of the meet-in-the-middle attack is
quoted as "approximately 2^(1+n/2)".  In our case, n=320, so this still
works out to out to ~ 2^160.   An attacker would be better off trying to
brute-force the original key matter, which is "only" 128 bits long in
the first place.

***** 
Sidenote: Check out
http://www.scs.carleton.ca/~morin/publications/crypto/aardvark-sac.ps.gz

Pat Morin proposes a block cipher called AARDVARK that resists the
attacks above.  Sadly, we can't use it, since len(E(x)) > len(x), and so
decryption can't be used as encryption.
****

Anyway, should we reconsider BEAR?  It would mean a 25% speed
improvement to FWD mixing, and roughly a 45% improvement to message
generation.  The attacks seem not to apply to us.

What do you guys think?

-- 
Nick