1
$\begingroup$

Recently a friend of mine showed me a "puzzle" he created with curve ed25519

It is based on adding and multiplying points on the curve

You supply three arguments to the program

The 'public key'
The 'private key'
additional data

He considers the puzzle as solved if the following 'equation' applies:

static-point = cdaaf6715f5aace083b25b3b2f621ebacc5e7f25463e1e51100cc16677bb158a

hash = sha512(public key + data)[:32] // first 32 bytes

private key * ed25519 base point == ed25519addpoint(ed25519scalarmult(hash * public key), static point)

It can be represented with the following python code with the usage of nacl cryptography library:

import nacl.bindings
import hashlib

def sha512(data):
    h = hashlib.sha512()
    h.update(data)
    res = h.digest()
    return res

data = "additional data in hex".decode("hex")
privkey = "private key in hex".decode("hex")
pubkey = "public key in hex".decode("hex")
static = "cdaaf6715f5aace083b25b3b2f621ebacc5e7f25463e1e51100cc16677bb158a".decode("hex")

pprim = sha512(pubkey + data)
pprim = pprim[:32]

x = nacl.bindings.crypto_scalarmult_ed25519_base(privkey)
y = nacl.bindings.crypto_core_ed25519_add(nacl.bindings.crypto_scalarmult_ed25519(pprim, pubkey), static)

if x == y:
    print "Congratulations, puzzle solved!"
else:
    print "Not really"

He claims that he found multiple solutions to this problem. My question is: is this really solvable (and if yes, how?) or is he only trying to trick me into trying to solve an unsolvable problem.

From my cryptographic knowledge of ed25519 curve you cannot solve this from both ways:

  • if you supply any value as the private key you could subtract the static point and then try to find values of pprim and public key - if it is solvable this is the way I tried to solve it

  • compute the hash of public key and data and then try to find the value of private key

Both of this ways are impossible for me, because either solution is equal to finding private key from public (d from having P = d*G) on ed25519 which, from my knowledge is impossible.

$\endgroup$
3
  • $\begingroup$ Duplicate of crypto.stackexchange.com/questions/106900/… $\endgroup$
    – knaccc
    Commented Dec 18, 2023 at 12:17
  • $\begingroup$ @knaccc: well spotted. I closed the other Q as duplicate of this one, since we have an answer here, and the question contains more of the original problem (likely a CTF): here it looks like we can't change static, when it looks like we could in the other Q. To the OP: I guess you lost access to your former account deneth0r9. Merging these is possible, but unfortunately is complex. $\endgroup$
    – fgrieu
    Commented Dec 18, 2023 at 14:22
  • $\begingroup$ Is the actual puzzle finding what hex strings must be put instead of "additional data in hex", "private key in hex" and "public key in hex" in order to reach the Congratulations branch? This looks like a CTF (which is bordeline if at all on-topic), and it would help (towards being on-topic, and resolution) to write it in mathematical notation rather than Python. Possible hint: have you considered deliberately making pubkey such that pprim×pubkey is one of few remarkable points regardless of the haphazard construction of pprim ? $\endgroup$
    – fgrieu
    Commented Dec 18, 2023 at 14:35

2 Answers 2

1
$\begingroup$

Reading another closed question I must add cases to this answer. The question, however, still provide insufficient details.

CASE 1: If static point is always constant (the one you gave in question) no matter what private key and data value you choose

It is impossible. Let,

$x_p$ be private key, public key be $x_{pu}$, $s_{pu}$ be static point and the key corresponding to static point be $s_p$, and let $e$ be hash bytes, and let $d$ is data.

Notaions: $*$ sigify multiplication as if $2*2=4$, $+$ sinify addition as if $2+6=8$ $.$ signify scalar multiplication and $+'$ signify point addition.

Now:

$x_p.G=(e.x_{pu})+'(s_p.G)$

$x_p.G=(e*x_{p}.G)+'(s_p.G)$

$x_p.G=(e*x_{p}+s_p).G$

$x_p = e*x_p + s_p$

Since, all opertaions in elliptic curves are performed modulo $n$ the above holds true iff:

$x_p \equiv e*x_p + s_p \mod{n}$

$x_p - s_p \equiv e*x_p \mod{n}$

$1 - (s_p*(x_p)^{-1}) \equiv e \mod{n}$ ...(i)

We know that hash functions are always one way so in order to produce same output, input must be same.

We also know that $e = H (x_p || d)$ where $H$ is the hash function.

Analysing (i) we can conclude:

for a given $x_p$ there will be only one hash $e$

But this contradict the fact that our hash function $e = H (x_p || d)$ depends on two variables namely $x_p$ and $d$.

