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