Subject: [MLS] hardening MLS against bad randomness

From: Joel Alwen <[email-masked]>
Date: Fri, 17 Apr 2020 21:42:11 +0900

hey everyone,

Sandro Coretti and I have the following suggestions around MLS's defenses
against bad randomness.

The Issue: Currently the (CGKA) protocol TreeKEM relies heavily on people
continuously having good randomness available.

The problem: Good randomness may not always be available though in which case
things can go pretty wrong. E.g. Say, Alice does a Commit with too little
entropy (from the adversaries perspective). This results in all new keys on her
Direct Path (and the update_secret) having too little entropy because they are
all derived deterministically *purely* from the entropy she samples in that
procedure.

To be clear, by "bad randomness" we're not just talking about low entropy
because of an on-device attacks by an adversary. We also mean things like very
deterministic boot process/environments. (E.g. on some VMs, embedded device or
even sometimes mobiles.) There's also buggy RNGs. (Things like the Infineon
keygen bug in the Estonian ID cards. Also the stuff in "Mining you Ps and Qs".)
The point is, low entropy can be a practical concern even when an adversary can
*not* access the rest of your local state.

The fix: We thought of 2 types of fixes to reduce the dependence on continuous
fresh entropy.

General Fix
-----------
Basic Idea: MLS explicitly mandates a local entropy pool.

Whenever MLS needs random bytes (i.e. when doing KeyBundle gen, or a Commit)
call the OS/crypto-lib to get some (supposed) random bytes B from outside. HKDF
bytes B with your local entropy pool. First part of output overwrites your
entropy pool. Second part are the bytes you actually pass on to the calling MLS
function.

This gives you 2 nice properties. First, you are accumulating any entropy B
*may* have into your pool. So even with consistently low (but not 0) external
entropy your pool fills up and eventually your good for ever more (till your
state leaks of course). That's true even if your external calls start going back
to 0 entropy (e.g. say you update to a buggy external RNG implementation or your
in a VM and the OS is getting (poorly) initialized from some fixed snapshot but
your apps local state is persistent). Second, if your pool leaks, then as soon
as your OS/lib gives you enough good entropy again you back to having a good
pool to. So you have PCS for leaked randomness. As long as either pool or
external entropy are good the resulting being passed to MLS have enough entropy.

Pro: general catch-all solution. efficient, easy to analyze.
Con: requires implementors to handle cryptographically valuable randomness &
probably, to hook calls from their crypto-libs; a new and maybe touchy practical
requirement for implementors compared to what MLS currently asks of them.

MLS Specific Fix
----------------
To avoid the above cons (and maybe others we didnt think of) here's an alternate
solution approach using only already defined functions from the MLS spec. We
demonstrate it on the case of a Commit as this is probably the most egregious
case. (If Alice uses bad randomness it doesnt just "pollute" her own leaf like
when she does an update proposal. It pollutes a whole chunk of the ratchet tree.)

Basic idea: Whenever sampling/deriving a new secret key, make it also depend on
the old secret key and on the application key schedule. That way, if either the
old secret or application key schedule was secure, then so will the new one be
*even when using bad randomness*. Mixing in the application key schedule is
valuable if there was no old secret e.g. when we're assigning a new key pair to
a previously blank node.

For concreteness here's how that can work for the Commit operations (C.f.
Section 5.4 in MLS protocol version 9)

commit_secret = HKDF-Expand(epoch_secret, "mls 1.0 welcome", Hash.length)

---------- snip -----------
path_secret[0] = HKDF(leaf_hpke_secret||commit_secret, "path",
							"", Hash.Length)

If node n on direct path is blank
  sk[n] := ciphersuite key length number of 0 bytes.
Else
  sk[n] := old_node_priv[n]
	
path_secret[n] = HKDF(path_secret[n-1]||sk[n], "path", "", Hash.Length)

new_node_priv[n], new_node_pub[n] = Derive-Key-Pair(path_secret[n])
---------- snip -----------

Pros: only uses existing MLS functions. other parties implicitly verify that the
fix is being used by re-deriving same key material as commiter. no need to hook
RNG calls.

Con: less general so full fix requires changing other parts of MLS where
security critical randomness is used. In particular, key bundle generation (or
at least updating in an existing session).

- Joël & Sandro

---

From: "Christopher Wood" <[email-masked]>
Date: Tue, 21 Apr 2020 12:37:09 -0700

