cis4360 midterm part 2 #fml

home assignments. these are all short-answer written questions (minus the 5 that are multiple choice).

if a reversible n-bit block mapping is used for a substitution, what would the minimum bit-length of the key be

[log2((2^n)!)] bits

choose 128 linearly independent plaintexts

obtain their 128 ciphertexts

express any target ciphertext as a XOR combination of those basis ciphertexts

XOR the corresponding plaintexts to recover the original plaintext, without knowing the key

OC

[88][77][66][99]

x * (x² + 1) = x³ + x

x³ + x + 1 = 0

x³ + x = 1

101 = x² + 1

x * (x² + 1) = 1 (from the previous question)

x = 010

[01]

2nd entry:

[01][0E] XOR [02][09] XOR [03][0D] XOR [01][0B]

[01][0E] = [0E]

[02][09[

[09] = 00001001 (shift left) → 00010010 = [12]

[03][0D] = [02][0D] XOR [01][0D]

[0D] = 00001101 (shift left) → 00011010 = [1A]

[01][0D] = [0D]

[1A] XOR [0D] = 00010111 = [17]

[01][0B] = [0B]

0E XOR 12 XOR 17 XOR 0B

0E (00001110) XOR 12 (00010010) = 1C (00011100)

1C (00011100) XOR 17 (00010111) = OB (0000 1011)

OB XOR OB = 00

show the value of the state matrix after initial AddRoundKey

00 04 08 0C

01 05 09 0D

02 06 0A 0E

03 07 0B OF

01 05 09 0D

00 04 08 0C

03 07 0B OF

02 06 0A OE

ECB

Parallel?

Error Propagation:

Requirements:

Security:

yes. independent blocks. none. insecure.

CBC

Parallel?

Error Propagation:

Requirements:

Security:

no. affects some blocks. random IV. secure.

CTR

Parallel?

Error Propagation:

Requirements:

Security:

yes. none. unique nonce. secure.

GCM

Parallel?

Error Propagation:

Requirements:

Security:

yes. none. unique nonce. secur

why is ECB mode considered insecure? give a real-world example of where this weakness becomes visible

identical plaintext blocks give identical ciphertext blocks, which reveals the structure and patterns of the plaintext. 2013 Adobe breach.

why must IVs in CBC mode be unpredictable, while nonces in CTR mode must be unique but not necessarily random

in CBC mode, an unpredictable IV prevents attackers from predicting how a chosen plaintext will be encrypted. in CTR mode, a nonce must be unique with each key to prevent reusing the same keystream, which can expose plaintexts.

in CTR mode, what happens if the same nonce is reused with the same key? show how an attacker can recover information from 2 ciphertexts encrypted under the same keystream.

if one plaintext is known we can use XOR to get P2 = C1 XOR C2 XOR P1

P2 = Dk(C2) XOR C1

what is the security basis of RSA

multiplying numbers is easy, but going backwards is a lot harder. RSA’s private key depends on knowing the 2 original primes, which means an attacker has to “undo” the multiplication to break RSA

because there’s no private key d if they are not. you could lock messages but never actually unlock them.

why is “textbook RSA” insecure in practice?

because it is deterministic, malleable, and vulnerable to chosen ciphertext attacks.

what problem does OAEP padding solve

it adds randomness, which makes encryption probabilistic and gives semantic security.

n = 3233

60 × 52 = 3120

d = 2753

3120/17 = 183 remainder 9

17/9 = 1 remainder 8

9/8 = 1 remainder 1

9 = 3120-183×17

8 = 17-9

1 = 9-8

1 = 9 - (17-9)

1 = 2×9-17

1 = 2*(3120-183×17)-17

1 = 2×3120-366×17-17

1 = 2×3120-367×17

-367+3120=2753

m^ed = m^ko/(n)+1 = (m^o/(n))^k * m = m (mod n)

explain why small public exponent attacks can be dangerous without padding

if M is small, then M^e < n. no modular reduction happens. the attacker takes the integer e-th root of the ciphertext to get M.

describe a chosen-ciphertext attack against textbook RSA.

the adversary can ask for the plaintext of C’ = C*r^e mod n and then divide by r to get M

explain the RSA common modulus attack.

c1^a * c2^b = m^(ae1+be2) = m’ = m (mod n)

what is a timing attack in RSA? why does it work?

infer bits of the private exponent d because decryption does an extra multiplication for each 1-bit of d. the time it takes depends on d’s bits. the attacker can work out d one bit at a time by measuring many decryptions

Why does RSA encryption not provide forward secrecy?

if a private key leaks, all traffic is decryptable because every recorded session key was encrypted under that one long-term private key. the attacker can recover each session key and decrypt the recorded traffic.

describe the diffie-hellman key exchange protocol.

Public: a prime p and a number g that everyone can see

A picks a number a and sends g^a mod p

B picks a number b and sends g^b mod p

Shared: A computes (g^b)^a = g^ab and B computes (g^a)^b = g^ab. The eavesdropper sees p, g, g^a, and g^b but not a or b so they don’t know g^ab.

what mathematical assumption does Diffie-Hellman rely on

hardness of the discrete logarithm problem. computing g^a is easy but recovering a from g^a is basically impossible when p is big

What are the following problems?

The Discrete Log Problem:

Computational Diffie-Hellman:

Decisional Diffie-Hellman:

given p, g, and g^a find a

given p, g, g^a, and g^b compute g^ab

given p, g, g^a, and g^b distinguish g^ab from a random value g^c

explain the Man-in-the-Middle attack on Diffie-Hellman

an attacker intercepts and replaces the public keys exchanged by Alice and Bob, establishing separate shared keys with each. the attacker can read, modify, and forward their messages without them realizing

why does authenticated Diffie-Hellman prevent MITM

it authenticates the exchanged public keys using digital signatures or certificates, which prevents an attacker from replacing them undetected

what happens if the DH parameters are weak:

if g’s powers cycle through only a few values, then g^a takes only a few possible values. the key space collapses since an attacker will just be able to try them all.

if p is small, there are few possible values mod p. an attacker can solve the discrete log directly by brute-forcing every exponent a until g^a matches.

5^6 = 15625

15625 mod 23 = 8

public key: (23, 5, 8)

Explain how ElGamal encryption works.

Public key:

Encrypt message m:

Decrypt ciphertext (c1,c2):

p, g, y = g^x mod p

c1 = g^k mod p, c2 = m*y^k mod p

m = c2 * (c1^x)^-1 mod p

why is randomness (k) required in ElGamal encryption ?

(the answer is an equation)

m’ = m * c2^1 * c2^-1 mod p

show the ElGamal encryption and decryption formulas

encrypt m: c1=g^k mod p, c2 = m * y^k mod p

decrypt (c1,c2): m = c2 * c1^-x mod p

what happens if the same random value k is reused in 2 ElGamal encryptions?

the value m/m’ mod p can be computed by anyone from the ciphertexts because it is equivalent to c2/c2’ mod p.

explain why ElGamal is malleable.

if (c1,c2) is the ElGamal encryption of m then (c1, m’ * c2) is the encryption of m’ * m (mod p)

explain how ElGamal can be converted into a digital signature scheme:

the ElGamal digital signature is (r,s) where r = g^k mod p and s = k^-1 * (h(m) - x * r) mod (p-1)

C

A

D

B

C

what types of attacks are addressed by message authentication

masquerade attacks, content modification, sequence modification, and timing modification

what is the difference between a message authentication code and a one-way function

a one-way function is easy to compute but computationally difficult to reverse. a message authentication code uses a secret key with a message to produce an authentication tag.

in what ways can a hash value be secured so as to provide message authentication

symmetric encryption, a message authentication code, a digital signature

compute the tag T for the single block D

T = E(K,D)

compute the tag T’ for the string of 2 blocks D, D XOR T and show that it has the same tag T

O2 = E(K, D2 XOR O1)

O2 = E(K, (D XOR T) XOR T)

O2 = E(K, D XOR (T XOR T))

O2 = E(K, D XOR O)

O2 = E(K, D)

T’ = O2 = T

what does this mean ? how can this be addressed ?

an attacker who knows a valid message D and its tag T can produce a different message with the same tag. a verifier that only checks the tag could accept the fake message. you can address this by using a secure construction for messages of varying lengths.

this matrix is in a useful form for Alice to encrypt messages. construct a matrix with the same information that is useful for Bob to decrypt messages.

Ciphertext/Key 1 2 3 4

00 0 1 Invalid Invalid

01 1 Invalid 0 Invalid

10 Invalid 0 Invalid 1

11 Invalid Invalid 1 0

what is the probability that someone can replace an intercepted message with another message successfully

P = ½ = 50%

what is the probability that someone can successfully impersonate Alice

P = ½ = 50%

the DH protocol is subject to a MITM attack in which an adversary, say Trudy, manages to get in the middle of the conversation between Alice and Bob, relaying the messages in such a way that Trudy can impersonate both of them. one way to prevent such attacks is to encrypt the DH values sent with the other side’s public key. show why this is the case, given that the attacker can encrypt whatever they want with the other side’s public key ?

Trudy cannot impersonate Alice or Bob without their private decryption keys, so she cannot read and replace the DH values undetected.