In other words the output of hash is independent of variables which means collisions which means that the hash function is itself broken.

Recall that your friend is talking about SHA512. Which means he has broken one of the most secure hashing algorithm. Volla.

CASE 2: If choice of static point depends on the private key value and data

It is possible. Because in that case you need to define $s_{pu}$ as $(1-e).x_{pu}$. Because:

$s_p = (1-e)*x_p$ substituting this in

$x_p = e*x_p + s_p$

$x_p = e*x_p + x_p - e*x_p$

$x_p = x_p$

Hence LHS = RHS

But if case 2 is your case then there is nothing like puzzle in your question.

$\endgroup$
3
  • $\begingroup$ Possible hint [updated to match the extended answer, and clarify]: Could there be a loophole in the CASE 1 argument where it is assumed that $x_{pu}$ (that is pubkey) can be written as $x_p.G$? Independently, this arguments holds if static was random, which is unclear in the Q. If we are allowed to choose static, it's easy to do so as a function of data, privkey, pubkey to satisfy the requirement. Assuming the problem was generated in this way with guessable data (e.g. empty), privkey (e.g.equivalent to integer 2) and pubkey (e.g. equivalent to $3.G$), then it can be solved. $\endgroup$
    – fgrieu
    Commented Dec 18, 2023 at 15:08
  • $\begingroup$ @fgrieu I am unable to understand your hint, what does 'loophole' means? $\endgroup$
    – madhurkant
    Commented Dec 19, 2023 at 3:47
  • $\begingroup$ [updated to match the extended answer] A loophole is a mean of escape, here of the conclusion in CASE 1 (I hope my usage is correct; I'm not a native English speaker either). I mean, if it was mathematically incorrect that for any point $x_{pu}$ of the curve (as limited by the possibility of applying the code fragments shown without causing an exception), it can be found integers $x_{p}$ with $x_p.G=x_{pu}$, the argument developed in CASE 1 would be wrong (beside not stating as hypothesis that static is arbitrary). This suggests an unexplored path, which may not lead to a solution. $\endgroup$
    – fgrieu
    Commented Dec 19, 2023 at 7:48
0
$\begingroup$

I find the thought process to try tackle the question representative of the right state of mind for attacks on implementations, thus interesting even though the question is likely a CTF (which is why I wouldn't fully answer if I had solved the puzzle; I have not).

Notation from the Ed25519 paper

Let $q=2^{255}-19$. Let $d=−121665/121666\in\mathbb F_q$. Let $$E=\{(x,y)\in\mathbb F_q\times\mathbb F_q:\;-x^2+y^2=1+dx^2y^2\}$$ Define addition on $E$ as $(x_1,y_1)+(x_2,y_2)=(\frac{x_1\,y_2+x_2\,y_1}{1+d\,x_1 x_2\,y_1\,y_2},\frac{y_1\,y_2-x_1\,x_2}{1-d\,x_1\,x_2\,y_1\,y_2})$.

Let $B$ be the unique $(x,4/5)\in E$ for which $x\bmod 2=0$ (where $0\le x<q$).

$(E,+)$ is an Elliptic Curve group of order $8\,\ell\gtrsim q$, with $B$ of prime order $\ell$.

Any $P\in E$ has a unique 32-byte representation as bytestring noted $\underline P$. But only a little above $\frac 1 2$ of 32-byte bytestrings represent an element of $E$.

The question's problem

Note the question's variables as follows. All are bytestrings, and I assume all except perhaps data are 32-byte:

data privkey pubkey static pprim
$D$ $R$ $U$ $S$ $P$

$P$ is constructed by a pseudorandom function of $D$ and $U$ built from SHA-512. I assume $R$ and $P$ are assimilated to integers $r$ and $p$ in $[0,2^{256})$ per some convention that I won't dive into, built into crypto_scalarmult_ed25519_base and crypto_scalarmult_ed25519.

Broadly, we are given $S$ that Google finds only in the question, and asked $D$, $R$, $U$ with $$r\cdot B=\bigl(p\cdot U\bigr)+S$$ where $\cdot$ and $+$ are scalar multiplication and addition for the elliptic curve group $E$. This however is a simplification assimilating bytestrings $U$ and $S$ to points on $E$ with these representations, and leaves aside:

  • Our ability to supply $U$ (aka pubkey) that's not among the 32-byte bytestrings that represent an element of $E$.
  • The lack of assurance that the value of $S$ (aka static) in the question is among the 32-byte bytestrings that represent an element of $E$.

Possible hint: explore what adding $S$ with crypto_core_ed25519_add actually does.

Another possible hint: explore the ways to make $U$ (the representation of) some element of $E$ such that $p\cdot U$ would be noteworthy despite the hapazardness of $p$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.