MCH2022 CTF Crypto Writeups

qEXMRY^7
Sharing is caring
Squaring Off

qEXMRY^7

We found this encrypted text, could you convert it back to plaintext?

Attachment: qexmry^7.tgz

10 solves, 100 points

Challenge file CHALLENGEtext
16160027070008531b54170e0f04534f1b1d1152481d543c411a0c1249101c17163211534a491d0116484317001000451c54010b0648534173090116040c430a001f380b470f07094907070004410000411d19010b1507124e37410605190d1007081677134915001a06014400040f0748460e180416524e1d543c410f440506140a0a12234b0032010b490501530c150c1a000e0407091d401a5a36124244160707480c1d23174f021c0d0c0048480c0c100d4c09540916527701493d020b443f080d1b451c3145540e0c4e3a1c1d540d0411060026070400010953743b0e1b031f490206021625004446081a491501521615430a594f00000052441f553e12070a121a10480a1577114803491d1d01094e02041144002e1a0604524e000032151a16160a170d0153351c002e08001a54484115110609520e1a0b0052481d4336411d0c12490f091c00770d4514490b10161b000a0f430049025a48361a42534826131c0d121a4307031577124803074e1a1b0d000d04021a534f00000052441b5521020644150c0f04165d5d6f650a1a0f49010d4d04080d1b0001111a131d52000037141c0d190e431c0d1677064f1406000807014f0b41000d520a19070b0b0953743b044e061e1a0b07155325004d0f070a1a53004517411707001b1503005248154673090b16570e0f071316244542030f011b1648530d04431c4104111b450757534836134e031805070d0b533817424608000d531b430011170d524154200a1e431a4e34411a0c12044f48161b324554131b001a531c4f4507020b454f00000052441c4e34130b03161d0a070b5f77075512490f051e075311410a054d0a10010406421f597f411d0c1249100d0000771148034909061f0c000a0f431c480a5407171007005432131a440306430e171c241100091f0b1b5d48730d04431a451b011a0b0107074836410116154902060153240645161d0b1b53005517130a0d44030d48111d07074836410c0d04010c184953360b4446191b1d0048480013430f4c00020d16524512433841010a5b490d09170138124c1f490f1f161a540c0f044844060709160642010e596b2f10571d0b0d451038174f08081a001c06001704000d501b1d070b5e071c4e36410102571d0b0d450032175607071a1a53014e11130c0c550c111b45374b00417300000057280d060453230a0012010b49101a4f12054d4861011a09420107154921121a44111b0a0d0b173b1c000f071a0c01094311080c0600181d1c0d52621f533241070a5710060917007707520f07091a5319550c1506485407114801174b1a473b1508111b49050d001f3e0b47461d0149070045451111014e0c111b165e07154c26121a01050c07480407770349141a1a4553094e0141100d45061a0f45374b0041731201441f0813181c533e0b53120c0f0d5307464512061a4900011b451349170021041d01051f060c4511380a53121a4e281d06414212430b4f01120101174910457f411e161804131c0c1d304548031b4e1d1c48430a0f17014e1a11480a1c07044927094e101f0c430b0a1d21005215081a001c060e45350b0d5948060d451b49074521131b14030c0748041523005211081c0d0048421c41170045060648160642044121054e2f160043010b07250a44130a07071448540d04432c550411480a14072445200402101807431f0d1c770a46000c1c1a532d4c16004300451d540e0c00540700370000071249021b450222004508474e2c1f1b4145110c04491b11041c524316433f080001044917000053380346031b4249111d5445080d1b540a150c45024b1259351402080e4915070906391145031b1d4932064e044d4305550c1c48111d07074836412a111c0c441b451732094901011a491d074e00150b0d4c0a071b4952461d4473150601571d1407451b3204444606080f53014e110e4309000c1b050c11461f00370000071249100b001d324b0023051d08530b410b461748520a07011606071048260205081e0704481616320c4e01492f071d09000204174849011a07061749074c2a410808021a170d17163345421f491a01164864100a064f534f1b1e00000a0748364c1a0b07494b090b17770c4e051b0b0d1a0a4c1c41170d521d1d0a09170e5344320f0d0d190e431b0e1a3b095348493a011a1b000600161b451c54290b1c4653543c410801120543021000234541154919011a05530c020204000e1607100607074836410b0a0300110d451e361154031b42491507524512060d49011348201e5412003a0f4e17020a0b480453241141120c4e0000484145120a0f481b5a48241c49120021041a1105071048070a77204c1508491a531b4901044309461b111a12135517537f410d0b1a040606111a39020009074e011c1f0012040f04001b1c010b1554534832170b44150c06064514380c4e01491a010107550209431c480a540c040b0b53413d054e010f19110d16003216000e0c1c490401530d0410485400540004044253543b080003044917000053200459461d060c0a4857001306485407151c451c4e144827410f081b4917000053230c4d03474e2c1f1b4145050c0d534f150f17174253543b0e1b031f490b0d17532408490a0c4e1c1d0e4f17151606411b11041c5241124436124e0500081a44451239010015010b49010d4c100217094e1b18114516421d4936124e251907024f1653200c530e0c1d4912044c450017484f01170d45164200503a150b4411080a040c1d30455409490b110304410c0f431f48165a626f33491d4173000000572102061653230d4508491d0716094b450e050e001b1b481602421d4473150601570c150d0b1a3902001206090c070045174d431955061703090b070145320d071e1e070448111b32454d131d1b081f484111151109431b1d070b5245165424040b0a571d0b0d085d77314803491c061e094e11080048440e1a0b00524205453d151b051b051a480916360153461d0149120600000f1701520a540c0406425f0024081a0c571d0b0d4516391149140c4e071a0f4811410c0e001b1c0d450b48064e34410d0b02190f0d4511320c4e01491d1916065445030c0644061a0f4b526f124e204d4e00021b0a060253230d450f1b4e1d1a054545150c0f451b1c0d175e071f453213001757060548241d390407154902061d0f490b064307464f1c09131b491400200e030118070648160332064907054e001d4848001343044909114445054e074873090b16571a0a1b111625454116190f1b1606540918430c451911040a024e1d4773004e001e1a0f010e16770a46460b0b001d0f0004130c1d4e0b5400000007115973121b00130c0d041c53240d55121d07071448610b0f02484f1a00480a1c42534432184e131f0c0d48111b321c00110c1c0c53034901124d48680e1a1b451d57164e3f184e161205021c000077114f461d06000044000a0f0f110009011a111a4201493d064e251907024f1653340a4e080c0d1d1a074e45160a1c484f1c01085c073b413d124e101f0c0d481501380849150c1d490707000b04150d524f0700100607324e3d004e0b021d431d0b1f3e0e45462c021a12440008140000001b1b48111a42537021080007121a104f165336075309051b1d16484a0a184d622a2d0d48111a4253453d054e0b11491700001a254554091c1c490700520a1404004f1a0048111a42536b3a0f090018044f482d12391600161b01191c1b4516411707002e1a060452551a473b154e0b19491700005324154f124919011a0b4845120b0d0006190500164e1254360d1744160a000d15072445480f1a4e0f1f094745150c48480607480d1746015469410808160e180d5010310017540d5a504550435c035050455b4c5d561041111564595b53160b1e62