For what it's worth, I lean towards the general fix. This doesn't seem to be a protocol issue, so mitigating it with a protocol-specific fix doesn't seem ideal. 

Best,
Chris

On Fri, Apr 17, 2020, at 5:42 AM, Joel Alwen wrote:
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 21 Apr 2020 15:46:37 -0400

Hi Joël,

Thanks for thinking about this, and for the reminder on the call.

I'm inclined to say that this is not a matter for the MLS spec.  It's not a
protocol / interoperability issue, it's a consideration for how you build
your client.

So I definitely would rather go for the general fix.  If some better
platform guidance is needed, run it through CFRG.  Maybe describe the
implications of bad randomness in the Security Considerations to the
protocol.

--Richard

---

From: Joel Alwen <[email-masked]>
Date: Wed, 22 Apr 2020 21:15:08 +0900

Hey Richard,

> I'm inclined to say that this is not a matter for the MLS spec.

> So I definitely would rather go for the general fix.

I'm not sure I understood you. Could you clarify? Are you leaning towards
putting the general fix in the protocol RFC or rather leave it out? Or something
else?

As for not being in spec. My take is a bit different. In principle at least, I
like the idea of designing crypto/security tools to withstand bad randomness
when possible (at a reasonable cost). Two examples of modern designs which I
believe take a similar view are EdDSA (i.e. Ed25519 & Ed448) and AES-GCM-SIV
(and other nonce reuse/misuse resistant AEADs). They all include mechanisms to
reduce the impact of bad randomness. I think similar defenses could be in scope
for MLS too.

Could you elaborate why you lean towards this not being a matter for the MLS spec?

In the mean time, continuing with the EdDSA / AES-GCM-SIV analogies, the general
fix is philosophically closer to the EdDSA's approach. Functionality doesn't
depend on actually implementing the defense. (The verifier of an EdDSA signature
would still accept signatures if R where chosen differently than specified in
the spec. Similarly, a Commit msg receiver in MLS wouldn't know if the sender is
using an entropy pool.) None-the-less the EdDSA designers felt it a good idea to
design their scheme with such a defense in place.

The second solution for MLS -- "hashing in old keys" -- is more inline with
AES-GCM-SIV in that if you don't implement it as specified then you loose
functionality. Receivers wont decrypt / process your output correctly.

- Joël

On 22/04/2020 04:46, Richard Barnes wrote:
> protocol / interoperability issue, it's a consideration for how you build your
> client.
> 
> So I definitely would rather go for the general fix.  If some better platform
> guidance is needed, run it through CFRG.  Maybe describe the implications of bad
> randomness in the Security Considerations to the protocol.
> 
> --Richard
> 
> 
> 
> 
> On Fri, Apr 17, 2020 at 8:42 AM Joel Alwen <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>     hey everyone,
> 
>     [email-masked] <mailto:[email-masked]>

---

From: Konrad Kohbrok <[email-masked]>
Date: Wed, 22 Apr 2020 14:24:55 +0200

> functionality. Receivers wont decrypt / process your output correctly.

One way to keep it transparent for the receiver (if that is indeed what we want)
would be for the updating party to include the previous epoch's path_secret[0]
when creating a fresh path_secret[0] and then KDF'ing up the tree as before. In
other words, follow your MLS specific suggestion, but only for the leaf secrets.
Since that is (I think?) the only place new randomness comes into the tree
anyway, it would have about the same effect, wouldn't it? Also, it would be a
minor change to the protocol and the receiver wouldn't even notice if the sender
did it (for better or worse).

Cheers,
Konrad

---

From: Joel Alwen <[email-masked]>
Date: Wed, 22 Apr 2020 21:47:52 +0900

Hey Konrad!

> did it (for better or worse).

I like that this is less invasive in terms of changes. (Though IMO its actually
a Pro not a Con that functionality breaks when you don't implement any given
defense correctly, including those against bad randomness.)

One nit: better to derive something off of the old path_secret[0] and use that
rather than use path_secret[0] directly. Don't want to keep path_secret[0]
around after a commit (bad for FS of TreeKEM / PCFS of MLS).

I do think that using only path_secret[0] defends a bit less though. E.g. say
Alice & Bob are siblings (and everything is delivered & process immediately).
Here's an execution.

1) Alice commits.
2) Leak Alice's state to adversary.
3) Bob commits.
4) Alice commits with bad randomness.

