CS4286 Cheat Sheet
· 12 minutes read
2 Symmetric Cryptography
Classical cryptography

Ceasar cipher, simple substitution

Vigenère cipher: use multiple cipher alphabets, which can be Ceasar cipher alphabets that start from the letters of a word as key.
 Considered secure until Kasiski examination in 1863

Onetime pad

Plaintext XOR key → ciphertext. Ciphertext XOR key → plaintext

Key must be random, used only once, and has the same size as message

Good: relatively secure

Bad: key management


Stream cipher (RC4)

Produce a keystream from a small key and a deterministic keystream generator

The keystream is then used to encrypt the plaintext of arbitrary length


Block cipher

Encrypt a block of plaintext with the key to produce a block ciphertext; key is reused for all blocks

Properties

Confusion: small changes in the key yield 50% changes in the ciphertext

Diffusion: small changes in the plaintext yield 50% changes in the ciphertext

Completion: each bit of the ciphertext depends on every bit of the key
 Attacker cannot guess a part of a key using divideandconquer


An algorithm is secure if the best attack against it is bruteforce → Minimum key length: 128 bit

DES: 56bit key, 64bit block

Initial permutation, then 16 rounds of Feistel transformation, then final permutation

Process half the data block in each round


3DES: two 56bit keys
 $C = \text{DES}(\text{DES}^{1}(\text{DES}(M, K_1), K_2), K_1)$

DESX: three 56bit keys
 $C = K_3 \oplus \text{DES}(M \oplus K_1, K_2)$

AES: 128, 192, or 256bit key, 128bit block

State is represented as a 4x4 table of 16 bytes

Substitution–permutation network of 10 to 14 rounds

Each round except the last has 4 operations (ByteSub, ShiftRow, MixColumn, AddRoundKey)


Modes of operation: how to encrypt multiple blocks $P_0, P_1, \ldots$

ECB: encrypt each block independently
 $C_n = E(K, P_n), P_n = E(K, C_n)$

CBC: chain blocks together

Use a random (but not secret) initialization vector (IV)

$C_n = E(K, P_n \oplus C_{n1}), P_n = C_{n1}\oplus E(K, C_n)$, with $P_{1} = IV$


CTR: counter mode (popular for random access)
 $C_n = P_n \oplus E(K, IV + n), P_n = C_n\oplus E(K, IV + n)$

CFB: combines CBC and CTR
 $C_n = P_n \oplus E(K, C_{n1}), P_n = C_n\oplus E(K, C_{n1})$, with $C_{1}=IV$


