Scribd
Upload
16 views4 pages

Symmetric Cryptography Problem Set

The document outlines Problem Set 2 for the Applied Cryptography course at the American University of Beirut, focusing on symmetric cryptography topics. It includes instructions for submission, various problem sets covering pseudorandomness, chosen-plaintext and chosen-ciphertext attacks, collision-resistant hash functions, and password hashing. Additionally, it features case studies for block cipher modes and hash function security analysis, along with a bonus question on advanced attacks against AES.

Uploaded by

Phan Thanh Tấn
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views4 pages

Symmetric Cryptography Problem Set

The document outlines Problem Set 2 for the Applied Cryptography course at the American University of Beirut, focusing on symmetric cryptography topics. It includes instructions for submission, various problem sets covering pseudorandomness, chosen-plaintext and chosen-ciphertext attacks, collision-resistant hash functions, and password hashing. Additionally, it features case studies for block cipher modes and hash function security analysis, along with a bonus question on advanced attacks against AES.

Uploaded by

Phan Thanh Tấn
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Applied Cryptography American University of Beirut

Applied Cryptography
CMPS 297AD/396AI, Fall 2025

Lecturer: Nadim Kobeissi Website: [Link]

Problem Set 2: Symmetric Cryptography

Instructions: This problem set covers topics in provable security from topics 1.4a , 1.5b and 1.6c of the
course. Submit your solutions as a neatly formatted PDF. You are encouraged to collaborate with class-
mates in studying the material, but your submitted solutions must be your own work. For proofs,
clearly state your assumptions, steps, and conclusions.
a [Link]
b [Link]
c [Link]

1 Pseudorandomness
1. (10 points) Pseudorandom Generators
(a) (5 points) Explain the limitations of the one-time pad for practical encryption and why pseudoran-
dom generators (PRGs) are needed in modern cryptographic systems.
(b) (5 points) Analyze the security implications of the following PRG construction, where 𝐺 is a secure
PRG:

𝐻(𝑆) = 𝐴‖𝐵‖𝐶‖𝐷 where 𝐴‖𝐵 = 𝐺(𝑆) and 𝐶‖𝐷 = 𝐺(𝐵)

Determine whether 𝐻 is a secure PRG. If not, provide a distinguisher that can tell apart 𝐻(𝑆) from
a truly random string with non-negligible advantage.
2. (10 points) Pseudorandom Functions and Permutations
(a) (5 points) Consider the following PRF construction: 𝐹(𝐾, 𝑋) = 𝐺(𝐾) ⊕ 𝑋, where 𝐺 is a secure PRG.
Is 𝐹 a secure PRF? If not, describe a distinguisher that can effectively tell 𝐹 apart from a random
function.
(b) (5 points) Compare and contrast PRFs and PRPs:
i. Explain the key differences in their definitions and properties.
ii. Describe how PRPs can be “downgraded” to PRFs, but not necessarily vice versa.
iii. Explain why collisions are inevitable for PRFs but not for PRPs.

2 Chosen-Plaintext and Chosen-Ciphertext Attacks


1. (10 points) CPA Security
(a) (5 points) Consider the CPA security definition:

Σ
ℒcpa-real
Σ
ℒcpa-rand

𝐾 ↞ Σ.𝒦
≊ [Link](𝑀):
[Link](𝑀):
𝐶 ↞ Σ.𝒞(|𝑀|)
𝐶 ≔ Σ.Enc(𝐾, 𝑀)
return 𝐶
return 𝐶

CMPS 297AD/396AI, Fall 2025 Page 1 of 4


Applied Cryptography American University of Beirut

i. Explain why deterministic encryption schemes always fail CPA security.


