Discussion:
Questions on Anderson's "Dancing Bear"
Lon Willett
2004-06-17 20:03:03 UTC
Raw Message
I'm hoping some of you crypto gurus can help me: I have some questions
about Ross Anderson's paper "The Dancing Bear - A New Way of Composing
Ciphers" <http://www.cl.cam.ac.uk/ftp/users/rja14/grizzle.pdf>.

I am wondering about the significance of the parameters used in his
definition of a "grizzle":

G_N(M) = Pi(N,M,c(N,M))

where M is the message (plain text), N is a "random nonce", c() is a
checksum, and Pi is a fixed pseudo-random permutation.

First, it seems to me that the "random nonce" (i.e. N) is really a
misnomer. It clearly must be kept secret, and contain sufficient
entropy to be "unguessable", in order for the Jakobsson-Stern-Yung
construction to be secure. This is more "key-like" than "nonce-like",
so perhaps a name like "grizzle key" would be more appropriate. Or
have I misunderstood?

Next, I am unclear on the significance of the "checksum" (i.e. c()).
Its purpose would seem to be solely to provide message integrity. If
so, then it should be a cryptographic checksum of sufficient length
for one's security purposes (e.g. SHA-1 truncated to 80 bits). Or is
there some other significance buried in the proofs?

Finally, it seems then that a grizzle is (more or less) just an
encryption of a message with a random key, which includes the key
modified in a cipher-text dependent fashion. So it could be
implemented somewhat more straightforwardly as:

C = E(K,M),
G_K(M) = (H(C) xor K) || C
where
E(K,M) is the authenticated encryption of message M using key K,
K is a random key of the correct size,
H(C) is a cryptographic checksum of C of the appropriate size,
and "||" is concatenation.
e.g.
E(K,M) is AES-256 encryption of M with key K using EAX mode with
empty header and empty nonce and a 128 bit tag,
H is SHA-256,
K is a randomly chosen 256 bit value.

Or, again, is there something that I don't understand? What does
Anderson's construction accomplish that this doesn't? Is this at
least close to the same (meaning that it might need tweaking to get
the proofs to work out, but roughly does the same thing)?

Thanks.

Lon Willett
Richard Clayton
2004-06-29 18:13:23 UTC
Raw Message
Post by Lon Willett
I'm hoping some of you crypto gurus can help me: I have some questions
about Ross Anderson's paper "The Dancing Bear - A New Way of Composing
Ciphers" <http://www.cl.cam.ac.uk/ftp/users/rja14/grizzle.pdf>.
ObDeclaration: Ross is my PhD supervisor ... but I haven't discussed
this with him, so if it turns out that I've screwed up the answer this
reflects entirely on me and not on him :)
Post by Lon Willett
I am wondering about the significance of the parameters used in his
G_N(M) = Pi(N,M,c(N,M))
where M is the message (plain text), N is a "random nonce", c() is a
checksum, and Pi is a fixed pseudo-random permutation.
First, it seems to me that the "random nonce" (i.e. N) is really a
misnomer. It clearly must be kept secret, and contain sufficient
entropy to be "unguessable", in order for the Jakobsson-Stern-Yung
construction to be secure.
it must not be available to anyone who has not unpicked the grizzle, so
in that sense, yes it must be secret and unguessable
Post by Lon Willett
This is more "key-like" than "nonce-like",
A key suggests that it might be shared with someone, or that the value
is used during the process of revealing the message ... and it isn't.

There isn't actually a key (in the way that word is usually used) in
this part of the paper -- anyone who wishes can unpick the grizzle (and
in doing so will reveal the nonce).

It's only when later operations are done upon the result that only
people holding keys can unpick the key operation, and only once they've
done that is the grizzle visible for unpicking and only when they've
finished unpicking the grizzle will the nonce be visible to them.
Post by Lon Willett
so perhaps a name like "grizzle key" would be more appropriate. Or
have I misunderstood?
IMHO, the only key at this point in the paper was the (publicly
declared) 0 in the BEAR construction
Post by Lon Willett
Next, I am unclear on the significance of the "checksum" (i.e. c()).
Its purpose would seem to be solely to provide message integrity.
it convinces you that the unpicking has been successful. This is quite a
useful thing to know :)

It just appears, unheralded, at the end of the message, which might make
you think about things being appended, but since Pi is applied before
any bad people can mess with the byte stream, I can't immediately see
how that can be turned into an attack.
Post by Lon Willett
If
so, then it should be a cryptographic checksum of sufficient length
for one's security purposes (e.g. SHA-1 truncated to 80 bits).
Ross mentions SHA, so yes that would be suitable -- I don't see why
you'd wish to reduce its length.

To be honest, for a strong function Pi I'd doubt that a CRC of similar
length would make it any less secure a construction .. but everyone
would be entirely sceptical so I doubt it would wise :)
Post by Lon Willett
Or is
there some other significance buried in the proofs?
Finally, it seems then that a grizzle is (more or less) just an
encryption of a message with a random key, which includes the key
modified in a cipher-text dependent fashion. So it could be
C = E(K,M),
G_K(M) = (H(C) xor K) || C
where
E(K,M) is the authenticated encryption of message M using key K,
K is a random key of the correct size,
H(C) is a cryptographic checksum of C of the appropriate size,
and "||" is concatenation.
Suppose that E was just simple encryption (3DES say). If someone flips a
bit in the value of G_K(M) as it travels over the wire then when you
unpick your construction you will get garbage out as the contents of M
when you decrypt .... BUT you will not get any indication that it is
garbage. This makes this construction somewhat less desirable IMHO...
Post by Lon Willett
E(K,M) is AES-256 encryption of M with key K using EAX mode with
empty header and empty nonce and a 128 bit tag,
...however, if you use only of these fancy new-fangled :) encryptions
that also does authentication then, agreed, you would not get that
problem....

... whether you think that using "authenticated encryption" is more
"straightforward" than a "pseudo-random permutation" seems to me to be
the sort of thing that people take positions on without necessarily
being able to construct such devastating arguments that others will
concede they were wrong :)

... though I suppose you might get out a stopwatch and equate straight-
forwardness with coding time or execution time [comparing a hash and a
decrypt against an un-permute and a 'checksum'] or how long till the
onlookers drift away...

--
richard Richard Clayton

They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety. Benjamin Franklin