Mixing in only something from path_secret[0] means all keys in commit (4) are
now bad. But mixing in something from old path_secret[n] for new pub/priv key n
means all but her leaf are now good keys.

- Joël

---

From: "Hale, Britta (CIV)" <[email-masked]>
Date: Wed, 22 Apr 2020 14:58:31 +0000

I am trying to understand the threat model we are working with on this. When trying to protect against bad randomness, the goal would seem to be to protect a receiver against potentially bad randomness from the sender. However, if receiver would not notice if the sender took the correct steps, then they do not have any guarantee - in fact, a sender could just incorrectly implement this without breaking functionality and no one would be the wiser that the bad-randomness protection has been lost (if I understand the proposal correctly).

So is the goal to protect the sender from their own bad randomness, or to protect an unaware receiver, in the event that the sender actually behaves correctly? There can still be a gain from such a change, but it seems to be a far weaker guarantee if there is no awareness at the receiver. 

We also need to be careful in the differentiation of leaking state to the adversary, which may well reveal the entire current state, and a bad random generator.

-- Britta

On 4/22/20, 5:48 AM, "MLS on behalf of Joel Alwen" <[email-masked] on behalf of [email-masked]> wrote:

    Hey Konrad!

    

    1) Alice commits.

    - Joël

---

From: Joel Alwen <[email-masked]>
Date: Thu, 23 Apr 2020 00:30:36 +0900

Roughly speaking, I'd say the goal is to protect honest group members from
members unintentionally using bad randomness (i.e. randomness with low entropy
for the adversary) but who otherwise follow the protocol. This includes the
sender using bad randomness and the receivers. Of course, there are limits to
what can be achieved but that's the ideal. In practical terms, this can well be
caused by poor configurations, overly deterministic boot processes or straight
up buggy logic rather than actual explicit attacks by an adversary.

So put differently, the idea is to reduce what an attacker with information (or
influence over) randomness can achieve in terms of breaking privacy,
authenticity and whatever other security goals we have for MLS.

>  However, if receiver would not notice if the sender took the correct steps,
then they do not have any guarantee

Yup, some solutions have that property (e.g. the "entropy pool" approach and
Konrad's proposal). Others are more tightly connected to correctness like the
"mixing in old keys" approach. (Personally I favor the latter. I like things
noticeably breaking when security precautions aren't being taken.)

> So is the goal to protect the sender from their own bad randomness, or to
protect an unaware receiver, in the event that the sender actually behaves
correctly? There can still be a gain from such a change, but it seems to be a
far weaker guarantee if there is no awareness at the receiver.

What do you mean by far weaker? From what I can tell whats lost when receivers
can (in fact, are forced to) verify that defenses are being applied is that it
becomes harder to implement the protocol poorly. Is that what you mean? Or is
there more?

> We also need to be careful in the differentiation of leaking state to the
adversary, which may well reveal the entire current state, and a bad random
generator.

I agree. Both are interesting and different attacks / failure modes. (In Sandro,
Yiannis and my work on security analysis of MLS we're treating these as two
different types of corruption modes available to the adversary.)

- Joël

---

From: "Hale, Britta (CIV)" <[email-masked]>
Date: Wed, 22 Apr 2020 16:28:50 +0000

On 4/22/20, 8:30 AM, "Joel Alwen" <[email-masked]> wrote:

Basically, by losing detection guarantees on the receiver, we also lose all assurance of protection from bad randomness. That is not the same as losing protection - which we still have if all parties are acting in good faith - but we do lose assurance of it. 

Konrad's solution still has benefits for a sender (if the protocol is an honest implementation and the randomness generation is bad), and for a receiver (if the sender has an honest implementation). However, since the receiver only gets guarantees based on an unverifiable assumption, the benefit is far weaker. Personally, I favor the verifiable approach (receiver can detect).   

However, if the computational cost is low (which it seems to be), then it is still worthwhile to make that change if not going for the full assurance approach. There is certainly other work based on the assumption of a "mostly honest" sender, where an adversary can control partial inputs. 

OK, then I misunderstood your meaning. Your (1-2-3-4) example had explicitly described a Reveal query-type setting with leakage of the whole state, vice bad randomness generation. 

Final comment: 
    But mixing in something from old path_secret[n] for new pub/priv key n means all but her leaf are now good keys.

I want to note that this solution has the added benefit of a maintaining a form of transcript history per key.

-- Britta