Skip to content

Latest commit

 

History

History

Cloud9

Folders and files

NameName
Last commit message
Last commit date

parent directory

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

README.md

Cloud9 (Crypto 608)

Description

We've been tricked, we've been backstabbed and we've been quite possibly, bamboozled.

Flag

CODEGATE2020{Here_comes_the_crypto_genius}

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).

sage chall_debug.sage | tee output

WARNING: Do not run chall.sage. random_point() method is currently not implemented in sage(over composite ring). So I implemented myself(basically decryption of rabin cryptosystem) at chall_debug.sage. It is intended to use this function, and players are desired to overcome the situation.

# Not Implemented, but you get the point :D
self.G = E.random_point()

Exploit

  • P0 = P1 & ord('?')
  • Q0 = Q1 & ord('?')
  • ord('?') == 0b00111111
  • ECDLP over integer ring of composite n = P0 * Q0
    • n is small and brutable
  • ECDLP over integer ring of composite N = P1 * Q1
    • Give order of ECC defined over integer modulo P0
    • Coppersmith attack feasible because of Hasse’s theorem
      • Still need to brute 5 lsbs: known because P0 known
  • Now we know P1, Q1
  • ECDLP over P1
    • Order of Elliptic curve will have small factors
    • Solve ECDLP by pohlig hellman, with a slight twist(ignoring big factors by estimating solution size)
  • ECDLP over Q1
    • Order of Elliptic curve == Q1: Anomalous case
    • Smart’s attack: tear down ECDLP to additive group which solving DLP is trivial
  • Combination of solving ECDLP over finite field generated by integer mod P1, Q1
    • Use CRT to combine the results to solve ECDLP over integer modulo N

External Writeups

  • TBD