02/66: ccs-2021: Write "Implementation" section.

[Ludovic Courtès]

civodul pushed a commit to branch master
in repository maintenance.

commit f8f4fdc87f2d4ee4e2ff0f9f114cb43afcd6272e
Author: Ludovic Courtès <ludo@gnu.org>
AuthorDate: Thu Apr 29 22:26:14 2021 +0200

    ccs-2021: Write "Implementation" section.
---
 doc/ccs-2021/security.sbib    |  16 ++++
 doc/ccs-2021/supply-chain.skb | 165 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 179 insertions(+), 2 deletions(-)

diff --git a/doc/ccs-2021/security.sbib b/doc/ccs-2021/security.sbib
index 6ec2fa8..5cfbb3f 100644
--- a/doc/ccs-2021/security.sbib
+++ b/doc/ccs-2021/security.sbib
@@ -96,6 +96,22 @@
   (publisher "USENIX Association")
   (month "August"))
 
+(misc callas98:rfc2440-openpgp
+  (author "Jon Callas, Lutz Donnerhacke, Hal Finney, Rodney
+Thayer")
+  (title "OpenPGP Message Format (RFC 2440)")
+  (institution "Internet Engineering Task Force (IETF)")
+  (year "1998")
+  (month "November")
+  (url "https://tools.ietf.org/html/rfc2440";))
+
+(misc callas2007:rfc4880-openpgp
+  (author "Jon Callas, Lutz Donnerhacke, Hal Finney, Rodney Thayer")
+  (title "OpenPGP Message Format (RFC 4880)")
+  (institution "Internet Engineering Task Force (IETF)")
+  (year "2007")
+  (month "November")
+  (url "https://tools.ietf.org/html/rfc4880";))
 
 #|
 (defun skr-from-bibtex ()
diff --git a/doc/ccs-2021/supply-chain.skb b/doc/ccs-2021/supply-chain.skb
index 97fb222..5827d42 100644
--- a/doc/ccs-2021/supply-chain.skb
+++ b/doc/ccs-2021/supply-chain.skb
@@ -588,9 +588,170 @@ Building from this channel:
 satisfy the graph theorist or the Git geek in you, but if you are up for
 a quick tour of the implementation, the next section is for you!]))
 
