1/100
Looks like no tags are added yet.
DES facts?
64-bit block, 56-bit key, 16 rounds.
AES facts?
128-bit block; 128/192/256-bit keys; 10/12/14 rounds.
Feistel equations?
L_i=R_(i-1); R_i=L_(i-1) XOR f(R_(i-1),k_i).
Feistel decryption?
Same structure, round keys reversed.
Confusion mainly comes from?
Nonlinear substitution / S-boxes.
AES diffusion mainly comes from?
ShiftRows and MixColumns.
AES round order?
SubBytes -> ShiftRows -> MixColumns -> AddRoundKey.
Final AES round omits?
MixColumns.
Why is DES weak?
56-bit key is too short.
Double DES attack?
Meet-in-the-middle.
ECB weakness?
Equal plaintext blocks give equal ciphertext blocks; patterns leak.
CBC core idea?
XOR plaintext with previous ciphertext before encryption; IV for first block.
OFB vs CFB?
OFB feeds cipher output and is synchronous; CFB feeds ciphertext and is self-synchronising.
CTR advantage?
Counter-based, hides repeats, parallelisable.
Preimage resistance?
Given digest D, infeasible to find M with H(M)=D.
Second-preimage resistance?
Given M, infeasible to find M != M' with the same hash.
Collision resistance?
Infeasible to find any distinct M,M' with H(M)=H(M').
Generic collision work for an n-bit digest?
About 2^(n/2).
256-bit digest generic collision security?
About 2^128 work.
Why must hash collisions exist?
Hashing is many-to-one: arbitrary-length inputs map to fixed-length outputs.
Merkle-Damgard h0?
A fixed IV.
Merkle-Damgard recurrence?
h_i = H(h_(i-1), M_i).
Merkle-Damgard final digest?
h(M)=h_n.
What happens to the final block in Merkle-Damgard?
It is padded and the message length is appended.
MAC vs MDC?
MAC uses a secret key; MDC is an unkeyed check/hash.
CBC-MAC core idea?
CBC-process the message and use the final output block as the MAC.
Why is H(k||m) risky with Merkle-Damgard?
Length extension: the digest exposes the final chaining state.
Password storage with salt?
Store
Is a salt secret?
No; it is a known random value stored with the digest.
Why use salts?
They defeat/prevent reuse of precomputed digest tables across passwords.
Hash-based PRNG recurrence?
S0=H(S), then S_i=H(S_(i-1)); extract a small number of bits.
Three PRG properties?
Randomness, unpredictability, unreproducibility.
Blum Blum Shub update?
X_(n+1)=X_n^2 mod m.
What secures Blum Blum Shub?
Difficulty of factoring m=pq.
Why not use BBS as a fast cipher?
It is too slow.
When does b have an inverse mod n?
Exactly when gcd(b,n)=1.
How do you calculate a/b mod n?
a*b^(-1) mod n.
What does XGCD give?
x,y with gcd(a,b)=xa+yb.
How does XGCD give a^(-1) mod n?
If 1=xa+yn, then x mod n is a^(-1).
What is phi(n)?
The number of residues modulo n relatively prime to n; |Z_n*|.
phi(p) for prime p?
p-1.
phi(pq) for distinct primes p,q?
(p-1)(q-1).
General totient formula?
If n=product p_i^e_i, phi(n)=product p_i^(e_i-1)(p_i-1).
Euler's theorem?
If gcd(a,n)=1, then a^phi(n)=1 mod n.
How does Euler help with modular powers?
Reduce the exponent modulo phi(n), when the base is invertible.
Fermat's Little Theorem?
If p is prime and p does not divide a, then a^(p-1)=1 mod p.
Purpose of square-and-multiply?
Efficient modular exponentiation using the binary exponent.
CRT condition for unique reconstruction?
The moduli must be pairwise coprime.
CRT core idea?
Compute modulo smaller coprime factors, then reconstruct the unique result.
Quadratic residue q mod n?
Some x exists with x^2=q mod n.
If n=pq and a is a QR in Z_n*, how many roots?
Exactly four.
How do you find roots mod pq?
Find roots mod p and mod q, then combine sign choices with CRT.
Exam trigger: a/b mod n?
Find b^(-1) with XGCD, then multiply by a.
Exam trigger: huge exponent mod n?
Look for phi/Euler or Fermat reduction, then square-and-multiply.
Exam trigger: all roots mod pq?
Factor n, solve mod each prime, combine four sign pairs with CRT.
RSA modulus?
n=pq for large primes p,q.
RSA phi(n)?
(p-1)(q-1).
Condition on RSA e?
gcd(e,phi(n))=1.
RSA private exponent d?
d=e^(-1) mod phi(n).
RSA public key?
(e,n).
RSA encryption?
c=m^e mod n.
RSA decryption?
m=c^d mod n.
RSA problem?
Given c,n,e with c=m^e mod n, recover m.
Why is RSAP no harder than factorisation?
Factor n, compute phi(n), find d, then m=c^d mod n.
Efficient RSA exponentiation algorithm?
Square-and-multiply.
How does CRT speed RSA private operations?
Exponentiate mod p and q separately, then recombine with CRT.
RSA signature idea?
Hash the message and apply the private-key operation to the digest.
RSA signature verification?
Apply the public-key operation to the signature and compare with the message hash.
What do digital signatures provide?
Authentication and non-repudiation.
Do signatures provide confidentiality?
No.
Why sign a hash instead of the whole message?
The digest is smaller, so signing is more efficient.
Toy RSA private-key question: first steps?
Factor n, compute phi(n), then d=e^(-1) mod phi(n).
Toy RSA encryption/decryption: method?
Write the modular exponentiation and use square-and-multiply; use CRT if helpful.
Two main security-protocol goals?
Entity authentication and key exchange.
How should a protocol exam answer be structured?
Objectives, exact protocol steps, security analysis.
What does a nonce provide?
Freshness / replay protection.
What does a timestamp provide?
Time-based freshness, usually requiring synchronised clocks.
NSPK objective?
Mutual authentication using public keys.
NSPK steps?
1 A->B:{N_A,A}_K_B+; 2 B->A:{N_A,N_B}_K_A+; 3 A->B:{N_B}_K_B+.
What breaks original NSPK?
Lowe's interleaving attack.
Diffie-Hellman objective?
Agree a shared symmetric key over an insecure channel.
DH messages?
A sends g^x mod p; B sends g^y mod p.
DH shared key?
g^(xy) mod p.
Main weakness of unauthenticated DH?
Man-in-the-middle attack.
NSSK objective?
Mutual authentication plus a trusted-server-generated session key K_AB.
NSSK steps?
1 A->T:A,B,N_A; 2 T->A:{N_A,B,K_AB,{K_AB,A}_KBT}_KAT; 3 A->B:{K_AB,A}_KBT; 4 B->A:{N_B}_KAB; 5 A->B:{N_B-1}_KAB.
NSSK freshness weakness?
An old compromised session key/ticket can be replayed because B cannot directly prove freshness.
What is Kerberos based on?
Needham-Schroeder Secret-Key.
Main Kerberos difference from NSSK?
Timestamps and explicit session-key/ticket lifetimes.
Kerberos trusted server name?
Key Distribution Centre (KDC).
Kerberos steps?
1 A->T:A,B,N_A; 2 T->A:{K_AB,A,L}_KBT,{K_AB,N_A,L,B}_KAT; 3 A->B:{K_AB,A,L}_KBT,{A,T_A}_KAB; 4 B->A:{T_A}_KAB.
What is L in Kerberos?
Session-key/ticket validity period.
Does Kerberos rely on timestamps?
Yes.
Otway-Rees objective?
Mutual authentication plus trusted-server generation of a fresh session key.
Does Otway-Rees need synchronised clocks?
No; it uses nonces for freshness.
Otway-Rees steps?
1 A->B:N,A,B,{N_A,N,A,B}_KAT; 2 B->T:N,A,B,{N_A,N,A,B}_KAT,{N_B,N,A,B}_KBT; 3 T->B:N,{N_A,K_AB}_KAT,{N_B,K_AB}_KBT; 4 B->A:N,{N_A,K_AB}_KAT.
What is N in Otway-Rees?
A transaction identifier binding A and B data to the same run.
What do N_A/N_B do in Otway-Rees?
Guarantee freshness of the server response/session key.
Otway-Rees weakness in the notes?
Type-flaw attack.
What is a type-flaw attack?
Data of one type is misinterpreted as another type.