ii. Construct a simple distinguisher program that can break the CPA security of any deterministic
encryption scheme.
iii. Analyze what practical security vulnerabilities exist in systems that use non-CPA-secure encryp-
tion.
(b) (5 points) For each of the following encryption schemes, determine whether it achieves CPA secu-
rity. If not, provide a specific attack:
i. Enc(𝐾, 𝑀) = (𝑅, 𝐹(𝐾, 𝑅) ⊕ 𝑀) where 𝑅 ↞ {0, 1}𝜆 and 𝐹 is a secure PRF.
ii. Enc(𝐾, 𝑀) = (𝑅, 𝐹(𝐾, 𝑀) ⊕ 𝑅) where 𝑅 ↞ {0, 1}𝜆 and 𝐹 is a secure PRF.
iii. AES in Electronic Codebook (ECB) mode.
iv. AES in Counter (CTR) mode with a randomly chosen IV.
2. (10 points) CCA Security and Authenticated Encryption
(a) (3 points) Format oracle attacks:
i. Explain how the null-oracle attack works against CTR mode encryption and why it’s devastating
despite CTR mode being CPA-secure.
ii. Describe a real-world scenario where a format oracle might be inadvertently exposed in a cryp-
tographic system.
iii. Calculate the approximate number of oracle queries needed to recover a 1 KB file using the
null-oracle attack, and explain why this is practical for an attacker.
(b) (4 points) For the following encryption scheme constructions, determine whether each provides
CCA security and/or authenticated encryption (AE). Justify your answers with brief explanations:
i. Encrypt-then-MAC: 𝐶 = Enc(𝐾𝑒 , 𝑀), 𝑇 = MAC(𝐾𝑚 , 𝐶), output (𝐶, 𝑇)
ii. Encrypt-and-MAC: 𝐶 = Enc(𝐾𝑒 , 𝑀), 𝑇 = MAC(𝐾𝑚 , 𝑀), output (𝐶, 𝑇)
iii. MAC-then-encrypt: 𝑇 = MAC(𝐾𝑚 , 𝑀), 𝐶 = Enc(𝐾𝑒 , 𝑀‖𝑇), output 𝐶
iv. Explain a scenario where replay attacks could succeed even against a system using authenti-
cated encryption, and how associated data (AD) addresses this vulnerability.
(c) (3 points) AES-GCM (Galois/Counter Mode):
i. Explain how AES-GCM combines CTR mode encryption with Galois field multiplication for au-
thentication. What security advantages does this provide over using separate encryption and
MAC algorithms?
ii. Describe the critical security implications of nonce reuse in AES-GCM. What specific vulnerabil-
ities arise when the same nonce is used for multiple messages?
iii. AES-GCM is sometimes implemented with different tag lengths. Analyze the security tradeoffs
when using 128-bit tags versus 64-bit or 32-bit tags.
iv. Aside from nonce reuse, what is an unexpected vulnerability in AES-GCM that developers and
engineers might not be aware of, but that might significantly impact the security of their soft-
ware?

3 Collision-Resistant Hash Functions


1. (15 points) Hash Function Properties
(a) (5 points) Collision resistance:
i. Explain why collisions must exist in any hash function that maps arbitrary-length inputs to
fixed-length outputs.
ii. Using the birthday paradox, calculate approximately how many hashes must be computed to
find a collision with 50% probability in a 256-bit secure hash function.
iii. Describe a practical attack scenario where finding hash collisions would compromise a security
system.
(b) (5 points) Hash function construction:
i. Compare and contrast the Merkle-Damgård construction (used in SHA-2) and the Sponge con-
struction (used in SHA-3).

CMPS 297AD/396AI, Fall 2025 Page 2 of 4


Applied Cryptography American University of Beirut

ii. Explain how length extension attacks work against Merkle-Damgård hash functions and why
the Sponge construction is resistant to these attacks.
iii. Describe the HMAC construction and explain how it protects against length extension attacks.
(c) (5 points) Hash function evolution:
i. Describe the successful attacks against MD5 and SHA-1 that led to their deprecation.
ii. Explain the concept of chosen-prefix collisions and why they are particularly dangerous for cer-
tificate authorities.
iii. Compare the security of SHA-2 and SHA-3 against known cryptanalytic techniques.

2. (15 points) Password Hashing


