ICMTC Crypto

Twilight

We encountered an image that contained some unkown characters. To analyze the cipher, I utilized the Symbols Cipher List on the dcode.fr website. It was determined that the cipher was the Hylian Language.

Decrypting the cipher yielded the following text: REVWALJHEHIDDWNPLAINSWCRWJMESSADE. By making slight adjustments to the text,

1
2


print("REVWALJHEHIDDWNPLAINSWCRWJMESSADE".replace("W", "E").replace("J", "T"))
# and replace the last D in MESSADE with G

Flag: EGCERT{REVEALTHEHIDDENPLAINSECRETMESSAGE}

Simple Cipher

Challenge

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


import os 

FLAG = open("flag.txt", "rb").read()
KEY = os.urandom(FLAG.index(b"{")+1)
def xor(plain):
    enc = b""
    for i, c in enumerate(plain):
        enc += int.to_bytes(c ^ KEY[i % len(KEY)])
    return enc.hex()    

print(xor(FLAG)) # out: 61bade96f3f7f36d90c29b92d1bb7b8aa9ba9692e61da2c9e3fefbb876dce0

Solution

The challenge uses XOR encryption alogrithm and a 7-byte key length. It loop through the plaintext and encrypting the first 7 bytes, then repeating the key from the beginning.

XOR is commutative means that a⊕b = b⊕a.
XOR is associative means that a⊕(b⊕c) = (a⊕b)⊕c = (a⊕c)⊕b.
If the plaintext was this_is_test and the key is key so the operation would be like
- this_is_test ⊕ keykeykeykey

