Subject: [MLS] Include signature in the confirmed transcript hash?

From: Marta Mularczyk <[email-masked]>
Date: Thu, 17 Sep 2020 15:52:54 +0200

Hi all,

 �

Together with Joël Alwen and Daniel Jost, we noticed some unexpected (at least to us) effects of the way transcript hash is computed. What are your thoughts on this?

 �

Details: Say Alice and Bob each processes a commit packet and they end up with the same epoch secrets. Expected guarantee: agreement on the secrets implies being in sync -- agreement on the group state, and being able to continue progressing epochs.

Problem: the latter is false if the packets processed by Alice and Bob only differ in the signature string (it's easy to come up with many equivalent ECDSA signatures, given only the signer's public key). Now Alice and Bob agree on the confirmed_transcript_hash, and hence on the current secrets, but not on the interim_transcript_hash, so they won't agree on the next epoch secrets. Result: they will never accept the same commit (due to not matching confirmation_tag) and so they'll never be in sync in the next epoch.

 �

This can be solved by including the signature in the confirmed_transcript_hash and not signing the confirmation_tag (the tag is also not part of the transcript_hash). We claim that this doesn't affect security. Assume Alice sends a commit and the adversary intercepts the packet. Consider these 3 cases:

- if the adversary doesn't know the current epoch secrets, then he can't modify any part of Alice's packet (due to AEAD/MAC security of the message framing).

- if he knows the epoch secrets but not Alice's signing key, then the only thing he can, in principle, modify is the confirmation_tag. However, the tag is fully determined by the signed part of the commit (and the transcript history).

- if he knows both, then the adversary can already produce any packet he wants on behalf of Alice.

 �

An additional advantage of this solution is that it simplifies the protocol by removing the interim_transcript_hash.

 �

In detail, a commit now proceeds as follows:

1. construct the MLSPlaintext with the Commit object and confirmation_tag=0,

2. sign the MLSPlaintext and include the result in the confirmed_transcript_hash,

3. advance the key schedule and update the confirmation_tag in the MLSPlaintext.

 �

If the working group generally agrees on the above approach, we'll be happpy to draft a PR.

 �

Best,

Marta

---

From: Natanael <[email-masked]>
Date: Thu, 17 Sep 2020 21:11:02 +0200

Den tors 17 sep. 2020 19:43Marta Mularczyk <[email-masked]> skrev:

> Hi all,
>
> Together with Joël Alwen and Daniel Jost, we noticed some unexpected (at
> least to us) effects of the way transcript hash is computed. What are your
> thoughts on this?
>
> Details: Say Alice and Bob each processes a commit packet and they end up
> with the same epoch secrets. Expected guarantee: agreement on the secrets
> implies being in sync -- agreement on the group state, and being able to
> continue progressing epochs.
>
> Problem: the latter is false if the packets processed by Alice and Bob
> only differ in the signature string (it's easy to come up with many
> equivalent ECDSA signatures, given only the signer's public key). Now Alice
> and Bob agree on the confirmed_transcript_hash, and hence on the current
> secrets, but not on the interim_transcript_hash, so they won't agree on the
> next epoch secrets. Result: they will never accept the same commit (due to
> not matching confirmation_tag) and so they'll never be in sync in the next
> epoch.
>
> This can be solved by including the signature in the
> confirmed_transcript_hash and not signing the confirmation_tag (the tag is
> also not part of the transcript_hash). We claim that this doesn't affect
> security. Assume Alice sends a commit and the adversary intercepts the
> packet. Consider these 3 cases:
>
I'd like to note that another option to changing what's hashed is to use an
algorithm designed to guarantee determinism with no malleability, like
Verifiable Random Functions (VRF).

There's currently an ongoing standardization process for VRF:s (one type
based on RSA, one based on ECC), see below;

https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-07

---

From: Richard Barnes <[email-masked]>
Date: Thu, 17 Sep 2020 18:21:40 -0400

Hi Marta,

Thanks for writing this up.  This analysis seems sound to me. It reminds me
of the structure of the server's first flight post-ServerHello in TLS [1]:

    AEAD(EncryptedExtensions Certificate CertificateVerify Finished)

That means you end up with (1) message content, (2) signature over message
content, (3) MAC that confirms agreement on the derived secrets (4) AEAD
authentication tag that verifies membership in the prior group (established
by the ClientHello/ServerHello).  Which I think is the same order you're
proposing here.  Just to restate to confirm I'm understanding:

