CS4286 Cheat Sheet

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

• One-time 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 divide-and-conquer

  • An algorithm is secure if the best attack against it is brute-force → Minimum key length: 128 bit

  • DES: 56-bit key, 64-bit block

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

    • Process half the data block in each round

  • 3DES: two 56-bit keys

    • $C = \text{DES}(\text{DES}^{-1}(\text{DES}(M, K_1), K_2), K_1)$

  • DESX: three 56-bit keys

    • $C = K_3 \oplus \text{DES}(M \oplus K_1, K_2)$

  • AES: 128, 192, or 256-bit key, 128-bit 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_{n-1}), P_n = C_{n-1}\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_{n-1}), P_n = C_n\oplus E(K, C_{n-1})$, 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, (p-1)(q-1)) = 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

    • 2048-bit keys are now considered the standard

    • RSA problem - Wikipedia

• ElGamal

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

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

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

  • Encryption

    • Pick $r$ randomly from $Z_{p-1}$. 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$

      • Diffie-Hellman problem: find $g^{rx}\bmod p$ from $g^r\bmod p$ and $g^x\bmod p$

    • Solving DLP also solves Diffie-Hellman, but the converse is unresolved.

• Diffie-Hellman 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, non-repudiation, origin authentication

• Digital signature

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

  • Purpose: origin authentication, non-repudiation

  • 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

    • Pre-image 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 pre-image 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 (SHA-1 and SHA-2)

      • Susceptible to Length extension attack

    • Sponge function - Wikipedia (SHA-3)

• 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 non-repudiation 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

    • Prevent Padding oracle attack - Wikipedia

    • 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

  • Challenge-based response

    • Bob sends a nonce to Alice (single-use number)

    • Alice sends F(password, nonce) to Bob, where F is an one-way 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 (non-trivial)

    • 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

• Symmetric-key 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 well-known

    • 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

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

      2. 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 non-secret, then store $(s, H(\text{password}, s))$

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

  • Challenge-response or OTP

• Authorization

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

  • Role-based 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

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

    • Signature-based, 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)$

    • Signature-based, 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$

    • PKE-based does not offer non-repudiation, i.e., it has plausible deniability

  • Secure channel - ESP/AH

    • Two modes

      • Transport mode: for host-to-host link

        • IPSec wraps data but reuses the original header

      • Tunnel mode: for router-to-router or gateway-to-gateway

        • 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)

      • Challenge-response

        • 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: CRC-32

    • 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)

    • CBC-MAC 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)