---
# System prepended metadata

title: CS 526 Final Notes

---

# CS 526 Final Notes

## Denial of Service
- too much traffic for network
- use up memory or CPU resources

### Reflection
send a request to other machine, cause it send back to real victim
- reduce traceability
- amplify the attack
![](https://i.imgur.com/QoovBpx.png)

## Firewall
- service control
    - what service can be accessed (in or out)
- behavior control
    - how service are accessed (spam filtering, web content filtering)
- user control
    - control access to service on per-user level
- auditing
- network address translation

### Packet filtering
- apply a set of rules for all incoming/outgoing packets
- can based on any part of the header
    - IP address
    - port numbers
    - flags
    - network interface

disadvantages:
- difficult to configure for buth usability and security
- misconfiguration can be easily exploited
- doesn't examine application-level data
- no user authentication
- still has TCP/IP vulnerabilities
    - e.g. address spoofing

### Stateful firewall
- can also look at context
    - maintain list of active TCP connection (useful with dynamic port)
- can also use global information (e.g. number of packets for particular IP address)

### Host-based firewall
- can be used on machine no matter is it part of a larger network
- filter can be machine-specific

### Multiple firewall
- can have multiple firewall, each provide different protection

## DHCP
![](https://i.imgur.com/GkHu1TU.png)

### DHCP attacks
- DHCP starvation
    - exhaust all IP address of a DHCP server
- DHCP spoofing
    - send forged DHCP response to divice
    - replace IP address of gateway and DNS server to divert the traffic to malicious server
    - Man-In-The-Middle attack

## DNS
![](https://i.imgur.com/5aZknza.png)
![](https://i.imgur.com/5rc9rx9.png)

### How to know IP address ?
- local DNS server: via DHCP
- parent know its children
- root name server: hardcoded in all name servers

### DNS cache poisoning
What we care in a DNS response?
- A record: the authoritative response for the IP address of the hostname
- NS record: name of name server who know more about the answer
    - often **also contains IP address** of the name server
    - resolver will cache all result
- query id: use query id to determine which response map to which query
    - 16 bits field in DNS header
    - basically used to increment

![](https://i.imgur.com/mhmob87.png)
- guess the query id via a dns query
    - partial fix: randomize query id (small space)
- guess source port number
- send fake response to local name server
    - answer must not already be in the cache

### Kaminsky attack
based on the ability to overwrite cache
![](https://i.imgur.com/viy7uzE.png)
- ask a name that is not used
    - e.g. 1.victim.com, 2.victim.com
    - fake a NS response

![](https://i.imgur.com/NRbzRy0.png)
- a higher trust level record could overwrite a lower trust level record

### Solution
- randomize query id
    - no sufficient: only 16 bits
- randomize port number
- DNSSEC
![](https://i.imgur.com/kf9cLCg.png)
- every query is encrypt with target server's public key
- if everyone use DNSSEC, then prevents spoofed response
- but not everyone use DNSSEC

## SQL Injection
```
user = "John' OR 1=1; --";
pass = "12345";
mysql_query("select * from Users
where name = '$user' and password = '$pass';");
```
If we didn't escape the singe quote, the SQL statement will be like
```
select * from Users
where name = 'John' OR 1=1; --' and password = '12345';
```
which can pass the condition statement or execute other SQL statement.

### Solution
- whitelist
    - check the input is in some safe set
    - reject invalid input rather than dix them
- escape characters
    - ' => \\'
    - " => \\"
    - \- => \\-
    - \ => \\\
    - mysql_real_escape_string()
- prepared statements and bind variables
    - decouple code and data
- limit privileges
    - incomplete fix, but helpful
- encrypt sensitive data in database

## Cross-Site Request Forgery
![](https://i.imgur.com/3oQNECC.png)

### Defenses
- same site cookies
    - browser will send cookies only if the request originated from the same site
- cookie-to-header token
    - because of same origin policy, javascript can only create custom header in same site 
    - use javascript to create custom header
    - server verify the custom header
- secret vaildation token
    - server generate csrf token and send to client
    - client store token in form
    - client send request with the token
    - server validate the token
- referer validation
    - check if the referer is expected site
    - weak defense
    - attacks from HTTPS leave referer blank
    - many valid requests remove referer header
    - many implementation mistake of check
- X‐Requested‐With header
    - this header cannot cross domain
    - server drop request without this header
- reauthentication
    - password: if password is known, then it is useless
    - onetime token: strong defense

### User defenses
- logout after using web application
- don't save password, don't remember login
- don't use tabbed browsing
- no script

## How can you steal session token ?
- compromise user's machine / browser
- sniffing
- DNS cache poisoning
    - trick user to think you are Facebook, the user will send you cookie
- XSS

### Mitigate cookie security threats
- cookies must not easy to guess
    - random
    - sufficiently long
- time out sessions ID

## Cross Site Scripting
- scripts are embedded in web pages
- scripts are execute by browser
    - alter page content
    - track events
    - issue web requests
    - maintain persistent connections
    - read and set cookies
- PDF documents can also execute JavaScript code
    - malicious code can access local file

### Same Origin Policy
- only scripts received from same origin have access to page's element
- scheme, host, port should be same to comply with Same Origin Policy
    - scheme: protocol

### Subvert Same Origin Policy: XSS
- reflected XSS: attack script reflected back to user's web page
- stored XSS: attacker stores malicious code in victim's database
- DOM-based XSS: injected script is part of document attributes

### Stored XSS
![](https://i.imgur.com/B7aRody.png)
- attacker leave their script on the target server
- the server later send it to user's browser
- the browser executes within same origin

### Reflected XSS
![](https://i.imgur.com/Tk7wbwU.png)
- attacker create an url include some malicious code
- target server echoes the script back
- the browser executes the script

### DOM-based XSS
![](https://i.imgur.com/A2MDomh.png)

- no server needed
- if the script write the url to DOM directly, we can easily inject attack code into web page

### XSS Protection
- whitelist: validate headers, cookies, query...
- don't blacklist
- use "positive" security policy that specifies what is allowed
- never trust client data
- encode special characters
    - <: &lt\;
    - \>: &gt\;
    - ": &quot\;
    
Good idea
- static analysis
- framework support

## XSS vs CSRF
- XSS based on the trust of the browser in server
    - try to control what server send to browser
- CSRF based on the trust of the server in browser
    - try to control what browser send to server

## Towards Computational Security
- perfect secrecy is too difficult to achieve
- security is preserved only against **efficient** adversaries
- adversaries can suceed with **very small probability**

### How to Prove Computational Security
- assume some problem is hard
- show that breaking the security means solving the problem

## Crytography Big Picture
![](https://i.imgur.com/pUywKYn.png)

## Kerckhoff's Principle
- a cryptosystem should be secure even if it is known by the adversary
    - security should rely only on secrecy of the key
### Reason
- easier to change key than to change algorithm
- algorithm can be leaked by insider
- easier to make n key for different paries than to make n algorithm

## Symmetric Cryrtography
- encryption: stream cipher or block cipher
- authentication: MAC

### Hash Function
- easy to compute but hard to invert
- determinsitic
- small change in input create large change in output
- collision resistant
    - hard to find (x1, x2) such that h(x1) = h(x2)
- pre-image resistant
    - given y, hard to find x that y = h(x)
- second pre-image resistant
    - given x1, hard to find x2 that h(x1) = h(x2)

### Attack on Hash Function
- collision
    - level of security of a hash function that output n bits is n / 2 bits
    - it takes $2^{n/2}$ time to bruteforce it
    - level of security of an encrypt function using k bits key is k bits
- length extension

### Well Known Hash Function
- md5
    - output 128 bits
- SHA1
    - output 160 bits
- SHA2(SHA-224, SHA-256, SHA-384, SHA-512)
    - output 224, 256, 384, 512 bits
    - no real security concern yet
- SHA3(224, 256, 384, 512)

### Symmetric Encryption
- relies on shared key
- stream cipher
- block cipher

### Stream Cipher
![](https://i.imgur.com/w6mv60z.png)
- use pseudo random number generator
- expand a short random seed (e.g. 128 bits) into long string (e.g. $10^{6}$ bits)
- secret is the seed
- typically fast
- widely used, often incorrectly
- **if same keystream is usred twice, then easy to break**

#### Use Stream Cipher in Practice
- in practice, one key is used to encrypt many messages
    - example: wireless communication
    - solution: use **Initial Vector** (IV)
    - E(M) = [IV, M $\oplus$ PRNG(key || IV)]
    - IV is sent in clear to receiver
    - IV ensure the key stream do not repeat

#### Pseudo Random Numeber Generator
- useful for crytorgaphy, simulation...
- same seed always gives same output
- crytography needs unpredictable sequence
- some PRNG is weak: knowing sufficient long sequence can recover the key

#### RC4 Stream Cipher
- variable key size (40 ~ 256 bits)
- output length unbounded
- not a completely secure PRNG
- disabled in most of the place now

### Block Cipher
- operate on a fix-length groups of bits

#### DES (Data Encryption Standard)
- block size is 64 bits
- key size is 56 bits
- designed mostly for hardware
- consider **insecure now** (brute force)

#### AES (Advanced Encryption Standard)
- designed for both hardware and software
- block size is 128 bits
- variable key size: 128, 192, 256 bits
- no known algorithmic weakness

#### Block Cipher Modes
- Electronic Codebook (ECB)
- Cipher Block Chaining (CBC)
- Output Feedback (OFB)
- Counter (CTR)
- ECB and CBC are encrypt with plaintext, OFB and CTR are encrypt with IV or counter
    - ECB and CBC need padding, but OFB and CTR don't need

#### ECB
![](https://i.imgur.com/cG4d318.png)
- same plaintext will result in same output
- don't use

#### CBC
![](https://i.imgur.com/P72ai4B.png)
- each block xor with previous cipertext block then encrypt
- used in project 4
- may be attacked by padding oracle attack
- encryption cannot be parallelize, but decryption can be parallelize

#### OFB
![](https://i.imgur.com/ApRjOu8.png)
- turn block cipher into stream cipher
- can pre-encrypt the IV, then parallelize the encryption and decryption

#### CTR
![](https://i.imgur.com/p8d4OdN.png)
- turn block cipher into stream cipher where key streams are created by encrypting counter
- both encryption and decryption can be parallelize

### Authentication
| security goals | Hash | MAC | Digital Signature |
| -------- | -------- | -------- | -------- |
| Integrity     | Yes     | Yes     | Yes     |
| Authentication     | No     | Yes     | Yes     |
| Non-repudiation     | No     | No     | Yes     |
| Kind of keys     | none     | symmetric     | asymmetric     |

### Message Authentication Code (MAC)
- used to verify both integrity and authentication of a message
- make sure right person sent the message and hasn't been changed
- should be hard to forge
- aka "tag"

#### CBC-MAC
![](https://i.imgur.com/UDhBAXc.png)
- secure only for fix-length messages
- three ways to ensure security for variable length messages
    - input-length key seperation **(?)**
    - length-prepending
        - put length info in the first block
        - why? put length in the last block may be modifed by length extension attack
    - encrypt last block
        - use additional key to encrypt the last block
- misuse
    - use same key for encryption and authentication
    - allow IV to vary in value
        - use 0 as IV
    - use predictable IV

#### HMAC
- hash-based MAC
- to concatenate the key and the message, and hash them together
$HMAC_K(M) = Hash((K^+ \oplus opad) || Hash((K^+ \oplus ipad)||M)))$
    - $K^+$ is key padded to B bytes
    - ipad = 0x36 repeated B times
    - opad = 0x5c repeated B times
    - B is the input block size
    
### Authenticated Encryption
- provide both data authenticity (integrity) and confidentiality in one algorithm
- three approaches
    - encrypt-then-MAC
    - encrypt-and-MAC
    - MAC-then-encrypt

#### Encrypt-then-MAC
![](https://i.imgur.com/Ef0I17h.png)
- used in IPsec
- most secure way

### Encrypt-and-MAC
![](https://i.imgur.com/xKNmPDU.png)
- used in SSH

### MAC-then-Encrypt
![](https://i.imgur.com/Nso5C9N.png)
- used in SSL/TLS
- used in project 4
- may be attacked by padding oracle attack

## Public Key Cryrtography

### Diffie-Hellman Key Exchange
![](https://i.imgur.com/1jHPGRR.png)
- $B^a = (g^b \ mod \ p)^a = g^{ab} \ mod \ p$
- $A^b = (g^a \ mod \ p)^b = g^{ab} \ mod \ p$

#### Security of DH based on 3 hard problems
- discrete log problem: given (g, h) compute $a$ such that $g^a = h$
- computational Diffie Hellman problem: given ($g$, $g^a$, $g^b$), compute $g^{ab}$
- dicisional Diffie Hellman problem: given ($g^a$, $g^b$, $h$), dicide if $h = g^{ab}$
- if one can solve DLOG, then one can solve CDH
- if one can solve CDH, then one can solve DDH
- DDH **assumed hard to solve if p is large** (at least 1024 bits)

### Public Key Encryption Algorithms
- El Gamal
    - based on the hardness of solving discrete logarithm
    - same idea as Diffie Hellman key agreement
- RSA
    - based on the hardness of factoring large numbers

### El Gamal Encryption
- public key: $pk = (g, h = g^x)$
- private key: $sk = x$ (via DH protocol)
- encrypt: choose random r
$ct = (g^r, M * h^r) = (g^r, M * g^{xr})$
- decrypt: $ct = (c_1, c_2)$
$M = (c_1^x)^{-1} * c2 = g^{-xr} * M * h^r = g^{-xr} * M * g^{xr}$
- **not secure**

### RSA
1. select two large prime number p and q
2. compute $n = pq$, and $\Phi(n) = (q - 1)(p - 1)$
3. select e, 1 < e < $\Phi(n)$, such that gcd(e, $\Phi(n)$) = 1
    - typically e is 3 or 65537
4. compute d, 1 < d < $\Phi(n)$, such that 
$ed \equiv 1 \ mod \ \Phi(n)$
$d \equiv e^{-1} \ mod \ \Phi(n)$
- public key: $pk = (e, n)$
- private key: $sk = d$

#### RSA Encryption
$c = M^e (mod \ n)$

#### RSA Decryption
$M = c^d (mod \ n)$

#### Hard Problem on which RSA depends
- factoring problem: given n = pq, compute p, q
- RSA problem: from (e, n), c, compute M such that c = $M^e$
    - aka compute e'th root of c
- **minimum 2048 bits recommand** for current usage

## Hybrid Encryption
- overcome fixed message size problem in public key encryption
![](https://i.imgur.com/EAyQka3.png)
1. generate public key and private key pair
2. generate symmetric key
3. use symmetric key encrypt message
4. use public key encrypt symmetric key
5. use private key decrypt symmetric key
6. use symmetric key decrypt message

## Digital Signature
### Signing Function
- input: secret key, fixed length message
- output: signature
- this is a randomized algorithm

### Verification Function
- input: public key, message and signature
- output: is valid
- anyone with public key can verify

### Digital Signature Properties
- Authenticity: we can prove that a message signed by Alice is truly from Alice
- Integrity: we can prove that no one has tampered the message
- Non-repudiation: Once Alice signed a message, she cannot claim she didn't sign that message

### RSA Signature
- sign message: $\sigma = H(M)^d \ mod \ n$
- verify signature: $H(M) = \sigma^e \ mod \ n$
- use hash to avoid the condition that message is larger than n

## Public Key Infrastructure (PKI)
- anyone can send Bob encrypt message
- how do we know the key belong to Bob?
- using PKI
    - trusted root Certificate Authority
    - everyone must know root CA
    - root CA signed intermediate CA

### Certificate
#### generate
1. Bob generate public key/private key pair
2. Bob send public key and identity information to CA
3. CA use its private key to sign Bob's public key and identity as certificate
4. CA send certificate to Bob

#### use
1. Bob can release its certificate to everyone
2. Alice use CA's public key to verify Bob's certificate. if valid, then she can trust the key is belong to Bob
3. Alice can use Bob's public key to encrypt message, and then send to Bob

#### Certificate Chain
![](https://i.imgur.com/CsNnEio.png)

### Certificate Revocation
![](https://i.imgur.com/1JaRyhG.png)

#### Obtain revocation data
1. download CRL
![](https://i.imgur.com/jTqFWqt.png)
2. online certificate status protocol
![](https://i.imgur.com/kKntFDU.png)
- also has privacy concern: CA will know who visit the server
3. **OCSP stapling**
![](https://i.imgur.com/7fsPPpl.png)

### Certificate transparency
- make it difficult for CA to issue a certificate without the certificate being visible to domain owner
- provide open auditing and monitoring system
- protect user from being duped (受騙) by certificate that was mistaken or malicious

## SSL/TLS
- allow secure connection between client and server
    - often used to secure reliable protocol (TCP)
    - doesn't require pre-shared key
    - most common usage: https

### Server authentication
- attacker's goal: convince the client that he is server
- our goal: establish symmetric key between client and server
- we want forward secrecy
    - compromise long-term key should not know past session key

#### RSA key exchange
![](https://i.imgur.com/MU9WHmU.png)
- problem: what if the attacker know the secret key?
- no forward secrecy

#### Diffie-Hellman key exchange
![](https://i.imgur.com/jjCcDw3.png)

## Interesting Security Games
### IND-EAV (Indistinguishable Eavesdropping)
- attacker send two plaintext
- challenger send one of the ciphertext
- if attacker can guess which the plaintext is, attacker win

### IND-CPA (Indistinguishable Choson Plaintext Attack)
- attacker send many plaintext to challenger
- challenger response ciphertext
- if attacker can guess what is the plaintext according to the ciphertext, attacker win
- who failed:
    - stream cipher who reuse the key
    - ECB
- who succeeded:
    - CBC
    - OFB
    - CTR

### IND-CCA (Indistinguishable Choson Ciphertext Attack)
- attacker send many ciphertext to challenger
- challenger response plaintext
- if attacker can guess what is the plaintext according to the plaintext. attacker win
- who failed:
    - El Gamal
- who succeeded:
    - RSA

### EU-CMA (Existential Unforgeability under a Choson Message Attack)
- if attacker can forge MAC, then attacker win
- who failed:
    - CBC-MAC
- who succeeded:
    - HMAC





