[messaging] Deniable authenticated group messaging

Ximin Luo infinity0 at pwned.gg
Sat Apr 18 05:13:09 PDT 2015

On 18/04/15 00:00, Michael Rogers wrote:
> On 17/04/15 22:35, Ben Laurie wrote:
>>     It's not a fantasy requirement, it's a standard property of MACs. If
>>     Alice and Bob share a MAC key and Alice uses it to create a MAC, Bob
>>     knows that since he didn't create the MAC, Alice must have done. But Bob
>>     can't prove to Carol that it was Alice rather than Bob who created it.
>> If Carol knows everything Bob knows, then Carol also knows Alice created
>> it. That's my point.
> I see, thanks for explaining. Even if Bob shares his private key with
> Carol, Carol doesn't know whether he shared it with anyone else. So
> Carol doesn't know whether the MAC was created by Alice or an accomplice
> of Bob.
> Bob knows he hasn't shared his private key with anyone else, but he
> can't prove it.
>> I don't believe it is possible for Bob to prove there is no Carol.
> Indeed, and it's not possible for Bob to prove there's only one Carol.
>> All I'm really saying is the property you can have is something a little
>> weaker, as Ximin has expounded on at some length.
> I'm not sure how much of Ximin's message applies, as he's talking about
> ciphertext transcripts whereas I'm talking about plaintext.

Deniability is a property that the ciphertext may have. (I use the term loosely to refer to the public output of any protocol, so e.g. plaintext+signature would count in this definition and fail deniability.)

Plaintext is intrinsically deniable with no further effort - anyone can fake any amount of plaintext, and there's nothing cryptographically associated with this to prove anything to anyone. Whether it's plausibly convincing that Bob could have faked 3GB worth of Alice talking, is another matter outside of the scope of "deniability". In fact, as Trevor points out here and elsewhere, it is this intrinsic property of the plaintext that we also want the ciphertext to have (but also be able to authenticate it). My previous email was outlining ways you can try to achieve this, and limits to what you can achieve.

Is the property you're thinking of any different from the "deniability" that OTR refers to? Because that's what I thought you meant, and what my previous and current emails are talking about.

I have not explored this area in much more depth that what I already said, but if I was going to solve your problem myself right now, I would start by looking at the "Composability and On-Line Deniability of Authentication" paper mentioned previously. (I haven't yet done this myself, but it looks good at a first glance.)

I also found [1] useful in defining the security properties and threat models more precisely in terms of security games. It's quite accessible, requires little background, and the proofs are relatively easy to follow.

[1] Deniable Authentication and Key Exchange https://www.dmi.unict.it/diraimondo/web/wp-content/uploads/papers/deniability-ake.pdf



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150418/4363f75b/attachment.sig>

More information about the Messaging mailing list