Re: [MLS] hardening MLS against bad randomness

"Hale, Britta (CIV)" <> Wed, 22 April 2020 16:28 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 431E83A0FAC for <>; Wed, 22 Apr 2020 09:28:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id QNfiIuMCpzhC for <>; Wed, 22 Apr 2020 09:28:53 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id 12B123A0FAB for <>; Wed, 22 Apr 2020 09:28:52 -0700 (PDT)
X-ASG-Debug-ID: 1587572932-0e394549633cf900001-bGA3T6
Received: from ( []) by with ESMTP id eksyigfKP8S4yfVH; Wed, 22 Apr 2020 09:28:52 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.1.1531.3; Wed, 22 Apr 2020 09:28:52 -0700
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.1.1531.3 via Frontend Transport; Wed, 22 Apr 2020 09:28:51 -0700
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901;; cv=none; b=Sre2QA9fUs/Rk7qrQH6D5WTzuusy5dipzXZlrRzpXyO4sJOpEhEE19TJ/qa8w1RHU52A6k8xmth8CuDiihiRyt1Q3lSGMIoRKozVL2GU9JN+GAhtiP5npKv8Xc9DHJ4M0Hyu8sqVH9tb8yOumdgeK9fGBv5wcv4j1SYDso4TBV8RR1kRGQ9F0IXR3fOWmkm/UNApVKmwif5Av/hShTEJGYrp3yJNCxGtlTWi1gdQ4LqfG3AxWL0g4LFBhxfyavL8OxNgq90ldoWSiw/B3d38VfUDilBOTfy34wEyqjsqxuyAnnnj4A/4TAFcmCoXhTrAb53jJenM4UFidWHcZNulYg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed;; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=k6GRzx1RORDNB3NQMLGwwvUTn8f9EeFKKSQdaQY36JE=; b=RgnlB0TfDrpGusZ4I1cLlx66fjKX9izqyV8wCvcCzqDS5K/yCHN6oSBWJjenbwUNmIuRRcNEA99GYQ1bKWhiDuKOnxAScG3fMFwOaaPrt5oRQuGbRD0CP9ZYTwgf6It5/svEUgBAdgmd5g/c/cZWQWSMv/iw2v7e6avEgNUQKR081cg3ZD70JU2GuxK9SoCt63OhgrXjANd7Wemb6LA08ZffA1gsTSDr9vF5LTe33tSBwVY8KpJSZL0QYGNLoG4oq54gdSmsIQO1/eEZX+vd1Xg8aMbb/5jSnsGyFQHG1IcChuK/Vvd/RT//2oiLJdjUYJ5AucU17gLlcYE3Cub0Uw==
ARC-Authentication-Results: i=1; 1; spf=pass; dmarc=pass action=none; dkim=pass; arc=none
Received: from (2603:10b6:a03:185::31) by (2603:10b6:a03:1a8::27) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2937.11; Wed, 22 Apr 2020 16:28:50 +0000
Received: from ([fe80::b93a:9f12:aa45:6194]) by ([fe80::b93a:9f12:aa45:6194%7]) with mapi id 15.20.2937.012; Wed, 22 Apr 2020 16:28:50 +0000
X-Barracuda-Effective-Source-IP: UNKNOWN[2603:10b6:a03:1a8::27]
X-Barracuda-Apparent-Source-IP: 2603:10b6:a03:1a8::27
From: "Hale, Britta (CIV)" <>
To: Joel Alwen <>, "" <>
Thread-Topic: [MLS] hardening MLS against bad randomness
X-ASG-Orig-Subj: Re: [MLS] hardening MLS against bad randomness
Thread-Index: AQHWFLWofXOAPH5gNE6s9ckk8yY+RaiFGKOAgAAGagD//68jgIAAflQA//+a6YA=
Date: Wed, 22 Apr 2020 16:28:50 +0000
Message-ID: <>
References: <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
authentication-results: spf=none (sender IP is );
x-originating-ip: []
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 96b62ac2-1dd8-401f-db89-08d7e6da3d8c
x-ms-traffictypediagnostic: BY5PR13MB3507:
x-microsoft-antispam-prvs: <>
x-ms-oob-tlc-oobclassifiers: OLM:8273;
x-forefront-prvs: 03818C953D
x-forefront-antispam-report: CIP:; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM;; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(396003)(346002)(136003)(366004)(376002)(39850400004)(75432002)(66556008)(66446008)(110136005)(66476007)(316002)(5660300002)(786003)(8936002)(36756003)(6512007)(76116006)(66946007)(86362001)(64756008)(8676002)(26005)(6486002)(81156014)(2616005)(478600001)(71200400001)(186003)(33656002)(6506007)(2906002); DIR:OUT; SFP:1101;
received-spf: None ( does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: NRFyWbcdnIx/a5Cx3CaVGY4jI2Y8FuSfPENKHIU7NOrpDBxibqUYhzrgQ23fhht/V599/5Ern75GRcPNceJNEyJ3wLKLNMRj51M2e/rYr/zltlVX/GxtopuWOjNj4VY8XwXajQtDylkI3y+KFUfGJgJpV0EUQgZAKsQQT3ukIF2umz22rkRUipocX4/FaRSnjp6JiqUxy9goLs1U8HSL6MB58FZXipZDrQg/k1WPAPzI5U+StrynL3Q0Fg+1RCNaSPPWZcj2834222xNCyyTkvWG1N80tINUeKNWsHisLKIhGib3ylepvY3Hbp16hvnhf6Yxk/kmAvbBzsA1/5GLRddo7CZm5hm6lDO+jDsTTqNsP7NHyg5564NzVydfVNkBMz9QYAUEvDTFw5CjRDopJbVbPjn6v0h9kQLFXNjylRAORM8pugi6RWs05D0A9ak+
x-ms-exchange-antispam-messagedata: FM6coRr3AQNIvFM8LRcn+rMo8ubxNzgL9O4GE+CgreX7RQhyqFEk2WVZcdlulQ+8G61OKCz89VEui1K9CcZKLZqJ7cOuFuoAdnpQKXLGtUtd5cYrUJxFp9d2QsbUWb7XWcsqDdmG+xco7ra3+eEQiA==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="utf-8"
Content-ID: <>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 96b62ac2-1dd8-401f-db89-08d7e6da3d8c
X-MS-Exchange-CrossTenant-originalarrivaltime: 22 Apr 2020 16:28:50.4146 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 6d936231-a517-40ea-9199-f7578963378e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: oiiOLzg+hdrFUzB3hGQhEDsBTSmdVflYmBhsQUKl8aZ5su5yYVa86Mgf4UJZFmzLxoAwCli4zL6oryb40nPYwg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY5PR13MB3507
X-Barracuda-Start-Time: 1587572932
X-Virus-Scanned: by bsmtpd at
X-Barracuda-Scan-Msg-Size: 1971
X-Barracuda-BRTS-Status: 1
X-Barracuda-Spam-Score: 0.00
X-Barracuda-Spam-Status: No, SCORE=0.00 using global scores of TAG_LEVEL=1000.0 QUARANTINE_LEVEL=1000.0 KILL_LEVEL=9.0 tests=
X-Barracuda-Spam-Report: Code version 3.2, rules version Rule breakdown below pts rule name description ---- ---------------------- --------------------------------------------------
Archived-At: <>
Subject: Re: [MLS] hardening MLS against bad randomness
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 22 Apr 2020 16:28:55 -0000

´╗┐On 4/22/20, 8:30 AM, "Joel Alwen" <> wrote:

    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?

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. 

    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.)

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