{"thread":{"id":"29225","subject":"[PATCH 6/6] Provide documentation for git message digest extensions","startedAt":"2011-12-21T07:13:28Z","lastAt":"2011-12-21T07:13:28Z","messageCount":1,"participants":["Bill Zaumen"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"181567","messageId":"1324451608.1684.24.camel@yos","threadId":"29225","inReplyTo":null,"subject":"[PATCH 6/6] Provide documentation for git message digest extensions","fromName":"Bill Zaumen","fromEmail":"bill.zaumen+git@gmail.com","sentAt":"2011-12-21T07:13:28Z","receivedAt":"2011-12-21T07:13:28Z","isPatch":true,"sender":{"key":"bill.zaumen+git@gmail.com","avatar":null},"body":"The documentation includes API documentation for commands\nand technical documentation for the message-digest-related\nchanges. The technical documentation is in\n\n* Documentation/technical/collision-detect.txt\n* Documentation/technical/pack-format.txt\n\nThe modified commands are documented in\n\n* Documentation/git-count-objects.txt\n* Documentation/git-index-pack.txt\n* Documentation/git-verify-pack.txt\n\nSigned-off-by: Bill Zaumen \n---\n Documentation/git-count-objects.txt | 12 +-\n Documentation/git-index-pack.txt | 17 +-\n Documentation/git-verify-pack.txt | 27 ++\n Documentation/technical/collision-detect.txt | 342 ++++++++++++++++++++++++++\n Documentation/technical/pack-format.txt | 47 ++++\n 5 files changed, 439 insertions(+), 6 deletions(-)\n create mode 100644 Documentation/technical/collision-detect.txt\n\ndiff --git a/Documentation/git-count-objects.txt b/Documentation/git-count-objects.txt\nindex 23c80ce..4cdbaf5 100644\n--- a/Documentation/git-count-objects.txt\n+++ b/Documentation/git-count-objects.txt\n@@ -8,7 +8,7 @@ git-count-objects - Count unpacked number of objects and their disk consumption\n SYNOPSIS\n --------\n [verse]\n-'git count-objects' [-v]\n+'git count-objects' [-v] [-M]\n \n DESCRIPTION\n -----------\n@@ -25,6 +25,16 @@ OPTIONS\n \tobjects, number of packs, disk space consumed by those packs,\n \tand number of objects that can be removed by running\n \t`git prune-packed`.\n+-M::\n+--count-md::\n+\tReport the number of loose objects with no stored message digests.\n+\tWith the -v option, the number of missing \"mds\" files (these\n+\tcontain the message digests for the SHA1 hashes in the corresponding\n+\t\"idx\" files) is reported, along with a count of the number of\n+\tmds files whose size is wrong (e.g., an index was created but the\n+\texisting MDS file was not updated) and a count of the number of\n+\tobjects in pack files that do not have a stored message digest.\n+\tValues that are zero are not shown.\n \n GIT\n ---\ndiff --git a/Documentation/git-index-pack.txt b/Documentation/git-index-pack.txt\nindex 909687f..c9389f4 100644\n--- a/Documentation/git-index-pack.txt\n+++ b/Documentation/git-index-pack.txt\n@@ -11,14 +11,14 @@ SYNOPSIS\n [verse]\n 'git index-pack' [-v] [-o ] \n 'git index-pack' --stdin [--fix-thin] [--keep] [-v] [-o ]\n- []\n+\t\t [-m ] []\n \n\n DESCRIPTION\n -----------\n-Reads a packed archive (.pack) from the specified file, and\n-builds a pack index file (.idx) for it. The packed archive\n-together with the pack index can then be placed in the\n+Reads a packed archive (.pack) from the specified file, and builds a\n+pack index file (.idx) and a pack mds file (.mds) for it. The packed\n+archive together with the pack index can then be placed in the\n objects/pack/ directory of a git repository.\n \n\n@@ -35,6 +35,14 @@ OPTIONS\n \tfails if the name of packed archive does not end\n \twith .pack).\n \n+-m ::\n+\tWrite the generated pack mds file into the specified.\n+\tfile Without this option, the name of the pack mds\n+\tfile is constructed from the name of packed archive\n+\tfile by replacing .pack with .idx (and the program\n+\tfails if the name of packed archive does not end\n+\twith .pack).\n+\n --stdin::\n \tWhen this flag is provided, the pack is read from stdin\n \tinstead and a copy is then written to . If\n@@ -74,7 +82,6 @@ OPTIONS\n --strict::\n \tDie, if the pack contains broken objects or links.\n \n-\n Note\n ----\n \ndiff --git a/Documentation/git-verify-pack.txt b/Documentation/git-verify-pack.txt\nindex cd23076..f69ed3f 100644\n--- a/Documentation/git-verify-pack.txt\n+++ b/Documentation/git-verify-pack.txt\n@@ -33,6 +33,19 @@ OPTIONS\n \tDo not verify the pack contents; only show the histogram of delta\n \tchain length. With `--verbose`, list of objects is also shown.\n \n+-M::\n+--show-mds::\n+\tShow the message digests along with the 40-character object names\n+\t(SHA1 value in hexidecimal). Ignored if --stat-only is set. If\n+\t--verbose is not set, only the table indexed by object names is\n+\tshown, although the files will be verified. The message digests\n+\tprinted are the actual ones - if the MDS file does not contain these,\n+\tthe verification will fail. The message digests will be\n+\tprefaced with a two-byte code indicating the type of digest.\n+\tThe values (n hexadecimal) are 01 for a CRC, 05 for SHA-1, 08\n+\tfor SHA-256, and 10 for SHA-512. If the digest stored does\n+\tnot match the actual digest, the actual one is printed as well.\n+\n \\--::\n \tDo not interpret any more arguments as options.\n \n@@ -48,6 +61,20 @@ for objects that are not deltified in the pack, and\n \n for objects that are deltified.\n \n+When the -M option is used, the offset-in-pack field is followed by an\n+entry giving the message digest. The format used is:\n+\n+ md=0xHEX_VALUE\n+\n+when a message digest exists, and\n+\n+ \n+\n+when a message digest does not exist. These entries precede the depth\n+entry for deltified objects. A non-existent message digest will be shown\n+only if the MDS file is missing - while the MDS-file format allows missing\n+entries, the file will not be considered valid.\n+\n GIT\n ---\n Part of the linkgit:git[1] suite\ndiff --git a/Documentation/technical/collision-detect.txt b/Documentation/technical/collision-detect.txt\nnew file mode 100644\nindex 0000000..d5a4364\n--- /dev/null\n+++ b/Documentation/technical/collision-detect.txt\n@@ -0,0 +1,342 @@\n+Hash-Collision Detection using Message Digests\n+=============================\n+\n+Initially Git used a SHA-1 hash as an object ID under the assumption\n+that a hash collision would never occur in practice. While an\n+accidental SHA-1 collision is extremely unlikely, it is possible,\n+although very expensive, to generate multiple files with the same\n+SHA-1 value in under 2^57 operations. With computer performance\n+increasing significantly from one year to the next, Git's assumptions\n+about SHA-1 will eventually not hold in the case of a malicious\n+attempt to damage a project. One should note that just because the\n+probability of a SHA-1 collision occurring accidentally is extremely\n+low does not mean a priori that SHA-1 provides an adequate safety\n+margin for preventing a malicious attempt to damage repositories and a\n+discussion below outlines some of the issues regarding this\n+possibility.\n+\n+While one could modify Git to use SHA-224, SHA-256, SHA-384, or\n+SHA-512 instead of SHA-1, the change would have to support the\n+original format as well (in order to deal with existing Git\n+repositories). While one could convert an existing repository to use\n+the new hash function, this would require rewriting every object,\n+including trees and commits. The outcome would be problematic given\n+the existence of email and documentation that might name commits by\n+their SHA-1 hashes. One should note that Git performs a byte-by-byte\n+check for hash collisions when a pack file is indexed. Unfortunately,\n+during fetch or pull operations, Git tries to avoid copying objects\n+when a peer already has a copy, and this is determined solely on the\n+basis of SHA-1 hashes.\n+\n+The following describes a modification to Git's initial design that is\n+(a) relatively easy to implement, (b) is compatible with and can\n+interoperate with older versions of Git (both the program and the\n+repositories) (c) has a small computational overhead, and (d)\n+increases security substantially, with a goal of detecting hash\n+collisions early and automatically. Because the implementation is\n+relatively simple and the overhead very low, it makes sense to\n+incorporate this change (or some alternative) before the security\n+issue becomes a serious problem.\n+\n+Although Git generally uses that assumption that there will never be a\n+hash collision using SHA-1 in practice, under some circumstances, Git\n+will detect collisions via a byte-by-byte comparison as objects are\n+added to the repository or as pack files are indexed. This test is\n+performed when an index is built (via the Git pack-index command), but\n+a byte-by-byte comparison was deemed too computationally expensive to\n+use in all circumstances: with pack files in particular, simply\n+extracting an object can require not only decompressing it, but\n+handling a series of delta encodings.\n+\n+Collision detection has been extended by computing a message digest of\n+the object's contents (i.e., excluding the Git header). These message\n+digests are stored separately from Git objects and are used for an\n+independent collision test - looking up the message digests using the\n+SHA-1 IDs as a key can be done quickly, and comparing them is fast as\n+well (the digests are aligned to allow 32-bit or 64-bit integer\n+comparisions). This extension is computationally cheap (timing the\n+Git test suite (run via 'make test') showed only a small increase in\n+running time and the extension is backwards compatible with existing\n+Git repositories - if a MD is not available for a SHA-1 value, the\n+implementation reverts to its former behavior and simply compares\n+SHA-1 values. The implementation allows message digests to be easily\n+added.\n+\n+The implementation creates a directory in .git/objects named \"mdsd\",\n+which contains sub-directories and file names identical to the\n+sub-directories in objects used to store loose objects: a two\n+character directory name, with a 38-character file name, the\n+concatenation of which gives the SHA-1 hash for the object. the files\n+in sub-directories of \"mdsd\", however, simply contain a one-byte code\n+indicating the type of message digest, followed by the digest in its\n+binary representation as a sequence of bytes. In addition, for each\n+pack file (.../objects/pack/FILE.pack), there is a corresponding file\n+named .../objects/pack/FILE.mds in addition to\n+.../objects/pack/FILE.idx. The MDS file contains the MDs, stored in\n+the same order as the SHA-1 hashes in .../objects/pack/FILE.idx. The\n+format of the MDS file is described in pack-format.txt.\n+\n+Thus, the directory structure (only part of it is shown) is as\n+follows:\n+\n+ .git---.\n+\t|\n+\t|-objects-.\n+\t|\t |--XX--.\n+\t.\t |\t |--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n+\t.\t |\t .\n+\t.\t |\t .\n+\t\t |\t .\n+\t\t .\n+\t\t .\n+\t\t .\n+\t\t |-mdsd-.\n+\t\t |\t |--XX--.\n+\t\t |\t |\t|--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n+\t\t |\t .\t.\n+\t\t |\t .\t.\n+\t\t |\t .\t.\n+\t\t |\n+\t\t |-pack-.\n+\t\t |\t |--YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY.pack\n+\t\t |\t |--YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY.idx\n+\t\t |\t |--YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY.mds\n+\t\t |\t .\n+\t\t |\t .\n+\t\t |\t .\n+\t\t |\n+\t\t `-info-.\n+\t\t\t .\n+\t\t\t .\n+\n+The mds files are relatively short - an average of N+1 bytes per MD\n+of length N (provided N is a multiple of 4)\n+plus some fixed overhead due to a header and trailer, with the MDs\n+listed in the same order as the SHA-1 values in the matching idx file\n+(a function named nth_packed_object_digest has the same signature as\n+the previously-defined function nth_packed_object_offset, so the\n+procedure to look up the MD value from a pack file is the same).\n+\n+For fetch and push operations, the commands fetch-pack, send-pack,\n+receive-pack, and upload-pack were modified so that various object IDs\n+can have any one of the following formats, with each number\n+represented in hexadecimal:\n+\n+\t\tSHA1\n+\t\tSHA1-MD\n+\n+where SHA1 is the SHA-1 hash of a commit and MD the message digest\n+(prefixed by a code indicating the type of digest) of the commit\n+(uncompressed, not including the Git object header).\n+\n+Both receive-pack and upload-pack send a capability named \"mds-check\"\n+to allow the two longer object IDs. When the MDs are available, the\n+longer formats are used, but are generated only by fetch-pack and\n+send-pack: because of backwards-compatibility constraints,\n+receive-pack and upload-pack cannot determine the capabilities of\n+fetch-pack and send-pack when connected to a remote repository). The\n+collision checks during a fetch, push, or pull command are done by\n+receive-pack and upload pack because send-pack and fetch-pack do not\n+receive their peers' MD values - send-pack and fetch-pack cannot determine\n+their peers' capabilities given the current design.\n+\n+Changes to the Commit Format\n+----------------------------\n+\n+A new header is available, positioned as the last header. It's name is\n+\"digest\" and its value is a hex representation of a message digest in\n+which the first two bytes name the algorithm used to generate the\n+digest and the remaining bytes are the digest itself. This digest is\n+a digest of other digests or SHA-1 values. It starts by including the\n+digests of each object in the commit's tree with the exception of a\n+commit from a submodule - in that case, the SHA-1 value itself is\n+used. The tree is searched depth first, including the tree's root,\n+which provides the first digest. This is followed by the digest for\n+each parent commit in the order listed in the commit. Finally, the\n+digest covers the author, committer, encoding, and the commit message,\n+all excluding the terminating newline character in the header.\n+\n+Note that the digest header complicates any attempt at generate a hash\n+collision for a commit message - if you change a field, you also have\n+to change the digest in a specific way.\n+\n+Configuration\n+-------------\n+\n+There are several variables in the Makefile:\n+\n+ * MDSDB should have the value 0. If an alternative implementation\n+\tis defined, other values will be available.\n+\n+ * MDIGEST_DEFAULT should be defined to explicitly set the\n+\tdefault message digest.\n+\n+ * PACKDB should be defined to turn on the packdb functions.\n+\n+ * PACKDB_TEST should be defined only for debugging. It uses some\n+\tpackdb functions where not necessary to verify that these work\n+\tproperly. Turning this test on decreases performance.\n+\n+ * COMMIT_DIGEST should be defined to add a digest header to\n+\tcommit messages as described above\n+\n+ * COMMIT_DIGEST_TEST should be defined to force commit_tree to\n+\tcompute the digest even when COMMIT_DIGEST is undefined, in\n+\twhich case the digest will be computed but not included in a\n+\tcommit.\n+\n+Key Functions\n+-------------\n+\n+For general use, the functions documented in mdigest.h can extract\n+data from message digests and compare them. The function verify_commit\n+will test a commit to make sure that its digest field matches the\n+repository. The function has_sha1_file_digest allows one to determine\n+if a digest exists and obtain a copy of that digest.\n+\n+To find functions that are used in the implementation (e.g., if changes\n+to the pack-file format become necessary), search for the type\n+mdigest_t or variables width digest in their names (e.g., digestp).\n+\n+\n+Implementation Details\n+----------------------\n+\n+Functions to manipulate the message digest/MD database are declared\n+in the file mdsdb.h. The implementation as described above is in the\n+file objd-mdsdb.c: it is thus easy to change the implementation of how\n+these objects are stored with minimal impact on the rest of the source\n+code. The message digest structure and functions to manipulate it are\n+declared in mdigest.h, with the implementation in mdigest.c.\n+\n+In pack-write.c, there is a new function named write_mds_file with the\n+same function signature as write_idx_file. Both are called in pairs\n+(write_idx_file first) so that the idx file and mds file for the\n+corresponding pack file will always be created.\n+\n+In commit.c, there is a new function that recursively traverses the\n+tree associated with a commit and finds the \"blob\" entries and looks\n+up those entries' message digests in order to compute a message digest\n+of these message digests (which is faster than computing a message\n+digest of all the bytes in the blobs associated with a commit).\n+\n+Various function names signatures in sha1_file.c were changed to take\n+two additional arguments, the first a pointer to an int used as a flag\n+to indicate whether a MD exists, and the second a pointer to a\n+uint32_t containing the MD. For backwards compatibility with\n+previously existing functions, those functions had there names changed\n+by adding \"_extended\" to them, with macros in cache.h defined so that\n+existing code that does not need to obtain a MD would not be\n+changed. There are a few additional functions added to sha1_file.c\n+such as one to determine if there is an MD for a given SHA-1\n+value. Many changes in the rest of Git that result from this simply\n+change the arguments to these functions. As a convention, most such\n+arguments use names like objcrc32, objcrc32p, has_objcrc32 and\n+has_objcrc32p in order to make it easy to find areas of the code\n+implementing hash-collision detection using the git-grep command.\n+\n+A few data structures (notably struct pack_idx_entry and struct\n+packed_git) contain fields used to store has_objcrc32 and objcrc32\n+values or data associated with MDS files. These are used while\n+building new MDS files.\n+\n+Some of the Git commands (count-objects, index-pack, and verify-pack)\n+have additional command-line options related to the MDs and mds\n+files. This makes it possible to explicitly name an mds file being\n+created and to request that various listings show both the MD\n+values in addition to SHA-1 hashes (the MD values are not listed\n+by default in case user-defined scripts assume the current behavior).\n+\n+For C files, changes were made to the following files (compared to\n+commit f56564968 - v1.7.8-rc4) for the initial collision-detection\n+implementation:\n+\n+ * builtin/count-objects.c\n+ * builtin/fetch-pack.c\n+ * builtin/index-pack.c\n+ * builtin/init-db.c\n+ * builtin/pack-objects.c\n+ * builtin/pack-redundant.c\n+ * builtin/prune-packed.c\n+ * builtin/prune.c\n+ * builtin/receive-pack.c\n+ * builtin/send-pack.c\n+ * builtin/verify-pack.c\n+ * commit.c\n+ * environment.c\n+ * fast-import.c\n+ * gdbm-packdb.c (new file)\n+ * git.c\n+ * hex.c\n+ * http.c\n+ * mdigest.c (new file)\n+ * objd-mdsdb.c (new file)\n+ * pack-write.c\n+ * sha1_file.c\n+ * upload-pack.c\n+\n+The other files had changes that reflected changes to function\n+signatures.\n+\n+The header files that were modified are\n+\n+ * cache.h\n+ * commit.h\n+ * mdigest.h (new file)\n+ * mdsdb.h (new file)\n+ * pack.h\n+ * packdb.h (new file)\n+\n+where the changes are mostly new function declarations, a few macros\n+for backwards-compatibility, and a few additional fields in some\n+data structures.\n+\n+Minor changes were made to the test suite: t0000-basic.sh,\n+t5300-pack-object.sh, t5304-prune.sh, t5500-fetch-pack.sh, and\n+t5510-fetch.sh.\n+\n+The packdb functions are conditionally compiled and by default are not\n+used. When used, these use GDBM to store MDs for SHA-1 hashes in\n+cases in which the hash was not available - in this case the hash will\n+be recomputed and stored for future use. Testing indicates that\n+packdb is not needed. It may be worth turning on during debugging to\n+verify if a problem is discovered involving a missing MD. (As an\n+aside, the packdb code is based on a test to see if GDBM would be\n+efficient enough to store the MD values in general, thus avoiding\n+the need to create \"mds\" files and reducing the number of files in the\n+\"mdsd\" directory, but it turned out that performance was not\n+acceptable.)\n+\n+Security-Issue Details\n+----------------------\n+\n+Without hash-collision detection, Git has a possible risk of data\n+corruption due to the obvious hash-collision vulnerability, so the\n+issue is really whether a usable vulnerability exists. In the case\n+of a single shared repository (one common repository shared by\n+multiple developers), this risk is mitigated by Git's rule that\n+an existing entry is never overridden. The situation is more complex\n+when multiple repositories are used, as a race condition may exist.\n+Also, the risk depends on whether or not developers exchange source\n+files by some out-of-band mechanism (e.g., email) - when programming\n+in Java, for example, it is customary to use the javadocs program to\n+create API documentation from stylized comments in source files. A\n+programmer might send a peer a copy of a source file and to review\n+and correct the java-doc comments, providing an opporunity for the\n+second developer to insert a modified file into the respository. The\n+first developer would presumably check that the source code has not\n+changed (an automated test for this might use the java compiler's\n+\"-g:none\" option so that line-number data does not appear in the object\n+file), and review the comments, but would not care about formatting\n+(location of line breaks, etc., as the javadocs program generates HTML).\n+\n+In any event, recent research has shown that SHA-1 collisions can be\n+found in 2^63 operations or less. While one result claimed 2^53\n+operations, the paper claiming that value was withdrawn from\n+publication due to an error in the estimate. Another result claimed a\n+complexity of between 2^51 and 2^57 operations, and still another\n+claimed a complexity of 2^57.5 SHA-1 computations. A summary is\n+available at\n+.\n+This is within or close to the number of computations that can be\n+managed by a well-funded organization.\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex 1803e64..a2aad5f 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -158,3 +158,50 @@ Pack file entry: <+\n corresponding packfile.\n \n 20-byte SHA1-checksum of all of the above.\n+\n+\n+= pack-*.mds files contain message digests for objects. The digests\n+ are stored in the same order as the sha-1 values in the matching idx\n+ file. These files have the following format:\n+\n+ - A 6-byte magic number consisting the the characters \"PKMDS\" followed\n+ by a NULL character (0).\n+\n+ - A one-byte version number (= 1)\n+\n+ - A one-byte field-length value for message digest fields, in units\n+ of 4-byte words. (The length of the message digest fields in bytes\n+ is denoted as wbsize below)\n+\n+ - A set of blocks, each of which contains 4 entries encoded as follows:\n+\n+ * four one-byte fields (wcode fields), one per entry, for which\n+\ta zero value indicates that a matching entry does not exist\n+\tand a non-zero value indicates the type of message digest\n+\tencoded as follows:\n+\n+\t + 1 for a CRC (used as a trivial case for performance testing)\n+\n+\t + 5 for SHA-1\n+\n+\t + 8 for SHA-256\n+\n+\t + 16 for SHA-512\n+\n+ * 4 wbsize-byte fields, each containing a message digest (by\n+\tconvention which must be all NULL characters if the MD does\n+\tnot exist). For each field, the data it contains should start\n+\tat the first byte, padded with NULL characters if the field is\n+\tlonger than the digest it stores.\n+\n+ For the set of all blocks, the nth one-byte field and the nth\n+ wcode field store the values for the nth entry in the\n+ file. The format ensures that each message digest starts on a\n+ 32-bit boundary, allowing 32-bit integer operations to be used in\n+ copying or comparing values.\n+\n+ - A 20 byte SHA-1 hash of the SHA-1 hashes naming the objects whose\n+ message digests are being stored, in the same order as they\n+ appear in the corresponding idx file.\n+\n+ - A 20 byte SHA-1 hash of all of the above.\n-- \n1.7.1\n"}]}