crypto

[tight trellis]

for plagiarism can anybody explain the hxp code section where they say exponentiation is slow?

#g = (ZnX.X + ZnX(delta)) ** key.e - ZnX(Zn(c1)) #exponentiation is slow...
gs = [delta ** key.e]
for k in range(key.e):
gs.append(Zn(key.e - k) / (Zn(k + 1) * delta) * gs[-1])
g = ZnX(gs, 'little') - ZnX(Zn(c1))

[upbeat hazel]

it won't matter because their code

won't work

[tight trellis]

yeah i know we don't have the library

[upbeat hazel]

but I think it's just referring to the fact that

well

even if you had the library

it wouldn't work

but it's referring to the fact that computing out the expanded form of (x + m)^e

[deep sedge]

they're taking a polynomial and raising it to a high power

hence why it's slow

if you remember binomial expansion you would know why it's slow

[tight trellis]

why is what they do faster though

[deep sedge]

they do it manually i think

i haven't really looked at the code in depth

[tight trellis]

are they creating the binomial expansion in that for loop?

[deep sedge]

uh maybe idk their library and code is weird

[surreal coral]

just use Sage

[deep sedge]

hehj

if it was that easy it wouldn't have 7 solves

[bright sky]

nah 7 solves bc no one wants to use sage

[grave dune]

[latent tiger]

Now I'll just wait for solutions

Also for Tux crypto , that only Hellman solved :feelsbadman:

[indigo stag]

wondering what this "show solved" button should do

doesn’t trigger anything for me

[analog stump]

it shows all challenges including the ones you have solved

[indigo stag]

well I thought the joke on the fact that I solved zero crypto challs was obvious 😅

[analog stump]

ohhhh

damn it

[indigo stag]

3 hours on plagiarism and around 4 on benaloh

should have looked at garbled maybe

[analog stump]

probably

~~our solution is a little ~~

if you can even call it a solution

[indigo stag]

looking forward to see the smart tricks in benaloh solution

[vernal crater]

i think our garbled time was spent like

10% actually working out solution

30% fixing stupid indexing errors

60% waiting for code to run so we could keep debugging it

will there be a newcrypt writeup

[prime eagle]

[surreal coral]

imagine not using pypy

[full temple]

That my experience overall for this CTF, waiting heavy algos to finish again and again. Not blamings orgs since my approaches were not optimal

[prime eagle]

and thats why idont do crypto

[upbeat hazel]

rip

i won't be able to make writeups

in time

err

i'll probably finish benaloh

s5 will be sparse tho

[violet coral]

That's good news 🥳

[deep sedge]

not having writeups already done

WeirdChamp

i wanna see what i did wrong for benaloh

[indigo stag]

same

[full temple]

use grobner basis

[upbeat hazel]

benaloh and signature sheep scheming signature schemes: https://priv.pub/posts/dicectf-2021/

[violet coral]

Is that some kind of fun number theory thingy owo

[upbeat hazel]

fml i shouldn't have procrastinated on writing this

fweaf

[violet coral]

Lol

This site cannot provide a secure connection. priv.pub uses an unsupported protocol (-113)

[tight timber]

fweaf

[upbeat hazel]

it's github pages + cloudflare

idk what to say

[compact jacinth]

fweaf

[wary geode]

cloudflare too secure

[deep sedge]

i tried grobner basis but my sage cried at me

how do you get rid of a and c

resultant?

[neat shard]

how was plagiarism done

[upbeat hazel]

a is a constant

some c with a multiple of u, which I suppose counts as resultant

[deep sedge]

i guess i had the wrong

equations

[sullen oar]

What was newcryptv2? I was using the paper using Minkowski sums to find polynomials but couldn’t get any grobner or resultant computations done in time

[full temple]

it's the right paper

[compact jacinth]

solve script posted here: #writeups message

[neat shard]

?how

[upbeat hazel]

the one by aono is the right paper

it's a pain in the ass to implement though

i tried doing it for redpwnctf

[sullen oar]

What m did you use? And did you use all 5? Also did you prune their polynomial set at all or straight from the paper

[deep sedge]

how in the hell were you supposed to find that paper

[tight timber]

all of the relevant papers suck to implement

[full temple]

I used bit-by-bit bruteforce instead of Grobner but there was something weird happening: I got 73 good polynomials out of 113 and still the bit-based search exploded, while the 74th poly was always overflowing modulo once, and using the poly with the correction magically helped.

m=1

[tight timber]

use a faster gcd algorithm

[upbeat hazel]

"Cryptanalysis of RSA with Multiple Small Secret Exponents" sth like that

[neat shard]

which

[tight timber]

idk just look up faster gcd algorithm lul

[sullen oar]

Ya I had the 73 good polys after filtering the LLL rows cause my variety kept coming back empty, but my grobner bases in sage never finished. Guess I should’ve waited longer

[full temple]

I didn't use the heuristic and on dimension 112 LLL took 2h 23m 35s :/

[tight timber]

the original writeup uses euclid gcd which is unfortunately too slow for the provided numbers

i believe ireland's intended sol used half gcd

[full temple]

Maybe try with 74th one +- modulus

[lunar elbow]

Need more easy cryptos that can be solved with pen and paper

[deep sedge]

half gcd?

never heard of that

[tight timber]

pen and paper crypto is dead

[violet coral]

Reading a bit on gröbner basis and wikipedia says it's done on finite fields.
Correct me if I'm wrong but since n is not prime, Z/nZ is no field?

[deep sedge]

that's what my sage was complaining about it hink

[violet coral]

Could it be the idea is "the chance of finding multiples of primes of n and it actually hindering the algorithm is so small we can say Z/nZ is essentially a field" ?

[sullen oar]

Which problem are you talking abt Grobner bases for

[violet coral]

Benaloh

[deep sedge]

defund can you explain why a grobner base works

[full temple]

my intuition is that the space of monomials is rather limited so it quickly gets saturated and yields "nicest" basis

[full temple]

this is a good explanation, groebner basis is based on simple arithmetic

[deep sedge]

i guess fundamentally i don't understand what a grobner basis does

[full temple]

it combines multiples of polynomials into new polynomials in nice ways (such that high-degree terms are cancelled)

[deep sedge]

thanks that makes more sense

[full temple]

having many low degree polys is nice since you can do linear algebra on them

[deep sedge]

can someone show their gcd algorithm for plagarism

