git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 04/39] t3404: prepare 'short SHA-1 collision' tests for SHA-256

From
brian m. carlson <sandals@crustytoothpaste.net>
Date
Jul 13, 2020, 02:48 UTC
Message-ID
<20200713024909.3714837-5-sandals@crustytoothpaste.net>
In-Reply-To
<20200713024909.3714837-1-sandals@crustytoothpaste.net>
From: Johannes Schindelin <johannes.schindelin@gmx.de>

The idea of the magic value "ac4f2ee" in this test is to make the reworded commit `collide2` have the same shortened ID as the commit `collide3`.

To port the same idea to the SHA-256 version of Git, we therefore need another magic value that causes the same collision, but this time with the SHA-256 version of the commit IDs.

In this patch, we add code guarded by `GIT_TEST_FIND_COLLIDER` to do exactly that. Essentially, a large number of integers is appended to the commit message "collide2" to find such a collision. To make it easier to find such a collision, we reduce the number of digits to 4.

The `t/oid-info/oid` file now lists the values found in that way, and the test cases are modified to use those values.

As the tests are no longer dependent on SHA-1, we also rename their titles to talk about "commit IDs" instead of "SHA-1s".

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 t/t3404-rebase-interactive.sh | 50 ++++++++++++++++++++++++++++-------
 1 file changed, 41 insertions(+), 9 deletions(-)
diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index 4a7d21f898..2fb2c581cb 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -30,6 +30,7 @@ Initial setup:
 . "$TEST_DIRECTORY"/lib-rebase.sh
 
 test_expect_success 'setup' '
+	test_oid_init &&
 	test_commit A file1 &&
 	test_commit B file1 &&
 	test_commit C file2 &&
@@ -1250,7 +1251,7 @@ test_expect_success 'rebase -i error on commits with \ in message' '
 	test_expect_code 1 grep  "	emp" error
 '
 
-test_expect_success SHA1 'short SHA-1 setup' '
+test_expect_success 'short commit ID setup' '
 	test_when_finished "git checkout master" &&
 	git checkout --orphan collide &&
 	git rm -rf . &&
@@ -1262,23 +1263,54 @@ test_expect_success SHA1 'short SHA-1 setup' '
 	)
 '
 
-test_expect_success SHA1 'short SHA-1 collide' '
+if test -n "$GIT_TEST_FIND_COLLIDER"
+then
+	author="$(unset test_tick; test_tick; git var GIT_AUTHOR_IDENT)"
+	committer="$(unset test_tick; test_tick; git var GIT_COMMITTER_IDENT)"
+	blob="$(git rev-parse collide2:collide)"
+	from="$(git rev-parse collide1^0)"
+	repl="commit refs/heads/collider-&\\n"
+	repl="${repl}author $author\\ncommitter $committer\\n"
+	repl="${repl}data <<EOF\\ncollide2 &\\nEOF\\n"
+	repl="${repl}from $from\\nM 100644 $blob collide\\n"
+	test_seq 1 32768 | sed "s|.*|$repl|" >script &&
+	git fast-import <script &&
+	git pack-refs &&
+	git for-each-ref >refs &&
+	grep "^$(test_oid t3404_collision)" <refs >matches &&
+	cat matches &&
+	test_line_count -gt 2 matches || {
+		echo "Could not find a collider" >&2
+		exit 1
+	}
+fi
+
+test_expect_success 'short commit ID collide' '
+	test_oid_cache <<-EOF &&
+	# collision-related constants
+	t3404_collision	sha1:6bcd
+	t3404_collision	sha256:0161
+	t3404_collider	sha1:ac4f2ee
+	t3404_collider	sha256:16697
+	EOF
 	test_when_finished "reset_rebase && git checkout master" &&
 	git checkout collide &&
-	colliding_sha1=6bcda37 &&
-	test $colliding_sha1 = "$(git rev-parse HEAD | cut -c 1-7)" &&
+	colliding_id=$(test_oid t3404_collision) &&
+	hexsz=$(test_oid hexsz) &&
+	test $colliding_id = "$(git rev-parse HEAD | cut -c 1-4)" &&
+	test_config core.abbrev 4 &&
 	(
 		unset test_tick &&
 		test_tick &&
 		set_fake_editor &&
-		FAKE_COMMIT_MESSAGE="collide2 ac4f2ee" \
+		FAKE_COMMIT_MESSAGE="collide2 $(test_oid t3404_collider)" \
 		FAKE_LINES="reword 1 break 2" git rebase -i HEAD~2 &&
-		test $colliding_sha1 = "$(git rev-parse HEAD | cut -c 1-7)" &&
-		grep "^pick $colliding_sha1 " \
+		test $colliding_id = "$(git rev-parse HEAD | cut -c 1-4)" &&
+		grep "^pick $colliding_id " \
 			.git/rebase-merge/git-rebase-todo.tmp &&
-		grep "^pick [0-9a-f]\{40\}" \
+		grep "^pick [0-9a-f]\{$hexsz\}" \
 			.git/rebase-merge/git-rebase-todo &&
-		grep "^pick [0-9a-f]\{40\}" \
+		grep "^pick [0-9a-f]\{$hexsz\}" \
 			.git/rebase-merge/git-rebase-todo.backup &&
 		git rebase --continue
 	) &&
