CSE 291E, Fall 2020
Homework 7: Repeated ECDSA nonces

The web application located here validates API queries using an ECDSA signature before executing the commands in the query string. To validate the token, the web server parses the full query as:

    query = token=token_string&rest_of_query_string
and then checks whether token_string is a valid ECDSA signature over the SHA256 hash of rest_of_query_string using the NIST p256 pubic key 0aab330d1a7ae4f6bfd35f9c5f6600ca42a8090142be2cfe37cd7a87d4483630045e8a5146cd1f4ddc2c150bebc2c2c8b969e8bf86186f3d62d77106cd2b6700.

Unfortunately for this server, it didn't use a very good random number generator when generating the ECDSA signatures, and accidentally repeated the signature nonce k. Here is another valid token/query combo. Your task is to recover the server's secret signing key and forge a valid ECDSA signature on the query string user=admin&get_file=hw7.pdf that will allow you to download the rest of your homework.

Repeated DSA and ECDSA nonces have been found many times in the wild, including for Bitcoin (2013 and 2016) and other cryptocurrencies as well as in protocols like SSH.

You may use pure Python or any version of Sage to implement your solution, just document what version you used for the graders. Gradescope will expect your script to be named hw7-sol.py.

You do not need to implement elliptic curve addition or point multiplication yourself for this assignment. Feel free to use the Python ecdsa package or Sage's EllipticCurve class.

Please submit your code and a short description of how you solved the problem along with a PDF named hw7-solutions.pdf of your LaTeXed solutions to the other problems to Gradescope before class on Tuesday, December 1. You may discuss this assignment in small groups with classmates, but please code and write up your solutions yourself. Please credit any collaborators you discussed with and any references you used.

Here is some sample code illustrating ECDSA validation for our example inputs:
#!/usr/bin/env python3

import ecdsa
import hashlib
import binascii

pubkey = b'0aab330d1a7ae4f6bfd35f9c5f6600ca42a8090142be2cfe37cd7a87d4483630045e8a5146cd1f4ddc2c150bebc2c2c8b969e8bf86186f3d62d77106cd2b6700'
signature = b'3f8c5fe7180473a25e446498accabb2b5a21d1a106c3be8c0651ac95225938282fa2412f00e161321fd2b213c7f8a2409c70d852d4332d06f0196b604518bce9'
query_string = b'user=admin&get_file=kitten.jpg'

vk = ecdsa.VerifyingKey.from_string(binascii.unhexlify(pubkey),curve=ecdsa.NIST256p)