]>
Commit | Line | Data |
---|---|---|
752414ae JN |
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 | |
5988eb63 ÆAB |
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. | |
752414ae JN |
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 | ----- | |
0ed8d8da | 62 | 1. The transition to SHA-256 can be done one local repository at a time. |
752414ae | 63 | a. Requiring no action by any other party. |
0ed8d8da | 64 | b. A SHA-256 repository can communicate with SHA-1 Git servers |
752414ae | 65 | (push/fetch). |
0ed8d8da | 66 | c. Users can use SHA-1 and SHA-256 identifiers for objects |
752414ae JN |
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 | --------- | |
0ed8d8da | 79 | 1. Add SHA-256 support to Git protocol. This is valuable and the |
752414ae JN |
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. | |
0ed8d8da JN |
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 | |
752414ae JN |
91 | protocol.) |
92 | ||
93 | Overview | |
94 | -------- | |
95 | We introduce a new repository format extension. Repositories with this | |
0ed8d8da | 96 | extension enabled use SHA-256 instead of SHA-1 to name their objects. |
752414ae JN |
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 | ||
0ed8d8da | 101 | SHA-256 repositories cannot be read by older versions of Git. |
752414ae | 102 | |
0ed8d8da JN |
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 | |
752414ae | 105 | locally and can be verified using "git fsck". Object lookups use this |
0ed8d8da | 106 | mapping to allow naming objects using either their SHA-1 and SHA-256 names |
752414ae JN |
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 | |
0ed8d8da | 116 | SHA-256 form and record the mapping in the bidirectional mapping table |
752414ae JN |
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 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
0ed8d8da | 125 | A SHA-256 repository uses repository format version `1` (see |
752414ae JN |
126 | Documentation/technical/repository-version.txt) with extensions |
127 | `objectFormat` and `compatObjectFormat`: | |
128 | ||
129 | [core] | |
130 | repositoryFormatVersion = 1 | |
131 | [extensions] | |
0ed8d8da | 132 | objectFormat = sha256 |
752414ae JN |
133 | compatObjectFormat = sha1 |
134 | ||
45fa195f ÆAB |
135 | The combination of setting `core.repositoryFormatVersion=1` and |
136 | populating `extensions.*` ensures that all versions of Git later than | |
0ed8d8da | 137 | `v0.99.9l` will die instead of trying to operate on the SHA-256 |
45fa195f | 138 | repository, instead producing an error message. |
752414ae | 139 | |
45fa195f ÆAB |
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 | |
752414ae JN |
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 | |
0ed8d8da | 155 | hexadecimal digit sha256-name, plus names derived from those (see |
752414ae JN |
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 | ||
0ed8d8da JN |
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. | |
752414ae JN |
164 | |
165 | Object format | |
166 | ~~~~~~~~~~~~~ | |
167 | The content as a byte sequence of a tag, commit, or tree object named | |
0ed8d8da JN |
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 | |
752414ae JN |
170 | refers to other objects by their sha1-names. |
171 | ||
0ed8d8da JN |
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 | |
752414ae | 174 | instead of sha1-names. Because a blob object does not refer to any |
0ed8d8da | 175 | other object, its sha1-content and sha256-content are the same. |
752414ae | 176 | |
0ed8d8da | 177 | The format allows round-trip conversion between sha256-content and |
752414ae JN |
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 | |
0ed8d8da | 184 | today. The content that is compressed and stored uses sha256-content |
752414ae JN |
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: | |
0ed8d8da | 255 | - A copy of the 20-byte SHA-256 checksum at the end of the |
752414ae JN |
256 | corresponding packfile. |
257 | ||
0ed8d8da | 258 | - 20-byte SHA-256 checksum of all of the above. |
752414ae JN |
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 | |
0ed8d8da | 266 | (sha256-name SP sha1-name LF)* |
752414ae JN |
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 | |
0ed8d8da JN |
292 | and sha256-names. The lookup proceeds similarly to ordinary object |
293 | lookups. For example, to convert a sha1-name to a sha256-name: | |
752414ae JN |
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 | |
0ed8d8da JN |
301 | c. Read the corresponding entry in the full sha256-name table. |
302 | That is the object's sha256-name. | |
752414ae JN |
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 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
0ed8d8da JN |
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. | |
752414ae JN |
320 | |
321 | Fetch | |
322 | ~~~~~ | |
323 | Fetching from a SHA-1 based server requires translating between SHA-1 | |
0ed8d8da | 324 | and SHA-256 based representations on the fly. |
752414ae JN |
325 | |
326 | SHA-1s named in the ref advertisement that are present on the client | |
0ed8d8da | 327 | can be translated to SHA-256 and looked up as local objects using the |
752414ae JN |
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 | |
0ed8d8da | 332 | mentioned by the server are converted to SHA-256 when looking them up |
752414ae JN |
333 | locally. |
334 | ||
335 | After negotiation, the server sends a packfile containing the | |
0ed8d8da | 336 | requested objects. We convert the packfile to SHA-256 format using |
752414ae JN |
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.) | |
0ed8d8da | 351 | 3. convert to sha256: open a new (sha256) packfile. Read the topologically |
752414ae | 352 | sorted list just generated. For each object, inflate its |
0ed8d8da JN |
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. | |
752414ae | 355 | 4. sort: reorder entries in the new pack to match the order of objects |
0ed8d8da | 356 | in the pack the server generated and include blobs. Write a sha256 idx |
752414ae JN |
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 | ~~~~~~~~~~~~~~ | |
0ed8d8da | 388 | We add a new field "gpgsig-sha256" to the commit object format to allow |
752414ae | 389 | signing commits without relying on SHA-1. It is similar to the |
0ed8d8da JN |
390 | existing "gpgsig" field. Its signed payload is the sha256-content of the |
391 | commit object with any "gpgsig" and "gpgsig-sha256" fields removed. | |
752414ae JN |
392 | |
393 | This means commits can be signed | |
394 | 1. using SHA-1 only, as in existing signed commit objects | |
0ed8d8da | 395 | 2. using both SHA-1 and SHA-256, by using both gpgsig-sha256 and gpgsig |
752414ae | 396 | fields. |
0ed8d8da | 397 | 3. using only SHA-256, by only using the gpgsig-sha256 field. |
752414ae JN |
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 | ~~~~~~~~~~~ | |
0ed8d8da | 405 | We add a new field "gpgsig-sha256" to the tag object format to allow |
752414ae | 406 | signing tags without relying on SHA-1. Its signed payload is the |
0ed8d8da | 407 | sha256-content of the tag with its gpgsig-sha256 field and "-----BEGIN PGP |
752414ae JN |
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 | |
0ed8d8da | 412 | 2. using both SHA-1 and SHA-256, by using gpgsig-sha256 and an in-body |
752414ae | 413 | signature. |
0ed8d8da | 414 | 3. using only SHA-256, by only using the gpgsig-sha256 field. |
752414ae JN |
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 | ||
0ed8d8da JN |
421 | The mergetag field in the sha256-content of the same commit contains the |
422 | sha256-content of the same tag. | |
752414ae JN |
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 | |
24966cd9 | 459 | refer to new, non-UNREACHABLE_GARBAGE packs (or loose objects). |
752414ae JN |
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 | ~~~~~~~~~~~~~~~ | |
0ed8d8da | 497 | The conversion from sha1-content to sha256-content retains any |
752414ae JN |
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 | ~~~~~~~~~~ | |
0ed8d8da | 516 | For the same reason, a sha256 repository cannot borrow objects from a |
752414ae JN |
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 | |
0ed8d8da | 524 | sha256-names. That migration is expected to happen separately (for |
752414ae JN |
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 | ~~~~~~~~~~~~~~~~ | |
0ed8d8da | 530 | Until Git protocol gains SHA-256 support, using SHA-256 based storage |
752414ae | 531 | on public-facing Git servers is strongly discouraged. Once Git |
0ed8d8da | 532 | protocol gains SHA-256 support, SHA-256 based servers are likely not |
752414ae | 533 | to support SHA-1 compatibility, to avoid what may be a very expensive |
031fd4b9 | 534 | hash re-encode during clone and to encourage peers to modernize. |
752414ae JN |
535 | |
536 | The design described here allows fetches by SHA-1 clients of a | |
0ed8d8da | 537 | personal SHA-256 repository because it's not much more difficult than |
752414ae JN |
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 | |
0ed8d8da | 547 | hexadecimal digit) or SHA-256 (64 hexadecimal digit) objects then the |
752414ae JN |
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 | ||
0ed8d8da | 562 | Fortunately SHA-256 and SHA-1 have different lengths. If Git starts |
752414ae JN |
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 | |
0ed8d8da | 574 | objects using SHA-256. This allows users to test the code with no |
752414ae JN |
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 | ||
0ed8d8da | 579 | 2. ("early transition") Allow both SHA-1 and SHA-256 object names in |
752414ae JN |
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 | ||
0ed8d8da JN |
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 | |
752414ae JN |
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 | |
0ed8d8da | 591 | SHA-256 and write output using SHA-256. This is safer than mode 3 |
752414ae JN |
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 | ||
0ed8d8da | 601 | git --output-format=sha1 log abac87a^{sha1}..f787cac^{sha256} |
752414ae | 602 | |
0ed8d8da JN |
603 | Choice of Hash |
604 | -------------- | |
031fd4b9 | 605 | In early 2005, around the time that Git was written, Xiaoyun Wang, |
752414ae JN |
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 | ||
0ed8d8da JN |
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. | |
752414ae JN |
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 | ||
0ed8d8da JN |
624 | 2. High quality implementations should be widely available (e.g., in |
625 | OpenSSL and Apple CommonCrypto). | |
752414ae JN |
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 | ||
0ed8d8da | 634 | We choose SHA-256. |
752414ae JN |
635 | |
636 | Transition plan | |
637 | --------------- | |
638 | Some initial steps can be implemented independently of one another: | |
639 | - adding a hash function API (vtable) | |
0ed8d8da | 640 | - teaching fsck to tolerate the gpgsig-sha256 field |
752414ae JN |
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 | |
0ed8d8da | 667 | - ^{sha1} and ^{sha256} revision notation |
752414ae JN |
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 | |
0ed8d8da | 675 | - convert the fetched packfile to sha256 format and generate an idx |
752414ae JN |
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" | |
0ed8d8da | 683 | section). In particular this allows users to verify SHA-256 signatures |
752414ae JN |
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 | |
0ed8d8da | 689 | new, more futureproof SHA-256 object names. |
752414ae JN |
690 | |
691 | When objectFormat and compatObjectFormat are both set, commands | |
0ed8d8da | 692 | generating signatures would generate both SHA-1 and SHA-256 signatures |
752414ae JN |
693 | by default to support both new and old users. |
694 | ||
0ed8d8da | 695 | In projects using SHA-256 heavily, users could be encouraged to adopt |
752414ae JN |
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 | |
0ed8d8da | 700 | can verify SHA-256 signatures and have converted their existing |
752414ae | 701 | repositories to support verifying them, we can add support for a |
0ed8d8da | 702 | setting to generate only SHA-256 signatures. This is expected to be at |
752414ae JN |
703 | least a year later. |
704 | ||
705 | That is also a good moment to advertise the ability to convert | |
0ed8d8da | 706 | repositories to use SHA-256 only, stripping out all SHA-1 related |
752414ae JN |
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 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
3eae30e4 | 733 | (e.g. https://lore.kernel.org/git/22708.8913.864049.452252@chiark.greenend.org.uk/ ) |
752414ae JN |
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 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
0ed8d8da JN |
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 | |
752414ae JN |
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 | |
0ed8d8da | 754 | attest to the sha1-name and sha256-name referring to the same object. |
752414ae JN |
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>" | |
0ed8d8da | 763 | and "hash sha1 parent <sha1-name>" to the sha256-content of a signed |
752414ae JN |
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" | |
0ed8d8da | 767 | field to suppress including "hash sha1" fields in the sha256-content |
752414ae JN |
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 | |
0ed8d8da | 775 | being streamed to disk and having its sha256-name calculated should be |
752414ae JN |
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 | |
3eae30e4 | 786 | http://lore.kernel.org/git/20170304011251.GA26789@aiede.mtv.corp.google.com |
752414ae JN |
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 | ||
13f5e098 ÆAB |
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 | ||
3eae30e4 JK |
823 | [1] http://lore.kernel.org/git/CA+55aFzJtejiCjV0e43+9oR3QuJK2PiFiLQemytoLpyJWe6P9w@mail.gmail.com/ |
824 | [2] http://lore.kernel.org/git/CA+55aFz+gkAsDZ24zmePQuEs1XPS9BP_s8O7Q4wQ7LV7X5-oDA@mail.gmail.com/ | |
825 | [3] http://lore.kernel.org/git/20170306084353.nrns455dvkdsfgo5@sigill.intra.peff.net/ | |
826 | [4] http://lore.kernel.org/git/20170304224936.rqqtkdvfjgyezsht@genre.crustytoothpaste.net | |
827 | [5] https://lore.kernel.org/git/CAJo=hJtoX9=AyLHHpUJS7fueV9ciZ_MNpnEPHUz8Whui6g9F0A@mail.gmail.com/ |