Tags: crypto
Rating:
# guess-the-bit (crypto) by freed
```
crypto/guess-the-bit!
freed
I'm trying out for this new game show, but it doesn't seem that hard since there are only two choices? Regardless, I heard someone name Pollard could help me out with it?
nc lac.tf 31190
```
### Source Code:
We got a python script:
```
#!/usr/local/bin/python3
import random
from Crypto.Util.number import getPrime
n = 43799663339063312211273714468571591746940179019655418145595314556164983756585900662541462573429625012257141409310387298658375836921310691578072985664621716240663221443527506757539532339372290041884633435626429390371850645743643273836882575180662344402698999778971350763364891217650903860191529913028504029597794358613653479290767790778510701279503128925407744958108039428298936189375732992781717888915493080336718221632665984609704015735266455668556495869437668868103607888809570667555794011994982530936046877122373871458757189204379101886886020141036227219889443327932080080504040633414853351599120601270071913534530651
a = 6
print("n = ", n)
print("a = ", 6)
for i in range(150):
bit = random.randrange(0,2)
c = random.randrange(0, n)
c = c**2
if bit == 1:
c *= a
print("c = ", c)
guess = int(input("What is your guess? "))
if guess != bit:
print("Better luck next time!")
exit()
print("Congrats! Here's your flag: ")
flag = open("flag.txt", "r").readline().strip()
print(flag)
exit(0)
```
By looking at the code we see, that we have to correctly guess "0" or "1", 150 consecutive times, where the only clue is that "c" is multiplied by 6 if the bit is "1".
When we execute the script we get:
```
n = 43799663339063312211273714468571591746940179019655418145595314556164983756585900662541462573429625012257141409310387298658375836921310691578072985664621716240663221443527506757539532339372290041884633435626429390371850645743643273836882575180662344402698999778971350763364891217650903860191529913028504029597794358613653479290767790778510701279503128925407744958108039428298936189375732992781717888915493080336718221632665984609704015735266455668556495869437668868103607888809570667555794011994982530936046877122373871458757189204379101886886020141036227219889443327932080080504040633414853351599120601270071913534530651
a = 6
c = 1410132788608602763158396295624793759904655068051423981654157408858516026643980786856015619052298024807772928582489337691467942913156648729914931486795307951043818464031117288130179675799373821086788361878963242640731127560775267553300797276590046325077916983342153282725870806303932237803398185892655978024005382393197627845440584640158085873863438715977431270918091974946191705315979525940276484143527850043259370577160815242392335466977633709148891754549875667790088878329357384980261534051937286670977696831607765415121400667438479466496843247444740737689841014683444173927090709875884586976983787960903008800682080998624903829642633288754059748302392804655391341909383708326141414538118706706193002866326200907188769586264734937048444005702348541967340602885269784331311114178318613496397173661613650164549737500854189221532106801126563074403397990825351801004596417821801104738103953469714525263238105010960618179916170944313252522209199260608056099722100087218029189691725628387132589723192354630001293643477579628697822084503351723020388065247018710912728049752095530572151655528210320574613101568566631349290814504466543787365308284621127890546203499258501497921210098334717912419847132348899737023840376088480068924340126667045094
What is your guess?
```
and are prompted for an input. If we guess correct we get another input, else it stops executing.
Since we get c printed in every iteration, my first thought was to check if c / 6 is an integer (and not a float) and then check the same for the squareroot of the result.
### Solve Script
With my first try I encountered the problem of the numbers being too big for python to handle so I set the challenge aside but came back to it later thanks to my colleague.
With a quick search I found the "decimal" library to handle big numbers and wrote the following script:
```
from pwn import *
import decimal
# function to check if a number is an integer (and not a float)
def isInt(x):
if x%1 == 0:
return True
return False
proc = remote("lac.tf", 31190)
n = 43799663339063312211273714468571591746940179019655418145595314556164983756585900662541462573429625012257141409310387298658375836921310691578072985664621716240663221443527506757539532339372290041884633435626429390371850645743643273836882575180662344402698999778971350763364891217650903860191529913028504029597794358613653479290767790778510701279503128925407744958108039428298936189375732992781717888915493080336718221632665984609704015735266455668556495869437668868103607888809570667555794011994982530936046877122373871458757189204379101886886020141036227219889443327932080080504040633414853351599120601270071913534530651
a = 6
proc.recvline() # receives "n"
proc.recvline() # receives "a"
log.info(f"{n=}")
log.info(f"{a=}")
decimal.getcontext().prec = 2000 #defines the precision with which to handle numbers
for i in range(150):
c = (proc.recvline())[4 : -1].strip() # receives "c" and strips it of "c = " and the newline
#c = recv[4 : -1]
log.info(f"{c=}")
proc.recvuntil("What is your guess? ")
# handle "c" as a decimal object
c = decimal.Decimal(int(c))
calc = c / 6
# check if "c" can be divided by 6 (and is an integer)
if isInt(calc):
# check if the squareroot "c" is an integer
if (isInt(decimal.Decimal(calc).sqrt())):
proc.sendline("1")
else:
proc.sendline("0")
else:
proc.sendline("0")
proc.interactive()
```
### Executing:
The script iterates over all 150 guesses and spits out the flag:
```
[*] c=b'6379556576818693476369652866915677377894413664645382309301046455530350313139827129026846449494475147450731648674871386465561190560881760544434252973905184998040779242274724137559921251802376149876047770962192322136011026031759129519388371222799582697342394927282160454467050064239172830827064982617817916765430915280461553093988461788535096830251310062487858833260064754131490708505294695001627827459963566392063942637563391480440641587416365725231721767342990858613705671645430779221321661576064018147470503132703573690569406345476551084447152873929870226766169407602537799916516459358727305881894446739481824907493101771532823203181529285829652651946506724328146183512313412023176965096663100649684186075991234406802656214153681998369180788285773901356468222885287272369202768139169438185333271146557270387060308971440789929111988491595436646666114288010993725911690744430390504835053338292404143911651834228370248273827881655858411596671372928064517440745261111412661679694629015085332978109036673981210845423451990686744969976947180174463621257122381650087097071960264711047734964803372453372631394536146795698349408032673863338309434066801671063071954162980181366564780183827187245533775694383130630158378130517918884259829343471484934'
.
.
.
[*] c=b'6038670922528791006574237845246172509058837062551726491217358038095981690407070072180666580087324570715456435143466739702698882251273209366460724417208218488018591826065629909759434492037599591554602290059411179571690837723775347405485130120576664469078054827418647881117411271802609149492164629723597746961448546436781397396595293646024452910052788072169315058767747784475138892627915404370736615318593760966907449530258439343918390321549846788258812549565618914834121173186784027463338010685511385899363775586734638617912400115420586078383678300340717277346087687529265000384996748663271464528159538150425841122659226596410887335693057292714056690527167287989839980984643430259292180475013549084543750720342000610935829910517486298660403339002914736158937030590002718742108102534829881266984508458887611829499901141774951542746589113997806246676334770327926189552974086732835924208174769412480622008687207634048594740090234092165088255872231601018555153579886508313574779316164514095783855237901879516111612535536680613134042848496708388807132346594459326812877728486597189592281687906594985176565014487243306028283741554012966908508482726256106692353541554789556765995305308824660115129770791259589401609404176154281095543838522252854656'
[*] Switching to interactive mode
Congrats! Here's your flag:
lactf{sm4ll_pla1nt3xt_sp4ac3s_ar3n't_al4ways_e4sy}
[*] Got EOF while reading in interactive
$
```
It was a fun challenge which I almost missed due to the hardship with large number operations in python.
