Subject: [MLS] reusing HPKE keys from welcome messages

From: Joel Alwen <[email-masked]>
Date: Fri, 17 Apr 2020 16:47:56 +0900

Hey Everyone,

Sandro Coretti and I have a few suggestions. To keep threads on the list topic
specific I'm putting the suggestions in separate emails so please excuse the
spam. Here goes.

Issue: HPKE Key Reuse
Suppose Alice (commits to a proposal that) invites Bob to a group. For this she
uses a Key Bundle for Bob with an HPKE pub key in it. That pub key has 2
functions (and correct me if I'm wrong here). On the one it becomes the HPKE key
in Bob's leaf in the new ratchet tree. On the other hand, the Welcome message to
Bob is also encrypted to that HPKE key.

Problem: Bob must keep around the corresponding HPKE secret until he updates or
leaves the group. Thing is, that same HPKE sec key lets you reprocess that
welcome message. Ergo, until he does an update we have no FS for all MLS epochs
after his join. (See PS. at end of email for more.)

Proposed Solution: Separate HPKE keys for welcome message and initial leaf key.
E.g. Key Bundles registered on the Key Server have two HPKE keys. One for the
welcome message only and the other used as new leaf's HPKE key. As soon as Bob
processes the welcome message he deletes the HPKE key he used for it.

Thoughts?

- Joël & Sandro

PS. For those familiar, this is basically a special case of the FS issues with
TreeKEM we address with RTreeKEM in eprint/2019/1189. But normally attacks on
the FS of some TreeKEM epoch msg still requires u to somehow know the previous
epochs init_secret. Thats why, normally, FS attacks on TreeKEM "only" translate
to PCFS attacks on MLS. But for the welcome message variant that's different.
The whole point of the welcome message is to bootstrap from that one HPKE secret
key all the way to full-state MLS (including current key schedule). So the
attacker no longer needs an extra init_secret if they leak that one HPKE secret
key. Thus, this goes from the usual PCFS attack for MLS to being a plain FS one.

---

From: Konrad Kohbrok <[email-masked]>
Date: Fri, 17 Apr 2020 10:22:24 +0200

Hi everyone,

nice catch! Although I have to say I'm surprised this is how it's currently
defined in the draft. I just checked back in draft-8 (which is what we're
currently analyzing) and back then it was like your proposed Option 2 (if I
understand it correctly).

I think deriving a key/secret from an HPKE private key is a very bad idea in
terms of key separation. I must have missed this change and the corresponding
discussion back when it got into the draft.

What was the reason for the change from how it worked in draft-8 in the first
place? If it doesn't break anything, I would very much like to adopt one of the
options proposed by Joël & Sandro. If it does break something, we should still
reconsider the current design.

Cheers,
Konrad

On 17.04.20 09:47, Joel Alwen wrote:
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Konrad Kohbrok <[email-masked]>
Date: Fri, 17 Apr 2020 10:23:39 +0200

Ah, replied to the wrong mail. This was meant to be a reply to "somewhat better
PCFS for cheap". Sorry about that!

Konrad

---

From: Richard Barnes <[email-masked]>
Date: Fri, 17 Apr 2020 10:40:26 -0400

This seems like a reasonable trade-off in terms of performance.  There are
some mechanical issues to address because we use the same KeyPackage struct
for initialization and for leaves in the tree.  In particular, if we have
both "WelcomeKey" and "LeafKey" in the package, we probably don't want the
leaves to keep making new WelcomeKeys forever.

I think that's adequately addressed, though, by just putting the WelcomeKey
in an extension, and requiring that extension to be present in KeyPackages
used for initialization.

Alternatively, it seems like this issue could be papered over operationally
if a member updates on joining.  That would push the expense to join time
instead of KP generation time.  I don't think this is a great trade-off,
though, just wanted to document it.

--Richard