Previous: brian m. carlsonNext: brian m. carlson
Message 22 of 44 in “SHA-256, part 3/3”
  1. 00/39 SHA-256, part 3/3brian m. carlson, Jul 13, 2020
  2. 01/39 t: make test-bloom initialize repositorybrian m. carlson, Jul 13, 2020
  3. 09/39 t6501: avoid hard-coded objectsbrian m. carlson, Jul 13, 2020
  4. 10/39 t7003: compute appropriate length constantbrian m. carlson, Jul 13, 2020
  5. 14/39 t7400: make hash size independentbrian m. carlson, Jul 13, 2020
  6. 06/39 t6101: make hash size independentbrian m. carlson, Jul 13, 2020
  7. 18/39 t8002: make hash size independentbrian m. carlson, Jul 13, 2020
  8. 11/39 t7063: make hash size independentbrian m. carlson, Jul 13, 2020
  9. 17/39 t7508: use $ZERO_OID instead of hard-coded constantbrian m. carlson, Jul 13, 2020
  10. 16/39 t7506: avoid checking for SHA-1-specific constantsbrian m. carlson, Jul 13, 2020
  11. 12/39 t7201: abstract away SHA-1-specific constantsbrian m. carlson, Jul 13, 2020
  12. 02/39 t1001: use $ZERO_OIDbrian m. carlson, Jul 13, 2020
  13. 21/39 t9300: abstract away SHA-1-specific constantsbrian m. carlson, Jul 13, 2020
  14. 22/39 t9300: use $ZERO_OID instead of hard-coded object IDbrian m. carlson, Jul 13, 2020
  15. 19/39 t8003: make hash size independentbrian m. carlson, Jul 13, 2020
  16. 37/39 ci: run tests with SHA-256brian m. carlson, Jul 13, 2020
  17. 38/39 docs: add documentation for extensions.objectFormatbrian m. carlson, Jul 13, 2020
  18. 39/39 t: remove test_oid_init in testsbrian m. carlson, Jul 13, 2020
  19. 07/39 t6301: make hash size independentbrian m. carlson, Jul 13, 2020
  20. 03/39 t3305: make hash agnosticbrian m. carlson, Jul 13, 2020
  21. 05/39 t6100: make hash size independentbrian m. carlson, Jul 13, 2020
  22. 04/39 t3404: prepare 'short SHA-1 collision' tests for SHA-256brian m. carlson, Jul 13, 2020
  23. 34/39 t: add test_oid option to select hash algorithmbrian m. carlson, Jul 13, 2020
  24. 29/39 http-fetch: set up git directory before parsing pack hashesbrian m. carlson, Jul 13, 2020
  25. 08/39 t6500: specify test values for SHA-256brian m. carlson, Jul 13, 2020
  26. 15/39 t7405: make hash size independentbrian m. carlson, Jul 13, 2020
  27. 33/39 Enable SHA-256 support by defaultbrian m. carlson, Jul 13, 2020
  28. 13/39 t7102: abstract away SHA-1-specific constantsbrian m. carlson, Jul 13, 2020
  29. 24/39 t9350: make hash size independentbrian m. carlson, Jul 13, 2020
  30. 25/39 t9500: ensure that algorithm info is preserved in configbrian m. carlson, Jul 13, 2020
  31. 20/39 t8011: make hash size independentbrian m. carlson, Jul 13, 2020
  32. 26/39 t9700: make hash size independentbrian m. carlson, Jul 13, 2020
  33. 27/39 t5308: make test work with SHA-256brian m. carlson, Jul 13, 2020
  34. 28/39 t0410: mark test with SHA1 prerequisitebrian m. carlson, Jul 13, 2020
  35. 35/39 t: allow testing different hash algorithms via environmentbrian m. carlson, Jul 13, 2020
  36. 36/39 t: make SHA1 prerequisite depend on default hashbrian m. carlson, Jul 13, 2020
  37. 32/39 setup: add support for reading extensions.objectformatbrian m. carlson, Jul 13, 2020
  38. 30/39 builtin/verify-pack: implement an --object-format optionbrian m. carlson, Jul 13, 2020
  39. 31/39 bundle: add new version for use with SHA-256brian m. carlson, Jul 13, 2020
  40. Junio C HamanoJul 13, 2020
  41. SZEDER GáborJul 13, 2020
  42. Johannes SchindelinJul 15, 2020
  43. Junio C HamanoJul 15, 2020
  44. 23/39 t9301: make hash size independentbrian m. carlson, Jul 13, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.