Re: some related work on tagging attacks

[David Hopwood <david.hopwood@zetnet.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----

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

- -- 
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPVmOVzkCAxeYt5gVAQETzwf/RpooqAVoCCUiuPjy5nEYgqi421ue0G3V
akBQbqWn/PKp8F7kJhVpHaAJCplj4P05RX/QwGvtg3xH3sWGbOJAd6+fVi1Wjmrj
ZpIAbIOt2zaCjcOjndzro6wFH/k8UxUJLNzriLrXSCR3m/9BOyRX+peHAVz0VbVx
h5YGaVPdr+w649dlV5EfuC9U1tjJlcXLB+ocrNk7f9jAgWERDCyFhkx8VRSJdTfv
y2PwJ6kdXozwskSzYUXDfHKj08G39BKrwWSG+kZ9v7v23Jj2hhBjG+lIjEbZyDoJ
ZVRAb0G9AcWRxOfZJRDo/WCZdjTewECVsyUes8UrtrwY+83cNuAJIg==
=+qMt
-----END PGP SIGNATURE-----