3 Number theory
Extended Euclid’s algorithm
def extendedEuclidean(a, b):
if b == 0:
return a, 1, 0
else:
d, x, y = extendedEuclidean(b, a % b)
return d, y, x  (a // b) * y
4 Public key cryptography

Each person has a pair of key: a public key and a private key

RSA

Two large primes with similar length: $p$ and $q$

Let $n=pq$, choose a random $e$ with $\gcd(e, \phi(n)) = \gcd(e, (p1)(q1)) = 1$.

Find $d$ such that $de\equiv 1 \pmod{\phi(n)}$

Public key: $(n,e)$. Private key: $d$

Encryption: $C=M^e\bmod n$. Decryption: $M=C^d\bmod n$

Security

Depends on the intractability of factoring large primes

2048bit keys are now considered the standard



ElGamal

For a large prime $p$, let $Z_p^* = \{1,2,\ldots,p1\}$ and $Z_{p1} = \{0,2,\ldots,p2\}$.

Let $g\in Z_p^*$ be such that none of $g^1, g^2, \ldots, g^{p2}$ is equal to $1 \bmod p$.

Private key: $x$ picked randomly from $Z_{p1}$, public key: $y=g^x\bmod p$

Encryption

Pick $r$ randomly from $Z_{p1}$. Ciphertext is the pair $(A, B)$.

$A=g^r\bmod p$, $B=My^r\bmod p$ where $M\in Z_p^*$ is the message


Decryption: $K = A^x\bmod p$, $M=BK^{1}\mod p$

Security

Given the ciphertext $(A, B)$ and public key $y=g^x\bmod p$, the adversary can break the scheme if they can break

Discrete log problem: find $r$ such that $A=g^r\bmod p$ or $x$ such that $y=g^x\bmod p$

DiffieHellman problem: find $g^{rx}\bmod p$ from $g^r\bmod p$ and $g^x\bmod p$


Solving DLP also solves DiffieHellman, but the converse is unresolved.



DiffieHellman key exchange

Alice sends $g^a\bmod p$ to Bob, while Bob sends $g^b\bmod p$ to Alice

Both computes $g^{ab}\bmod p$ as the symmetric key

Secure against eavesdroppers but not MITM

5 Integrity

Detect modification, nonrepudiation, origin authentication

Digital signature

Characteristics: easy for author to sign, easy for anyone to check, difficult for anyone else to forge

Purpose: origin authentication, nonrepudiation

Method
 Asymmetric cryptography: sign using private key, verify using public key

RSA signature scheme

$n=pq$ where $p$ and $q$ are large primes, $e$ coprime to $\phi(n)$

Signing key $d = e^{1} \bmod \phi(n)$

Verification key $(e, n)$

Signing: $S=M^d\bmod n$

Verification: valid if and only if $S^e\bmod n = M$

Problem

Message must has size at most $n$

RSA has cubic time complexity with regards to key length



Other: ElGamal, DSA signature schemes


Hash function

Properties

Compression: arbitrary length input to output of small, fixed length

Easy to compute: expected to run fast

Preimage resistance: given a hash value $y$ it is infeasible to find an $x$ such that $h(x) = y$

Collision resistance: infeasible to find $x$ and $y$, with $x \ne y$ such that $h(x) = h(y)$

Second preimage resistance: given $y$ and $h(y)$, infeasible to find $x$ where $h(x)=h(y)$


A $N$bit hash function needs $2^{N/2}$ operations to have a >50% chance of finding a collision

Block ciphers not suitable due to their small block sizes

Merkle–Damgård construction  Wikipedia (SHA1 and SHA2)
 Susceptible to Length extension attack

Sponge function  Wikipedia (SHA3)



Message authentication

Method: symmetric cryptography

Alice and Bob share a secret key $K$

Alice creates a MAC tag using the message and $K$, then send it along with the message.

Bob computes a MAC tag using the message and $K$ then check if it is the same as the received MAC tag.


Does not provide nonrepudiation as both sender and receiver share a key
 E.g., after Alice sent Bob a message with MAC tag, Alice can claim that she never sent it as Bob could have made the message and the MAC tag himself.

HMAC

Use two different keys $K_1$ and $K_2$ and a hash $H$

$\text{HMAC}_k(M) = H(K_2 \ \ H(K_1\  \ M))$


Provide both integrity and confidentiality: encrypt then MAC (preferred)

Detect modification before decrypting

Can be done in one go with Authenticated encryption  Wikipedia


6 Authentication

Entity authentication

Alice wants to prove her identity to Bob, e.g. for password authentication

Sending encrypted or hashed password is prone to replay attack

Challengebased response

Bob sends a nonce to Alice (singleuse number)

Alice sends F(password, nonce) to Bob, where F is an oneway function


Formal definitions

Claimant: entity claiming an identity

Principal: the claimed identity

Verifier: entity verifying the principal


Entity authentication protocol: a sequence of messages between the claimant and the verifier to confirm the identity of the claimant


Origin authentication

Integrity

Sends a manipulation detection code (MDC) to the message before encryption

The message is uncompromised if the MDC is expected


Freshness

Timestamp: requires secure synchronization (nontrivial)

Counter: shared by both parties, similar to TCP sequence number

Nonce: can use counter, but sometimes need to be random



Attacks

Masquerade: faking identity
 Prevented by origin authentication

Replay attack: replay the message to the verifier
 Prevented by freshness

Reflection attack

The data produced by the verifier is sent back to the verifier

Mallory intercepts and gets the nonce, who asks Bob to verify with the same nonce

Bob sends the valid verification with that nonce, which Mallory then sends back to Bob


Prevented by destination authentication, i.e., putting receiver identifier in the message


7 Key management

Components

Key agreement: establishing a key but neither entity has key control

Key transport: securely transferring a key from one entity to another

Key confirmation: assurance that another entity has a key

Implicit key auth to A: A knows only another identified entity can possess a key

Explicit key auth to A: A knows another identified entity actually possess a key



Hardware Security Module (HSM): trusted, key generation and storage

Symmetrickey protocols

Directly communicating entities

Two entities directly communicate to establish keys

Must use a secure channel


Key translation center (KTC): trusted entity transports keys between entities

Key distribution center (KDC): trusted entity generate and distribute keys to entities
 The KDC has complete key control


Key hierarchy

Key in higher levels used to protect or generate keys in lower layers; eys in the lowest levels are session keys, used for data security key

Key establishment from nothing is hard; the longer the lifespan of key, the less often it should be used


Public key management

How to verify A’s public key?

Digital certificates: a document from a trusted Certificate Authority vouching that a public key belongs to some entity

The identity of the owner and the public key

The expiry date of the certificate

The CA’s signature


Certificate Authority (CA): trusted party whose public key is wellknown

How to verify CA’s public key? → built into browsers/operating systems

Responsible for identify entities before generating certificate, generating or verifying user key, and keeping its private key secret

Before generating a certificate, the CA should check a user knows the private key coupled to its claimed public key


Relationships

User requests key pair from key generation facility (KGF, can be user, TTP, CA, …)

KGF sends key pair to user and CA

User proves its identity to the CA through the registration authority or directly

The CA generates and published the certificate


Standard: X.509 certificate

CA can revoke a certificate by

Certificate Revocation Lists (CRLs), signed by CA

Online certificate status protocol (OCSP) allows certificate status to be queried


PKI trust models

Monopoly: one universally trusted organization is the CA for the entire world

Anarchy model: everyone is a CA, users decide which CAs to trust themselves (PGP)

Structured model: multiple trusted CAs

Cross certification: two CAs accept certificates produced by the other

Certificate hierarchy: root CA certifies other CA’s certificates

Certificate chains


Example: EMV smart cards

Card signs transaction data and sends the certificate signed by card’s vendor

The reader has card vendor’s certificate and can verify the card certificate



8 Computer security

Access control

Authentication: who are you?

Authorization: what are you allowed to do?


Authentication

Password

Prone to human error and laziness, timing attack based on how long it takes to compare passwords, phishing attacks, social engineering attacks

Hash the password

Prone to dictionary attack: precomputed hashes of common terms

Hash with salt, a random nonsecret, then store $(s, H(\text{password}, s))$



2factor authentication: requires 2 different proof of identity (password + security token, ATM card + pin)

Challengeresponse or OTP


Authorization

Lampson’s access control matrix: specifies permissions of each users on each resources

Rolebased access control: each user is assigned a role, each role is assigned rights to resources


Firewall

Allows traffic into or out of internal network

Packet filter: network layer

Filter based on: source and destination IP addresses, source and destination port, flag bits

Pros: fast

Cons

Cannot see application data

Cannot see TCP connections

Prone to TCP ACK packet attack



Stateful packet filter: transport layer

Add states to remember TCP connections and flag bits. Can remember UDP packets (e.g., DNS requests)

Pros: can do everything a packet filter can plus keeping track of ongoing connections

Cons

Cannot see application data

Slower than packet filtering



Application proxy: application layer

Looks at incoming application data

Pros

Complete view of connections and applications data

Filter bad data using more sophisticated rules


Cons: slow


Malware
Malware  Description  Host Program  Replication  Example 

Backdoor  a secret entry point into a program, usually inserted during code development or testing  yes  no  xz backdoor 
Logic bomb  code that is set to explode when certain conditions are met  yes  no  railway service in Poland, 2024 
Trojan horse  hidden code that perform hidden function  yes  no  
Virus  infect other programs by modifying them  yes  other files  
Bacteria  replicate itself to take up resources  no  launch more instances  
Worm  spreading to other machines over network  no  over network  ILOVEYOU (2000) 
Ransomware  encrypt user data and demand payment for decryption  no  no  Wannacry 
9 Network Security

TLS/SSL (transport layer)

TLS/SSL lies between HTTP and TCP, securing transactions over the Internet

TLS is the modern version of SSL

Handshake: authentication, key establishment, cipher options

Record: confidentiality and integrity


TLS simple flow

A → B: cipher suites, TLS version, $R_A$

B → A: cipher suites, CertB, $R_B$

A → B: $\{S\}_B, \text{PRF}(K, h(\text{message}))$

$S$ is randomly chosen by A, $K = h(S, R_A, R_B)$

$\text{PRF}$ is a pseudorandom function


B → A: $\text{PRF}(K, h(\text{message}))$

A ↔ B: data encrypted with $K$


Efficient way to open new connections given an existing secured session, i.e., $S$ is already known


IPSec (network layer)

Establish a session key  IKE

Signaturebased, main mode

A → B: crypto proposed; B → A: crypto selected

A → B: $g^a\bmod p, R_A$; B → A: $g^b\bmod p, R_B$

A → B: $E(K, ID_A  \text{proof}_A)$; B → A: $E(K, ID_B  \text{proof}_B)$


Signaturebased, aggressive mode

A → B: Alice, crypto proposed, $g^a\bmod p, R_A$; B → A: Bob, crypto selected, $R_B, g^b\bmod p, \text{proof}_B$

A → B: $\text{proof}_A$

Does not protect identities, cannot negotiate $g$ or $p$


PKEbased does not offer nonrepudiation, i.e., it has plausible deniability


Secure channel  ESP/AH

Two modes

Transport mode: for hosttohost link
 IPSec wraps data but reuses the original header

Tunnel mode: for routertorouter or gatewaytogateway

IPSec wraps the entire original packet in new packet

Original IP header not visible



AH: authentication header

Only message authentication

Transport:
[ original IP header  AH  payload ]

Tunnel:
[new IP header  AH  original IP header  payload ]


ESP: encapsulating security payload

Encryption only, or encryption with message authentication

Transport:
[ original IP header  ESP header  payload  ESP trailer  ESP auth ]

Tunnel:
[ new IP header  ESP header  original IP header  payload  ESP trailer  ESP auth ]




Mobile network security

Requirements: confidentiality, anonymity, prevent malicious users from using phones

GSM (second generation)

Components

Mobile phone contains SIM, the security module

IMSI (International Mobile Subscriber ID)

User key Ki (128 bit)


Visiting network: network where the phone is currently located

Base station

Base station controller manages many cells

Visitor Location Register (VLR)


Home network

Home Location Register (HLR) keeps track of most recent location of phone

Authentication center (AuC)



Anonymity

IMSI is used to identify users initially

TMSI (Temporary Mobile Subscriber ID) is used, which changes frequently and is encrypted


Authentication

Caller is authenticated to the base station (not mutual)

Challengeresponse

AuC generates random nonce R and sends (R, A3(R, Ki)) to the base station

Base station sends R to mobile phone

Mobile phone sends back A3(R, Ki) to the base station



Confidentiality: data encrypted with stream cypher A5

Insecurity

Weak hash, weak encryption

No encryption from base station to base station controller



3GPP (third generation)

Mutual authentication

Keys (encryption/integrity) cannot be reused, triples cannot be replayed

Strong encryption algorithm (AES), message authentication

Encryption extended to base station controller

Authentication and Key Agreement (AKA)



Wifi security

WEP (BROKEN)

Secret key: 40 or 104 bits. Integrity: CRC32

Keystream: generated by RC4


WPA

Authentication: session keys using EAP

Encryption: temporal key integrity protocol (TKIP)

Integrity: proprietary Michael algorithm


WPA2

AES (still operating like a stream cipher in Counter Mode)

CBCMAC for integrity



Denial of Service (DoS)

Actions by a third party preventing authorized users from access to or use of a resource or service

Sources of consumption

Network connectivity

Bandwidth consumption

Others (state storage, disk space, power)


Resource amplification

Attacker either need more resource than victim or be able to force an asymmetric workload


Distributed Denial of Service (DDoS)

Multiple machines perform a synchronized attack

One DDoS “master” program controls a number of “agent” program

Botnet

Infection through trojans or worms (download, email, etc.)

Command and control (centralized, P2P, etc.)

Communication protocols (IRC, HTTP, P2P, etc.)

Payload/action (spam, DDoS, keyloggers, Bitcoin mining)

