Git hash function transition============================ Objective---------Migrate Git from SHA-1 to a stronger hash function. Background----------At its core, the Git version control system is a content addressablefilesystem. It uses the SHA-1 hash function to name content. Forexample, files, directories, and revisions are referred to by hashvalues unlike in other traditional version control systems where filesor versions are referred to via sequential numbers. The use of a hashfunction to address its content delivers a few advantages: * Integrity checking is easy. Bit flips, for example, are easily  detected, as the hash of corrupted content does not match its name.* Lookup of objects is fast. Using a cryptographically secure hash function brings additionaladvantages: * Object names can be signed and third parties can trust the hash to  address the signed object and all objects it references.* Communication using Git protocol and out of band communication  methods have a short reliable string that can be used to reliably  address stored content. Over time some flaws in SHA-1 have been discovered by securityresearchers. On 23 February 2017 the SHAttered attack(https://shattered.io) demonstrated a practical SHA-1 hash collision. Git v2.13.0 and later subsequently moved to a hardened SHA-1implementation by default, which isn't vulnerable to the SHAtteredattack. Thus Git has in effect already migrated to a new hash that isn't SHA-1and doesn't share its vulnerabilities, its new hash function justhappens to produce exactly the same output for all known inputs,except two PDFs published by the SHAttered researchers, and the newimplementation (written by those researchers) claims to detect futurecryptanalytic collision attacks. Regardless, it's considered prudent to move past any variant of SHA-1to a new hash. There's no guarantee that future attacks on SHA-1 won'tbe published in the future, and those attacks may not have viablemitigations. If SHA-1 and its variants were to be truly broken, Git's hash functioncould not be considered cryptographically secure any more. This wouldimpact the communication of hash values because we could not trustthat a given hash value represented the known good version of contentthat the speaker intended. SHA-1 still possesses the other properties such as fast object lookupand safe error checking, but other hash functions are equally suitablethat are believed to be cryptographically secure. Goals-----1. The transition to SHA-256 can be done one local repository at a time.   a. Requiring no action by any other party.   b. A SHA-256 repository can communicate with SHA-1 Git servers      (push/fetch).   c. Users can use SHA-1 and SHA-256 identifiers for objects      interchangeably (see "Object names on the command line", below).   d. New signed objects make use of a stronger hash function than      SHA-1 for their security guarantees.2. Allow a complete transition away from SHA-1.   a. Local metadata for SHA-1 compatibility can be removed from a      repository if compatibility with SHA-1 is no longer needed.3. Maintainability throughout the process.   a. The object format is kept simple and consistent.   b. Creation of a generalized repository conversion tool. Non-Goals---------1. Add SHA-256 support to Git protocol. This is valuable and the   logical next step but it is out of scope for this initial design.2. Transparently improving the security of existing SHA-1 signed   objects.3. Intermixing objects using multiple hash functions in a single   repository.4. Taking the opportunity to fix other bugs in Git's formats and   protocols.5. Shallow clones and fetches into a SHA-256 repository. (This will   change when we add SHA-256 support to Git protocol.)6. Skip fetching some submodules of a project into a SHA-256   repository. (This also depends on SHA-256 support in Git   protocol.) Overview--------We introduce a new repository format extension. Repositories with thisextension enabled use SHA-256 instead of SHA-1 to name their objects.This affects both object names and object content --- both the namesof objects and all references to other objects within an object areswitched to the new hash function. SHA-256 repositories cannot be read by older versions of Git. Alongside the packfile, a SHA-256 repository stores a bidirectionalmapping between SHA-256 and SHA-1 object names. The mapping is generatedlocally and can be verified using "git fsck". Object lookups use thismapping to allow naming objects using either their SHA-1 and SHA-256 namesinterchangeably. "git cat-file" and "git hash-object" gain options to display an objectin its sha1 form and write an object given its sha1 form. Thisrequires all objects referenced by that object to be present in theobject database so that they can be named using the appropriate name(using the bidirectional hash mapping). Fetches from a SHA-1 based server convert the fetched objects intoSHA-256 form and record the mapping in the bidirectional mapping table(see below for details). Pushes to a SHA-1 based server convert theobjects being pushed into sha1 form so the server does not have to beaware of the hash function the client is using. Detailed Design---------------Repository format extension~~~~~~~~~~~~~~~~~~~~~~~~~~~A SHA-256 repository uses repository format version `1` (seeDocumentation/technical/repository-version.txt) with extensions`objectFormat` and `compatObjectFormat`: 	[core]		repositoryFormatVersion = 1	[extensions]		objectFormat = sha256		compatObjectFormat = sha1 The combination of setting `core.repositoryFormatVersion=1` andpopulating `extensions.*` ensures that all versions of Git later than`v0.99.9l` will die instead of trying to operate on the SHA-256repository, instead producing an error message. 	# Between v0.99.9l and v2.7.0	$ git status	fatal: Expected git repo version <= 0, found 1	# After v2.7.0	$ git status	fatal: unknown repository extensions found:		objectformat		compatobjectformat See the "Transition plan" section below for more details on theserepository extensions. Object names~~~~~~~~~~~~Objects can be named by their 40 hexadecimal digit sha1-name or 64hexadecimal digit sha256-name, plus names derived from those (seegitrevisions(7)). The sha1-name of an object is the SHA-1 of the concatenation of itstype, length, a nul byte, and the object's sha1-content. This is thetraditional <sha1> used in Git to name objects. The sha256-name of an object is the SHA-256 of the concatenation of itstype, length, a nul byte, and the object's sha256-content. Object format~~~~~~~~~~~~~The content as a byte sequence of a tag, commit, or tree object namedby sha1 and sha256 differ because an object named by sha256-name refers toother objects by their sha256-names and an object named by sha1-namerefers to other objects by their sha1-names. The sha256-content of an object is the same as its sha1-content, exceptthat objects referenced by the object are named using their sha256-namesinstead of sha1-names. Because a blob object does not refer to anyother object, its sha1-content and sha256-content are the same. The format allows round-trip conversion between sha256-content andsha1-content. Object storage~~~~~~~~~~~~~~Loose objects use zlib compression and packed objects use the packedformat described in Documentation/technical/pack-format.txt, just liketoday. The content that is compressed and stored uses sha256-contentinstead of sha1-content. Pack index~~~~~~~~~~Pack index (.idx) files use a new v3 format that supports multiplehash functions. They have the following format (all integers are innetwork byte order): - A header appears at the beginning and consists of the following:  - The 4-byte pack index signature: '\377t0c'  - 4-byte version number: 3  - 4-byte length of the header section, including the signature and    version number  - 4-byte number of objects contained in the pack  - 4-byte number of object formats in this pack index: 2  - For each object format:    - 4-byte format identifier (e.g., 'sha1' for SHA-1)    - 4-byte length in bytes of shortened object names. This is the      shortest possible length needed to make names in the shortened      object name table unambiguous.    - 4-byte integer, recording where tables relating to this format      are stored in this index file, as an offset from the beginning.  - 4-byte offset to the trailer from the beginning of this file.  - Zero or more additional key/value pairs (4-byte key, 4-byte    value). Only one key is supported: 'PSRC'. See the "Loose objects    and unreachable objects" section for supported values and how this    is used.  All other keys are reserved. Readers must ignore    unrecognized keys.- Zero or more NUL bytes. This can optionally be used to improve the  alignment of the full object name table below.- Tables for the first object format:  - A sorted table of shortened object names.  These are prefixes of    the names of all objects in this pack file, packed together    without offset values to reduce the cache footprint of the binary    search for a specific object name.   - A table of full object names in pack order. This allows resolving    a reference to "the nth object in the pack file" (from a    reachability bitmap or from the next table of another object    format) to its object name.   - A table of 4-byte values mapping object name order to pack order.    For an object in the table of sorted shortened object names, the    value at the corresponding index in this table is the index in the    previous table for that same object.     This can be used to look up the object in reachability bitmaps or    to look up its name in another object format.   - A table of 4-byte CRC32 values of the packed object data, in the    order that the objects appear in the pack file. This is to allow    compressed data to be copied directly from pack to pack during    repacking without undetected data corruption.   - A table of 4-byte offset values. For an object in the table of    sorted shortened object names, the value at the corresponding    index in this table indicates where that object can be found in    the pack file. These are usually 31-bit pack file offsets, but    large offsets are encoded as an index into the next table with the    most significant bit set.   - A table of 8-byte offset entries (empty for pack files less than    2 GiB). Pack files are organized with heavily used objects toward    the front, so most object references should not need to refer to    this table.- Zero or more NUL bytes.- Tables for the second object format, with the same layout as above,  up to and not including the table of CRC32 values.- Zero or more NUL bytes.- The trailer consists of the following:  - A copy of the 20-byte SHA-256 checksum at the end of the    corresponding packfile.   - 20-byte SHA-256 checksum of all of the above. Loose object index~~~~~~~~~~~~~~~~~~A new file $GIT_OBJECT_DIR/loose-object-idx contains information aboutall loose objects. Its format is   # loose-object-idx  (sha256-name SP sha1-name LF)* where the object names are in hexadecimal format. The file is notsorted. The loose object index is protected against concurrent writes by alock file $GIT_OBJECT_DIR/loose-object-idx.lock. To add a new looseobject: 1. Write the loose object to a temporary file, like today.2. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the lock.3. Rename the loose object into place.4. Open loose-object-idx with O_APPEND and write the new object5. Unlink loose-object-idx.lock to release the lock. To remove entries (e.g. in "git pack-refs" or "git-prune"): 1. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the   lock.2. Write the new content to loose-object-idx.lock.3. Unlink any loose objects being removed.4. Rename to replace loose-object-idx, releasing the lock. Translation table~~~~~~~~~~~~~~~~~The index files support a bidirectional mapping between sha1-namesand sha256-names. The lookup proceeds similarly to ordinary objectlookups. For example, to convert a sha1-name to a sha256-name:  1. Look for the object in idx files. If a match is present in the    idx's sorted list of truncated sha1-names, then:    a. Read the corresponding entry in the sha1-name order to pack       name order mapping.    b. Read the corresponding entry in the full sha1-name table to       verify we found the right object. If it is, then    c. Read the corresponding entry in the full sha256-name table.       That is the object's sha256-name. 2. Check for a loose object. Read lines from loose-object-idx until    we find a match. Step (1) takes the same amount of time as an ordinary object lookup:O(number of packs * log(objects per pack)). Step (2) takes O(number ofloose objects) time. To maintain good performance it will be necessaryto keep the number of loose objects low. See the "Loose objects andunreachable objects" section below for more details. Since all operations that make new objects (e.g., "git commit") addthe new objects to the corresponding index, this mapping is possiblefor all objects in the object store. Reading an object's sha1-content~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~The sha1-content of an object can be read by converting all sha256-namesits sha256-content references to sha1-names using the translation table. Fetch~~~~~Fetching from a SHA-1 based server requires translating between SHA-1and SHA-256 based representations on the fly. SHA-1s named in the ref advertisement that are present on the clientcan be translated to SHA-256 and looked up as local objects using thetranslation table. Negotiation proceeds as today. Any "have"s generated locally areconverted to SHA-1 before being sent to the server, and SHA-1smentioned by the server are converted to SHA-256 when looking them uplocally. After negotiation, the server sends a packfile containing therequested objects. We convert the packfile to SHA-256 format usingthe following steps: 1. index-pack: inflate each object in the packfile and compute its   SHA-1. Objects can contain deltas in OBJ_REF_DELTA format against   objects the client has locally. These objects can be looked up   using the translation table and their sha1-content read as   described above to resolve the deltas.2. topological sort: starting at the "want"s from the negotiation   phase, walk through objects in the pack and emit a list of them,   excluding blobs, in reverse topologically sorted order, with each   object coming later in the list than all objects it references.   (This list only contains objects reachable from the "wants". If the   pack from the server contained additional extraneous objects, then   they will be discarded.)3. convert to sha256: open a new (sha256) packfile. Read the topologically   sorted list just generated. For each object, inflate its   sha1-content, convert to sha256-content, and write it to the sha256   pack. Record the new sha1<->sha256 mapping entry for use in the idx.4. sort: reorder entries in the new pack to match the order of objects   in the pack the server generated and include blobs. Write a sha256 idx   file5. clean up: remove the SHA-1 based pack file, index, and   topologically sorted list obtained from the server in steps 1   and 2. Step 3 requires every object referenced by the new object to be in thetranslation table. This is why the topological sort step is necessary. As an optimization, step 1 could write a file describing what non-blobobjects each object it has inflated from the packfile references. Thismakes the topological sort in step 2 possible without inflating theobjects in the packfile for a second time. The objects need to beinflated again in step 3, for a total of two inflations. Step 4 is probably necessary for good read-time performance. "gitpack-objects" on the server optimizes the pack file for good datalocality (see Documentation/technical/pack-heuristics.txt). Details of this process are likely to change. It will take someexperimenting to get this to perform well. Push~~~~Push is simpler than fetch because the objects referenced by thepushed objects are already in the translation table. The sha1-contentof each object being pushed can be read as described in the "Readingan object's sha1-content" section to generate the pack written by gitsend-pack. Signed Commits~~~~~~~~~~~~~~We add a new field "gpgsig-sha256" to the commit object format to allowsigning commits without relying on SHA-1. It is similar to theexisting "gpgsig" field. Its signed payload is the sha256-content of thecommit object with any "gpgsig" and "gpgsig-sha256" fields removed. This means commits can be signed1. using SHA-1 only, as in existing signed commit objects2. using both SHA-1 and SHA-256, by using both gpgsig-sha256 and gpgsig   fields.3. using only SHA-256, by only using the gpgsig-sha256 field. Old versions of "git verify-commit" can verify the gpgsig signature incases (1) and (2) without modifications and view case (3) as anordinary unsigned commit. Signed Tags~~~~~~~~~~~We add a new field "gpgsig-sha256" to the tag object format to allowsigning tags without relying on SHA-1. Its signed payload is thesha256-content of the tag with its gpgsig-sha256 field and "-----BEGIN PGPSIGNATURE-----" delimited in-body signature removed. This means tags can be signed1. using SHA-1 only, as in existing signed tag objects2. using both SHA-1 and SHA-256, by using gpgsig-sha256 and an in-body   signature.3. using only SHA-256, by only using the gpgsig-sha256 field. Mergetag embedding~~~~~~~~~~~~~~~~~~The mergetag field in the sha1-content of a commit contains thesha1-content of a tag that was merged by that commit. The mergetag field in the sha256-content of the same commit contains thesha256-content of the same tag. Submodules~~~~~~~~~~To convert recorded submodule pointers, you need to have the convertedsubmodule repository in place. The translation table of the submodulecan be used to look up the new hash. Loose objects and unreachable objects~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Fast lookups in the loose-object-idx require that the number of looseobjects not grow too high. "git gc --auto" currently waits for there to be 6700 loose objectspresent before consolidating them into a packfile. We will need tomeasure to find a more appropriate threshold for it to use. "git gc --auto" currently waits for there to be 50 packs presentbefore combining packfiles. Packing loose objects more aggressivelymay cause the number of pack files to grow too quickly. This can bemitigated by using a strategy similar to Martin Fick's exponentialrolling garbage collection script:https://gerrit-review.googlesource.com/c/gerrit/+/35215 "git gc" currently expels any unreachable objects it encounters inpack files to loose objects in an attempt to prevent a race whenpruning them (in case another process is simultaneously writing a newobject that refers to the about-to-be-deleted object). This leads toan explosion in the number of loose objects present and disk spaceusage due to the objects in delta form being replaced with independentloose objects.  Worse, the race is still present for loose objects. Instead, "git gc" will need to move unreachable objects to a newpackfile marked as UNREACHABLE_GARBAGE (using the PSRC field; seebelow). To avoid the race when writing new objects referring to anabout-to-be-deleted object, code paths that write new objects willneed to copy any objects from UNREACHABLE_GARBAGE packs that theyrefer to new, non-UNREACHABLE_GARBAGE packs (or loose objects).UNREACHABLE_GARBAGE are then safe to delete if their creation time (asindicated by the file's mtime) is long enough ago. To avoid a proliferation of UNREACHABLE_GARBAGE packs, they can becombined under certain circumstances. If "gc.garbageTtl" is set togreater than one day, then packs created within a single calendar day,UTC, can be coalesced together. The resulting packfile would have anmtime before midnight on that day, so this makes the effective maximumttl the garbageTtl + 1 day. If "gc.garbageTtl" is less than one day,then we divide the calendar day into intervals one-third of that ttlin duration. Packs created within the same interval can be coalescedtogether. The resulting packfile would have an mtime before the end ofthe interval, so this makes the effective maximum ttl equal to thegarbageTtl * 4/3. This rule comes from Thirumala Reddy Mutchukota's JGit changehttps://git.eclipse.org/r/90465. The UNREACHABLE_GARBAGE setting goes in the PSRC field of the packindex. More generally, that field indicates where a pack came from:  - 1 (PACK_SOURCE_RECEIVE) for a pack received over the network - 2 (PACK_SOURCE_AUTO) for a pack created by a lightweight   "gc --auto" operation - 3 (PACK_SOURCE_GC) for a pack created by a full gc - 4 (PACK_SOURCE_UNREACHABLE_GARBAGE) for potential garbage   discovered by gc - 5 (PACK_SOURCE_INSERT) for locally created objects that were   written directly to a pack file, e.g. from "git add ." This information can be useful for debugging and for "gc --auto" tomake appropriate choices about which packs to coalesce. Caveats-------Invalid objects~~~~~~~~~~~~~~~The conversion from sha1-content to sha256-content retains anybrokenness in the original object (e.g., tree entry modes encoded withleading 0, tree objects whose paths are not sorted correctly, andcommit objects without an author or committer). This is a deliberate

Lines 1–500 of 827. Load more