MLSPlaintext.signature = Sign(sig_private_key; MLSPlaintext.group_id, ...
MLSPlaintext.proposal/commit/application)
confirmed_transcript_hash = Hash(confirmed_transcript_hash,
MLSPlaintext.group_id...MLSPlaintext.signature)
MLSPlaintext.confirmation_tag = MAC(confirmation_key,
confirmed_transcript_hash)

I don't think this completely gets us out of the need for the
interim_transcript_hash.  We will still need it if we want to include the
confirmation_tag in the transcript.  This seems like a good idea, analogous
to TLS including the Finished message in the transcript for post-handshake
messages [2].  (For the same reason, I would argue that the membership_tag
would *not* need to go in the transcript.)

There's also a bit of weirdness here arising from the fact that we use the
same framing for Commits, Proposals, and application data
(MLSPlaintext/MLSCiphertext).  In particular, the signature part is
shared.  So on the one hand, the natural syntax given the above is to put
the confirmation_tag after the signature (so that the signature covers
everything above it).  But on the other hand, that's weird because what do
you do with the confirmation_tag for non-Commit messages?  ("Leave it
empty" would be the obvious answer.). You could leave the confirmation_tag
where it is syntactically, and just change the computations, but that would
break the (admittedly aesthetic) property that the signature covers
everything above it.

Overall, though, I think this is worth writing up a PR on.  I look forward
to your proposal for how to resolve the syntax issue :)

Thanks again,
--Richard

[1]
https://github.com/tlswg/tls13-spec/blob/master/draft-ietf-tls-tls13.md#protocol-overview
[2]
https://github.com/tlswg/tls13-spec/blob/master/draft-ietf-tls-tls13.md#authentication-messages

On Thu, Sep 17, 2020 at 1:43 PM Marta Mularczyk <[email-masked]> wrote:

> - if the adversary doesn't know the current epoch secrets, then he can't
> modify any part of Alice's packet (due to AEAD/MAC security of the message
> framing).
>
> - if he knows the epoch secrets but not Alice's signing key, then the only
> thing he can, in principle, modify is the confirmation_tag. However, the
> tag is fully determined by the signed part of the commit (and the
> transcript history).
>
> An additional advantage of this solution is that it simplifies the
> protocol by removing the interim_transcript_hash.
>
>
>
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Cornelissen Eric <[email-masked]>
Date: Fri, 18 Sep 2020 11:48:24 +0000

Hey,

You say "Now Alice and Bob agree on the confirmed_transcript_hash [...] but not on the interim_transcript_hash" which, to me, seems improbable as the confirmed_transcript_hash is computed based on the interim_transcript_hash (see the interim_transcript_hash/confirmed_transcript_hash chain below).

Hence, if Alice and Bob receive packets with different signatures in epoch e, interim_transcript_hash_[e] will be different (due to MLSPlaintextCommitAuthData_[e]) and so will confirmed_transcript_hash_[e] (due to interim_transcript_hash_[e]).

I'm guessing the confusion comes from the way the definition of the interim and confirmed_transcript_hash are written. The definition may seem to say that you compute a confirmed_transcript_hash for this epoch and interim_transcript_hash for the next epoch upon a commit (in which case your attack works). But, I think(!), it is actually the case that you compute an interim_transcript_hash from the previous epoch's confirmed_transcript_hash and a new confirmed_transcript_hash from that interim_transcript_hash upon a commit.

Hope that helps (and that I understood correctly),

Eric

---

interim_transcript_hash/confirmed_transcript_hash chain:

FIRST COMMIT:

interim_transcript_hash_[0] = 0;

confirmed_transcript_hash_[0] = Hash(interim_transcript_hash_[0] ||MLSPlaintextCommitContent_[0]);

SECOND COMMIT:

interim_transcript_hash_[1] = Hash(confirmed_transcript_hash_[0] ||MLSPlaintextCommitAuthData_[0]);

confirmed_transcript_hash_[1] = Hash(interim_transcript_hash_[1] ||MLSPlaintextCommitContent_[1]);

THIRD COMMIT:

interim_transcript_hash_[2] = Hash(confirmed_transcript_hash_[1] ||MLSPlaintextCommitAuthData_[1]);

confirmed_transcript_hash_[2] = Hash(interim_transcript_hash_[2] ||MLSPlaintextCommitContent_[2]);

etc.

________________________________
From: Marta Mularczyk <[email-masked]>
Sent: Thursday, September 17, 2020 4:52 PM
To: [email-masked]
Subject: [MLS] Include signature in the confirmed transcript hash?

