CPSC 4200 Midterm

Adversary

An intelligence that actively tries to cause a system to misbehave

aka the attacker or the bad guy

Security Mindset - Attacker

• look for weakest links (easy to attack)

• identity assumptions that security depends on (are they false, can they be made false)

• think outside the box (not contained by system designer’s worldview)the

Security Mindset - Defender

security policy

• what assets are we trying to protect

• what properties are we trying to enforce

threat model

• who’s the attacker? capabilities? motivations?

• what kind of attack are we trying to protect?

risk assessment

• what are the weaknesses of the system?

• what will successful attacks cost us?

• how likely?

countermeasures

• cost vs benefits

• technical vs non-technical

Security Policies

What asset are we trying to protect?

asset - any data/device/component that supports info-related activities

What properties are we trying to enforce?

CIA (Confidentiality, Integrity, Availability)

and other AAA

Confidentiality

ensure information has not been disclosed in an unauthorized way

problem: ensure only Bob can read the message from Alice

attack: eavesdropping (passively listening to communication)

countermeasure: encryption

keep this conversation confidential (between you and me)

Integrity

ensures information has not been altered in an unauthorized way

problem: ensure the message received by Bob is a message sent by Alice

attack: spoofing (altering original message)

countermeasure: message authentication code (MAC)

keep this conversation strong (no changes)

Availability

assures systems work promptly and service is not denied to authorized users

problem: Alice needs to access her email server at all times

attack: denial of service attack

countermeasure: intrusion detection system

keep this conversation available at all times

CIA

Terminology: Threat

any potential occurrence, malicious or not that could harm an asset

• can be a SW bug

Terminology: Vulnerability

A weakness that makes a threat possible is often due to poor design or insecure coding techniques

• ex. poor design, config mistakes, insecure coding techniques

Terminology: Attack

An action that exploits a vulnerability or enacts a threat, implying intent.

• implicit concept of intent (intentional threat)

• server crash can also cause loss of availability, but not an attack

Terminology: Authenticity

The ability to determine that statements, policies, and permissions issued by persons or systems are genuine.

Terminology: Anonymity

The characteristic that ensures certain records or transactions cannot be attributed to any individual.

Terminology: Accountability

The requirement for actions of an entity to be traced uniquely to that individual.

Terminology: Passive vs Active Attack

passive - an attack that involves eavesdropping or monitoring messages without altering them

active - n attack that involves modification of messages

• ex. masquerading, replaying, or spoofing.

Terminology: Inside vs Outside Attack

Inside - initiated by authorized entity inside security perimeter

Outside - initiated by unauthorized entity outside the perimeter

Terminology: Attack Surface

The different vectors through which an attack can occur

• network (weak crypto for digital signature)

• software (buffer overflow)

• human components (social engineering)

Why are there security vulnerabilities?

lots of buggy software (programmers are unaware)

contributing factors

• C is unsafe language (memory issue)

• legacy software

• consumers don’t care about security (not a selling point)

• security is expensive

State of Security

never ending war between good and bad guys

every asset has at least one vulnerability

no such thing as bullet proof barrier

only a multi-layered approach has a change of success

Cryptography

core building block of cyber security (basis for security mechanisms)

• CIA and AAA properties are provided using cryptography

cryptography is not:

• solution to all security problems

• reliable unless implemented/used properly

• something you should invent yourself

• bitcoin

Never do what with crypto?

Do NOT roll your own crypo

Message Integrity with Functions

goal: ensure the message received by Bob is a message sent by Alice (m = m’)

approach: send a message-dependent message along with the original message

• v = f(m)

bob checks that f(m’) == v’, otherwise m’ untrusted

Function Properties

• generate consistent output (with no collisions)

• 1-to-1 mapping between m and f(m) (bijection)

• unknown to Mallory

Random Function

input: arbitrary size (up to huge max)

output: fixed size (256 bits)

• defined by a large lookup table that’s filled with flipping coin

• mapped each input independently at random at any of the possible outputs

• idealization of a cryptographic hash function

Random Function: is it secure?

Yes

• mallory’s best chance is to guess

• caveat: lookup table needs to be exchanged securely in advance

Random Function: is it practical?

No

• both sides have other know entire table beforehand

• table might be to large to conveniently share between parties

Pseudorandom Function (PRF)

set of functions that “look“ random but are practical