i'm assuming you also probably had to manually calculate the coefficients

my sage died after trying to generate the polynomail

[full temple]

weird, i used sage to multiply polynomials and it was reasonably fast

[deep sedge]

no i mean more it died trying to do (x + diff)^e - c1

i wanted to generate the coefficients manually but didn't really know what to do after that since i knew gcd would take too long

[full temple]

was <1 minute for me to generate the polynomials

[deep sedge]

really?

guess my sage sucks

lol

mind sharing your code? or just the relevant parts

[surreal coral]

I can share my soln

[full temple]

missing from binteger import Bin

[deep sedge]

huh i'm surprised this worked for you cause my just wouldn't get past it

pb = (x + mb)**e - ciphertext_Blex

thanks for the solution

[full temple]

I think I used SageMath 9.1, but during CTF I upgraded to 9.2, which had more bugs 😦

[deep sedge]

rip

[surreal coral]

reference solution, implements Half-GCD ( http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf )

[indigo stag]

that’s really not intuitive for me how all Ui can be represented as multiples of c in benaloh

i get the solution, but if that’s based on simple arithmetic shouldn’t we get an intuition without just trying out the groebner basis blackbox like it was some LLL magic

[deep sedge]

huh i really wish i found that paper

[surreal coral]

"subquadratic gcd algorithm" is the google-fu

it's surprisingly hard to find if you use other keywords

or u can be hellman and derive it from scratch

[deep sedge]

"fast polynomial gcd algorithm" and it's the 3rd link for me

:)))))))))))

deriving it from scratch sounds like some god tier math skills

@upbeat hazel any reason you only used 4 polynomials instead of 10

for the groebner basis

i assume 4 is faster and sufficient enough i guess

[upbeat hazel]

sorry I'm eating dinner rn

I'll answer stuff later

[surreal coral]

also the original franklin-reiter paper for plagiarism talks about groebner basis

[upbeat hazel]

to the best of my ability

[deep sedge]

i assume you're talking about this paper

https://0xdktb.top/2020/05/04/WriteUp-De1CTF2020-Crypto/howgrave-graham1999.pdf

it did talk about groebner basis

i was too stupid to input the correct polynomails

[surreal coral]

from hxp

[deep sedge]

link is borken xd

[finite otter]

I found this document to create the correct polynomials and the diagonal matrix to balance the equation https://cr.yp.to/bib/1998/howgrave-graham.pdf

[solid venture]

ono cr.yp.to

[halcyon belfry]

djb 🙏

[finite otter]

But I couldnt decrypt the message with the d that i compute

[deep sedge]

which question was this

[indigo stag]

newcrypt v2

[deep sedge]

oh i tried that too

never got a good basis out of it

i assume the polyniomials and the diagonal matrix was wrong because delta was too big

[maiden narwhal]

what's the approximate runtime?

[upbeat hazel]

30 min on his computer

[maiden narwhal]

thanks!

[upbeat hazel]

4 is sufficient, you can't do any better than the polynomials they give I'm pretty sure

[upbeat hazel]

which part is unintuitive?

[indigo stag]

the multiplicative relation between u and c

for example to make the challenge did you just try it out with different r values until groebner basis gave smth good enough to solve?

[upbeat hazel]

no the r value doesn't really matter

besides increased time complexity

[indigo stag]

or maybe it’s good enough for all r values

[upbeat hazel]

!purge 20

[uneven gazelle]

✅ Deleted 20 messages!

[upbeat hazel]

lemme think about this

a bit more

[tight timber]

smh defund nazi modding

[upbeat hazel]

wait I think i'm right

actually

because literally given

u^17 i was able to construct

the sequence of masks

rip

there goes the message history

[halcyon belfry]

!archive channel 805962661833474048 50

[uneven gazelle]

✅ Archived 60 messages from crypto.

[upbeat hazel]

thanks

but going back to the challenge it's not that

c is some multiple of u by design or anything

almost any number is a multiple of another number in the ring

so it's more just that the polynomials basis has that relation

[deep sedge]

see what i have a little trouble connecting is the linear relation between u, a, and c and how that extends to the power of 17

i can't see u, a, and c to the power of 17 having a linear relation

but i guess they do

[upbeat hazel]

grobner basis uses polynomial gcd

too

[deep sedge]

wait now that i htink about it all of thoes numbers will be different integers in the ring

so they all have to have some kind of relation

[indigo stag]

Yeah I get what you mean, I will have to dig a bit deeper into groebner basis to understand how these relations are found

thanks 🙂

[upbeat hazel]

yeah, sorry i can't provide sth more concrete

it's not entirely clear to me either why the polynomials can be reduced this far

besides the reasoning I laid out for why

the polynomial reduction

can't give you

the values completely

due to finding roots being hard*

as to why you can find a or c^17 or u^17 directly, for example - unclear to me too

that being said grobner basis is good to have in toolbox

[indigo stag]

So just out of curiosity on the challenge crafting did you end up on this setup by trying different ones basically?

[upbeat hazel]

i made the chall a couple days ago

and I guess I started from,

[surreal coral]

finding roots isnt unique so groebner wouldnt help

cant reduce x^16 - 1 uniquely

[upbeat hazel]

benaloh with bad nonce generation

and the first thing I thought of, what if we add 1 to u at every step

and that lead to, how about we just make that a random value 😛

actually I initially was doing goldwasser micali

which is just benaloh with r=2

[indigo stag]

sticking to the add 1 chall would have been nicer 😅

[upbeat hazel]

lol

[indigo stag]

anyway thanks for the explanations 🙂

[upbeat hazel]

I don't really like releasing challenges in series though

yeah np

[indigo stag]

I was just kidding that would have made the chall really classical whereas it brings smth nice here

[upbeat hazel]

😌

[glacial cobalt]

are there garbled writeups

[upbeat hazel]

https://www.josephsurin.me/posts/2021-02-08-dicectf-2021-garbled

[glacial cobalt]

thanks

[latent tiger]

I just woke up where is plagiarism solution ?

[upbeat hazel]

@latent tiger pinned

[latent tiger]

Thanks

[full temple]

wonderful creative challenge!

[upbeat hazel]

glad you enjoyed it 😁

[violet coral]

I can't believe I forgot to google the title of the chall for benaloh

[prime eagle]

[limpid jetty]

[merry sedge]