We get one text file containing a lot of hex characters. Converting from hex to bytes gets a garbage string, however it is interesting that all of them are in the 0-127 range.

python

with open("qme/CHALLENGE", "r") as f:
    raw = f.read()
enc = bytes.fromhex(raw)
print("First 25 decoded", enc[:25])
print("enc length:", len(enc))
print(
    "Min:", min(enc),
    "Max:", max(enc),
    "Unique:", len(set(enc))
)

output

First 25 decoded b"\x16\x16\x00'\x07\x00\x08S\x1bT\x17\x0e\x0f\x04SO\x1b\x1d\x11RH\x1dT<A"
enc length: 2803
Min: 0 Max: 127 Unique: 106

This seems like it may be a xor cipher with an ASCII key. We can try to brute force the xor key; a good key should have a decryption such that all plaintext is printable.

python

from string import printable
printable_set = set(printable.encode())

for key in range(128):
    pln = bytes([i ^ key for i in enc])
    if all([i in printable_set for i in pln]):
        print("Found key:", key)

output

# empty output

Single character key doesn’t work, how about multiple letter key? We can brute force different key lengths and split the ciphertext into key_len chunks by starting from different offsets and skipping key_len bytes each time. For each chunk we then try all possible xor keys to see which keys give valid output.

python

