Computer security - Appunti

Intro to computer security

Basic security requirements

CIA paradigm:

• Confidentiality: information can be accessed only by authorized entities;
• Integrity: information can be modified only by authorized entities and only in the way such entities are entitled to modify it;
• Availability: information must be available to all parties who have a right to access it.

Security as an engineering problem

• Vulnerability: something that allows to violate one of the constraints of the CIA paradigm;
• Exploits: a specific way to use one or more vulnerabilities to accomplish a specific objective that violates the constraints;
• Assets: identifies what is valuable for an organization;
• Threats: potential violation of CIA;
• Risk: statistical and economical evaluation of the exposure to damage because of the presence of vulnerabilities and threats.

RISK = Asset × Vulnerabilities × Threats

Asset, vulnerabilities: controllable variables

Independent variable

SECURITY: balance (reduction of vulnerabilities + damage containment) vs cost.

INTRO TO COMPUTER SECURITY 1

Cryptography

The study of techniques to allow secure communication and data storage in presence of attackers.

Features provided:

• Confidentiality: data can be accessed only by chosen entities;
• Integrity/freshness: detect/prevent tampering or replays;
• Authenticity: data and their origin are certified;
• Non-repudiation: data creator cannot repudiate created data.

Advanced features: proofs of knowledge/computation.

Kerchoff’s six principles for a good cipher apparatus

1. It must practically, if not mathematically, unbreakable;
2. It should be possible to make it public, even to the enemy;
3. The key must be communicable without written notes and changeable whenever the correspondents want;
4. It must be applicable to telegraphic communication;
5. It must be portable, and should be operable by a single person;
6. Given the operating environment, it should be easy to use.

Randomness

Randomness characterizes a generative process, not a variable or a number.

Cipher definitions

DATA

plaintext space: set of possible messages ∈P ptx P

ciphertext space: set of possible ciphertext ∈C ctx C

CRYPTOGRAPHY 1

key space: set of possible keys K

FUNCTIONS

Encryption function: E P K C: × →

Decryption function D D K P: × →

Correctness: we need ′ ′P∀ptx ∈ s.t.D(E(ptx, ) =k, k k), k ptx

Providing confidentiality

GOAL: prevent anyone not authorized form being able to understand data

Possible attacker models:

• The attacker simply eavesdrops;
• The attacker knows a set of possible plaintexts;
• The attacker may tamper with the data and observe the reactions of a decryption-capable entity.

Perfect secure cipher

In a perfect cipher ⇒P C∀ ∈ ∧ ∀ ∈ptx ctx seeing a⇒sent = = sent = sent =P r(ptx ptx) P r(ptx ptx∣ctx ctx) ciphertext gives us no information on what the plaintext corresponding C∈cto could be.c

THEOREM (SHANNON 1949)

Any symmetric cipher with is perfectly E, DP, K, C,< > ∣P∣ = ∣K∣ = ∣C∣ secure if and only if 1

Every key is used with probability ∣K∣

A unique key maps a given plaintext into a given ciphertext: ∀(ptx, ∈ctx)P C, Ks.t.E(ptx,× ∃!k ∈ =k) ctx

This perfect secure cipher is not usable because:

• Storing key material and changing keys is a nightmare;
• Perfect cipher broken in practice due to key theft/reuse;
• Generating random keys is also an issue.

CRYPTOGRAPHY 2

Computationally secure cipher

Build a cipher so that a successful attack is also able to solve a hard computational problem efficiently.

PROOF

• Attacker represented as a program able to call given libraries;
• Libraries implements the cipher at hand;
• Define the security property as answering to a given question;
• The attacker wins the game if it breaks the security property more often than what is possible through a random guess.

CSPRNG

Cryptographically Safe Pseudorandom Number Generator.

ASSUMPTION

We want to use a finite length key and a Vernam cipher.

We assume that the attacker can only perform poly( ) computationsλ

DEFINITION

A CSPRNG is a deterministic function whose: {0, 1} → {0, 1}λ λ+I PRNG output cannot be distinguished from an uniform random sampling of {0, 1} λ+I in . is called CSPRNG stretch. O(poly(λ)) I

In practice we only have candidate CSPRNGs because we have no proof that a function PRNG exists.

Practical constructions

Building a CSPRNG from scratch is possible but not efficient. Usually it is built with a PseudoRandom Permutations (PRPs) (defined starting from PseudoRandom Functions PRFs).

Random functions: RFs