Hi all,

Best,

Marta

---

From: Cornelissen Eric <[email-masked]>
Date: Fri, 18 Sep 2020 17:05:43 +0000

Hi Marta,

1. Now I'm confused as well. It could very well be that I'm misunderstanding the draft. I cannot definitively tell from the current document when the next interim_transcript_hash is computed. But this argument seems to suggest I was wrong.

2. interim_transcript_hash_[0] is the input into the confirmation_transcript_hash_[0] of the first commit, so it is the value before processing the first commit.

interim_transcript_hash_[1] would be included in the second commit.

Regards,
Eric

________________________________
From: Marta Mularczyk <[email-masked]>
Sent: Friday, September 18, 2020 6:23:11 PM
To: Cornelissen Eric; [email-masked]
Subject: RE: [MLS] Include signature in the confirmed transcript hash?

Hi Eric,

I'm a bit confused:
1. The protocol seems to sign the confirmation_tag, so isn’t it circular to include the signature in the key derivation leading to the confirmation_tag?
2. In your diagram, confirmed_transcript_hash_[0] is the value after processing the first commit, right? This doesn't include the signature from the first commit, because that goes into MLSPlaintextCommitAuthData_[0], which is only included after processing the second commit. (That's also why Alice and Bob won't accept the same commits anymore.)

What am I missing?

Best,
Marta

From: Cornelissen Eric [mailto:[email-masked]]
Sent: Friday, September 18, 2020 1:48 PM
To: Marta Mularczyk <[email-masked]>; [email-masked]
Subject: Re: [MLS] Include signature in the confirmed transcript hash?

Hey,

Eric

---

FIRST COMMIT:

SECOND COMMIT:

THIRD COMMIT:

etc.

________________________________
From: Marta Mularczyk <[email-masked]<mailto:[email-masked]>>
Sent: Thursday, September 17, 2020 4:52 PM
To: [email-masked]<mailto:[email-masked]>
Subject: [MLS] Include signature in the confirmed transcript hash?

Hi all,

Best,

Marta

---

From: "Mularczyk Marta" <[email-masked]>
Date: Mon, 21 Sep 2020 12:17:01 +0000

Hi Richard,

Thank you for the comments and for pointing to TLS! It's reassuring that TLS uses a very similar mechanism.

Yes, the order you gave is exactly what I meant. But I'm not sure about including the confirmation tag in the interim_transcript: if the MAC is unique given the key and the message (since for many MACs, including HMAC, verification works by deterministically re-computing the tag, this seems reasonable), then there's no need to include it. And if it's not unique, then we get the same problem as with signatures but with confirmation tags, right?
Another option (discussed at some point in the list) would be to publish the confirmation key instead of the MAC.

Anyway, we'll think what to do with the syntax issue :-)

Best,
Marta

________________________________
From: Richard Barnes <[email-masked]>
Sent: Friday, September 18, 2020 12:21:40 AM
To: Mularczyk Marta
Cc: Messaging Layer Security WG
Subject: Re: [MLS] Include signature in the confirmed transcript hash?

Hi Marta,

Thanks for writing this up.  This analysis seems sound to me. It reminds me of the structure of the server's first flight post-ServerHello in TLS [1]:

That means you end up with (1) message content, (2) signature over message content, (3) MAC that confirms agreement on the derived secrets (4) AEAD authentication tag that verifies membership in the prior group (established by the ClientHello/ServerHello).  Which I think is the same order you're proposing here.  Just to restate to confirm I'm understanding:

MLSPlaintext.signature = Sign(sig_private_key; MLSPlaintext.group_id, ... MLSPlaintext.proposal/commit/application)
confirmed_transcript_hash = Hash(confirmed_transcript_hash, MLSPlaintext.group_id...MLSPlaintext.signature)
MLSPlaintext.confirmation_tag = MAC(confirmation_key, confirmed_transcript_hash)

I don't think this completely gets us out of the need for the interim_transcript_hash.  We will still need it if we want to include the confirmation_tag in the transcript.  This seems like a good idea, analogous to TLS including the Finished message in the transcript for post-handshake messages [2].  (For the same reason, I would argue that the membership_tag would *not* need to go in the transcript.)

There's also a bit of weirdness here arising from the fact that we use the same framing for Commits, Proposals, and application data (MLSPlaintext/MLSCiphertext).  In particular, the signature part is shared.  So on the one hand, the natural syntax given the above is to put the confirmation_tag after the signature (so that the signature covers everything above it).  But on the other hand, that's weird because what do you do with the confirmation_tag for non-Commit messages?  ("Leave it empty" would be the obvious answer.). You could leave the confirmation_tag where it is syntactically, and just change the computations, but that would break the (admittedly aesthetic) property that the signature covers everything above it.

