Solving this problem requires not the use of the Birthday Paradox, but the Binominal Theorem. If we assume that SHA-1 follows the "random oracle" model, then each time we compute the SHA-1 of a random input, there is a 1 out of 2^32 chance that the SHA-1 residue will being with the hexdecimal string "deadbeef." You can find a nice discussion of the Binominal Theorem at: http://mathworld.wolfram.com/BinomialTheorem.html What does this have to do with the Binominal Theorem? For each random SHA-1, there is a 1 out of 2^32 chance that you will find the correct result, which means that there is a 2^32-1 out of 2^32 chance that you will not. (2^32-1) / (2^32) is very close to one. We probably won't find it on the first try. The odds of not finding it on the second try are (2^32-1) (2^32-1) -------- * -------- (2^32) (2^32) if p = (2^32-1) / (2^32), then the odds of not finding the SHA-1 on any of the 0..n tries is p^n. So to find out how many tries we need to use, we just need to find a value of n such that (2^32-1)^n / (2^32)^n < 0.5 If you work the math, you will find that, on average, you will need to perform 2^31 events for one of these to come out correctly. My computer can do 1 million SHA-1s in about 5 seconds, or about 200,000 SHA-1s per second. 2 billion / 200,000 = 10,000 seconds, or about 15 minutes. That's about how long it took, in fact.
2. Is there time after which your computer is guaranteed to find a file that begins with the string deadbeef? Why or why not?
No, your computer is never guaranteed to find such a solution. There might be a flaw in the SHA-1 algorithm and it might never come up with such a solution.
3. If such a file can be found, find it. How many other files do you think there may be?
I actually found a 128-byte file that both begins with 0xdeadbeef and has the SHA-1 that begins 0xdeadbeef. The file, in hex: % hexdump -C buf.sha1 00000000 de ad be ef d8 88 9a 5c 00 00 00 00 00 00 00 00 |.......\........| 00000010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00000080 % % openssl sha1 < buf.sha1 deadbeef34de2a599fd73611efa56840d85af835 % I had to iterate through 1,553,631,448 different files before I found this one, so I actually got lucky.download the file 4. Find a 5-letter combination of lower-case letters and numbers that has this MD5: f5a744dd3bbb7b759036b3845caafd80
gf3ds
5. Find a 7-digit decimal number represented as an ASCII string (e.g. "7777777") such that, when you compute the SHA-1 of the number's MD5 represented as a hexdecimal string, then append a newline, you get this value: 5a3ad15140a3a06e26d2061df31d2da748a57e89
# Find a 7-digit decimal number represented as an ASCII string such that, when you compute the SHA-1 of the number's MD5 represented as a hexdecimal string, you get this value: 7f06c04d59bd83605193621e8d0d693bd30cdc9e
# Find a 7-digit decimal number represented as an ASCII string such that, when you compute the SHA-1 of the number's MD5 in binary, you get this value: 0a2b5ab5c8296e0039abf4091726bd6c33537fc3
1234567
6. Crack this unix password: Ha0YFTpyToKcE
Harvard7. Imagine that you are a security officer working for a large government agency. You need to need to move large video files over the Internet to agents in the field. Assuming that the agents can successfully authenticate themselves to your system, design a protocol that allows them to transfer the video securely over the Internet. What sort of encryption do you want to use? There are two caveats:
* This is highly sensitive information, so many other governments may try to crack your system.
* Due to softare validation constraints, once the protocol is approved, it cannot be changed for the next 5 years. Write a page describing a protocol to solve this problem and why you decided to use various types of security/encryption mechanisms.