3
$\begingroup$

I have an elliptic curve system with only one point P. Let's say the client A and server B generate a secret R1 and R2.

A is sending X1 = mul(R1, P) to B and B is sending X2 = mul(R2, P) to A then shared secret is the same for both : S = X1R2 = X2R1

The system only have one point and i have X1,X2 and P. I'm trying to compute the shared secret, by calculating R1 and R2. However the curve function is hard to reverse because of the n = n // 2.

The function :

#R is the private number generated client/server side
# P is the point
def mul(R, P):
         
        Q = P.copy()
        Q2 = PointInf()
        while R > 0:
            if R % 2 == 1:
                Q2 = add(Q2, Q)
            Q = add(Q, Q)

            R //= 2
    
        return Q2

On small number n, we can easily reverse the function and find R because there is not a lot of iteration so we can make a aproximation and then bruteforce, but what can we do for big R (my case is 175 iterations) .

Is that mathematically possible ?

$\endgroup$

1 Answer 1

3
$\begingroup$

What you are describing is Diffie-Hellman on some group with neutral PointInf() [hereafter noted $\infty$] and law add() [hereafter noted $\boxplus$]. The problem statement does not say which, but the title suggests an Elliptic Curve group over some finite field. Function mul(R, P) computes scalar multiplication $R\boxtimes P=\underbrace{P\boxplus \ldots\boxplus P}_{R\text{ terms}}$. From associativity of $\boxplus$ it follows $R\boxtimes P$ is well-defined, and that $R_1\boxtimes (R_2\boxtimes P)=(R_1\times R_2)\boxtimes P=(R_2\times R_1)\boxtimes P=R_2\boxtimes (R_1\boxtimes P)$ [where $\times$ is integer multiplication].

I'm trying to compute the shared secret, by calculating $R_1$ and $R_2$.

$R_2\boxtimes P$ and $R_1\boxtimes P$ are known, thus an attacker only needs to compute $R_1$ or $R_2$ to recover the shared $S$.

On small number $n$, we can easily reverse the function and find $R$ because there is not a lot of iterations, so we can make an approximation and then bruteforce, but what can we do for big $R$ (my case is 175 iterations).

If indeed we are on an Elliptic Curve over some finite field, I don't see how we can "make an approximation". I'll assume both $R_i$ are random in $[0,n)$ with $n\boxtimes P=\infty$ or a similar interval, and $\log_2(n)\approx175$.

Can we reverse Elliptic Curve multiplication?

Finding $R$ given $R\boxtimes P$ and $P$ is the Discrete Logarithm Problem. It's the best known general method to find $S$. The best known general methods to solve the DLP (e.g. distributed Pollard's rho with distinguished points) have cost in the order of $2\sqrt n$ additions, and that's out of reach (unless one can invest billions in designing, producing and running specialized gear). However

  • there are much better algorithms for some Elliptic Curves (e.g. supersingular, or when $n$ is composite).
  • perhaps one of the $R_i$ is not really random
  • perhaps some extra information leaks (like the time required for the computation of $R\boxplus P$, or CPU cache lines used by that computation; both could help).
  • or perhaps this is a devious CTF and the problem does not call for finding $S$.
$\endgroup$
6
  • $\begingroup$ Ok. Thanks for the explanation. Yes indeed R is fully random and really big so yeah guessing is completely impossible. Gonna check the supersingular algorithm and distributed Pollard's to check if this can help me in my problem (it is indeed a ctf ). When you say Extra information leaks, what information could help us to recover R1 or R2 ? $\endgroup$ Jul 27, 2021 at 10:39
  • $\begingroup$ @ThibaultPoncetta: see updated butlast bullet. [update: see penultimate bullet point] $\endgroup$
    – fgrieu
    Jul 27, 2021 at 11:09
  • $\begingroup$ butlast bullet ? Do you have another word to describe it ? I don't find a traduction of this ^^. $\endgroup$ Jul 27, 2021 at 11:26
  • $\begingroup$ In my butlast bullet (point), the butlast is trying to mean: before the last (it's common in computer science, but I don't know if it's attested elsewhere as a single word [update: see comment below, it has a different meaning]). And bullet is a typographical term, designating the symbol (often a black disc) introducing an item in a list. I'm not a native English speaker, so beware of my explanations about that! $\endgroup$
    – fgrieu
    Jul 27, 2021 at 11:55
  • 1
    $\begingroup$ This is getting off-topic, but as a native speaker of American English who has studied CS for over 20 years, this is the first time I've ever seen the word "butlast." I would use "penultimate" to mean the $(n-1)$th item in a list of $n$ items, or even "next-to-last" to sound less fancy. A quick search (i.e., I might be missing other usages) shows "butlast" being used to mean items 1 through $n-1$ -- all items but the last -- rather than only the $(n-1)$th item. $\endgroup$
    – Mikero
    Jul 27, 2021 at 19:22

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .