Assignment #3 - Size matters: small subgroups

Background

As you know from the lecture, the Diffie-Hellman key exchange scheme allows two parties to securely establish a shared secret. Currently, the most popular variant of this scheme is the elliptic curve Diffie-Hellman (ECDH) which is based on the group of points of an elliptic curve. Recall that an elliptic curve is the set of solutions $(x,y)$, called points, of an equation $y^2=x^3+ax+b$ for $x,y \in \mathbb{F}_p$. This set forms a group with the operation $P+Q$ for any two points $P$, $Q$, as defined in the lecture (we use the additive notation for the group operation). For cryptographic applications, for any two points $P$ and $k\cdot P $ it should be unfeasible to compute the scalar $k$ (the discrete logarithm problem).

We will consider the following version of ECDH between server and a client on a group of points with a generator $G$:

1. Server randomly samples a private scalar $k \in \{1,\dots,|G|-1\}$ and computes his public key as $P = k \cdot G$. Server then sends $P$ to the client.
2. Client randomly samples a private scalar $l \in \{1,\dots,|G|-1\}$ and computes his public key as $Q = l \cdot G$. Client then sends $Q$ to the server.
3. Server computes $k\cdot Q = S$. The shared secret is then the hash SHA-256($x|y$), where $S = (x,y)$ and $|$ denotes concatenation.
4. Client computes $l\cdot P = S$. The shared secret is then, again, the hash SHA-256($x|y$) where $S = (x,y)$.

The shared secret can thereafter be used, for example, as a symmetric key for encryption.

Instructions

Petr has decided to implement ECDH on his server and selected the elliptic curve $ y^2=x^3+ax+b$ over $\mathbb{F}_p$, where $$ \begin{align*} p &= \mathtt{0x586be5268256ae12d62631efc2784d02dcff420d262da9cd94c62d5808bee24d},\\ a &= \mathtt{0x45f1cdae7af39607fe50b9d51661908139070320393d2c393fe6f2dc6b6ceb75},\\ b &= \mathtt{0x0}. \end{align*} $$

The neutral element in the group of points is represented as $(0,1)$. The curve has the number of points equal to $N=n_1\cdot n_2$, where $n_2$ is a prime and $$ \begin{align*} n_1 &= 940258296925944608662895221235664431210, \\ n_2 &= 42535295865117307932921825928971027169. \end{align*} $$

Petr heard that groups in cryptographic applications should have number of elements equal to prime and so he decided to only use the subgroup of points of size $n_2$. He figured that this will be more efficient anyway. For his ECDH implementation, Petr picked a point $G = (x_G, y_G)$ of order $n_2$ where $$ x_G = \mathtt{0x2b58947b361fe7fed0d059da0c99483b1085a9b75b13ca65d2e6ee2919e9967},\\ y_G = \mathtt{0x2f50b39c4a1573511b08ca9505f234a13e215b3c213197633cb8eb7a2f5fd818}. $$ Petr then randomly generated a private scalar $k \in \{1,\dots,n_2\}$ and a corresponding public key $P=k\cdot G$. He implemented on his server a function $\text{ECDH}_{\text{Petr}}$ which, given a point $Q$ on the curve, outputs SHA-256($x|y$), where $(x,y)=k\cdot Q$. In real life scenario, the shared secret should not be revealed at the end, but rather used for further operations like key derivation and symmetric key encryption (whose output then might be revealed). In this homework, we will settle with this simplification.

You can find a copy of an implementation of elliptic curve operations and the ECDH scheme running on Petr's server in ec.py. You might find useful, among others, an implementation of point addition (ec.add), scalar multiplication (ec.rtl), or the compression function (ec.compress).

Sagemath

Petr wrote the provided implementation in ec.py for his purposes only. While it correctly implements the computation specified above, it is not correct to re-use it for more general elliptic-curve computations. We recommend to use a foolproof implementation of elliptic curve arithmetic from the computer algebra software Sagemath (see the documentation). The following is an example of a basic usage of Sagemath for ECC.

        from sage.all import *

        Fp = GF(13590256669019655763)
        a,b = 8440144734531749845,6555503898170400986
        E = EllipticCurve(Fp,[a,b])
        n = E.order()
        G = E(4631243722373859192, 12742715404725835811)
        k = randint(1,n) # Unknown private key
        P = k*G # Known public key
        