(a) (5 points) For each of the following password storage approaches, analyze the security implications
if a server database is compromised:
i. Storing passwords in plaintext.
ii. Encrypting passwords with a key stored on the same server.
iii. Storing unsalted SHA-256 hashes of passwords.
iv. Storing salted SHA-256 hashes of passwords.
v. Using a specialized password hashing function like Scrypt.
(b) (5 points) Salting:
i. Explain how salt protects against precomputation attacks like rainbow tables.
ii. Calculate the storage requirements for properly salted password hashes, assuming 10,000 users,
16-byte salts, and 32-byte hash outputs.
iii. Describe best practices for generating and storing salts.
(c) (5 points) Specialized password hashing functions:
i. Explain why memory-hard functions like Scrypt provide better protection against specialized
hardware attacks compared to PBKDF2.
ii. Describe how each of Scrypt’s parameters (N, r, p) affect its security and performance.
iii. Compare the relative speeds of SHA-256, PBKDF2, and Scrypt for password hashing, and explain
the security implications of these speed differences.

4 Applied Cryptography Case Studies


1. (10 points) Block Cipher Modes Analysis
With reference to the block cipher modes covered in our lectures, analyze the following scenarios:
(a) A secure file storage application needs to encrypt user files at rest. Compare CBC, CTR, and AES-GCM
modes for this application, discussing:
• Performance implications for large files.
• Error propagation if parts of the ciphertext are corrupted.
• The security implications of IV/nonce reuse.
• Data integrity guarantees and the advantages of authenticated encryption with AES-GCM.
(b) A real-time messaging application needs to encrypt short messages with minimal latency. Compare
CBC, CTR, and AES-GCM modes for this application, discussing:
• Parallelizability for encryption/decryption.
• Suitability for streaming data.
• Protection against chosen-ciphertext attacks.
• How AES-GCM addresses authentication needs compared to unauthenticated modes.
(c) For AES-GCM specifically:
• Explain the security impact of nonce reuse in AES-GCM compared to nonce reuse in CTR mode.
• Discuss the performance tradeoffs of AES-GCM compared to using separate encryption (CTR
mode) and authentication (HMAC).
• Explain how AES-GCM’s authenticated encryption properties protect against attacks that would
succeed against CBC or CTR modes.

CMPS 297AD/396AI, Fall 2025 Page 3 of 4


Applied Cryptography American University of Beirut

2. (10 points) Hash Function Security Analysis


A software update system uses hash functions to verify the integrity of downloads. The system works
as follows:

• The software vendor posts SHA-1 hashes of legitimate update files on their HTTPS website.
• Users download the update file over HTTP (not HTTPS) for bandwidth efficiency.
• The update client verifies the downloaded file by computing its SHA-1 hash and comparing it to the
hash obtained from the HTTPS website.
• If the hashes match, the update is installed automatically.
Analyze this system:
(a) Identify at least three security vulnerabilities in this design.
(b) For each vulnerability, describe a specific attack scenario.
(c) Propose improvements to address each vulnerability while maintaining performance and usability.
(d) Design a more secure alternative system using modern cryptographic primitives discussed in class.

3. (10 points) Password Management System Design


You are designing a password management system for a new web application with the following require-
ments:

• Users must be able to securely recover their account if they forget their password.
• The system must be resistant to offline dictionary attacks if the database is compromised.
• The system must support high-performance authentication for a large user base.
• The system should detect and prevent credential stuffing attacks.
Design and analyze a complete solution:
(a) Specify which cryptographic primitives you would use for password storage and why.
(b) Describe your password recovery mechanism and analyze its security properties.
(c) Explain how your system balances security and performance requirements.
(d) Analyze potential vulnerabilities in your design and how they are mitigated.

Bonus Question
1. (10 points (bonus)) The security of AES and other block ciphers depends on their resistance to
various forms of cryptanalysis. Research and analyze one of the following advanced attacks:
(a) Side-channel attacks: Explain how timing attacks, power analysis, or cache attacks can leak
information about encryption keys in practical implementations of AES.
(b) Related-key attacks: Describe how related-key attacks work against block ciphers and why
they are significant even when normal usage involves only unrelated keys.
(c) Quantum attacks: Analyze the impact of Grover’s algorithm on the security of AES with dif-
ferent key sizes (128, 192, 256 bits) and discuss appropriate post-quantum key length recom-
mendations.
Your answer should include: a description of the attack, its practical feasibility, relevant examples
of successful implementations against real systems, and appropriate countermeasures.

