Note: All analysis problems can (and should!) be solved using the “estimation with powers of two” techniques from the class reading. You should always show all steps of your work, with explanations as necessary (don’t just write formulas!).
In class we did some calculations of how large a key would need to be to protect against brute force attacks under reasonable assumptions. For this problem, you should do a similar analysis but using extreme, over-the-top assumptions about the attacker’s computational capabilities (obviously far, far beyond what any conventional computer, now or ever, could do).
Consider if you could convert the entire planet into one big computer (suggestion: read The Hitchhiker’s Guide to the Galaxy if you haven’t) — do some research and find a good estimate for how many atoms are in the Earth, making sure you use a reliable source and include a citation in your answer. Assume that you can make a logic gate using just 8 atoms. Next, assume that you can clock those gates at the fastest imaginable speed, the frequency of ultraviolet light, which would be a 1,000 THz computer, and testing a key takes 1000 Boolean operations. Finally, a “super-secure” cipher is one that cannot be brute-forced (on average) in under 128 years. What key size would need to be used so that a cipher is “super-secure” against attacks using this ultra-fast full-planet computer?
Even if you could build huge key-cracking machines, you still have to power them, and power is proportional to processors (doubling the processors doubles the power usage). The most efficient (publicly-known!) hardware that can be used for brute forcing keys is a machine known as RIVYERA S6. At the average cost of energy in the U.S., $1 will provide enough energy to crunch through around 8 quadrillion (8,000 trillion or 8,000,000 billion) keys.
How much would the power cost (on average) to brute force a 56-bit DES key?
How much would the power cost (on average) to brute force a 128-bit AES key?
In the Bitcoin system, transactions are stored in blocks that have an 80 byte header, and “Bitcoin mining” involves repeatedly hashing modifications of the header until a hash is found that ends in a certain number of zero bits (this is not entirely accurate, but close enough for this homework question!). When you do the labtainer lab (last question, below), you’ll experiment with a small version of this problem in “Task 4.” The necessary number of zero bits is set so that the expected time for some miner to find the right input is around 10 minutes, and this length has increased over time as more and faster miners have come online. Currently, in September 2020, the hash must end in 76 zeroes. Bitcoin miners all use specially-built hardware these days – let’s see how long it would take to successfully find such a hash input on a regular system with standard software.
On my desktop computer, the OpenSSL implementation of SHA256 can hash roughly 4 million 80-byte blocks per second. There are 8 cores, so the overall number of hashes that can be computed per second is 8 times that. The probability of some randomly chosen input having a hash that ends in 76 zeros is basically \(2^{-76}\), so a single test has a Bernoulli distribution with \(p=2^{-76}\). The number of trials needed before the first success has a Geometric distribution. With those hints, first find the expected number of trials before mining succeeds. Then calculate the expected time to success, using the rate of 4 million trials per second per core, and using 8 cores. Note that all values here are nicely approximated by powers of two, so use the “estimation by powers of two” techniques for your calculations, and show your work! Your final answer should be as a meaningful number, such as “16 seconds,” or “21 days,” or “2,000 years” (and not something like “\(2^{31}\) seconds”).
While not part of the homework, you might find it interesting to see how the speed of your own personal system compares. If you can run openssl (either natively or in the labtainer virtual machine), then run this command:
openssl speed -bytes 80 -seconds 10 sha256The output on my system includes the line:
Doing sha256 for 10s on 80 size blocks: 33933618 sha256's in 10.00sThis says it could do 33,933,618 SHA256 hashes in 10 seconds, so about 3,393,361.8 per second. I rounded up a little when I said 4 million per second.
Bitcoin blocks are identified by their hash, and it would break the system if two blocks had the same hash. Unfortunately, since a large number of bits are constrained to be zero, this reduces the overall number of possible hashes and increases the probability of a collision. Let’s see if this is a problem. Solving this question involves using the techniques and estimations from the section on the “Birthday Problem” in the assigned reading.
Hash values are 256 long, and assume that every hash ends in 76 zero bits. The current bitcoin blockchain has around 650,000 blocks, so let’s round that up to a million blocks. Estimate the probability that two blocks have the same hash value (assume all but the 76 fixed bits are random and uniformly distributed).
Let’s turn the problem around: How many blocks would need to be hashed before there’s roughly probability 1/2 of a repeated hash?
One of the most popular hash functions in the 1990’s was MD5, which produces 128-bit hash values. Repeat the two calculations above for 128-bit hash values (still with 76 zero bits). (Note: MD5 has been shown to be very insecure with respect to collision resistance, so should not be used. While collision resistance isn’t really the right measure for applications like this one, MD5 should still be avoided!)
Complete the “macs-hash” labtainer exercise. Here are a few tips:
This lab requires putting some values into a spreadsheet and completion of both a lab report, using templates that are provided. When you start the lab, it will give you paths to both documents (as well as the lab writeup). Just right-click on those links to open them.
Make sure you complete the spreadsheet and lab report, and save them, before typing “stoplab”. Since “stoplab” bundles these into the .zip file that you will submit, they must be completed and saved before the “stoplab”!
From the original student window (not the labtainer window), you can type “checkwork” to see what the labtainer window thinks you have done or not done. You are encouraged to do this to make sure your actions are being recorded properly! In particular, it is looking for some specific actions that are described in the lab, and is not very smart about seeing alternatives. If you know shortcuts or simplified commands, do not use them - stick with what is described in the lab instructions.