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

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 7 Jul 2021 12:03:41 -0400

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 (ycombinator.com)
<https://news.ycombinator.com/item?id=27728287>

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?

---

From: Chelsea Komlo <[email-masked]>
Date: Wed, 7 Jul 2021 23:40:54 +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,

Chelsea

________________________________
From: CFRG <[email-masked]> on behalf of Phillip Hallam-Baker <[email-masked]>
Sent: Wednesday, July 7, 2021 4:03:41 AM
To: IRTF CFRG
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 (ycombinator.com)<https://news.ycombinator.com/item?id=27728287>

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.

---

From: Tim Dierks <[email-masked]>
Date: Wed, 7 Jul 2021 22:36:21 -0400

I haven't looked at the code in question for the Merkle tree in the
certificate transparency logs, but we have solved similar problems [1]
through the simpler mechanism of just validating one's answers before one
releases them. If, in this case, the log construction system had signed the
tree, then validated the correctness of the signature before releasing the
signature, it could have just done it again when it discovered that the
tree correctness could no longer be validated.

If I understand correctly [2] the hash of a leaf node in the Merkle tree
had one bit flipped before the hash was incorporated into the parent node.
The best way to avoid this failure depends on the structure of the
distributed systems, but double-checking that the data in memory hasn't
changed (through keeping a simple CRC32 or similar), and validating that
cryptographic outputs are reproducible should be sufficient; e.g.:

 * when producing leaf nodes:
  1. first hash the source data with SHA-256
  2. then validate it for inclusion in the tree
  3. then make a crc32 hash of the SHA-256 hash
  4. then rehash the source data with SHA-256
  5. validate that the hashes in step 1 and 4 are the same
  6. retain in memory the hash from step 1 or 4 along with the crc from
step 3
 * when incorporating leaf nodes into tree nodes:
  7. calculate the SHA-256 over the child nodes
  8. go through each of the child nodes and validate that you can reproduce
the crc for their hashes
  9. calculate the crc32 for the hash from step 7
  10. rehash the child nodes
  11. validate that the hashes from step 7 and 10 are the same
  12. retain the hash from step 7 or 10 along with the crc from step 9
 * when doing a signature over a tree
  13. create a signature over the tree hash
  14. take a crc32 of the signature
  15. validate that the crc32 on the tree hash can be computed from the
tree hash used as input to step 13
  16. validate that the signature from step 13 can be validated as signing
the tree hash
Then send the pair of (signature, crc32) to the requesting system. (Sending
the crc32 can be avoided if the requesting system can validate the
correctness of the signature in other ways.)

I think by so having a validator which covers every step and which can be
checked, you can avoid ever having exposure to a bit error be undetectable.
The cost of the crc32s and duplication of all cryptographic operations is a
small price to pay, and much cheaper and simpler than fully-redundant
notaries.

If you need protection of storage or across networks, it can be done by
storing or sending crc32s along with data. While disks and networks have
correctness checks of their own (or error recovery), and with TLS, network
integrity is cryptographic, there's no protection for data as it moves
through API stacks before it gets protected; for this reason, managing the
redundancy checks as a part of the full data lifecycle is necessary to
provide full protection against memory errors or processor flaws.

Note: for processor flaws we were concerned about reproducible error (in
this case, hypothetically that calculating the SHA-256 would produce the
wrong value repeatedly), so for cryptographic operations we have considered
using two independent implementations with independent intermediate data
structures (such as key schedules) to mitigate this risk.

 - Tim

[1]
https://sigops.org/s/conferences/hotos/2021/papers/hotos21-s01-hochschild.pdf
[2]
https://groups.google.com/a/chromium.org/g/ct-policy/c/PCkKU357M2Q/m/xbxgEXWbAQAJ

On Wed, Jul 7, 2021 at 12:04 PM Phillip Hallam-Baker <[email-masked]>
wrote:

> 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
> 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
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 8 Jul 2021 00:54:09 -0400

If you have a single CPU, you will always have the possibility of an error.
Not all faults are transient. If the data was corrupted in the cache, it is
going to be corrupted both times it is hashed. And optimizing compilers can
screw you in really imaginative ways.

I have had RAID 6 arrays die in production. These things really do happen.
If the controller card goes, all your copies end up corrupted.

Three copies, two different media, one offsite.

Threshold sigs might not be the only way to do it but it is an elegant way
to get to six nines.

On Wed, Jul 7, 2021 at 10:36 PM Tim Dierks <[email-masked]> wrote:

