Skip to content

Latest commit

 

History

History

MUNCH

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
binary_flag
binary_flag
 
 
prob_src
prob_src
 
 
.gitignore
.gitignore
 
 
README.md
README.md
 
 

README.md

MUNCH (Crypto 750)

Description

Munch out the bits!

Flag

CODEGATE2020{5e7c462214d48ea48045add289f70b0619a0552bdd4201d8c20cedbfd9ce43cd}

Challenge setup

Deploy chall.py and output which is in binary_flag directory.

If you want to generate different output, simply run the below command in prob_src directory(obviously replace the output file :D).

python3 chall.py > output

Exploit

Outline

Two stages:

  • Stage 1
    • Solve the hidden number problem by knowing the bit length of hidden numbers(exposed as output)
    • Solve four times to recover four bit chunks of RSA prime p.
  • Stage 2
    • Apply generalized coppersmith attack. See the entire paper here.

Vulnerability

I gave bitlength of hidden four chunks. Also, I gave 200 / 4 = 50 queries(which exposes information of each chunks) to solve the hidden number problem. I tested that 50 queries are enough to fully recover each chunks.

Now the chunks are prepared to recover entire RSA prime p. Recover p and decrypt ciphertext to get flag.

External Writeups