Assignment #4 - Bonus: Blind signatures

A blind signature is a type of digital signature whose content is blinded prior to being signed so that the signer does not get any information about what it is issuing the signature for. The resulting blind signature can be unblinded and publicly verified as a regular digital signature, unlinkable with the blinded signature. This property has been utilized in the design of earlier electronic cash systems prior to the invention of blockchain-based solutions.

IA174 Electronic Cash System

In this assignment, you will work with the IA174 Electronic Cash System. The system allows clients to perform two operations: withdrawing and depositing of coins. Withdrawn coins are represented as digital signatures that can be later used to deposit a coin to an account. In a real system, withdrawn coins could be exchanged between clients and deposited to a different account. However, for the purpose of this assignment, no transfers between clients are possible (you will use only your account).

To withdraw a coin from an account, a client requests a blind signature of an arbitrary message (e.g., IA174Coin). When the signature is issued, the balance on the client's account is decreased.

To deposit a coin to an account, a client has to present a valid (unblinded) signature together with the signed message. The system verifies the signature using its own public key. If the signature is valid and it has not been previously used in a deposit, the client's account balance is increased.

Task

You are given an account in the IA174 Electronic Cash System containing 256 coins. Your main task is to perform an attack on the system, after which you end up with more coins in your account than you started with. If you manage to perform the attack while withdrawing at most 240 coins, you will be awarded additional points. The extended attack requires only a minor modification of the basic attack.

You can get one point for a deposit even without succeeding with the attack.

Background

This section defines Schnorr signatures, presents a Schnorr blind signing protocol, and gives an intuition of the ROS problem.

Schnorr signatures

The IA174 Electronic Cash System utilizes Schnorr signatures which allow for simple and efficient blind signing. In this assignment, we will be using Schnorr signatures over the group of points of an elliptic curve (hence the additive notation), but they can be formulated for any group.

Given a group of points of an elliptic curve $\mathbb{G}$ with generator point $G$ of order $q$ and a hash function $H: \mathbb{G} \times \{0, 1\}^* \rightarrow \mathbb{Z}_q$, a Schnorr signature of a message $m \in \{0, 1\}^*$ verifiable with a public key $X = x\cdot{}G$ corresponding to a private key $x \in \mathbb{Z}_q$ is a pair $(R, s) \in \mathbb{G} \times \mathbb{Z}_q$, for which the verification equation $s\cdot{}G = R + H(R, m)\cdot{}X$ holds.

With the knowledge of the private key $x$, such signature can be computed in three steps:

1. Uniformly sample a nonce $r \in \mathbb{Z}_q$ and compute the point $R = r\cdot{}G$.
2. Apply the hash function to $R$ and $m$ to obtain the challenge $e = H(R, m)$.
3. Compute the signature as $(R, r + ex \pmod q)$.

Blind Schnorr signing

A two-round protocol for blind signing resulting in Schnorr signatures is shown in the following diagram. First, a nonce point $R$ that will be used in the signing is received from the server. The user then samples two random blinding values $\alpha$ and $\beta$, using which he blinds the nonce $R$, resulting in $R'$. Subsequently, the challenge is computed using the blinded nonce $R'$, and the result is blinded with $\beta$. The blinded challenge is then sent to the server, for which it outputs a blinded signature. The user then unblinds the signature by adding $\alpha$, obtaining a valid Schnorr signature $(R', s')$ verifiable with the server's public key $X$.

Note that blinding is performed only on the client side, thus it can be avoided to simplify your implementation, if you do not need unlinkability.

The security of blind Schnorr signing protocol has been reduced to both DLOG and ROS problems, the latter of which has been found vulnerable to sub-exponential and under specific conditions even polynomial attacks.

Attack by finding a solution to the ROS problem

A paper published in 2020 by Benhamouda et al. shows how an attack on the Schnorr blind signature protocol (and a number of other similar protocols) can be achieved if certain preconditions are met. The rest of this section gives a rough intuition of the attack. However, you should read the paper for full details.

ROS problem intuition

