diff options
Diffstat (limited to 'rainbow/permissions/manifest.txt')
| -rw-r--r-- | rainbow/permissions/manifest.txt | 153 |
1 files changed, 153 insertions, 0 deletions
diff --git a/rainbow/permissions/manifest.txt b/rainbow/permissions/manifest.txt new file mode 100644 index 0000000..cf0ff54 --- /dev/null +++ b/rainbow/permissions/manifest.txt @@ -0,0 +1,153 @@ +Verification System Data +======================== + +:Author: Michael Stone <michael@laptop.org>, Noah Kantrowitz <noah@laptop.org> +:Date: August 8, 2007 + +Our system for update verification manipulates four kinds of data: +envelopes, keys, credentials, and manifests. + +Presently, we intend to use JSON as a transfer encoding because we only need to +represent tree-structured data and because we want an encoding that is easily +and safely parseable in pure Python and in other languages. + +If we learn that we need a canonical encoding, a more space-efficient encoding, +or an encoding that can be more efficiently streamed, then we will consider +alternatives. + + +Envelopes +--------- + +Envelopes are tuples of the form + + (version, type, data) :: (Integer, String, Value) + ^ ^ ^ + | | \________ a JSON value in a format governed by (version, type) + | \______ a hint about how to interpret the data field that follows. + \_________ an opaque version identifier; see below. + +The version identifier is intended to specify a minimal dialect that must be +supported by compliant clients. Backwards-compatible extensions of this dialect +may be included in an enveloped value without changing the version identifier. + + Note: Noah suggests make the version identifier transparent and declare it to + be an integer with a a monotonically increasing value. I'm okay with this, + but since we anticipate changing the identifer only when making + backwards-incompatible protocol changes, I think it might as well be opaque. + +Keys +---- + +Keys are envelopes with version 1 and type "key". A key's datum consists of a +tuple + + (algorithm, fingerprint, key) :: (String, String, String) + ^ ^ ^ + | | \______ an opaque string specifiying the actual key + | \______ an opaque string to use to refer to the key + \_________ an opaque algorithm identifier; + +In practice, we might see a key encoded as: + [1, "key", ["rsa", "12508713460986140897", "AE1908579871250981230896109761"]] + + +Credentials +----------- + +A credential is an envelope with version 1 and type "credential". Conceptually, +its datum consists of a relation whose tuples are signatures of the form: + + (signature-algorithm, key, message, signature) + +However, in practice, the message is defined implicitly by context (i.e. as the +hash of the manifest with which this credential is paired) and we wish to use +the credential/manifest system to help detect accidental corruption as early as +possible, including corruption of the manifest. + +Therefore, we actually propose to represent the datum of a manifest credential +as a tuple of + + (hash-alg, sig-alg, expected-hash, key-identifier, signature) + +We include the manifest hash as a convenient way to check that the manifest +was not accidentally damaged in transit (e.g. by a flash corruption bug). + +The key fingerprint identifies the key that should be used to verify the +signature. + +The hash-algorithm and signature-algorithm are used to verify the signature +against the *computed* manifest-hash (not the one cached in the signature +message). + +Finally, the signature itself is opaque. + +In actual JSON, we might imagine that such a message would look like: + + [1, "credential", [ ["sha1", "rsa", "DEADBEEF", "123MYKEY", "0PAQU3S1G"], + ["whirlpool", "ecc", "123095", "9912KEY", "8567A"] ] ] + + + +Manifests +--------- + +Manifests are the most complicated piece of the system because they have +different conceptual and transfer-encoded forms. + +Conceptually, a manifest's datum is a constraint-set. Implementations of this +constraint language are free to support checking as many or as few kinds of +constraint as they wish. Clearly, though, adequate verification of a file-system +against a manifest depends on both the presence of a constraint set that +sufficiently constrains the properties of the file-system being checked and a +correct and complete implementation of a checker for that constraint-set. + +This model controls the implementation cost of both the verification machine +(and the manifest generation tool) while allowing great flexibility in the +underlying properties being verified and in the degree to which we compromise +our implementation goals in the face of time pressure. + +Details +~~~~~~~ + +There are several basic constraints we wish to support. These include +constraints on file content, file type (normal, hardlink, symlink, device, ...), +permissions, ownership, and on the contents of directories. + +Manifests are envelopes with version 1 and type "manifest". A manifest's datum +consists of a tuple of a dictionary of optimization hints and a dictionary of +constraints. Structurally, the datum looks like + + (Hint -> Value, Constraint -> (Query, Result)) + +Here "hints" are opaque strings that may be given some uninterpreted data as an +argument (e.g. "invert-filesystem" : true). These are provided because checking +some of the global constraints may rely on expensive-to-compute structures such +as an inverted index that maps inodes to the paths that point to them. + +The constraint itself dictionary is also made slightly more complicated in the +name of speed and memory usage. While conceptually, we wish to store a ternary +relation with columns + + (constraint-algorithm, query, expected-result) + +in practice, we expect that there will very few (~5) constraint algorithms and +very many (~100000) (query, expected-result) pairs. Hence we suggest +optimizing for this case by grouping the relation's tuples by +constraint-algorithm, as shown above in the structural description. + +A small example of a manifest might be: + + [1, "manifest", [ + {"invert-filesystem": ["/links"]}, + {"file-sha1" : [ ["/etc/passwd", "BLAH18AK"], + ["/bin/bash", "LA81985ED"]], + "permissions" : [ ["/my/secret", 448] ], + "same-inode" : [ [["/links/1", "/links/2", "/links/3"], null] ], + "dir-contains" : [ ["/", ["bin", "sbin"]] ], + "update-excludes": [ ["/security", null] ] + }]] + + + + |