• “looks“ random: two inputs that differ by 1, likely to produce different outputs

• practical: computable (no need to pre-share all possible input to output pairing/lookup table)

properties

• family of function can be public

• k is a secret only known to Alice/Bob

  • randomly chosen (256 bits)

follows Kerckhoff’s Principles

Length of key k

the length of key k determines how many functions they have to check for the right one

ex. |k| = 8, f₀ → f_2⁸(f₂₅₆)

Function keys should be how long?

128 bits

at least 80

Kerckhoff’s Principles

1. system must be practically, if not mathematically, indecipherable;

2. it should not require secrecy, and I should not be a problem if it fall into enemy hands;

3. must be possible to communicate and remember the key without using notes, and parties must be able to change/modify it at will;

4. It must be applicable to telegraph communications;

5. It must be portable, and should not require several persons to

   handle or operate;

6. It must be easy to use and should not be stressful to use or

   require its users to know and comply with a long list of rules.

Advantage of PRFs

PRFs depend on secret of key, not knowledge of the system

• system: random function f

• advantage: good, secure functions f can be public

• NO security of obscurity

key k must be exchanged between Alice and Bob

• k us much smaller than f

Message Integrity Using PRFs

goal: message received by Bob is a message sent by Alice

PRF approach

• let f be a secure PRF

• in advance, choose a random k known only by Alice and Bob

• let v = f_k(m)

• Bob checks that f_k(m’) == v’

Message Integrity Using Multiple PRFs

goal: multiple messages received by Bob are messages sent by Alice

problem:

• replay attack - Mallory resends message from earlier communication

• reordering attack - Mallory sends a message out of order

countermeasure

• add sequence number (“freshness value“/sequence number)

• use a different key k each time

Do PRFs Exist?

we don’t know

best we can do: well studied function we havn’’t spotted issues with yet

• HMAC-SHA256

Message Authentication Code (MAC)

essentially the same as PRF

currently popular PRF: HMAC-SHA256

• hash-based message authentication code (HMAC)

Hash Functions

input: arbitrary length data

output: fixed size digest (n bits)

• no key, fixed function

properties:

• collision resistance (hard to find x ≠ y such that h(x) = h(y))

• pre-image resistance (given y, hard to find x such that f(x) = y)

• second pre-image resistance (given fixed x, should be hard to find x’ ≠ x such that h(x) = h(x’))

Hash Functions: Good vs. Broken

good functions:

• SHA-2 (include SHA-256)

• SHA - 3

• SHA-5 (include SHA-512)

broke functions (DO NOT USE):

• SHA-1

• MD5

Hash Function Rule of Thumb

hash output should be at least 256 bits long

MAC vs Hash

use a MAC instead of a hash

message authentication code (MAC)

• think of as synonymous with PRF

• ex. HMAX-SHA256

cryptographic hash function

• not a strong PRF

• ex. SHA256

• have a weakness

Hash Function Vulnerability

hash function vulnerable to length extension attacks

• given z = H(m) for some unknown m, can construct H(m || padding || v) for v we choose.

• aka HW1

Goal of Cryptography

approaching true randomness practically

Pseudo Randomness

true randomness

• output of a physical process that is inherently random

• scarce and hard to get

• slow

pseudorandom generator (PRG)

• takes small seek (key k) that is really random

• generates long sequence of numbers that “appear random“

• different from PRF

Source of Randomness

• coin flip

• human behavior

• atomic decay

• thermal noise

• electromagnetic noise

• physical variation

  • clock drift

  • DRAM decay

  • image sensor error

  • SRAM startup state

• lava lamps

Where do we get true randomness?

key k needs to be truly random (with secure PRF f)

• adversary can’t guess it

• gather details about computer that’s hard for adversary to guess

modern OSs collar randomness and provide API to access it

• /dev/random

• /dev/urandom

Message Confidentiality with Encryption

Ciphers

• Caesar Cipher

• Vigenère Cipher

• One-Time Pad (OTP)

• Stream Cipher

• Block Ciphers

Caesar Cipher

replaces each plaintext letter with one a fixed number of places down the alphabet

Caesar Cipher Cryptanalysis

how to break it:

• only 26 possible keys (“brute force“ every possible k)

how can a computer recognize the right one?

• English has distinctive letter frequency distribution (use X² test)

Vigenère Cipher