for key_len in range(1, 50):
    print("Try key length", key_len)
    all_key_pos_valid = True
    for key_pos in range(key_len):
        print("Position", key_pos, ": ", end="")
        enc_slice = enc[key_pos::key_len]
        key_pos_valid = False
        for key in range(128):
            pln_slice = [i ^ key for i in enc_slice]
            if all([i in printable_set for i in pln_slice]):
                key_pos_valid = True
                print(f"{key} ", end="")
        print()
        if not key_pos_valid:
            all_key_pos_valid = False
    if all_key_pos_valid:
        print("Key length", key_len, "is possible")
        break
    print()

output

Try key length 1
Position 0 :

Try key length 2
Position 0 :
Position 1 :

...

Try key length 11
Position 0 :
Position 1 :
Position 2 : 32 33 37 39
...
Position 9 :
Position 10 : 102 103 108 112 113

...

Try key length 33
Position 0 : 26 27 28 29 31 80 81 84 86 87 122 123 124 125 126
Position 1 : 98 100 101 102
Position 2 : 32 33 34 35 36 37 39 40 46 47 52 53 60 63 105 108 110 111
...
Position 31 : 96 97 98 100 101 102 103 107 109 112 121 122
Position 32 : 33 35 36 37 38 39 40 41 42 43 45 46 ...
Key length 33 is possible

A key of length 33 is possible, but we have too many candidate keys for each position. Lets assume that the plaintext is written english; the most common character should either be a space " " or lowercase "e". The most common encrypted character in each slice should then be key ^ ord(" ") or key ^ ord("e").

python

from collections import Counter

space_key = []
e_key = []
for key_pos in range(33):
    enc_slice = enc[key_pos::key_len]
    most_common_enc = Counter(enc_slice).most_common(1)[0][0]
    space_key.append(most_common_enc ^ ord(" "))
    e_key.append(most_common_enc ^ ord("e"))

print("Space key:", bytes(space_key).decode())
print("e key    :", bytes(e_key).decode())

output

Space key: We finish e$ch ;1her'sh?andwic-es
e key    : ? e#,+,6-e a&-e~t- 7b6-S$+!2,&h 6

From this, guess the xor key We finish each other's Sandwiches. Run the xor with the encrypted text in python (or with CyberChef) to get the flag.

python

from itertools import cycle

pln = bytes([
    i ^ j
    for i, j in zip(enc, cycle(b"We finish each other's Sandwiches"))
]).decode()

print("head:")
print(pln[:200])
print()
print("tail:")
print(pln[-200:])

output

head:
As Anna strolls out onto the streets, she crashes into a horse belonging to a charming
and handsome visitor, and falls into a rowboat. The visitor apologizes, and introduces
himself as Prince Hans of

tail:
s's absolute joy.

By the end of their tour throughout the Kingdom, Hans proposes to Anna right on the
spot which she immediately accepts his flag to his heart:
flag{e5cfe72d4968c9b38e4853bfb57857ab}

We would like to share a free flag with you! According to Shamir you need five shares, but we will only give you three ;) And we keep the modulus we used secret, all you get to know is that it is a random 1024-bit prime. The flag was converted to an integer via a function called bytes_to_long().

Attachment: sharingiscaring.tgz

16 solves, 200 points

Challenge file sharespython
(2740898742966601935114133183106529, 956157655799717714864508073016211621761609346753693883071835634336701162346899667843127478623689609421921959757635162027164435651849444039861798305449805669806060897098677034940051454923858123316418111771244842263136200150949)
(4681515083705154508573047498744706, 8137729467373933116892508790883965853824225864544185629594304843306928863961691391715058478012421229999432914675335993933647800020626034683613711997688036772875553560302624022039862210798719189229119735618787699810723188634719)
(713083567420521725647105281913383, 4380455310144784872605974709167150361708365833979536574950088299593054964905207611091625844071796262320158274849703026573280865132707680730814638177402685313693168998262565678693098484143079216308958193534983606222931969247)

