Lab 2: Bad randomness
Instructions on how to submit Lab 2: Please download all the required files from the lab2 github repo.

Problem 0: Please complete the True/False questions in the lab2problem0 gradescope assignment.

Code: Place your code answers in the template
ecdsa/sol.py
for ecdsa questions andwep/attacker.py
. Please include all code necessary to generate your solution in each of the respective methods. Do not just hard code working answers! 
Text: Place your written answers in the template
questions.txt
Upload all files (sol.py
, attacker.py
, questions.txt
) to the lab2 gradescope assignment.
Running the Lab on Windows
make check
and make venv
do not natively work on Windows.
If you are using a windows machine, please see the Windows Instructions.
Gradescope autograder: Your code will be graded with the Gradescope autograder with a total timeout of 40 minutes.
There is a STRICT 6.0GB memory limit on Gradescope. Reasonable solutions to this lab should not come close to approaching this memory limit.
Plagiarism: Gradescope automatically runs a surprisingly effective plagiarismdetection tool on your submissions. Please do not copy code from your fellow students. Refer to the “Collaboration” section of the course info document for details on what types of collaboration are and aren’t allowed in 6.1600. If you are having trouble completing an assignment for whatever reason, please ask the course staff for help. We are often happy to give help and, in many cases, extensions too! We are not happy when we find copied code.
Problem 0: True/False
Please complete the True/False questions in the lab2problem0 gradescope assignment.
For these problems, let \(F \colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n\) be a pseudorandom function. Let \(n \approx 256\) be the security parameter.

