Merge branch 'nd/config-core-checkstat-doc'
[git/git.git] / Documentation / technical / hash-function-transition.txt
1 Git hash function transition
2 ============================
3
4 Objective
5 ---------
6 Migrate Git from SHA-1 to a stronger hash function.
7
8 Background
9 ----------
10 At its core, the Git version control system is a content addressable
11 filesystem. It uses the SHA-1 hash function to name content. For
12 example, files, directories, and revisions are referred to by hash
13 values unlike in other traditional version control systems where files
14 or versions are referred to via sequential numbers. The use of a hash
15 function to address its content delivers a few advantages:
16
17 * Integrity checking is easy. Bit flips, for example, are easily
18 detected, as the hash of corrupted content does not match its name.
19 * Lookup of objects is fast.
20
21 Using a cryptographically secure hash function brings additional
22 advantages:
23
24 * Object names can be signed and third parties can trust the hash to
25 address the signed object and all objects it references.
26 * Communication using Git protocol and out of band communication
27 methods have a short reliable string that can be used to reliably
28 address stored content.
29
30 Over time some flaws in SHA-1 have been discovered by security
31 researchers. On 23 February 2017 the SHAttered attack
32 (https://shattered.io) demonstrated a practical SHA-1 hash collision.
33
34 Git v2.13.0 and later subsequently moved to a hardened SHA-1
35 implementation by default, which isn't vulnerable to the SHAttered
36 attack.
37
38 Thus Git has in effect already migrated to a new hash that isn't SHA-1
39 and doesn't share its vulnerabilities, its new hash function just
40 happens to produce exactly the same output for all known inputs,
41 except two PDFs published by the SHAttered researchers, and the new
42 implementation (written by those researchers) claims to detect future
43 cryptanalytic collision attacks.
44
45 Regardless, it's considered prudent to move past any variant of SHA-1
46 to a new hash. There's no guarantee that future attacks on SHA-1 won't
47 be published in the future, and those attacks may not have viable
48 mitigations.
49
50 If SHA-1 and its variants were to be truly broken, Git's hash function
51 could not be considered cryptographically secure any more. This would
52 impact the communication of hash values because we could not trust
53 that a given hash value represented the known good version of content
54 that the speaker intended.
55
56 SHA-1 still possesses the other properties such as fast object lookup
57 and safe error checking, but other hash functions are equally suitable
58 that are believed to be cryptographically secure.
59
60 Goals
61 -----
62 1. The transition to SHA-256 can be done one local repository at a time.
63 a. Requiring no action by any other party.
64 b. A SHA-256 repository can communicate with SHA-1 Git servers
65 (push/fetch).
66 c. Users can use SHA-1 and SHA-256 identifiers for objects
67 interchangeably (see "Object names on the command line", below).
68 d. New signed objects make use of a stronger hash function than
69 SHA-1 for their security guarantees.
70 2. Allow a complete transition away from SHA-1.
71 a. Local metadata for SHA-1 compatibility can be removed from a
72 repository if compatibility with SHA-1 is no longer needed.
73 3. Maintainability throughout the process.
74 a. The object format is kept simple and consistent.
75 b. Creation of a generalized repository conversion tool.
76
77 Non-Goals
78 ---------
79 1. Add SHA-256 support to Git protocol. This is valuable and the
80 logical next step but it is out of scope for this initial design.
81 2. Transparently improving the security of existing SHA-1 signed
82 objects.
83 3. Intermixing objects using multiple hash functions in a single
84 repository.
85 4. Taking the opportunity to fix other bugs in Git's formats and
86 protocols.
87 5. Shallow clones and fetches into a SHA-256 repository. (This will
88 change when we add SHA-256 support to Git protocol.)
89 6. Skip fetching some submodules of a project into a SHA-256
90 repository. (This also depends on SHA-256 support in Git
91 protocol.)
92
93 Overview
94 --------
95 We introduce a new repository format extension. Repositories with this
96 extension enabled use SHA-256 instead of SHA-1 to name their objects.
97 This affects both object names and object content --- both the names
98 of objects and all references to other objects within an object are
99 switched to the new hash function.
100
101 SHA-256 repositories cannot be read by older versions of Git.
102
103 Alongside the packfile, a SHA-256 repository stores a bidirectional
104 mapping between SHA-256 and SHA-1 object names. The mapping is generated
105 locally and can be verified using "git fsck". Object lookups use this
106 mapping to allow naming objects using either their SHA-1 and SHA-256 names
107 interchangeably.
108
109 "git cat-file" and "git hash-object" gain options to display an object
110 in its sha1 form and write an object given its sha1 form. This
111 requires all objects referenced by that object to be present in the
112 object database so that they can be named using the appropriate name
113 (using the bidirectional hash mapping).
114
115 Fetches from a SHA-1 based server convert the fetched objects into
116 SHA-256 form and record the mapping in the bidirectional mapping table
117 (see below for details). Pushes to a SHA-1 based server convert the
118 objects being pushed into sha1 form so the server does not have to be
119 aware of the hash function the client is using.
120
121 Detailed Design
122 ---------------
123 Repository format extension
124 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
125 A SHA-256 repository uses repository format version `1` (see
126 Documentation/technical/repository-version.txt) with extensions
127 `objectFormat` and `compatObjectFormat`:
128
129 [core]
130 repositoryFormatVersion = 1
131 [extensions]
132 objectFormat = sha256
133 compatObjectFormat = sha1
134
135 The combination of setting `core.repositoryFormatVersion=1` and
136 populating `extensions.*` ensures that all versions of Git later than
137 `v0.99.9l` will die instead of trying to operate on the SHA-256
138 repository, instead producing an error message.
139
140 # Between v0.99.9l and v2.7.0
141 $ git status
142 fatal: Expected git repo version <= 0, found 1
143 # After v2.7.0
144 $ git status
145 fatal: unknown repository extensions found:
146 objectformat
147 compatobjectformat
148
149 See the "Transition plan" section below for more details on these
150 repository extensions.
151
152 Object names
153 ~~~~~~~~~~~~
154 Objects can be named by their 40 hexadecimal digit sha1-name or 64
155 hexadecimal digit sha256-name, plus names derived from those (see
156 gitrevisions(7)).
157
158 The sha1-name of an object is the SHA-1 of the concatenation of its
159 type, length, a nul byte, and the object's sha1-content. This is the
160 traditional <sha1> used in Git to name objects.
161
162 The sha256-name of an object is the SHA-256 of the concatenation of its
163 type, length, a nul byte, and the object's sha256-content.
164
165 Object format
166 ~~~~~~~~~~~~~
167 The content as a byte sequence of a tag, commit, or tree object named
168 by sha1 and sha256 differ because an object named by sha256-name refers to
169 other objects by their sha256-names and an object named by sha1-name
170 refers to other objects by their sha1-names.
171
172 The sha256-content of an object is the same as its sha1-content, except
173 that objects referenced by the object are named using their sha256-names
174 instead of sha1-names. Because a blob object does not refer to any
175 other object, its sha1-content and sha256-content are the same.
176
177 The format allows round-trip conversion between sha256-content and
178 sha1-content.
179
180 Object storage
181 ~~~~~~~~~~~~~~
182 Loose objects use zlib compression and packed objects use the packed
183 format described in Documentation/technical/pack-format.txt, just like
184 today. The content that is compressed and stored uses sha256-content
185 instead of sha1-content.
186
187 Pack index
188 ~~~~~~~~~~
189 Pack index (.idx) files use a new v3 format that supports multiple
190 hash functions. They have the following format (all integers are in
191 network byte order):
192
193 - A header appears at the beginning and consists of the following:
194 - The 4-byte pack index signature: '\377t0c'
195 - 4-byte version number: 3
196 - 4-byte length of the header section, including the signature and
197 version number
198 - 4-byte number of objects contained in the pack
199 - 4-byte number of object formats in this pack index: 2
200 - For each object format:
201 - 4-byte format identifier (e.g., 'sha1' for SHA-1)
202 - 4-byte length in bytes of shortened object names. This is the
203 shortest possible length needed to make names in the shortened
204 object name table unambiguous.
205 - 4-byte integer, recording where tables relating to this format
206 are stored in this index file, as an offset from the beginning.
207 - 4-byte offset to the trailer from the beginning of this file.
208 - Zero or more additional key/value pairs (4-byte key, 4-byte
209 value). Only one key is supported: 'PSRC'. See the "Loose objects
210 and unreachable objects" section for supported values and how this
211 is used. All other keys are reserved. Readers must ignore
212 unrecognized keys.
213 - Zero or more NUL bytes. This can optionally be used to improve the
214 alignment of the full object name table below.
215 - Tables for the first object format:
216 - A sorted table of shortened object names. These are prefixes of
217 the names of all objects in this pack file, packed together
218 without offset values to reduce the cache footprint of the binary
219 search for a specific object name.
220
221 - A table of full object names in pack order. This allows resolving
222 a reference to "the nth object in the pack file" (from a
223 reachability bitmap or from the next table of another object
224 format) to its object name.
225
226 - A table of 4-byte values mapping object name order to pack order.
227 For an object in the table of sorted shortened object names, the
228 value at the corresponding index in this table is the index in the
229 previous table for that same object.
230
231 This can be used to look up the object in reachability bitmaps or
232 to look up its name in another object format.
233
234 - A table of 4-byte CRC32 values of the packed object data, in the
235 order that the objects appear in the pack file. This is to allow
236 compressed data to be copied directly from pack to pack during
237 repacking without undetected data corruption.
238
239 - A table of 4-byte offset values. For an object in the table of
240 sorted shortened object names, the value at the corresponding
241 index in this table indicates where that object can be found in
242 the pack file. These are usually 31-bit pack file offsets, but
243 large offsets are encoded as an index into the next table with the
244 most significant bit set.
245
246 - A table of 8-byte offset entries (empty for pack files less than
247 2 GiB). Pack files are organized with heavily used objects toward
248 the front, so most object references should not need to refer to
249 this table.
250 - Zero or more NUL bytes.
251 - Tables for the second object format, with the same layout as above,
252 up to and not including the table of CRC32 values.
253 - Zero or more NUL bytes.
254 - The trailer consists of the following:
255 - A copy of the 20-byte SHA-256 checksum at the end of the
256 corresponding packfile.
257
258 - 20-byte SHA-256 checksum of all of the above.
259
260 Loose object index
261 ~~~~~~~~~~~~~~~~~~
262 A new file $GIT_OBJECT_DIR/loose-object-idx contains information about
263 all loose objects. Its format is
264
265 # loose-object-idx
266 (sha256-name SP sha1-name LF)*
267
268 where the object names are in hexadecimal format. The file is not
269 sorted.
270
271 The loose object index is protected against concurrent writes by a
272 lock file $GIT_OBJECT_DIR/loose-object-idx.lock. To add a new loose
273 object:
274
275 1. Write the loose object to a temporary file, like today.
276 2. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the lock.
277 3. Rename the loose object into place.
278 4. Open loose-object-idx with O_APPEND and write the new object
279 5. Unlink loose-object-idx.lock to release the lock.
280
281 To remove entries (e.g. in "git pack-refs" or "git-prune"):
282
283 1. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the
284 lock.
285 2. Write the new content to loose-object-idx.lock.
286 3. Unlink any loose objects being removed.
287 4. Rename to replace loose-object-idx, releasing the lock.
288
289 Translation table
290 ~~~~~~~~~~~~~~~~~
291 The index files support a bidirectional mapping between sha1-names
292 and sha256-names. The lookup proceeds similarly to ordinary object
293 lookups. For example, to convert a sha1-name to a sha256-name:
294
295 1. Look for the object in idx files. If a match is present in the
296 idx's sorted list of truncated sha1-names, then:
297 a. Read the corresponding entry in the sha1-name order to pack
298 name order mapping.
299 b. Read the corresponding entry in the full sha1-name table to
300 verify we found the right object. If it is, then
301 c. Read the corresponding entry in the full sha256-name table.
302 That is the object's sha256-name.
303 2. Check for a loose object. Read lines from loose-object-idx until
304 we find a match.
305
306 Step (1) takes the same amount of time as an ordinary object lookup:
307 O(number of packs * log(objects per pack)). Step (2) takes O(number of
308 loose objects) time. To maintain good performance it will be necessary
309 to keep the number of loose objects low. See the "Loose objects and
310 unreachable objects" section below for more details.
311
312 Since all operations that make new objects (e.g., "git commit") add
313 the new objects to the corresponding index, this mapping is possible
314 for all objects in the object store.
315
316 Reading an object's sha1-content
317 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
318 The sha1-content of an object can be read by converting all sha256-names
319 its sha256-content references to sha1-names using the translation table.
320
321 Fetch
322 ~~~~~
323 Fetching from a SHA-1 based server requires translating between SHA-1
324 and SHA-256 based representations on the fly.
325
326 SHA-1s named in the ref advertisement that are present on the client
327 can be translated to SHA-256 and looked up as local objects using the
328 translation table.
329
330 Negotiation proceeds as today. Any "have"s generated locally are
331 converted to SHA-1 before being sent to the server, and SHA-1s
332 mentioned by the server are converted to SHA-256 when looking them up
333 locally.
334
335 After negotiation, the server sends a packfile containing the
336 requested objects. We convert the packfile to SHA-256 format using
337 the following steps:
338
339 1. index-pack: inflate each object in the packfile and compute its
340 SHA-1. Objects can contain deltas in OBJ_REF_DELTA format against
341 objects the client has locally. These objects can be looked up
342 using the translation table and their sha1-content read as
343 described above to resolve the deltas.
344 2. topological sort: starting at the "want"s from the negotiation
345 phase, walk through objects in the pack and emit a list of them,
346 excluding blobs, in reverse topologically sorted order, with each
347 object coming later in the list than all objects it references.
348 (This list only contains objects reachable from the "wants". If the
349 pack from the server contained additional extraneous objects, then
350 they will be discarded.)
351 3. convert to sha256: open a new (sha256) packfile. Read the topologically
352 sorted list just generated. For each object, inflate its
353 sha1-content, convert to sha256-content, and write it to the sha256
354 pack. Record the new sha1<->sha256 mapping entry for use in the idx.
355 4. sort: reorder entries in the new pack to match the order of objects
356 in the pack the server generated and include blobs. Write a sha256 idx
357 file
358 5. clean up: remove the SHA-1 based pack file, index, and
359 topologically sorted list obtained from the server in steps 1
360 and 2.
361
362 Step 3 requires every object referenced by the new object to be in the
363 translation table. This is why the topological sort step is necessary.
364
365 As an optimization, step 1 could write a file describing what non-blob
366 objects each object it has inflated from the packfile references. This
367 makes the topological sort in step 2 possible without inflating the
368 objects in the packfile for a second time. The objects need to be
369 inflated again in step 3, for a total of two inflations.
370
371 Step 4 is probably necessary for good read-time performance. "git
372 pack-objects" on the server optimizes the pack file for good data
373 locality (see Documentation/technical/pack-heuristics.txt).
374
375 Details of this process are likely to change. It will take some
376 experimenting to get this to perform well.
377
378 Push
379 ~~~~
380 Push is simpler than fetch because the objects referenced by the
381 pushed objects are already in the translation table. The sha1-content
382 of each object being pushed can be read as described in the "Reading
383 an object's sha1-content" section to generate the pack written by git
384 send-pack.
385
386 Signed Commits
387 ~~~~~~~~~~~~~~
388 We add a new field "gpgsig-sha256" to the commit object format to allow
389 signing commits without relying on SHA-1. It is similar to the
390 existing "gpgsig" field. Its signed payload is the sha256-content of the
391 commit object with any "gpgsig" and "gpgsig-sha256" fields removed.
392
393 This means commits can be signed
394 1. using SHA-1 only, as in existing signed commit objects
395 2. using both SHA-1 and SHA-256, by using both gpgsig-sha256 and gpgsig
396 fields.
397 3. using only SHA-256, by only using the gpgsig-sha256 field.
398
399 Old versions of "git verify-commit" can verify the gpgsig signature in
400 cases (1) and (2) without modifications and view case (3) as an
401 ordinary unsigned commit.
402
403 Signed Tags
404 ~~~~~~~~~~~
405 We add a new field "gpgsig-sha256" to the tag object format to allow
406 signing tags without relying on SHA-1. Its signed payload is the
407 sha256-content of the tag with its gpgsig-sha256 field and "-----BEGIN PGP
408 SIGNATURE-----" delimited in-body signature removed.
409
410 This means tags can be signed
411 1. using SHA-1 only, as in existing signed tag objects
412 2. using both SHA-1 and SHA-256, by using gpgsig-sha256 and an in-body
413 signature.
414 3. using only SHA-256, by only using the gpgsig-sha256 field.
415
416 Mergetag embedding
417 ~~~~~~~~~~~~~~~~~~
418 The mergetag field in the sha1-content of a commit contains the
419 sha1-content of a tag that was merged by that commit.
420
421 The mergetag field in the sha256-content of the same commit contains the
422 sha256-content of the same tag.
423
424 Submodules
425 ~~~~~~~~~~
426 To convert recorded submodule pointers, you need to have the converted
427 submodule repository in place. The translation table of the submodule
428 can be used to look up the new hash.
429
430 Loose objects and unreachable objects
431 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
432 Fast lookups in the loose-object-idx require that the number of loose
433 objects not grow too high.
434
435 "git gc --auto" currently waits for there to be 6700 loose objects
436 present before consolidating them into a packfile. We will need to
437 measure to find a more appropriate threshold for it to use.
438
439 "git gc --auto" currently waits for there to be 50 packs present
440 before combining packfiles. Packing loose objects more aggressively
441 may cause the number of pack files to grow too quickly. This can be
442 mitigated by using a strategy similar to Martin Fick's exponential
443 rolling garbage collection script:
444 https://gerrit-review.googlesource.com/c/gerrit/+/35215
445
446 "git gc" currently expels any unreachable objects it encounters in
447 pack files to loose objects in an attempt to prevent a race when
448 pruning them (in case another process is simultaneously writing a new
449 object that refers to the about-to-be-deleted object). This leads to
450 an explosion in the number of loose objects present and disk space
451 usage due to the objects in delta form being replaced with independent
452 loose objects. Worse, the race is still present for loose objects.
453
454 Instead, "git gc" will need to move unreachable objects to a new
455 packfile marked as UNREACHABLE_GARBAGE (using the PSRC field; see
456 below). To avoid the race when writing new objects referring to an
457 about-to-be-deleted object, code paths that write new objects will
458 need to copy any objects from UNREACHABLE_GARBAGE packs that they
459 refer to to new, non-UNREACHABLE_GARBAGE packs (or loose objects).
460 UNREACHABLE_GARBAGE are then safe to delete if their creation time (as
461 indicated by the file's mtime) is long enough ago.
462
463 To avoid a proliferation of UNREACHABLE_GARBAGE packs, they can be
464 combined under certain circumstances. If "gc.garbageTtl" is set to
465 greater than one day, then packs created within a single calendar day,
466 UTC, can be coalesced together. The resulting packfile would have an
467 mtime before midnight on that day, so this makes the effective maximum
468 ttl the garbageTtl + 1 day. If "gc.garbageTtl" is less than one day,
469 then we divide the calendar day into intervals one-third of that ttl
470 in duration. Packs created within the same interval can be coalesced
471 together. The resulting packfile would have an mtime before the end of
472 the interval, so this makes the effective maximum ttl equal to the
473 garbageTtl * 4/3.
474
475 This rule comes from Thirumala Reddy Mutchukota's JGit change
476 https://git.eclipse.org/r/90465.
477
478 The UNREACHABLE_GARBAGE setting goes in the PSRC field of the pack
479 index. More generally, that field indicates where a pack came from:
480
481 - 1 (PACK_SOURCE_RECEIVE) for a pack received over the network
482 - 2 (PACK_SOURCE_AUTO) for a pack created by a lightweight
483 "gc --auto" operation
484 - 3 (PACK_SOURCE_GC) for a pack created by a full gc
485 - 4 (PACK_SOURCE_UNREACHABLE_GARBAGE) for potential garbage
486 discovered by gc
487 - 5 (PACK_SOURCE_INSERT) for locally created objects that were
488 written directly to a pack file, e.g. from "git add ."
489
490 This information can be useful for debugging and for "gc --auto" to
491 make appropriate choices about which packs to coalesce.
492
493 Caveats
494 -------
495 Invalid objects
496 ~~~~~~~~~~~~~~~
497 The conversion from sha1-content to sha256-content retains any
498 brokenness in the original object (e.g., tree entry modes encoded with
499 leading 0, tree objects whose paths are not sorted correctly, and
500 commit objects without an author or committer). This is a deliberate
501 feature of the design to allow the conversion to round-trip.
502
503 More profoundly broken objects (e.g., a commit with a truncated "tree"
504 header line) cannot be converted but were not usable by current Git
505 anyway.
506
507 Shallow clone and submodules
508 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
509 Because it requires all referenced objects to be available in the
510 locally generated translation table, this design does not support
511 shallow clone or unfetched submodules. Protocol improvements might
512 allow lifting this restriction.
513
514 Alternates
515 ~~~~~~~~~~
516 For the same reason, a sha256 repository cannot borrow objects from a
517 sha1 repository using objects/info/alternates or
518 $GIT_ALTERNATE_OBJECT_REPOSITORIES.
519
520 git notes
521 ~~~~~~~~~
522 The "git notes" tool annotates objects using their sha1-name as key.
523 This design does not describe a way to migrate notes trees to use
524 sha256-names. That migration is expected to happen separately (for
525 example using a file at the root of the notes tree to describe which
526 hash it uses).
527
528 Server-side cost
529 ~~~~~~~~~~~~~~~~
530 Until Git protocol gains SHA-256 support, using SHA-256 based storage
531 on public-facing Git servers is strongly discouraged. Once Git
532 protocol gains SHA-256 support, SHA-256 based servers are likely not
533 to support SHA-1 compatibility, to avoid what may be a very expensive
534 hash reencode during clone and to encourage peers to modernize.
535
536 The design described here allows fetches by SHA-1 clients of a
537 personal SHA-256 repository because it's not much more difficult than
538 allowing pushes from that repository. This support needs to be guarded
539 by a configuration option --- servers like git.kernel.org that serve a
540 large number of clients would not be expected to bear that cost.
541
542 Meaning of signatures
543 ~~~~~~~~~~~~~~~~~~~~~
544 The signed payload for signed commits and tags does not explicitly
545 name the hash used to identify objects. If some day Git adopts a new
546 hash function with the same length as the current SHA-1 (40
547 hexadecimal digit) or SHA-256 (64 hexadecimal digit) objects then the
548 intent behind the PGP signed payload in an object signature is
549 unclear:
550
551 object e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7
552 type commit
553 tag v2.12.0
554 tagger Junio C Hamano <gitster@pobox.com> 1487962205 -0800
555
556 Git 2.12
557
558 Does this mean Git v2.12.0 is the commit with sha1-name
559 e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7 or the commit with
560 new-40-digit-hash-name e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7?
561
562 Fortunately SHA-256 and SHA-1 have different lengths. If Git starts
563 using another hash with the same length to name objects, then it will
564 need to change the format of signed payloads using that hash to
565 address this issue.
566
567 Object names on the command line
568 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
569 To support the transition (see Transition plan below), this design
570 supports four different modes of operation:
571
572 1. ("dark launch") Treat object names input by the user as SHA-1 and
573 convert any object names written to output to SHA-1, but store
574 objects using SHA-256. This allows users to test the code with no
575 visible behavior change except for performance. This allows
576 allows running even tests that assume the SHA-1 hash function, to
577 sanity-check the behavior of the new mode.
578
579 2. ("early transition") Allow both SHA-1 and SHA-256 object names in
580 input. Any object names written to output use SHA-1. This allows
581 users to continue to make use of SHA-1 to communicate with peers
582 (e.g. by email) that have not migrated yet and prepares for mode 3.
583
584 3. ("late transition") Allow both SHA-1 and SHA-256 object names in
585 input. Any object names written to output use SHA-256. In this
586 mode, users are using a more secure object naming method by
587 default. The disruption is minimal as long as most of their peers
588 are in mode 2 or mode 3.
589
590 4. ("post-transition") Treat object names input by the user as
591 SHA-256 and write output using SHA-256. This is safer than mode 3
592 because there is less risk that input is incorrectly interpreted
593 using the wrong hash function.
594
595 The mode is specified in configuration.
596
597 The user can also explicitly specify which format to use for a
598 particular revision specifier and for output, overriding the mode. For
599 example:
600
601 git --output-format=sha1 log abac87a^{sha1}..f787cac^{sha256}
602
603 Choice of Hash
604 --------------
605 In early 2005, around the time that Git was written, Xiaoyun Wang,
606 Yiqun Lisa Yin, and Hongbo Yu announced an attack finding SHA-1
607 collisions in 2^69 operations. In August they published details.
608 Luckily, no practical demonstrations of a collision in full SHA-1 were
609 published until 10 years later, in 2017.
610
611 Git v2.13.0 and later subsequently moved to a hardened SHA-1
612 implementation by default that mitigates the SHAttered attack, but
613 SHA-1 is still believed to be weak.
614
615 The hash to replace this hardened SHA-1 should be stronger than SHA-1
616 was: we would like it to be trustworthy and useful in practice for at
617 least 10 years.
618
619 Some other relevant properties:
620
621 1. A 256-bit hash (long enough to match common security practice; not
622 excessively long to hurt performance and disk usage).
623
624 2. High quality implementations should be widely available (e.g., in
625 OpenSSL and Apple CommonCrypto).
626
627 3. The hash function's properties should match Git's needs (e.g. Git
628 requires collision and 2nd preimage resistance and does not require
629 length extension resistance).
630
631 4. As a tiebreaker, the hash should be fast to compute (fortunately
632 many contenders are faster than SHA-1).
633
634 We choose SHA-256.
635
636 Transition plan
637 ---------------
638 Some initial steps can be implemented independently of one another:
639 - adding a hash function API (vtable)
640 - teaching fsck to tolerate the gpgsig-sha256 field
641 - excluding gpgsig-* from the fields copied by "git commit --amend"
642 - annotating tests that depend on SHA-1 values with a SHA1 test
643 prerequisite
644 - using "struct object_id", GIT_MAX_RAWSZ, and GIT_MAX_HEXSZ
645 consistently instead of "unsigned char *" and the hardcoded
646 constants 20 and 40.
647 - introducing index v3
648 - adding support for the PSRC field and safer object pruning
649
650
651 The first user-visible change is the introduction of the objectFormat
652 extension (without compatObjectFormat). This requires:
653 - implementing the loose-object-idx
654 - teaching fsck about this mode of operation
655 - using the hash function API (vtable) when computing object names
656 - signing objects and verifying signatures
657 - rejecting attempts to fetch from or push to an incompatible
658 repository
659
660 Next comes introduction of compatObjectFormat:
661 - translating object names between object formats
662 - translating object content between object formats
663 - generating and verifying signatures in the compat format
664 - adding appropriate index entries when adding a new object to the
665 object store
666 - --output-format option
667 - ^{sha1} and ^{sha256} revision notation
668 - configuration to specify default input and output format (see
669 "Object names on the command line" above)
670
671 The next step is supporting fetches and pushes to SHA-1 repositories:
672 - allow pushes to a repository using the compat format
673 - generate a topologically sorted list of the SHA-1 names of fetched
674 objects
675 - convert the fetched packfile to sha256 format and generate an idx
676 file
677 - re-sort to match the order of objects in the fetched packfile
678
679 The infrastructure supporting fetch also allows converting an existing
680 repository. In converted repositories and new clones, end users can
681 gain support for the new hash function without any visible change in
682 behavior (see "dark launch" in the "Object names on the command line"
683 section). In particular this allows users to verify SHA-256 signatures
684 on objects in the repository, and it should ensure the transition code
685 is stable in production in preparation for using it more widely.
686
687 Over time projects would encourage their users to adopt the "early
688 transition" and then "late transition" modes to take advantage of the
689 new, more futureproof SHA-256 object names.
690
691 When objectFormat and compatObjectFormat are both set, commands
692 generating signatures would generate both SHA-1 and SHA-256 signatures
693 by default to support both new and old users.
694
695 In projects using SHA-256 heavily, users could be encouraged to adopt
696 the "post-transition" mode to avoid accidentally making implicit use
697 of SHA-1 object names.
698
699 Once a critical mass of users have upgraded to a version of Git that
700 can verify SHA-256 signatures and have converted their existing
701 repositories to support verifying them, we can add support for a
702 setting to generate only SHA-256 signatures. This is expected to be at
703 least a year later.
704
705 That is also a good moment to advertise the ability to convert
706 repositories to use SHA-256 only, stripping out all SHA-1 related
707 metadata. This improves performance by eliminating translation
708 overhead and security by avoiding the possibility of accidentally
709 relying on the safety of SHA-1.
710
711 Updating Git's protocols to allow a server to specify which hash
712 functions it supports is also an important part of this transition. It
713 is not discussed in detail in this document but this transition plan
714 assumes it happens. :)
715
716 Alternatives considered
717 -----------------------
718 Upgrading everyone working on a particular project on a flag day
719 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
720 Projects like the Linux kernel are large and complex enough that
721 flipping the switch for all projects based on the repository at once
722 is infeasible.
723
724 Not only would all developers and server operators supporting
725 developers have to switch on the same flag day, but supporting tooling
726 (continuous integration, code review, bug trackers, etc) would have to
727 be adapted as well. This also makes it difficult to get early feedback
728 from some project participants testing before it is time for mass
729 adoption.
730
731 Using hash functions in parallel
732 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
733 (e.g. https://public-inbox.org/git/22708.8913.864049.452252@chiark.greenend.org.uk/ )
734 Objects newly created would be addressed by the new hash, but inside
735 such an object (e.g. commit) it is still possible to address objects
736 using the old hash function.
737 * You cannot trust its history (needed for bisectability) in the
738 future without further work
739 * Maintenance burden as the number of supported hash functions grows
740 (they will never go away, so they accumulate). In this proposal, by
741 comparison, converted objects lose all references to SHA-1.
742
743 Signed objects with multiple hashes
744 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
745 Instead of introducing the gpgsig-sha256 field in commit and tag objects
746 for sha256-content based signatures, an earlier version of this design
747 added "hash sha256 <sha256-name>" fields to strengthen the existing
748 sha1-content based signatures.
749
750 In other words, a single signature was used to attest to the object
751 content using both hash functions. This had some advantages:
752 * Using one signature instead of two speeds up the signing process.
753 * Having one signed payload with both hashes allows the signer to
754 attest to the sha1-name and sha256-name referring to the same object.
755 * All users consume the same signature. Broken signatures are likely
756 to be detected quickly using current versions of git.
757
758 However, it also came with disadvantages:
759 * Verifying a signed object requires access to the sha1-names of all
760 objects it references, even after the transition is complete and
761 translation table is no longer needed for anything else. To support
762 this, the design added fields such as "hash sha1 tree <sha1-name>"
763 and "hash sha1 parent <sha1-name>" to the sha256-content of a signed
764 commit, complicating the conversion process.
765 * Allowing signed objects without a sha1 (for after the transition is
766 complete) complicated the design further, requiring a "nohash sha1"
767 field to suppress including "hash sha1" fields in the sha256-content
768 and signed payload.
769
770 Lazily populated translation table
771 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
772 Some of the work of building the translation table could be deferred to
773 push time, but that would significantly complicate and slow down pushes.
774 Calculating the sha1-name at object creation time at the same time it is
775 being streamed to disk and having its sha256-name calculated should be
776 an acceptable cost.
777
778 Document History
779 ----------------
780
781 2017-03-03
782 bmwill@google.com, jonathantanmy@google.com, jrnieder@gmail.com,
783 sbeller@google.com
784
785 Initial version sent to
786 http://public-inbox.org/git/20170304011251.GA26789@aiede.mtv.corp.google.com
787
788 2017-03-03 jrnieder@gmail.com
789 Incorporated suggestions from jonathantanmy and sbeller:
790 * describe purpose of signed objects with each hash type
791 * redefine signed object verification using object content under the
792 first hash function
793
794 2017-03-06 jrnieder@gmail.com
795 * Use SHA3-256 instead of SHA2 (thanks, Linus and brian m. carlson).[1][2]
796 * Make sha3-based signatures a separate field, avoiding the need for
797 "hash" and "nohash" fields (thanks to peff[3]).
798 * Add a sorting phase to fetch (thanks to Junio for noticing the need
799 for this).
800 * Omit blobs from the topological sort during fetch (thanks to peff).
801 * Discuss alternates, git notes, and git servers in the caveats
802 section (thanks to Junio Hamano, brian m. carlson[4], and Shawn
803 Pearce).
804 * Clarify language throughout (thanks to various commenters,
805 especially Junio).
806
807 2017-09-27 jrnieder@gmail.com, sbeller@google.com
808 * use placeholder NewHash instead of SHA3-256
809 * describe criteria for picking a hash function.
810 * include a transition plan (thanks especially to Brandon Williams
811 for fleshing these ideas out)
812 * define the translation table (thanks, Shawn Pearce[5], Jonathan
813 Tan, and Masaya Suzuki)
814 * avoid loose object overhead by packing more aggressively in
815 "git gc --auto"
816
817 Later history:
818
819 See the history of this file in git.git for the history of subsequent
820 edits. This document history is no longer being maintained as it
821 would now be superfluous to the commit log
822
823 [1] http://public-inbox.org/git/CA+55aFzJtejiCjV0e43+9oR3QuJK2PiFiLQemytoLpyJWe6P9w@mail.gmail.com/
824 [2] http://public-inbox.org/git/CA+55aFz+gkAsDZ24zmePQuEs1XPS9BP_s8O7Q4wQ7LV7X5-oDA@mail.gmail.com/
825 [3] http://public-inbox.org/git/20170306084353.nrns455dvkdsfgo5@sigill.intra.peff.net/
826 [4] http://public-inbox.org/git/20170304224936.rqqtkdvfjgyezsht@genre.crustytoothpaste.net
827 [5] https://public-inbox.org/git/CAJo=hJtoX9=AyLHHpUJS7fueV9ciZ_MNpnEPHUz8Whui6g9F0A@mail.gmail.com/