crypto

[blissful cape]

holy wtf

[reef marten]

https://www.cryptoisnotcryptocurrency.com :>

[hexed solar]

: https://cryptoiscryptocurrency.com/

[surreal coral]

How do I ban someone?

[sacred blade]

right click, ban

(cannot be an organizer)

[violet coral]

How come that team has ban immunity?

[upbeat hazel]

we got three types of post-quantum crypto this year

[surreal coral]

1. tall challenges
2. wet challenges
3. fashionable challenges

[scarlet forge]

Moist*

[tawdry forge]

hi, I tried to create a ticket twice but the bot said there was an error. Who can I contact for provably secure?

[plucky solstice]

can you screenshot the error you're getting?

[wary geode]

try again now

[upbeat hazel]

it should work now

[wary geode]

someone was adjusting permissions and disallowed it from making tickets

[tawdry forge]

ok, tnx

[ocean tangle]

why is this the most silent channel

unironically

[cosmic condor]

Is there any issue with the netcat server for the Provably secure chall?

I am not able to connect to it

[upbeat hazel]

works for me

[ocean tangle]

works just fine

probably an issue on your side

[twilit edge]

The PS challs were surprisingly fun

[hoary cedar]

Hi we are trying to solve Provably secure 2 and we have this issue:

1. Encrypt values (works fine)
2. Call decrypt (does not response)
   Does someone have a similar problem or is it at our end?

[sacred blade]

make a ticket

[hoary cedar]

Thank you mb

[lost summit]

n00b here. working through Provably Secure. i got pretty far doing it manually but not through 128 challenges. my assumption is that this needs to be solved programmatically... just wondering if someone might nudge me toward what scripting i should be learning for the problem. maybe pwntools? thanks

[sullen oar]

yes i would recommend pwntools for interacting with most ctf challenges

[lost summit]

thank you. if there is a particularly good tutorial that you recommend for someone new to this, i'd be appreciative, otherwise i'll figure out

[sullen oar]

i would just google some tutorials, or look at crypto problem writeups and mimic their code

you only need a small subset of what it can do for cryptography problems

[lost summit]

sounds good, i'll get to learnin

[plucky solstice]

cryptohack and cryptopals are decent learning/practice resources too

[lost summit]

anyone else in my position, this is good for learning the very basic skill of setting up a harness to interact with the remote challenge: https://www.youtube.com/watch?v=bzVIHp49ECU

[torn snow]

when can we learn from wp

[vernal haven]

yes, i finished it usin pwntools.

[winged oxide]

...

i am confuse

wtf are the intended solutions to the provably secures omg lamo

like one script solved both?

[vernal haven]

provably secure 2 can't use the same script, since we can't do decrypt on provable secure 2.

[distant furnace]

we can actually, but not the same string we encoded

[red moon]

btw, did inversion end up getting a "hint released soon"?

[red moon]

Any script that solves ps2 will solve ps1, but not the other way round

[vernal haven]

any other hints?

[distant furnace]

unfortunately yes... Im trying to see how to cheese ps2

[red moon]

It's not really a hint

[vernal haven]

trying to modify the encoded string, but didn't work for me.. at least so far..

[umbral verge]

Neobeo will solved

[winged oxide]

idk man

like it solved ps1, then it just worked for ps2

[red moon]

Inversion? It's kinda haunting me tbh

[red moon]

Yeah, this isn't too unusual. It just means you found the more general solution

[umbral verge]

[umbral verge]

strong

[umbral verge]

so strong!!!

[summer crest]

vinaigrette is too much code to dig through to understand the formats to implement the solution... 😩

[vernal haven]

About encoding? Or more general than that?

[summer crest]

like the main task here is not to figure out the solution in mathematical terms but to reverse the uncommented code to find out how the public key etc. is encoded or what

[summer crest]

yeah, like e.g. the public key encodes some matrices in GF(256) or GF(16). spent already a while trying to dig through the code to figure out how i go from the unsigned char array this is encoded in to the actual components as elements of GF(256) or GF(16) of those matrices. i am a bit frustrated at the authors of the paper for not properly documenting this.

[red moon]

I don't think we should be discussing specifics before the CTF ends

[summer crest]

i don't think i am discussing the challenge itself, just frustration with the associated code from that paper?

[crimson pollen]

cracked

[supple kestrel]

I feel like ive been a small step from the solution for like 16 hours now so either that no hint is on me or im completely off and someone else made a lot of progress

[umbral verge]

still work on seaside

omg

i'm tooo noob

[ocean tangle]

me crying at rSabin

I am garbage

[vernal haven]

rsabin, only able to create a working script with a fake public key.. still stuck 🥶 🥶

[fathom basalt]

Meanwhile I gave up seaside cuz me dogshit, and now have been stuck on membrane for 6+ hours

[surreal coral]

for inversion, you can optimize the cost of HE matrix multiplication down to a single level

[red moon]

now I have to decide whether I want to sleep, or try to interpret this hint

[crimson pollen]

full solve dicectf crypto could be something

[fathom basalt]

rest is for the weak

[umbral verge]

god

[supple kestrel]

And here i am looking at inversion so much i havent rly properly looked at most other challs

[viral gulch]

WHY DOES THE CONNECTION KEEP CLOSING

I pwn btw

[crimson cape]

each connection should timeout after 30m

[viral gulch]

it doesn't last that long 😭

just 30 secs

[crimson cape]

can you open a ticket?

[viral gulch]

Okay, I opened one

[vernal haven]

were you just waiting and not sending new sendline() command? I think you need to choose new action. Or error might happen if you accidentally send more than 1 line.

[wary geode]

open a ticket for stuff like this

[lost summit]

got it. my bad.

[red moon]

Wanna collab? (at some later point)

[graceful cypress]

i wish i had time to think about inversion

[supple kestrel]

im pretty sure im 1 parameter change away from the solve...

[graceful cypress]

i thought about the matrix diagonal trick with shift and mask by a plaintext

but not sure it would work

[twilit edge]

👉 👈 so what was the proper way of doing rSabin

[supple kestrel]

the algo that needs 4 steps for the error to get small enough only worked for 3 steps, then scaling fucked me up...

[proper night]

^

[full temple]

did you know rotations mess up the values

[waxen valve]

rSabin solver
Steps:
Recover N
Factorizing it
decrypto RSA OAEP using custom decrypt function

[crimson pollen]

What do you mean by proper ?

[supple kestrel]

sure, can you help me debug this

[crimson pollen]

Is there a bypass for rSabin ?

[graceful cypress]

ma Rsabin solve

[full temple]

got 0.05 error in 4 iters.. (at level 9)

[supple kestrel]

i found 3 different ways for rotation not to fuck it up. i could compute the inverse, but with max error ~0.1. with some numeric approximation, needed 1 more iteration and it would work

i never got it to work with 4 iters

[twilit edge]

attempted a timing attack o7

[supple kestrel]

but i got matrix multiplication down to 1 homomorphic mult

[twilit edge]

since for divisors of p-1 and q-1 the nth roots get calc'd quicker

[torpid dove]

another rSabin solve

[graceful cypress]

the nth_root algorithm is awful

Cantor-Zassenhaus is much faster

[full temple]

if you extract single entries, the basic matrix mult works? (1 mult level)

[graceful cypress]

the nth_root never finished on my computer

[supple kestrel]

yep, thatw what i did

[graceful cypress]

(x^17-k).roots() is always intantaneous

[torpid dove]

curious about whats the intended of membrane, it took me tons of LLL....

[supple kestrel]

extraced the same position from all matrices, then could pretend that was a regular matrix to do naive matrix multiplication. but the inverse algo didnt converge fast enough

[waxen valve]

Provable Secure solver
It has a bug fixed in the second version

[supple kestrel]

i have a feeling ill stumble upon the solution when cleaning up that mess of a script

[graceful cypress]

For BBBB I sent a=-1 and seeds 11, 13, 15, b-13, b-11 + Hastad related message

[waxen valve]

Provable Secure 2 solver

[full temple]

I had a formula that worked in numpy but in FHE there were more errors

[supple kestrel]

in numpy it worked for me with error of like 10^-16

this FHE system is a pain to use

[fathom basalt]

solutions for seaside and membrane? 🥲

[supple kestrel]

i was doing random FHE matrix stuff from 5 different papers before thinking of splitting up the matrix entries, but i had inverse algo from the start i think i just need to tweak some scaling for it to work, but dont know where or how

[red moon]

I reduced it to a 100x150 lattice, though I still needed BKZ rather than LLL

[torpid dove]

did you find the private key directly?

my solution works but solving the hidden c vector for each plaintext/ciphertext pair

and solving it by sampling random columns in its left kernel to do LLL 🥲

my horrible solution

[upbeat hazel]

I don't think you can get the private key?

low m should just mean that you can decrypt the ciphertext

[tawdry kite]

what was the sol for the oil and vinegar chall

i didn't get anywhere but it looked like a tuff chall

nvm found defunds writeup we good

[fathom basalt]

is there another solution for membrane?

[tight pine]

I'm wondering how you did this, I was thinking CRT + small_roots, but the polynomial is not gonna be monic

[graceful cypress]

I followed the standard "20 years of attacks on RSA"
multiply by x^2 or x^4 to make everything the same degree
Each (x+pad)^k is monic, the CRT of 1 is 1

but with the 2^128 it also works because you can invert 2^128 modulo N

[fathom basalt]

you can also force exponents to be the same 4 times, with small probability

[graceful cypress]

Also the sage small_roots didn't work, i used defund's coppersmith code

I thought the sage small_roots would always work for univariate polynomials, especially in this case the root is really small

[surreal coral]

Should have used this alg isntead

[graceful cypress]

I liked my seeds because if B is odd, since even exponents are always rejected, it works 100% of time to get 5 small exponents