The function \(F'(k) := F(k, 0)\) must be a oneway function.

The function \(F'(k) := F(0, k)\) must be a oneway function.

The function \(F'(k) := F(k, 0) \ k\) must be a oneway function.

A oneway function must be collision resistant.

If \(\mathsf{MAC}(k,m)\) is a secure MAC, then \(\mathsf{MAC}(k,m)\) must be a pseudorandom function.

The function \(\mathsf{MAC}(k,m) := F(k,m)\) is a secure MAC with message space \(\{0,1\}^n\).

The function \(\mathsf{MAC}(k,m) := F(k,\textbf{0}^{n1}\m)\) is a secure MAC with message space \(\{0,1\}\), where \(\textbf{0}^{n1}\) is a string of \(n1\) zeros.

The function \(\mathsf{MAC}(k,m) := k \oplus m\) is a secure MAC.

Let \(H \colon \{0,1\}^* \to \{0,1\}^\ell\) be a collisionresistant hash function. There is a collisionfinding attack on \(H\) that runs in time roughly \(2^{\ell/2}\).

If \(\Sigma\) is a secure digital signature scheme (using the definition from lecture), then \(\Sigma\) remains secure even if an adversary can obtain many signatures on messages of its choice.

If \(\Sigma\) is a secure digital signature scheme (using the definition from lecture), then \(\Sigma\) remains secure even if an adversary can obtain half of the bits of the secret signing key.

It is possible to use the ``hashandsign’’ paradigm with Lamport signatures.

The RSA fulldomainhash signature scheme is proven secure under the RSA assumption and the assumption that the hash function is collision reistant.

A Lamport signature on an \(n\) bit message requires \(\lambda^2 n\) bits to represent, where \(\lambda\) is the output length of the oneway function.

There are in principle efficient (polynomialtime) attacks that break all known oneway functions on a quantum computer.

There are in principle efficient (polynomialtime) attacks that break RSA on a quantum computer.
Problem 1: Bad randomness in key generation
The file
ecdsa/keygen.py
generates an ECDSA signing keypair and prints the
resulting public key to standard output.

The public keys generated using this script are insecure, in the sense that it is possible to recover the secret signing key given only the public verification key.
Your task is to write a program,
problem_1a
insol.py
, that:
takes a date (formatted as
YYYYMMDD
) as a single commandline argument, 
reads a public key, generated by
ecdsa/keygen.py
, from standard input, and 
outputs the corresponding secret key, formatted as a base10 integer.
For example, on August 16, 2023 we generated a key…
$ python keygen.py > key.txt BEGIN PUBLIC KEY MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEQfbUYzbQUiQWHcOtcmf/cVr+ygHI hs560RKiVUV0gqm4OyNLB+HCSf8c7mGzxDuuid8z3RkdXC9vw1e6tDuSRg== END PUBLIC KEY
Later on, we should be able to use
problem_1a
to recover the secret key…$ with open('key.txt', 'r') as file: $ print(problem_1a("20230816", VerifyingKey.from_pem(file.read()))) 88928882924258032953987945121779605092553192944307381616887680985059143398985
Run
make check
to test your solution.Hint: Your program should not require more than a few minutes of compute time.
Hint: If you are running on a multicore machine, use as many cores as you can!


Your friend proposes instead reading
N
bytes of randomness from/dev/random
and using these bytes as the seed used to generate a 256bit ECDSA keypair.For which values of
N
is this approach secure? (Indicate all that apply.)
4 bytes

16 bytes

32 bytes

256 bytes

Problem 2: Bad randomness in ECDSA
ECDSA is one of the most widely used digitalsignature schemes. ECDSA is a randomized signature scheme; generating each ECDSA signature requires the signer to sample a fresh random signing nonce.
See Chapter 19.3 of BonehShoup book for a detailed description of ECDSA. You should think of an ECDSA signature as being computed as:
\(s \gets(H(m) + f(g^{\alpha_\text{t}}) \cdot \alpha)/\alpha_\text{t} \in \mathbb{Z}_q\),
where:

\(q \in \mathbb{Z}\) is a fixed 256bit prime,

\(m \in \{0,1\}^*\) is the message to be signed,

\(H\colon \{0,1\}^* \to \mathbb{Z}_q\) is a hash function,

\(g\) is the generator of and order\(q\) group \(\mathbb{G}\),

\(\alpha_\text{t} \in \mathbb{Z}_q\) is the signing nonce,

\(\alpha \in \mathbb{Z}_q\) is the signer’s secret key, and

\(f \colon \mathbb{G} \to \mathbb{Z}_q\) is some function fixed in the ECDSA standard.
Throughout this problem, we assume that ECDSA signatures are always computed using the P256 elliptic curve, where the order \(q\) is a 256bit integer.

Say that an attacker can obtain two valid ECDSA signatures \((r_0, s_0)\), \((r_1, s_1)\) that were generated using the same secret key \(\alpha\) and signing nonce \(\alpha_\text{t}\).
Show how an attacker can use these signatures to recover the signer’s secret key \(\alpha\). In particular, write an expression for \(\alpha\) in terms of the other quantities.
Hint: Your attack should not need to use any properties of elliptic curves.
Hint: Appendix A.2 of the BonehShoup book has helpful background about arithmetic modulo \(q\).

Write a program, in
problem_2b()
that takes as input two ECDSA signatures, signed using the same nonce, the hashes of the two messages signed, and outputs the signer’s secret key.The input to problem_2b will be two tuple signatures (in the form
(r,s)
) as well asH(m1)
andH(m2)
(converted to an integer) for example:sig1 = (3373270495537608166420301124031645059552155087339817978895, 4866115514576831317719439267655910857343196914135233616904) sig2 = (3373270495537608166420301124031645059552155087339817978895, 1026436076375142414773366823398026947727009880581933863772) Hm1 = 549937035807590235590408220127762782653536091071 Hm2 = 111625161468258865202361239710433310078751980605
Each
(r,s)
pair is one ECDSA signature. The orderq
of the NIST curve is listed here for your convenience.q=6277101735386680763835789423176059013767194773182842284081

In the ECDSA specification, \(\alpha_\text{t}\) is a uniformly random integer in the range \(\{1, 2, 3, \dots, q1\}\), where \(q \approx 2^{256}\) is the group order. Since ECDSA in this setting is only supposed to provide 128bit security, you might think that it would be safe to instead sample the signing nonce \(\alpha_\text{t}\) as a random number in the range \(\{1, \dots, 2^{128}\}\). Call this modified system “BadECDSA”.
Show that after an attacker obtains \(2^{64}\) BadECDSA signatures, it can recover the signer’s secret key with constant probability. Therefore BadECDSA can have at most 64bit security.
Problem 3: Security issues in the WEP encryption scheme
The early versions of wifi used the WEP standard to encrypt wireless network traffic. In this problem, we will explore a few weaknesses of the WEP standard.
WEP encrypts each packet (“data frame”) using the RC4 stream cipher. Given a secret key \(k\), the RC4 cipher generates a long sequence of pseudorandom bytes – the “keystream”. To encrypt a message we XOR these bytes with the message. To decrypt, we XOR these bytes with the ciphertext.

For the RC4 secret key, the WEP endpoints use a longterm secret (typically of 40 or 104 bits), concatenated with a 24bit random initialization vector (IV). The longterm secret is fixed – it is the wifi password – but the IV changes with each data frame.
Each 802.11b data frame is at most 2312 bytes and an 802.11b network has a theoretical maximum throughput of 11 megabits per second. Roughly how long will an attacker have to wait to see two frames encrypted using the same IV, assuming a busy network operating at maximum capacity?
What information can an attacker learn when this occurs?

WEP uses an insecure “hashthenencrypt” scheme for integrity protection. In particular, the sender sends the RC4 encryption of \((m \ \text{Hash}(m))\) to the recipient. To check message integrity, the recipient decrypts the frame to get \((m \ h)\) and accepts the packet if \(\text{Hash}(m) = h\).
Show that if the attacker intercepts a data frame containing the encryption of a known plaintext \(m\), the attacker can trick the recipient into accepting a message (of length \(m\)) of the attacker’s choosing.
Implement your attack as
attack_one
inwep/attacker.py
. The precise encryption scheme used by WEP is implemented bysend_packet()
inwep/victim.py
. 
WEP uses the CRC32 noncryptographic hash function to compute the messageintegrity hash.
The CRC32 hash function has the property that \(\text{CRC32}(x) \oplus \text{CRC32}(y) \oplus \text{CRC32}(z) = \text{CRC32}(x \oplus y \oplus z)\). Explain how an attacker can abuse this property to XOR bytes of its choice into a WEPencrypted data frame, even without knowing the message that the frame encrypts.
Implement your attack as
attack_two
inwep/attacker.py
. 
Extra credit (challenging): A WEP recipient who receives a data frame with an invalid integrity hash will complain, while a recipient who receives a valid data frame will not. Explain how an attacker can use this information to extract the entire contents of an encrypted frame.
Implement your attack as
attack_three
inwep/attacker.py
.Hint: Think about resizing the packet that the attacker intercepts.
Hint: The fastest attack will exploit some structural properties of the CRC32 checksum. You will have to do some research to figure it out.
Extra credit: Bad randomness in GMAC
Read Chapter 9.7 of BonehShoup book, which is about the AESGCM mode of operation. AES is by far the most widely used cipher today and GCM is a popular modern mode of operation, used in TLS 1.3 and many other places.
This problem will demonstrate that bad randomness is catastrophic for AESGCM: if the sender of a message reuses an encryption nonce even once, an attacker can break the CCA security of the encryption scheme.

Say that an attacker intercepts a GCM ciphertext \((c,t)\) and is somehow able to obtain the GHASH key \(k_\text{m}\) used to generate this ciphertext.
Explain how the attacker can use its knowledge of \(k_\text{m}\) to break the CCA security of AESGCM.

Say that an attacker intercepts a pair of distinct GCM ciphertexts \((c_0, t_0)\) and \((c_1, t_1)\), both encrypted with the same secret key and the same 96bit encryption nonce \(\mathcal{N}\). Show how the attacker can recover the GHASH key \(k_\text{m}\) from these two ciphertext pairs.
Hint: The function GHASH is defined using arithmetic in \(GF(2^{128})\), but you can think of GHASH as using arithmetic modulo a 128bit prime \(p\). In this setting, all of the “nice” algebraic properties hold: a polynomial of degree \(d < p\) has at most \(d\) distinct roots (and there is an efficient algorithm to find them), every element has an additive and multiplicative inverse, etc.

Propose one way to modify AESGCM so that this integrity attack is not possible, even if the sender reuses the nonce. In one sentence, speculate on why the GCM designers did not incorporate your fix into their design.