encrypts successive letters using a sequence of Caesar ciphers determined by the letters of a keyword

Vigenère Cipher Cryptanalysis

how to break it:

• simple if we know the keyword length, n

  • break cipher text into n slices

  • solve each slice as caesar cipher

• distance between repeated strings in cipher tests (likely) a multiple of key length n

  • ex. distance 16 implies n is 16, 8, 4, 2, 1 (find multiple repeat to narrow down)

• how to find n?: Kasiski method

One-Time Pad (OTP)

Alice encrypts, and Bob decrypts using the same key k and uses OTP for E and D

• both generate a secret, long string of truly random bits (the OTP k)

• to encrypt: c = p XOR k

• to decrypt: p = c xor k = p xor k xor k

theoretically secure since cipher text doesn’t reveal any info (besides length) about plain text

One-Time Pad (OTP) Reuse Problem

should never reuse any part of the pad

• adversary can learn (a xor k) and (b for k)

• adversary xors those to get (a xor b) which is useful

Stream Cipher

using pseudorandom generator

• inputs seed k

• outputs stream that is indistinguishable from true randomness unless know k

1. start with shared secret key truly random number k

2. Alice and Bob use k to seed the PRG

3. to encrypt, Alice XORs next bit of her output with next bit of plaintext

4. to decrypt, Bob XORs next bit of his output with next bit of ciphertext

Stream Cipher: Questions

what happens if you reuse the key?

• Mallory can save sequences and look for repeats (like Vigenère cipher)

what happens if you reuse the output of the PRG?

• Mallory can save sequences and look for repeats (like Vigenère cipher)

what is the tradeoff between OTP and Stream Cipher?

• OTP: true randomness and random key = len(m)

• Stream Cipher: pseudorandomness and random key = 256 bits

what are some examples of Stream Cipher?

• Salsa20, RC2 (broken), RC4 (broken)

should I roll my own Stream Cipher instead?

• NO

Block Cipher

functions that encrypt fixed-size blocks with a reusable key

• inverse function decrypts when used with same key

• most commonly used approach to encrypting for confidentiality

• Block Cipher is a Pseudorandom Permutation (PRP)

Pseudorandom Permutation

input: n-bit string (or block)

output: n-bit block

confusion

• each bit of the cipher text should depend on several parts of the key

• destroy features of the plaintext

diffusion

• changing a single bit of plaintext, statistically changes 50% of the cipher text bits,

• and similarly changing one bit of the cipher text causes 50% of the plaintext bits to change

• hides features of the plaintext

Data Encryption Standard (DES)

key: 64-bit quantity = 8-but parity + 56-bit key

input/output: 46 bits

brute force key search

• trying 1 key/microsecond would take 1000+ yrs (2⁵⁶)

no longer secure since 56-bit key vulnerable toe exhaustive search

Alternatives to DES

Triple DES (3DES)

• 168-bit key

• no brute force attacks

• encryption is slower than DES

Advanced Encryption Standard (
AES)

Advanced Encryption Standard (AES)

most common block cipher

128-bit block size

variable key size (128, 192, or 256)

• AES-128, AES-192, AES-256

designed to run fast in SW

How to encrypt longer message?

can only encrypt in units of cipher block size

• cut message into multiple chunks

message might not be multiple of block size

• add padding to end of message

• add n bytes that have value n

• must be able to recognize and remove padding after decryption

how to properly encrypt multi-block messages? (cipher modes)

• ECB, CBC, CTR

Electronic Codebook (ECB) Mode

just encrypt each block individually

• DON’T USE ECB

Cipher-Block Chaining (CBC) Mode

Counter (CTR) Mode

XOR i^th block of message with E_k(nonce || ctr)

• effectively a stream cipher

blocks can be decrypted independently

How to enforce confidentiality AND integrity?

Encrypt-then-MAC

“E then M” in the alphabet

Questions

we need two shared keys, but only have one?

• use a PRG

we have a reverse channel (Bob to Alice), do we use the same key?

• no, use separate keys

in networking applications, we cannot encrypt header. what do we do?

• use authentication encryption with associated data (AEAD)

Secret Key (Symmetric) Cryptography

assumptions we’ve made so far: Alice and Bob shared a secret key in advance

limitation: sender/receiver must share the same key

• needs secure channel of key distribution

