7

I was just about to remove a feature from a site admin that I don't believe anyone is using. However I wanted to leave a message on the off-chance that someone is still using it. I was going to replace the HTML template with something to the effect of:

<p>This feature has been disabled.  If you need it back please ask engineering to revert #1234567890abcdef<p>

Obviously I realize this can easily be done in two commits. However I thought it was an interesting question from a cryptography angle.

Assuming you can only modify the hash itself, what are the chances that a hash actually exists that satisfies this property? As you shorten the hash (since git allows unique prefixes) presumably the chances of such a hash increase. What would the probability be for a 6-char prefix and how hard would it be to find?

gtd
  • 16,956
  • 6
  • 49
  • 65
  • I have marked this question for closure, because I believe that it is not a *practical problem for the programming profession*. On the off chance that it is, it's better suited for http://crypto.stackexchange.com/ – Andrew Savinykh Jun 05 '13 at 23:19

3 Answers3

2

This script does something similar with short hashes.

It's easy to calculate the probability, assuming the (SHA-1) hash function is evenly distributed (which is kind of the point). Here's an example SHA-1 hash:

0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33

40 characters. 4 bits per character. 2^(number-of-characters * 4) possibilities.

So if you want the first 7 nibbles (hex characters) of the SHA-1, you're looking at 2^(7*4) == 1/268435456 chance of finding the correct hash. (which shouldn't be too difficult for a script, as you can see!)

mpontillo
  • 13,559
  • 7
  • 62
  • 90
  • Note, I'm not sure the script can actually find 7 nibbles easily (its example usage uses less) but in theory, [there are tools](http://www.golubev.com/hashgpu.htm) that can calculate *billions* of SHA-1 hashes per second. – mpontillo Jun 06 '13 at 15:53
1

You can do this if the hash:

  1. Is short. Simply try many times until the property is fulfilled. Cost is 2^n for an n bit hash. SHA-1's 160 bits are far too long for this to work. You can do this for the first few digits of the hash. About 8-12 hex digits (32-48 bits) should be feasible without too much effort.
  2. The hash has a mathematical structure that allows this. CRCs and similar hashes work like this. Not possible with typical cryptographic hashes like SHA-1.

In short you can't have a commit that contains its own hash.

CodesInChaos
  • 106,488
  • 23
  • 218
  • 262
-2

you can get the hash of an object with git hash-object <fileName> take a look at this post How to assign a Git SHA1's to a file without Git?

Although I don't think what you want to do is possible. Editing the file will change the hash of the file. So if you calculate the hash and put that value into the file, the hash of the file has now changed. So the hash that you have saved in the file wont be the correct hash.

Community
  • 1
  • 1
Connr
  • 408
  • 6
  • 10