Gonna-Lift-Em-All

Background

Quick, there’s a new custom Pokemon in the bush called “The Custom Pokemon”. Can you find out what its weakness is and capture it?

Difficulty: Easy

Overall difficulty for me: Very hard

In this challenge, we can download a file:

┌──(root🌸siunam)-[~/ctf/HackTheBoo/Crypto/Gonna-Lift-Em-All]
└─# unzip crypto_gonna-lift-em-all.zip 
Archive:  crypto_gonna-lift-em-all.zip
   creating: gonna-lift-em-all/
  inflating: gonna-lift-em-all/chall.py  
  inflating: gonna-lift-em-all/data.txt

┌──(root🌸siunam)-[~/…/HackTheBoo/Crypto/Gonna-Lift-Em-All/gonna-lift-em-all]
└─# file *                                                    
chall.py: Python script, ASCII text executable, with CRLF line terminators
data.txt: ASCII text, with very long lines (633), with CRLF line terminators

Find the flag

chall.py:

from Crypto.Util.number import bytes_to_long, getPrime
import random

FLAG = b'HTB{??????????????????????????????????????????????????????????????????????}'

def gen_params():
  p = getPrime(1024)
  g = random.randint(2, p-2)
  x = random.randint(2, p-2)
  h = pow(g, x, p)
  return (p, g, h), x

def encrypt(pubkey):
  p, g, h = pubkey
  m = bytes_to_long(FLAG)
  y = random.randint(2, p-2)
  s = pow(h, y, p)
  return (g * y % p, m * s % p)

def main():
  pubkey, privkey = gen_params()
  c1, c2 = encrypt(pubkey)

  with open('data.txt', 'w') as f:
    f.write(f'p = {pubkey[0]}\ng = {pubkey[1]}\nh = {pubkey[2]}\n(c1, c2) = ({c1}, {c2})\n')


if __name__ == "__main__":
  main()

data.txt:

p = 163096280281091423983210248406915712517889481034858950909290409636473708049935881617682030048346215988640991054059665720267702269812372029514413149200077540372286640767440712609200928109053348791072129620291461211782445376287196340880230151621619967077864403170491990385250500736122995129377670743204192511487
g = 90013867415033815546788865683138787340981114779795027049849106735163065530238112558925433950669257882773719245540328122774485318132233380232659378189294454934415433502907419484904868579770055146403383222584313613545633012035801235443658074554570316320175379613006002500159040573384221472749392328180810282909
h = 36126929766421201592898598390796462047092189488294899467611358820068759559145016809953567417997852926385712060056759236355651329519671229503584054092862591820977252929713375230785797177168714290835111838057125364932429350418633983021165325131930984126892231131770259051468531005183584452954169653119524751729
(c1, c2) = (159888401067473505158228981260048538206997685715926404215585294103028971525122709370069002987651820789915955483297339998284909198539884370216675928669717336010990834572641551913464452325312178797916891874885912285079465823124506696494765212303264868663818171793272450116611177713890102083844049242593904824396, 119922107693874734193003422004373653093552019951764644568950336416836757753914623024010126542723403161511430245803749782677240741425557896253881748212849840746908130439957915793292025688133503007044034712413879714604088691748282035315237472061427142978538459398404960344186573668737856258157623070654311038584)

Oh boi, looks like we have to do some math.

Let’s break down the chall.py first!

In the main() function, pubkey and privkey is assigned by function gen_params():

Function gen_params()
- p = Random 1024 bit prime number
- g = Random integer between 2 to p - 2
- x = Random integer between 2 to p - 2
- h = g ** x %(modulo) p
- After running this function, we’ll get the value of pubkey and privkey

After running the function gen_params(), c1 and c2 will be assigned by function encrypt(pubkey), and it needs pubkey as an argument:

Function encrypt(pubkey)
- p, g and h = The value of pubkey
- m = Convert the FLAG string to a long integer
- y = Random integer between 2 to p - 2
- s = h ** y %(mod) p
- After running this function, we’ll get the value of: (g * y % p, m * s % p)

After finishing the encrypt(pubkey) function, it’ll open data.txt, and write:

p = pubkey index 0
g = pubkey index 1
h = pubkey index 2
c1, c2 = c1, c2

