Font size
WorksheetsCryptography
Total questions: 80
Worksheet time: 41mins
Consider the Vigenere cipher over the lowercase English alphabet, where the key length can be anything from 8 to 12 characters. What is the size of the key space for this scheme?
4 * 26^12
26!
26^12
26^8 + 26^9 + 26^10 + 26^11 + 26^12
Consider the Vigenere cipher over the lowercase English alphabet, where the key has length 8. For which of the following message spaces will this scheme be perfectly secret? (Check all that apply.)
The set of all 8-character strings of lowercase English letters.
The set of all 9-character strings of lowercase English letters.
The set of all strings of lowercase English letters containing at most 8 characters.
The set of all 7-character strings of lowercase English letters.
What is the result of encrypting the ASCII plaintext 'cool!' using the variant Vigenere cipher (where encryption is done using byte-wise XOR) and key 0x01 3F?
0x26 05 E6 35 02
0x63 6F 6F 6C 21
0x62 50 6F 6C 21
0x62 50 6E 53 20
Say we have a scheme with a claimed proof of security with respect to some definition, based on some assumption. The scheme was successfully attacked when used in the real world. What are possible reasons for this? (Check all that apply.)
The proof might be incorrect.
The definition of security may not correctly capture the real-world threat model.
The assumption may be false.
The attacker did not read the proof of security.
In the definition of perfect secrecy, what threat model is assumed?
The attacker can eavesdrop on a single ciphertext.
The attacker is able to interfere with the communication channel between the two honest parties.
The attacker can eavesdrop on as many ciphertexts as it likes.
The attacker can carry out a chosen-plaintext attack.
Consider the Vigenere cipher over the lowercase English alphabet, where the key can have length 1 or length 2, each with 50% probability. Say the distribution over plaintexts is Pr[M='aa'] = 0.4 and Pr[M='ab'] = 0.6. What is Pr[C='bb']? Express your answer to 4 decimal places with a leading 0, i.e., if your answer was 1/2 then you would enter 0.5000 (without a trailing period).
0.01
0.0001
0.0084
0.0072
Consider the Vigenere cipher over the lowercase English alphabet, where the key can have length 1 or length 2, each with 50% probability. Say the distribution over plaintexts is Pr[M='aa'] = 0.4 and Pr[M='ab'] = 0.6. What is Pr[M='aa' | C='bb']? Express your answer to 4 decimal places with a leading 0, i.e., if your answer was 1/2 then you would enter 0.5000 (without a trailing period). Note: carry out the calculation exactly (i.e., do not use the truncated result that you entered as your answer in the previous question) before truncating your answer to 4 decimal places.
0.9473
0.1
0.0024
0.4839
Which of the following are true for obtaining perfect secrecy using the one-time pad, assuming the message space contains messages all of some fixed length? (Check all that apply.)
The all-0 key must be avoided, since when the all-0 key is used the ciphertext is equal to the message being encrypted.
The key should be shared between the two communicating parties, and kept secret from any potential attacker.
The key must be as least as long as the messages in the message space.
The key should be chosen uniformly.
Consider the one-time pad over the message space of 5-bit strings, where Pr[M=00100] = 0.1 and Pr[M=11011] = 0.9. What is Pr[C=00000]? Express your answer to 5 decimal places with a leading 0. I.e., if your answer was 1/2, then you would enter 0.50000 (without a trailing period).
0.0107
0.03125
0.93481
0.83459
Which of the following are true about the Vigenere cipher? (Check all that apply.)
The Vigenere cipher is computationally infeasible to break if the key has length 100, even if 1000s of characters of plaintext are encrypted.
The Vigenere cipher is perfectly secret if the length of the key is equal to the length of the messages in the message space.
The Vigenere cipher can always be broken, regardless of the length of the key and regardless of the length of plaintext being encrypted.
A Vigenere cipher with key of length 100 can be broken (in a reasonable amount of time) using exhaustive search of the key space.
Two ASCII messages containing English letters and spaces only are encrypted using the one-time pad and the same key. The 10th byte of the first ciphertext is observed to be 0xB7 and the 10th byte of the second ciphertext is observed to be 0xE7. Let m1 (resp., m2) denote the 10th ASCII character in the first (resp., second) message. What is the most you can conclude about m1 and m2?
Nothing can be determined about m1 or m2 since the one-time pad is perfectly secret.
m1 is the character 'p' and m2 is the space character.
m1 is the space character and m2 is the character 'p'.
One of m1 or m2 is the space character, and the other is the character 'p'.
m1 is the character 'B' and m2 is the character 'E'.
Three ASCII messages containing English letters and spaces only are encrypted using the one-time pad and the same key. The 10th byte of the first ciphertext is observed to be 0x66, the 10th byte of the second ciphertext is observed to be 0x32, and the 10th byte of the third ciphertext is observed to be 0x23. Let m1 (resp., m2, m3) denote the 10th ASCII character in the first (resp., second, third) message. What is the most you can conclude about m1, m2, and m3?
Exactly one of m1, m2, or m3 is the space character, but nothing else can be determined.
m1 is the character 't', m2 is the space character, and m3 is the character 's'.
m1 is the space character, m2 is the character 't', and m3 is the character 'e'.
Nothing can be determined about m1, m2, or m3 since the one-time pad is perfectly secret.
Which of the following is true about computational secrecy? (Select all that apply.)
Computational secrecy only ensures secrecy against attackers running in some bounded amount of time.
Computational secrecy means that it is trivial for an attacker to always learn the entire message.
Computational secrecy allows an attacker to learn information about the message with small probability.
Computational secrecy currently relies on unproven assumptions.
Let G be a function mapping n-bit inputs to 2n-bit outputs. Which of the following is true of the pseudo one-time pad encryption scheme based on G? (Check all that apply.)
The scheme is perfectly secret.
The scheme is computationally secret if G is a pseudorandom generator.
The scheme can be used securely to encrypt multiple messages using the same key.
The key space of the scheme is at least as large as the message space.
Which of the following attackers can be used to demonstrate that the shift cipher for 3-character messages does not satisfy perfect indistinguishability?
Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output 1 if the three characters of C are all different.
Output m0 = 'aaa' and m1 = 'bbb'. Given challenge ciphertext C, output 0 if the first character of C is 'a'.
Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output 0 if the first character of C is 'a'.
Output m0 = 'abc' and m1 = 'bcd'. Given challenge ciphertext C, output 1 if the three characters of C are all different.
Which of the following is a negligible function? (Check all that apply.)
f(n) = n/2^n
f(n) = 1/n.
f(n) = 1/2^n
f(n) = 1/2
Define the following function G taking n-bit inputs and producing (n+1)-bit outputs: G(x)=x∥0, where ∥ denotes concatenation. Which of the following attackers shows that this G is not a pseudorandom function?
On input an (n+1)-bit string y, output 1 if the first bit of y is 0.
On input an (n+1)-bit string y, output 0 if the first bit of y is 0.
On input an (n+1)-bit string y, output 0 if the last bit of y is 0.
On input an (n+1)-bit string y, output 0 if the first bit of y is equal to the last bit of y.
Say G is a pseudorandom generator taking n-bit inputs and producing 2n-bit outputs. Which of the following are necessarily true? (Check all that apply. The symbol '|' is used here for string concatenation.)
G(r) | G(r+1) is computationally indistinguishable from a uniform, 4n-bit string if r is a uniform n-bit string.
G(0 | r) is computationally indistinguishable from a uniform, 2n-bit string if r is a uniform (n-1)-bit string.
r | G(r) is computationally indistinguishable from a uniform, 3n-bit string if r is a uniform n-bit string.
G(r) is computationally indistinguishable from a uniform, 2n-bit string if r is a uniform n-bit string.
Which of the following is a setting in which a pseudorandom generator could be applied?
You have a 1 MB file and you would like to make sure that it has not been tampered with.
You have a 1 MB file that you would like to compress.
You have a way to generate random bits at the rate of 100 bits/second, but you need 1,000,000 random bits to run a statistical simulation.
Consider a pseudo one-time pad encryption scheme Π constructed using some function G. Which of the following did our proof of security for the pseudo one-time pad show?
If G is a pseudorandom generator, then Π is computationally secret.
Π is always computationally secret, for any G.
If G is a pseudorandom generator, then Π is perfectly secret.
Π is always perfectly secret, for any G.
True or false: any private-key encryption scheme that is CPA-secure must also be computationally indistinguishable.
True
False
True or false: any private-key encryption scheme that is CCA-secure must also be perfectly secret.
True
False
True or false: any private-key encryption scheme that is CCA-secure must also be CPA-secure.
True
False
Let F be a block cipher with 128-bit block length. Consider the following encryption scheme for 256-bit messages: to encrypt message M=m1∥m2 using key k (where m1=m2=128), choose random 128-bit r and compute the ciphertext. Which of the following strategies would lead to a valid chosen-plaintext attack?
Choose random r and let m be arbitrary but not equal to r. Output messages Mo = r||m and M1 = m||m. Output 0 if the second block of the challenge ciphertext is all-0s.
Let m1 and m2 be arbitrary but distinct. Using the encryption oracle, obtain an encryption r||c1||c2 of m1||m2. Output messages M0 = m1||m2 and M1 = m2||m1. Output 0 if the third block of the challenge ciphertext is c2.
There is no attack; this scheme is randomized, so it is CPA-secure.
Let m1 and m2 be arbitrary but distinct. Using the encryption oracle, obtain an encryption r||c1||c2 of m2 || m2. Output messages M0 = m1||m1 and M1 = m1||m2. Output 0 if the third block of the challenge ciphertext is c2.
Let F be a pseudorandom function with 128-bit key and 256-bit block length. Which of the following functions G are necessarily pseudorandom generators? (Select all that apply.)
G(x) = F.(0...0)|F.(1...1), where x is a 128-bit input.
G(x) = F,(0...0)| F,(0...0), where x is a 128-bit input.
G(x) = F.(0...0), where x is a 128-bit input.
G(x) = F0...0(x)| F1...1(x), where x is a 256-bit input
Define the keyed function F as follows: Fk(x) = f O x. Which of the following distinguishers demonstrates that F is not a pseudorandom function?
Given access to an oracle g, query y = g(0... 0). Then output 1 if and only if the first bit of y is equal to 1.
Given access to an oracle g, query g(0 ... 0). Then output 1 because we now have the key.
Given access to an oracle g, query y = g(0...0) and y' = g(0...0). Then output 1 if and only if y = у'.
Given access to an oracle g, query y0 = g(0...0) and y1 = g(1... 1). Then output 1 if and only if Y0 ⊕ У1 = 1... 1.
Let F be a block cipher with n-bit block length. Consider the following encryption scheme: to encrypt a message viewed as a sequence of n-bit blocks m1,m2,...,mt using a key k, choose a random n-bit value r and then output the ciphertext r,Fk(r+1+m1),Fk(r+2+m2),...,Fk(r+t+mt), where addition is done modulo 2n. Which of the following attackers demonstrates that this scheme is not computationally indistinguishable:
Choose random n-bit blocks m and m', and output Mo = m, m and M1 = m, m'. Given challenge ciphertext r, C1, C2, output 1 if and only if c1 = C2.
Let m be an arbitrary n-bit block, and output Mo = m, m and M1 = m, m - 1. Given challenge ciphertext r, C1, C2, output 1 if and only if c1 = C2.
Let m be an arbitrary n-bit block, and output Mo = m and M1 = m, m. Given a challenge ciphertext, output 0 if the challenge ciphertext contains 2 blocks, and output 1 otherwise.
Choose random n-bit blocks m1, m2, m3, m4, and output Mo = m1, m2 and M1 = m3, m4. Given challenge ciphertext r, C1, C2, output 0 if r = 0.0, and output 1 otherwise.
Say we use CBC-mode encryption based on a block cipher with 256-bit key length and 128-bit block length to encrypt a 512-bit message. How long is the resulting ciphertext?
768 bits
Not enough information to determine.
512 bits
640 bits
Assume an honest user wants to send an 8-bit integer to their bank indicating how much money should be transferred to the bank account of an attacker. The user uses CTR-mode encryption based on a block cipher F with 8-bit block length. (Yes, this is a made-up example.) The attacker knows that the amount of money the user wants to transfer is exactly $16, and has compromised a router between the user and the back. The attacker receives the ciphertext 10111100 01100001 (in binary) from the user. What ciphertext should the attacker forward to the bank to initiate a transfer of exactly $32?
10111100 01010001
10111100 00100000
01100001 10111100
10001100 01100001
Assume CTR-mode encryption with PKCS #5 padding and a block cipher with 8-byte block length. Say a 4-byte message is encrypted, resulting in ciphertext 0x00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07. Which of the following ciphertexts will NOT yield an error upon decryption?
0x00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 F7
0x00 01 02 03 04 05 06 07 00 01 02 03 04 05 07 07
0x00 01 02 03 04 05 06 07 00 01 02 03 05 05 06 07
0x00 01 02 03 04 05 06 07 00 01 02 04 04 05 07 07
True or false: CBC-mode encryption with PKCS #5 padding provides message integrity, as long as the receiver makes sure to verify the padding upon decryption.
True
False
Let F be a block cipher with n-bit block length. Consider the message authentication code for 2n-bit messages defined by Mack(m1,m2)=Fk(m1⊕m2). Which of the following gives a valid attack on this scheme?
Obtain tag t on message m, 0 ... 0 (with m≠0...0), and then output the tag t on the message 0...0,0...0.
Obtain tag t on message m1,m2 (with m1≠m2), and then output the tag t on the message m2,m1.
Obtain tag t on message m,m, and then output the tag 0...0 on the message 0...0,m.
Obtain tag t on message m,0...,0, and then output the tag t⊕(1...1) on the message m,1...1.
Let F be a block cipher with n-bit block length. Consider the message authentication code for 2n-bit messages defined by Mack(m1,m2)=Fk(m1)⊕Fk(m2). Which of the following gives a valid attack on this scheme?
There is no attack; the scheme is secure.
Output the tag 0...0 on the message 0...0,0...0.
Obtain tag t on the message 0...0,1...10...0,1...1, and output the tag t⊕(1...1) on the message 1...1,1...11... 1,1...1.
Obtain tag �t on the message 0...0,1...10...0,1...1, and output the tag t⊕(1...1) on the message 1...1,0... 01...1,0...0.
Assume a sender and receiver use basic CBC-MAC but authenticate/accept messages of different lengths. Which of the following is a valid attack?
Obtain tag t1 on message m1, and tag t2 on message m1,m2. Then output the tag t1 on the message t2⊕m2.
Obtain tag t1 on message m1, and tag t2 on message m2,m1. Then output the tag t2 on the message m1,m2.
Obtain tag t1 on message m1, and tag t2 on message m1,m2. Then output the tag t2 on the message t1⊕m2.
Obtain tag t1 on message m1, and tag t2 on message t1,m2. Then output the tag t2 on the message m1⊕m2.
Assume we want to use a hash function with output length as small as possible, subject to being collision resistant against a birthday attack running in time 2^192. Which hash function would be the best choice?
MD5.
SHA-1.
SHA-2, with output truncated to 192 bits.
SHA-3 with 384-bit output.
Let H,H′ be collision-resistant hash functions. Which of the following functions H′′ is NOT necessarily collision-resistant?
H′′(x)=H(x)⊕H′(x).
H′′(x)=H(x)∥H′(x), where ∥∥ denotes concatenation.
H′′(x)=H(H′(x)).
H′′(x)=H(x)∥0...0, where ∥∥ denotes concatenation.
Assume a sender and receiver use the encrypt-and-authenticate approach for variable-length messages, using CTR-mode encryption and a variant of CBC-MAC secure for authenticating variable-length data (and independent keys for each). Which of the following statements is true?
The combination is not CPA-secure, but it does provide integrity.
The combination is CPA-secure, but it does not provide integrity.
The combination is not CPA-secure, and it does not provide integrity because the CTR-mode encryption allows the attacker to forge a tag in the CBC-MAC.
The combination is not CPA-secure, and it does not provide integrity because CTR-mode encryption is malleable.
Let F be a block cipher with block length n. Consider the following encryption scheme for n-bit messages: to encrypt message m using key k, choose a random c0∈{0,1}^n and output the ciphertext c0,c1,Fk(Fk (c0)⊕c1), where c1=Fk(c0)⊕m. Which of the following statements is true?
This can be viewed as an example of the encrypt-and-authenticate approach using CBC-mode and CBC- MAC (with the same key), and is insecure.
This looks like the authenticate-then-encrypt approach using CBC-MAC and CBC-mode encryption (with the same key) -- but here it's ok, since CBC-MAC is applied to something random.
This looks like the encrypt-then-authenticate approach using CTR-mode and CBC-MAC, except that here
the same key is being used for both -- Prof. Katz warned us about that; this looks insecure!
This is an example of the encrypt-then-authenticate approach using CTR-mode and CBC-MAC, so is secure.
Which of the following is the most appropriate primitive for achieving message integrity between two users sharing a key?
Collision-resistant hash function.
Message authentication code.
Block cipher.
Private-key encryption scheme.
Which of the following is an example of a message authentication code used widely in practice?
HMAC.
CBC-mode encryption.
SHA-1.
AES.
Consider the following algorithm for factoring an integer N provided as input (in binary): For i=2to⌈N−
−√⌉, if I divides N, then output(i,N/i). Which of the following statements is true?
This algorithm is correct, but it runs in exponential time.
This algorithm is not correct, because it will sometimes fail to find a factorization of N even if N is composite.
This algorithm runs in sub-linear time, and always factors N if N is composite.
This algorithm is not correct, because it will sometimes output a non-trivial factorization of N even when N is prime.
Which of the following is NOT a group?
The integers under addition.
The set {0,1,2,...,27} under addition modulo 28.
The integers under multiplication.
The set {1,3,7,9} under multiplication modulo 10.
Which of the following is the multiplicative inverse of 10 modulo 15?
10
1
There is none, since gcd(10,15) !=1.
5
What is [5^80 mod79]? (Note that 79 is prime. Don't use a calculator/computer!)
25
15
100
20
How many elements are in the group Z*403? (Note that 403=13⋅31.)
402
403
360
290
Which of the following gives the 3rd root of 92 modulo 187? (Note that 187=11⋅17.)
[92^107 mod 187]
[92^3mod187]
[92^107mod160]
[92^160mod187]
Which of the following problems is hard if the RSA assumption holds? In all the below, N is a product of distinct, large primes p and q, and e is relatively prime to φ(N).
Given N and e, find x such that x^e=8modN.
Given N,e, and a uniform value x∈ZN∗, find y such that x^e=ymodN.
Given N and e, find x,y such that x^e=ymodN.
Given N, e, and a uniform value y∈ZN∗, find x such that x^e=ymodN.
Which of the following is a generator of Z13∗?
3
4
Z13∗ does not have a generator since it is not a cyclic group.
2
Z23∗ is a cyclic group with generator 5. In this group, what is DH5(2,20)?
22
17
9
5
Let G be a cyclic group of order q and with generator g. Based only on the assumption that the discrete- logarithm problem is hard for this group, which of the following problems is hard?
Find x,y such that gx=y.
Given uniform x∈Zq and uniform y∈G, compute yx⋅g.
Given a uniform y∈G, find x such that gx=y.
Given a uniform x∈Zq, find y such that gx=y.
Which of the following is a drawback of the private-key setting that is NOT addressed by the public-key setting?
The communicating parties need to have some prior relationship.
The communicating parties need to share some secret information in advance.
Users must manage and securely store keys for every other party with whom they wish to communicate securely.
The communicating parties need the ability to generate random bits.
Which of the following BEST describes the security offered by the Diffie-Hellman key-exchange protocol (assuming the DDH problem is hard)?
An attacker eavesdropping on an execution of the protocol cannot distinguish the key shared by the
parties from a uniform key.
An attacker eavesdropping on an execution of the protocol cannot compute the key shared by the parties.
An attacker eavesdropping on an execution of the protocol does not know whether the parties have shared a key or not.
An attacker is unable to impersonate either party taking part in the protocol.
Assume the Diffie-Hellman protocol is run by two parties in the subgroup of Z23∗ generated by 2. (This subgroup has order 11.) If the first party chooses private exponent 3 and the second chooses private exponent 10, which of the following characterizes the execution of the protocol in this case?
The first party sends 8, the second party sends 12, and they share the key 3.
The first party sends 8, the second party sends 1, and they share the key 1.
The first party sends 3, the second party sends 10, and they share the key 11.
The first party sends 8, the second party sends 12, and they share the key 20.
In which of the following scenarios is public-key encryption a better choice than private-key encryption?
A user wants to send his credit-card number to a merchant on the web.
A general wants to communicate securely with a lieutenant.
A user wants to encrypt the contents of her hard drive.
Two police officers want to set up their communication devices to communicate securely before heading out to an operation.
Which of the following would NOT be a secure way for a receiver to distribute her key for a public-key encryption scheme? (Assume a passive, eavesdropping attacker here.)
Email the public key to the other party upon request.
Post the public key on one's webpage.
Post the private key on one's webpage.
Put the public key into a public directory.
Which of the following is true in the public-key setting, but NOT true in the private-key setting?
(Under standard assumptions) there exist schemes that are CPA-secure, but are not CCA-secure.
It is possible to achieve perfect secrecy.
Allowing the attacker to have access to an encryption oracle makes no difference when defining security.
A deterministic encryption scheme cannot be CPA-secure.
Assume for the purposes of this question a public-key encryption scheme for which the time to encrypt a 128-bit message is 100 times slower than the time to compute one AES evaluation. Which of the following is true if we want to encrypt a 100MB message M?
Public-key encryption of M using the given scheme is going to be only about 10 times slower than private-key encryption of M, because for secure private-key encryption AES would have to be used in a chaining mode of operation.
Public-key encryption of M is not possible with the given scheme, since the scheme only supports 128- bit messages.
If hybrid encryption is used, then public-key encryption of M will take roughly the same time as private-
key encryption of M.
Public-key encryption of M using the given scheme is inherently going to be 100 times slower than private-key encryption of M.
Assume El Gamal encryption, where the group being used is Z47∗ with generator 5. (This group has order 46, which is not prime. But El Gamal encryption can be defined in any cyclic group.) Assume the public key contains h=10. Say an attacker sees a ciphertext (41, 18) that is the encryption of some unknown message m. Which of the following is an encryption of [5m mod47]?
(17, 18)
(41, 43)
(1, 5)
(41, 5)
Assume "plain RSA" encryption is used with public key (N=33,e=3). What is the encryption of the message m=2?
2
7
32
8
Which of the following is true about "plain RSA" encryption (assuming the RSA problem is hard)?
If the message m is uniform in ZN∗, then m cannot be recovered in its entirety from the ciphertext in polynomial time.
If the message m is a uniform, 128-bit string then m cannot be recovered in its entirety from the
ciphertext in polynomial time. (Here, assume N is at least 1000 bits long, and e=3.)
The scheme is CPA-secure, but not CCA-secure.
If the message m is uniform in Zn∗, then no information about m can be recovered from the ciphertext in polynomial time.
The Federal Government wants to be able to issue advisories to the general public while ensuring that no one will be able to tamper with their messages or spoof a fake advisory. Which of the following is the best cryptographic approach to address this problem?
Use a digital signature scheme, with the public key known to everyone, to sign each advisory when it is
released.
Use a message authentication code, with the key known to everyone, to generate a tag for each advisory when it is released.
Use a public-key encryption scheme, with the public key known to everyone, and decrypt each advisory when it is released.
Use multiple message authentication codes, with each member of the public being given a unique key, and generate one tag per key each time an advisory is released.
The president and vice president of a company want to communicate while ensuring integrity of their communication. Which of the following is the best cryptographic approach to address this problem?
Use a message authentication code, with the key shared between them, and generate a tag for each
message they send.
Use a CPA-secure private-key encryption scheme, with the key shared between them, and encrypt each message they send.
Use a digital signature scheme, with the public key known to everyone, and sign each message they send.
Use a message authentication code, with the key made public, and generate a tag for each message they send.
Assume for the purposes of this question a digital signature scheme for which the time to sign a 256-bit message is 100 times slower than the time to evaluate SHA-256 on a 512-bit input. Which of the following is true if we want to sign a 500MB message M?
If the hash-and-sign approach is used, then signing M will take roughly the same time as hashing M.
Signing M using the given scheme is not possible, since it only supports 256-bit messages.
We can securely sign M by breaking it into 256-bit chunks, and signing each chunk.
We can sign M by simply hashing it, and avoid using the digital signature scheme altogether.
Assume the "plain" RSA signature scheme, with public key (N=55,e=3). Which of the following verifies correctly as the signature on the message m=17?
43
4
7
8
Assume the "plain" RSA signature scheme with public key (N,e=3). For which of the following messages is it always possible to forge a signature without seeing any prior signatures or factoring N? (Assume N>1000, and N relatively prime to each of the messages that follow.)
27
37
47
2
Assume the "plain" RSA signature scheme with public key (N,e). Say we want to forge a signature on m=289 but can only obtain a signature on one other message. Which of the following strategies will work? (Assume N>1000.)
Obtain signature σ on m′=288. Output [σ+1modN] as the signature on m.
Obtain signature σ on m′=578. Output [2^-1*σmodN] as the signature on m.
Obtain signature σ on m′=17. Output [σ^2modN] as the signature on m.
Obtain signature σ on m′=288. Output [σ-1modN] as the signature on m.
In this and the next question, assume the Schnorr identification protocol is run in the subgroup of Z23∗ generated by 2. (This subgroup has order 11.) Say the prover's private key is x=7. What is the prover's public key?
7
3
14
13
(This is a continuation of the previous question.) Say the prover runs an execution of the Schnorr identification protocol with a verifier. The prover chooses r=4 and sends A=16. The verifier sends challenge 3. What response does the prover send?
13
3
4
7
As in the lectures, let cert A→B denote a certificate issued by A for B, i.e., certA→B=Sign skA(B,pkB). Assuming D knows pkC and trusts C, which of the following provides evidence to D that A's public key is pkA?
certA→B, pkA, certB→C and pkB
certC→B, pkB, certB→A and pkA
certC→B, pkB, certA→B and pkA
certA→C and pkA
Consider the SSL/TLS handshake protocol as described on slide 5 of the SSL/TLS lecture. Say the encryption of pmk were changed from using a CCA-secure public-key encryption scheme to using a CPA- secure public-key encryption scheme. Which of the following attacks would this change potentially enable?
A passive eavesdropper can now learn Nc and Nb. In combination with other known information, this allows the attacker to recover mk.
An attacker can eavesdrop on an execution of the protocol to learn the ciphertext c. Then, it can
impersonate the client, send modified versions of c to the server, and learn pmk by using information
about whether the server returns an error or not in response to these ciphertexts.
An attacker can impersonate the server by sending its own public key pk∗ to the client. By doing so, it can convince the client to encrypt pmk again, but this time using a public key for which the attacker can decrypt.
A passive eavesdropper can now learn pmk. In combination with Nc and Nb, this allows the attacker to recover mk.
What was your favorite part of this class?
(a)
What is the most appropriate cryptographic primitive to use if a company wants to distribute authenticated software updates to its customers?
Digital signature scheme.
Public-key encryption scheme.
Pseudorandom function/block cipher.
Hash function.
Message authentication code.
What is the most appropriate cryptographic primitive to use if an individual wants to ensure confidentiality of the files stored on her hard drive?
Message authentication code.
Pseudorandom function/block cipher.
Hash function.
Public-key encryption.
Private-key encryption.
A user wants to design a CPA-secure public-key encryption scheme to be used for emailing large files. Of the following, which would be the best approach?
To encrypt a file M, use DSS to encrypt a random key, and then use that key to encrypt M using HMAC.
To encrypt a file M, hash the file to a short value h=H(M), and then encrypt h using El Gamal encryption.
To encrypt a file M, break it into a sequence of blocks M1, M2,.... Then encrypt each block independently using El Gamal encryption.
To encrypt a file, use El Gamal encryption to encrypt a random AES key; then use AES (with that key) in
CBC mode to encrypt the file.
Consider the following "hybrid" signature scheme, which will give better efficiency when signing long messages. To sign message M using private key sk, choose a uniform key k for a message authentication code and then send k,Signsk(k),Mack(M). Verification is done in the natural way. Which of the following is true regarding this scheme?
This is a secure signature scheme, if the underlying signature scheme and MAC are secure.
This is not secure because it is very likely that a key k will be used twice by the signer.
This is not secure because given k,Signsk(k),Mack(M) an attacker can forge k,Signsk(k),Mack(M′) on any M′ of its choice.
This is not secure because given the message/signature pair (k,Signsk(k)) an attacker can easily forge Signsk(k′) on a key k′ of its choice.
Let G be a group, and consider the following private-key encryption scheme with message space G: The shared key is a uniform element k∈G. To encrypt a message m∈G using key k, output the ciphertext k⋅m. To decrypt a ciphertext c∈G using key k, output the message k−1 ⋅c. Which of the following is true about this scheme?
The scheme is perfectly secret.
The scheme is CCA-secure.
The scheme is CPA-secure, but not CCA-secure.
The scheme is computationally indistinguishable, but not perfectly secret.
Consider hybrid encryption using plain RSA and AES-128 in CTR mode, with public key N,e. Say a 128-bit message m is encrypted, yielding ciphertext c,c0,c1, with c∈ZN*and c0, c1 ∈ {0,1}128. Which of the following would be an encryption of m, the bitwise complement of m?
[2e ⋅ cmodN],c0,c1
c, c-0, c1
c, c0, c-1
The given encryption scheme is CCA-secure (hence non-malleable), so it is infeasible to come up with an encryption of m.
Say El Gamal encryption is used in the subgroup of Z47∗ generated by 4. The public key is 21 and the private key is 4. The ciphertext (34,42) is an encryption of some message m. Which of the following is an encryption of [4mmod47]?
(34, 46)
(34, 27)
(42, 42)
(42, 27)
Consider the plain RSA encryption scheme with public key N=55,e=3. Say the encryption of some unknown message m is 6. What is the encryption of [2mmodN]?
3
12
48
31
Say you have "oracle access" to a piece of code that, given a message m, appends an unknown 8-byte password p, applies PKCS #7 padding, and then encrypts the result using AES-128 in ECB mode with an unknown key. Which of the following attacks can be used to confirm that the first byte of p is 'Z'?
Submit the null message and check whether the first byte of the ciphertext is equal to 'Z'.
Submit the 16-byte message "ZZZZZZZZZZZZZZZZ," and check whether the first byte of the first block of the resulting ciphertext is equal to the first byte of the second block of that ciphertext.
Submit the 1-byte message "Z," and check whether any two bytes in the resulting ciphertext are equal.
Submit the 15-byte message "ABCDEFGHIJKLMNO" and the 16-byte message "ABCDEFGHIJKLMNOZ,"
and check if the first blocks of the resulting ciphertexts are equal.
