Re: [CFRG] Threshold Sig required - Random bit flip hits Cert Transparency Log

Chelsea Komlo <> Wed, 07 July 2021 23:41 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id C57413A1748 for <>; Wed, 7 Jul 2021 16:41:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id kIqR-FLElXEb for <>; Wed, 7 Jul 2021 16:40:57 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 0B5063A1754 for <>; Wed, 7 Jul 2021 16:40:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;;; q=dns/txt; s=default; t=1625701257; x=1657237257; h=from:to:subject:date:message-id:references:in-reply-to: mime-version; bh=wm+bN/OFnqnRGnPVqJlurYckPWx0xyCtSZLgpnwd8nk=; b=rvINYVrovvJQvt+ssMMIXSEBXihoBeQLXPNObldNX4fi8H0qP3H4kaBi SBowPquaOTKz2UVGTlHBBxBmXZ/FsFcUGcWyaGUkdw7AHDmaEm28tQJou t+svNfec7gY/bWDFpXOHtqmuEWt3bxGSmb/ehairQHqoHjCHqiclXWIBC 8=;
Received: from (HELO ([]) by with ESMTP/TLS/AES256-GCM-SHA384; 07 Jul 2021 19:40:54 -0400
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.2176.2; Wed, 7 Jul 2021 19:40:54 -0400
Received: from ([]) by ([]) with mapi id 15.01.2176.012; Wed, 7 Jul 2021 19:40:54 -0400
From: Chelsea Komlo <>
To: Phillip Hallam-Baker <>, IRTF CFRG <>
Thread-Topic: [CFRG] Threshold Sig required - Random bit flip hits Cert Transparency Log
Thread-Index: AQHXc0m352iygELPiU6yckK6yGD90as4K25d
Date: Wed, 07 Jul 2021 23:40:54 +0000
Message-ID: <>
References: <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
x-originating-ip: []
Content-Type: multipart/alternative; boundary="_000_0e6508a9132d499a9189bf016430c46cuwaterlooca_"
MIME-Version: 1.0
Archived-At: <>
Subject: Re: [CFRG] Threshold Sig required - Random bit flip hits Cert Transparency Log
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 07 Jul 2021 23:41:03 -0000

Hi Phillip,

Thanks for the mail. We are working on the next version of the FROST draft and are aiming to have this draft ready to review for the 112 meeting in November.

All the best,


From: CFRG <> on behalf of Phillip Hallam-Baker <>
Sent: Wednesday, July 7, 2021 4:03:41 AM
Subject: [CFRG] Threshold Sig required - Random bit flip hits Cert Transparency Log

So it has actually happened, a one in a billion computing error has caused a cert transparency log to become corrupted due to a bit flip error. There is a discussion of the issue here:

Single random bit flip causes error in certificate transparency log | Hacker News (<>

The solution they obsess over (ECC RAM) is actually irrelevant to the error in that case as it was an even rarer CPU error. Which means that what I considered to be a more or less theoretical concern about signing append only logs turns out to have actually occurred. Do things billions of times and billion to one chances will happen.

The only robust solution to this issue is for redundant notaries to sign the log.

Consider the case where we have an append only log that is authenticated by means of a Merkle tree with the apex of the tree being signed at 10 minute intervals. If we have a single server doing the signing, any error that occurs will lead to the log becoming invalid. This condition cannot be distinguished from a notary default.

But consider the case where there are three notaries each signing the log, which private key should they use?

All three signers use the same key means that if an error occurs, we risk having a correct and incorrect version of the same log being signed. That means there is a real risk of the incorrect log and signature leaking somehow.

All three signers using different keys is also bad because now we have three independent notaries and the relying party has to do the job of deciding which one to trust. There is an even greater risk of the wrong log being relied on at some point.

A threshold scheme with three shares and a quorum of 2 solves the problem very neatly. The possibility of an undetected error is now much smaller as two signers must be hit with an error having exactly the same effect at the same time. That is a very remote possibility unless the error is somehow caused by an architectural defect in the CPU. So we should probably choose separate chipset architectures (Intel, AMD, ARM?) if we want to get to maximum robustness.

So how is the FROST draft coming?