Consider the set N}F = {f : {0, 1} → {0, 1} , ∈in out in, out

A uniformly randomly sampled can be encoded by a entries table, $ F← 2 infout in each entry bit wide .2⇒ ∣F∣ = (2 )out

CRYPTOGRAPHY 3

Pseudorandom functions: PRFs

DEFINITION

A function taking an input and a bits seed.: {0, 1} → {0, 1}in out prf λseed

The entire is described ny the value of the seed prf seed

It cannot be told apart from a random in∈ {f : {0, 1} → {0, 1} }in outfpoly(λ)

If they give you , you can’t tell which one of ∈ {f : {0, 1} → {0, 1} }in out a the following is true:

with $←= (⋅) {0, 1} λseed a prf seed, where

$ F F = {f : {0, 1} → {0, 1} }← in out b

Pseudorandom permutations: PRPs

DEFINITION

A bijective PRF: len len: {0, 1} → {0, 1} prf seed

It is uniquely identified by the value of the seed.

It’s not possible to tell apart in from a RF poly(λ)

It’s a permutation of all the possible strings {0, 1} len

Real world PRPs

Typical construction:

1. Compute a small Bijective Boolean function of input and key f;
2. Compute again between the previous output and the key f;
3. Repeat 2. until you’re satisfied.

PRPs a.k.a. Block ciphers

Concrete PRPs go by the historical name of block ciphers.

Considered broken if, with less than operations, they can be told apart from 2 λ a PRP.

The key length is chosen to be large enough so that computing guesses is 2 λλ not feasible.

Examples are:

CRYPTOGRAPHY 4

AES (Advanced Encryption Standard): 128 bit block, three key lengths: 128, 192, 256 bits

DEA (Data Encryption Algorithm)

First attempt encryption with PRPs: electronic codebook

COUNTER MODE (CTR)

Achieving CPA security

We need a non-deterministic way of encrypting messages (same ptxs different → ctxs), otherwise if the attacker is active (it knows some plaintexts) he can decrypt easily some data.

Decryptable nondeterministic encryption

1. Rekeying: change the key for each block with a ratchet;
2. Randomize the encryption: add randomness to the encryption;
3. Number used ONCE: (NONCEs): in the CTR case, pick a NONCE as the counter starting point. NONCE is public.

CRYPTOGRAPHY 5

Symmetric ratcheting

It’s not possible to roll-back the procedure once you delete the value carried by green arrow. This is how an end-to-end encryption works: both and only sender and receiver know the key. The message is sent, the recipient delete the key; once the receiver decrypt the message, the key is deleted.

Data integrity

Confidentiality doesn’t necessarily means Integrity.

Malleability

Making changes to the ciphertext (not knowing the key) maps to predictable changes in the plaintext. This can be abused (example: an attacker modifies a bank transaction ciphertext, without knowing the values of the transaction, changing some bits).

We need some mechanism to guarantee integrity.

CRYPTOGRAPHY 6

MAC: Message Authentication Code

MAC does not provide Authentication but Integrity.

The idea is to add a small piece of information, TAG, allowing us to test for the message integrity of the encrypted message itself.

A MAC is constituted by a pair of functions:

COMPUTE_TAG(string, key) #returns the tag for the input string

VERIFY_TAG(string, tag, key) #returns true or false

The problem with tag is the same as the previous one.

How to build the MAC?

In this way, the tag is both message and key dependent.

In this way the tag cannot be forged by an attacker if the message is prefix-free.

If the message is not prefix-free, the attacker, even without knowing the key but understanding how the hashing function works, can append additional data to the message while still maintaining a valid MAC. This happens because the MAC is computed sequentially.

We can fix this problem encrypting the complete message another time.

Efficiency

If the tag is too long, testing the integrity of a message takes too much time.

It would be fantastic if we can test only short, fixed length strings independently from the file size.

CRYPTOGRAPHY 7

A way to do so is HASH FUNCTIONS.

Hash function

A cryptographic hash is a function for which the ∗: {0, 1}1 → {0, 1} I H following problems are computationally hard:

1. Given find s (1st preimage) =d H(s);
2. Given find (2nd preimage) = = : =s, d H(s) r s d H(s);
3. Find with (collision): = =r, s r s H(s) H(r).

The ideal behavior of a concrete cryptographic hash is:

1. Finding 1st preimage takes hash computations guessing) dO(2 s;
2. Finding 2nd preimage takes hash computations guessing) dO(2 r;
3. Finding a collision takes hash computations d )≈ O(2 2.

Hash functions to use:

• SHA-2: privately designed;
• SHA-3 (similar to AES).

Hash function to not use:

• SHA-1: collision-broken;
• MD-5: horribly broken.

Asymmetric cryptography

Symmetric cryptography not allow to communicate keys between long distances.

With symmetric cryptography the security margin is the number of the keys and the time to bruteforce all of them ( ))λO(2

This is not true in asymmetric cryptography, because in this case keys are not only random strings, but they are mathematical object. In this cryptography is much easier violate crypted data than in symmetric one.

Diffie-Hellman key agreement

GOAL: make two parties share secret value with only public messages.

ATTACKER MODEL: Can eavesdrop anything, but not tamper.

ASSUMPTION:

CRYPTOGRAPHY 8

Let be a finite cyclic group; two numbers taken (G, ⋅) ≡ < >g a, b uniformly from G{0, ..., − 1} (λ = ≈ log ∣G∣)len(a) 2

Given finding costs more than, ∣G∣)a b abg g g poly(log

Best current attack approach: find either or b a

Key agreement between A and B

A: pick and sends to B $ {0, ..., ∣G∣ − 1}← ag a

B: pick and sends to A $ {0, ..., ∣G∣ − 1}← bg b

A: gets from B and computes (g )b a bg

B: gets from B and computes (g )b b ag

Since is commutative DONE! ⇒ ⇒a b b a(G, ⋅) (g ) = (g )

Public key encryption

The public key is used to encrypt the message; the private key is used to decrypt the message.

Given the public key is unfeasible to obtain the private key;

Given the ciphertext, the decryption is computationally hard without the private key.

Asymmetric encryption ciphers

RSA (Rivest, Shamir, Adleman)

• 2048 to 4096 bit message-size and key-size;
• Patented after the invention, patent now expired;
• No ciphertext expansion;
• The encryption with a fixed key is a PRP.

CRYPTOGRAPHY 9

ElGamal encryption scheme

• Either kbit range keys, or 100’s of bits keys, depending on the variant;
• The ciphertext is twice the size of the plaintext;
• Widely used as an RSA alternative where patents were a concern.

Key encapsulation

1. A: generates a keypair and sends them to B. (k , )kpri pub
2. B: gets encrypts it with , sends ctx to A $ {0, 1}← λ ks pub
3. A: decrypts the ctx with , recovers sk pri
4. Repeat the procedure with swapped roles and combine the two secrets to achieve similar guarantees to a key agreement.

EFFICIENCY only

Can we skip a step? A and B could employ an asymmetric cryptosystem to communicate, but this approach in practice would be inefficient: symmetric cryptosystems are 10x-1000x slower than their symmetric counterparts.

Recipient:

1. Encrypt the random key;
2. Encrypt the message with public key;
3. Send message.

Receiver

CRYPTOGRAPHY 10

1. Decrypt the key part of the message with private key;
2. Decrypt the ciphertext with the previously decrypted key.

This process guarantee confidentiality and integrity.

Authenticating data

We need to be sure that the public key the sender uses is the one of the recipient. We would like to be able to verify the authenticity without a pre-shared key.

Digital signatures

Evidence that data is bound to a specific user.

No shared secret is needed to validate the signature.

They are asymmetric; otherwise is formally proved that you cannot get non-repudiation property.

It’s computationally hard to:

• Sign a message without the signature key;
• Compute the signature key given only the verification key;
• Derive the signature key form signed message.

Signature schemes

RSA (Rivest, Shamir, Adleman):

• Unique case: the same hard-to-invert function to build an asymmetric encryption scheme and signature;
• Signing slower than verification ≈ 300×.

DSA: Digital Signature Standard

CRYPTOGRAPHY 11

Derived from tweaking signature schemes by Schnorr and Elgamal.

Signature and verification take approximately the same time.

It is based on the generation of a random number, because it is not a deterministic algorithm (generation of the signature).

It is important to generate a NEW random number for each signature; otherwise the private key becomes public.

The public key binding problem

• The public key must be bound to the correct user identity;
• The public key authenticity is guaranteed with another signature;
• We need someone to sign the public-key/identity pair;
• We need a format to distribute signed pairs.

Solution: digital certificates

They bind a public key to a given identity:

• For humans: ASCII string;
• For machines: CNAME or IP address;
• They specify the intended use for the public key contained;
• They contain a time interval in which they are valid;
• Certificate signer is a trusted third party, the CA; its public key is authenticated with another certificated…. and so on… up to a self-signed certificate which has to be trusted a priori.

CRYPTOGRAPHY 12

Final mixup: CIA

Modern cryptography

We based all cryptography on the hard computationally problems (polynomial).

But with quantum computers this would be not enough.

Information theory

CRYPTOGRAPHY 13

Shannon’s information theory is a way to mathematically frame communication or to quantify information.

We would use it to quantitatively frame “luck” and “guessing”.

A communication takes place between two endpoints:

Sender

Receiver

Information is carried by a channel in the form of a sequence of symbols of a finite alphabet.

The receiver gets information only through channel.

It will be uncertain on what the next symbol is, until the symbol arrives ⇒ we model the sender as a random variable.

Acquiring information is modeled as getting to know an outcome of a random variable . The amount of information depends on the distribution of X the variable.

Entropy

Let be a discrete random variable with outcomes in with {x , ..., }X n x0 n−1. The entropy of is= ) = , ∀ 0 ≤ ≤ H(X ) =XP r(X x p i ni i n−1 log−p (p )∑ i ibi=0

Shannon’s noiseless coding theorem

It is possible to encode the outcomes of i.i.d. random variables, each one n with entropy , into no less than bits per outcome. If H(X ) ) < )nH(X nH(X bits are used, some information will be lost.

Guessing a piece of information is at least as hard as guessing a bit long H(X ) bitstring.

Min-entropy

Min-entropy of = H ( ) = − log(max )X X p∞ i i

CRYPTOGRAPHY 14

AUTHENTI