Skip to content

Latest commit

 

History

History

Polynomials

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

Polynomials (Crypto 810)

Description

Something is wrong...

Flag

CODEGATE2020{86f94100f760b45e9c0f6925f5b474b24387ff6be5732ab88d74b4bfbff35951}

Challenge setup

Deploy chall.sage 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).(Do not run chall.sage). It is because the polynomials(secret.py: secret, public keys for the cryptosystem) are meticulously chosen.

sage chall_genoutput.sage > output

Exploit

Outline

  • 16 bytes are generated from urandom, which will be the key of AES-CBC encryption
  • The key will be divided to two equilengthed chunks(8 bytes)
  • Each key chunk will be encrypted by plain NTRUEncrypt cryptosystem.
  • Publickey and encrypted result will be given to user, with additional information(number of positive/negative/zero coeffients of private key polynomial)
  • Given setup will be broken by LLL.

Vulnerability

  • Public keys are selected to make the given cryptosystem broken by LLL algorithm
    • See section 4 in this paper.
  • First break the NTRUEncrypt cryptosystem, recover key for AES and decrypt and get profit.

External Writeups