I made the same mistake 😕

[frail kettle]

Although it is kinda late to say this, but seriously thanks for the wonderful crypto challenges!!!

[upbeat hazel]

thanks 😀

[tight trellis]

What is binteger? I can't get that to run

[short birch]

https://pypi.org/project/binteger/

[bright sky]

does this have docs

[short birch]

considering it appears to be a library written by hellman himself and doesn't appear to have an associated github repository, i would suppose not

[bright sky]

sad

[wary geode]

just read the source

it's not that long

[manic stump]

Hello !
Is there any recommendations ( book or paper or lecture ) for beginner of crypto?
It's too hard to solve a problem without background knowledge :’
I felt it every time I participated in the ctf
Thank you for reading this message : )

[upbeat hazel]

https://cryptohack.org

[manic stump]

oh that seems like crypto ctf page?
Thanks for letting me know !

[modern forge]

@everyone

[compact jacinth]

you tried

[modern forge]

@compact jacinth no one likes me ;p

[umbral sparrow]

need one play crypto join to my team

[upbeat hazel]

sorry in advance

[pseudo dune]

For how hard the challs will be ?

[violet coral]

best category in any case

[fathom saddle]

😩 looking forward to it

[crimson pollen]

Death time, be prepare

[heavy fox]

👀

[bold horizon]

how long the ctf will be ?

[crimson cape]

February 4 21:00 UTC to February 6 21:00 UTC

[reef marten]

true crypto will be fun

Is there any quantum this year though?

[pseudo dune]

and at the same time there is none

[solid venture]

when dunfed apologizes in advance for the crypto

me scared

[reef marten]

same

but hey at least ireland isnt apologizing for quantum

[violet coral]

scary
But fun

[reef marten]

true

[violet coral]

Last year was awesomely great

[reef marten]

yep I looked them up

prob easy for you given you do crypto 24/7 but

[violet coral]

Don't say such things

[solid venture]

what if defund is apologizing because he didn't write anything

👀

wild theories

[violet coral]

:rooScream:

[upbeat hazel]

isogenies!!!

[gloomy maple]

who is the author of baby-rsa?

[sullen oar]

@surreal coral

[sacred blade]

ireland

[sullen oar]

you can open a ticket though

[hallow vale]

Baby rsa is really doable ?

[wary geode]

it has 23 solves

so probably

[compact jacinth]

Yes

[hallow vale]

i never see that

[surreal coral]

🪢

[upbeat hazel]

🩸

[crimson pollen]

I guess I used a hammer for the baby

[surreal coral]

👶 🔨

[upbeat hazel]

the horror

[misty glen]

[upbeat hazel]

who solved pow-pow on galhacktic? nvm, found

[misty glen]

courtesy of everyone's favorite pb-er http://cryptoiscryptocurrency.com/

[crimson pollen]

I can't see this, only truth can live

[misty glen]

[serene minnow]

[willow skiff]

@surreal coral can i dm ?

[wary geode]

no but you can open a ticket

[reef marten]

inside said ticket do we ping the challenge creator?

[misty glen]

you don't have to

we usually do it

once someone triages

[warped halo]

i get it, math is important to solving these 🤔

[surreal coral]

math? In my crypto?
It's more likely than you think

[umbral verge]

crypto is math :d

[warped halo]

huh, this is why i've been completely lost

I've been trying to solve baby-rsa by reading The Count of Monte Cristo

[misty glen]

you see crypto is just where the math nerds on our team get to flex how many papers they read every day

<Ireland frantically trying to defend themself>

[surreal coral]

pwn is where people compete on how much of glibc and linux kernel source code they can recite from memory

[brave light]

what the heck does the data.txt is for, is it supposed to be the original values? for baby-rsa

[surreal coral]

Yup

[lean arch]

ikr

[hallow vale]

Ikr ?

[lean arch]

its seems very undoable

but obv people has solved it

ive been scratching my brain for like 30 min

[hallow vale]

I think it’s possible but i never do that

[brave light]

same here lol, don't know what the heck I am supposed to be doing here

[warped halo]

after spending the last few hours on baby-rsa, i can confirm that the cipher is divisible by 1

[upbeat hazel]

pog

[surreal coral]

It's also divisible by negative 1, but that requires quantum mechanics to explain

[reef marten]

Its also divisible by itself

impossible

[warped halo]

divisible by 2 numbers?! How much more could it be?!

[surreal coral]

I'm pretty sure that means it's prime

[warped halo]

you might be right about that

[surreal coral]

A number is prime if it's divisible by one and itself

[reef marten]

are we talking about n or p and q?

lmfao I got to <redacted> then just got stuck

[surreal coral]

N but mostly we're messing around

[reef marten]

fun fact, n is divisible by p and q

[warped halo]

not really sure how you can divide letters, this makes no sense

[sacred blade]

math goes from word problems, to numbers, to letter symbols, to word problems (but now you have to prove stuff and write complete sentences 😔 )

[reef marten]

Im on normal symbols
and I hate ∫ D:

oh well

[merry bolt]

letter opener

... sort of

[warped halo]

🤨

[reef marten]

see im just ded in rsa

what about you guys?

[warped halo]

the only challenge i have solved is the discord flag

[reef marten]

Same

[warped halo]

i will solve baby-rsa

maybe

[reef marten]

Same maybe

idk

[upbeat hazel]

you got this

(•̀ᴗ•́)و ̑̑

[upbeat hazel]

another blood!

braid and psych left

[reef marten]

I am going to have a great time reading the writeups and not understanding anything

[upbeat hazel]

well, and potentially unreleased challs

[warped halo]

my free grammarly account does not know what to do with these numbers

[proper flume]

oh yeah you need grammarly premium

[warped halo]

https://tenor.com/view/sueñitosgifs-traumatized-mr-incredible-los-increibles-meme-gif-24305569

[candid girder]

mfw i find papers that seem related to this and am still stuck

[reef marten]

when you have p q e phi n and c but its 11:00 am and you forgot how to decrypt rsa

[candid girder]

Bruh

Baby rsa makes me want to kms

It's so free I can tell

But I'm just monkeying it

Why couldn't they have done a normal babyrsa

Omg

[warped halo]

honestly running out of lined paper for the brute-force by hand

[upbeat hazel]

it's the twist

[candid girder]

Not a good one tho

0/10

[compact jacinth]

very hard chall

[candid girder]

