Subject: [MLS] Deniability without pairwise channels.

From: Mathias Hall-Andersen <[email-masked]>
Date: Wed, 22 Jan 2020 15:34:17 +0100

Dear MLS group,

In MLS: since all group members share the same secret,
the application of an AEAD does not provide authentication within the group,
MLS mitigates this using sign-then-encrypt with a long-term signing key.

> [[ OPEN ISSUE: Signatures under the identity keys, while simple, have the side-effect of preclude deniability.
> We may wish to allow other options, such as (ii) a key chained off of the identity key,
> or (iii) some other key obtained through a different manner,
> such as a pairwise channel that provides deniability for the message contents.]]
>
> -- Section 12.2 Authentication

If deniability (without pairwise channels) is a desired feature in MLS,
has the group discussed the feasibility of applying a "sign & reveal" type scheme?
There are essentially two different options:

1. Short-term credentials:

Clients would generate temporary "credentials" pk_{temp} for the group,
by creating a certificate under their long term credential pk_{long term}:

S <- Sign(sk_{long term}, <Group Identifier, Expiry, pk_{temp}>)

Publish (S, pk_{temp}) to the group.

Then when sending messages apply sign-then-encrypt using the short-term credential:

S_{msg} <- Sign(sk_{term}, m)
c <- Seal(k, .., .., <S_{msg}, m>)

Later, e.g. in lock-step with updates to the ratchet tree,
the client publishes sk_{temp} to the group and generates a new short-term credential.

2. One-time credentials:

When sending messages apply sign-then-encrypt using a one-time credential:

S_{cert} <- Sign(sk_{long term}, <Group Identifier, Message Index, pk_{temp}>)
S_{msg} <- Sign(sk_{term}, m)

Then encrypt:

c <- Seal(k, .., .., <S_{cert}, S_{msg}, sk_{old}, m>)

Where k is the group key and sk_{old} is the sk_{temp} from the previous message.

Best Regards,
Mathias

---

From: Raphael Robert <[email-masked]>
Date: Wed, 22 Jan 2020 16:54:41 +0100

Hi Mathias,

For general context: Deniability is something that is being discussed right now and we should send some update to the list as soon as we have sorted things a bit better.

I hope I understood your correctly, you are essentially proposing a “sign & reveal” scheme. If not, I’m sorry, and please let me know.

What has become clearer in some of the discussion is that a “sign & reveal” scheme puts the burden of proof on the victim to some (large) extent. The attacker can publish a signature chain that starts with the public identity of the victim and ends with the signature of a specific message. This signature chain will most likely look valid to a third party at first sight. It then becomes the duty of the victim to prove that they indeed published secret keys and that therefore anyone could have signed the last part in the signature chain. For the victim, this is painful at best and impossible at worst. It would be much nicer if the attacker couldn’t publish such a signature chain in the first place.

There might be another problem, regarding synchronicity: since MLS is completely asynchronous no one should publish a secret key too early (i.e. before others have consumed the encrypted messages) otherwise we might not be able to trust the authentication any longer. 

But I fully agree that your proposal is obviously much more efficient than a 1:1 fanout.

Thanks

Raphael

> On 22 Jan 2020, at 15:34, Mathias Hall-Andersen <[email-masked]> wrote:
> 
> Dear MLS group,
> 
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 22 Jan 2020 12:21:26 -0500

> On 22 Jan 2020, at 10:54, Raphael Robert <raphael=[email-masked]> wrote:

Interesting thanks!

I suppose the victim could often be prevented from providing this proof too, like by evidence being “lost”, making this worse than no deniability.

It appears the golden rule for deniability is
  (*) anytime the parties have unequal power then deniability heavily favours party with more power,
so your observation provides a case when “sign & reveal” just makes (*) even worse.

I’ve never seen a “user story” that contradicts (*) but please do let me know if you think you know one, maybe off list if that’s a derail here.  I’d love to participate in some more user oriented formalisation of deniability eventually.  I do think deniability becomes useful when both parties have relatively equal power, although maybe the user interface suffices for the common messaging cases, but presumably properties related to full deniability become really useful in layer 2 blockchain scaling solutions like state channels.

Anyways in the vein of "sign & reveal” making (*) worse, I also want to caution that deniability schemes based on ring signatures actually make (*) worse because they prove that some party made the comment.  If you assume the parties have unequal power, as in a court case, then a ring signature effectively means the more powerful party can convince the court that the less powerful party signed the document.