• impossible for two parties having no prior relationship

• needs many keys for N partiers to communicate

Alice and Bob can have public conversation to derive a shared key

How to derive a shred secret key?: Diffie-Hellman (DH) Key Exchange

Diffie-Hellman (DH) Example

Diffie-Hellman (DH): Passive Eavesdropping Attack

DH secure against passive eavesdropping attacks since no known efficient algorithm

Diffie-Hellman (DH): Man-in-the-middle (MITM) Attack

DH not secure against MITM attack

• DH gives shared secret, but you don’t know who's on the other end

Defending against MITM Attacks

• rely on out-of-band communication between users (2FA)

• rely on physical contact (smartcards)

• use digital signuature

Key Management

key management is hard (protecting keys, communicating keys, etc)

each key should have 1 purpose

vulnerability of a ket increases:

• the more you use

• the more places you store it

• the longer you have it

Forward Secrecy

protestation against old keys that have been compromised

• learning old keys shouldn’t help adversary learn new keys

• compromising an individual session should not compromise future sessions

• compromising a long-term key should not enable decryption of recorded cypher text

use short-lived ephemeral keys or sessions keys

Secret Key (Symmetric) Cryptography

assumptions we’ve made so far: Alice and Bob shared a secret key in advance

limitation: sender/receiver must share the same key

• needs secure channel of key distribution

• impossible for two parties having no prior relationship

• use Diffie-Hellman (DH) to determine shared secret key

problem: Scaling

Scaling Problem

suppose Alice publishes data to lots of people, and they all want to verify integrity

• can’t share integrity let with everyone, or else anybody could forge messages

suppose Bob wants to receive data from lots of people confidentially

• schemes we’ve discusses would need separate encryption key shared with each person

Solution: Public-Key Crypto

Public-key (Asymmetric) Cryptography

so far: encryption key E_K = Decryption key D_k

• Symmetric-Key Cryptography

• require a separate key shared with each person

new idea: each party has a pair (K, K^-1) of keys

• K is the public key (can be shared with any other party)

• K^-1 is the private key (kept secret)

private key K^-1 to pubic key K (impossible)

pubic key K to private key K^-1 (possible)

Rivest-Shamir-Adleman (RSA)

best known public-key cryptosystem

• secure based on difficulty of factoring large numbers

uses for encryption AND asymmetric cryptography

drawback: factor of +1000 slower than AES

How Rivest-Shamir-Adleman (RSA) Works

Asymmetric Encryption

Alice wants to send encrypted message to Bob

• they know each other’s public keys

Alice encrypts with K_B, now only Bob can decrypt with K_B^-1

• D(E(m, K_B), K_B^-1) = m

many can encrypt a message for Bob, but only Bob can decrypt

solves message confidentiality

Digital Signiture

Bob needs to know if the message is coming from Alice

• they know each other’s public key

Alice encrypts (signs) with K_A^-1, Bob decypts (verifies) decrypts with K_A

• only Alice has her own private key (so message must be from her)

• Bob receives Alices’s digital signature d

solves message integrity AND sender authenticity

Question

since RSA encryption is much slower than AES and message lengths are constrained, why bother?

• AES requires symmetric key, needs to be derived first

• DH fails under the presence of Mallory (MITM attack), so RSA needs to be used to distribute the symmetric (secret) key

how do we distribute the symmetric key using RSA?

• RSA with DH

• RSA without DH

RSA with Diffie-Hellman (DH)

1. establish shared secret k using DH (even with Mallory is there)

2. make sure they’re really talking to each other by exchanging/verifying RSA signatures on k (if Mallory were there, this would fail)

3. split k into four distinct keys (integrity and confidentiality in both ways)

4. to encrypt: encrypt with symmetric cipher, then add MACs for integrity (Encrypt-then-MAC)

RSA without Diffie-Hellman (DH)

1. Alice generates secret key k and encrypts with Bob’s public key K_B. Cipher text is sent to Bob who decrypts with his private key K_B^-1

2. Use RSA signatures on ciphertext to avoid Mallory from tampering

3. with the message

4. Decrypted plaintext is k, now both Alice and Bob can use k for symmetric encryption ( AES).

5. Split k into four distinct keys (integrity and confidentiality in both ways)

6. To encrypt: Encrypt with symmetric cipher, then add MACs for integrity (Encrypt-then-MAC)