Don't recommend

[upbeat hazel]

😦

[candid girder]

U done it or still stuck like me?

[reef marten]

its nice when you get the keys

[compact jacinth]

stuck

[reef marten]

defund I got the keys but im so tired I forgot rsa decrypting lmfao

[compact jacinth]

@candid girder Only sanity completed

[reef marten]

and I cant seem to remember frick

[candid girder]

Cryptohack

If uve done any rsa already

[upbeat hazel]

the private key doesn't work

[candid girder]

Steal code from the solutions

[reef marten]

wat

[upbeat hazel]

you won't be able to do normal rsa decryption

[reef marten]

WAT

[reef marten]

WAT

[upbeat hazel]

wat

[wary geode]

wat

[candid girder]

Yeah obv

[warped halo]

w a t

[reef marten]

rip

nooo

[candid girder]

Issue is to decrypt rsa u do pow(ciphertext, d, n)

[compact jacinth]

rip

[sacred blade]

because this is dicectf 🙂

not picoctf

[candid girder]

D is inverse (e, phi(n))

But that ain't gonna work round these parts

[south vine]

yeah there are so many challenges where you copy paste some cookie cutter rsa template and dont learn anything

[reef marten]

oof private key ded how dare you defund

[sacred blade]

umm...

[candid girder]

I mean that ain't a hint

[sacred blade]

these are getting into too technical

[sacred blade]

not yet...

[candid girder]

Cause that's how to do normal rsa

This is some off brand infant shit

[compact jacinth]

@candid girder Only sanity done

[upbeat hazel]

I didn't write the challenge 😨

[compact jacinth]

the challenges are brainfuck

[wary geode]

lots of teams only have welcome solved

[candid girder]

Mfw I've done all the cryptohack rsa challs and can't do a fucking baby rsa chall

[wary geode]

no worries

[sacred blade]

imagine if we put baby in front of the hardest challs

sike

[candid girder]

Vote for Pedro was way easier than this shit

[wary geode]

haha that's funny

I get the joke

because sike

nvm

[warped halo]

quick write it down

[upbeat hazel]

I see you panda

[sacred blade]

i think it's past your bedtime kfb

[compact jacinth]

all hard

[candid girder]

U done any cryptohack man?

U should

Is v fun

And ACTUALLY POSSIBLE UNLIKE THIS IMMA KILL TBE CHALLENGE AUTHOR

[compact jacinth]

no

[wary geode]

oh no don't do that

he's a nice guy

[compact jacinth]

same here

[wary geode]

D:

[candid girder]

I hope they go to diffie-hell

[warped halo]

this challenge is def out of my league, but reading up on RSA very nice

[sacred blade]

i need to get back into cryptohack

school L 😔

[candid girder]

Just do it during class

I'm in HS and all my classes become cryptohack from time to time

[sacred blade]

I'm in college, and I'm paying for class time

so...no

[candid girder]

In the us?

[upbeat hazel]

this challenge is not out of your league!

[candid girder]

out of mine lol

[upbeat hazel]

if you solved all the cryptohack rsa

you can solve this

[sacred blade]

yeah. $$$

[plucky solstice]

yeah if you solved and understand all cryptohack rsa you can 100% solve it

[warped halo]

eventually

[candid girder]

ah fair, gotta get something out of it when u go 4 million into debt for a fancy cheet of paper

[sacred blade]

maybe 90%

[candid girder]

yeah but im monke

[wary geode]

number theory knowledge is helpful probably

[sacred blade]

fermat's little theorem 😍

[wary geode]

I actually haven't seen the challenge

so idk

[edgy zodiac]

skill issues

[sacred blade]

did ireland write both baby challs?

[candid girder]

eh i think it is

yeah ireland wroet babyrsa at least

yep

and babyrop

someone gotta teach em what baby means

[wary geode]

I think that's the joke

[sacred blade]

nah next time we'll just not make baby challs 🙂

so he doesn't get bombarded with questions

[wary geode]

well we gotta have a couple

[warped halo]

is this fermat guy a smart dude? 🤔

[reef marten]

the french one? yes very

very

smart

big brain

if we are talking about Fermat's little theorem fermat

are we talking about that fermat

[candid girder]

yeah maybe, but he never did anything big. only came up with some little theorems

[wary geode]

idk he left the proof for his last theorem as an exercise for the reader

sounds like something someone without a proof would do

[reef marten]

little? do you realize how useful they are?
Litterally one of rsa's proofs use that little. theorem

[reef marten]

Lmaooo Fermat's Last Theorem

[candid girder]

yeah ik

[reef marten]

The solution on that

was complex

[compact jacinth]

xd

[warped halo]

my computer doing matrix stuff woah

[candid girder]

bruh

fully done with this

[sly tree]

bru

baby rsa is gonna be the death of me

[candid girder]

fr

[upbeat hazel]

😦

you know, you could also look at some of the other crypto

[compact jacinth]

same

[upbeat hazel]

like rejected

[compact jacinth]

f**k

[sly tree]

nah but i started baby rsa

i needa finish

i feel like im close

[upbeat hazel]

o

[sly tree]

but idk

[upbeat hazel]

tru

[sly tree]

could i dm?

[upbeat hazel]

feel free to file a ticket

#create-ticket

or DM, idm either

[candid girder]

wait a minute

ϕ may be dead to me

nope

my boy mike failed me to

or maybe i failed him

idk at this point

i am mentally running round in circles and regressing to a baby

[sacred blade]

me in every ctf

[candid girder]

do u want me to delete those message btw, i think they are cryptic enough but obv your call

@sacred blade

[sacred blade]

i don't even know what those messages are saying 🤷‍♂️

[candid girder]

fair

dm?

[sacred blade]

other orgs might delete them though

[winter arrow]

Where can you learn the maths for cryptic - rip. Cant even solve baby rsa xD

[sacred blade]

there's cryptohack

[winter arrow]

Oh, thank you 🙂

[warped halo]

i've been trying to find the bridge between stuff like PicoCTF and this more advanced stuff, is CryptoHack that inbetween?

[plucky solstice]

I would say so

[compact jacinth]

@candid girder The Baby RSA is f**k i'm gonna suicide

[gray bay]

yeah

[sacred blade]

ok maybe not a perfect bridge lmao

[compact jacinth]

basically all challenges are suicide

moew over admin are rude and not helper

