diff options
| -rw-r--r-- | README.md | 6 | ||||
| -rw-r--r-- | doc/design.md | 256 |
2 files changed, 144 insertions, 118 deletions
@@ -1,7 +1,7 @@ # The Sigsum Project -Sigsum is a free and open-source project that brings transparency logging to -**sig**ned check**sum**s. The overall design is kept general by not logging -a more concrete data structure like TLS certificates or Go modules. +Sigsum is a free and open source software project that brings transparency +logging to **sig**ned check**sum**s. The overall design is kept general +by not logging a more concrete data structure like TLS certificates. - [x] Discoverability of signed checksums for the data of your choice - [x] Centralised log operations but distributed trust assumptions diff --git a/doc/design.md b/doc/design.md index 535685b..4f7c06a 100644 --- a/doc/design.md +++ b/doc/design.md @@ -33,11 +33,11 @@ sigsum logging as pre-hashed digital signing with transparency. The signing party is called a _signer_. The user of the signed data is called a _verifier_. -The problem with _just digital signing_ is that it is difficult to determine -whether the signed data is _actually the data that should have been signed_. -How would we detect if a secret signing key got compromised? -How would we detect if something was signed by mistake, or even worse, -if the signing party was forced to sign malicious data against their will? +The problem with _digital signing on its own_ is that it is difficult to +determine whether the signed data is _actually the data that should have been +signed_. How would we detect if a secret signing key got compromised? How +would we detect if something was signed by mistake, or even worse, if the +signing party was forced to sign malicious data against their will? Sigsum logs make it possible to answers these types of questions. The basic idea is to make a signer's _key-usage_ transparent. This is a powerful building @@ -46,7 +46,7 @@ block that can be used to facilitate verification of falsifiable claims. Examples include: - Everyone gets the same executable binaries [\[BT\]](https://wiki.mozilla.org/Security/Binary_Transparency) -- A domain does not serve malicious javascript +- A web server does not serve malicious javascript [\[SRI\]](https://developer.mozilla.org/en-US/docs/Web/Security/Subresource_Integrity) - A list of key-value pairs is maintained with a certain policy. @@ -107,10 +107,6 @@ that a verifier is required to support. Signers, monitors, and witnesses additionally need to interact with a sigsum log's line-terminated ASCII HTTP(S) [API](https://git.sigsum.org/sigsum/tree/doc/api.md). -### 1.3 - Roadmap -First we describe our threat model. Then we give a bird's view of the design. -Finally, we wrap up with an incomplete frequently asked questions section. - ## 2 - Threat model We consider a powerful attacker that gained control of a signer's signing and release infrastructure. This covers a weaker form of attacker that is able to @@ -121,17 +117,18 @@ The fact that signing keys and related infrastructure components get compromised should not be controversial these days [\[SolarWinds\]](https://www.zdnet.com/article/third-malware-strain-discovered-in-solarwinds-supply-chain-attack/). -The attacker can also gain control of the log's signing key and infrastructure. -This covers a weaker form of attacker that is able to sign log data and -distribute it to a subset of isolated verifiers. For example, this could have -been the case when a remote code execution was found for a Certificate -Transparency Log +The same attacker also gained control of the signing key and infrastructure of a +sigsum log that is used for transparency. This covers a weaker form of attacker +that is able to sign log data and distribute it to a subset of isolated +verifiers. For example, this could have been the case when a remote code +execution was found for a Certificate Transparency Log [\[DigiCert\]](https://groups.google.com/a/chromium.org/g/ct-policy/c/aKNbZuJzwfM). -The overall system is said to be secure if a monitor can discover every signed -checksum that a verifier would accept. A log can misbehave by not presenting -the same append-only Merkle tree to everyone because it is attacker-controlled. -However, a log operator would only do that if it is likely to go unnoticed. +The overall system is said to be secure if a log monitor can discover every +signed checksum that a verifier would accept. +A log can misbehave by not presenting the same append-only Merkle tree to +everyone because it is attacker-controlled. +The attacker would only do that if it is likely to go unnoticed, however. For security we need a collision resistant hash function and an unforgeable signature scheme. We also assume that at most a threshold of independent @@ -140,7 +137,7 @@ attempts [split-view](https://datatracker.ietf.org/doc/html/draft-ietf-trans-gossip-05) and [slow-down](https://git.sigsum.org/sigsum/tree/archive/2021-08-24-checkpoint-timestamp) -attacks. A log operator can at best deny service with these assumptions. +attacks. An attacker can at best deny service with these assumptions. ## 3 - Design An overview of sigsum logging is shown in Figure 1. Before going into detail @@ -160,7 +157,7 @@ we give a brief primer below. | +---------->| Monitor |<-------+ |proof v +---------+ v +---------+ | +----------+ - | witness | | false | Verifier | + | Witness | | false | Verifier | +---------+ | claim +----------+ v investigate @@ -194,78 +191,63 @@ verify that this tree is fresh and append-only before cosigning it to achieve a distributed form of trust. A tree leaf contains four fields: - **shard_hint**: a number that binds the leaf to a particular _shard interval_. Sharding means that the log has a predefined time during which logging requests -are accepted. Once elapsed, the log can be shut down. +are accepted. Once elapsed, the log can be shut down or be made read-only. - **checksum**: most likely a hash of some data. The log is not aware of data; just checksums. - **signature**: a digital signature that is computed by a signer over the -leaf's shard hint and checksum. +selected shard hint and checksum. - **key_hash**: a cryptographic hash of the signer's verification key that can be used to verify the signature. -A shard hint is included in the signed statement to prevent replays in a -non-overlapping shard. See details in Section 4.2. - Any additional metadata that is use-case specific can be stored as part of the data that a checksum represents. Where data is located is use-case specific. Note that a key hash is logged rather than the public key itself. This reduces the likelihood that an untrusted key is discovered and used by mistake. In -other words, verifiers and monitors must locate keys and trust them explicitly. +other words, verifiers and monitors must locate signer verification keys +independently of logs, and trust them explicitly. ### 3.2 - Usage pattern #### 3.2.1 - Prepare a request -A signer selects a shard hint and a checksum that should be logged. The -selected shard hint represents an abstract statement like "sigsum logs that are -active during 2021". The selected checksum is most likely the output of a -hash function. For example, it could be the hash of an executable binary. +A signer selects a checksum that should be logged. For example, it could be the +hash of an executable binary or something else. + +The signer also selects a shard hint representing an abstract statement like +"sigsum logs that are active during 2021". Shard hints ensure that a log's +leaves cannot be replayed in a non-overlapping shard. -The selected shard hint and checksum are signed by the signer. A shard hint is -incorporated into the signed statement to ensure that a log's leaves cannot be -replayed in a non-overlapping shard by a good Samaritan. +The signer signs the selected shard hint and checksum. The signer also has to do a one-time DNS setup. As outlined below, logs will check that _some domain_ is aware of the signer's verification key. This is -part of a defense mechanism that helps us combat log spam. +part of a defense mechanism that helps log operators to deal with log spam. +Once present in DNS, a verification key can be used in subsequent log requests. #### 3.2.2 - Submit request Sigsum logs implement an HTTP(S) API. Input and output is human-readable and -uses a simple ASCII format. A more complex parser like JSON is not needed -because the exchanged data structures are primitive enough. - -A signer submits their shard hint, checksum, signature, and public verification -key as key-value pairs. The log uses the public verification key to check that -the signature is valid, then hashes it to construct the leaf's key hash. - -The signer also submits a _domain hint_. The log will download a DNS TXT -resource record based on the provided domain name. The downloaded result must -match the public verification key hash. By verifying that all signers control a -domain that is aware of their verification key, rate limits can be applied per -second-level domain. You would need a large number of domain names to spam the -log in any significant way if rate limits are not too loose. - -Using DNS to combat spam is convenient because many signers already have a -domain name. A single domain name is also relatively cheap. Another benefit is -that the same anti-spam mechanism can be used across several independent logs -without coordination. This is important because a healthy log ecosystem needs -more than one log to be reliable in case of downtime or unexpected events like - [cosmic rays](https://groups.google.com/a/chromium.org/g/ct-policy/c/PCkKU357M2Q/). +use a simple ASCII format. A more complex parser like JSON is not needed +since the data structures being exchanged are primitive enough. -A signer's domain hint is not part of the logged leaf because key management is -more complex than that. A separate project should focus on transparent key -management. Our work is about transparent _key-usage_. +The signer submits their shard hint, checksum, signature, public verification +key and domain hint as ASCII key-value pairs. The log verifies that the public +verification key is present in DNS and uses it to check that the signature is +valid, then hashes it to construct the Merkle tree leaf as described in +Section 3.1. -A sigsum log _tries_ to incorporate a leaf into its Merkle tree if a logging -request is accepted. There are however no _promises of public logging_ as in -Certificate Transparency. Therefore, sigsum logs do not provide low-latency. A -signer has to wait for an inclusion proof and a cosigned tree head. +When a submitted logging request is accepted, the log _tries_ to incorporate the +submitted leaf into its Merkle tree. There are however no _promises of public +logging_ as in Certificate Transparency. Therefore, sigsum logs do not provide +low latency---the signer has to wait for an inclusion proof and a cosigned tree +head. #### 3.2.3 - Wait for witness cosigning -Sigsum logs freeze a tree head every five minutes. Cosigning witnesses poll the -logs for so-called _to-sign_ tree heads, verifying that they are fresh and -append-only before doing a cosignature operation. Cosignatures are posted back -to the logs so that signers can easily fetch the finalized cosigned tree heads. +Sigsum logs periodically freeze the most current tree head, typically every five +minutes. Cosigning witnesses poll logs for so-called _to-sign_ tree heads and +verify that they are fresh and append-only before doing a cosignature operation. +Cosignatures are posted back to logs so that signers can easily fetch finalized +cosigned tree heads. -It takes five to ten minutes before a signer's distribution phase can start. +It thus takes five to ten minutes before a signer's distribution phase can start. The added latency is a trade-off that simplifies sigsum logging by removing the need for reactive gossip-audit protocols [\[G1,](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7346853) @@ -276,78 +258,83 @@ need for reactive gossip-audit protocols Use-cases like instant certificate issuance are not supported by design. #### 3.2.4 - Distribution -After a signer collected proofs of public logging the distribution phase can +Once a signer has collected proofs of public logging the distribution phase can start. Distribution happens using the same mechanism that is normally used for the data. For example, on a website, in a git repository, etc. +Signers distribute at least the following pieces: **Data:** -the signer's data. It can be used to reproduce a logged checksum. +the signer's data, for example an executable binary. It can be used to +reproduce a logged checksum. **Metadata:** -a signer's shard hint, signature, and verification key hash. Note that the -combination of data and metadata can be used to reconstruct the logged leaf. +the shard hint, the signature over shard hint and checksum, and the verification +key hash used in the log request. Note that the combination of data and +metadata can be used to reconstruct the logged leaf. **Proof:** -an inclusion proof that leads up to a cosigned tree head. +an inclusion proof that leads up to a cosigned tree head. Note that _proof_ +refers to the collection of an inclusion proof and a cosigned tree head. #### 3.2.5 - Verification -A verifier should only accept the distributed data if these criteria hold: -1. The signer's checksum is correct for the distributed data. -2. The signer's signed statement is valid for the specified public key. -3. The provided tree head can be reconstructed from the logged leaf and +A verifier should only accept the distributed data if the following criteria hold: +1. The data's checksum and shard hint are signed using the specified public key. +2. The provided tree head can be reconstructed from the logged leaf and its inclusion proof. -4. The provided tree head is from a known log with enough valid cosignatures. +3. The provided tree head is from a known log with enough valid cosignatures. Notice that there are no new outbound network connections for a verifier. -Therefore, a proof of public logging is only as convincing as the tree head that -an inclusion proof leads up to. Sigsum logs have trustworthy tree heads due to -using a variant of witness cosigning. In other words, a verifier cannot be -tricked into accepting some data whose checksum have yet to be publicly logged -unless the attacker controls more than a threshold of witnesses. +Therefore, a verifier will not be affected by future log downtime since the +signer already collected relevant proofs of public logging. Log downtime may be +caused by temporary operational issues or simply because a shard is done. -#### 3.2.6 - Monitoring -An often overlooked step is that transparency logging falls short if no-one keeps -track of what appears in the public logs. Monitoring is necessarily use-case -specific in sigsum. At minimum, you need to locate relevant public keys. You -may also need to be aware of how to locate the data that a checksum represents. +The lack of external communication means that a proof of public logging cannot +be more convincing than the tree head an inclusion proof leads up to. Sigsum +logs have trustworthy tree heads thanks to using a variant of witness cosigning. +A verifier cannot be tricked into accepting data whose checksum have not been +publicly logged unless the attacker controls more than a threshold of witnesses. -It should also be noted that sigsum logging can facilitate detection of attacks -even if a verifier fails open by enforcing the third and fourth criteria partially -in Section 3.2.5. For example, the fact that a distribution mechanism does not -serve proofs of public logging could indicate that there is an ongoing attack -against a signer's distributed infrastructure. A monitor may detect that. +#### 3.2.6 - Monitoring +An often overlooked step is that transparency logging falls short if no-one +keeps track of what appears in the public logs. Monitoring is necessarily +use-case specific in sigsum. At a minimum, monitors need to locate relevant +public keys. They may also need to be aware of how to locate the data that +logged checksums represent. ### 3.3 - Summary Sigsum logs are sharded and shut down at predefined times. A sigsum log can shut down _safely_ because verification on the verifier-side is not interactive. + The difficulty of bypassing public logging is based on the difficulty of controlling enough independent witnesses. A witness checks that a log's tree -head is correct before cosigning. Correct refers to fresh and append-only. +head is correct before cosigning. Correctness includes freshness and the +append-only property. Signers, monitors, and witnesses interact with the logs using an ASCII HTTP(S) -API. A signer must prove that they own a domain name as an anti-spam mechanism. -No data and rich metadata is logged to protect the log operator from poisoning. -It also keeps log operations simpler because there are fewer bytes to manage. +API. A signer must prove that they control a DNS domain name as an anti-spam +mechanism. No data or rich metadata is being logged, to protect the log +operator from poisoning. This also keeps log operations simpler because there +are less data to manage. -Verifiers interact with the logs indirectly through their signer's existing +Verifiers interact with logs indirectly through their signer's existing distribution mechanism. Signers are responsible for logging signed checksums -and distributing necessary proofs of public logging. Monitor discover signed -checksums in the logs, generating alerts if any key-usage is inappropriate. +and distributing necessary proofs of public logging. Monitors discover signed +checksums in the logs and generate alerts if any key-usage is inappropriate. ### 4 - Frequently Asked Questions -#### 4.1 - What parts of the design are we still thinking about? +#### 4.1 - What parts of the design are up for debate? A brief summary appeared in our archive on [2021-10-05](https://git.sigsum.org/sigsum/tree/archive/2021-10-05-open-design-thoughts?id=5c02770b5bd7d43b9327623d3de9adeda2468e84). It may be incomplete, but covers some details that are worth thinking more -about. We are still open to remove, add, or change things if it is motivated. +about. We are still open to remove, add, or change things. #### 4.2 - What is the point of having a shard hint? Unlike TLS certificates which already have validity ranges, a checksum does not carry any such information. Therefore, we require that the signer selects a -shard hint. The selected shard hint must be in a log's shard interval. A shard -interval is defined by a start time and an end time. Both ends of the shard -interval are inclusive and expressed as the number of seconds since the UNIX -epoch (January 1, 1970 00:00 UTC). +shard hint. The selected shard hint must be within a log's shard interval. A +shard interval is defined by a start time and an end time. Both ends of the +shard interval are inclusive and expressed as the number of seconds since the +UNIX epoch (January 1, 1970 00:00 UTC). Without sharding, a good Samaritan can add all leaves from an old log into a newer one that just started its operations. This makes log operations @@ -360,13 +347,52 @@ set it as large as possible. If a verified timestamp is needed to reason about the time of logging, you may use a cosigned tree head instead [\[TS\]](https://git.sigsum.org/sigsum/commit/?id=fef460586e847e378a197381ef1ae3a64e6ea38b). -#### 4.3 - XXX -- Why not store data in the log? XXX: answered enough already? -- Why not store rich metadata in the log? XXX: answered enough already? -- What (de)serialization parsers are needed and why? -- What cryptographic primitives are supported and why? -- What thought went into witness cosigning? Compare with other approaches, and -should include `get-tree-head-*` endpoints in more detail. -- Are there any privacy concerns? -- How does it work with more than one log? -- What policy should a verifier use? +A log operator that shuts down a completed shard will not affect verifiers. In +other words, a signer can continue to distribute proofs that were once +collected. This is important because a checksum does not necessarily expire. + +#### 4.3 - What is the point of having a domain hint? +Domain hints help log operators combat spam. By verifying that every signer +controls a domain name that is aware of their public key, rate limits can be +applied per second-level domain. You would need a large number of domain names +to spam a log in any significant way if rate limits are not set too loose. + +Notice that the effect of spam is not only about storage. It is also about +merge latencies. Too many submissions from a single party may render a log +unusable for others. This kind of incident happened in the real world already + [\[Aviator\]](https://groups.google.com/a/chromium.org/g/ct-policy/c/ZZf3iryLgCo/m/rdTAHWcdBgAJ). + +Using DNS as an anti-spam mechanism is not a perfect solution. It is however +better than not having any anti-spam mechanism at all. We picked DNS because +many signers have a domain. A single domain name is also relatively cheap. + +A signer's domain hint is not part of the logged leaf because key management is +more complex than that. A separate project should focus on transparent key +management. Our work is about transparent _key-usage_. + +We are considering if additional anti-spam mechanisms should be supported. + +#### 4.4 - What parts of witness cosigning are not done? +There are interesting policy aspects that relate to witness cosigning. For +example, what witnessing policy should a verifier use and how are trustworthy +witnesses discovered. This is somewhat analogous to a related policy question +that all log ecosystems must address. Which logs should be considered known? + +We do however think that witness cosigning could be done _from the perspective +of a log and its operator_. The + [sigsum/v0 API](https://git.sigsum.org/sigsum/tree/doc/api.md) +supports witness cosigning. Policy aspects for a log operator are easy because +it is relatively cheap to allow a witness to be a cosigner. It is not a log +operator's job to determine if any real-world entity is trustworthy. It is not +even a log operator's job to help signers and verifiers discover witness keys. + +Given a permissive policy for which witnesses are allowed to cosign, a signer +may not care for all retrieved cosignatures. Unwanted ones can simply be +removed before distribution to a verifier takes place. This is in contrast to +the original proposal by + [Syta et al.](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7546521), +which puts an authority right in the middle of a slowly evolving witnessing policy. + +#### 4.5 - More questions +- What are the privacy concerns? +- Add more questions here! |