Re: some related work on tagging attacks

[George Danezis <gd@theory.lcs.mit.edu>]

Bodo,

Thanks for your paper, it has been interesting reading. I have a few notes 
that I thought you might find useful:

1 - In section 2, near the end of paragraph one you describe the problem
that the final receipient knows the route length of the message by finding
out how much padding is present. This can be avoided, as we do in
mixminion, by adding the padding at the end of a fixed length header. This
wastes some space, and makes the maximum route length smaller, but has the
advantage of keeping the route length secret for everyone but the original
sender.

2 - Markus Jakobson has done some similar work about hybrid mixes. His
page is http://www.rsasecurity.com/rsalabs/staff/bios/mjakobsson/ and the
paper I am thinking of is

M. Jakobsson, A. Juels, "An Optimally Robust Hybrid Mix
                             Network", PODC '01 (ps,pdf) 
http://www.rsasecurity.com/rsalabs/staff/bios/mjakobsson/hybridmix/hybridmix.pdf

He has done a lot about proving things about mixes so you might be 
interested to have a look.

3 - It is worth thinking how to do reply blocks. ... ?

Hope the above help,

George

On Wed, 14 Aug 2002, Bodo Moeller wrote:

> On Tue, Aug 13, 2002 at 10:55:55PM +0000, David Hopwood wrote:
> > Bodo Moeller wrote:
> 
> >>      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.
> 
> > Here's the problem:
> > 
> > ====
> > AFAICS, the proof in section 4
> 
> Appendix B now.
> 
> >                                is correct as far as it goes. However, I'm not
> > convinced that it's proving the right thing. The [chain_encrypt] algorithm
> > takes an input Ci such that 0 <= |Ci| < l - KEM_Mj.CipherLen - MAC_Mi.OutLen.
> > So, the proof shows that the scheme is non-malleable on those inputs.
> > 
> > The property we really need, though, is that the decryption operation of a
> > mix "randomises" each message, so that if we have a batch of non-equal
> > ciphertexts, decrypting them and destroying the original ordering will ensure
> > unlinkability and resistance to tagging attacks. Since the decryption is only
> > required to match a prefix of the original plaintext (i.e. excluding the
> > padding), this isn't implied by non-malleability/IND-CCA2.
> > 
> > More specifically, there are two ways in which a scheme that is secure according
> > to section 3.1 of the paper can fail to be secure when used in a mix-net:
> > 
> >  - it can fail to hide length (for example, an ordinary IND-CCA2 PKE scheme
> >    with prefix-free ciphertexts, padded to length \ell with zeroes),
> >  - the padding can leak information that links plaintexts and ciphertexts
> >    (for example, an IND-CCA2 scheme where the padding added on decryption is
> >    a simple function of the ciphertext).
> > 
> > I think your construction prevents these problems, but I don't think you've
> > proven it.
> 
> Which is why in the final paper I'll define unlinkability against
> passive attacks (Adv_link or somethink like that; the attacker sees
> two ciphertexts and the two resulting decryption results in either the
> original or permuted order and has to guess whether they are permuted
> or not).
> 
> Unlinkability against *active* attacks is not possible in the most
> general case (the attacker can suppress all but a single one of the
> legitimate ciphertexts and substitutes new ciphertexts for them), so
> one has to settle for less.  Various active attacks can be prevented
> -- it is crucial to prevent replay attacks (as noted in the
> introduction), and modified replay does not work according to my CCA
> result.
> 
> 
>