[silk wagon]

thats why the ctf has name

because its tooo hard

[warped halo]

I

my guess is that using an on-screen keyboard for this is not recommended

[candid girder]

my guess is that being bad is not recommended cause i am fully stuck

#badgang

[warped halo]

all i need are the discord points ;-;

[lunar forge]

hellman 🙇‍♂️

[candid girder]

author of babyrsa going to diffie-hell

[dusk thunder]

hellman is busy today, so I have a chance to solve something too 🙂

[upbeat hazel]

are you on MSLC?

[dusk thunder]

yep

[lunar forge]

wait

[upbeat hazel]

did you solve the crypto?

[lunar forge]

mslc op 🙇‍♂️

[dusk thunder]

yes

[upbeat hazel]

oh sick

[lunar forge]

sorry I kinda just assumed hellman was only cryptographer for some reason

[umbral verge]

🙇‍♂️

[upbeat hazel]

what are you trying now

psych?

actually mslc didn't solve rejected yet either

[zealous bough]

rejected is so difficult..

[upbeat hazel]

good luck

[silk wagon]

they are hard

[quick birch]

#!/usr/bin/env python

import z3

with open("data.txt") as f:
    for line in f:
        var, val = line.split(" = ")
        globals()[var] = int(val)

s = z3.Solver()

p, q = z3.Ints("p q")

s.add(p * q == N)

if s.check() == z3.sat:
    m = s.model()
    print(f"p = {m[p].as_long()}")
    print(f"q = {m[q].as_long()}")
else:
    print("Unsolvable")

dice_ctf/crypto/baby-rsa
➜ ./solve.py
p = 57996511214023134147551927572747727074259762800050285360155793732008227782157
q = 1

I mean, its not wrong 😂

[candid girder]

bruh

it aint wrong

but ill tell ya this

you dont need z3 for p and q

[quick birch]

yeah I know

I have p and q

was just curious to see if it could

[winter arrow]

Can I dm someone pls? I figured out a solution that works, but yet doesnt work for the flag xD

[quick birch]

dice_ctf/crypto/baby-rsa
➜ ./solve.py
p = -1
q = -57996511214023134147551927572747727074259762800050285360155793732008227782157

it has mugged me off again but yeah it can't

[quick birch]

~~doesn't work then does it 😂 ~~

[winter arrow]

I hate my life, it only works for a plaintext of length 1 xD

[candid girder]

rippppppppppp

[winter arrow]

split flag.txt
cat * > /user/officialbenko

[signal ermine]

any hint for babyRSA 🥲

[quick birch]

f

[candid girder]

i am so close to just trying to bruteforce babyrsa

[sacred blade]

create a ticket and we may or may not help 🙃

[ruby bane]

any hint for BabyRSA ?

Dachshund, wiener attack doesn't even solve it

i'm literally crying 😢

[sacred blade]

😦

[worldly scroll]

We can't solve baby rsa without finding p and q right?

or can we?

[gray bay]

i can't solve it with even p and q

[worldly scroll]

🤣

[gray bay]

and here u r asking if u can solve it with p and q

[compact jacinth]

same 💀

[sullen oar]

Who solved commitment issues 😅

Curious about your solution

[gray bay]

ig someone outsmarted u.

just saying 🤷

[sullen oar]

Clearly hahah

[frosty bramble]

I'm working on an algorithm solving baby_rsa without p & q, but python can't do all my calculations as longs get even longer.

lol

OverflowError: int too large to convert to float

[winter arrow]

!giveup

[sullen oar]

Who is on Nu1L

[verbal thicket]

mensa-baby-%s

[compact jacinth]

!fuck

[candid girder]

!killmeplease

[junior moth]

I found a lead for RSA but....couldnt solve it yet...

then i should just leave the CTF and solve cryptohack it seems

[candid girder]

doesnt help

im a 🍋 that cant

[frosty bramble]

Any admin available for sanity-check on baby_rsa please?

[halcyon belfry]

#create-ticket

[surreal coral]

Well done on solving shibari 🪢 !
Would you mind DM-ing me your solution?

[silk wagon]

see admins asking for writeups

[lunar forge]

we are curious 👁️ 👄 👁️

[winter arrow]

Im sitting on this baby_rsa challenges for hours, tried 100+ possible methods & did a lot of research. How come that it has soo many solves 😂

[modest ore]

no one will be on fishing 😄

no one will be on fishing 😄

no one will be on fishing 😄

no one will be on fishing 😄

[potent grotto]

classic example of breaking the rules of RSA to implement RSA! smh

[surreal coral]

The first rule of RSA is you don't talk about RSA

[candid girder]

Oh your online now

I can finally tell you to got to diffie-hell cause of babyrsa

[sacred blade]

Lmao

[candid girder]

It is probably very simple

Seems it

[surreal coral]

ngl this sounds like a you kind of problem

[candid girder]

But has caused hours of pain

Yeah it is

[surreal coral]

Pain is pleasure and pleasure is pain

[candid girder]

So you're a masochist

[crimson pollen]

Yes

We are

[surreal coral]

no u

[inland ruin]

what kink is this

[torn spade]

🥺

[surreal coral]

This took a turn

[crimson pollen]

https://tenor.com/view/angry-birds-dice-jumpscare-dice-jumpscare-angry-birds-gregory-gif-24379056

[sacred blade]

ono

[surreal coral]

Let's go back to wholesome family friendly content like shibari

[candid girder]

also would like to say nice chall, I have seen a decent number of rsa challs (too many with the same name lol) and somehow never come across this

[inland ruin]

😆

[crimson pollen]

rejected already not friendly

[candid girder]

This chat is #crypto not #dicegangepsychosexualanalysis

[inland ruin]

petition to create one

[surreal coral]

Petition to ban Moriarty

[candid girder]

*bean Moriarty

!bean @inland ruin kinky

[uneven gazelle]

✅ Moriarty#8077 (518674233484640256) was beaned. Reason: kinky

[full temple]

is it possible to mirror psych?

is unreasonably slow

[wary geode]

@upbeat hazel

[surreal coral]

we are working on a fix, will be deployed with some other adjustments (to other challenges)

[river copper]

any idea abt this crypto/baby-rsa

[surreal coral]

1. open a ticket
2. try harder

[reef marten]

so in said ticket can we ask for help or is it only for technical difficulties

like how do I get rustc on a mac