Overall, though, I think this is worth writing up a PR on.  I look forward to your proposal for how to resolve the syntax issue :)

Thanks again,
--Richard

[1] https://github.com/tlswg/tls13-spec/blob/master/draft-ietf-tls-tls13.md#protocol-overview
[2] https://github.com/tlswg/tls13-spec/blob/master/draft-ietf-tls-tls13.md#authentication-messages

On Thu, Sep 17, 2020 at 1:43 PM Marta Mularczyk <[email-masked]<mailto:[email-masked]>> wrote:
Hi all,

Best,
Marta
_______________________________________________
MLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/mls

---

From: Marta Mularczyk <[email-masked]>
Date: Fri, 18 Sep 2020 17:19:32 +0200

Hi Richard,

Best,

Marta

From: Richard Barnes [mailto:[email-masked]] 
Sent: Friday, September 18, 2020 12:22 AM
To: Marta Mularczyk <[email-masked]>
Cc: Messaging Layer Security WG <[email-masked]>
Subject: Re: [MLS] Include signature in the confirmed transcript hash?

 �

Hi Marta,

 �

Thanks for writing this up. � This analysis seems sound to me. It reminds me of the structure of the server's first flight post-ServerHello in TLS [1]:

 �

 � � � AEAD(EncryptedExtensions Certificate CertificateVerify Finished)

 �

That means you end up with (1) message content, (2) signature over message content, (3) MAC that confirms agreement on the derived secrets (4) AEAD authentication tag that verifies membership in the prior group (established by the ClientHello/ServerHello). � Which I think is the same order you're proposing here. � Just to restate to confirm I'm understanding:

 �

 �

I don't think this completely gets us out of the need for the interim_transcript_hash. � We will still need it if we want to include the confirmation_tag in the transcript. � This seems like a good idea, analogous to TLS including the Finished message in the transcript for post-handshake messages [2]. � (For the same reason, I would argue that the membership_tag would *not* need to go in the transcript.)

 �

There's also a bit of weirdness here arising from the fact that we use the same framing for Commits, Proposals, and application data (MLSPlaintext/MLSCiphertext). � In particular, the signature part is shared. � So on the one hand, the natural syntax given the above is to put the confirmation_tag after the signature (so that the signature covers everything above it). � But on the other hand, that's weird because what do you do with the confirmation_tag for non-Commit messages? � ("Leave it empty" would be the obvious answer.). You could leave the confirmation_tag where it is syntactically, and just change the computations, but that would break the (admittedly aesthetic) property that the signature covers everything above it.

 �

Overall, though, I think this is worth writing up a PR on. � I look forward to your proposal for how to resolve the syntax issue :)

 �

Thanks again,

--Richard

 �

 �

 �

 �

On Thu, Sep 17, 2020 at 1:43 PM Marta Mularczyk <[email-masked] <mailto:[email-masked]> > wrote:

Hi all,

 �

 �

 �

 �

 �

 �

 �

Best,

Marta

_______________________________________________
MLS mailing list
[email-masked] <mailto:[email-masked]> 
https://www.ietf.org/mailman/listinfo/mls

---

From: Marta Mularczyk <[email-masked]>
Date: Fri, 18 Sep 2020 17:23:11 +0200

Hi Eric,

 �

I'm a bit confused:

 �

What am I missing? 

 �

Best,

Marta

 �

Hey,

Eric

---

FIRST COMMIT:

SECOND COMMIT:

THIRD COMMIT:

etc.

  _____  

From: Marta Mularczyk <[email-masked] <mailto:[email-masked]> >
Sent: Thursday, September 17, 2020 4:52 PM
To: [email-masked] <mailto:[email-masked]> 
Subject: [MLS] Include signature in the confirmed transcript hash? 

Hi all,

 �

 �

 �

 �

 �

 �

 �

Best,

Marta

---

From: Marta Mularczyk <[email-masked]>
Date: Sat, 19 Sep 2020 21:35:10 +0200

Hi Richard,

Best,

Marta

 �

Hi Marta,

 �

 �

 �

 �

 �

 �

 �

 �

Thanks again,

--Richard

 �

 �

 �

 �

Hi all,

 �

 �

 �

 �

 �

 �

 �

Best,

Marta