-   (chapter :title [Implementation])
+   (chapter :title [Implementation]
+      
+      (p [Channel authentication as described above is now used in
+production.  This section documents the reasoning behind some of the
+important implementation choices that we made and our early
+experience.])
+
+      (section :title [Commit Signatures]
+        
+        (p [We chose to use detached OpenPGP signatures on commits.
+This choice was not motivated by a belief that OpenPGP is the “right
+tool for the job”—on the contrary, its complexity, which is a result its
+broad and extensible specification ,(ref :bib
+'callas2007:rfc4880-openpgp), made it a poor candidate in our eyes.
+More focused options, such as minisign,(footnote (ref :url
+"https://jedisct1.github.io/minisign";)), looked more appealing.
+However, we felt that the fact that OpenPGP commit signing is
+well-supported by Git makes a significant practical difference:
+developers can easily be set up to sign commits with GnuPG and commands
+such as ,(tt [git log]) can verify and display signatures; ways to deal
+with OpenPGP keys and signatures, although complex, are also
+well-documented.])
+        
+        (p [Key distribution is an important issue.  We did not want
+the whole mechanism to lazily fetch keys (,(it [certificates]) in
+OpenPGP parlance) from key servers: this was bound to be unreliable and
+slow.  We instead chose to store keys inside the repository, as plain
+binary or ASCII-armored OpenPGP packets.  Our recommendation is to keep
+them in a dedicated branch to avoid cluttering regular branches (channel
+authors can include in the channel metadata the name of the branch where
+keys are to be found).  The authentication code loads keys in memory
+when it starts and looks them up for signature verification.  All the
+keys ever used to sign commits must be kept in the repository so that
+past commits can be authenticated.  Guix today has 81 ASCII-armored keys
+representing less than 2 MiB.  If needed, this could be reduced by
+removing unused OpenPGP packets from the keys, such as signature
+packets, and by storing them in binary format.]))
+
+      (section :title [Performance]
+      
+        (p [The core idea, the authorization invariant, is simple to
+understand and its implementation can be relatively simple, too—a good
+property for security-sensitive code.  However, with more than a
+thousand commit pushed to Guix every month, users may often find
+themselves authenticating hundreds of commits when running ,(tt [guix
+pull]).  The implementation must be able to perform well.])
+      
+        (p [At the algorithmic level, the main optimization is to
+consider than, if a commit has been authenticated, then all the commits
+in its transitive closure are automatically considered authentic and do
+not need to be checked.  This optimization stems from the fact that the
+commit graph is a Merkle DAG.  The implementation takes advantage of it
+in two ways: by not skipping commits that are in the transitive closure
+of the currently-used Guix commit, and by maintaining a per-user cache
+of previously-authenticated commits that can also be skipped.])
+        
+        (p [At the implementation level, two key decisions were made:
+verifying signatures in-process, and dismissing unnecessary OpenPGP
+features.  The go-to technique of spawning GnuPG and Git processes to
+verify each commit signature would have been prohibitively expensive.
+Instead, to traverse the Git commit graph, we use libgit2, a C library
+that implements the Git “protocols”, ,(it [via]) its Guile-Git bindings.])
+
+        (p [We also have an OpenPGP implementation for GNU Guile, the
+implementation language of Guix.  This OpenPGP implementation is limited
+to parsing the OpenPGP packets found in signatures and in keys, and to
+verifying signatures.  It does not implement the more complex OpenPGP
+features that are useless in this context, such as: key signatures and
+the web of trust, and key expiration and revocation.  Timestamps in
+OpenPGP signatures and expiry dates are easily forged; what matters in
+our context is the causality of commits: that a signature on a commit is
+valid and authorized.  Likewise, revocation makes little sense in this
+context; what matters is whether the authorization invariant holds.]))
+      
+      (section :title [Generalization]
+        
+        (p [As explained in ,(numref :text [Section] :ident
+"rationale"), the general problem being solved—authenticating Git
+checkouts—is in no way specific to Guix, and the solution we devised may
+in fact be of interest to ,(emph [any]) Git user.  For this reason, and
+also to facilitate the work of Guix channel developers, we introduced a
+new command, separate from the channel machinery, to authenticate a Git
+checkout.  The command can be invoked on any Git repository, as in this
+example:])
+       
+        (prog :line #f :class "small" [
+guix git authenticate \\
+  0c119db2ea86a389769f4d2b9c6f5c41c027e336 \\
+  "3CE4 6455 8A84 FDC6 9DB4  0CFB 090B 1199 3D9A EBB5"
+])
+       
+        (p [The command above authenticates the checkout in the current
+directory.  The arguments represent its ,(emph [introduction]): the
+introductory commit, and the fingerprint of the OpenPGP key used to sign
+that commit.  Additional options allow users to specify, for instance,
+the name of the branch where OpenPGP keys are to be found.])
+
+        (p [This command can also authenticate ,(emph [historical
+commits])—signed commits that were made ,(emph [before]) a ,(tt
+[.guix-authorizations]) file was introduced in the repository.  In that
+mode, users must provide an authorization file that represents the
+static set of authorizations for all those commits whose parent(s) lack
+,(tt [.guix-authorizations]).  We found it useful to retroactively
+history of the Guix repository, where commit signing became compulsory
+several years before this authentication mechanism was in place.])
+        
+        (p [This interface is low-level and would benefit from
+simplifications.  For instance, repository introductions obtained by
+users could be gathered in a single place, once for all, such that users
+do not have to specify them every time.  Communicating introductions
+could also be simplified: the two twenty-byte strings above could be
+represented as a single 56-character base64 string, or as a QR code.
+For broad acceptance, the best option would be to integrate the
+functionality in Git proper.]))
+
+      (section :title [Experience]
+        
+        (p [Channel authentication as described above has been deployed
+and used in production in Guix for a year, since June 2020.  At that
+time, users who ran ,(tt [guix pull]) transparently obtained the new
+code, and all subsequent invocations of ,(tt [guix pull]) performed code
+authentication and downgrade prevention.  In one year, there was one
+incident where a committer mistakenly pushed a commit signed with an
+unauthorized key, which was immediately detected by anyone who attempted
+to run ,(tt [guix pull]), and the offending commit was removed in
+minutes (with a ,(emph [hard reset]) to its parent commit, in Git
+parlance).  Such mistakes can be avoided by having a server-side hook
+running ,(tt [guix git authenticate]), but we did not have the ability
+to run such hooks at the time.])
+        
+        (p [Downgrade prevention has had a more visible impact, at
+least for advanced users with rather unusual workflows.  As an example,
+we have had reports of users who would pull to development or
+work-in-process branches, using ,(tt [guix pull --branch=,(it
+[devel])]), where ,(it [devel]) is the name of the branch.  When trying
+to pull back to the main branch, ,(tt [guix pull]) would report an
+error saying that the target commit is “unrelated” to the source
+commit.  Indeed, because the development branch has not been merged into
+the main branch, the latest commit on the main branch is not a
+descendant of the latest commit on the development branch.  Some users
+were initially surprised but quickly understood the value of this
+protection.])
+        
+        (p [System downgrade prevention has already proved helpful.
+Since ,(tt [guix system reconfigure]) and ,(tt [guix deploy]) prevent
+downgrades, a sysadmin cannot mistakenly reconfigure the system to and
+older or unrelated commit; this is particularly useful on system
+administered by several people, where an administrator cannot mistakenly
+“undo” the upgrade performed by another administrator.])
+        
+        (p [More importantly, checkout authentication together with
+system downgrade prevention enabled us to provide a trustworthy ,(emph
+[unattended upgrade]) service.  This functionality is typically depended
+on by server administrators.  The service periodically pulls and
+reconfigures the system.  With the guarantees Guix provides, the worst
+that can happen is that an upgrade does not take place.])
+        
+        (p [Generalized authentication support offered by ,(tt [guix
+git authenticate]) has allowed Guix developers to use authentication
+support on a few repositories beside Guix and Guix channels.  We have
+yet to see broader adoption but we reckon that simplifying the interface
+may be a precondition, as explained above.])))
    
-   (chapter :title [SHA-1] :ident "sha1"
+   (chapter :title [Notes on SHA-1] :ident "sha1"
       
       (p [We can’t really discuss Git commit signing without mentioning
 SHA-1.  The venerable crytographic hash function is approaching end of