Jeff

---

From: Jon Callas <[email-masked]>
Date: Wed, 22 Jan 2020 11:59:48 -0800

> On Jan 22, 2020, at 7:54 AM, Raphael Robert <raphael=[email-masked]> wrote:
> 

Please do. I have some tart opinions about deniability, and don't want to waste anyone's time before we know what we're really talking about.

It's also probably best not to talk about things like courts and so on.

There are a number of reasons, starting with jurisdictional issues. Inevitably, each of us will talk about legal issues through the lens of our own native jurisdiction and that lens is cracked with our own misunderstandings of law and procedure, not to mention that these things do change over time. A procedural stage setting of today may not be the setting of a decade from now.

Lots of protocols talk about "deniability" and it's often a weird concept that is a term of art and doesn't mean at all what a reasonable person might think. I've had some discussions with people about the "deniability" of OTR and others, where it doesn't mean what any non-expert would think it does.

There are other deniability issues that are peculiar. A way that I've characterized this issue is that deniability assumes that your adversary is either stupid or good. By "stupid" I mean that they understand what deniability is, and might not even look for it. (e.g. hidden volumes in Truecrypt). By "good" I mean that you're going to give some mathematical explanation and they'll accept it. If the adversary is smart and evil, deniability can be a weakness, not a strength.

Here's an example, again with Truecrypt hidden volumes. I once talked to some customs officials in a country that's not mine, and I asked them about hidden volumes. They said, "Oh, yeah, we know about hidden volumes and if we see Truecrypt, we *assume* there's a hidden volume. Why would anyone use Truecrypt and not have a hidden volume?" That might not be precisely evil, but it shows a basic issue. True evil would be that after getting to the hidden volume, they ask you to open up the hidden volume in the hidden volume. You reply that there's only one level of hidden volume and they reply (knowing that you're right, but because they're evil), "That's your story. This is open source software. Open up the other hidden volume."

Another form of assumption as either smartness or evil is that if you have a ring signature that could have been made by Alice, Bob, or Charlie, they just assume that Alice made it and let Alice know that's they're working hypothesis since she's their suspect. (I don't want to go too far down this rathole, but it might be the smart way to bet. Suppose the signature was made at 4am Pacific or 12pm GMT and Alice is the only European in that set -- it's a reasonable hypothesis that Alice made it.)

Thus, when we talk about deniability, let's talk about the specific security property and not an aspirational thing like "deniable" that might not work out the way we think. If the property is that a signature could be made by any element of a set, that's a nice property, even if there are externalities that can winnow that set down, even to a single member.

	Jon

---

From: Raphael Robert <[email-masked]>
Date: Wed, 22 Jan 2020 21:40:44 +0100

> On 22 Jan 2020, at 20:59, Jon Callas <[email-masked]> wrote:
> 
> 
> 

I agree with the above. Ideally we would like to combine academic precision with common sense definitions and be clear about the threat model too. I also agree that we should leave aside legal considerations for all the reasons you mentioned and focus on the social aspect of the facets of deniability.

We’ll chew through the existing material to see what could make sense in terms of properties and how we could achieve them in practical terms. Obviously not all aspects of deniability are straight forward in a group messaging protocol, all the more so since MLS has strong authentication guarantees that 1:1 protocols might not have.

Raphael

---

From: Sofía Celi <[email-masked]>
Date: Thu, 23 Jan 2020 20:42:28 -0500

Hello!

Very interesting insight!

> What has become clearer in some of the discussion is that a “sign & reveal” scheme puts the burden of proof on the victim to some (large) extent. The attacker can publish a signature chain that sta…

The "sign & reveal" mechanism is something that can be considered coming
from OTR, because in it you reveal the MAC keys. But the idea, since the
first paper of OTR[1] was to use the revelation of keys as an additional
measure to expand the set of possible message forgers. Message
unlinkability and deniability was provided in some previous version of
OTR by using MAC keys instead of long-term keys for signing messages.
OTR even provides a stronger notion for it by also using malleable
encryption so anyone can forge a message. So only revealing keys is not
enough to achieve strong offline deniability. OTR also used an
authenticated key exchange where conversation partners are able to reuse
ephemeral keys signed by the other party in forged transcripts, thereby
providing partial participation repudiation. This insight by Trevor
Perrin is nice to read[2]

