Stream Ciphers and Computational Security

Carla Ràfols

Theory Session 2b

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 1 / 27

 Computational Security

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 2 / 27

Computational Security

A new paradigm for Cryptography

An encryption scheme is considered secure if EFFICIENT adversaries cannot infer
any information about the plaintext (except with some very tiny probability).

What does it mean precisely that an algorithm is efficient?

What does it mean that a probability is tiny?
Need to make this precise.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 3 / 27

Concrete vs Asymptotic

Two different views of “Efficiency”:

Asymptotic: We consider algorithms that take inputs of length λ, and we
consider the running time as a function of λ.

Concrete: We count the number of steps that an algorithm does.

Two different views of “Tiny probability”:

Asymptotic: We consider algorithms that take inputs of length λ, and we
consider the probability of breaking security as a function of λ. Tiny
probability= “ a function that decreases very fast”

Concrete: Some very small number, i.e. 2−80 .

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 4 / 27

What do we mean by efficient?

Definition
An algorithm A is said to be efficient (or polynomial-time) if there exists a
positive polynomial p such that, for any n ∈ N, when A receives as input a
bitstring of length n, it finishes in at most p(n) steps.

Important note: observe that the polynomial is the same for all n ∈ N.

Example
1) is schoolbook multiplication polynomial time? 2) and schoolbook factoring?

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 5 / 27

Example
School Book Multiplication

School book algorithm that takes two integers of λ/2 bits and multiplies them
 2  2
needs approximately λ2 multiplications and λ2 sums. We count sums and
multiplications as one step.
This algorithm takes as input two integers of length λ2 and terminates in at most
λ2
4 steps, so this algorithm runs in polynomial time.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 6 / 27

Example
School Book Factoring

In schoolbook factoring we try to factor by finding

√ a prime factor by exhaustive
search. The algorithm in the worst case does n steps. If n has λ bits,
√ λ
n = 2 2 ⇒ not polynomial time.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 7 / 27

Secure and Efficient Encryption, formally

An encryption scheme is composed of three algorithms: (KeyGen, Enc, Dec).

(KeyGen, Enc, Dec) are algorithms that should run in time polynomial1 in the
security parameter λ.

The scheme is secure against a certain type of attack (e.g. a key recovery
attack) if no attack is known that runs in polynomial time in λ.

Observe:
Larger λ means slower (KeyGen, Enc, Dec), but better security (security has
costs!).

1 To indicate this, in several books you will find that KeyGen takes as input 1λ = 11 . . . 1 and

not λ. This is so that KeyGen takes as input a bitstring of length λ.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 8 / 27
 Security Level

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 9 / 27

Security Level: Definition

Definition
A cryptographic scheme has n-bit security if the best known attack requires 2n
steps.

What is the relation with the security parameter λ (the keylength)?

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 10 / 27

Brute Force Attacks

c = 0101101010101010...

Alice (sender) Bob (receiver)

When a scheme has perfect secrecy, brute force attacks (that try every
possible key) do not work.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 11 / 27

Brute Force Attacks

c = 0101101010101010...

Alice (sender) Bob (receiver)

When a scheme has perfect secrecy, brute force attacks (that try every
possible key) do not work.
This is because every ciphertext is compatible with every message, so we
cannot try if a key works.
Example: suppose m ∈ {0, 1}, k ∈ {0, 1}. Every choice of k leads to a
possible m, but we cannot decide what is the valid choice.
This is different from trying all combinations of a safe, when you find the
right one the door will open.
Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 11 / 27
Brute Force Attacks

c = 0101101010101010...

Alice (sender) Bob (receiver)

If the keylength is λ, then we have seen that AT BEST the first λ bits of c
are independent of m.
When more than λ bits are sent, there is enough redundancy in messages
that one attack that will always work is to try all the possible keys of length
λ to try to decrypt.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 12 / 27

Security Parameter vs Security Level

Lemma
The security level of a cryptographic scheme with security parameter λ is at most
n = λ.
Proof:
Since a brute force attack is always possible (since we assume more than λ bits
are sent), the number of steps necessary to attack a scheme is at most 2λ .

But very often attacks better than brute force exist, and the security level
when the key is of size λ is n = f (λ) < λ.
Example: RSA keys2 with bit length of λ = 1024 gives you approximately
n = 80 bit security.
∗
Example: A hash function H : {0, 1} → {0, 1}n always has security level
n ≤ λ/2.

2 RSA is a widely used encryption scheme to be seen later in this course

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 13 / 27
General Approach

Design a cryptographic primitive (e.g. encryption), study the best attack and
choose key length to have the desired security level.

But... What is a good security level by

today’s standards?
Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 14 / 27
Security Level

A minimum of 80 bits;
More like 100 -112 bits for good mid-term security.
128 bits - very strong security.

([Link] and [Link], Understanding Cryptography)

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 15 / 27

Efficient Algorithms Summary

