[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: some related work on tagging attacks
On Mon, Aug 12, 2002 at 02:04:16PM -0400, 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. :}
I described a tagging attack countermeasure in an e-mail message to
Lance Cottrell in August 1998, which is reproduced below; you'll also
find mention of pseudo-random padding with a sender-specified seed in
the unfinished Mixmaster Protocol Version 3 draft from June (?) 2000.
The ideas have evolved over time, and by now I have finally written a
long-planned paper on the subject:
Provably Secure Public-Key Encryption for Length-Preserving Chaumian Mixes
http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#mixencrypt
David Hopwood has pointed out to me that my security model in this
paper neglects the unlinkability aspect. The final version of the
paper will discuss that the data expansion needed to maintain message
length, which is part of the output of a stream cipher in my
construction, does not provide linkability. (I'll also add an
acknowledgement to David -- I simply forgot to insert this when
deanonymizing the paper, which is also a conference submission.)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Lance --
while reading Ulf's current version of what is to become an Internet
Draft describing the Mixmaster protocol (version 2), it occured to me
that there there is a previously unnoticed (AFAIK) weakness against
active attacks that needs to be corrected for version 3.
The Security Considerations section already explains that
"Message integrity must be verified to prevent the adversary from
performing chosen ciphertext attacks or replay attacks with modified
packet IDs, and from encoding information in an intercepted message
in a way not affected by decryption (e.g. by modifying the message
length or inducing errors). This version of the protocol provides
integrity for the packet header sections only",
thus indicating that body integrity is neglected by the protocol (an
active attacker can mark a message by modifying some block of the
body, and only after the final hop when the payload is availabe in
clear this defect becomes visible). This can easily be fixed by
including an appropriate message digest of the body into each header.
The new attack is on headers themselves. There is already some
authentication for headers, namely a message digest over most of the
encrypted header part. However, this allows authentication only of
the one header section which is currently in the first slot.
Modifications to later header sections cannot be detected until, some
hops later, they have reached section one. This allows a similar
marking attack: Knowing that CBC decryption causes defects to
propagate "one block to the right" at each hop, a modification in one
of the header sections can be so prepared that it becomes detectable
when this header section has reached slot one. If the attacker
happens to be the one operating the corresponding mix, he can
recognize the marked message (other mixes likely would just throw it
away because the message digest over the encrypted header part is not
correct).
This shows that more authentication is necessary: When the message is
constructed, we need to provide each mix in the chain with means of
authentication for *all* of the message. This problem is non-trivial
because on the way through the chain, some random padding is put into
the 20th header section at each hop; and the mixes cannot know which
header sections contain real data (which needs authentication) and
which contain only junk (for which authentication seems hard to
achieve, because not the original sender is generating the random
numbers).
The solution is to specify a pseudo-random number generator (e.g., the
one from the NIST DSA standard) to be used for filling the dummy
header sections; each encrypted header part has to contain the seed
that the corresponding mix must use to create the new 20th header
section. This way, the original sender can predict what exactly the
message will look like at each stage, so that a message digest over
all the header sections can be added to the encrypted header part,
which will provide the necessary authentication.
Compared to the current protocol, message creation will be more
time-consuming. Currenctly, for a remailer chain of length
n, we need 1 + 2 + ... + n = (n + 1)/2 header encryptions. The
changed protocol will need 20 * n header en-/decryption (the
"decryptions" are of the pseudo-random header sections -- the sender
has to compute what they will look like at later stages because
otherwise he cannot provide authentication for them). Nothing is
changed for the message body (still n encryptions are needed).
Another slight disadvantage is that compatibilty with protocol
version 2 will be reduced. You will not be able to arbitrarily
intermix version 2 remailers into the remailing chain. Rather, the
chain will have to have an imaginary separation between version 3
remailers (the hops nearer to the sender, with full authentication)
and version 2 remailers (the hops nearer to the recipient,
insufficient authentication).
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
--
Bodo Möller <moeller@cdc.informatik.tu-darmstadt.de>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036