We get a text file with three $(x, y)$ shares of a Shamir’s Secret Sharing key and need to find the secret.

The sizes of $y$ is suspiciously small.

python

shares = [
    (2740898742966601935114133183106529, 956157655799717714864508073016211621761609346753693883071835634336701162346899667843127478623689609421921959757635162027164435651849444039861798305449805669806060897098677034940051454923858123316418111771244842263136200150949),
    (4681515083705154508573047498744706, 8137729467373933116892508790883965853824225864544185629594304843306928863961691391715058478012421229999432914675335993933647800020626034683613711997688036772875553560302624022039862210798719189229119735618787699810723188634719),
    (713083567420521725647105281913383, 4380455310144784872605974709167150361708365833979536574950088299593054964905207611091625844071796262320158274849703026573280865132707680730814638177402685313693168998262565678693098484143079216308958193534983606222931969247)
]

for x, y in shares:
    print(
        "x bits:", x.bit_length(),
        "x**4 bits:", (x ** 4).bit_length(),
        "y bits:", y.bit_length()
    )

output

x bits: 112 x**4 bits: 445 y bits: 748
x bits: 112 x**4 bits: 448 y bits: 751
x bits: 110 x**4 bits: 437 y bits: 740

Though the challenge description says the secret sharing was done with a 1024 bit modulus, the $y$ values given are small. This suggests that the coefficients used are too small to reach our modulus. We can try to solve for the coefficients over the integers instead of over a prime field.

In this solution, I use z3 with added constraints that forces the secret to follow the flag format.

python

from Crypto.Util.number import bytes_to_long, long_to_bytes
from z3 import *

c0_min = bytes_to_long(b"flag{00000000000000000000000000000000}")
c0_max = bytes_to_long(b"flag{ffffffffffffffffffffffffffffffff}")

s = Solver()

coefs = [Int(f"c{i}")for i in range(5)]
for i in coefs:
    s.add(i > 0)
s.add(coefs[0] > c0_min)
s.add(coefs[0] < c0_max)

for x, y in shares:
    lhs = y
    rhs = sum([(x ** idx) * c for idx, c in enumerate(coefs)])
    s.add(lhs == rhs)

print(s.check())
model = s.model()
print(model)

pln = model[coefs[0]].as_long()
print(long_to_bytes(pln))

output

sat
[c1 = 9149973739832620057478847718776452909331856972029008300360177592450620034257795148944344951350371379,
    c2 = 21852324209882123490658179451915713008912172861754912704645862360748736081487467009914473423,
    c3 = 17225419049983238433022388253207352091968966615710375798758976424953462181144130648738420756,
    c4 = 16941721566856152254123570703807718073696708778985529143925939030871597271771646691833211826,
    c0 = 13040004482825156863985359800205430911225096100664137614933903523156378313952146898308838525]
b'flag{a729a11d2dc62daa300a8b9623057e44}'

Squaring Off

Discrete logarithms are hard, especially if the numbers are big enough. Can you still get the flag?

Attachment: squaringoff.tgz

5 solves, 300 points

Challenge file squaring_off.pypython
#!/usr/bin/python

from Crypto.Util.number import bytes_to_long
from secret import flag

# parameters
BASE = 2
MODULUS = 0xfffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001

print( pow(BASE, bytes_to_long(flag), MODULUS) )

Challenge file outputpython
4275333096397007849067777941008675457617279615546105194323216811550797075772016607215703868747693795339025886078058526791464546941731743196384839138407576

Given that $\texttt{enc} = 2^\texttt{m} \mod \texttt{modulus}$ and the values of modulus and enc, we need to find m.

modulus looks suspicious. Using factordb we find that modulus is a square of a prime. Lets call prime $p$ .

sage

modulus = 0xfffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001
enc = 4275333096397007849067777941008675457617279615546105194323216811550797075772016607215703868747693795339025886078058526791464546941731743196384839138407576

p = 2^256 + 2^192 + 2^96 - 2^224 - 1
assert p^2 == modulus
print("modulus bits:", modulus.nbits())
print("p bits      :", p.nbits())