CMPS 297AD/396AI, Fall 2025 Page 4 of 4

Common questions

Powered by AI

Using SHA-1 over HTTP for software updates has vulnerabilities such as susceptibility to man-in-the-middle attacks where an attacker can intercept and alter updates, hash collisions due to SHA-1's vulnerabilities, and potential hash manipulation since the integrity check relies on insecure transmission channels. Mitigation involves using HTTPS for all transmissions to prevent eavesdropping, deploying hash functions with better collision resistance like SHA-256, and implementing digital signatures to ensure authenticity beyond hash comparisons .

The one-time pad has limitations mainly due to the impracticality of key distribution and key management since it requires a truly random, unique key of the same length as the message for every instance of encryption. This makes it difficult to implement for large volumes of data or frequent communications. Pseudorandom generators (PRGs) are necessary as they allow the generation of cryptographic keys from a small, secure seed, making it feasible to produce long keys necessary for encryption without needing to manually manage long truly random keys .

PRFs differ from PRPs in that PRFs lack the property of invertibility; PRPs are bijections on their input space, meaning every output maps to one unique input, guaranteeing no collisions. PRFs can have collisions because they are mappings from a possibly larger input to a smaller output space, inevitably leading to some inputs mapping to the same output due to the pigeonhole principle .

A format oracle attack against CTR mode encryption involves an adversary using side information to deduce plaintext properties based on ciphertext formats returned from encryption queries. Although CTR mode is CPA-secure, an oracle that leaks information about ciphertext content can allow attackers to format queries such that they gradually deduce the structure or precise content of plaintext, based on their control of the ciphertext's relationship to formats .

Nonce reuse in AES-GCM compromises security by allowing attackers to exploit predictable input-output relationships due to CTR mode derivations, leaking plaintext relationships via ciphertext differences. Reused nonces lead to identical streams, permitting successful plaintext recovery through crafted ciphertexts. Known attacks, like altering ciphertexts based on these repeats, become feasible since predictable structures turn data leakage into predictable operations accessible via message integrity compromise .

Storing unsalted SHA-256 hashes is insecure because the absence of salt exposes the system to rainbow table and precomputation attacks, where attackers can rapidly identify passwords against precomputed hash tables. In contrast, using Scrypt, a memory-hard function, enhances security by making it computationally intensive and memory-demanding to generate hash tables, thwarting rapid or parallel hash generation attempts, thus providing resilience against brute force attacks on hashed passwords .

Using a 128-bit tag in AES-GCM offers better security due to a larger tag space, reducing collision and forgery probability by increasing distinct verification instances before collisions are likely. However, implementing a 32-bit tag may increase vulnerability, sacrificing integrity assurance and making manufacture feasible forgery attempts often due to shorter tag lengths. This trade-off balances bandwidth or storage needs against desired security strength. For high-security applications, larger tags are recommended to thwart potential attacks despite increased computational effort .

The PRG construction H(S) is not secure. A distinguisher can exploit that both segments C||D and A||B are generated from related seeds (S and B respectively), compromising independence. Since B is part of the initial PRG output, the second generator input is predictable, allowing an adversary to distinguish H(S) from true randomness by detecting patterns or structures not present in a truly random sequence .

The Merkle-Damgård construction, used in SHA-2, is vulnerable to length extension attacks because attackers can append data to known hashes and calculate new hashes without knowing the original data, compromising data integrity where hash verification is the sole method. In contrast, Sponge constructions, like in SHA-3, resist such attacks through internal state memory that absorbs all incoming data before finalizing output, preventing modification-oriented attacks by ensuring input transformations nullify appending exploits, allowing no easy new hash derivations .

Deterministic encryption schemes fail to achieve CPA security because they encrypt the same plaintext identically every time, allowing adversaries to learn information by observing repeated ciphertexts. A distinguisher could simply encrypt a plaintext and check if it gets the same ciphertext again in another instance, thus being able to distinguish between different messages or ciphertext states. For example, an adversary could submit a known message to be encrypted and determine iteration potential by observing deterministic outcomes .

You might also like