Armed with the above information, let’s backup the data.txt, as it’ll overwrite the real flag content if we run chall.py again.

┌──(root🌸siunam)-[~/…/HackTheBoo/Crypto/Gonna-Lift-Em-All/gonna-lift-em-all]
└─# mv data.txt data.txt.bak

To decrypt the flag(data.txt.bak), we need to find the value of:

In the data.txt.bak, we can see the value of:

pubkey (p, g, h)

p = 163096280281091423983210248406915712517889481034858950909290409636473708049935881617682030048346215988640991054059665720267702269812372029514413149200077540372286640767440712609200928109053348791072129620291461211782445376287196340880230151621619967077864403170491990385250500736122995129377670743204192511487

g = 90013867415033815546788865683138787340981114779795027049849106735163065530238112558925433950669257882773719245540328122774485318132233380232659378189294454934415433502907419484904868579770055146403383222584313613545633012035801235443658074554570316320175379613006002500159040573384221472749392328180810282909

h = 36126929766421201592898598390796462047092189488294899467611358820068759559145016809953567417997852926385712060056759236355651329519671229503584054092862591820977252929713375230785797177168714290835111838057125364932429350418633983021165325131930984126892231131770259051468531005183584452954169653119524751729

Ciphertext (c1, c2)

(c1, c2) = (159888401067473505158228981260048538206997685715926404215585294103028971525122709370069002987651820789915955483297339998284909198539884370216675928669717336010990834572641551913464452325312178797916891874885912285079465823124506696494765212303264868663818171793272450116611177713890102083844049242593904824396, 119922107693874734193003422004373653093552019951764644568950336416836757753914623024010126542723403161511430245803749782677240741425557896253881748212849840746908130439957915793292025688133503007044034712413879714604088691748282035315237472061427142978538459398404960344186573668737856258157623070654311038584)

Then, we can write a python script to reverse that encryption process:

#!/usr/bin/env python3

from Crypto.Util.number import long_to_bytes
import gmpy2

# p, g, h, c1, c2 values from data.txt
p = 163096280281091423983210248406915712517889481034858950909290409636473708049935881617682030048346215988640991054059665720267702269812372029514413149200077540372286640767440712609200928109053348791072129620291461211782445376287196340880230151621619967077864403170491990385250500736122995129377670743204192511487
g = 90013867415033815546788865683138787340981114779795027049849106735163065530238112558925433950669257882773719245540328122774485318132233380232659378189294454934415433502907419484904868579770055146403383222584313613545633012035801235443658074554570316320175379613006002500159040573384221472749392328180810282909
h = 36126929766421201592898598390796462047092189488294899467611358820068759559145016809953567417997852926385712060056759236355651329519671229503584054092862591820977252929713375230785797177168714290835111838057125364932429350418633983021165325131930984126892231131770259051468531005183584452954169653119524751729
(c1, c2) = (159888401067473505158228981260048538206997685715926404215585294103028971525122709370069002987651820789915955483297339998284909198539884370216675928669717336010990834572641551913464452325312178797916891874885912285079465823124506696494765212303264868663818171793272450116611177713890102083844049242593904824396, 119922107693874734193003422004373653093552019951764644568950336416836757753914623024010126542723403161511430245803749782677240741425557896253881748212849840746908130439957915793292025688133503007044034712413879714604088691748282035315237472061427142978538459398404960344186573668737856258157623070654311038584)

# Find the value of y, then we can calculate s
y = gmpy2.divm(c1, g, p)

# Found y's value, calculate s, then we can calculate m, which is the encrypted flag
s = pow(h, y, p)

m = gmpy2.divm(c2, s, p)

# Use long_to_bytes to convert to a byte string
flag = long_to_bytes(m).decode('UTF-8')
print(flag)

Output:

┌──(root🌸siunam)-[~/…/HackTheBoo/Crypto/Gonna-Lift-Em-All/gonna-lift-em-all]
└─# python3 solve.py
HTB{b3_c4r3ful_wh3n_1mpl3m3n71n6_cryp705y573m5_1n_7h3_mul71pl1c471v3_6r0up}

Conclusion

What we’ve learned:

Decrypting Encrypted Message via Basic Modular Arithmetic