Lab 3: Understanding the computational limitation of the modern processor and exponential growth¶
- Exponential functions
- CPU cycles
- Moore's law
- Bremermann's limit
The cryptographic primitives that we have seen so far in class rely on the attacker having some upper limit on how much computation they can do. We call this type of security computational security. In this lab, we are going to investigate some of the constraints we impose on our attacker and reason whether they make sense.
Exponential Functions¶
Exponential functions grow very fast: "Would you rather have a million dollars or a penny on day one, doubled every day until day 30?"
def f():
pennies = 1
for i in range(1, 31):
pennies = 2 * pennies
print(pennies/100)
f()
That's more than 10 million dollars!
Story of the chessboard and the wheat problem:¶
"The inventor of chess request his ruler give him wheat according to the wheat and chessboard problem. The ruler laughs it off as a meager prize for a brilliant invention, only to have court treasurers report the unexpectedly huge number of wheat grains would outstrip the ruler's resources."
Source: Wikipedia
print(2**64)
Brute force attacks on modern CPUs¶
In a bruteforce attack, the attacker systematically checks all possible passwords and passphrases until the correct one is found.
# trying to bruteforce a weak password made of 4 digits
def try_key(key):
# returns true if key is found
pass
def bruteforce():
for i in range(0, 10**4):
if try_key(i):
return i
# trying to bruteforce a 128 bit key
def try_key(key):
# returns true if key is found
pass
def bruteforce():
for i in range(0, 2**128):
bytes_val = i.to_bytes(16, 'big')
if try_key(bytes_val):
return bytes_val
When will this attack stop being possible? How long should the key be so that we keep attackers at bay?
The answer to these question depends on two things:
The time it takes to try one key.
The total number of keys that has to be tried.
The time it takes to try one key:
Set in 2011, the Guinness World Record for the highest CPU clock rate is 8.42938 GHz. the record was then broken many times accross the years. The latest one was in late 2022 when an Intel Core i9-13900K was overclocked to 9.01 GHz. Source: Wikipedia
What does 9 GHZ mean?
1 Hz means one cpu instruction per second
1KHz kilo (k) — 1,000 cpu instructions per second
1MHz mega (M) — 1,000,000 (million) cpu instructions per second
1GHz giga (G) — 1,000,000,000 (billion) cpu instructions per second
1THZ tera(T) — 1,000,000,000,000 (trillion) cpu instructions per second
The time it takes to try one key:
Let's be generous and say that the attacker has the fastest computer on earth. Moreover, let's also assume that it takes only one cpu instruction to try one key (in reality it takes much more). This means the attacker can try 1,000,000,000 keys per second. One key can be tried in $1 * 10^{-9}$ seconds.
If your password is 20 bits long, how much time does the attacker need to crack your password?
# a 20 bit password has 2^{20} possible passwords
print(2**20)
Going through all the possible keys takes less than 1 second!
What if we increase the length of our key?¶
| key length |
Total number of keys |
|---|---|
| 2 bits |
4 |
| 4 bits |
16 |
| 8 bits |
256 |
| 16 bits |
65,536 |
| 32 bits |
4,294,967,296 |
| 64 bits |
18,446,744,073,709,551,616 |
| 128 bits |
340,282,366,920,938,463,463,374,607,431,768,211,456 |
| 256 bits |
115792089237316195423570985008687907853269984665640564039457584007913129639936 |
What if your password is 64 bits long?
# number of seconds to crack a 64 bit long password
# total number of passwords divided by the time it takes to break one password
# 2^44 seconds
seconds = 2**64/2**20
hours = seconds/60
days = hours/24
years = days//365
print(years)
What if your password is 256 bit long and there is a million million million million of those computers?¶
# number of seconds to crack a 256 bit long password
# total number of passwords divided by the time it takes to break one password
# 2^236 seconds
seconds = 2**256/2**20
hours = seconds/60
days = hours/24
years = days//365
# dividing the work between a million million million million computers
print(years//(1000000*1000000*1000000*1000000))
#the age of the universe is around 14billion years
print("Age of the universe in base 2")
print("2^" + str(math.log(14000000000)))
Instead of bruteforcing keys what if we are bruteforcing games or algorithms?
| Games | number of states |
|---|---|
| Tic-Tac-Toe | 3^9 |
| Checkers | 2^67 |
| Chess | 2^133 |
| Go (19 × 19) | 2^568 |
Moore's law¶
The number of transistors in a CPU and the clock speed are related in that the more transistors a CPU has, the faster it can operate, allowing for a higher clock speed.
Moore's law is the observation that the number of transistors in a dense integrated circuit (IC) doubles about every two years. Moore's law is an observation and projection of a historical trend.
Source: Wikipedia
Are we at risk if Moore's law continues to be true?¶
Note: some argue that it's already broken
NO FEAR! Physics is HERE!¶
Bremermann's limit¶
Bremermann's limit is a theoretical limit on the maximum rate of computation in a self-contained system, derived from the mass-energy equivalency and the Heisenberg uncertainty principle and is $\frac{c^2}{h}$ ≈ $1.36 × 10^{50}$ bits per second per kilogram.
For example, a computer with the mass of the entire Earth operating at Bremermann's limit could perform approximately $10^{75}$ (or roughly $2^{225}$ in base 2) mathematical computations per second. A 128-bit encryption key could be cracked in under $10^{-36}$ seconds, but a 256-bit key would take 2 minutes to crack and a 512-bit key would take $10^{72}$ years. Source: Wikipedia