config.txt: clarify core.checkStat
[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 Where NewHash is a strong 256-bit hash function to replace SHA-1 (see
63 "Selection of a New Hash", below):
64
65 1. The transition to NewHash can be done one local repository at a time.
66 a. Requiring no action by any other party.
67 b. A NewHash repository can communicate with SHA-1 Git servers
68 (push/fetch).
69 c. Users can use SHA-1 and NewHash identifiers for objects
70 interchangeably (see "Object names on the command line", below).
71 d. New signed objects make use of a stronger hash function than
72 SHA-1 for their security guarantees.
73 2. Allow a complete transition away from SHA-1.
74 a. Local metadata for SHA-1 compatibility can be removed from a
75 repository if compatibility with SHA-1 is no longer needed.
76 3. Maintainability throughout the process.
77 a. The object format is kept simple and consistent.
78 b. Creation of a generalized repository conversion tool.
79
80 Non-Goals
81 ---------
82 1. Add NewHash support to Git protocol. This is valuable and the
83 logical next step but it is out of scope for this initial design.
84 2. Transparently improving the security of existing SHA-1 signed
85 objects.
86 3. Intermixing objects using multiple hash functions in a single
87 repository.
88 4. Taking the opportunity to fix other bugs in Git's formats and
89 protocols.
90 5. Shallow clones and fetches into a NewHash repository. (This will
91 change when we add NewHash support to Git protocol.)
92 6. Skip fetching some submodules of a project into a NewHash
93 repository. (This also depends on NewHash support in Git
94 protocol.)
95
96 Overview
97 --------
98 We introduce a new repository format extension. Repositories with this
99 extension enabled use NewHash instead of SHA-1 to name their objects.
100 This affects both object names and object content --- both the names
101 of objects and all references to other objects within an object are
102 switched to the new hash function.
103
104 NewHash repositories cannot be read by older versions of Git.
105
106 Alongside the packfile, a NewHash repository stores a bidirectional
107 mapping between NewHash and SHA-1 object names. The mapping is generated
108 locally and can be verified using "git fsck". Object lookups use this
109 mapping to allow naming objects using either their SHA-1 and NewHash names
110 interchangeably.
111
112 "git cat-file" and "git hash-object" gain options to display an object
113 in its sha1 form and write an object given its sha1 form. This
114 requires all objects referenced by that object to be present in the
115 object database so that they can be named using the appropriate name
116 (using the bidirectional hash mapping).
117
118 Fetches from a SHA-1 based server convert the fetched objects into
119 NewHash form and record the mapping in the bidirectional mapping table
120 (see below for details). Pushes to a SHA-1 based server convert the
121 objects being pushed into sha1 form so the server does not have to be
122 aware of the hash function the client is using.
123
124 Detailed Design
125 ---------------
126 Repository format extension
127 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
128 A NewHash repository uses repository format version `1` (see
129 Documentation/technical/repository-version.txt) with extensions
130 `objectFormat` and `compatObjectFormat`:
131
132 [core]
133 repositoryFormatVersion = 1
134 [extensions]
135 objectFormat = newhash
136 compatObjectFormat = sha1
137
138 The combination of setting `core.repositoryFormatVersion=1` and
139 populating `extensions.*` ensures that all versions of Git later than
140 `v0.99.9l` will die instead of trying to operate on the NewHash
141 repository, instead producing an error message.
142
143 # Between v0.99.9l and v2.7.0
144 $ git status
145 fatal: Expected git repo version <= 0, found 1
146 # After v2.7.0
147 $ git status
148 fatal: unknown repository extensions found:
149 objectformat
150 compatobjectformat
151
152 See the "Transition plan" section below for more details on these
153 repository extensions.
154
155 Object names
156 ~~~~~~~~~~~~
157 Objects can be named by their 40 hexadecimal digit sha1-name or 64
158 hexadecimal digit newhash-name, plus names derived from those (see
159 gitrevisions(7)).
160
161 The sha1-name of an object is the SHA-1 of the concatenation of its
162 type, length, a nul byte, and the object's sha1-content. This is the
163 traditional <sha1> used in Git to name objects.
164
165 The newhash-name of an object is the NewHash of the concatenation of its
166 type, length, a nul byte, and the object's newhash-content.
167
168 Object format
169 ~~~~~~~~~~~~~
170 The content as a byte sequence of a tag, commit, or tree object named
171 by sha1 and newhash differ because an object named by newhash-name refers to
172 other objects by their newhash-names and an object named by sha1-name
173 refers to other objects by their sha1-names.
174
175 The newhash-content of an object is the same as its sha1-content, except
176 that objects referenced by the object are named using their newhash-names
177 instead of sha1-names. Because a blob object does not refer to any
178 other object, its sha1-content and newhash-content are the same.
179
180 The format allows round-trip conversion between newhash-content and
181 sha1-content.
182
183 Object storage
184 ~~~~~~~~~~~~~~
185 Loose objects use zlib compression and packed objects use the packed
186 format described in Documentation/technical/pack-format.txt, just like
187 today. The content that is compressed and stored uses newhash-content
188 instead of sha1-content.
189
190 Pack index
191 ~~~~~~~~~~
192 Pack index (.idx) files use a new v3 format that supports multiple
193 hash functions. They have the following format (all integers are in
194 network byte order):
195
196 - A header appears at the beginning and consists of the following:
197 - The 4-byte pack index signature: '\377t0c'
198 - 4-byte version number: 3
199 - 4-byte length of the header section, including the signature and
200 version number
201 - 4-byte number of objects contained in the pack
202 - 4-byte number of object formats in this pack index: 2
203 - For each object format:
204 - 4-byte format identifier (e.g., 'sha1' for SHA-1)
205 - 4-byte length in bytes of shortened object names. This is the
206 shortest possible length needed to make names in the shortened
207 object name table unambiguous.
208 - 4-byte integer, recording where tables relating to this format
209 are stored in this index file, as an offset from the beginning.
210 - 4-byte offset to the trailer from the beginning of this file.
211 - Zero or more additional key/value pairs (4-byte key, 4-byte
212 value). Only one key is supported: 'PSRC'. See the "Loose objects
213 and unreachable objects" section for supported values and how this
214 is used. All other keys are reserved. Readers must ignore
215 unrecognized keys.
216 - Zero or more NUL bytes. This can optionally be used to improve the
217 alignment of the full object name table below.
218 - Tables for the first object format:
219 - A sorted table of shortened object names. These are prefixes of
220 the names of all objects in this pack file, packed together
221 without offset values to reduce the cache footprint of the binary
222 search for a specific object name.
223
224 - A table of full object names in pack order. This allows resolving
225 a reference to "the nth object in the pack file" (from a
226 reachability bitmap or from the next table of another object
227 format) to its object name.
228
229 - A table of 4-byte values mapping object name order to pack order.
230 For an object in the table of sorted shortened object names, the
231 value at the corresponding index in this table is the index in the
232 previous table for that same object.
233
234 This can be used to look up the object in reachability bitmaps or
235 to look up its name in another object format.
236
237 - A table of 4-byte CRC32 values of the packed object data, in the
238 order that the objects appear in the pack file. This is to allow
239 compressed data to be copied directly from pack to pack during
240 repacking without undetected data corruption.
241
242 - A table of 4-byte offset values. For an object in the table of
243 sorted shortened object names, the value at the corresponding
244 index in this table indicates where that object can be found in
245 the pack file. These are usually 31-bit pack file offsets, but
246 large offsets are encoded as an index into the next table with the
247 most significant bit set.
248
249 - A table of 8-byte offset entries (empty for pack files less than
250 2 GiB). Pack files are organized with heavily used objects toward
251 the front, so most object references should not need to refer to
252 this table.
253 - Zero or more NUL bytes.
254 - Tables for the second object format, with the same layout as above,
255 up to and not including the table of CRC32 values.
256 - Zero or more NUL bytes.
257 - The trailer consists of the following:
258 - A copy of the 20-byte NewHash checksum at the end of the
259 corresponding packfile.
260
261 - 20-byte NewHash checksum of all of the above.
262
263 Loose object index
264 ~~~~~~~~~~~~~~~~~~
265 A new file $GIT_OBJECT_DIR/loose-object-idx contains information about
266 all loose objects. Its format is
267
268 # loose-object-idx
269 (newhash-name SP sha1-name LF)*
270
271 where the object names are in hexadecimal format. The file is not
272 sorted.
273
274 The loose object index is protected against concurrent writes by a
275 lock file $GIT_OBJECT_DIR/loose-object-idx.lock. To add a new loose
276 object:
277
278 1. Write the loose object to a temporary file, like today.
279 2. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the lock.
280 3. Rename the loose object into place.
281 4. Open loose-object-idx with O_APPEND and write the new object
282 5. Unlink loose-object-idx.lock to release the lock.
283
284 To remove entries (e.g. in "git pack-refs" or "git-prune"):
285
286 1. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the
287 lock.
288 2. Write the new content to loose-object-idx.lock.
289 3. Unlink any loose objects being removed.
290 4. Rename to replace loose-object-idx, releasing the lock.
291
292 Translation table
293 ~~~~~~~~~~~~~~~~~
294 The index files support a bidirectional mapping between sha1-names
295 and newhash-names. The lookup proceeds similarly to ordinary object
296 lookups. For example, to convert a sha1-name to a newhash-name:
297
298 1. Look for the object in idx files. If a match is present in the
299 idx's sorted list of truncated sha1-names, then:
300 a. Read the corresponding entry in the sha1-name order to pack
301 name order mapping.
302 b. Read the corresponding entry in the full sha1-name table to
303 verify we found the right object. If it is, then
304 c. Read the corresponding entry in the full newhash-name table.
305 That is the object's newhash-name.
306 2. Check for a loose object. Read lines from loose-object-idx until
307 we find a match.
308
309 Step (1) takes the same amount of time as an ordinary object lookup:
310 O(number of packs * log(objects per pack)). Step (2) takes O(number of
311 loose objects) time. To maintain good performance it will be necessary
312 to keep the number of loose objects low. See the "Loose objects and
313 unreachable objects" section below for more details.
314
315 Since all operations that make new objects (e.g., "git commit") add
316 the new objects to the corresponding index, this mapping is possible
317 for all objects in the object store.
318
319 Reading an object's sha1-content
320 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
321 The sha1-content of an object can be read by converting all newhash-names
322 its newhash-content references to sha1-names using the translation table.
323
324 Fetch
325 ~~~~~
326 Fetching from a SHA-1 based server requires translating between SHA-1
327 and NewHash based representations on the fly.
328
329 SHA-1s named in the ref advertisement that are present on the client
330 can be translated to NewHash and looked up as local objects using the
331 translation table.
332
333 Negotiation proceeds as today. Any "have"s generated locally are
334 converted to SHA-1 before being sent to the server, and SHA-1s
335 mentioned by the server are converted to NewHash when looking them up
336 locally.
337
338 After negotiation, the server sends a packfile containing the
339 requested objects. We convert the packfile to NewHash format using
340 the following steps:
341
342 1. index-pack: inflate each object in the packfile and compute its
343 SHA-1. Objects can contain deltas in OBJ_REF_DELTA format against
344 objects the client has locally. These objects can be looked up
345 using the translation table and their sha1-content read as
346 described above to resolve the deltas.
347 2. topological sort: starting at the "want"s from the negotiation
348 phase, walk through objects in the pack and emit a list of them,
349 excluding blobs, in reverse topologically sorted order, with each
350 object coming later in the list than all objects it references.
351 (This list only contains objects reachable from the "wants". If the
352 pack from the server contained additional extraneous objects, then
353 they will be discarded.)
354 3. convert to newhash: open a new (newhash) packfile. Read the topologically
355 sorted list just generated. For each object, inflate its
356 sha1-content, convert to newhash-content, and write it to the newhash
357 pack. Record the new sha1<->newhash mapping entry for use in the idx.
358 4. sort: reorder entries in the new pack to match the order of objects
359 in the pack the server generated and include blobs. Write a newhash idx
360 file
361 5. clean up: remove the SHA-1 based pack file, index, and
362 topologically sorted list obtained from the server in steps 1
363 and 2.
364
365 Step 3 requires every object referenced by the new object to be in the
366 translation table. This is why the topological sort step is necessary.
367
368 As an optimization, step 1 could write a file describing what non-blob
369 objects each object it has inflated from the packfile references. This
370 makes the topological sort in step 2 possible without inflating the
371 objects in the packfile for a second time. The objects need to be
372 inflated again in step 3, for a total of two inflations.
373
374 Step 4 is probably necessary for good read-time performance. "git
375 pack-objects" on the server optimizes the pack file for good data
376 locality (see Documentation/technical/pack-heuristics.txt).
377
378 Details of this process are likely to change. It will take some
379 experimenting to get this to perform well.
380
381 Push
382 ~~~~
383 Push is simpler than fetch because the objects referenced by the
384 pushed objects are already in the translation table. The sha1-content
385 of each object being pushed can be read as described in the "Reading
386 an object's sha1-content" section to generate the pack written by git
387 send-pack.
388
389 Signed Commits
390 ~~~~~~~~~~~~~~
391 We add a new field "gpgsig-newhash" to the commit object format to allow
392 signing commits without relying on SHA-1. It is similar to the
393 existing "gpgsig" field. Its signed payload is the newhash-content of the
394 commit object with any "gpgsig" and "gpgsig-newhash" fields removed.
395
396 This means commits can be signed
397 1. using SHA-1 only, as in existing signed commit objects
398 2. using both SHA-1 and NewHash, by using both gpgsig-newhash and gpgsig
399 fields.
400 3. using only NewHash, by only using the gpgsig-newhash field.
401
402 Old versions of "git verify-commit" can verify the gpgsig signature in
403 cases (1) and (2) without modifications and view case (3) as an
404 ordinary unsigned commit.
405
406 Signed Tags
407 ~~~~~~~~~~~
408 We add a new field "gpgsig-newhash" to the tag object format to allow
409 signing tags without relying on SHA-1. Its signed payload is the
410 newhash-content of the tag with its gpgsig-newhash field and "-----BEGIN PGP
411 SIGNATURE-----" delimited in-body signature removed.
412
413 This means tags can be signed
414 1. using SHA-1 only, as in existing signed tag objects
415 2. using both SHA-1 and NewHash, by using gpgsig-newhash and an in-body
416 signature.
417 3. using only NewHash, by only using the gpgsig-newhash field.
418
419 Mergetag embedding
420 ~~~~~~~~~~~~~~~~~~
421 The mergetag field in the sha1-content of a commit contains the
422 sha1-content of a tag that was merged by that commit.
423
424 The mergetag field in the newhash-content of the same commit contains the
425 newhash-content of the same tag.
426
427 Submodules
428 ~~~~~~~~~~
429 To convert recorded submodule pointers, you need to have the converted
430 submodule repository in place. The translation table of the submodule
431 can be used to look up the new hash.
432
433 Loose objects and unreachable objects
434 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
435 Fast lookups in the loose-object-idx require that the number of loose
436 objects not grow too high.
437
438 "git gc --auto" currently waits for there to be 6700 loose objects
439 present before consolidating them into a packfile. We will need to
440 measure to find a more appropriate threshold for it to use.
441
442 "git gc --auto" currently waits for there to be 50 packs present
443 before combining packfiles. Packing loose objects more aggressively
444 may cause the number of pack files to grow too quickly. This can be
445 mitigated by using a strategy similar to Martin Fick's exponential
446 rolling garbage collection script:
447 https://gerrit-review.googlesource.com/c/gerrit/+/35215
448
449 "git gc" currently expels any unreachable objects it encounters in
450 pack files to loose objects in an attempt to prevent a race when
451 pruning them (in case another process is simultaneously writing a new
452 object that refers to the about-to-be-deleted object). This leads to
453 an explosion in the number of loose objects present and disk space
454 usage due to the objects in delta form being replaced with independent
455 loose objects. Worse, the race is still present for loose objects.
456
457 Instead, "git gc" will need to move unreachable objects to a new
458 packfile marked as UNREACHABLE_GARBAGE (using the PSRC field; see
459 below). To avoid the race when writing new objects referring to an
460 about-to-be-deleted object, code paths that write new objects will
461 need to copy any objects from UNREACHABLE_GARBAGE packs that they
462 refer to to new, non-UNREACHABLE_GARBAGE packs (or loose objects).
463 UNREACHABLE_GARBAGE are then safe to delete if their creation time (as
464 indicated by the file's mtime) is long enough ago.
465
466 To avoid a proliferation of UNREACHABLE_GARBAGE packs, they can be
467 combined under certain circumstances. If "gc.garbageTtl" is set to
468 greater than one day, then packs created within a single calendar day,
469 UTC, can be coalesced together. The resulting packfile would have an
470 mtime before midnight on that day, so this makes the effective maximum
471 ttl the garbageTtl + 1 day. If "gc.garbageTtl" is less than one day,
472 then we divide the calendar day into intervals one-third of that ttl
473 in duration. Packs created within the same interval can be coalesced
474 together. The resulting packfile would have an mtime before the end of
475 the interval, so this makes the effective maximum ttl equal to the
476 garbageTtl * 4/3.
477
478 This rule comes from Thirumala Reddy Mutchukota's JGit change
479 https://git.eclipse.org/r/90465.
480
481 The UNREACHABLE_GARBAGE setting goes in the PSRC field of the pack
482 index. More generally, that field indicates where a pack came from:
483
484 - 1 (PACK_SOURCE_RECEIVE) for a pack received over the network
485 - 2 (PACK_SOURCE_AUTO) for a pack created by a lightweight
486 "gc --auto" operation
487 - 3 (PACK_SOURCE_GC) for a pack created by a full gc
488 - 4 (PACK_SOURCE_UNREACHABLE_GARBAGE) for potential garbage
489 discovered by gc
490 - 5 (PACK_SOURCE_INSERT) for locally created objects that were
491 written directly to a pack file, e.g. from "git add ."
492
493 This information can be useful for debugging and for "gc --auto" to
494 make appropriate choices about which packs to coalesce.
495
496 Caveats
497 -------
498 Invalid objects
499 ~~~~~~~~~~~~~~~
500 The conversion from sha1-content to newhash-content retains any
501 brokenness in the original object (e.g., tree entry modes encoded with
502 leading 0, tree objects whose paths are not sorted correctly, and
503 commit objects without an author or committer). This is a deliberate
504 feature of the design to allow the conversion to round-trip.
505
506 More profoundly broken objects (e.g., a commit with a truncated "tree"
507 header line) cannot be converted but were not usable by current Git
508 anyway.
509
510 Shallow clone and submodules
511 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
512 Because it requires all referenced objects to be available in the
513 locally generated translation table, this design does not support
514 shallow clone or unfetched submodules. Protocol improvements might
515 allow lifting this restriction.
516
517 Alternates
518 ~~~~~~~~~~
519 For the same reason, a newhash repository cannot borrow objects from a
520 sha1 repository using objects/info/alternates or
521 $GIT_ALTERNATE_OBJECT_REPOSITORIES.
522
523 git notes
524 ~~~~~~~~~
525 The "git notes" tool annotates objects using their sha1-name as key.
526 This design does not describe a way to migrate notes trees to use
527 newhash-names. That migration is expected to happen separately (for
528 example using a file at the root of the notes tree to describe which
529 hash it uses).
530
531 Server-side cost
532 ~~~~~~~~~~~~~~~~
533 Until Git protocol gains NewHash support, using NewHash based storage
534 on public-facing Git servers is strongly discouraged. Once Git
535 protocol gains NewHash support, NewHash based servers are likely not
536 to support SHA-1 compatibility, to avoid what may be a very expensive
537 hash reencode during clone and to encourage peers to modernize.
538
539 The design described here allows fetches by SHA-1 clients of a
540 personal NewHash repository because it's not much more difficult than
541 allowing pushes from that repository. This support needs to be guarded
542 by a configuration option --- servers like git.kernel.org that serve a
543 large number of clients would not be expected to bear that cost.
544
545 Meaning of signatures
546 ~~~~~~~~~~~~~~~~~~~~~
547 The signed payload for signed commits and tags does not explicitly
548 name the hash used to identify objects. If some day Git adopts a new
549 hash function with the same length as the current SHA-1 (40
550 hexadecimal digit) or NewHash (64 hexadecimal digit) objects then the
551 intent behind the PGP signed payload in an object signature is
552 unclear:
553
554 object e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7
555 type commit
556 tag v2.12.0
557 tagger Junio C Hamano <gitster@pobox.com> 1487962205 -0800
558
559 Git 2.12
560
561 Does this mean Git v2.12.0 is the commit with sha1-name
562 e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7 or the commit with
563 new-40-digit-hash-name e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7?
564
565 Fortunately NewHash and SHA-1 have different lengths. If Git starts
566 using another hash with the same length to name objects, then it will
567 need to change the format of signed payloads using that hash to
568 address this issue.
569
570 Object names on the command line
571 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
572 To support the transition (see Transition plan below), this design
573 supports four different modes of operation:
574
575 1. ("dark launch") Treat object names input by the user as SHA-1 and
576 convert any object names written to output to SHA-1, but store
577 objects using NewHash. This allows users to test the code with no
578 visible behavior change except for performance. This allows
579 allows running even tests that assume the SHA-1 hash function, to
580 sanity-check the behavior of the new mode.
581
582 2. ("early transition") Allow both SHA-1 and NewHash object names in
583 input. Any object names written to output use SHA-1. This allows
584 users to continue to make use of SHA-1 to communicate with peers
585 (e.g. by email) that have not migrated yet and prepares for mode 3.
586
587 3. ("late transition") Allow both SHA-1 and NewHash object names in
588 input. Any object names written to output use NewHash. In this
589 mode, users are using a more secure object naming method by
590 default. The disruption is minimal as long as most of their peers
591 are in mode 2 or mode 3.
592
593 4. ("post-transition") Treat object names input by the user as
594 NewHash and write output using NewHash. This is safer than mode 3
595 because there is less risk that input is incorrectly interpreted
596 using the wrong hash function.
597
598 The mode is specified in configuration.
599
600 The user can also explicitly specify which format to use for a
601 particular revision specifier and for output, overriding the mode. For
602 example:
603
604 git --output-format=sha1 log abac87a^{sha1}..f787cac^{newhash}
605
606 Selection of a New Hash
607 -----------------------
608 In early 2005, around the time that Git was written, Xiaoyun Wang,
609 Yiqun Lisa Yin, and Hongbo Yu announced an attack finding SHA-1
610 collisions in 2^69 operations. In August they published details.
611 Luckily, no practical demonstrations of a collision in full SHA-1 were
612 published until 10 years later, in 2017.
613
614 The hash function NewHash to replace SHA-1 should be stronger than
615 SHA-1 was: we would like it to be trustworthy and useful in practice
616 for at least 10 years.
617
618 Some other relevant properties:
619
620 1. A 256-bit hash (long enough to match common security practice; not
621 excessively long to hurt performance and disk usage).
622
623 2. High quality implementations should be widely available (e.g. in
624 OpenSSL).
625
626 3. The hash function's properties should match Git's needs (e.g. Git
627 requires collision and 2nd preimage resistance and does not require
628 length extension resistance).
629
630 4. As a tiebreaker, the hash should be fast to compute (fortunately
631 many contenders are faster than SHA-1).
632
633 Some hashes under consideration are SHA-256, SHA-512/256, SHA-256x16,
634 K12, and BLAKE2bp-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-newhash 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 ^{newhash} 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 newhash 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 NewHash 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 NewHash object names.
690
691 When objectFormat and compatObjectFormat are both set, commands
692 generating signatures would generate both SHA-1 and NewHash signatures
693 by default to support both new and old users.
694
695 In projects using NewHash 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 NewHash signatures and have converted their existing
701 repositories to support verifying them, we can add support for a
702 setting to generate only NewHash 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 NewHash 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-newhash field in commit and tag objects
746 for newhash-content based signatures, an earlier version of this design
747 added "hash newhash <newhash-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 newhash-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 newhash-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 newhash-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 newhash-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 [1] http://public-inbox.org/git/CA+55aFzJtejiCjV0e43+9oR3QuJK2PiFiLQemytoLpyJWe6P9w@mail.gmail.com/
818 [2] http://public-inbox.org/git/CA+55aFz+gkAsDZ24zmePQuEs1XPS9BP_s8O7Q4wQ7LV7X5-oDA@mail.gmail.com/
819 [3] http://public-inbox.org/git/20170306084353.nrns455dvkdsfgo5@sigill.intra.peff.net/
820 [4] http://public-inbox.org/git/20170304224936.rqqtkdvfjgyezsht@genre.crustytoothpaste.net
821 [5] https://public-inbox.org/git/CAJo=hJtoX9=AyLHHpUJS7fueV9ciZ_MNpnEPHUz8Whui6g9F0A@mail.gmail.com/