The key length matching the length of the flag format, which is EGCERT{. Therefore, we can XOR the first 7 characters of the cipher with the flag format to obtain the key.

1
2
3
4
5


from pwn import xor
out = bytes.fromhex("61bade96f3f7f36d90c29b92d1bb7b8aa9ba9692e61da2c9e3fefbb876dce0")
known = b"EGCERT{"
key = xor(out[:7], known)
print(xor(out, key))

Flag: EGCERT{Im_H3r3_w4i71n9_T0_X0R!}

Easy Encryption

Challenge

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


from gmpy2 import next_prime
from Crypto.Util.number import getPrime,bytes_to_long
from random import randint
import os
from flask import Flask

app = Flask(__name__)
@app.route('/start/')
def decrypt():
    flag = os.environ.get("CTF_FLAG", "EGCTF{FAKE_FLAAAAAAAAAAAAG}")
    m1 = bytes_to_long(flag[:len(flag)//2])
    m2 = bytes_to_long(flag[len(flag)//2:])
    e = 0x10001
    z = getPrime(512)
    p1 = getPrime(512)
    q1 = next_prime(p1)
    n1 = p1*q1
    p2 = next_prime(q1)
    q2 = next_prime(p2)
    n2 = p2*q2
    n3 = n1 * n2
    n4 = q1 * getPrime(1024)
    c1 = (z * pow(m1,e,n3)) % n3 
    c2 = (m1*randint(1000,30000) * pow(m2,e,n4)) % n4
    
    return {'n1':int(n3) , 'n2':int(n4), 'c1':int(c1), 'c2':int(c2), 'z':int(z), 'e':int(e)}

@app.route('/')
def home():
	return "Hi!"

if __name__ == "__main__":
    app.run()

Solution

It took me too much time, nearly 1H, until i reialized that he sent n3, n4 instead of n1, n2 😂😂.
Let’s see, we have two equations

c₁ = (z * pow(m₁, e, n₃)) % n₃
c₂ = (m₁ * randint(1000,30000) * pow(m₂, e, n₄)) % n₄

let’s find a starting point, if look at app.py we will notice that

n₃ = n₁ * n₂ = = p₁ * q₁ * p₂ * q₂
n₄ = q₁ * RandomPrime

S0o0, n3 and n4 have a common factor which is q1. We can use Common Prime Attack to retrieve factors of the moduli.

If N1 and N2 have a common factor that is mean GCD(N1, N2) != 1
We can calculate P as the following
- p = GCD(N1, N2), q1 = N1 // p, and q2 = N2 // p

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


import requests
import json
vals = json.loads(requests.get("http://209.38.200.9:7715/start/").text)
n3, n4, c1, c2, z, e = vals['n1'], vals['n2'], vals['c1'], vals['c2'], vals['z'], vals['e']

n1 = GCD(n3, n4)
n2 = n3 // n1
n4_rand = n4 // n1
# print(n1 * n2 == n3)
# print(n4_rand * n1 == n4, isPrime(n4_rand), isPrime(n1))

Now we have n3 and n4 factors if we can get pow(m1, e, n3) and pow(m2, e, n4) then it will be easy to solve 🙂. Wait actuall we can !
We can retrieve pow(m1, e, n3) easily using Modular Division

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


from Crypto.Util.number import GCD, inverse, long_to_bytes, isPrime

def modDivide(a,b,m):
    a %= m
    inv = inverse(b,m)
    if(inv == -1):
        return -1
    else:
        return (inv*a) % m

# pow_m1_e_n3 = (c1 * inverse(z, n3)) % n3
pow_m1_e_n3 = modDivide(c1, z, n3)
phi = (n1 - 1) * (n2 - 1)
d = inverse(e, phi)
m1 = pow(pow_m1_e_n3, d, n1) # EGCERT{16500bc003f74b4ba6ef96

Now doing the same with pow(m2,e,n4), but we just need to brute force the RandomNumber randint(1000,30000)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


# randint(1000,30000) * pow(m2,e,n4)
rand_mul_pow_m2_e_n4 = modDivide(c2, m1, n4)

for i in range(1000, 30000+1, 1):
    pow_m2_e_n4 = modDivide(rand_mul_pow_m2_e_n4, i, n4)
    
    phi = (n4_rand - 1) * (n1 - 1)
    d = inverse(e, phi)
    m2 = pow(pow_m2_e_n4, d, n4)
    
    if len(long_to_bytes(m2)) < 50:
        print(long_to_bytes(m2))
        exit()

Full code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


import requests
import json
from Crypto.Util.number import GCD, inverse, long_to_bytes, isPrime
# from sage.all import *

def modDivide(a,b,m):
    a %= m
    inv = inverse(b,m)
    if(inv == -1):
        return -1
    else:
        return (inv*a) % m

'''
c1 = (z * pow(m1,e,n3)) % n3 
c2 = (m1 * randint(1000,30000) * pow(m2,e,n4)) % n4
'''

vals = json.loads(requests.get("http://209.38.200.9:7715/start/").text)
n3, n4, c1, c2, z, e = vals['n1'], vals['n2'], vals['c1'], vals['c2'], vals['z'], vals['e']

n1 = GCD(n3, n4)
n2 = n3 // n1
n4_rand = n4 // n1
# print(n1 * n2 == n3)
# print(n4_rand * n1 == n4, isPrime(n4_rand), isPrime(n1))

# pow_m1_e_n3 = (c1 * inverse(z, n3)) % n3
pow_m1_e_n3 = modDivide(c1, z, n3)
phi = (n1 - 1) * (n2 - 1)
d = inverse(e, phi)
# EGCERT{16500bc003f74b4ba6ef96 
m1 = pow(pow_m1_e_n3, d, n1)

# randint(1000,30000) * pow(m2,e,n4)
rand_mul_pow_m2_e_n4 = modDivide(c2, m1, n4)

for i in range(1000, 30000+1, 1):
    pow_m2_e_n4 = modDivide(rand_mul_pow_m2_e_n4, i, n4)
    
    phi = (n4_rand - 1) * (n1 - 1)
    d = inverse(e, phi)
    m2 = pow(pow_m2_e_n4, d, n4)
    
    if len(long_to_bytes(m2)) < 100:
        print(long_to_bytes(m2))
        exit()
    
print("Failed")

Bad Mode

Challenge

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


from flask import Flask
import os
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import codecs

KEY = os.urandom(16)
app = Flask(__name__)

@app.route('/decrypt/<ciphertext>/')
def decrypt(ciphertext):
    ciphertext_bytes = codecs.decode(ciphertext, "hex")
    decrypted = AES.new(KEY, AES.MODE_CBC, KEY).decrypt(ciphertext_bytes)
    return codecs.encode(decrypted, "hex").decode()

@app.route('/encrypt/<plaintext>/')
def encrypt(plaintext):
    plaintext_bytes = codecs.decode(plaintext, "hex")
    encrypted = AES.new(KEY, AES.MODE_CBC, KEY).encrypt(plaintext_bytes)
    return codecs.encode(encrypted, "hex").decode()

@app.route('/check_key/<user_key>/')
def check_key(user_key):
    FLAG = os.environ.get("FLAG")
    FLAG = pad(FLAG.encode(), 16)
    user_key_bytes = codecs.decode(user_key, "hex")
    return codecs.encode(FLAG, "hex").decode() if user_key_bytes == KEY else "Try Again !!"

@app.route('/')
def home():
    return "Hi!"

if __name__ == "__main__":
    app.run()

Solution

Using the key as an IV is insecure; an attacker that can modify ciphertext in flight can get the receiver to decrypt a value that will reveal the key. [Here you can find a better explanation]

encrypt the message that is at least 3 blocks long
- AES-CBC(P_1, P_2, P_3) -> C_1, C_2, C_3
Modify the message (you are now the attacker)
- C_1, C_2, C_3 -> C_1, 0, C_1
Decrypt the message (you are now the receiver) and raise the appropriate error if high-ASCII is found.
As the attacker, recovering the plaintext from the error, extract the key:
- P’_1 XOR P’_3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


import requests
import json
from Crypto.Util.number import bytes_to_long

url = "http://209.38.200.9:7710/"

def decrypt(cipher):
    new_url = url + "decrypt" + "/" + cipher + "/"
    res = requests.get(new_url)
    return res.text

def encrypt(plaintext):
    new_url = url + "encrypt" + "/" + plaintext + "/"
    res = requests.get(new_url)
    return res.text

def check_key(key):
    new_url = url + "check_key" + "/" + key + "/"
    res = requests.get(new_url)
    return res.text

# any plaintext
plaintext = (b'a'*(16*3)).hex()

# decrypt the plaintext
# we get c1 -> c2 -> c3
response_cipher = encrypt(plaintext)
response_cipher = json.loads(response_cipher)
cipher = response_cipher['ciphertext']

# Modify the message
# C_1, C_2, C_3 -> C_1, 0, C_1
fake_cipher = cipher[:32] + '0'*32 + cipher[:32]

# we get the fake plaintext
response_plain = decrypt(fake_cipher)
response_plain = json.loads(response_plain)
fake_plain = bytes.fromhex( response_plain['error'][19:] )

# the length of fake_plain is 48
# As the attacker, recovering the plaintext from the error, extract the key:
# P'_1 XOR P'_2
iv = [0]*16
for i in range(len(iv)):
   iv[i] = fake_plain[i] ^ fake_plain[32+i] 

key = bytes(iv).hex()

response_flag = check_key(key)
response_flag = json.loads(response_flag)

Sign Gate

RSA has a homomorphic property. First, we need to understand what homomorphic means and how we can utilize this property to sign our message

What is homomorphic encryption

It’s property that allows performing certain operations on encrypted data, resulting in equivalent operations on the plaintext when decrypted.

Multiplicative homomorphism specifically means that given the encrypted values of two plaintexts, it is possible to compute the encryption of their product without decrypting them.

RSA, does not possess full multiplicative homomorphism. However, it does have a limited form of homomorphic property with respect to multiplication.

How we can utilize this

The rules of exponents say that (a)ⁿ * (b)ⁿ = (ab)ⁿ. This means that multiplying two ciphertexts encrypted with the same key is equivalent to raising the product of the plaintexts to the power of the secret key. Therefore, RSA is multiplicatively homomorphic. [1]

c₁c₂ mod N = m₁^dm₂^d mod N = (m₁m₂)^d mod N

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse, long_to_bytes
key = RSA.generate(2048)

msg1 = bytes_to_long(b"this_is_msg_1"); msg2 = bytes_to_long(b"test")
enc1 = pow(msg1, key.e, key.n);         enc2 = pow(msg2, key.e, key.n)

# first multiplying two ciphers
cipher_product = (enc1 * enc2) % key.n
# encrypt the cipher_product with the same key == product of two msgs
print(pow(cipher_product, key.d, key.n) == msg1 * msg2)

Think

Now Think about it, how can we sign our msg 🤔?

Solution

We need to get a msg_enc = pow(b'Crypt0N19h7'), d, n) but the server will not accept our msg s0o0oo, if we for example sign msg+b'\x00' which is bytes_to_long(msg)*256 we will have msg_mul_256_enc = pow(bytes_to_long(b'Crypt0N19h7\x00'), e, n) and sign (256), num_256_enc = pow((256), e, n)

msg_mul_256_enc = pow(bytes_to_long(b’Crypt0N19h7\x00’), e, n) = pow(bytes_to_long(b’Crypt0N19h7’) * 256, e, n)
num_256_enc = pow((256), e, n)
We can get pow(bytes_to_long(b’Crypt0N19h7’), e, n) using modular multiplicative inverse

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


from pwn import *
import ast
from Crypto.Util.number import bytes_to_long, inverse

def sign_msg(n):
  r.sendline(b"1")
  r.recvuntil(b'Enter message to sign: ')
  r.sendline(str(n).encode())
  val = int(r.recvuntil(b'=> ')[:-4].decode())
  return val

def check(n):
  r.sendline(b"2")
  r.recvuntil(b'Enter signature to verify: ')
  r.sendline(str(n).encode())

  print(r.recvline())
  print(r.recvline())

def modDivide(a,b,m):
  a %= m
  inv = inverse(b,m)
  if(inv == -1):
      return -1
  else:
      return (inv*a) % m

r = remote('209.38.200.9', 7725)

x = r.recvuntil(b'=> ')

pub_key = ast.literal_eval(x[x.find(b"("):x.find(b")")+1].decode())
n, e = pub_key[0], pub_key[1]

msg = bytes_to_long(b"Crypt0N19h7")
msg *= 256 
# msg = b'Crypt0N19h7\x00'

msg_mul_256 = sign_msg(msg)
sign_256 = sign_msg(256)
msg_sign = modDivide(msg_mul_256, sign_256, n)

check(msg_sign)

Parameter Injection

We are allowed to send the parameters A, g, and p to Bob. This enables us to send a smooth number p, which allows us to apply the Pohlig-Hellman Attack.

What is smooth number

Smooth number is a number which can be written from small prime factors. Smooth number must be a prime so that we can use Pohlig-Hellman Attack, the use of a smooth prime is a crucial step in efficiently computing the discrete logarithm.

What is Pohlig-Hellman Attack

In the Pohlig-Hellman Attack, we aim to compute the discrete logarithm of a given value. Let’s say we have a generator g, a prime modulus p, and a public value A such that A ≡ g^a (mod p) for some unknown private exponent a.

It factoring the smooth prime p-1 into its prime factors. Let’s denote these prime factors as p_1, p_2, ..., p_k. For each prime factor p_i, we compute a partial discrete logarithm x_i using the Chinese Remainder Theorem (CRT) method.

By applying the CRT to the partial discrete logarithms, we can reconstruct the full discrete logarithm a modulo p-1. Once we have a, we can compute the shared secret key.

The use of a smooth prime* allows us to efficiently compute the partial discrete logarithms and apply the CRT to reconstruct the full discrete logarithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse, isPrime, getPrime
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
import hashlib
import json
from pwn import *

def repeat(n):
    x = 1
    for i in range(n):
        x *= getPrime(32)
    return x*2+1

def create_weak_prime(n):
    while True:
        x = repeat(n)
        if isPrime(x):
            print(x)
            break

def decrypt_flag(shared_secret, iv, ciphertext):
    key = hashlib.sha1(str(shared_secret).encode()).hexdigest()[:16].encode()
    cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(iv))
    decrypted_data = cipher.decrypt(bytes.fromhex(ciphertext))
    plaintext = unpad(decrypted_data, 16).decode()
    return plaintext


conn = remote('209.38.200.9', 7720)

conn.recvuntil(b"Intercepted from Alice: ")
alice = json.loads(conn.recvuntil(b"}"))
p = alice['p']
g = alice['g']
A = alice['A']

conn.recvuntil(b"Intercepted from Bob: ")
bob = json.loads(conn.recvuntil(b"}"))
B = bob['B']

conn.recvuntil(b"Intercepted from Alice: ")
alice_iv = json.loads(conn.recvuntil(b"}"))
iv = alice_iv['iv']
encrypted_flag = alice_iv['encrypted']

fake_p = create_weak_prime(64)

val = json.dumps({"p":fake_p, "g":g, "A":A})
conn.recvuntil(b"Bob connects to you, send him some parameters:\n")
conn.sendline(val.encode())

conn.recvuntil(b"Bob says to you: ")
bob2 = json.loads(conn.recvuntil(b"}"))
B2 = bob2['B']

'''
Discrete logarithm calculator https://www.alpertron.com.ar/DILOG.HTM
Base: g = 2
Power: B2
Modulus: fake_p
'''
b = discrete_log(fake_p, B2, g)
shared_secret = pow(A, b, p)
print(decrypt_flag(shared_secret, iv, encrypted_flag))

ICMTC Crypto

All Cryptography's challenge write-ups. ⭐⭐⭐⭐⭐

Twilight

Simple Cipher

Challenge

Solution

Easy Encryption

Challenge

Solution

Bad Mode

Challenge

Solution

Sign Gate

What is homomorphic encryption

How we can utilize this

Think

Solution

Parameter Injection

What is smooth number

What is Pohlig-Hellman Attack

See Also