{"thread":{"id":"29049","subject":"[PATCH 2/3] Add documentation for fast hash collision detection","startedAt":"2011-11-30T06:12:39Z","lastAt":"2011-11-30T06:12:39Z","messageCount":1,"participants":["Bill Zaumen"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"180133","messageId":"1322633559.1728.331.camel@yos","threadId":"29049","inReplyTo":null,"subject":"[PATCH 2/3] Add documentation for fast hash collision detection","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-11-30T06:12:39Z","receivedAt":"2011-11-30T06:12:39Z","isPatch":true,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"The documentation added is technical documentation describing\nhow fast hash collision detection operates and changes to\nseveral git commands (a few new command-line arguments, mostly).\n\nNote: the change to the implementation is in the child of\nthis commit.\n\nSigned-off-by: Bill Zaumen \n---\n Documentation/git-count-objects.txt | 12 +-\n Documentation/git-index-pack.txt | 16 +-\n Documentation/git-verify-pack.txt | 23 ++\n Documentation/technical/collision-detect.txt | 385 ++++++++++++++++++++++++++\n Documentation/technical/pack-format.txt | 40 +++\n 5 files changed, 471 insertions(+), 5 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..3285fae 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\ndiff --git a/Documentation/git-verify-pack.txt b/Documentation/git-verify-pack.txt\nindex cd23076..e81c514 100644\n--- a/Documentation/git-verify-pack.txt\n+++ b/Documentation/git-verify-pack.txt\n@@ -33,6 +33,15 @@ 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.\n+\n \\--::\n \tDo not interpret any more arguments as options.\n \n@@ -48,6 +57,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..0d33da8\n--- /dev/null\n+++ b/Documentation/technical/collision-detect.txt\n@@ -0,0 +1,385 @@\n+Fast Hash-Collision Detection\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 or\n+CRC of the object's contents (i.e., excluding the Git header). These\n+message digests are stored separately from Git objects and are used\n+for an independent collision test - looking up the message digests or\n+CRCs using the SHA-1 IDs as a key can be done quickly, and comparing\n+them is fast as well (a single unsigned-integer comparison for a\n+32-bit CRC). Assuming statistical independence in the CRC case, the\n+changes of an undetected SHA-1 collision, should one occur, is 1 in\n+2^32. This extension is computationally cheap (timing the Git test\n+suite (run via 'make test') showed only a small increase in running\n+time and the extension is backwards compatible with existing Git\n+repositories - if a CRC is not available for a SHA-1 value, the\n+implementation reverts to its former behavior and simply compares\n+SHA-1 values. The CRC can, of course, be easily replaced with a\n+SHA-256 or SHA-512 digest to reduce the chances of an undetected SHA-1\n+collision to nearly zero. For that reason, in the following we will\n+use the terms MD (Message Digest) and CRC interchangeably.\n+\n+The implementation creates a directory in .git/objects named \"crcs\",\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 \"crcs\", however, simply contain 32-bit CRCs\n+stored in network byte order. In addition, for each pack file\n+(.../objects/pack/FILE.pack), there is a corresponding file named\n+.../objects/pack/FILE.mds in addition to .../objects/pack/FILE.idx.\n+The MDS file contains the CRCs, stored in the same order as the SHA-1\n+hashes in .../objects/pack/FILE.idx. The format of the MDS file is\n+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 |-crcs-.\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 5 bytes per CRC\n+plus some fixed overhead due to a header and trailer, with the CRCs\n+listed in the same order as the SHA-1 values in the matching idx file\n+(a function named nth_packed_object_objcrc32 has the same signature as\n+the previously-defined function nth_packed_object_offset, so the\n+procedure to look up the MD/CRC 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+\t\tSHA1-MD-BlobMD\n+\n+where SHA1 is the SHA-1 hash of a commit, MD is the 32-bit CRC of the\n+commit (uncompressed, not including the Git object header), and BlobMD\n+is a CRC of the CRCs for each blob found by traversing the commit's\n+tree using a depth-first search, with blobs processed in the order\n+they appear in the trees (this is a relatively fast operation because\n+the CRCs of each blob are stored in the repository).\n+\n+Both receive-pack and upload-pack send a capability named \"mds-check\"\n+to allow the two longer object IDs. When the CRCs 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).\n+While the message digests associated with each object are computed\n+once and stored, the \"BlobMD\" ones are computed each time - the\n+\"BlobMD\" ones are only used by the Git commands fetch-pack,\n+upload-pack, send-pack, and receive-pack. In each case, a\n+hash-collision check is performed only if the message digest used is\n+available. The collision checks during a fetch, push, or pull command\n+are done by receive-pack and upload pack because send-pack and\n+fetch-pack do not receive their peers' MD and BlobMD values.\n+\n+\n+Implementation Details\n+----------------------\n+\n+Functions to manipulate the message digest/CRC database are declared\n+in the file crcdb.h. The implementation as described above is in the\n+file objd-crcdb.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.\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/CRC exists, and the second a pointer to a\n+uint32_t containing the MD/CRC (a CRC currently). For backwards\n+compatibility with previously existing functions, those functions had\n+there names changed by adding \"_extended\" to them, with macros in\n+cache.h defined so that existing code that does not need to obtain a\n+MD/CRC would not be changed. There are a few additional functions\n+added to sha1_file.c such as one to determine if there is an MD/CRC\n+for a given SHA-1 value. Many changes in the rest of Git that result\n+from this simply change the arguments to these functions. As a\n+convention, most such arguments use names like objcrc32, objcrc32p,\n+has_objcrc32 and has_objcrc32p in order to make it easy to find areas\n+of the code implementing hash-collision detection using the git-grep\n+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 MD/CRCs 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/CRC\n+values in addition to SHA-1 hashes (the MD/CRC 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 017d1e13) for the initial collision-detection 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+ * objd-crcdb.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+ * crcdb.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 CRCs 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/CRC. (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/CRC values in general, thus avoiding\n+the need to create \"mds\" files and reducing the number of files in the\n+\"crcs\" 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 higher risk of data\n+corruption due to the obvious hash-collision vulnerability, so the\n+issue is really whether a usable vulnerability exists. Recent research\n+has shown that SHA-1 collisions can be found in 2^63 operations or\n+less. While one result claimed 2^53 operations, the paper claiming\n+that value was withdrawn from publication due to an error in the\n+estimate. Another result claimed a complexity of between 2^51 and 2^57\n+operations, and still another claimed a complexity of 2^57.5 SHA-1\n+computations. A summary is available at\n+. Given the\n+number of recent attacks, possibly by governments or large-scale\n+criminal enterprises\n+(,\n+,\n+),\n+which include botnets with an estimated 30 million computers, there is\n+reason for some concern: while generating a SHA-1 collision for\n+purposes of damaging a Git repository is extremely expensive\n+computationally, it is possibly within reach of very well funded\n+organizations. 2^32 operations, even if the operations are as\n+expensive as computing a SHA-1 hash of a modest source-code file, can\n+be performed in a reasonably short period of time on the type of\n+hardware widely used in desktop or laptop computers at present. With\n+sufficient parallelism, 30 million personal computers sufficient for\n+playing the latest video games could perform 2^56 operations in a\n+reasonable time.\n+\n+The security implications depend on how Git is used. In the simplest\n+case in which a single, shared repository is used by a number of\n+developers, with source code only shared though this repository, the\n+problems are minimal - Git will not allow one to insert an object\n+whose SHA-1 hash matches that of an existing object. Since an\n+attacker would not know the SHA-1 hash until the correct object is\n+already in the shared repository, all an attacker would succeed in\n+doing is to create some confusion in his/her private repository and\n+working copy (but note that some of the assumptions break down if\n+developers email source files between themselves rather than transferring\n+everything via a Git repository).\n+developers, with source code only shared though this repository, the\n+problems are minimal - Git will not allow one to insert an object\n+whose SHA-1 hash matches that of an existing object. Since an\n+attacker would not know the SHA-1 hash until the correct object is\n+already in the shared repository, all an attacker would succeed in\n+doing is to create some confusion in his/her private repository and\n+working copy (but note that some of the assumptions break down if\n+developers email source files between themselves rather than transferring\n+everything via a Git repository).\n+\n+In other cases, however, there could be an issue if a SHA-1 collision\n+can be created quickly enough. As an example, suppose one is using the\n+\"Integration-manager workflow\" described in \"Pro Git\" (see\n+) with a \"blessed repository\" BR\n+and two public developer repositories DPR1 and DPR2. Suppose a\n+developer puts a legitimate change to the code into DPR2. Another\n+developer with read access to DPR2 and write access to DPR1\n+immediately fetches this commit, and replaces one file with a modified\n+version of the same size that has the same SHA-1 value, and then puts\n+the commit into DPR1 (the change may be a trivial one designed to\n+introduce an obscure buffer overflow error that can be exploited and\n+may not stand out in a code review). At this point DPR1 and DPR2 have\n+identical commits (i.e., the same commit object) but with one file\n+modified. No local test on either DPR1 or DPR2 will uncover a\n+discrepancy based on SHA-1 values, object contents, and digital\n+signatures for commits. Further assume that both developers send an\n+email to the \"integration manager\" notifying him/her of the changes.\n+\n+Now suppose the above changes occurred late on a Friday afternoon and\n+over a weekend. On the next Monday morning, the \"integration manager\"\n+reads the emails and pulls changes from DPR1 and then DPR2. Once a\n+'fetch' from DPR1 is complete, a subsequent fetch from DBR2 will not\n+transfer any data related to the commit, as the integration manager's\n+repository already has a commit with the matching SHA-1 value. A\n+modified copy will have been introduced into the system, and the\n+developers using DPR2 may never notice the difference - as they will\n+pull from DPR2 more often than BR, they will most likely have the\n+correct files and the commit in their local repositories and the\n+transfer protocol will avoid sending the commit if it is already\n+available. Furthermore, if the modified file introduces a hard-to-find\n+buffer overflow testing may not uncover the problem.\n+\n+If the file in question is modified again, and a thin pack is used in\n+a fetch so that the change is delta-encoded, the SHA-1 hashes may\n+differ after de-deltafication, but such a change might not be\n+introduced before a release. While obtaining a different SHA-1\n+hash than expected would be detected, the error would be a corrupted\n+repository - a missing SHA-1 value in the tree associated with a commit.\n+It would take some effort to figure out what went wrong - what\n+happens depends on the state of both the client and server when a\n+git-fetch operation runs.\n+\n+As a justification for the scenarios just described, one can use MD5\n+as a model: http://www.mscs.dal.ca/~selinger/md5collision/ gives the\n+following two 128-byte sequences (expressed in hexadecimal) as ones\n+with the same MD5 hash:\n+\n+d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89\n+55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b\n+d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0\n+e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70\n+\n+and\n+\n+d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89\n+55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b\n+d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0\n+e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70\n+\n+These can be used for test purposes. If you change the first 16 bytes\n+of both sequences to the same new value, before the point where the\n+files differ, you will get different MD5 hash values. If you append\n+the same text to both files, the MD5 values of the modified files are\n+equal (and, of course, different from the previous value) but\n+fortunately Git includes the length of an object's contents in the\n+object's header, and the SHA-1 hash includes the header). In most\n+cases, whever a file is modified during software development, the\n+file's length will change. This causes a change early enough in the\n+object so that applying the same patch to two different files that\n+have the same SHA-1 value will typically result in two files with\n+different SHA-1 values. So, the result of a hash collision when\n+multiple remote repositories are used would initially be different\n+versions of the same file for the same commit in different\n+repositories, possibly followed by some of the repositories being\n+corrupted as one of these files is modified, depending on the state\n+of each server and client when a fetch or pull operation is run.\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex 1803e64..4dfaf92 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -158,3 +158,43 @@ 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 (CRCs\n+ initially, with other options possibly added at a later date such as\n+ SHA-256). The digests are stored in the same order as the sha-1 values\n+ in the matching idx 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 of\n+ 4-byte words, with the legal value being 1. The length of the message\n+ digest fields in bytes is denoted as wsize below).\n+\n+ - A set of blocks, each of which contains 4 entries encoded as follows:\n+\n+ * four one-byte fields, one per entry, for which a zero value\n+\tindicates that a matching entry does not exist and for which a\n+\tvalue of 1 indicates that the field contains a 32-bit CRC stored\n+\tin network byte order.\n+\n+ * 4 wsize-byte fields, one per entry, each containing a CRC\n+\t(by conventionwhich should be 0 if the CRC does not exist).\n+\tFor each field, the data it contains should start at the first\n+\tbyte, padded with NULL characters if the field is longer than\n+\tthe digest it stores.\n+\n+ For the set of all blocks, the nth one-byte field and the nth 4-byte\n+ field store the values for the nth entry in the file. The format\n+ ensures that each message digest starts on a 32-bit boundary,\n+ allowing 32-bit integer operations to be used in copying or\n+ 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"}]}