#pee-side thread

1 messages · Page 1 of 1 (latest)

dense pasture
#

foo

sonic musk
#

bar

#

@rich olive

Screenshot_2024-02-03_at_08.png
fierce prism
#

wororororororoo

quartz kernel
#

Challenge was great

rich olive
#

some explaination with the screen ?

quartz kernel
# 
sage: def recover_secret(P):
....:     res = []
....:     for (ell, _) in P.order().factor()[1:]:
....:         Qy = ((P.order() // ell) * P)[1]
....:         if Qy[0] == 0:
....:             res.append(1)
....:         elif Qy[1] == 0:
....:             res.append(-1)
....:         else:
....:             res.append(0)
....:     return res
....:     
sage: b = recover_secret(Pa)
sage: b == a
True
#

I just recovered a from the image of PP and sent Ea as my curve and Eaa as a shared secret

sonic musk
#

let me explain wpaeohkawpoehkko

#

whatever

storm shore
#

mine's basically the same as jack:

def getval(P, l):
    w = [z.frobenius()==z for z in (psidh.p+1)//l*P]
    return w[0]*(-1)**w[1]
a = [getval(Pa, l) for l in ell]
quartz kernel
#

I can do a write up maybe

#

But it was a cute challenge. I really liked it

rich olive
#

I thought we had to create some curve for which we could guess the shared secret

sonic musk
#

You can recover a

quartz kernel
#

“Torsion point attack for CSIDH” haha

rich olive
#

ok so i have to rethink everything now, I'll look at that before looking at a wu

sonic musk
#

Recall the notation: The starting curve is E0 and point is P0
And say we walk a l0 = 211-degree isogeny from E0 i.e. set Ea = act(E0, [1, 0, 0, ..., 0]) and denote by phi the isogeny
Then one can prove that phi(P0) will be of the form (x : y : 1) where x is in F_p, and y is in F_p^2

And if you know how CSIDH works you already know this, because the group action also satisfies E0 = act(Ea, [-1, 0, 0, ..., 0]) right (the dual isogeny phi_dual), and its kernel point will be the (F_p : F_p^2 : 1) form.

On the other hand, if Ea = act(E0, [-1, 0, 0, ..., 0]), then its dual will correspond to be vector [1, 0, 0, ..., 0], so its kernel point(which will be phi(P0) again) is of the form (F_p : F_p : 1)

You can see the observation above in the CSIDH code (you can prove it by looking at the Frobenius eigenvalues blablabla)

        while any(es):
            E.set_order((self.p + 1)**2)

            P = E.lift_x(ZZ(randrange(self.p)))
            s = [-1, 1][P[1] in GF(self.p)] # if y is in F_p^2, then it corresponds to a "-1" in exponent
            k = prod(l for l, e in zip(self.l, es) if sign(e) == s)
            P *= (self.p + 1) // k

        ...
#

And once you get this, the rest is clear some cofactors then check whether the case above happens

storm shore
#

If you don't really want to think about kernels and stuff, basically you just have to know that an isogeny composed with its dual is the multiplication-by-l map. So roughly speaking you can brute force the dual to see which points are multiplied by l

fierce prism
sonic musk
#

I think looking at the kernel is not that hard anyways since you need it to know how CSIDH works

unkempt cape
sonic musk
#

Also you can send a 2-torsion point and ignore the part about the image in the hash

#

btw I told y7 to look at it, and a few hours later he just came back with a "indeed!", and I see hxp with one single solve 😂

quartz kernel
#

I think the way I thought about it is that on Fp2 you can see the curve E/Fp and it’s twist hiding inside E/Fp2 and because all the kernel points in CSIDH have Fp rational c values, you know that the isogeny is essentially killing the contribution from E/Fp or it’s twist

#

By knowing which was “projected out” you can spot what sign the exp must have been and recover the secret

sonic musk
# 
sage: pos = []
....: for i, l in enumerate(ell):
....:     if P.order() % l != 0:
....:         print("hmm", i) # fail with 12%, restart
....:         continue
....:     Q = P * (P.order() // l)
....:     y = str(Q[1])
....:     if "+" in y:
....:         pos.append(0)
....:     elif "i" in y:
....:         pos.append(1)
....:     else:
....:         pos.append(-1)
....: print(pos)```
string matching ![PI_ThumbsUp](https://cdn.discordapp.com/emojis/703131448361746452.webp?size=128 "PI_ThumbsUp")
quartz kernel
sonic musk
#

oh oops

storm shore
#

isn't the fail rate roughly double that (23%)?

sonic musk
#

uh prod(1-1/l)

#

where does the 2 come from

storm shore
#

prod((1-1/l)^2)

sonic musk
#

don't think so. I just need P.order() % l != 0 right

#

just treat P.order()random 😂

storm shore
#

lemme think a bit. but I think yours might have some false positives (where it doesn't "hmm" but can end up with the wrong answer)

#

because it's not matching up with my intuition. but also my intuition could be completely wrong

sonic musk
#

I think not

#

hmm

sonic musk
#

sry for bad notation phone bad

storm shore
sonic musk
#

And where’s the square coming from? You want both Pa and P0 to have order not divisible by l?

#

Oh hmm. I thought they will have the same order but now I think abt it maybe not

#

(eg kernel points)

storm shore
#

I should probably think in kernel points

sonic musk
#

I sse what you mean but I don’t think so

#

sec

#

ok back on laptop
Say the 4-torsion group is generated by P, Q independently, so 4P = 4Q = 0
And the starting point is P0 = a * P + b * Q or sth

And say your isogeny is phi = (E0 -> Ea := E0 / <P>)
Then the point you receive is Pa = phi(P0) = b * phi(Q) // because phi(P) = 0
(and phi(Q) must have full order, else there'll be a multiple in the kernel <P>)
So as long as b doesn't vanish it's fine, what a is doesn't matter

#

So if your isogeny kernel is the "real direction", then what it is doesn't matter

#

lol

#

only need the imaginary direction to be nonzero

storm shore
#

right, no you're correct in that we can detect an error in about 12% of cases and should restart

#

but assuming you don't restart, then the probability that your recovered a is equal to the original a then fails with a further 12%

#

but there is no way to detect this

#

so overall, only 77% of connections to the remote will result in the flag

#

12% will have "restart" and not submit an input at all

#

the remaining 11% will submit an input and the remote will say "wrong"

hardy mist
#

Didnt know anything about isogeny before, so couldnt solve
But I think the time I had yesterday struggling was worth it, maybe I can solve the next isogeny challenge 🥲

sonic musk
#

hi idol! Yes, I think this is a pretty good intro chal (as in you can learn enough from scratch in two days to solve it)
You should also check out Neobeo's own challenge (the mitm one, I forgot chal name). That one at least gets you familiar with what isogenies are

#

re neobeo, I'll read later, doing assignment 🤡

storm shore
#

here's a horrible mspaint drawing of what the challenge looks like in my head

sonic musk
storm shore
sonic musk
#

This requires bruteforcing isogenies right

#

Like the dual

#

but me and jack’s doesn’t

#

Because the kernel of the dual isogenies are special (they’re the “csidh prime isogenies”)

#

So ours won’t work if the secret vector a is sampled from [-2,2]^42 i think

#

While yours will

storm shore
sonic musk
#

Not exactly

#

I think

storm shore
#

but in any case no, mine doesn't work with [-2,2]. I'm not sure you can detect this in any meaningful way

unkempt cape
#

i think you need a random (p + 1)^n torsion point to detect keys in the range [-n, n]

#

at least for the solutions im aware of

sonic musk
#

ahhhh, my bad

#

Ok I will reply when I can actually talk, and also see experimentally how much % my sol works

storm shore
sonic musk
#

Hi, I can finally look at this lol

hardy mist
#

solved, thanks for the nice challenge🥹
btw I have one question, is it possible to recover (a + randrange(-5, 6) initial action) with just Ea's result?

#

since its EllipticCurve(K, [1, 0]) -> Ea with (a + randrange(-5, 6)), theoretically its possible, but is it efficiently possible without bruteforcing 11^42 or 13^42?

#

Also fun thing I discovered:
action([1, 0, 0, ...]) + action([-1, 0, 0, ...]) moves the curve into different curve, but the j_invariant is the same

storm shore
storm shore
#

but also cryptohack has the wonderful #isogeny-school where you can get better answers from someone who's not noob like me

hardy mist
#

Ah, thanks for the explanation and suggestion!!
I have a long way to goPepe_Excited

sonic musk
sonic musk
storm shore
# sonic musk Hi, I can finally look at this lol

so I think the actual probability of getting the flag (per remote connection) lies somewhere in between both our values. for each prime ℓ:

  • if the key is 1 or -1 (prob ⅔), there is a 1/ℓ chance that the random P₀ is "projected" in a bad direction
  • if the key is 0 (prob ⅓), there is a (2ℓ-1)/ℓ²≈2/ℓ chance that the random P₀ is "projected" in either direction (or both)
sonic musk
#

If key=0 why is it 2/l chance?

#

I actually thought it's 0 chance lol

#

If P is a (F_p^2 : F_p^2 : 1) l-torsion point, and phi is a l-isogeny, then phi(P) should also give a (F_p^2 : F_p^2 : 1) point
I think you can show this because phi is a CSIDH-isogeny, so the eigenvalue is like 1 or -1

#

(My notation means x and y coordinates are both in F_p^2 / F_p lol)

storm shore
#

we can do this by thought experiment (no maths). if the key is 0, then instead of (E0,P0) we move one step to (E1,P1) and consider this to be our new starting point instead

sonic musk
#

Yeah, and say P0 is l-torsion and deg(E0 -> E1 isogeny) is not divisible by l right

#

It's a fact that if P0 doesn't lie on the real axis nor imaginary axis, then P1 doesn't either

storm shore
#

my point is that you cannot distinguish whether you started at P0 or P1. you have to guess, and it's more likely that it started at P0 but it doesn't have to

storm shore
sonic musk
#

Like the setting is E1 = act(E0, [0, xxxxxxx]) right? Is that not what you meant for key=0

storm shore
#

ok, I'm saying compare these two scenarios:

  1. start at (E0, P0, a=[1, xxx])
  2. let (E1,P1) = action(E0,P0,[1,0,...,0]), then start at (E1, P1, a=[0,xxx])
#

they both end up to the same (Ea,Pa)

sonic musk
#

I don't think so

storm shore
#

but if the "actual" starting point was (E1,P1) then we'd get it wrong because we'd actually guess (E0,P0)

sonic musk
#

let (E1,P1) = action(E0,P0,[1,0,...,0]), then start at (E1, P1, a=[0,xxx])
The distribution of P1 won't be uniform on E1

storm shore
#

ok, I agree P1 is not uniform on E1

#

the probability of getting such a P1 is 1/l

sonic musk
#

Sorry I think I'm a bit lost right now

#

We're thinking about this statement right

if the key is 0 (prob ⅓), there is a (2ℓ-1)/ℓ²≈2/ℓ chance that the random P₀ is "projected" in either direction (or both)

storm shore
#

yes

#

I'm saying here that if (E1, P1) was the actual key (i.e. key=0), we would not get it right because P1 is already projected

#

so actual_key = 0, but recovered_key = 1

sonic musk
#

Oh! I think you're right

#

Okay I finally understand

storm shore
#

yeah sorry about all my bad terminology lol. I never learnt this stuff formally

sonic musk
#

So like when it does self.P0 = self.E0.random_point() it might already be on the real or imaginary axis

#

which we'll detect as 1 or -1 even tho it's not

storm shore
#

yup

sonic musk
#

ok yeah makes sense

#

oops

#

btw the real and imaginary axis actually makes sense

storm shore
#

yeah that's how I have it in my head, and it seems to be consistent with everything so 🤷

#

yeah that kinda makes sense I guess. I probably need to read more solve more isogeny ctf challs

lapis gulch
plucky sonnet
#

Me neither, maybe since I'm dumb. Actually I think the most intuitive way is to think of doing the reverse action/dual isogeny and check the order thing.

sonic musk
#

You're not dumb, you just haven't learned it yet Shrug

sonic musk
#

In particular, the section under "Rational Elkies primes" and section 8 basically describes what jack is saying

#

And the Frobenius action I described above is a more laid out explanation

lapis gulch
#

Thank you so much 🙏

sonic musk
#

I think the CSIDH paper (linked) is the easiest to start with, as a "first goal" to understand. The concepts are elementary enough that even if you're new to isogenies, you can just ask and dig around and eventually get through the whole thing

plucky sonnet
#

Indeed, the paper describes everything nicely in high level for someone isogeny beginner like me. Actually, this is a nice challenge, since it mixes CSIDH with a specific point on a curve. I usually just see CSIDH as a group action between curves and this makes me fail to dig into inspect a specific curve point in the scheme. So much to learn.

#

Is there anywhere I can learn and try nice isogeny chals?

sonic musk
#

it's quite a new area so I don't think so. I can suggest Neobeo's isogeny maze (easy)

#

I also have a chal but it's not solvable yet, but it's only because the params are set wrong. You can think about the ideas. I am happy to discuss them, found here (medium)

#

y7 has some challenges for hxp ctf, backed up on ctf.link (click on "scoreboard")
hxp 2022: not csidh (quite hard)
hxp 2021: infinity (medium iirc)

#

m0lecon ctf had a sigiso challenge which is also good intro chal (easy)

sonic musk
#

If not, there won't be isogeny-based crypto - it will just be classical diffie-hellman crypto or its friends

storm shore
#

I suspect we'll start to see more isogeny challenges in CTFs going forward anyway (I have some in the pipeline myself)

sonic musk
#

Hopefully no more "modify castryck-decru/jack-remy's code"

#

I purposely avoided suggesting them above

quartz kernel
#

<P,Q> is our basis for this abelian group (Z/nZ) x (Z/nZ)

#

Once such basis can be thought of as defined by the action of Frobenius (see above messages) or simply “is the y coordinate real or imaginary”

#

When I apply an isogeny phi it sends all the points in its “kernel” to the identity so phi(P) = 0 if P is in the kernel

#

So if I look at some random point K = aP + bQ

#

And the image of K is phi(K) = phi(aP + bQ) = aphi(P) + bphi(Q)

#

If phi kills either the real or imaginary component of the basis this can be seen by looking at the y coordinate of phi(K) as the image will be purely imaginary or real as the other part is projected out

lapis gulch
#

Ahh

lapis gulch
sonic musk
#

(or if it's cyclic)

#

More specifically, (for our setting) every n-torsion point can be written as aP + bQ for n-torsion points P, Q which are linearly independent. This is a consequence of that E[n] (the subgroup of n-torsion points) has group structure Z/m1 x Z/m2, where m1, m2 | n

#

So the 16-torsion points might be like Z/8Z x Z/4Z, and those two directions will give a basis

#

(Set n = |E| to get the full thing) this is shown in Silverman's book

plucky sonnet
plucky sonnet
hardy mist
sonic musk
#

I think using pairing you can show they're equivalent (?) like you can solve dlp

hardy mist
#

Hmm, I gotta study pairing first then

sonic musk
#

You're saying that given R (= aP + bQ, a,b hidden), P, Q, recover aP and bQ right

hardy mist
#

Yeah

#

Hmm, most of the case I've tested with random GF(p^2) and random invariants, most of the case, P's order and Q's order is different

sonic musk
#

Yes

hardy mist
#

That way, it will be done easily I guess

sonic musk
#

Why?

hardy mist
#

mul Q's order and mul Q's order ^ -1 mod P's order

#

that way aP will be left

sonic musk
#

Oh. If all P, Q, R are n-torsion points, then ord(P) | ord(Q) | n

hardy mist
#

Ah really, hmm

sonic musk
#

Silverman

Screenshot_2024-02-05_at_09.42.36.png
#

This is when K is algebraically closed. If not say K=GF(p) then it's a subgroup of ^

hardy mist
#

Idk about torsion points(Things I need to study is exponentially increasing), but I think with random GF(p^2) and random invariants, P's order and Q's order arent dependent to each other

sonic musk
#

How are you generating P and Q?

hardy mist
#

P: E.lift_x(random) until P[1] is in GF(p)

#

Q: the opposite

sonic musk
#

the opposite as in, Q[1] is in GF(p^2) - GF(p)? or wdym

hardy mist
#

when it has form of 12341234432 * i

sonic musk
#

I see ah um

#

Yes those will have independent orders

#

Ah I see what you mean, sorry I got confused

hardy mist
#

I thought P's order and Q's order were always the same but guess not

#

maybe its related to supersingular blah blah

sonic musk
#

nono not in this case

#

You can think of P is on E/F_p because P[0] and P[1] is on GF(p)

hardy mist
#

yeah

sonic musk
#

and Q is on the quadratic twist of it

#

because if you recall, if P[0] is not an x-coordinate on E/F_p, then it is an x-coordinate on its twist

hardy mist
#

Ok, yep

sonic musk
#

Oh wait but the two curves have the same order here Thonk

#

oops

hardy mist
#

yeah maybe thats reason is related to supersingularity (maybe)

quartz kernel
#

But given a basis P,Q you can solve R = aP + bQ on the curve (BSGS) or you can use pairings to move this to Fp^k when the curve has embedding degree k

#

For these curves k = 2, so the pairing trick is particularly efficient

hardy mist
#

if dlp is easy, recovering a from a*phi(P) and phi(P) should be easy
Thats what I thought about dlp part

sonic musk
#

I think there are two parts

  1. For jack's explanation, you don't actually have to recover a and b, it's just theoretical analysis. In theory it just works out
  2. And soon_haari is asking a separate/independent question: Given R = aP + bQ, P, Q, find aP, bQ without dlog
sonic musk
# 
sage: p = random_prime(2^16)
....: a, b = [randrange(p) for _ in range(2)]
....: E = EllipticCurve(GF(p^2), [a, b])
....: Ep = E.change_ring(GF(p))
....: Fp_points = []
....: Fp2_points = []
....: while len(Fp_points) < 5 or len(Fp2_points) < 5:
....:     P = E.lift_x(ZZ(randrange(p)))
....:     if P[1] in GF(p): Fp_points.append(P)
....:     else: Fp2_points.append(P)
....: lcm([P.order() for P in Fp_points]), Ep.order()
....: lcm([Q.order() for Q in Fp2_points]), Ep.quadratic_twist().order()
(16056, 32112) # lhs divides rhs
(16242, 32484) # lhs divides rhs
#

However for supersingular curves, |E / F_q| = |(E / F_q)^t| because trace = 0

hardy mist
#

What is the requirement for curve on GF(p)'s order to be same with its twist?

#

is it iff supersingularity

sonic musk
#

Do you know that |E / F_p| = p + 1 - trace(E)?

hardy mist
#

not reallyPepe_Excited

sonic musk
#

Well there you go. and |(E / F_p)^t| = p + 1 + trace(E)

hardy mist
#

ah!

sonic musk
#

So you're correct, the order of curve and its twist is the same when it's supersingular

#

actually I forgot if it's true when p is prime power, but anyways

hardy mist
#

Ok that solves my question a lot

#

what is trace of E btw?

sonic musk
#

Just think of it as a quantity for now

#

Alternatively, you can define trace(E) := p + 1 - |E / F_p|

#

Defining it correctly is slightly too hard to describe here

hardy mist
#

hmm, alright thanks for telling

sonic musk
#

It is actually called the trace of Frobenius. In Sage you type E.trace_of_frobenius()

#

Again, I recommend reading Silverman's book, "The Arithmetic of Elliptic Curves"

#

it's a math book, so there's some math, but it's worth it to get a proper grasp of the concepts
IMO

quartz kernel