0:00

In practice, it is common to design a cryptosystem that is computationally secure.

Computational security relies on two assumptions.

First, the attackers are computationally limited,

which is applicable to all real world systems.

It is said that a cryptosystem is computationally

secure when the computational requirements become

so large that it becomes practically

infeasible to break their cipher in a reasonable time period.

Second, the cryptosystem relies on

mathematical problems that are assumed to be difficult to solve.

Even though these problems have not been proven to be difficult,

they are widely believed to be practically infeasible to compute.

We will revisit some of the mathematical problems that become the basis for

this computational hardness assumption such as

prime factorization or discrete log problem.

We will revisit these later when we discuss more mathematics.

In this video, let's farther study

the first assumption that the attacker is computationally bounded.

Suppose the attacker wants to find a key by conducting a brute-force search.

Previously, we discussed how the attacker effort grows with two to the nth power,

where n is the key length.

Now, let's do a back-of-the-envelope type of calculations to provide a perspective about

the feasibility of doing brute-force attacks

by computing the time it takes in units that are familiar to us,

namely seconds and years.

A brute-force attacker tries the possible keys one by one until it finds the correct one,

suppose the attacker has a machine that can perform x decryptions per second.

The value of x depends on many factors including the choice of the cipher algorithm,

the implementation methods of the cipher,

the processing speed of the attacker's machine, and so on.

Let's arbitrarily choose a value for x and suppose

that the attacker can compute 10 million decryptions per second.

That is 10th to the 7th power decryptions per second.

Then let's look at how long it will take the attacker to brute-force

the key depending on the key size.

We look at the case of the key size, or n,

being 56 bits, 128 bits,

and 168 bits, because these are

the key lengths in some of the popularly used symmetric ciphers.

And given the key length n,

the possible number of key is two to the nth power.

In the best case,

the attacker gets very lucky and finds the key in its first try.

And in the worst case,

the attacker tries all possible keys and finds the key in its last try,

or the two to the nth power try.

Because the attacker is randomly choosing the keys to try,

on the average case,

it will find the key in the middle between those two extreme cases.

That is, it will find the key when it tries half of the possible keys.

So, on average, it will take the attacker two to the nth power divided by two,

or two to the n minus first power decryption attempts to find the key.

And that number of decryption attempts can be converted into time,

because we know that it takes one second for

the attacker to perform 10 million decryption attempts.

For example, when n is equal to 56 or the key is 56 bits long,

it takes the attacker 3.6 billion seconds for brute-forcing.

And, this value can be computed by taking two to

the 55th power attempts and dividing that by 10 to the 7th attempts per seconds.

This average time to conduct brute-force in years is 114 years,

which makes the attack unrealistic,

because 114 years is a long time for lifespan in cryptography.

Now, let's introduce a stronger attacker

that has a super computer with many processing course.

And, suppose that this new attacker supports

a processing capability that is million times greater than the previous attacker.

In other words, it can compute 10 to the 13th power decryption attempts per second.

Using the same logic as before,

the stronger attacker can actually crack the 56-bit long key in approximately one hour.

And now, the attack becomes realistic.

However, as the key size gets bigger,

for example with n being 128 bits or when the key is 128 bits long,

it takes 5.4 times 10 to the 17th power years.

That is 16 zeros following the decimals five and four.

When n is equal to 256,

it takes 5.9 times 10 to the 29th power years.

To put that into perspective,

the age of the universe is about 14 billion years or 14 times 10 to the 9th years.

In general, the computational effort by the attacker

conducting brute-force searching grows by two to the nth power as n grows.

In other words, it grows exponentially with the key size.

Therefore, the cryptosystem designer can quickly make

the brute-force impractical by increasing the key size.