initially I was sending 11,12,13 but if B is even, the 12 makes server go in infinite loop

[surreal coral]

The soln to inversion is that you can compute the matrix inverse via A^T * (A * A^T)^(-1), which only requires inverting a psd matrix.

all of the iterative algorithms for matrix inverse require eigenvalues st |x - 1| < 1, so they don't work for negative eigenvalues.
this is because of complex analysis reasons: the range of convergence must be a ball that includes 1 but can't include zero

The complex number generalization of the above trick is (A A^dagger) which involves a conjugation operation so the ball doesn't apply

Suitable algorithms for performing the inversion are newton's method and geometric series, but geometric series converges faster

[amber sapphire]

what was provably secure solve

i don't know math

[torpid dove]

how did you find those numbers?
I find a by solving a from f^5(11)=11 and send 11,f(11),f^2(11),f^3(11),f^4(11) as seeds

[graceful cypress]

If you send a=-1, the RNG does: x, b-x, x, b-x, x ...

[torpid dove]

it only works if f(11),f^2(11),f^3(11),f^4(11) are even, so need a lot of bruteforce

[surreal coral]

why is a 14 yo child trying to start drama

[amber sapphire]

I don't start drama

I want to be friends with everyone

[main tulip]

😂

[amber sapphire]

I am a very extroverted person!

[fathom basalt]

same here

[amber sapphire]

oh this is a good opportunity for sudoBash418 to tell me what the solve to Provably Secure was

[chrome light]

basically you can just decrypt the message you get and send two unique messages

you'll know whcih one it was so that's the value of mbit

[amber sapphire]

what do all the funny math words and acronyms mean

what even is math

[main tulip]

one minute I'll send my script

[chrome light]

sniped

[amber sapphire]

congrats

[torpid dove]

a bonus about this solution is that it works on the original chall BBB too, because I also solved that one this way 😅

[full temple]

it works but need to set epsilon (at least for e=11 worked with epsilon=1/32 I think)

[main tulip]

dang that's shorter than mine lol

[amber sapphire]

so it's known plaintext attack?

[main tulip]

oh wait

that's ps not ps2

[chrome light]

essentially

[surreal coral]

https://eprint.iacr.org/2016/421.pdf

[chrome light]

ps2 is about the same

[main tulip]

yeah that might as well be my script lol

[chrome light]

u frankenstein two cts

[main tulip]

swap the halves

then decrypt and check if they match (m_bit == 0) or they don't (m_bit == 1)

[chrome light]

r1 r1^m1
r2 r2^m2

e(r1) e(r1^m1)
e(r2) e(r2^m2)

d1 = r1^r2^m2
d2 = r1^r2^m1

if m2 == m1 => d1 == d2 => mbit is 0
else: mbit is 1

basically what happens

[graceful cypress]

Is it equivalent to NEwton's method for inverse ?

[surreal coral]

Nope

[amber sapphire]

i have no idea how that leads to the flag

[surreal coral]

It's got its own name

[amber sapphire]

the flag is a number?

[main tulip]

no

[surreal coral]

It's literally the geometric series, lemme find a link

[main tulip]

the flag is your reward for guessing 128 bits correctly

[chrome light]

wait btw what paper is this from

[amber sapphire]

oh

I thought the flag was the ciphertext

and you had to decrypt

[main tulip]

nope

[surreal coral]

The one I linked

[chrome light]

oh

[amber sapphire]

this is what I get for failing to read challenge source

[chrome light]

i have to use my eyes

[amber sapphire]

what was the solve for funny SSH chall

brute force timestamps?

or was the prng broken

[graceful cypress]

hum, okay, I thought the newton method for inverse could be rewritten as this kind of infinite product, but I may be confusing with something else

[surreal coral]

https://en.m.wikipedia.org/wiki/Neumann_series#Approximate_matrix_inversion

It converges faster than newtons

[chrome light]

wtf happened to wikipedia embeds

[amber sapphire]

latex moment

why does everything on my screen look so bright

and yellow

wait even irl things look so white and yellow

am I jaundiced

[surreal coral]

What was your alg? The fhe params were pretty low precision

[red moon]

I think my solution was more or less the same as yours, but with a couple differences:

• I added an additional weight column for the solution row
• I didn't have to sample randomly; I just took the left 150 columns with BKZ, worked everytime apparently (wasn't working with LLL, but maybe that's what you're seeing and you need to sample randomly)

[surreal coral]

That's the intended solution. The main idea is that you don't have to use the entire vector in constructing your lattice

[surreal coral]

I assume you used either newton's method or you used the geometric series algorithm.

An important optimization for the latter is by how much do you rescale the matrix before computing the inverse

Intended solution is geometric series + rescaling

[torpid dove]

the reason I sample column randomly is because the output isn't always the expected one, perhaps BKZ works better in this case

[red moon]

yeah when I used LLL I often got results that weren't {0,+-1}, so I can see how you went about with your train of thought. I was lucky enough to just try BKZ and it just worked (actually I learnt this from you from your writeup of SEETF neutrality 😅 ), so I didn't explore other options

[red moon]

hm actually no that wasn't yours. probably a different writeup

[fathom basalt]

how come the desired "error vector" is uniquely described by a partial number of vectors?

[torpid dove]

maybe I really should use BKZ more oftenly, I didn't even try that because LLL basically works too and I thought BKZ is too slow

[misty glen]

hi math nerds, anyone wanna help me with my numerical methods hw

[full temple]

for me GramSchmidt was the slowest part (needed for CVP)

[red moon]

am I the only one who prefers kannan embedding over babai

[supple kestrel]

Ask @surreal coral , we all failed his numerical methods test

[misty glen]

💀

[surreal coral]

fyi I use they/them pronouns, as is written in my bio

[misty glen]

im implementing least-squares

[full temple]

I used to like the "wrong" kannan (with huge embedding factor so that you just have to look at the last LLL vector)

[misty glen]

and uh how does one implement least squares for specifically a second degree polynomial without finding RREF

😭

[fathom basalt]

maybe there is some combinatoric argument that can be made? something like probability of a vector in a vector space of dim n belonging in a subspace of dim k<n

[red moon]

yup, that's my preferred one as well. though if you say "used to" then you're probably ahead of me and I will learn in due time that it's bad

[supple kestrel]

Sry, dont usually read bios

[full temple]

It was Newton's method. I hadn't consider rescaling (it helps with FHE errors or with the stability itself?). A big problem I noticed is that rotations mess up the values (e.g. repeating a <<1 >> 1 consistently grows by ~1%). And I used lots of them (every matrix mult.).

[surreal coral]

Ah, I only rotated the values at the very first step so I never noticed.

The scaling helps the (non he) accuracy

[full temple]

Just with the right tuning of the embedding factor you'll get the answer in the shortest vector (which has better bound). Figuring it out is pain so I tend to use Babai (but then GramSchmidt is slow...).

[surreal coral]

Using the geometric series to compute inverses in ckks was proposed in the original heaan paper

[bleak warren]

The idea behind my BBBB solution:

• an LCG is a permutation
• solve for a such that the permutation will have a 5-cycle that includes 11
• set the seeds to be elements of the 5-cycle
• probability of getting atleast 3/5 outputs to be 11 is high enough
• Find m using hastad linear padding attack

I will post a full writeup in ~tuesday

[red moon]

Pretty much identical to mine, except I used a 4-cycle (and one random throwaway value)

[graceful cypress]

and 2-cycle here 🤡

[bleak warren]

lol how did that work

[graceful cypress]

i used degrees 11 and 13 and 15 (see above)

[bleak warren]

Ah, I see

makes sense

[analog stump]

(i rushed and forgot to check bounds on how many samples were required for coppersmith to work), but yeah, intended was pretty much as you described

[bleak warren]

Wish I had time to solve more challenges

[summer crest]

i did it like that as well, did it actually work with 3 ouputs being 11 for you? for me it failed for 3 usually, but i just let it run while i went for a run in the park and when i got back it got it with 5 of the values being 11. perhaps i did not set up the hastad stuff completely correctly

[bleak warren]

btw, for the web-csp I did a really efficient methkd

lemmd send my TL;DR writeup

[graceful cypress]

I had also some troubles with 3 values, this is why i went for 5 values with 100% success

[bleak warren]

the epsilon value is very important

default does not work, too small is too slow

I used epsilon=1/25

[summer crest]

why did you choose that particular value?

[red moon]

Haha, exactly what I used as well

I mean I really just went down from 0.1 in decrements of 0.01

[summer crest]

is epsilon used when you explicitly set X and beta?

i did something like this:

    bound = 2**(8*(50+4))
    solutions = g.small_roots(X=bound, beta=1/len(n))

