ALL Flashcards
What properties must a reference monitor have to be considered a Trusted Computer Base?
NEAT
Non-bypassable
Evaluable
Always invoked
Tamper-proof
What does a general mathematical formalisation of encryption/decryption contain?
- Finite set alphabet A
- Message space M subset of A*
plaintext m is an element of M - Ciphertext space C, alphabet may differ from M
- Space of keys K
- e element of K determined bijection from M to C denoted by Ee, encryption function expressed as Ee(M)=C
(same for d element of K with Dd) - encryption scheme is set {Ee|e element K} for each e element K there is d element K where Dd=Ee^-1
- e and d are key pair
- Encryption scheme constructed by fixing M, C, K, Ee, Dd
What is the formal description of Caesar Cipher?
- Message space M is set of all English character strings of arbitrary length
M={A, B, …, Z}={0, …, 25} - Key space K is set of all English character strings of length 1
K={A, …, Z}=M={0, …, 25} - Ciphertext space C is same as M
- Enc is addition of key to each character mod 26
Enc=(p1 + k)(p2 + k)…(pn + k) mod 26 - Dec is subtraction
What is the formal description of Vigenère cipher?
- Message space M is set of all English character strings of arbitrary length
M={A, B, …, Z}={0, …, 25} - Key space K is set of all English character strings of length N
K={A, …, Z}^N=M={0, …, 25}^N - Ciphertext space C is same as M
- Enc is addition of each key to each character mod 26
Enc=(p1 + k1)(p2 + k2)…(pn + kn) mod 26 - Dec is subtraction
What does Feistel Encryption include?
Input: 2w bit plaintext block, key K
- Divide plaintext into LEi and REi
- Derive subkey Ki from K
- LEi+1 = REi
- REi+1 = LEi XOR F(REi, Ki+1)
What does a round of DES involve?
- Initial permutation
- E table, XOR, S box, P
- XOR with Li-1 to get Ri
Li = Ri-1
KeyGen
- Input Key based on PC-1, treat as C0 and D0
- Rotate Ci-1 and Di-1 through circular left shift
- Input to next round
- Permute through PC-2 to input to F
What are the steps of Linear Cryptanalysis?
- Determine biases of S-boxes, construct LAT
- Approximate each S-box with (biased) linear expression
- Link expressions from initial plaintext to intermediate ciphertext
- Determine bias for linked expressions via Matsui’s Lemma
- For the final subkeys, determine how often expressions holds - if it matches bias, you have discovered the key!
- Repeat for each subkey
How to generate key pair for RSA?
- Generate large primes p and a
- Compute n = p x q and phi(n) = (p-1)x(q-1)
- Select e with 1 < e < phi(n) that is relatively prime to phi(n)
- Compute d = e^-1 mod phi(n)
How to encrypt and decrypt with RSA?
Encrypt:
Ci = Mi^e mod n
Decrypt:
Mi = Ci^d mod n
What is Extended Euclid’s algorithm?
EE(a,b)
if b=0 then
return (a, 1, 0)
else
(d’, x’, y’) <- EE (b, a mod b)
(d, x, y) <- (d’, y’, x’ - ([a/b] x y’)
What are the steps of Diffie-Hellman?
- Principals share prime number q and integer alpha that is a primitive root of q
- A and B generate XA and XB (private)
- YA =alpha^XA mod q
YB = alpha^XB mod q - KA = YB^XA mod q, KB = YA^XB mod q
KA= KB
What is Needham-Schroeder and what are the steps?
Goal: mutual authentication
1. A→B: {N1, A}KB
2. B→A: {N1, N2}KA
3. A→B: {N2}KB
vulnerable to man in the middle attack
High level overview of Kerberos
Authentication (session key, auth ticket, t1, key from users password)
Authorisation (auth ticket, authenticator, t2, session key, serv ticket)
Service (serv ticket, authenticator)
What does a round of Fiat-Shamir include?
T chooses large primes p and q, calculates n=pq
P chooses secret number s between 1 and n-1, calculates v=s^2 mod n
1. P chooses random no r as commitment 1<r<n-1
Calculates witness x = r^2 mod n and sends to V
2. V sends challenge c = {0,1}
3. P calculates y = (r.s^c) mod n and sends to V
4. V calculates y^2 mod n =?= (x.v^c) mod n
What is Matsui’s Lemma?
For binary independent (potentially biased) random variables Z1, … ZN
Pr(Z1 xor Z2 xor … xor ZN) = 1/2 + 2^N-1 x bias1 x bias2 x … x biasN
Bias of Zi represented by biasi
