[Cfrg] Vulnerability in threshold keygen and fix.

Phillip Hallam-Baker <phill@hallambaker.com> Tue, 28 January 2020 19:55 UTC

Return-Path: <hallam@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 6FE10120089 for <cfrg@ietfa.amsl.com>; Tue, 28 Jan 2020 11:55:05 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.396
X-Spam-Status: No, score=-1.396 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id TrkKRKzb7Ms1 for <cfrg@ietfa.amsl.com>; Tue, 28 Jan 2020 11:55:04 -0800 (PST)
Received: from mail-ot1-f43.google.com (mail-ot1-f43.google.com []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 43A1212007C for <cfrg@irtf.org>; Tue, 28 Jan 2020 11:55:04 -0800 (PST)
Received: by mail-ot1-f43.google.com with SMTP id h9so13215932otj.11 for <cfrg@irtf.org>; Tue, 28 Jan 2020 11:55:04 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=Emv2Y3Q/RI4Ad/8kqFCpO2geY/xauq5zjje3Jid1ZWQ=; b=kUZ1Ju8xYCQl/WX5dC6Jzd0ueGbsqb4EKr/gZdsyrF/lTnDA4ps4vqZ1KF0obwDkDx xTTQEpMCc/iNcFOzZ7YVdJ6qypfs7ovh48530OZsOc43DyGL5Rl33HgmvvKgyYjK9RTD 8/9KHA3GdxikABv0vBPs9/3LdagS4A+D360w7jW96T0rokqj1XeIMFgJ3gD4dYwH7yeb MfgxqPaQsCYTGeKbdxPcIWa8pGqr377LrRVI/DUozyn4hkq0Y7r1Y2nGvmIqOziO0vLL CGMxwr9EH0wEPLI9125zwth+flQy2o8FyOUBNAiEKW6P+ybfcBqFkneI3ocD9JBMX7nl hk/A==
X-Gm-Message-State: APjAAAW/v7RDsUZN5gL/dFR6o/aVA3YMZHgATTuqGM/CnwKpFf8F9QR2 qui5rZk08KWlYVN+ocBYqEOgPZ0DHiN0gxjXAGrqc/lmzmw=
X-Google-Smtp-Source: APXvYqyJA01G1Tcb8HfovgJN9cgv7io43fEKJljTqb1hQCLlbsD7LNxH6gtFkPkB0P0yaSQd1rnx+w4C/tbec5Wk7VY=
X-Received: by 2002:a9d:729c:: with SMTP id t28mr14811171otj.66.1580241303153; Tue, 28 Jan 2020 11:55:03 -0800 (PST)
MIME-Version: 1.0
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Tue, 28 Jan 2020 14:54:55 -0500
Message-ID: <CAMm+Lwjx_4_Oup6VMO2s4f5h1m3hzK5bC1m7TqA2n9GGB3MseA@mail.gmail.com>
To: IRTF CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000088b0bf059d389987"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/frxhqpXtZSIHCJWFoueTAuZi4w0>
Subject: [Cfrg] Vulnerability in threshold keygen and fix.
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 28 Jan 2020 19:55:05 -0000

I have been thinking further about the threshold key gen problem. There is
an important security caveat to add: Each side should only present a given
keypair contribution once and must keep both parts secret. Reuse provides
the attacker with a means of constructing an oracle for the base key which
is a bad thing.

The basic attack works like this:

Alice generates {a. P , a}, presents it to the service.
Service returns a value {s.P , s} via a confidential out of band

The composite key AS = (a+s). P

[NB in the Mesh the service actually returns a seed value x and Alice
generates a private key s = KDF (x, <stuff>)]

Alice presents {a. P , a}, presents to Mallet.
Service returns a value {m. P , m} via a confidential out of band

The composite key AM = (a+m).P

So if Mallet, knowing s is able to provoke Alice to return as.B he can then
recover the value am.P = (a+s).B - s.B + m.B.

This does not appear to affect the use cases I intend this scheme for in
the Mesh which are limited to providing some sort of limited defense
against weak key generation in IoT devices and devices compromised in the
supply chain.