Information Security
Ciphers
Classical
Modern
Public Key Cryptography
Mathematical problems
Integer factorization
Discrete logarithm problem
Elliptic curves
Applications
Public Key Encryption
Block ciphers
Stream ciphers
AES
DES
Modes of operation
CBC
ECB
CTR
Design criteria
Confusion and diffusion
Feistel network
Substitution-permutation network
n = lm
Round Function, KiWi
Encryption and decryption, LiRi
Differential and linear cryptanalysis
Plaintext and key avalanche
DES Feistel operation
Encryption operation
Double encryption
Meet-in-the-middle attack
Round-transformation
128 bits block size; 128,192,256 bits key size; 10, 12 or 14 rounds; byte based
64 bits block size; 56 bits key size; 16 rounds; bit based
Attacks
Exist on reduced-round version
Related key attacks
Most serious real attacks so far reduced effective key size by around 2 bits
CMAC (Authentication mode)
CCM (Authenticated Encryption mode)
Not randomized; Padding required; Error propagation within blocks; No IV; Parallel encryption and decryption
Randomized; Padding required; Error propagation within current block and specific bits of next block; IV must be random; Not parallell encryption but parallel decryption
Randomized; Padding not required; Error propagation within specific bits of current block; Nonce must be unique; Parallel encryption and decryption
Unforgeability: Without knowledge of the key K, it is not feasible to produce a message M and a tag T such that T = MAC(M, K)
MAC tag length (64 bits sufficient in most applications) = log_2 (I/R), I = limit on how many invalid messages are detected before the key is changed; R = acceptable probability (risk) that a false message is accepted
Payload: encrypted and authenticated; Associated data: only authenticated
CCM and GCM use CTR mode for confidentiality, but add integrity in different ways. They are both used in TLS 1.2
Pseudorandom numbers
TRNG rely on entropy sources -> physical noise source that is digitized and post-processed
PRNG uses seeds from TRNG
DRBG is recommended by NIST and based on
hash-functions
HMAC
block ciphers in counter mode
Security
Backtracking resistance
Forward prediction resistance
Types
CTR_DRBG
Dual_EC_DRBG
Based on Elliptic Curve discrete logarithm problem
Much slower than other DRBGs in the standard
Uses block cipher in CTR mode; AES with 128-bit keys is recommended.
Seed length = key length + block length (e.g. 128 + 128 = 256 for AES-128)
Seed defines a key K and counter value ctr, no separate nonce as in normal CTR mode. Encryption is run iteratively and output blocks form the output.
Update function
Each request generates 2^19 bits
Updating provides backtracking resistance
Standard restricts 2^48 requests to generate function before re-seeding is required.
Re-seeding provides forward prediction and backtracking resistance.
Synchronous stream ciphers
Key is generated independently of the plaintext, and both sender and receiver need to generate the same keystream and synchronize on its usage.
Ciphers
One-time pad
A5
A5/1
RC4
ChaCha
Binary synchronous stream cipher applied in most GSM mobile phones
Uses three Linear Feedback Shift Registers whose input is combined
Possible replacement for RC4
Number theory
CRT - Chinese Remainder Theorem
Euler function
Primality tests
Fermat
Miller-Rabin
Complexity theory
Hard problems
Discrete logarithm problem
Allows replacing computation on large integers with several similar computations on smaller integers, as long as you know the bounded size of the result
Finds all the integers less than n and relatively prime to n
Generating large primes: choose a random odd integer with the same number of bits as the required prime. Test if it's divisible by any of a list of small primes. Then apply Miller-Rabin test with 5 random (or fixed) bases. If this fails increment the number by 2 and test against small primes again, and then run miller rabin again and again til you find a prime.
Integer factorization
RSA
One-way functions
Multiplication of large primes; integer factorization
Exponentiation; discrete logarithm problem
Key generation algorithm
Encryption and decryption
Pre-processing before input (coding message as a number and adding randomness)
Applications
Message encryption
Digital signatures
Hybrid encryption - distributing a key for symmetric-key encryption
User-authentication - by proving you know the private key of a public key
Optimization
Key generation
Encryption
Decryption
Formatting data (padding)
Generating large primes with Miller-Rabin algorithm
Selecting e has an effect on efficiency
, e=3 smallest value, 2^16 + 1 popular choice, d should be at least sqrt(n)
Using fast exponentiation
Using fast exponentiation or CRT
Using Optimal Asymmetric Encryption Padding
Potential attacks
Factorization of n
Finding the private key from the public key
Quantum computers
Timing analysis uses timing of the decryption process to get information about the key
Key exchange
Elgamal
Diffie-Hellman
Hash functions and MACs
Security properties of hash functions
Collision resistant: It should be infeasible to find two values x1 and x2 such that H(x1) = H(x2)
Second-preimage resistant: Given a value x1 it should be infeasible to find a value x2 such that H(x1) = H(x2)
One-way (or preimage resistant): Given a value y it should e infeasible to find any input x such that H(x) = y
Hash functions should have output of at least 256 bits in order to avoid collision. For a random hash function of output size k bits, 2^k/2 trials are enough to find a collision with probability of around 0.5. In general the probability is around 0.5 to get two of the same value if you select sqrt(M) values from a set of size M.
Iterated hash functions
A hash function take arbitrary size input and make a fixed size output (digest)
Merkle-Damgård construction: use a fixed-size compression function applied to multiple blocks of the message. A compression functions take two n-bit input strings and produces an n-bit output string.
1) Break the message m into n-bit blocks
2) Add padding and an encoding of the length of m. This may or may not add one block
3) Input each block into the compression function h along with chained output; use IV to get started
Security of MD construction
If compression function h is collision resistant, then hash function H is collision resistant
Length-extension attack: once you have one collision, easy to find more
Second-preimage attacks not as hard as they should be
Collisions for multiple messages can be found without much more difficulty than collisions for 2 messages
Usages
Storing hashes of passwords together with the salt used to create the hash.
HMAC is using cryptographic hash functions to generate a MAC
Security
HMAC is secure if H is collision resistant or if H is a pseudorandom function
HMAC is designed to resist length extension attacks even if H is a Merkle-Damgård hash function
HMAC is often used as a pseudorandom function for deriving keys in cryptographic protocols
Authenticated encryption: split the key K into K1 and K2 encrypt with K1 for confidentiality and create MAC with K2 for authenticity and integrity. We use a dedicated algorithm for this. Encrypt the message then MAC it is the safest way.
Encrypt and MAC (insecure)
encrypt then MAC
MAC then encrypt (insecure)
Key establishment
Key pre-distribution
Session key distribution using symmetric keys
Session key distribution using asymmetric keys
Needham-schroeder protocol
Kerberos
General information
Requirements
Distribution of keys: should be in a secure fashion
Protection of keys: only accessible for use in relevant cryptographic algorithms, but not to unauthorized users
Destruction of keys: should be destroyed when served its purpose so that it is of no value to an attacker
Types of keys
Long term: used to protect distribution of session keys. Can be either symmetric or asymmetric
Short term: session keys used to protect communications in a session, e.g. in authenticated encryption. Usually symmetric keys used with ciphers such as AES and MACs because of efficiency
Mutual and unilateral
Generation of keys: all keys are equally likely to occur
Mutual authentication: both parties achieve authentication
Unilateral authentication: one party achieves authentication (very common)
TLS
History and overview
Attacks
TLS Record Protocol
TLS 1.3
TLS Handshake protocol
A cryptographic services protocol based upon PKI and commonly used on the internet
Runs primarily over TCP, but DTLS runs over datagram protocols
Provides message confidentiality and message integrity, from TLS 1.2 these services can be provided by authenticated encryption (CCM or GCM)
Operations
Record protocol headers
change-cipher-spec
alert
handshake
application-data
Fragmentation: each application layer message is fragmented into blocks of 2^14 bytes or less
Compression: optionally applied - default compression algorithm is null
Authenticated data: consists of the (compressed) data, the header, and an implicit record sequence number
Plaintext: compressed data and the MAC, if present
Session keys for the MAC and encryption algorithms, or the authenticated encryption algorithm, are computed during the handshake protocol
The encryption and MAC algorithms are specified in the negotiated ciphersuite
Algorithms
MAC algorithm
Encryption algorithm
Authenticated encryption algorithm
Purpose:
Negotiates the version of TLS and the cryptographic algorithms to be used.
Establishes a shared session key for use in the record protocol
Authenticates the server
Authenticates the client (optional)
Completes the session establishment
Handshake variants
RSA variant
DH variant
Pre-shared key variant
Mutual authentication or server-only authentication
Phases
Phase 1: initiates the logical connection and establishes its security capabilities
Pase 2 and 3: performs key exchange. The messages and message content used in this phase depend on the handshake variant negotiated in phase 1.
Phase 4: Completes the setting up of a secure connection.
Alert protocol
Improper handling of alert messages can lead to truncation attacks
Common TLS ciphersuites
Handshake algorithms
Record algorithms
DHE-RSA: Ephemeral DH with RSA signatures
ECDHE-RSA: Elliptic curve DHE with RSA signatures
DHE-DSS: DHE with DSS signatures
AES-GCM: AES authenticated encryption with GCM mode
AES-CBC-256: AES in CBC mode with HMAC from SHA256
CHACHA20-POLY1305: ChaCha stream cipher with Poly1305 MAC