Task 1 (7 points)

Your goal is to determine Petr's secret scalar $k$ given access to $\text{ECDH}_{\text{Petr}}$ running on his server. In order to do this, you should implement the so-called small subgroup attack (see the general explanation below). The task is divided into three subtasks:

1. Find a generator of Petr's elliptic curve (i.e., a point of order $N=n_1\cdot n_2$). You might find Chapter 4 of the Handbook of Applied Cryptography helpful (see course webpage for a link) or you can use an appropriate function in Sagemath. (1 point)
2. Implement the small subgroup attack and provide a short description of your attack (5 points). Focus on the differences between the general small subgroup attack and the attack in our scenario in your description. In particular, describe the condition that allows you to recover $k$ from the knowledge of its modulus.
3. In the description of your attack, justify why the following implication from the small subgroup attack holds: if $P_q = k\cdot G_q$ then $k=k_q \pmod q$ (1 point) .

Small subgroup attack

Let $E:y^2 = x^3+ax+b$ be an elliptic curve over a finite field $\mathbb{F}_p$ with a generator $G$. Assume that $E$ has an order $n$ divisible by a small prime $q$. Suppose that we are given a point $P$ which satisfies $P=k\cdot G$ for some secret $k\in \{1,\dots,n\}$. Small subgroup attacks recovers $k \pmod q$.

Denote $n_q = \frac{n}{q}$, $G_q = n_q \cdot G$ and $P_q = n_q \cdot P$. Point $G$ has order $n$, and the order of $P$ divides $n$. Since $q$ is a prime, the order of $G_q$ is q, and the order of $P_q$ is $q$ or $1$. Points $G$ and $P$ have order $n$, and so the points $G_q$ and $P_q$ have order $q$, since $q$ is a prime. It follows that the discrete logarithm $k_q$ of $P_q$ with respect to $G_q$ is an element of $\{1\dots,q\}$. We know that $P_q = k\cdot G_q$, which implies $k = k_q \pmod q$. In particular, if we can find $k_q$ (e.g. by brute-force) we can find $k \pmod q$.

Suppose that we have figured out $k \pmod {q_i}$ for several small primes $q_i$ dividing $n$. Then we can apply the Chinese remainder theorem to get $k \pmod{\prod q_i}$. Under certain conditions, which hold in our setting, this can be used to recover $k$.

Task 2 (3 points)

Petr found out about the small subgroup attack and implemented a small check to $\text{ECDH}_{\text{Petr}}$ from the safecurves website:

However, the recommended countermeasure does not work in this case. Your goal is, again, to determine Petr's secret scalar $k$ using an appropriate modification of the small subgroup attack and provide a short description of your attack (3 points).

API

There are several API functions available. You will be using functions Pubkey (easy) and ECDH (easy) for Task 1 and functions Pubkey (hard) and ECDH (hard) for Task 2.

Submission

You should submit a zip-file containing three things:

• A solution.txt file that contains three lines (if you skipped a task, leave the corresponding line empty):
  • $x$-coordinate and $y$-coordinate of the generator you found as decimal integers separated by a comma,
  • Petr's secret scalar from Task 1 as a decimal integer,
  • Petr's secret scalar from Task 2 as a decimal integer.
• A description.txt file that contains your description of how you solved the task (i.e. what you did in order to obtain the secret message, how you came up with it, etc.). Your solution of the third subtask of Task 1 should be a part of this file. Please keep the descriptions reasonably short and clear (4-5 paragraphs should be enough). Cite any external sources for the solution ideas and code that you have used accordingly. Use of large language models (LLMs, e.g., ChatGPT, Bing Chat, Bard, Copilot, etc.) must be declared in the description.txt file. Specify which LLMs you used and give a one-sentence description of the purpose for which you used them. You don't have to cite this course's materials and links provided in this assignment's text.
• A code directory that contains any source code used in solving the tasks (including any short scripts or commands in Sage).
• [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

Not conforming to the above format of the solution leads to a -0.5 point penalty.