Re: some related work on tagging attacks

[Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>]

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.


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