[surreal coral]

we don't give hints, but we sometimes clarify issues

[tight pine]

it shows ELF, which implies that it's a binary file, and prob you need to pwn it

[reef marten]

tthats a crypto chall

lmao

[solid venture]

e l F

100% pwn

ignore the fact that elfs have ELF in the first 4 bytes

[hexed solar]

lol

[sacred blade]

[fallen hedge]

Hi, in baby-rsa I think I got the correct way but I'm not sure because it doesn't work, can I msg anyone?

[sacred blade]

you can create a ticket, and ireland or others may choose to provide feedback

[pseudo dagger]

do I need to be a math major to solve rejected

[surreal coral]

you need to know what a LFSR is

[icy kite]

:0

[upbeat hazel]

crypto is cleared

🎉

well, except for any yet-to-be-released challs

[sacred blade]

which are delayed

[sullen oar]

[upbeat hazel]

ok crypto is cleared

[surreal coral]

@full temple @dusk thunder
Would whoever solved correlated please DM me your solution?

[vocal forge]

the crypto challenges are driving me insane 👍

[reef marten]

That means you're doing them right!

sanity and learn/gain are inversely proportional

[vocal forge]

i'm going insane and learning little at the same time so i know i'm doing a terrible job rn

[surreal coral]

That just means you're going to enjoy reading the write-ups even more

[sturdy epoch]

Any TBA for the writeups? Like immediately after the CTF or a couple of weeks

I'm going nutso lol

[wary geode]

what does tba mean

[sturdy epoch]

Like expected timeframe or date

[wary geode]

authors and other competitors may choose to publish writeups

but no guarantees

[sturdy epoch]

Gotcha

[wary geode]

usually if the challenge is interesting enough then someone will post something

[sturdy epoch]

Yeah I'm super curious for the baby rsa one

[sacred blade]

we have a writeups channel that other competitors here can write writeups/link to writeups they made once the competition's over

err... we had a writeups channel

where'd it go?

[wary geode]

#writeups

gonna keep that down there until end

or make a new one perhaps

[sacred blade]

oh ok

[upbeat hazel]

I will publish writeups for pow-pow and psych immediately after the ctf ends

hopefully

[candid girder]

time to make #dicegangphsycosexualanalysis real except its just the writeups channel

[violet coral]

Having an average of 4 bits of recovery error for correlated is quite infuriating

[warped halo]

back the baby-rsa grind

running out of time oh god

[warped halo]

running out of lined paper

this is a disaster

My TI-84 Plus CE can't handle this

[gloomy cedar]

Excited for writeuppssss 🎉

[indigo wigeon]

Can't wait to read the writeups to see how my brain is

[zenith bloom]

Same

[warped halo]

Anyone want to lend me a quantum computer for 33 min?

[surreal coral]

sorry mine broke last week

[ripe shore]

maybe if you ask nsa nicely they will lend their for you

[tribal zenith]

im trying to figure out baby-rsa, i have the primes and created a finite ring that d has to be in. its still way to large to compute tho. any tips?

[sacred blade]

we can answer any questions you have in 23 minutes

[reef marten]

IBM account

if it works it works ¯_(ツ)_/¯

Or you could actually just do the code

and not even make an account

would that even work?

[warped halo]

I found a sure fire way to solve all cryptography, it will just take some time....

[sacred blade]

🤡

i found a way to solve a ctf flags, it will just take some time

[warped halo]

no EZ just send a github RAT to the organizers

[reef marten]

lmaoooo

[warped halo]

things are becoming more desperate, anyone have a spare data center for 15 min?

[sacred blade]

🤡

[reef marten]

yep need more proccessing power

[sacred blade]

i have access to a supercomputer, but it requires my physical presence

and its still icy here in texas

[warped halo]

free cooling pog

[reef marten]

pls run the following script:
<redacted since competition not over>

[reef marten]

I have access to a quantum computer remotely
except for the hiccup that its too slow

[upbeat hazel]

author writeups for pow-pow and psych will likely be delayed by an hour

:x

[surreal coral]

!bean @upbeat hazel slow

[uneven gazelle]

🚫 Failed to parse the user param: multiple_potential_targets
🔧 Command usage: !bean <user> [reason]

[umbral verge]

expect for

stuck on pow-pow

XD

[upbeat hazel]

oh my pow-pow writeup is done

I just need to do psych

[umbral verge]

:d

[past turtle]

Writeup for baby rsa?

[winter arrow]

Plss

[analog stump]

https://blog.soreatu.com/posts/intended-solution-to-crypto-problems-in-nctf-2019/#easyrsa909pt-2solvers

[winter arrow]

English pls? :c

[analog stump]

the idea is to implement an algorithm to take find e'th roots mod p and q, and then combine all possible roots with crt

