documented the decided ssh signature format

Refer to doc/proposals/2021-11-ssh-signature-format.md for details.

2 files changed, 76 insertions, 66 deletions

diff --git a/doc/api.md b/doc/api.md
index 664f735..640a10d 100644
--- a/doc/api.md
+++ b/doc/api.md
@@ -31,16 +31,14 @@ Figure 1 of our design document gives an intuition of all involved parties.
 ## 2 - Primitives
 ### 2.1 - Cryptography
 Logs use the same Merkle tree hash strategy as
-[RFC 6962,§2](https://tools.ietf.org/html/rfc6962#section-2).
-The hash functions must be
-[SHA256](https://csrc.nist.gov/csrc/media/publications/fips/180/4/final/documents/fips180-4-draft-aug2014.pdf).
-Logs and witnesses must sign tree heads using
-[Ed25519](https://tools.ietf.org/html/rfc8032).
-
-All other parts that are not Merkle tree related should use SHA256 as
-the hash function.  Using more than one hash function would increases
-the overall attack surface: two hash functions must be collision
-resistant instead of one.
+	[RFC 6962,§2](https://tools.ietf.org/html/rfc6962#section-2).
+Any mention of hash functions or digital signature schemes refers to
+	[SHA256](https://csrc.nist.gov/csrc/media/publications/fips/180/4/final/documents/fips180-4-draft-aug2014.pdf)
+as well as
+	[Ed25519](https://tools.ietf.org/html/rfc8032).
+The exact
+	[signature format](https://github.com/openssh/openssh-portable/blob/master/PROTOCOL.sshsig)
+is defined by OpenSSH.
 
 ### 2.2 - Serialization
 Log requests and responses are transmitted using simple ASCII encodings, for a
@@ -52,21 +50,10 @@ favoring ease of decoding and encoding over efficiency on the wire.
 
 We use the [Trunnel](https://gitweb.torproject.org/trunnel.git)
 [description language](https://www.seul.org/~nickm/trunnel-manual.html)
-to define (de)serialization of data structures that need to be signed or
-inserted into the Merkle tree.  It is about as expressive as the
-[TLS presentation language](https://tools.ietf.org/html/rfc8446#section-3).
-However, it is readable by humans _and_ machines.
-"Obviously correct code" can be generated in C, Go, etc.
-
-A fair summary of our Trunnel usage is as follows.
-
-All integers are 64-bit, unsigned, and in network byte order.
-Fixed-size byte arrays are put into the serialization buffer in-order,
-starting from the first byte.  These basic types are concatenated to form a
-collection.  You should not need a general-purpose Trunnel
-(de)serialization parser to work with this format.  If you have one,
-you may use it though.  The main point of using Trunnel is that it
-makes a simple format explicit and unambiguous.
+to define data structures that need to be (de)serialized in the log.  Data
+structures that need to be signed have additional SSH-specific metadata.  For
+example, metadata includes a magic preamble string and a signing context.  An
+implementer can easily express the SSH signing format using Trunnel.
 
 ### 2.3 - Merkle tree
 #### 2.3.1 - Tree head
@@ -77,7 +64,6 @@ struct tree_head {
 	u64 timestamp;
 	u64 tree_size;
 	u8 root_hash[32];
-	u8 key_hash[32];
 };
 ```
 `timestamp` is the time since the UNIX epoch (January 1, 1970 00:00 UTC) in
@@ -90,25 +76,24 @@ to prove to a verifier that public logging happened within some interval
 
 `root_hash` is a Merkle tree root hash that fixes a log's structure and content.
 
-`key_hash` is a log's hashed public key.  The key is encoded as defined in
-[RFC 8032, section 5.1.2](https://tools.ietf.org/html/rfc8032#section-5.1.2)
-before hashing it.  The result is used as a unique log identifier that prevents
-an [attack](https://git.sigsum.org/sigsum/tree/archive/2021-08-10-witnessing-broader-discuss#n95)
-in multi-log ecosystems.
-
 #### 2.3.2 - (Co)signed tree head
-A signed tree head is composed of a tree head and a signature.  This structure
-does not have a Trunnel definition because it is neither signed nor logged.
-
-Logs and witnesses sign the same `tree_head` structure, see Section 2.3.1.
-
-Note that tree heads are scoped to a specific log to ensure that a witness
-signature for log X cannot be confused with a witness signature for log Y.
+Logs and witnesses perform (co)signing operations by treating the serialized
+tree head as the message `M` in SSH's 
+	[signing format](https://github.com/openssh/openssh-portable/blob/master/PROTOCOL.sshsig).
+The hash algorithm string must be "SHA256".  The reserved string must be empty.
+The namespace field must be set to `tree_head:v0:<key-hash>@sigsum.org`, where
+`<key hash>` is substituted with the log's hashed public key.  The public key is
+encoded as defined in
+	[RFC 8032, section 5.1.2](https://tools.ietf.org/html/rfc8032#section-5.1.2)
+before hashing it.  This ensures a _sigsum log specific tree head context_ that
+prevents a possible
+	[attack](https://git.sigsum.org/sigsum/tree/archive/2021-08-10-witnessing-broader-discuss#n95)
+in multi-log ecosystems.
 
 A witness must not cosign a tree head if it is inconsistent with prior history
-or if the timestamp is older than 5 minutes.  A witness can be viewed as two
-abstract roles: Verifier("append-only") and Verifier("freshness")
-	[\[WR\]](https://git.sigsum.org/sigsum/tree/archive/2021-08-31-checkpoint-timestamp-continued#n84).
+or if the timestamp is older than 5 minutes.  This means that a witness plays
+	[two abstract roles](https://git.sigsum.org/sigsum/tree/archive/2021-08-31-checkpoint-timestamp-continued#n84):
+Verifier("append-only") and Verifier("freshness").
 
 #### 2.3.3 - Tree leaf
 Logs support a single leaf type.  It contains a signer's statement,
@@ -116,7 +101,6 @@ signature, and key hash.
 
 ```
 struct statement {
-    u64 shard_hint;
     u8 checksum[32];
 }
 
@@ -127,16 +111,21 @@ struct tree_leaf {
 }
 ```
 
-`shard_hint` must match a log's shard interval and is determined by the signer.
-
 `checksum` is a hashed preimage.  The signer selects a 32-byte preimage which
 represents some data.  It is recommended to set this preimage to `H(data)`, in
 which case the checksum will be `H(H(data))`.
 
-`signature` is a signature over a serialized `statement`.  It must be possible
-to verify this signature using the signer's public verification key.
-
-`key_hash` is a hash of the signer's public verification key.  It is included
+`signature` is computed by treating the above preimage as the message `M`
+in SSH's 
+	[signing format](https://github.com/openssh/openssh-portable/blob/master/PROTOCOL.sshsig).
+The hash algorithm string must be "SHA256".  The reserved string must be empty.
+The namespace field must be set to `tree_leaf:v0:<shard_hint>@sigsum.org`, where
+`<shard_hint>` is replaced with the shortest decimal ASCII representation of a
+shard hint that matches the log's shard interval.  This ensures a _sigsum
+shard-specific tree leaf context_.
+
+`key_hash` is a hash of the signer's public verification key using the same
+format as Section 2.3.2.  It is included
 in `tree_leaf` so that each leaf can be attributed to a signer.  A hash,
 rather than the full public key, is used to motivate monitors and verifiers to
 locate the appropriate key and make an explicit trust decision.
@@ -276,7 +265,8 @@ Input:
 - `end_size`: index of the last leaf to retrieve, ASCII-encoded decimal number.
 
 Output on success:
-- `shard_hint`: `tree_leaf.statement.shard_hint`, ASCII-encoded decimal number.
+- `shard_hint`: shard hint to use as tree leaf context, ASCII-encoded decimal
+  number.
 - `checksum`: `tree_leaf.statement.checksum`, hex-encoded.
 - `signature`: `tree_leaf.signature`, hex-encoded.
 - `key_hash`: `tree_leaf.key_hash`, hex-encoded.
@@ -299,7 +289,8 @@ POST <base url>/sigsum/v0/add-leaf
 ```
 
 Input:
-- `shard_hint`: `tree_leaf.statement.shard_hint`, ASCII-encoded decimal number.
+- `shard_hint`: shard hint to use as tree leaf context, ASCII-encoded decimal
+  number.
 - `preimage`: the preimage used to compute `tree_leaf.statement.checksum`, hex-encoded.
 - `signature`: `tree_leaf.signature`, hex-encoded.
 - `verification_key`: public verification key that can be used to verify the
@@ -335,6 +326,7 @@ TODO: update the above with valid input.  Link
 on how one could produce it "byte-for-byte" using Python and ssh-keygen -Y.
 
 ### 3.7 - add-cosignature
+=======
 ```
 POST <base url>/sigsum/v0/add-cosignature
 ```
@@ -360,6 +352,10 @@ $ echo "cosignature=d1b15061d0f287847d066630339beaa0915a6bbb77332c3e839a32f66f18
 key_hash=662ce093682280f8fbea9939abe02fdba1f0dc39594c832b411ddafcffb75b1d" | curl --data-binary @- <base url>/sigsum/v0/add-cosignature
 ```
 
+TODO: update the above with valid input.  Link
+	[proposal](https://git.sigsum.org/sigsum/tree/doc/proposals/2021-11-ssh-signature-format.md)
+on how one could produce it "byte-for-byte" using Python and ssh-keygen -Y.
+
 ## 4 - Parameter summary
 Ed25519 as signature scheme. SHA256 as hash function.
 
diff --git a/doc/design.md b/doc/design.md
index ed972d0..7464ecc 100644
--- a/doc/design.md
+++ b/doc/design.md
@@ -97,7 +97,8 @@ protocol directly into the log.  It is a variant of
 	[witness cosigning](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7546521).
 - **No cryptographic agility**: the only supported signature schemes and hash
 functions are Ed25519 and SHA256.  Not having any cryptographic agility makes
-protocols and data formats simpler and more secure.
+protocols and data formats simpler and more secure.  The used signing format is
+compatible with OpenSSH and can easily be modelled with the below parsers.
 - **Simple (de)serialization parsers:** complex (de)serialization parsers
 increase attack surfaces and make the system more difficult to use in
 constrained environments.  Signed and logged data can be (de)serialized using
@@ -166,7 +167,7 @@ we give a brief primer below.
 ```
 
 A signer wants to make their key-usage transparent.  Therefore, they sign a
-statement that sigsum logs accept.  That statement encodes a checksum of some
+statement that sigsum logs accept.  That statement encodes a checksum for some
 data.  Minimal metadata must also be logged, such as the checksum's signature
 and a hash of the public verification key.  A hash of the public verification
 key is configured in DNS as a TXT record to help log operators combat spam.
@@ -193,7 +194,7 @@ distributed form of trust.  A tree leaf contains four fields:
 Sharding means that the log has a predefined time during which logging requests
 are accepted.  Once elapsed, the log can be shut down or be made read-only.
 - **checksum**: a cryptographic hash that commits to some data.
-- **signature**: a digital signature that is computed by a signer over the
+- **signature**: a digital signature that is computed by a signer for the
 selected shard hint and checksum.
 - **key_hash**: a cryptographic hash of the signer's verification key that can
 be used to verify the signature.
@@ -215,7 +216,9 @@ 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 signer signs the selected shard hint and checksum.
+The signer signs the selected checksum using a sigsum-specific context that
+incorporates the above shard hint.  The exact signing format is compatible with
+`ssh-keygen -Y` when using Ed25519 and SHA256.
 
 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
@@ -246,8 +249,9 @@ accepted their request, after which it can be verified using an inclusion proof.
 Cosigning witnesses poll the logs for tree heads to be cosigned once per minute,
 verifying that they are fresh (not back-dated more than five minutes) and
 append-only (no leaves were removed or modified) before doing any cosignature
-operations.  Cosignatures are posted back to the logs so that they become
-available in one place.
+operations.  Tree heads are signed using the same signing format as tree leaves,
+expect that a different sigsum and log-specific context is used.  Cosignatures
+are posted back to the logs, making them available in one place.
 
 The above means that it takes up to 5-10 minutes before a cosigned tree head is
 available.  Depending on implementation it may be as short as one minute.  The
@@ -271,9 +275,9 @@ the signer's data, for example an executable binary.  It can be used to
 reproduce a logged checksum.
 
 **Metadata:**
-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.
+the shard hint to use as signing context, the resulting signature over 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.  Note that _proof_
@@ -281,7 +285,7 @@ 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 the following criteria hold:
-1. The data's checksum and shard hint are signed using the specified public key.
+1. The data's checksum is signed using the specified shard hint and public key.
 2. The provided tree head can be reconstructed from the logged leaf and
 its inclusion proof.
 3. The provided tree head is from a known log with enough valid cosignatures.
@@ -324,6 +328,9 @@ distribution mechanism.  Signers are responsible for logging signed checksums
 and distributing necessary proofs of public logging.  Monitors discover signed
 checksums in the logs and generate alerts if any key-usage is inappropriate.
 
+The signing format for logs, witnesses, and signers is based on a subset of
+what is supported by OpenSSH.  Ed25519 and SHA256 must be used as primitives.
+
 ### 4 - Frequently Asked Questions
 #### 4.1 - What parts of the design are up for debate?
 A brief summary appeared in our archive on
@@ -331,7 +338,14 @@ A brief summary appeared in our archive on
 It may be incomplete, but covers some details that are worth thinking more
 about.  We are still open to remove, add, or change things.
 
-#### 4.2 - What is the point of submitting a checksum's preimage?
+# 4.2 - Why use the OpenSSH signing format?
+Our main criteria for a signing format is that it can express signing contexts
+without any complex parsers.  A magic preamble would be good for overall hygiene
+as well.  We sketched on such a format using Trunnel.  We realized that by
+tweaking a few constants it would be compatible with SSH's signing format.  If
+it is possible to share a format with an existing reliable ecosystem, great!
+
+#### 4.3 - What is the point of submitting a checksum's preimage?
 Logging arbitrary bytes can poison a log with inappropriate content.  While a
 leaf is already light in Sigsum, a stream of leaves could be used.  By not
 allowing any checksum to be arbitrary because logs compute them, a malicious
@@ -344,7 +358,7 @@ is `H(D)`.  The resulting checksum would be `H(H(D))`.  The log will not be in a
 position to observe the data `D`, thereby removing power in the form of trivial
 data mining while at the same time making the overall protocol less heavy.
 
-#### 4.3 - What is the point of having a domain hint?
+#### 4.4 - 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
@@ -371,7 +385,7 @@ that added this criteria.
 
 We are considering if additional anti-spam mechanisms should be supported in v1.
 
-#### 4.4 - What is the point of having a shard hint?
+#### 4.5 - 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 within a log's shard interval.
@@ -398,7 +412,7 @@ 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.5 - What parts of witness cosigning are not done?
+#### 4.6 - 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
@@ -419,6 +433,6 @@ 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.6 - More questions
+#### 4.7 - More questions
 - What are the privacy concerns?
 - Add more questions here!