>   8. go through each of the child nodes and validate that you can
> reproduce the crc for their hashes
> Then send the pair of (signature, crc32) to the requesting system.
> (Sending the crc32 can be avoided if the requesting system can validate the
> On Wed, Jul 7, 2021 at 12:04 PM Phillip Hallam-Baker <
> [email-masked]> wrote:
>
>> 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:
>>

---

From: Ben Laurie <[email-masked]>
Date: Thu, 8 Jul 2021 11:37:18 +0100

> The only robust solution to this issue is for redundant notaries to sign

That's not true - the solution CT uses already is to have multiple
redundant logs.

> separate chipset architectures (Intel, AMD, ARM?) if we want to get to

This seems no more robust to me than the existing scheme - in fact it is
probably less robust because it is more complex.

Also, I'm not sure why a quorum helps - logs are verifiably correct (or
not), so what's the quorum for? That requirement also reduces robustness.

---

From: Jeff Burdges <[email-masked]>
Date: Thu, 8 Jul 2021 14:06:23 +0200

> On 8 Jul 2021, at 12:37, Ben Laurie <benl=[email-masked]> wrote:
> That's not true - the solution CT uses already is to have multiple redundant logs.

Yes.  Threshold signatures are not attributable, which makes them kinda useless for CT.  Also the logs have different Merkle roots, so they cannot really be unified cleanly anyways.

Threshold signatures only work for cryptocurrency because the clients accept the attribution problems.  

I’d assume threshold signatures “real” application would be TLS certificates and perhaps app signing in app stores.  It’s obviously better if these were attributable too, but this could be handled internally by the CA or whatever, assuming the standard discusses validating signature shares. 

Jeff

---

From: Tim Dierks <[email-masked]>
Date: Thu, 8 Jul 2021 11:21:10 -0400

On Thu, Jul 8, 2021 at 12:54 AM Phillip Hallam-Baker <[email-masked]>
wrote:

> If you have a single CPU, you will always have the possibility of an
> error. Not all faults are transient. If the data was corrupted in
> the cache, it is going to be corrupted both times it is hashed. And
> optimizing compilers can screw you in really imaginative ways.
>

We will always have errors, that's the reason we have to take care. But I
believe that errors like this can be detected and prevented from being
committed/released using relatively straightforward redundant checks as
illustrated. If you can identify in the flow described where a bit error
could occur without detection, I'd be interested to know; we're protecting
a lot of data using similar designs. The failure of a reproducible log is
one thing; I'm very interested in avoiding errors when wrapping keys that
might lead to large quantities of data being unrecoverable if not detected
prior to commit.

 - Tim

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 8 Jul 2021 11:58:46 -0400

> That's not true - the solution CT uses already is to have multiple

It depends on the use that you want to make of them and who is observing.
In the case of CT, this error was caught because people are continually
monitoring the logs and independently verifying integrity. Which is fine
for the specific application for CT.

The use case I am considering is how to use a chained notary approach to
notarize digital evidence.

I understand the point about attribution. As a general matter, I reject the
notion of threshold signatures where the keys are held by independent
parties as the crypto currency folk are trying to do. If Alice and Bob and
Carol are going to sign a document, the only correct tool to use is a
multi-signature, that is sign under A, B and C. Sure, we can develop a
pretty algorithm that does this, but when we embed it in a protocol...
crypto-currencies are fragile enough when exposed to the real world as it
is...

The only use case I am interested in is when Alice is the signer and she
has redundant devices, all of which is trusted but one or more of which
might be faulty and/or compromised. In this case, I don't want to expose
the structure of how the signature came to be. So attribution doesn't
arise, if a fault occurs, Alice will be the only person who sees it.

Oh and yes, I get that it is a bit more complex and not the only way to do
this. But it is the most elegant way to do it and for some circumstances,
the additional cost is a feature, not a bug.

If I am visiting a national lab to discuss deployment of an apex notary for
the court system, they are going to be wanting to see bright shiny HSMs and
Tier 6 security etc. etc. they are going to want to perform management as
ceremonies because that is the way crypto has always been done at that
level. It is not how people administer individual machines but that is how
core crypto is managed.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 8 Jul 2021 12:36:59 -0400

On Thu, Jul 8, 2021 at 11:21 AM Tim Dierks <[email-masked]> wrote:

> On Thu, Jul 8, 2021 at 12:54 AM Phillip Hallam-Baker <

The potential for loss of static data is something that has been of
great concern to me throughout. Data at Rest is a much harder problem than
data in transit precisely because of the fact that loss of data is usually
more serious than disclosure.

Ransomware works because nobody can take new pictures of the kids.

When encrypting data to a threshold group that the encryptor is a member
of, I perform a trial decryption using the threshold shares. But that does
not work for cases where the encryptor is not permitted to decrypt.