CS 3IS3. Sample solutions to the assignment 1.
Total of this assignment is 139 pts. Each assignment is worth 20% of total. Many solutions are not unique.
If you think your solution has been marked wrongly, write a short memo stating where marking in wrong and what you think is right, and resubmit to me via e-mail (as pdf). The deadline for a complaint is 2 weeks after the assignment is marked and returned.
1.[15] Write a program in Java that tries to decrypt a message encrypted with a simple substitution cipher (page 14 of LN1). Assume English and frequencies from page 16 of LN1.
First write a method to help an analyst decrypt a simple substitution cipher. This method should take the ciphertext as input, compute letter frequency counts, and display these for the analyst. Just in case, the method should then allow the analyst to guess a key and display the results of the corresponding “decryption” with the putative key.
In case guessing a key does not work, the program should try to decrypt the message. One sensible way to proceed is to use the computed letter frequencies and the known frequencies of English for an initial guess at the key. Then from the resulting putative decryption, count the number of dictionary words that appear and use this as a score. Next, for each letter in the key, try swapping it with the letter that is adjacent (with respect to frequency counts) and recompute the score. If the score improves, update the key; if not, don’t change the putative key. Iterate this process until the score does not improve for an entire pass through the alphabet. At this point you will give your putative decryption to the analyst.
With a help of your program, decrypt:
MXDXBVTZWVMXNSPBQXLIMSCCSGXSCJXBOVQXCJZMOJZCVC TVWJCZAAXZBCSSCJXBQCJZCOJZCNSPOXBXSBTVWJC JZDXGXXMOZQMSCSCJXBOVQXCJZMOJZCNSPJZHGXXMOSPLH JZDXZAAXZBXHCSCJXTCSGXSCJXBOVQX
Solution.
This is an open ended programming problem that has many solutions. For the ciphertext above: the key is ZGYHXIWJVKULTMSARBQCPDOENF and the plaintext is from Alice in Wonderland (without spacing):
Never imagine yourself not to be otherwise than what it might appear to others that what you were or might have been was not otherwise than what you had been would have appeared to them to be otherwise.
1
2.[5] Encrypt the message:
we are all together
using a double transposition cipher (of the type described in LN1) with 4 rows and 4 columns, using the row permutation: (1,2,3,4) → (2,4,1,3)
and the column permutation: (1,2,3,4) → (3,1,2,4).
Solution:
The ciphertext is LEALETHRAWERGTOE.
3.[8] The following message was encrypted using a Vigenère cipher with a 3-letter English keyword:
CTMYR DOIBS RESRR RIJYR EBYLD IYMLC CYQXS RRMLQ FSDXF OWFKT CYJRR IQZSM X
Decrypt it. Use letters frequencies and your thinking skills.
Solution:
The plaintext is:
Spoon feeding in the long run teaches us nothing but the shape of the spoon.
4.[10] Suppose that a particular cipher uses a 40-bit key, and the cipher is secure (i.e., there is no known shortcut attack).
a.[3] How much work, on average, is an exhaustive search attack? b.[3] Outline an attack, assuming that known plaintext is available. c.[4] How would you attack this cipher in the ciphertext-only case?
Solution:
a. You must try half of the keys, on average, for a work factor of 239.
b. Do the exhaustive key search, and for each putative key, “decrypt” the ciphertext. Since
you know the corresponding plaintext, you’ll know when you’ve got the correct key.
c. This is not so easy, since you will have to do some work to tell when you’ve got the
correct key. If you know the plaintext is English, you could, in principle, visually inspect each putative decrypt until you see one that looks like English, but that would be impractical for such a large key space. To automate the attack, you would need to automatically test the putative decrypts to see if they appear to be English, which requires some additional work.
2
5.[6] Implement (in Java or C) the A5/1 algorithm. Suppose that, after a particular step, the values in the registers are
X = (x0, x1,…, x18) = (1010101010101010101)
Y = (y0 ,y1,…, y21) = (1100110011001100110011) Z = (z0, z1,…, z22) = (11100001111000011110000)
List the next 32 keystream bits and give the contents of X, Y, and Z after these 32 bits have been generated.
Solution:
Program is not provided. The keystream bits are
k0k1k2 … k32 = 10000011011100000111100000011001 and the registers are
and and
X = x0x1x2 … x18 = 0001101000000000000
Y = y0y1y2 … y21 = 1111101010101010101010 Z = z0z1z2 … z22 = 01101010111100001010101:
6.[5] Suppose that Trudy has a ciphertext message that was encrypted with the RC4 cipher (see LN2, pages 8,9 or Tables 3.1, 3.2 in the textbook). For RC4, the encryption formula is given by ci = pi ⊕ ki, where ki is the ith byte of the keystream, pi is the ith byte of the plaintext, and ci is the ith byte of the ciphertext. Suppose that Trudy, an attacker, knows the first ciphertext byte, and the first plaintext byte, that is, Trudy knows c0 and p0.
a.[2] Show that Trudy can determine the first byte of the keystream k0.
b.[3] Show that Trudy can replace c0 with c’0, where c’0 decrypts to a byte of Trudy’s
choosing, say, p’0.
Solution:
a. Trudy computes k0 = c0 ⊕ p0.
b. Replacec0 withp’0 ⊕k0 =p’0 ⊕(c0 ⊕p0).
3
7.[10] Consider a Feistel cipher with four rounds. Then the plaintext is denoted as P = (L0, R0) and the corresponding ciphertext is C = (L4, R4). What is the ciphertext C, in terms of L0, R0, and the subkey, for each of the following round functions?
a.[2] F(Ri-1, Ki) = 0
b.[2] F(Ri-1, Ki) = Ri-1
c.[3] F(Ri-1, Ki) = Ki
d.[3] F(Ri-1, Ki) = Ri-1 ⊕ Ki
Solution:
a. WehaveC=P.
b. Here,wefindC=(R0,L0⊕R0).
c. C = (L0 ⊕ K1 ⊕ K3 ⊕ … ⊕ K15 , R0 ⊕ K2 ⊕ K4 ⊕ … ⊕ K16)
d. C=(R0⊕K2⊕K3⊕K5⊕K6⊕K8⊕K9⊕K11⊕K12⊕K14⊕K15,
L0 ⊕K1 ⊕K3 ⊕K4 ⊕K6 ⊕K7 ⊕K9 ⊕K10 ⊕K12 ⊕K13 ⊕K15 ⊕K16)
8.[6] Suppose that we use a block cipher to encrypt according to the rule C0 = IV ⊕ E(P0, K), C1 = C0 ⊕ E(P1, K), C2 = C1 ⊕ E(P2, K), …
a.[3] What is the corresponding decryption rule?
b.[3] Give two security disadvantages of this mode as compared to CBC mode.
Solution:
a. The decryption rule is:
P0 =D(C0 ⊕IV,K),Pi=D(Ci ⊕Ci-1,K)
b. This approach is no better than ECB mode, since Trudy (an attacker) can compute
Ci ⊕Ci-1 to obtain ECB mode data. Consequently, this mode has all of the same problems as ECB mode.
9.[5] Using CBC mode, Alice encrypts four blocks of plaintext, P0, P1, P2, P3 and she sends the resulting ciphertext blocks, C0, C1, C2, C3, and the IV to Bob. Suppose that Trudy (an attacker) is able to change any of the ciphertex blocks before they are received by Bob. If Trudy knows P1, show that she can replace P1 with X.
Hint: Determine C’ so that if Trudy replaces C0 with C’, when Bob decrypts C1, he will obtain X instead of P1.
Solution:
Trudy (an attacker) replaces C0 with C~ = C0 ⊕ P1 ⊕ X.
4
10.[6] Suppose that Alice’s RSA public key is (N, e) = (33,3) and her private key is d = 7.
a.[3] If Bob encrypts the message M = 19 using Alice’s public key, what is the ciphertext C? Show that Alice can decrypt C to obtain M.
b.[3] Let S be the result when Alice digitally signs the message M = 25. What is S? If Bob receives M and S, explain the process Bob will use to verify the signature and show that in this particular case, the signature verification succeeds.
Solution:
a. To encrypt: 193 = 28 mod 33. To decrypt: 287 = 19 mod 33.
b. The signed result is S = Md mod N = 257 mod 33 = 31. To verify the signature,
Bob computes S3 mod N and the signature is verified if the result matches the received value M. In this case, 313 = 25 mod 33. Assuming Bob receives the sent message M = 25, the signature is verified.
Note that in practice, a hash function is usually used, so that the hash of the message is signed instead of message itself.
11.[11]Consider the RSA public key cryptosystem. The best generally known attack is to factor the modulus, and the best known factoring algorithm (for a sufficiently large modulus) is the number field sieve. In terms of bits, the work factor for the number field sieve is
f(n) = 1.9223n1/3(log2n)2/3,
where n is the number of bits in the number being factored. For example, since f(390)≈60, the work required to factor a 390-bit RSA modulus is roughly equivalent to the work needed for an exhaustive search to recover a 61-bit symmetric key.
a.[2] Calculate the function f(n) for n = 10, 100, 1000, 2000, 5000, 10000.
b.[3] A 1024-bit RSA modulus N provides roughly the same security as a symmetric key of
what length?
c.[3] A 2048-bit RSA modulus N provides roughly the same security as a symmetric key of
what length?
d.[3] What size of modulus N is required to have security roughly comparable to a 256-bit
symmetric key?
Solutions:
a. f(10) = 9.22, f(100) = 3153, f(1000) =89.02, f(2000) = 119.54, f(5000) = 175.04,
f(10000) = 232.34
b. Since about 88 bits of work are required, this is roughly equal to an exhaustive search for
an 89-bit symmetric key.
c. About 119 bits.
d. A modulus of about 13620 bits is required. 5
12.[6] Suppose that Alice and Bob share a 4-digit PIN number, X. To establish a shared symmetric key, Bob proposes the following protocol: Bob will generate a random key K that he will encrypt using the PIN number X, that is, E(K, X). Bob will send E(K, X) to Alice, who will decrypt it using the shared PIN number X to obtain K. Alice and Bob will then use the symmetric key K to protect their subsequent conversation. However, Trudy (an attacker) can easily determine K by a brute force attack on the PIN number X, so this protocol is insecure. Modify the protocol to make it more secure. Note that Alice and Bob only share the 4-digit PIN number X and they do not have access to any other symmetric key or public keys.
Hint: Use Diffie-Hellman.
Solution:
Use Diffie-Hellman and encrypt the exchange using the PIN X. That is, Alice computes and sends E(ga mod p, X) and Bob computes and sends E(gb mod p, X). Why is this more secure? To do the man-in-the-middle attack, Trudy must act in real time (i.e., while the exchange is taking place). When Trudy intercepts E(ga mod p, X), she can guess possible values for X, but she has no way to know whether her guess is correct. So, in effect, she gets one chance to guess X, so her chance of success is only 1/10000, while in the original protocol, her chance of success was 1. This is a big improvement in security for minimal additional work.
13.[9] Suppose that Bob’s knapsack private key consists of (3,5,10, 23) along with the multiplier m-1 mod n = 6 and modulus n = 47.
a.[3] Find the plaintext given the ciphertext C = 20. Give your answer in binary. b.[3] Find the plaintext given the ciphertext C = 29. Give your answer in binary. c.[3] Find m and the public key.
Solution:
a. First, compute m-1C = 6 ⋅ 20 = 120 = 26 mod 47. Using the superincreasing knapsack in
the private key, we find that the plaintext is 1001, in binary.
b. First, compute m-1C = 6 ⋅ 29 = 174 = 33 mod 47. Using the superincreasing knapsack in
the private key, we find that the plaintext is 0011.
c. Since m-1m = 6m = 1 mod 47, m = 8. Multiply each element in the superincreasing
knapsack by m and reduce mod 47 to obtain the “general” knapsack, (24; 40; 33; 43). It is easy to verify the encryptions that appear in parts a, and b.
6
14.[6] A digital signature or a MAC can be used to provide a cryptographic integrity check.
a.[3] Suppose that Alice and Bob want to use a cryptographic integrity check. Which would you recommend that they use, a MAC or a digital signature? Why?
b.[3] Suppose that Alice and Bob require a cryptographic integrity check and they also require non-repudiation. Which would you recommend that Alice and Bob use, a MAC or a digital signature? Why?
Solution:
a. There may be a slight efficiency advantage for the MAC (depending on the comparative
efficiency of the block cipher used for the MAC and the hash function public key method used for the signature). But, if public keys and symmetric keys are available, there is probably no major difference between the two. So the primary issue would simply be the type of keys available (symmetric or public/private).
b. In this case, they must use a signature, since a MAC does not provide nonrepudiation.
15.[5] The man-in-the-middle attack on Diffie-Hellman is illustrated on page 16 of LN4 (or Figure 4.2 in the textbook). Suppose that Trudy wants to establish a single Diffie- Hellman value, gabt mod p, that she, Alice, and Bob all share. Does the attack illustrated below succeed? Justify your answer.
Solution:
No. Trudy has no way to determine the secret value gabt mod p that Alice and Bob will share (short of solving a discrete log problem, that is).
7
16.[9] Suppose that h is a secure hash that generates an n-bit hash value.
a.[3] What is the expected number of hashes that must be computed to find one collision? b.[3] What is the expected number of hashes that must be computed to find 10 collisions? That is, what is the expected number of hashes that must be computed to find pairs (xi, zi) with
h(xi) = h(zi), for i = 0,1,2,…, 9?
c.[3] What is the expected number of hashes that must be computed to find m collisions?
Solution:
a. You need about 2n/2 hashes.
b. You will need about , since this number of hashes will result in about
10⋅2n comparisons, and for each 2n comparisons, we expect to find a collision.
c. We need hashes. Note that this implies that it gets progressively easier for find collisions as more hashes are computed. This is intuitive, since each new hash can be compared to all of the previous hashes.
17.[6] Let h be the Tiger hash and let F be the Tiger outer round (page 6 of LN6 or Figure 5.2 in the textbook).
a.[3] For M = (B1,B2,B2), where each Bi is 512 bits, give the analog the equation of equation h(M) = F(F(A,B1),B2)=F(h(B1),B2),
which is the equation (5.2) in the textbook or on a page devoted to HMAC in LN6. b.[3] Now suppose M = (B1, B2, … , Bn) where each Bi is 512 bits.
Show that h(M) = F(h(B1, B2, … , Bn-1), Bn)
Solutions:
a. We have
h(M) = F(F(F(A,B1),B2),B3) = F(F(h(B1),B2),B3) = F(h(B1,B2),B3),
b. The general case follows by a simple induction.
18.[5] Suppose that Alice wants to encrypt a message for Bob, where the message consists of three plaintext blocks, P0, P1, and P2. Alice and Bob have access to a hash function and a shared symmetric key K, but no cipher is available. How can Alice securely encrypt the message so that Bob can decrypt it?
Solution:
Alice could encrypt as C0 = P0 ⊕ K, C1 = P1 ⊕ h(K), and C2 = P2 ⊕ h(h(K)). This is not strong, since if Trudy knows Pi she can easily determine Pj for all j ≥ i.
8
19.[6] Suppose Bob and Alice want to flip a coin over a network. Alice proposes the following protocol.
(i) Alice randomly selects a value X ∈{0,1}.
(ii) Alice generates a 256-bit random symmetric key K.
(iii) Using the AES cipher, Alice computes Y = E(X,R,K), where R consists of 255
randomly selected bits.
(iv) Alice sends Y to Bob.
(v) Bob guesses a value Z ∈ {0,1} and tells Alice.
(vi) Alice gives the key K to Bob who computes (X, R) = D(Y, K).
(vii) If X = Z then Bob wins, otherwise Alice wins.
This protocol is insecure.
a.[3] Explain how Alice can cheat.
b.[3] Using a cryptographic hash function h, modify this protocol so that Alice can’t cheat.
Solution:
a. Once Alice knows Bob’s guess Z, she tries different “keys” K’ until she finds one
for which the first bit of W = D(Y,K0) is not Z. Then she sends the “key” K0 to Bob.
b. Alice sends h(K) along with Y , so she cannot change the key. That is, the hash of the key
commits Alice to K and since K is random, there is no forward search attack.
9