In most cases, it is covenient to parameterize cryptographic algorithms by λ

the key length.
The running time of the algorithm and possible attackers is considered
asymptotically: algorithms should be polynomial time in λ and attackers
NOT polynomial time.
But when we consider implementation, we need to choose a particular value
of λ. For this we consider the concrete cost of the computational resources
necessary to run the best possible attack;
For now, a choice of n around 100 − 128 is expected to give good long term
security.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 16 / 27

 Probabilistic Attackers

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 17 / 27

Brute Force Attack, Revisited

c = 0101101010101010...

Alice (sender) Bob (receiver)

Eve does not try all possible keys, instead she chooses one uniformly at
random. What is her probability of success?

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 18 / 27

Brute Force Attack, Revisited

c = 0101101010101010...

Alice (sender) Bob (receiver)

Eve does not try all possible keys, instead she chooses one uniformly at
1
random. What is her probability of success? ϵ = λ .
2
This attack is a probabilistic version of the brute force attack and is always
possible, but it does not seem critical if ϵ is sufficiently small.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 18 / 27

What Qualifies as Sufficiently Small?
Concrete Approach

To have a good level of security we would like that the best attack succeeds with
probability less than 2−80 , and ideally 2−128 .
If ϵ ≥ 230 , scheme considerem broken.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 19 / 27

Brute Force Attack, Revisited

c = 0101101010101010...

Alice (sender) Bob (receiver)

Eve does not try all possible keys, instead she chooses one uniformly at
1
random. What is her probability of success? ϵ = λ .
2

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 20 / 27

Negligible Function: Motivation

Repeating the attack ℓ times, the probability that at least one attack is
successful is:

1 − Pr[no attack is succesful] = 1 − (1 − ϵ)ℓ ≈ 1 − (1 − ℓϵ) = ℓϵ.

An efficient adversary can do a polynomial number of attempts, ℓ = p(λ).

It should be that if the adversary does ℓ = p(λ) attempts, ℓϵ = p(λ)ϵ is still
small.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 21 / 27

Negligible Function: Definition

Definition
A function ϵ is negligible if for all polynomial p, limn→∞ p(n)ϵ(n) = 0.

Definition
A cryptographic algorithm is secure against a certain type of attack if the best
probabilistic attack known has negligible sucess in the security parameter λ.

1
Example: If the best possible attack is trying a random key, ϵ = is a
2λ
negligible function, and the scheme is considered secure.

p(λ)
If the attack is repeated p(λ) times, 2λ
is still very small, so it does not matter!

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 22 / 27

 Extra Material

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 23 / 27

Computational Resources are Money!!

M. Rosulek. The Joy of Cryptography, values for 2018. Using general purpose CPU.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 24 / 27

Specialized Hardware

Cost can maybe be brought down with specialized hardware, specially if you
can amortize hardware use.

”For long-lived computations, the dominating cost is not the one-time cost of the
hardware, but rather the cost of electricity powering the hardware. Because of
that, it can be much cheaper to manufacture special-purpose hardware.
Depending on the nature of the computation, special-purpose hardware can be
significantly more energy-efficient. This is the situation with the Bitcoin
cryptocurrency. Mining Bitcoin requires evaluating the SHA-256 cryptographic
hash function as many times as possible, as fast as possible. When mining Bitcoin
today, the only economically rational choice is to use special purpose hardware
that does nothing except evaluate SHA-256, but is millions (maybe billions) of
times more energy effcient than a general-purpose CPU evaluating SHA-256.”

(Chapter 4, [Link]’s book)

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 25 / 27

Exercise (Paar and Pelzl, chap.1)

This exercise should convince you that even spending a lot of money in
hardware, 128 bit security takes a loooong time to break.

We consider the long-term security of the Advanced Encryption Standard (AES)

with a key length of 128-bit with respect to exhaustive key-search attacks. AES is
perhaps the most widely used symmetric cipher at this time.
Assume that an attacker has a special purpose application specific integrated
circuit (ASIC) which checks 5 · 108 keys per second, and she has a budget of
1 million dollars. One One ASIC costs $50, and we assume 100 % overhead
for integrating the the ASIC (manufacturing the printed circuit boards, power
supply, cooling, etc.). How many ASICs can we run in parallel with the given
budget? How long does an average key search take? Relate this time to the
age of the Universe, which is about 1010 years.

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 26 / 27

Exercise (Paar and Pelzl, chap. 1)

We try now to take advances in computer technology into account.

Predicting the future tends to be tricky but the estimate usually applied is
Moore’s Law, which states that the computer power doubles every 18 months
while the costs of integrated circuits stay constant. How many years do we
have to wait until a key-search machine can be built for breaking AES with
128 bit with an average search time of 24 hours? Again, assume a budget of
$1 million (do not take inflation into account).

Carla Ràfols Introduction to Cryptography and Security Theory Session 2b 27 / 27