(the documentation sounded like epsilon is used in setting the bound X if an explicit one isn't passed)

[graceful cypress]

this is why i often prefer defund's script, it takes integral parameters so you can't be adjusting things by 0.0001 steps

[summer crest]

what do you mean by defund's script?

[analog stump]

https://github.com/defund/coppersmith

[bleak warren]

Meme method to solve the first web challenge (NOTE: this explanation was written at 4AM, not cleaned up!)

can you remove the message then send again?

I want my 3 messages to be next to each other

Thanks 😄

[graceful cypress]

i thought you had finished
i posted my script here
#web message

i added light bruteforce to get a printable crc (easier to copypaste)

[bleak warren]

Actually I will post an explanation in my writeup once it's ready instead

deleted for now

[amber sapphire]

wait so Provably Secure is Python pwn?

[chrome light]

no?

[amber sapphire]

so yes

I see

or is it some kind of

known plaintext attack

[chrome light]

its simply using an oracle as intended

[amber sapphire]

what

[reef marten]

Provably Secure 1 was jyu accidently added .hex() when checking if the ct you were trying to decrypt was a ct you recieved

so you would pass m0 and m1 (then depending on the mbit one would be encrypted), then you could copy the ct and decrypt it to see what it decrypted to, then if it was m0 then mbit was 0, else 1

[amber sapphire]

what

oh so the check doesn't work?

[reef marten]

ye

Provable Secure 2 the check worked, but since it was 2 ciphertexts concatenated, you could encrypt m0,m1 and m0,m2 for some random m0,m1,m2, to get ct0 and ct1, then split both cts in half (since the enc was 2 rsa encryptions concatenated), to get ct01, ct02, ct11, ct12, then try decrypting ct01 || ct12 and ct11 || ct02, then if those 2 were equal then it mbit was 1 (as m0 was selected for both encryptions), else mbit was 1 (as m1/m2 were selected and those are not the same)
That works cuz c02 and c12 were encrypted by the same pk, and if m0 is chosen then are encryptions of the same msg

[amber sapphire]

so it was math trolling

well basically that's all crypto is

but

it seems similar in idea to AES bit flip trolling

[torn snow]

I do not understand PC2

[tranquil bolt]

Given:
Enc(msg)    = E(r, k0), E(msg ^ r, k1)
D(ct0, ct1) = D(ct0, k0) ^ D(ct1, k1) = r ^ msg ^ r = msg

Encrypt the msg 3 times
Enc(msg) = ct0_0, ct0_1
Enc(msg) = ct1_0, ct1_1
Enc(msg) = ct2_0, ct2_2

Then query decryption
D1 = Decrypt(ct1_0, ct0_1) = r_1 ^ r_0 ^ msg
D2 = Decrypt(ct2_0, ct0_1) = r_2 ^ r_0 ^ msg
D3 = Decrypt(ct1_0, ct2_1) = r_1 ^ r_2 ^ msg
And then use
D1 ^ D2 ^ D3 = r_1 ^ r_0 ^ msg ^ r_2 ^ r_0 ^ msg ^ r_1 ^ r_2 ^ msg = msg

[torn snow]

@tranquil boltthanks

[chrome light]

u can also do one in 2 encrypts 2 decrypts

r is random, m is decided by us
internal states (we dont get these)
r1 r1^ma (chosen from m0, m1 we supplied)
r2 r2^mb (chosen from m0, m2 we supplied)

encryption oracle (we DO get these): 
e(r1) e(r1^ma)
e(r2) e(r2^mb)

decryption oracle:
d(e(r1), e(r2^mb)) = r1^r2^mb
d(e(r2), e(r1^ma)) = r1^r2^ma

if d1 == d2, then ma must equal mb, so the two chosen messages were the same, which means m_bit must be 0 as m0 was chosen both times
otherwise m_bit is 1

[torn snow]

amazing

[red moon]

there's also a 0 encrypt 1 decrypt solution

[chrome light]

[red moon]

you have the the public key parameters, so just encrypt it locally (it's not a remote request so I didn't count it!)

[chrome light]

oh lol

[sacred blade]

It was intended to be an easier challenge with multiple valid solutions

Though I'm not sure if 1 decrypt is enough. The professor's example solution on the final exam key used 2 decrypts

[tranquil bolt]

How do you distinguish with 1 decrypt/encrypting locally

[chrome light]

wait this was a real class

[sacred blade]

Yeah lol

[chrome light]

what class lmao

[sacred blade]

Graduate cryptography

And I did screw up that question on the exam

[chrome light]

💀

[sacred blade]

By making an erroneous proof

That I'll be including in my official writeup

[red moon]

Nvm, I think you're probably right and I screwed it up. I solved it with 2 encrypts and 2 decrypts, but was just thinking that we could do some stuff locally but maybe not

[turbid acorn]

Deadass, the provably secure ones were actual questions for my crypto homework lmao

[vernal haven]

wow, I haven't think about this, I was thinking about guessing the r / rprime. Good logic. I think I need to save this one

[winged oxide]

I did that for the first one, and the second one. what was ps1 intended solution?

[crimson pollen]

ps1 intended solution was probably ps2 solution

[floral pike]

Writeup for BBBB: https://github.com/pcw109550/write-up/tree/master/2023/Dice/BBBB

[cosmic helm]

if factorising N is possible, why still bother to do the 17th root of the encrypted flag? is it not possible to decrypt with p and q?

[graceful cypress]

It's not, because you cannot invert 17 modulo (p-1)(q-1)

[cosmic helm]

if p and q is randomly genrated by getPrime, there must be a run where 17 does not divide p-1 and q-1.

[graceful cypress]

in that case the factorisation doesn't work

my script needs 17 to divide one of p-1 q-1 (not both)

[cosmic helm]

ok, thanks

[red moon]

it's interesting that the csidh modulus (5326738796327623094747867617954605554069371494832722337612446642054009560026576537626892113026381253624626941643949444792662881241621373288942880288065659) does not show up on a google search. I mean it does now, but only for a DiceCTF2023 writeup

[twin iris]

I guess it's because none of the CSIDH impl write it out

either it'll be encoded with a bunch of fixed limbs for constant time

or you might like to see p+1 as its factors 🙂

2^2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173 * 179 * 181 * 191 * 193 * 197 * 199 * 211 * 223 * 227 * 229 * 233 * 239 * 241 * 251 * 257 * 263 * 269 * 271 * 277 * 281 * 283 * 293 * 307 * 311 * 313 * 317 * 331 * 337 * 347 * 349 * 353 * 359 * 367 * 373 * 587

[crimson pollen]

smoothest smooth number

[twin iris]

2^1000000000000000000000000000000000000000000000000000000000000000000000000000000 would like to have a word

[crimson pollen]

Try to use it in a cryptosystem

[graceful cypress]

It certainly has more than a word

[crimson pollen]

Might be a sentence at this point

[ionic magnet]

Wrong type of crypto

[compact jacinth]

was it a crypto scam bot

[sacred blade]

yes

[upbeat hazel]

🤖

[crimson pollen]

Always wondering how you find so much good ideas

[upbeat hazel]

work on dicenet 🥺

[crimson pollen]

Ok, not sure this one was a good idea

But love on you

[wary wigeon]

hehe

retained my I5oG3Ny_W1z4rD title

[upbeat hazel]

🤖

[wary wigeon]

🎲

(I'm gambler that's why I have so many dice)

[wary wigeon]

@upbeat hazel how close are we

[upbeat hazel]

uh

do you know the bug

[wary wigeon]

no

no it's just a joke lm,fao

not related to chal

[upbeat hazel]

😭

i want a solve so badly

[wary wigeon]

i'm trying

trust

isogeny getting 3 solves so far is surprising tho xD

[turbid acorn]

Oh hey! I know the team at the end! 😄 Rosulek pogchamp

[wary wigeon]

[turbid acorn]

Fellow Rustacean in the wild!!! 😎

[wary wigeon]

I'm barely one lol

[turbid acorn]

And chad garbled circuits enjoyer

[wary wigeon]

Used Rust for advent of code, then forgot half of how borrow checker works

[turbid acorn]

Such a mood ngl

[wary wigeon]

At least it's not javascript

ok maybe that's a low bar

[turbid acorn]

I made a game engine, signal clone, and most of an OS in it and I still forget and google rust borrow checking 💀

[wary wigeon]

CS student spotted?

[turbid acorn]

Correction: Ex CS student hehe, finally graduated 😎

[wary wigeon]

Everyone is forever a student 😄

[turbid acorn]

I would like to defend myself and say that most of these were for fun or stupidly out of scope projects though x3

[turbid acorn]

Ur so right though 😂

[turbid acorn]

That's a depressingly low bar

;-;

[wary wigeon]

2pac

[turbid acorn]

My favorite is some disk util where the error is FSCKTHIS::bit_ch, cuz it's writing bits from a channel 😂

[solemn wolf]

NEEEERDS!

😉

[vernal crater]

Looks super cool, hoping to give it a few hours tonight.

Would be easier to rally the troops if the ctf wasnt just before Crypto deadline T.T

[bitter junco]

Hey

Why is the winternitz one so hard

Skill issue?

[wary urchin]

bruh I know how to do it

still unable to 😢

[austere anchor]

Am I causing too much traffic on rps-casino rn. I think my solve is bad but I did narrow the search space pretty heavily so I'm seeing if it works

[woeful otter]

What is the server timeout for rps-casino ?

[crimson cape]

20 seconds

[wary wigeon]

So why is the timeout for pee-side 90 minutes

[upbeat hazel]

mistake

[turbid acorn]

aw man, my script took exactly 91 minutes 😦 (/s)

[wary wigeon]

what team are u in

[turbid acorn]

osusec, im not a crypto dude though x3

[wary wigeon]

oh haha

[daring dagger]

mine takes 9001 centiminutes

[turbid acorn]

aight, in 30 seconds I wanna see the solution to winter, is there just some script online that does it all for u? XD

[next jetty]

casino please

[woeful otter]

z3

[next jetty]

i brute forced 2 sorted hashes

[next jetty]

took like 2 hours 👍

[next jetty]

z3 deez nuts

the how do

[turbid acorn]

wait whats a sorted hash lmao

[hexed marsh]

i lack patience

[next jetty]

well not sorted sorted

[next jetty]

like first byte in first hash is less than first byte in second, second byte in first less than second bytes in second and so on

[next jetty]

how did u do it?

[hexed marsh]

plis dont tell me that was the intended solution

[hexed marsh]

i didnt 🗿

[wary wigeon]

The vuln for winter is that it doesn't have checksum

[next jetty]

yup

[wary wigeon]

So just find two messages m1, m2 such that their hashes h1, h2 satisfy h1[i] < h2[i] for all i

Then forge signature

[hexed marsh]

yes how do u find those hashes ??

[wary wigeon]

bruteforce

[serene condor]

I used bitcoin hashes

[wary wigeon]

It happens with ~2^-31 anyways

[serene condor]

https://sylvainpelissier.gitlab.io/posts/2024-02-04-dicectf-winter/

[next jetty]

ha

[woeful otter]

inversion solution?

[wary wigeon]

https://ibm.github.io/helayers/reference/gen_pages/FunctionEvaluator.html

[next jetty]

thats really cool actually

[wary wigeon]

Another method:

In [57]: n = 2**20
    ...: x = np.random.uniform(-1, 1, n)
    ...: x = np.copysign(np.abs(x) + 0.4, x)
    ...: y = 1 / x
    ...: 
    ...: deg = 12
    ...: coef = np.polyfit(x, y, deg)
    ...: max(abs(np.polyval(coef, x) - y))
Out[57]: 0.224199649413253```
Literally interpolate a degree 12 polynomial, then its error is small enough

[somber grotto]

what about rps-casinno??

who solved it?

[oak wind]

Z3

[mortal night]

We solved rps

[next jetty]

➕

[crimson pollen]

any solve for pee-side ?

[violet birch]

How to shor?

[wary wigeon]

yes!

sec

[vast pollen]

What was the purpose of ssh connection in yaonet?(except for it's giving the flag back obviously)

[fading minnow]

you can also generate the two first input from full scratch

[wary wigeon]

@upbeat hazel can you make some threads

[somber grotto]

meaning?

[oak wind]

Z3?

[upbeat hazel]

you can't?

pee-side thread

[wary wigeon]

nope

can't pee

thanks

[wary geode]

uh huh

[somber grotto]

??

[vast pollen]

it's an smt solver. Usefull stuff

[next jetty]

he means how did you set up the equations

it was the first thing i tried

but i think i got them wrong

[oak wind]

lshr instead of >>

[vernal pollen]

what is the solution for iinversion, we got quite close but needed a few more multiplications in the end

[waxen valve]

does this really work ?? how you chose the bounds and resolution ?

[wary wigeon]

The inversion only works when the encrypted numbers are positive, so I first used a sgn with (f, g) = (1, 0) (one degree-7 polynomial approximation), then used inversion

or inverse I forgot

[gleaming glade]

yeah it works but only for inversion not iinversion

what is the iinversion trick ?

[waxen valve]

ow how i missed that .. spent some time on implementing approximation

[serene condor]

h_1 is the hash of m1

[daring dagger]

i think iinversion is doable if u abuse the 50 bit precision to zero out values and use that to scale low values into higher ones

[gleaming glade]

oh, how would you do that ?

[daring dagger]

smth smth scalar mult by 2^-49

[vernal pollen]

Our, failing, approach to iinversion was this. Multiplying with constants doesn't change the chain index so we rescale: y = g(2 * x^2) * 2 * x, where g is the geometric series (with q = 1 - x). By efficient evaluation we can evaluate the geometric series for the first 2^k terms with a multiplication depth of k. Sadly, to achieve the needed threshold we need 15 instead of the allowed 12 multiplications. Interestingly, this was also the max depth the library would accept as valid when creating a new context with the other params fixed 🤔

[daring dagger]

(i didnt implement, but the idea behind it is to do two low precision taylor series, one to get scale factors to make the low values closer to 1, and one to compute the inversion)

i think this should work?

[wary wigeon]

The library works with 13 multiplication depth

[vernal pollen]

what about the sign

the geometric only requires 13 i know, but it only converges for the positive interval

[brazen wave]

CASINO! chance 1 in 5 and sorry for the code, finished 5 minutes before the end

def setxor(st, ml):
    state = int(st + ml ,2)
    for i in range(4):
        bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
        state = (state >> 1) | (bit << 63) 
    el= bin(state)[2:].rjust(64, "0")[:4]
    return el

def getSM(st, ml, check):
    resm = []
    ress = []
    for b0 in st:
        for b1 in ml:
            state = int(b0 + b1 ,2)
            for i in range(4):
                bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
                state = (state >> 1) | (bit << 63) 
            el= bin(state)[2:].rjust(64, "0")[:4]
            if el in check:
                resm.append(b1)
                ress.append(b0)
    return sorted(list(set(ress))), sorted(list(set(resm)))

io = start()
lose = b'You lose!\n'  
win = b'You win!\n'  
tie = b'Tie!\n'
a0 = ["0000", "0011" , "0110", "1001", "1100", "1111"]  #0  rock
a1 = ["0001", "0100" , "0111", "1010", "1101"]          #1  paper
a2 = ["0010", "0101" , "1000", "1011", "1110"]          #2  sciccor     

vari = []

for i in range(56):
    io.recvuntil(b'Choose rock, paper, or scissors: ')
    io.sendline(b'rock')
    result = io.recvline() 
    if tie in result:
        vari.append(a0)
    elif lose in result:
        vari.append(a1)
    elif win in result:
        vari.append(a2)

#print(*vari, "\n", sep="\n")

for _ in range(100):
    for i in range(16, 56):
        vari[i-15], vari[i-16] = getSM(vari[i-15], vari[i-16], vari[i])
        if len(vari[i-15])==1 and len(vari[i-16])==1:
            vari[i] = [setxor(vari[i-15][0],vari[i-16][0] )]

print(*vari, "\n", sep="\n")

answer = []

for i in vari:
    answer.append(i[0])

for i in range(50):
    e = setxor(answer[-15], answer[-16])
    answer.append(e)   
    print(i, e, i-15, i-16)
    io.recvuntil(b'Choose rock, paper, or scissors: ')
    if answer[-1] in a0: 
        io.sendline(b'paper')
    elif answer[-1] in a1: 
        io.sendline(b'scissors')
    elif answer[-1] in a2: 
        io.sendline(b'rock')

io.interactive()

[cursive anvil]

https://connor-mccartney.github.io/cryptography/ecc/yaonet-DiceCTF-2024

[next jetty]

best writeups ive ever seen

[wary wigeon]

i didn't look at yaonet but is it jus bsgs/mitm/sth

I put my pseudo-sol for dicenet and pee-side at #writeups

[violet birch]

🥲

[fallow gale]

wonderful. ty

[wary wigeon]

find hash for winter

[upbeat hazel]

@surreal coral how to shor?

[wary wigeon]

How close is my dicenet defund

Or am I looking at the wrong gate

[upbeat hazel]

wdym

this is right: #writeups message

[wary wigeon]

💤

[upbeat hazel]

there's more to do ofc, but that's the core bug

do you wanna see sol code

[wary wigeon]

no

[upbeat hazel]

o

[wary wigeon]

I'll impl it

After I finish my project due in uh

hours

[upbeat hazel]

looking forward to it!

[wary wigeon]

Also this is the second week I clutch solution at the end of the ctf

Last week I also got the solution to TetCTF preimage in like the last 4 hours, but that one I implemented successfully

(frozen heart-like vuln)

[supple kestrel]

pls tell me intended for iinversion isnt this paper. been looking at it for hours but notation beat me

[wary wigeon]

I think not, I don't think you can interpolate iinversion with a "direct" polynomial ?

In [59]: n = 2**20
    ...: offset = 0.02
    ...: x = np.random.uniform(-1, 1, n)
    ...: x = np.copysign(np.abs(x) + offset, x) / (1 + offset)
    ...: y = 1 / x
    ...: 
    ...: deg = 64
    ...: coef = np.polyfit(x, y, deg)
    ...: max(abs(np.polyval(coef, x) - y))
Out[59]: 44.78878103156755

[spiral narwhal]

i used mathematica to optimize the integral of the squared difference and i think the result was too bad for a solution to exist in L_infinity
found some information on how to compute an exact solution via sum of squares programming (???) but decided it's not worth the time

[wary wigeon]

I think the solution requires some composition

http://ccl.snu.ac.kr/papers/journal_int/journal2021_8.pdf

[spiral narwhal]

how is it possible for this to be better than applying a polynomial directly? does it help bypass the multiplication depth limit?

[wary wigeon]

Yes that's what I think

And also it's exactly like newton-raphson, which has doubly exponential convergence

In fact I tried Newton-Raphson, but it converges too slow for the boundary values. It works here since f(x)=1/x -> f'(x)=-1/x^2 and after substituting the Newton-Raphson formula doesn't require division

[supple kestrel]

the title of the paper is the exact problem we have tho. idk what numpy is using, but there are many different way to polyfit

[wary wigeon]

least-square i think

[supple kestrel]

you should be able to get to degree 2^12 poly, not bypassing that tho

[wary wigeon]

hm

[spiral narwhal]

so the multiplication depth limit is based on number of multiplications and not the actual degree?

[supple kestrel]

should be i think

[wary wigeon]

Yeah

And you can do binexp or whatever

[deep sedge]

https://heaan.it/docs/stat/python/core.html#heaan_sdk.block.Block.sign there's also this updated api (since the one i found on github is from like 2016)

their sign/inverse funcs seem to be different

though the actual helayers says it uses this in the backend, but who knows what that means

[wary wigeon]

Like it calls this

[somber basin]

Anyone for iinversion? We at least had some idea, but gave up after seeing it does multiplications like (1.27 * 10^-7)^2 = 62.3

[wary wigeon]

Ah sorry

Iterations/composition is just faster

But it shouldn’t be theoretically best at all

mb

[deep sedge]

only blue water solved it and author didn't say anything yet, also curious on intended

[somber basin]

Also in yaonet, the repeated 4 byte doesnt matter? I thought it might be front 4 byte hash of something

[reef marten]

pls chall author

[cursive anvil]

What bytes?

[somber basin]

idk how to explain, but check_int_1 and check_int_2 in the codeblock

    "decipher_bytes_header": {
        "check_int_1": 488100094,
        "check_int_2": 488100094
    },
    "decipher_padding": "b'\\x01\\x02'"
}

[surreal coral]

idea for iinversion:
evaluating high degree polynomials directly is numerically unstable in FHE. Express them in a chebyshev basis instead. https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/FUNCTION_EVALUATION.md

I used linear opti to find a 59-degree chebyshev poly which minimizes the relative error to 1/x over the input range. Could use like least squares to find the poly instead.

Then finished up with two iterations of newton's method, which gets use 10x lower than the required error threshold.

[cursive anvil]

Ah, no the checkints or comment don’t have to match the server key

[wary wigeon]

Wait, so you use a relatively low degree polynomial PLUS newton-raphson?

that's so genious

[red moon]

I think many of us were trying this in various forms, it's just chebyshev that we missed

[wary wigeon]

Huh, that part is actually most obvious to me

Maybe because someone gave their second year essay talk on interpolation and mentioned this so I learned it then

[surreal coral]

yup. the usual approach for division in HE is newton-raphson. Chebyshev polys are mostly applied to approximation neural net activation functions
Point of iinversion is that the generic poly methods actually substantially outperform newton-raphson

you can also do it entirely with a 495 degree cheby poly and no newtons method (and have 2 levels to spare) but like I can't even count that high that sounds excessive

[red moon]

as others have mentioned, any pair of hashes has a 2^-31 chance of one dominating the other. so just compute all 2-byte hashes, and heuristically there'll be a dominating pair. in this case A8C1 and 04A4 provide such a pair:

>>> sha256(b'\xa8\xc1').hexdigest(); sha256(b'\x04\xa4').hexdigest()
'48538b629ad8539ec56267041c759e0d0f0d8bbb080a2140530eb3724422370d'
'ddcdc0d8c0e868eff387845f5792be8791eb93e24f4e95a3dfacd3ddd4e6b058'

[red moon]

but more importantly @surreal coral, how to shor?

[wary wigeon]

Hmm, I can't seem to replicate

In [47]: import numpy as np
    ...: import numpy.polynomial.chebyshev as C
    ...: 
    ...: n = 2**16
    ...: offset = 0.02
    ...: x = np.random.uniform(-1, 1, n)
    ...: x = np.copysign(np.abs(x) + offset, x) / (1 + offset)
    ...: y = 1 / x
    ...: 
    ...: # approximate
    ...: deg = 32
    ...: coefs = C.chebfit(x, y, deg)
    ...: evals = C.chebval(x, coefs)
    ...: 
    ...: # f(x) = 1 / x - D, f'(x) = -1 / x^2
    ...: # Newton-Raphson: x1 = x0 * (2 - D * x0)
    ...: for _ in range(4):
    ...:     evals = evals * (2 - x * evals)
    ...: 
    ...: delta = np.abs(evals - y)
    ...: print(np.argmax(evals))
    ...: print(np.min(delta), np.max(delta))
3718
0.0 208142663509.07803

It seems that Chebyshev polys are very numerically unstable at the edge or sth? or is it newton-raphson hmm

[surreal coral]

yah the chebyshev polys are p rapidly oscillating at the edge
so instead of uniformly random points
try like np.logspace
also would suggest like degree=120

[wary wigeon]

Ohh right. I remember something about that. Let me try

In [98]: import numpy as np
    ...: import numpy.polynomial.chebyshev as C
    ...: 
    ...: n = 2**16
    ...: offset = 0.02
    ...: # Interpolate on Chebyshev points (of the first kind)
    ...: x = C.chebpts2(n)
    ...: x = np.copysign(np.abs(x) + offset, x) / (1 + offset)
    ...: y = 1 / x
    ...: 
    ...: # approximate
    ...: deg = 255
    ...: coefs = C.chebfit(x, y, deg)
    ...: 
    ...: # Test on random data instead
    ...: x = np.random.uniform(-1, 1, n)
    ...: x = np.copysign(np.abs(x) + offset, x) / (1 + offset)
    ...: y = 1 / x
    ...: 
    ...: # Evaluate, then Newton-Raphson
    ...: evals = C.chebval(x, coefs)
    ...: for _ in range(3):
    ...:     evals = evals * (2 - x * evals)
    ...: 
    ...: delta = np.abs(evals - y)
    ...: print(np.argmax(evals))
    ...: print(np.min(delta), np.max(delta))
24382
0.0 1.3081091765343444e-11

oof

[supple kestrel]

Ive been looking at chebyshev all day but didnt know what to do with it

[wary wigeon]

Yeah, that should work ^

Newton-Raphson is degree 2 so requires one depth. chebyshev poly is degree 63, so it requires 10 depths ((^1 for free), ^2,^4,^8,^16,^32 then multiply them all)

So it should fit

oof.

Actually I'm running too many Newton-Raphson lol, but something like that I guess?

[surreal coral]

with the bin tree approach to evaluating cheby, you get a slightly lower max degree (59 vs 63) but exact same principle otherwise. main thing about cheby is that evaluating them is quite numerically stable

[wary wigeon]

That sounds smart, which is not me. I think numpy just do least-square best fit

oh look, you can read my blog on that

[digital thistle]

ok I just joined here

was there any discussion/writeup on measurement error

I’m just curious what the intended sol is

@surreal coral are you still up?

[digital thistle]

oh also other ppl asked

[wary wigeon]

afaik no solutions yet

[digital thistle]

I was wondering, is it even possible to use lattice methods cuz whatever xors can be expressed as sum of +-2^k values

but the lattice is already super big

it would be fun if there was a paper about removing measurement errors with a non-quantum algorithm

also I believe my teammate JOHNKRAM solved iinversion described as above, but he never shared his sol in our discord server

[supple kestrel]

every paper i found said that the problem is unsolvable if theres noise left after quantum error correction not ideal

[vocal frost]

my script tooks like 5-30 secs

still do compare all hash of msg2 < hash of msg1, but at the first time generate msg1, i try to create one such satisfied all of the element bigger than something between hash of msg1 and hash of msg2

def find_msg():
    while True:
        msg = os.urandom(32)
        ls = list(hash(msg, 1))
        if all(i >= 100 for i in ls):
            break

    while True:
        m = os.urandom(32)
        cand = list(hash(m, 1))
        #print(cand)
        if check(cand, ls):
            print("FOUND WITH m =", m)
            print(cand)
            break
    
    return msg, ls, m, cand

[turbid acorn]

drop the script

O pog

[vocal frost]

sth like this, the check function is just comparing them

[humble lake]

seems my solution is unintended

just newton's method. adjust the polynomial after first several iterations

start from f(x)=x

find a k1 to add k1*(x-x^3) after the first iteration

for the 2nd, k2*(x-x^3-x^5+x^7)

k3*(x-x^3-x^5+x^7-x^9+x^11-x^13+x^15)

and it seems to be small enough now

just guess, with some luck

anyway, so where is the sol for shor

[untold locust]

this writeup was very helpful.
I have a question.
Why
"We can also add the header 00000020 immediately after the second pubkey, and then the following 64 hex chars should represent d." ?
It is 00000021 with your dummy key.

[cursive anvil]

Good question

I’m not sure why

I can test with some more dummys, sometimes it’s one sometimes it’s the other

[white sapphire]

i like how MITM works so well especially due to the distributive nature of ECC scalar mul over ECC add

[untold locust]

thank you I'll look it up more.

[shy galleon]

i did similar but used https://beneri.se/hashgame/ (bytesum_min is exactly what we're looking for- a hash where all of its bytes are very low)

[cursive anvil]

a guess is the source does smth like this

sage: d2 = 0x455389dfb3ccae87f774d0a97aec2c494ba96da521dfffbbf9e0e7447fb7c9fe
sage: d1 = 61058868839081846412682869945227768869718126500541418541339379651273527212978

sage: f"{ceil(log(d1, 2))//8+1:x}"
'21'
sage: f"{ceil(log(d2, 2))//8+1:x}"
'20'

I'll do some more googling see if i can find the actual source

[wary wigeon]

I have a question about inversion, or more specifically about the underlying CKKS scheme. Am I correct that if two messages m1 and m2 have multiplication depth l1 and l2 "left", then m1 * m2 will have multiplication depth min(l1, l2) - 1?

[humble lake]

i think so

[wary wigeon]

I thought that's what I observed in repl/Python, but reading the [CKKS](https://eprint.iacr.org/2016/421.pdf , table 1) paper it seems that's not correct - they say that m1 * m2 actually retain layer min(l1, l2) (you still need to rescale to the lower layer hence the min)

The second param (\ell) is the level/depth

[humble lake]

it's impossible. min(l1,l2) means you can calc * for any ciphertext.

since min(L,L)=L

[wary wigeon]

Yeah exactly

But

It's literally the CKKS paper

From my understanding, I think the problem is if you do it as the table says, the ciphertexts will grow exponentially large? That's why they have a relinearisation step

But idk where it is, hence my question

[reef marten]

this also appeared in another paper
my really really rough understanding, and im not too sure im correct here but it may help in some form, i read in a paper on indcpa-d attacks on ckks that ckks scales (so we can call these levels), and RS goes down levels, and you can do operations on the same level, so m1*m2 only requires scaling m1 to the level of m2 (??)
now how that works out with what johnkram pointed out i have no clue, but heres the paper i was reading here, hope it can help in some way that i missed lol

[wary wigeon]

Were you reading it for DiceCTF 2022 learning without error lol, cuz my sol references the same paper 😂

[reef marten]

no i read it after this ctf lol, i was like hey ckks is cool what kinds of attacks exist on it

👀 did not know it was a past ctf chall tho lmao

[wary wigeon]

You should try that chal then, it's literally just impl the paper

I'll check out that paper

[reef marten]

will do, tyty

[wary wigeon]

also what the fuck happened to my blog formatting 😂 oops

[reef marten]

oh ya so no you can but also cant, pyhelayers has an extra step

Depending on scheme, this may perform some additional light-weight tasks allowing for a smooth sequence of operations.
seems that its "light-weight" tasks take a level

same with multiply raw

[reef marten]

so pyhelayers (as a library) preforms some L computations that take a layer

but the operation of multiplying does not

unless im misinterpreting my results

[wary wigeon]

I'll dig around the source code

[reef marten]

glgl

[wary wigeon]

oh, it's not open sourced

This package is provided under a community edition license for non-commercial use; see license. For commercial deployments and access to the source code, please contact [e-mail] for the Premium Edition license.

i think

[reef marten]

😭 nooo

[wary wigeon]

this is so confusing, since your multiply_raw seems to multiply correctly?

let me get my repl out again lol

[reef marten]

ya, im trying to see if theres effect if the numbers have more variance or are larger

[wary wigeon]

In [13]: cx = encoder.encode_encrypt(x)
    ...: for _ in range(5): cx.square_raw()
    ...: dec = encoder.decrypt_decode_double(cx)
    ...: np.max(np.abs(dec - x**32))
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
Cell In[13], line 2
      1 cx = encoder.encode_encrypt(x)
----> 2 for _ in range(5): cx.square_raw()
      3 dec = encoder.decrypt_decode_double(cx)
      4 np.max(np.abs(dec - x**32))

RuntimeError: Rescale counter should be less than or equal to the level

You will get error

This is so confusing, it doesn't explain when do you have to rescale

[reef marten]

maybe has to do with integer_part_precision = 10, - like the only explanation i can think of is if the number exceeds that precision level force a rescale? (but this is just guessing), then multiply rescales to be "safe"

[wary wigeon]

https://www.youtube.com/live/LNbGeaWKzpI?si=3Q3RQsXbGhuK25KF&t=1076
Their talk gives the example of f(x)=x^4, which also does this "square -> rescale -> square -> rescale" pattern

[wary wigeon]

hm

Don't think so, x = np.ones(n) still gives error

Or maybe it's the "worst case"

[reef marten]

hmmm maybe, but tbf that was just speculation

[reef marten]

wait i dont think its the rescale?

wtf me wen closed source libraries that are vague

[wary wigeon]

Well yeah because your error tolerance is okay right now

I think it's about the error not about precision

The precision is tracked in the (..., <err>)

i think

[reef marten]

oh ya you are right lol (about it being error based as far as i can tell)

[wary wigeon]

https://blog.openmined.org/ckks-explained-part-5-rescaling/ ok I think it's about the error yeah

So CKKS is a "leveled" FHE scheme i.e. there're multiple modulus, and each modulus can only tolerate a threshold amount of error

If the error is too large and you decrypt I think you'll error, so in that case you have to rescale

Rescaling will decrease both the error and the modulus, but most importantly the ratio of error/modulus will shrink

Something like that

(This contrast with bootstrapping FHE schemes where you can refresh the error without changing the modulus (??) so you get unlimited depth)

I think ^

OK maybe i'll implement it myself some day

thanks

[wary wigeon]

[deleted wrong idea]

maybe

[humble lake]

just 8

[wary wigeon]

oh how

[humble lake]

depth of x^7 is 3

x^15 is 4

[wary wigeon]

x->x^2->x^3->x^6->x^7 isn't it 4? How do you get x^7 with three multiplication depths

Or am I misunderstanding

[humble lake]

x^3*x^4

[wary wigeon]

oh

thanks

Okay but yes the idea is there 😛

[humble lake]

you can calc any x^t for 0<=t<=2^d with d depth

[wary wigeon]

AHHH ok nevermind yes you're correct

idk what I was thinking

[ornate prairie]

Depth vs total mults maybe

[humble lake]

yes

maybe more mults, but less depth

[wary wigeon]

Ahh yes yes

[ornate prairie]

Should still be possible to DP it, just accumulated with max + 1 instead of sunming

[wary wigeon]

Yeah but then now it becomes f(x) = max(f(a),f(x-a))+1=f(x//2)+1 which is just log

[ornate prairie]

Isn't that assuming some structure on f?

[humble lake]

in fact, it's f(x)=f((x+1)//2)+1 with f(0)=f(1)=0

[wary wigeon]

yea same thing

[wary wigeon]

Uh I guess in general you have f(x) = max(f(a_1), f(a_2), ..., f(a_k) | a_1 + a_2 + ... + a_k = x) + 1

But induction should show the above

Or just show that f(x) <= the solution, and you can get a lower bound by choosing a particular a_i i.e. the two element case above

[humble lake]

anyway, because there is no total mults limit in this chall, f(x) is easy to calc

[vivid verge]

Did anyone solve RPS-casino using sage?

[serene condor]

I tried but with the last modulo 3 it did not work

I would be interested to see a sage solution

[vivid verge]

Same for me

[white sapphire]

Wait is sage’s solve() not good enough compared to z3?

[toxic valve]

Here's a rps-casino solution using z3 (sometimes it may fails if there's multiple possible solutions):

#!/bin/env python
from pwn import *
from z3 import *
from Crypto.Util.number import bytes_to_long

pty = process.PTY
r = process(['python', 'server.py'])
#r = remote('mc.ax', 31234)


def LFSR(init_state):
    state = init_state
    while 1:
        yield state & 0xf
        for i in range(4):
            bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
            state = (state >> 1) | (bit << 63)


def z3LFSR(state):
    while 1:
        yield state & 0xf
        for i in range(4):
            bit = (state ^ LShR(state , 1) ^ LShR(state , 3) ^ LShR(state , 4)) & 1
            state = LShR(state , 1) | (bit << 63)

def get_state():
    z3state = BitVec('s',64)
    z3rng = z3LFSR(z3state)
    s = Solver()
    r.recvline()
    for _ in range(56):
        r.sendline(b'rock')
        res = r.recvuntil(b'!\n').strip().decode()
        if res.endswith('Tie!'):
            v = 0
        elif res.endswith('win!'):
            v = 2
        else:
            v = 1
        s.add(Extract(1,0,next(z3rng)%3) == BitVecVal(v,2))
    assert(s.check() == sat)
    return s.model()[z3state].as_long()

rng = LFSR(get_state())
for _ in range(56):
    next(rng)

rps = ["rock", "paper", "scissors"]
for _ in range(50):
    r.sendline(rps[(next(rng)+1)%3].encode())
r.interactive()

[cerulean warren]

@surreal coral don't keep us in suspense

[wary wigeon]

Maybe it's guest authored by factoreal

[woeful otter]

Any detailed wp for the inversion chall?

[deft obsidian]

Can you explain "s.add(Extract(1,0,next(z3rng)%3) == BitVecVal(v,2))" please?

[oak wind]

for me I didn't have to use extract, directly comparing it work

[white sapphire]

for me I'd hard coded in the possible values for 0,1,2 mod 3
then just did z3.Or() spam per each query

[deft obsidian]

I understand most of the code but that line is confusing me

[deft obsidian]

basically like how is he comparing the two things, not worrying about extract()

[deft obsidian]

so do you mean something like: s.add(next(z3rng)%3) == BitVecVal(v,2))?

[oak wind]

let me find my script

[deft obsidian]

alright

thank you for helping me!

[oak wind]

import os
from Crypto.Util.number import bytes_to_long, long_to_bytes
from z3 import *
from pwn import *
r = remote('mc.ax', 31234)
def LFSR(state):
    while 1:
        yield state & 0xf
        for i in range(4):
            bit = (state ^ LShR(state, 1) ^ LShR(state, 3) ^ LShR(state, 4)) & 1 # bit = xor(state[-1], state[-2], state[-4], state[-5])
            state = LShR(state, 1) | (bit << 63)
def num_LFSR(state):
    while 1:
        yield state & 0xf
        for i in range(4):
            bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
            state = (state >> 1) | (bit << 63)
# get test case
n = 56
#rng = num_LFSR(0xcafebabedeadbeef)
choices=['rock','paper','scissors','rock']
known_output = []
for i in range(n):
    #known_output.append(next(rng))
    r.recvuntil(b': ')
    r.sendline(b'rock')
    res=r.recvline()
    if b'Tie' in res: known_output.append(0)
    elif b'win' in res: known_output.append(2)
    else: known_output.append(1)
#known_output = [i % 3 for i in output]
#print(output)
#print(known_output)

# solve
s = Solver()
key = BitVec("k", 8*8)
rng = LFSR(key)
for i in range(n):
    val = next(rng)
    #print(val, output[i])
    s.add(val%3 == known_output[i])

print(s.check())
m = s.model()

res = 0
for d in m.decls():
    res = m[d].as_long()
print(hex(res))
# testing
rng = num_LFSR(res)
for _ in range(56): next(rng)
'''new_output = []
for i in range(n):
    new_output.append(next(rng))

print(new_output)
new_output_mod_3 = [i % 3 for i in new_output]
print(known_output)
print(new_output_mod_3)'''
for _ in range(50):
    r.recvuntil(b': ')
    opp_choice = next(rng)%3 
    choice = choices[opp_choice+1]
    r.sendline(choice)
r.interactive()

[deft obsidian]

Thanks!

[tawdry kite]

wtf i didnt know BitVec's could do modular stuff

[daring dagger]

lol

[chrome light]

???

[tawdry kite]

idk man

[red moon]

it's very easy to get the sign wrong on z3's mod stuff

[woeful otter]

Wait how did u solve it?

Do u have a not-z3 solution?

[tawdry kite]

Someone posted a sol without z3 about just bruting thru the possibilities of all mod 3 combinations

And u can reduce the search a lot by using the first 4 bits to check for the next 4 bits and make the brute manageable

I can’t find it anymore though

[woeful otter]

That's what I wanted to do initially. Wrote a DFS and using the guessed 4 bits to prune branches. But testing locally gave way too many valid solutions so I dropped that idea.

[fathom basalt]

So, do we desume that shor was actually intended to be broken when quantum computers arrive ?

[lone stream]

We're preparing a detailed writeup on ours, using the first 32 response to create a set of possible urandom value and then verify ith the remaining 24. At the end we have a final candidate for our initial random, and we can predict correclty the remaining 50 !

[reef marten]

ireland just has a pocket quantum computer

what you dont?

[daring dagger]

no someone with a pocket quantum computer just snuck the challenge in and put ireland as the author

[steep abyss]

mine worked something like this

i brute forced all triples of 4 bytes what the 6 rolls that come from them would be

then brute forced all ways of filling the seed, and just checked which were valid

here it is, mess and all, in c++ (just extracting a seed from mod 3 rolls, networking was another mess)

runs super fast (~20^5-20^6 ish ops)

[humble lake]

a new day without shor's write up

[wary wigeon]

^

[wary wigeon]

Search in this channel for my comment after CTF end

I gave like three different solutions

One is use the pyfelayers library (there’s a FunctionEvalutor class which implements a paper using low degree polynomial approximations)

One is directly perform polynomial least-square interpolation. IIRC using degree 250 (? Or is it 4095, forgot) gets you below the error, ~0.22

One is Newton-Raphson since it doesn’t require division for f(x)=1/x-D

[reef marten]

just gonna add one more for the fun, taylor series

[wary wigeon]

How does that work, there’s a discontinuity at 0 so it should diverge?

[reef marten]

unsure, its not my solution, gonna just @daring dagger (he used taylor here)

[white sapphire]

who's factoreal and what did factoreal do

[wary wigeon]

No comment

[reef marten]

but from my understanding -

[white sapphire]

(no like, i actually hv 0 context here)

[wary wigeon]

(No comment)

[red moon]

You can square it to x^2, find the reciprocal of that with taylor, then multiply it back by x

[wary wigeon]

That still has a discontinuity at 0?

[red moon]

No, the square is positive only

[reef marten]

beat me to sending the ss of helloperson saying that :<

[wary wigeon]

Like y=1/x has a pole at 0 so surely there’s no analytic continuation or whatever

[wary wigeon]

Oh

[reef marten]

its barely in range i think

[wary wigeon]

No but I mean the function itself

[reef marten]

lke barely taylorable

[wary wigeon]

Or what are you trying to taylor series on?

[reef marten]

given the func x, you taylor 1/x^2, then multiply that by x

[wary wigeon]

My understanding of taylor series is its radius of convergence is from the center of expansion up to the nearest pole

1/x^2 has a pole at 0, and there's no center z such that there's a ball covering [-1.4,-0.4] U [0.4,1.4] but not 0?

That's for both 1/x and 1/x^2, doesn't change anything

Oh okay nevermind

[red moon]

Once you multiply it by x it's no longer a taylor approximation

[wary wigeon]

huh

Okay I misunderstood, you probably meant like Enc(x) -> Enc(x^2) first (homomorphically)

[reef marten]

not that i know of

[wary wigeon]

And there x^2 is positive so you can taylor series to get Enc(1/x^2) -> Enc(1/x)

[reef marten]

i have his solve script

i think

lemme see if i can find

(maybe that will help understand?)

[wary wigeon]

I want to understand the math

😅

[red moon]

Yeah pretty much this

I used a square as well to get rid of the sign, but not a taylor series

[reef marten]

ya ofc

[wary wigeon]

I used FunctionEvaluator.sign 🤡 it takes 7 depth

[reef marten]

ye i just did funcevaluators inverse

[wary wigeon]

But yeah ok, 4 solving methods now

[reef marten]

helloperson orz

[red moon]

Yeah that would have been nice to know beforehand

[wary wigeon]

not bad

[wary wigeon]

Yeah I actually notified the author (was it ireland?) abt it but he just said "wtv it's a warmup chal" 😂

[reef marten]

newton-schlutz works too i think

but im not sure if we want to count that as seperate

cuz i think atp thats just inversion/divison algs

[wary wigeon]

According to this that Newton-Schlutz (idk what it is) iterates by x -> x(3-x^2)/2
so it's just a cubic iteration instead of Newton-Raphson's quadratic?

[reef marten]

ya

so diff poly

[humble lake]

it's worse

[reef marten]

not sure if we counting that as diff tho

[wary wigeon]

That's what I imagined too

[reef marten]

i think divison algs as general maybe?

[humble lake]

since its iteration's depth is 2

[reef marten]

(just nitpicking kinda cuz grkhm said newton-raphson specifically)

so maybe expand to iterative division algs?

idk doesnt matter not like this is a professional wp lmao mb

[wary wigeon]

No I think the problem is x^3 takes 2 depths

x^2 takes 1

So you get 6 iterations instead of 12, I guess

Also the convergence rate per iteration seems slower accordign to Theorem 2.2

[reef marten]

in ckks is there an issue with procrastinating on rescaling?

because the lib rescales after every single multipliction

but is it really necessary to rescale that often?

[wary wigeon]

you can do .multiply_raw

[reef marten]

ye

multiply_raw but

my question is

[wary wigeon]

no idea

[reef marten]

if you multiply a bunch, then rescale once at the end

ah

ok

actually thats a testable question lmao mb

hmm it still remains relatively precise?

(assuming this is showing (value,error))

[wary wigeon]

From the minimal knowledge I have about ckks, each level's error tolerance is a ratio times the modulus right
So I assume they fitted the parameters such that one multiplication requires a rescale already

[reef marten]

hmmm idk

ill experiment/read papers ig

[wary wigeon]

I don't know much about it

[reef marten]

ya me neither

idk much about cryptography lmaoo

[wary wigeon]

ckks is 2016/421 btw

not sure why i remember

[reef marten]

tyty, i was just reading attack papers descriptions of ckks till now lmaooo

[wary wigeon]

but it's a good number

uh

[reef marten]

i mean they give good descriptions

idk i just never pulled up the original paper for some reason

¯_(ツ)_/¯

[wary wigeon]

Yes the B something something 20 paper is good iirc

Okay maybe B something something isn't descriptive

https://eprint.iacr.org/2020/1533.pdf

[reef marten]

ya

its also a fun read overall lol

(or at least as far as i got)

hmm experimentally checking error if you dont rescale i think it could be possible for an unintended on iinversion 2
it seems if you dont rescale a single time over 12 multiplications your error isnt that bad

not too sure tho, might try it sometime later

[wary wigeon]

    ...: x = np.random.uniform(-1, 1, n)
    ...: x = np.copysign(np.abs(x) + 0.4, x)
    ...: 
    ...: cx1 = encoder.encode_encrypt(x)
    ...: cx2 = encoder.encode_encrypt(x)
    ...: for _ in range(8):
    ...:     cx1.multiply_raw(cx2)
    ...: cx1.rescale()
    ...: cx1
    ...: 
    ...: try: cx1.multiply(cx1)
    ...: except Exception as e: print("Error:", e)
Error: The Operands should have rescale counter zero

You mean like this to "bypass" the automatic rescaling? It won't work, once you do any operations you'll see

[reef marten]

no i mean

import pyhelayers
import numpy as np
import base64
import sys
import os
from copy import deepcopy
os.chdir("/tmp")

n = 16384
requirement = pyhelayers.HeConfigRequirement(
    num_slots = n, # Number of slots per ciphertext
    multiplication_depth = 12, # Allow x levels of multiplications
    fractional_part_precision = 50, # Set the precision to 1/2^x
    integer_part_precision = 10, # Set the largest number to 2^x
    security_level = 128)

he_context = pyhelayers.HeaanContext()
he_context.init(requirement)
encoder = pyhelayers.Encoder(he_context)
cutoff = 0.02
x = np.random.uniform(-1, 1, n)
x = np.copysign(np.abs(x) + cutoff, x)  / (1 + cutoff)
cx = encoder.encode_encrypt(x)

cx_rescale = deepcopy(cx)
cx_raw = deepcopy(cx)
base = deepcopy(cx_raw)
x_copy = x.copy()
for _ in range(12):
    cx_raw.multiply_raw(base)
    cx_rescale.multiply(base)
    x_copy *= x

#print(cx_rescale)
#print(cx_raw)
cx_raw.rescale()
#print(cx_raw)

cx_raw_dec = encoder.decrypt_decode_double(cx_raw)
cx_rescale_dec = encoder.decrypt_decode_double(cx)
# raw rescaled only at end, versus rescaled at each step
raw_error = max(abs(x_copy - cx_raw_dec))
rescaled_error = max(abs(x - cx_rescale_dec))
print(f"{raw_error = }")
print(f"{rescaled_error = }")
# for sanity checking a guesstimate
calculated = 3*np.sqrt(rescaled_error)
print(f"{calculated = }")

this is what i have so far

(3*√2 makes no sense to me that was just eyeball math but)

[wary wigeon]

Ah, maybe

[reef marten]

after 12 mults, 1 rescale you have ~3.99e-6 error

[wary wigeon]

I suspect that's a bug but I'm not sure

[reef marten]

so im saying maybe not as efficient algorithm could work if it ran raw numbers

im not sure either

i also cant math at 2 am so imma try this later lmao

[reef marten]

ah so while it looks like it could work, the library doesnt let you do past 12 mults anyways lol

RuntimeError: Rescale counter should be less than or equal to the level would happen at 13th

[wary wigeon]

Sounds normal?

[reef marten]

ya, tho id rather open source libs cuz then i could see like what the deg 7 polys were for sign and whatnot (ok yes i could prob recover them via just using the lib/dynamically but thats a later me issue and thats just an example)

[cerulean warren]

Must be unsolvable

[humble lake]

so will there be an official write up?

[upbeat hazel]

I’ve messaged the author but haven’t heard back yet

Sorry

[wary wigeon]

You shouldn’t be lol

[red moon]

Now that we have the private key on github, we can try the easier version of the challenge: can we recover all the j's?

[wary wigeon]

I haven’t looked at the chal in detail, but is this summary correct:
We’re given 1000 of floor(j * 2^6144 // phi(N)) XOR <sparse error, 5%>?

Is there a solution if the error is 1 bit lol

Or say 10 bits so you can’t bruteforce

(Sorry I suck at lattice)

[cyan onyx]

what's the purpose of a winternitz OTS? I don't understand how it's more secure than just using a normal hash checksum

i don't see how hashing it (256-N) times creates a signature that's useful

[chrome light]

its a signature meaning its signed by a specific priv key that u can verify with the pub key

[cyan onyx]

so you have your priv key: random bytes Priv[32]
you make a sha26 digest of your message, and split it into 32 bytes N[32]
your signature is priv[N] hashed 256-N times

how is this information useful??

does hashing a byte 256 times cause it to go back into identity?

[chrome light]

no 256 is just chosen because a byte cannot go above 256

[cyan onyx]

ohhh i see

[chrome light]

its a signature scheme

[cyan onyx]

so the public key is priv hashed 256 times

[chrome light]

yea

well actually idk i forgot

lol

[cyan onyx]

you hash your privkey 256-N, and then the client hashes it the remaining N times

and then it becomes public key

in order for this to work, don't you kinda have to trust that the public key is valid too?

couldn't someone send a fake public key AND file

i.e. forge the entire message

well i guess that's beyond the scope of a signature scheme

[chrome light]

thats like

yeah

thats just public key cryptography

[cyan onyx]

i see ty for the helpness

[chrome light]

np im also not super good at crypto so maybe someone better can touch in here but 👍

[cyan onyx]

why is this better than just sending the 256-bit digest of the contents, if you're using it as a one-time signature?

like isn't this accomplishing sort of the same thing as just doing a sha256

or am i misinterpreting the meaning of an OTS

does OTS mean that you can use the same privkey/publickey, but the signature itself needs to be new

or does it mean you need to make a new priv and public key

[chrome light]

this

thats the whole point of the challenge xd

[cyan onyx]

wait so then how does a winternitz signature scheme have any benefit over just sending the 256-bit digest of your message?

isn't it just adding more layers of convolution

[wary wigeon]

Btw another point you might have missed is that it isn't necessarily useful

IIRC it's proposed in the early 70s or 80s

Which is probably older than 99% of the people here except @hot kestrel

But there are advantages. For example, it relies purely on hash-based assumptions

Compare this with say most (all?) lattice-based cryptography, where even though the main security relies on some lattice hardness e.g. RLWE, it still actually requires a hash function when you do the hash-and-sign step at the very start

And also the Winternitz OTS scheme can be improved with various techniques. You can read about SPHINCS+ which is in the NIST thing

Where instead of OTS they use a variant to get Few-Time Signature instead, etc.

[cyan onyx]

what's the goal of the winternitz ots then? can'y tou jut like do something like

publicKey = hash256times(message)

[wary wigeon]

To get a scheme where again it's purely hash-based

[chrome light]

what did he do to you 😹

[wary wigeon]

That's not cryptography, there's no secret key

[cyan onyx]

what's the purpose of a secret key if you're only using it once?

like if a key can only be used exactly once, isn't it completely useless

[wary wigeon]

No because 1 > 0

[cyan onyx]

?

i mean if a secret key can only be used once, doesn't it hold no meaning?

[wary wigeon]

IIRC there's a one way function construction from OTS but I can't find it rn

And also it's used as a base primitive to build other stuff on

(from what I understand)\

[cyan onyx]

is a majority of cryptography just building high-level protocols out of low-level fundamental mathematical problems that are unsolvable without brute force 2^N

[wary wigeon]

Ahh e.g. you can combine a Merkle tree-like construction with OTS at the leaves layer to get a signature scheme. this explains it quite well if I remember correctly, but I haven't read it in a while

(Again, SPHINCS builds on top of few-time signatures, but you can "unoptimise" it to use one-time signatures + larger parameters)

[wary wigeon]

Uh yeah

There are usually standard well-established assumptions though

[cyan onyx]

like building layers of security upon fundamental cryptographical truth

[wary wigeon]

Yeah

Like in lattice {R,M}LWE is considered fundamental nowadays

Or classically RSA/pairing is considered fundamental

[cyan onyx]

is this like used to securely build up a protocol where you can create and exchange things like dual private keys and things

[wary wigeon]

Key exchange protocol is the most basic ones

Let me find a diagram, I remember seeing a good visualisation of this

[cyan onyx]

why does it need improvement? isn't it technically cryptographically sound

256-bit security

[wary wigeon]

Reduce key size, signature size, improve speed

[cyan onyx]

same security level, but better efficiency

[cyan onyx]

ah i just found out its called a "cryptographic primitive"

[wary wigeon]

Uh I can't find it but IIRC it goes something like
Basic primitives: Key exchange, encryption, signature, commitment
More advanced: OT, uh idk
More advanced: FHE, functional encryption
bruh: Witness encryption obfuscation bullshit

It's 7am right now so I probably remember half the stuff I should remember so maybe the actual cryptographers can fill in the blank

[upbeat hazel]

the point is you want to generate the keypair in advance of what message you want to sign

even though it's one-time use, that's still a useful feature

you can construct normal multi-use signature schemes from a one-time signature

[wary wigeon]

https://eprint.iacr.org/2010/446.pdf introduction seems to give some actual references for IRL uses

Despite the limitations of OTS, they have found many applications. On the more practical
side, OTS can be used to authenticate messages in sensor networks [18] and to provide source
authentication for multicast (also called broadcast) authentication [39]. One-time signatures are
also used in the construction of other primitives, such as online/offline signatures [22] and CCA-
secure public-key encryption [14].

[cyan onyx]

yeah, i see, you can use it to build up security protocols
the point is that you can sign a message and make a keypair using any privkey

which is why its useful

[wary wigeon]

I just saw the g4g page for winternitz lol

[cyan onyx]

yeah i couldn't find a wikipedia

[cyan onyx]

did you find it?

[wary wigeon]

I literally said I can't find it

[cyan onyx]

oh whoops

this?

https://www.researchgate.net/profile/Liam-Keliher-2/publication/239554949/figure/fig1/AS:349898198274048@1460433639512/Taxonomy-of-cryptographic-primitives.png

[wary wigeon]

Day idk of thinking about shor

[red moon]

can't be much longer now

[daring dagger]

at some point the challenge will be trivial by quantum computer accessibility

[wary wigeon]

contact the ireland police for a https://www.wikiwand.com/en/Wellness_check fr

[fathom basalt]

Found the solution to shor!

https://eprint.iacr.org/2021/933

[humble lake]

really?

[cyan onyx]

if you do the winternitz scheme on a byte-by-byte basis (you only hash 8 bits at a time), isn't it relatively easy to traceback?

you could just map out the entire network of all 256 values and their outputs, and use it to create a fake signature given any arbitrary public key and message

[wary wigeon]

That’s why in the real scheme there’s a checksum to prevent signature forgery

And that’s why it’s a one time signature scheme

[reef marten]

steal irelands personal quantum computer

[cursive anvil]

Anyone tried this?

[red moon]

admittedly I have not. I'm still just waiting and hoping the official writeup appears eventually

[woeful otter]

Can u share the writeup now?

[wary wigeon]

I determined it's impossible

Recovering them doesn't help in the original chal, so they shouldn't be recovered

[ornate prairie]

It's overall kinda similar to an a(g)cd, but just more annoying errors, but I can't quite get to a good formulation yet

[wary wigeon]

I'm not too familiar with agcd but I imagine they don't allow errors too large right

And here the error can be as large as the numbers in magnitude due to the xor

[humble lake]

one more day without quantum computer

[wooden spruce]

given that numpy default generator uses pcg64, which has a 128 bit state, and that the first bit must be 1, i think it should be possible to find the rng seed from just the first bit of the 1000 cases

[hot kestrel]

how do you extract those bits from shor.txt?

[wooden spruce]

just the most significant bit of each result

[red moon]

why must the first bit be 1?

[wooden spruce]

    res = v.digits(2)
    res = res + [0]*(mbits - len(res))
    res = res[::-1]

res is in base 2 and starts with 1, and is padded by 0s on the end
it then is reversed, so each sequence must end with a 1
so we can parse with like int(x[::-1],2) | 1<<6143

[hot kestrel]

doesnt v.digits(2) return the lsb first?

https://doc.sagemath.org/html/en/reference/rings_standard/sage/rings/integer.html#sage.rings.integer.Integer.digits

[wooden spruce]

huh guess im stupid

i thought digits was a python function and assumed

[humble lake]

one more day without readout correction algorithm

[nova breach]

guys we just need to apply the probability current equation, then everything will magically work

[reef marten]

😭 maybe we are expected to crowd solve shor

[daring dagger]

are you still tryna solve it?

[reef marten]

I havent even started

[red moon]

No time like the present

[daring dagger]

also no time like the future

[reef marten]

Have you heard the myth of the mea-shor-ment error write up?

[icy kite]

Yeah

[red moon]

At which point does a myth turn into a mystical folk legend

[wary wigeon]

It doesn't turn into a legend

It just turns into disappointment

[daring dagger]

depends on connotation ig

[humble lake]

still waiting

[wary wigeon]

@ admin, is there any plan to either release a solution/writeup or tell us whether it's impossible?

[opal plinth]

@wary wigeon do you know who the challenge author was?

[upbeat hazel]

none of the organizers (besides the challenge author) are aware of a solution

there are no plans to release a solution or writeup, unless the challenge author responds

for now I think it's best to consider the challenge unsolvable

[crimson pollen]

which one ?

[upbeat hazel]

mea-shor-ment error

[opal plinth]

Who is the challenge author?
Or was this a guest challenge?

[upbeat hazel]

ireland