It depends on what kind of notions of deniability want to be provided.

> There might be another problem, regarding synchronicity: since MLS is
completely asynchronous no one should publish a secret key too early
(i.e. before others have consumed the encrypted messages) otherwise we
might not be able to trust the authentication any longer.

This is super interesting and it is problem ;), see section '3.4 Message
Integrity' of this paper[3].

I think the notions of deniability in a cryptographic sense have evolved
and new ways of achieving it have been studied. So many things can be
done ;)

1. https://otr.cypherpunks.ca/otr-wpes.pdf
2. https://lists.cypherpunks.ca/pipermail/otr-dev/2013-July/001796.html

-- 
Sofía Celi
@claucece
Cryptographic research and implementation at many places
FAB9 3EDC 7CDD 1198 DCFD  4558 91BB 6B45 6F44 2D02

---

From: Sofía Celi <[email-masked]>
Date: Thu, 23 Jan 2020 20:47:45 -0500

I forgot to include paper [3]

3. http://www.jbonneau.com/doc/BM06-OTR_v2_analysis.pdf

Thanks!

---

From: Natanael <[email-masked]>
Date: Sun, 26 Jan 2020 16:09:09 +0100

I have previously suggested a method for deniable authentication using a
VDF (verifiable delay function);

This variant of deniable authentication would use a VDF construction with a
private key based shortcut function (like a PKE / VDF hybrid function),
implementing a challenge-response protocol where the verifier uses the
prover's public key to construct a challenge which only the prover can
immediately respond correctly to, but where the correct response value will
also automatically become public later on (since anybody can solve the VDF,
but not fast enough).

See more here: https://www.reddit.com/r/crypto/comments/bt7cq4

This construction provides authentication trough latency / provenance /
time asymmetry - as the verifier you know that you just constructed the
challenge with fresh randomness, and you know that only the private key
holder can respond before the timeout, while anybody else will be unable to
reply before the timeout / expiration of the challenge.

For example, a correct reply within a second when the VDF takes at minimum
an hour to solve is a certain proof of authentication.

This also means a genuine live session is indistinguishable from a forged
live session, since you can trivially pre-compute inauthentic replies to
your own arbitary challenges.

For example, Alice and Bob can authenticate to each other in a live genuine
session while Carol and Dave can simultaneously conspire together to
pretend to be Alice and Bob in their own separate inauthentic session. Eve
can not distinguish between these two sessions even when watching the
traffic live, because Eve don't know how the respective challenges were
chosen (fresh or pre-computed).

This should at minimum be an improvement over ring signatures (there's no
longer a limited group of possible provers), and many similar
constructions. The inherent automatic disclosure via the VDF is also an
improvement over manual MAC disclosure, and the prover does not otherwise
need to actively take action to disassociate themselves from the session
contents.

It would also be KCI attack resistant, since since disclosure of your
private key does not impact your ability to securely verify other's
responses to your challenges.

Note 1: I have not currently worked out how to best solve session binding,
this may vary between different protocols and VDF primitive. You need to
bind to session ID:s / session keys in some way. Perhaps by introducing
them as variables in the VDF construction.

Note 2: I don't currently know of a specific VDF primitive that would be
suitable for this. If there's no VDF construction that can do this
stand-alone, then this can still be done in a less elegant manner by
constructing the challenge message as a trio of VDF encrypted challenge,
public key encrypted challenge, and a Zero-knowledge proof that show the
two are equivalent.

The prover verifies equivalence first and then decrypt and returns the
challenge value, while the VDF still serves as a way to ensure the
transcript proves nothing after the fact.

Den fre 24 jan. 2020 02:47Sofía Celi <[email-masked]> skrev:

> >> What has become clearer in some of the discussion is that a “sign &
> reveal” scheme puts the burden of proof on the victim to some (large)
> extent. The attacker can publish a signature chain that starts with the
> public identity of the victim and ends with the signature of a specific
> message. This signature chain will most likely look valid to a third party
> at first sight. It then becomes the duty of the victim to prove that they
> indeed published secret keys and that therefore anyone could have signed
> the last part in the signature chain. For the victim, this is painful at
> best and impossible at worst. It would be much nicer if the attacker
> couldn’t publish such a signature chain in the first place.
> >