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