output

modulus bits: 512
p bits      : 256

The multiplicative order of $2$ in $\mathbb{Z}_{p^2}$ divides $(p-1) \times p$ . $p-1$ also has several small factors, which means we can recover some of the flag from a Pohlig-Hellman attack. Unfortunately this is insufficient to get the whole flag.

sage

large_p_minus_one_factor =  835945042244614951780389953367877943453916927241
assert (p-1) % large_p_minus_one_factor == 0

sub_order = (p-1) // large_p_minus_one_factor
print("Subgroup order  :", sub_order)
print("Subgroup factors:", sub_order.factor())


Fmod = Zmod(modulus)
g = Fmod(2)

# limit to subgroup with small factors
g_subgroup = g ^ (p * large_p_minus_one_factor)
enc_subgroup = Fmod(enc) ^ (p * large_p_minus_one_factor)
sub_pln = discrete_log(enc_subgroup, g_subgroup)
print("Subgroup pln    :", sub_pln)

output

Subgroup order  : 138516389665330497628477975950
Subgroup factors: 2 * 3 * 5^2 * 17 * 257 * 641 * 1531 * 65537 * 490463 * 6700417
Subgroup pln    : 27351092750900760751899107099

Going on another line of thought, the problem of solving a discrete log modulo a square number sounds similar to the Paillier cryptosystem. Usually paillier keys use some $n$ that is a product of two secret primes $p \times q$ , after which encryptions are done modulo $n^2$ . The security of the system lies in the difficulty of factoring $n$ .

This challenge sounds like a paillier cryptosystem using only one prime $p$ (and with a fixed $r=1$ ). We can try to adapt the key deriviation, encryption and decryption procedures for a one-prime system. We test it on a toy example to make sure that the underlying math is still valid.

sage

n = p
nn = n^2
lm = p - 1
g = 2

def L(x):
    # integer division
    return (ZZ(x) - 1) // n

mu = pow(g, lm, nn)
mu = L(mu)
mu = pow(mu, -1, n)
mu = ZZ(mu)

print("Paillier secret key")
print("lm:", lm)
print("mu:", mu)
print()

test_pln = 7124
print("Test pln:", test_pln)

test_enc = pow(g, test_pln, nn)
print("Test enc:", test_enc)

test_dec = pow(test_enc, lm, nn)
test_dec = L(test_dec)
test_dec = ZZ(test_dec) * mu % n
print("Test dec:", test_dec)

assert test_pln == test_dec

output

Paillier secret key
lm: 115792089210356248762697446949407573530086143415290314195533631308867097853950
mu: 78812824017716222166363941925380802771192279278247361315965095345324406579153

Test pln: 7124
Test enc: 5737727902519221468079395852768350568874602827815350243089325143035745759103407454635145636739342676688493617180231146002104121192021901346596740295748932
Test dec: 7124

The one prime paillier cryptosystem with $n=p$ works! We can use this on the challenge ciphertext next.

sage

from Crypto.Util.number import long_to_bytes

dec = pow(enc, lm, nn)
dec = L(dec)
dec = ZZ(dec) * mu % n

print("dec      :", dec)
print("dec bytes:", long_to_bytes(int(dec)))

output

dec      : 88483470362263460524909064780378318774420006807869637806239247866181975950362
dec bytes: b'\xc3\x9f\xde\x95\x04\xcdP\x96310e90\xfa\xc6\xd5\xd1N\xc45c9387\x96\xa3\xc7\x9eD\x1a'

The paillier decryption will only decrypt $m \mod n$ . Since the flag is 302 bits long while $n$ is 256 bits, the plaintext is truncated. However, we can combine this with the result of the Pohlig-Hellman attack from earlier using CRT to get the full flag.

sage

flag = CRT([dec, sub_pln], [n, sub_order])
print("flag      :", flag)
print("flag bytes:", long_to_bytes(int(flag)))

output

flag      : 13040004482819618304045499901471931824848159735015469323983519304523882287485236800384295549
flag bytes: b'flag{1b8cdf523310e91a3790a5c938707f6b}'

MCH2022 CTF Crypto Writeups

qEXMRY^7

Sharing is caring

Squaring Off