Digital signature schemes that rely on the use of a hash function can be broken without solving the underlying hard problem by finding a collision with a hash value used in a previously issued signature. For example, a signature $(R, s)$ of a message $m_1$ is also a valid signature of $m_2$ if $H(R, m_2) = H(R, m_1)$.

Finding such a collision in a well-designed hash function like SHA-256 should be infeasible and require approximately $2^{255}$ attempts. However, if you can control a challenge that gets signed, you can find a collision more efficiently due to the birthday paradox by searching for any $m_1, m_2$ such that $H(R, m_1) = H(R, m_2)$. Still, this approach would require approximately $2^{128}$ attempts and thus is impractical.

In the case of Schnorr signatures (and other linear signatures), this approach can be extended if you can concurrently control multiple challenges that get signed, since it holds for signatures $(R_1, s_1), (R_2, s_2)$ of messages $m_1, m_2$ that $(R_1 + R_2, s_1 + s_2)$ is a signature of some message $m_3$ such that $H(R_1 + R_2, m_3) = H(R_1, m_1) + H(R_2, m_2)$. Finding such $m_1, m_2, m_3$ requires approximately $2^{99}$ attempts using an algorithm for the generalized birthday problem. By combining more signatures, the expected number of attempts decreases, but only logarithmically.

The approach can be generalized not only to a sum of signatures, but to any linear function. In the case of Schnorr signatures, it suffices to find a linear function $\rho$, a message $m_{l+1}$ and a set of $l$ challenges $e_i = H(R_i, m_i)$ satisfying $\rho(e_1, \dots, e_l) = H(\rho(R_1, \dots, R_l), m_{l+1})$, which is an instance of the ROS problem. To find out how this problem can be efficiently solved in polynomial time for sufficiently large $l$, see the paper by Benhamouda et al. (Section 5.1 is particularly useful).

If you are interested in the ROS problem definition, see the original Schnorr's paper.

API

The interaction with the IA174 Electronic Cash System is realized via six endpoints. You authenticate to these endpoints with a token available in your IS notebooks. Try not to overload the server by making too many requests in a short period of time. Provided code contains a delay preventing the overloading - please, do not remove it.

You can find an example code performing blind signing using the endpoints in Python here. The example requires Python 3.8 or newer, requests package, and this ec.py file stored in the same directory as the example file.

Technical details

The system uses a custom implementation of Schnorr signatures over the secp256r1 curve (also known as P-256) instantiating the hash function with SHA-256.

Elliptic curve points are encoded using uncompressed SEC 1 encoding. All numeric computations with integers are performed modulo the curve order (slightly less than $2^{256}$); thus, every integer can be encoded in 32 bytes. Integers are encoded in big-endian. Strings are encoded in UTF-8. To send raw bytes to the API endpoints, encode it as a hex string.

The hash function takes in two inputs: an elliptic curve point and a string. Both of them are encoded as described in the previous paragraph and passed in the SHA-256 as bytes. The output of SHA-256 is interpreted as a big-endian integer modulo the curve order. This instantiation and the provided implementation are simplified for this assignment and quite likely insecure. Do not use it anywhere else, but also do not search for the vulnerability in the signature implementation itself.

Submission

You should submit a zip archive containing two things:

• A description.txt file that contains description of how you solved the task (i.e., what you did in order to deposit more coins than you withdrew). Please keep the descriptions reasonably short and clear (4-5 paragraphs should be enough).
• A code directory that contains any source code used in solving the task.
• [Optional] An llm.txt file. Include only if you used an LLM during your work. If you used an LLM with chat-like natural-language interface (ChatGPT, Bing Chat, etc.), the file should include the transcription of the relevant part of the interaction with the model (your prompts and the model's responses). If you used an LLM focused on code completion (such as Copilot), write a very brief description of how do you feel the model helped you with writing your code.

Grading

A successful attack on the system is worth 3 points. If you manage to forge a coin while withdrawing at most 240 coins, 4 additional points will be awarded. Up to 3 points can be awarded for the description. However, a submission with no description is worth 0 points. Not conforming to the submission format specified above leads to -0.5 point penalty.