path: root/Documentation/technical/hash-function-transition.txt

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 addressable
filesystem. It uses the SHA-1 hash function to name content. For
example, files, directories, and revisions are referred to by hash
values unlike in other traditional version control systems where files
or versions are referred to via sequential numbers. The use of a hash
function 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 additional
advantages:

* 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 security
researchers. 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-1
implementation by default, which isn't vulnerable to the SHAttered
attack.

Thus Git has in effect already migrated to a new hash that isn't SHA-1
and doesn't share its vulnerabilities, its new hash function just
happens to produce exactly the same output for all known inputs,
except two PDFs published by the SHAttered researchers, and the new
implementation (written by those researchers) claims to detect future
cryptanalytic collision attacks.

Regardless, it's considered prudent to move past any variant of SHA-1
to a new hash. There's no guarantee that future attacks on SHA-1 won't
be published in the future, and those attacks may not have viable
mitigations.

If SHA-1 and its variants were to be truly broken, Git's hash function
could not be considered cryptographically secure any more. This would
impact the communication of hash values because we could not trust
that a given hash value represented the known good version of content
that the speaker intended.

SHA-1 still possesses the other properties such as fast object lookup
and safe error checking, but other hash functions are equally suitable
that are believed to be cryptographically secure.

Goals
-----
Where NewHash is a strong 256-bit hash function to replace SHA-1 (see
"Selection of a New Hash", below):

1. The transition to NewHash can be done one local repository at a time.
   a. Requiring no action by any other party.
   b. A NewHash repository can communicate with SHA-1 Git servers
      (push/fetch).
   c. Users can use SHA-1 and NewHash 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 NewHash 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 NewHash repository. (This will
   change when we add NewHash support to Git protocol.)
6. Skip fetching some submodules of a project into a NewHash
   repository. (This also depends on NewHash support in Git
   protocol.)

Overview
--------
We introduce a new repository format extension. Repositories with this
extension enabled use NewHash instead of SHA-1 to name their objects.
This affects both object names and object content --- both the names
of objects and all references to other objects within an object are
switched to the new hash function.

NewHash repositories cannot be read by older versions of Git.

Alongside the packfile, a NewHash repository stores a bidirectional
mapping between NewHash and SHA-1 object names. The mapping is generated
locally and can be verified using "git fsck". Object lookups use this
mapping to allow naming objects using either their SHA-1 and NewHash names
interchangeably.

"git cat-file" and "git hash-object" gain options to display an object
in its sha1 form and write an object given its sha1 form. This
requires all objects referenced by that object to be present in the
object 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 into
NewHash form and record the mapping in the bidirectional mapping table
(see below for details). Pushes to a SHA-1 based server convert the
objects being pushed into sha1 form so the server does not have to be
aware of the hash function the client is using.

Detailed Design
---------------
Repository format extension
~~~~~~~~~~~~~~~~~~~~~~~~~~~
A NewHash repository uses repository format version `1` (see
Documentation/technical/repository-version.txt) with extensions
`objectFormat` and `compatObjectFormat`:

	[core]
		repositoryFormatVersion = 1
	[extensions]
		objectFormat = newhash
		compatObjectFormat = sha1

The combination of setting `core.repositoryFormatVersion=1` and
populating `extensions.*` ensures that all versions of Git later than
`v0.99.9l` will die instead of trying to operate on the NewHash
repository, 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 these
repository extensions.

Object names
~~~~~~~~~~~~
Objects can be named by their 40 hexadecimal digit sha1-name or 64
hexadecimal digit newhash-name, plus names derived from those (see
gitrevisions(7)).

The sha1-name of an object is the SHA-1 of the concatenation of its
type, length, a nul byte, and the object's sha1-content. This is the
traditional <sha1> used in Git to name objects.

The newhash-name of an object is the NewHash of the concatenation of its
type, length, a nul byte, and the object's newhash-content.

Object format
~~~~~~~~~~~~~
The content as a byte sequence of a tag, commit, or tree object named
by sha1 and newhash differ because an object named by newhash-name refers to
other objects by their newhash-names and an object named by sha1-name
refers to other objects by their sha1-names.

The newhash-content of an object is the same as its sha1-content, except
that objects referenced by the object are named using their newhash-names
instead of sha1-names. Because a blob object does not refer to any
other object, its sha1-content and newhash-content are the same.

The format allows round-trip conversion between newhash-content and
sha1-content.

Object storage
~~~~~~~~~~~~~~
Loose objects use zlib compression and packed objects use the packed
format described in Documentation/technical/pack-format.txt, just like
today. The content that is compressed and stored uses newhash-content
instead of sha1-content.

Pack index
~~~~~~~~~~
Pack index (.idx) files use a new v3 format that supports multiple
hash functions. They have the following format (all integers are in
network 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 NewHash checksum at the end of the
    corresponding packfile.

  - 20-byte NewHash checksum of all of the above.

Loose object index
~~~~~~~~~~~~~~~~~~
A new file $GIT_OBJECT_DIR/loose-object-idx contains information about
all loose objects. Its format is

  # loose-object-idx
  (newhash-name SP sha1-name LF)*

where the object names are in hexadecimal format. The file is not
sorted.

The loose object index is protected against concurrent writes by a
lock file $GIT_OBJECT_DIR/loose-object-idx.lock. To add a new loose
object:

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 object
5. 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-names
and newhash-names. The lookup proceeds similarly to ordinary object
lookups. For example, to convert a sha1-name to a newhash-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 newhash-name table.
       That is the object's newhash-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 of
loose objects) time. To maintain good performance it will be necessary
to keep the number of loose objects low. See the "Loose objects and
unreachable objects" section below for more details.

Since all operations that make new objects (e.g., "git commit") add
the new objects to the corresponding index, this mapping is possible
for all objects in the object store.

Reading an object's sha1-content
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The sha1-content of an object can be read by converting all newhash-names
its newhash-content references to sha1-names using the translation table.

Fetch
~~~~~
Fetching from a SHA-1 based server requires translating between SHA-1
and NewHash based representations on the fly.

SHA-1s named in the ref advertisement that are present on the client
can be translated to NewHash and looked up as local objects using the
translation table.

Negotiation proceeds as today. Any "have"s generated locally are
converted to SHA-1 before being sent to the server, and SHA-1s
mentioned by the server are converted to NewHash when looking them up
locally.

After negotiation, the server sends a packfile containing the
requested objects. We convert the packfile to NewHash format using
the 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 newhash: open a new (newhash) packfile. Read the topologically
   sorted list just generated. For each object, inflate its
   sha1-content, convert to newhash-content, and write it to the newhash
   pack. Record the new sha1<->newhash 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 newhash idx
   file
5. 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 the
translation table. This is why the topological sort step is necessary.

As an optimization, step 1 could write a file describing what non-blob
objects each object it has inflated from the packfile references. This
makes the topological sort in step 2 possible without inflating the
objects in the packfile for a second time. The objects need to be
inflated again in step 3, for a total of two inflations.
<