Re: [MLS] Deniability without pairwise channels.

[Natanael <[e-mail]>]

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 <[e-mail]> skrev:

> I forgot to include paper [3]
>
> 3. http://www.jbonneau.com/doc/BM06-OTR_v2_analysis.pdf
>
> Thanks!
>
> On 1/23/20 8:42 PM, Sofía Celi wrote:
> > 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 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.
> >
> > 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
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>