blog > MCH2022 CTF Crypto
2022 Jul 26ctfcrypto

# MCH2022 CTF Crypto

## qEXMRY^7

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

Attachment: qexmry^7.tgz

10 solves, 100 points

Challenge file CHALLENGE
TEXT
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: 2803Min: 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 printableprintable_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 1Position 0 :
Try key length 2Position 0 :Position 1 :
...
Try key length 11Position 0 :Position 1 :Position 2 : 32 33 37 39...Position 9 :Position 10 : 102 103 108 112 113
...
Try key length 33Position 0 : 26 27 28 29 31 80 81 84 86 87 122 123 124 125 126Position 1 : 98 100 101 102Position 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 122Position 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-ese 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 charmingand handsome visitor, and falls into a rowboat. The visitor apologizes, and introduceshimself as Prince Hans of
tail:s's absolute joy.
By the end of their tour throughout the Kingdom, Hans proposes to Anna right on thespot which she immediately accepts his flag to his heart:flag{e5cfe72d4968c9b38e4853bfb57857ab}

## Sharing is caring

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 shares
PYTHON
(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: 748x bits: 112 x**4 bits: 448 y bits: 751x 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_bytesfrom z3 import *
c0_min = bytes_to_long(b"flag{00000000000000000000000000000000}")c0_max = bytes_to_long(b"flag{ffffffffffffffffffffffffffffffff}")
s = Solver()
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.py
PYTHON
#!/usr/bin/python
from Crypto.Util.number import bytes_to_longfrom secret import flag
# parametersBASE = 2MODULUS = 0xfffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001
print( pow(BASE, bytes_to_long(flag), MODULUS) )
Challenge file output
PYTHON
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 = 0xfffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001enc = 4275333096397007849067777941008675457617279615546105194323216811550797075772016607215703868747693795339025886078058526791464546941731743196384839138407576
p = 2^256 + 2^192 + 2^96 - 2^224 - 1assert p^2 == modulusprint("modulus bits:", modulus.nbits())print("p bits      :", p.nbits())
OUTPUT
modulus bits: 512p 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 =  835945042244614951780389953367877943453916927241assert (p-1) % large_p_minus_one_factor == 0
sub_order = (p-1) // large_p_minus_one_factorprint("Subgroup order  :", sub_order)print("Subgroup factors:", sub_order.factor())

Fmod = Zmod(modulus)g = Fmod(2)
# limit to subgroup with small factorsg_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  : 138516389665330497628477975950Subgroup factors: 2 * 3 * 5^2 * 17 * 257 * 641 * 1531 * 65537 * 490463 * 6700417Subgroup 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 = pnn = n^2lm = p - 1g = 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 = 7124print("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 % nprint("Test dec:", test_dec)
assert test_pln == test_dec
OUTPUT
Paillier secret keylm: 115792089210356248762697446949407573530086143415290314195533631308867097853950mu: 78812824017716222166363941925380802771192279278247361315965095345324406579153
Test pln: 7124Test enc: 5737727902519221468079395852768350568874602827815350243089325143035745759103407454635145636739342676688493617180231146002104121192021901346596740295748932Test 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      : 88483470362263460524909064780378318774420006807869637806239247866181975950362dec 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      : 13040004482819618304045499901471931824848159735015469323983519304523882287485236800384295549flag bytes: b'flag{1b8cdf523310e91a3790a5c938707f6b}'