(although most people probably didnt implement the algorithm, since sage has it build in with nth_root()

[queen furnace]

I was sticking with this: https://crypto.stackexchange.com/questions/43660/rsa-how-to-compute-the-number-of-possible-plaintexts-if-e-is-not-coprime-to/83593#83593
But was unable to retrieve x T_T

[torpid dove]

do commitment-issues needs to compute resultants and use coppersmith to solve for flag?

[latent tiger]

solution for commitment-issues ?

[surreal coral]

there are a lot of things online for e | p-1
but not for e^2 | p-1

[sullen oar]

essentially

[crimson pollen]

I called roots() on a polynomial mod N and somehow it worked

[sullen oar]

my writeup of it should be there

[violet coral]

Aren't these the same though

[ornate prairie]

commitment issues, lots of computation + adaptive root with smooth exponent

[vocal forge]

https://eprint.iacr.org/2020/1059.pdf i'm p sure this is related to baby-rsa but i wasn't able to extend to higher powers

it says it's trivial to extend to higher powers but i couldn't figure it out

[queen furnace]

Indeed, I read this

[tribal zenith]

nooo way more roots in both rings if e^2

[sullen oar]

huh, curious what you did to solve

[ornate prairie]

lemme find the paper with the idea, lol

[sullen oar]

oh shoot theres a paper? lol

[violet coral]

But the principle remains the same

[latent tiger]

can i see the solver

[ornate prairie]

I think I confused two chals, nvm 😄

not sure

[violet coral]

ayye

[sullen oar]

oh yeah, okay that sounds like pow-pow haha

[ornate prairie]

Yepp

[sullen oar]

thats my commitment issues solver

but theres a much nicer explanation that is in the official writeup link, wherever that is

https://hackmd.io/fmdfFQ2iS6yoVpbR3KCiqQ

[full temple]

shibaru GPU bruteforce is intended?

[sullen oar]

no haha

[surreal coral]

solution is 2 parts:

1. the braid is already in normal form, so you can import it into LNF faster than computing LNF on it.

2. apply a length-based attack because the entire circuit is reversible.

if you guess that the first few gates are performing the subcircuit A := NOT bit 0; CCNOT(0,1,2)

then the length of the circuit A^-1 * Circuit should be "shorter" than the length of Circuit
where length is the length of the LNF canonical form

Whereas if you guess wrong and try the circuit B := NOT bit 0; NOT bit 1; CCNOT(0,1,2)
then the length of the circuit B^-1 * Circuit should be longer than the length of Circuit

so you can bruteforce the flag 2-bits at a time

the step 1) of importing into LNF is needed because computing the LNF is so slow for the obfuscated braids (it's pretty quick for the unobfuscated braids)

and the provided python bindings support quickly computing the LNF of LNF(a) * LNF(b)

in hindsight, I should have released the LNF form of the braids so that players didn't have to import it.

my solution doesn't actually use a length-based attack for 2) -- it uses an attack on the underlying Braid Conjugacy Problem.
This attack also requires having access to the braids in LNF

[violet coral]

What was the intended solution for pow pow? Mine feels way too dirty

[compact jacinth]

To whoever solved psych, did you manage to craft c0 which was "equal enough" to c0' to have a significant equality check time?

[upbeat hazel]

https://github.com/defund/ctf/tree/master/dicectf-2022

[violet coral]

Thanks!

[upbeat hazel]

yes, I'm making the writeup right now. The solve script is also in that repo

I'm so sorry :((((

writeups will be published in half an hour

[full temple]

I made the first point (P) fully equal, which adds +110 to time on correct match. So only 1 query / bit

[upbeat hazel]

oh and my psych solve script is unnecessarily complicated

because I obsesively optimized montgomery curve arithmetic

you can just use sage's libraries

[full temple]

I quickly gave up on montgomery stuff and switched to sage 🙂

[upbeat hazel]

my solve script runs in 5 seconds locally 😎

[compact jacinth]

Hm interesting, so it's possible to do the adaptive attack using just Q and P-Q?

[full temple]

yeah because sibc does not check anything

except the hash in the KEM, which should thwart all such attacks (unless leakage)

https://gist.github.com/hellman/5c2deab6dfcb179b101237471e7450ca

Basically keep P and make Q low order. I don't know what sibc's formulas compute on such inputs, but the output range is just the order of Q

which by comparison leaks LSBs of the secret

[compact jacinth]

Ahhhh this makes so much sense, I was going with the full ceremony from the original paper of passing through weil and all which doesn't leave much wiggle room. Thanks!

[abstract wigeon]

someone for the rsa pls ?

[full temple]

Yeah my first solution was to match 1-2 bytes in c0 and then GPST. But I messed up and recovered garbage in 2 hours... Had to improve

[fierce cave]

Hey hellman

Staying up all night to solve correlated was a thing I did

[upbeat hazel]

I think my solution passes those sorts of checks

but yeah those are irrelevant

in the context of SIKE

[full temple]

Sounds interesting, in 500 queries?

[upbeat hazel]

it varies, but on average yes

[full temple]

(but I only know the basic GPST attack on static keys)

[upbeat hazel]

I like your solution more though

maybe I'll just link it in my writeup

and call it a day

💀

[full temple]

no, I need to know how what I am missing 😛

[upbeat hazel]

ok welp, I'll include a brief note at the end

[upbeat hazel]

https://priv.pub/posts/dicectf-2022

my explanation is probably quite terrible

[candid girder]

I'm going to ✨KMS✨ after seeing a baby rsa writeup. I forgot that sage had functions for that and was trying to fucking monke brute force the CRT with python. Omfg that challenge fried my brain

[sacred blade]

https://www.lifeline.org.au/

[candid girder]

Lol

[vocal forge]

understandable

[tight pine]

How did people solve correlated? I just wait on the event that the first 48 bit of the stream has <= 5 wrong bits and bruteforce... hope this is not the official solution lol

[upbeat hazel]

it seems like many people solved it this way

it is not the intended solution

[tight pine]

what's the intended?

[surreal coral]

https://hackmd.io/fmdfFQ2iS6yoVpbR3KCiqQ?view#crypto/correlated

tbh the intended was super complicated, and i'm happier with this challenge being a fairly accessible filtered-LFSR challenge than it being a super hard one that no one attempts

[candid girder]

Why the fuck are y'all smart

[abstract pier]

We can extend by enumerating two variable from two groups with ord=e^2

I tried it and it worked

But it seems to be unintended after I looked at the writeup

[deft obsidian]

can anyone tell me what was the theoreom/using what method was the pow-pow chall made?

[sacred blade]

See the author's writeup: https://priv.pub/posts/dicectf-2022

[deft obsidian]

Thanks!

oh it's Wesolowski’s verifiable delay function

i see, intersting crypto challs@

[ripe shore]

in the author's writeup why did you also multiply with some small number less than 256?

[sour dune]

for rejected approximately how many bits would one need to obtain for the attack to work? would the linear system to solve have like 32k variables or is it usually much less than that

[upbeat hazel]

in case m has repeated small factors, like it's divisible by 4

[violet coral]

Doesn't the linear system have exactly n variables, where n is the bit length of the key?

[sour dune]

oh i assumed we were solving for the output of the lfsr instead of the key

oops

so given an output 1 at the xth bit of the output you represent it as a sum of the (x-tap[j])th bits in GF(2) and keep doing that until you reach the first n bits of the key? or is there a simpler method

[violet coral]

In rejected you aren't given the outputs

You are told whether its greater or lower than some threshold

And when you know the output is greater than the threshold, if said threshold starts with b 1 bits then you get that the output must start with b bits to 1 as well

[violet coral]

And then you can solve like this

And that's exactly what you said and I'm too tired please ignore me

[sour dune]

lol

so i guess around n bits need to be leaked for the linear system to be solved?

[violet coral]

At least n bits yes

[sour dune]

ok thanks

[urban wedge]

hello, anyone has writeup for crypto/baby-rsa

[ripe shore]

N is quite small so you can use alpetron or factordb to get two prime. Next brute force every single possibility and stop once you have clear plaintext because e and phi are not coprime (see: https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e/81966#81966)

[torpid dove]

actually, GF(p)(c).nth_root(e, all=True) works for this challenge since e is small

[abstract pier]

from Crypto.Util.number import long_to_bytes, bytes_to_long

p = 172036442175296373253148927105725488217
q = 337117592532677714973555912658569668821
N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
c = 19441066986971115501070184268860318480501957407683654861466353590162062492971
Z = ZZ.quotient_ring(N)
phi = (p-1)*(q-1)
d = inverse_mod(e, phi//e^4)

a = pow(c, d, N)

_phi = phi // e^4    
g_2 = pow(2, _phi, N)
g_3 = pow(3, _phi, N)
assert g_2 ^ e^2 == 1
assert g_3 ^ e^2 == 1


for i in range(0, e^2):
    for j in range(0, e^2):
        x, y = g_2^i, g_3^j
        m = long_to_bytes(int(a*x*y))
        if b"dice" in m:
            print(m)

This works

Generalization of this paper(https://eprint.iacr.org/2020/1059.pdf)

[potent cave]

Z = ZZ.quotient_ring(N)

I'm pretty sure that's not standard python, nor exists in the libs you imported

[abstract pier]

Its sagemath script

In pure python

Remove the line and replace ^ with **

[potent cave]

Side note: Interesting that rsactftool couldn't solve this one

[sacred blade]

That would be actually baby

Not dice baby

If running a pre-existing tool can solve the chall

[twin iris]

rsactftool 👎

[latent tiger]

from Crypto.Util.number import long_to_bytes

N = 0xba8cb3257c0c83edf4f56f5b7e139d3d6ac8adf71618b5f16a02d61b63426c2c275ce631a0927b2725c6cc7bdbe30cd8a8494bc7c7f6601bcee5d005b86016e79919e22da4c431cec16be1ee72c056723fbbec1543c70bff8042630c5a9c23f390e2221bed075be6a6ac71ad89a3905f6c706b4fb6605c08f154ff8b8e28445a7be24cb184cb0f648db5c70dc3581419b165414395ae4282285c04d6a00a0ce8c06a678181c3a3c37b426824a5a5528ee532bdd90f1f28b7ec65e6658cb463e867eb5280bda80cbdb066cbdb4019a6a2305a03fd29825158ce32487651d9bfa675f2a6b31b7d05e7bd74d0f366cbfb0eb711a57e56e6db6d6f1969d52bf1b27b
c1 = 0x75240fcc256f1e2fc347f75bba11a271514dd6c4e58814e1cb20913195db3bd0440c2ca47a72efee41b0f9a2674f6f46a335fd7e54ba8cd1625daeaaaa45cc9550c566f6f302b7c4c3a4694c0f5bb05cd461b5ca9017f2eb0e5f60fb0c65e0a67f3a1674d74990fd594de692951d4eed32eac543f193b70777b14e86cf8fa1927fe27535e727613f9e4cd00acb8fab336894caa43ad40a99b222236afc219397620ca766cef2fe47d53b07e302410063eae3d0bf0a9d67793237281e0bfdd48255b58b2c1f8674a21754cf62fab0ba56557fa276241ce99140473483f3e5772fcb75b206b3e7dfb756005cec2c19a3cb7fa17a4d17f5edd10a8673607047a0d1
c2 = 0xdb8f645b98f71b93f248442cfc871f9410be7efee5cff548f2626d12a81ee58c1a65096a042db31a051904d7746a56147cc02958480f3b5d5234b738a1fb01dc8bf1dffad7f045cac803fa44f51cbf8abc74a17ee3d0b9ed59c844a23274345c16ba56d43f17d16d303bb1541ee1c15b9c984708a4a002d10188ccc5829940dd7f76107760550fac5c8ab532ff9f034f4fc6aab5ecc15d5512a84288d6fbe4b2d58ab6e326500c046580420d0a1b474deca052ebd93aaa2ef972aceba7e6fa75b3234463a68db78fff85c3a1673881dcb7452390a538dfa92e7ff61f57edf48662991b8dd251c0474b59c6f73d4a23fe9191ac8e52c8c409cf4902eeaa71714
e = 281840717167239017970190225734406156171

P.<x,y> = PolynomialRing(Zmod(N))
f1 = y + x - c1
f2 = x ^ 5 - c2
I = Ideal([f1,f2])
G = I.groebner_basis()
g1 = G[0]
g1 = g1.univariate_polynomial()

M = Matrix.companion(g1)
M2 = M^e
f = M2.charpoly()

print(long_to_bytes(int(f.small_roots(epsilon=0.05)[0])))```
took me a while to understand , but it's my `commitment-issues` solver

[reef marten]

they know.......

[sacred blade]

[fading minnow]

Root of unity works well

[twin iris]

What’s the trick you’re doing with the companion matrix? Does this help with how M^e is computed?

[sullen oar]

That is how I originally solved it. Using the groebner basis/however else, you can get a polynomial with s = m^d as a root. If we place this polynomial f into a matrix M that has characteristic poly f, then any root x of f is an eigenvalue of M. Then for any polynomial p, p(x) is an eigenvalue of p(M). Thus the characteristic poly of M^e has (m^d)^e = m as a root

[twin iris]

Ahh! Thanks for the explanation

We solved by taking the quotient ring with k^5 - c2 and so could make degree 4 polynomials which with linear algebra can be combined to give a univariate polynomial with m as a small root

[sullen oar]

Yea, thats the explanation I included in the official writeup because I think its a lot better way to solve. The companion matrix thing is kinda quirky. I haven't had time to think about it, but I suspect these are the same computations somehow packaged in different ways

[icy kite]

are there official writeups?

[twin osprey]

https://hackmd.io/fmdfFQ2iS6yoVpbR3KCiqQ

More will be added overtime

[icy kite]

thx

[abstract pier]

It is

Maybe my approach is unintended way

[twin iris]

https://org.anize.rs/dicectf-2022/crypto/powpow

If people want another version of pow pow write up

[umbral verge]

nice

[twin iris]

Write up for commitment issues 🙂 — hopefully people can follow along and enjoy the challenge

https://org.anize.rs/dicectf-2022/crypto/commitment_issues