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
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.
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)))
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.
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)
# 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.
for key_len in range(1, 50):print("Try key length", key_len)all_key_pos_valid = Truefor key_pos in range(key_len):print("Position", key_pos, ": ", end="")enc_slice = enc[key_pos::key_len]key_pos_valid = Falsefor 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 = Trueprint(f"{key} ", end="")print()if not key_pos_valid:all_key_pos_valid = Falseif all_key_pos_valid:print("Key length", key_len, "is possible")breakprint()
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")
.
from collections import Counterspace_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())
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.
from itertools import cyclepln = bytes([i ^ jfor 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:])
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 oftail: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
(2740898742966601935114133183106529, 956157655799717714864508073016211621761609346753693883071835634336701162346899667843127478623689609421921959757635162027164435651849444039861798305449805669806060897098677034940051454923858123316418111771244842263136200150949)(4681515083705154508573047498744706, 8137729467373933116892508790883965853824225864544185629594304843306928863961691391715058478012421229999432914675335993933647800020626034683613711997688036772875553560302624022039862210798719189229119735618787699810723188634719)(713083567420521725647105281913383, 4380455310144784872605974709167150361708365833979536574950088299593054964905207611091625844071796262320158274849703026573280865132707680730814638177402685313693168998262565678693098484143079216308958193534983606222931969247)
We get a text file with three shares of a Shamir's Secret Sharing key and need to find the secret.
The sizes of is suspiciously small.
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())
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 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.
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()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 = yrhs = 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))
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
#!/usr/bin/pythonfrom Crypto.Util.number import bytes_to_longfrom secret import flag# parametersBASE = 2MODULUS = 0xfffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001print( pow(BASE, bytes_to_long(flag), MODULUS) )
Challenge file output
4275333096397007849067777941008675457617279615546105194323216811550797075772016607215703868747693795339025886078058526791464546941731743196384839138407576
Given that 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 .
modulus = 0xfffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001enc = 4275333096397007849067777941008675457617279615546105194323216811550797075772016607215703868747693795339025886078058526791464546941731743196384839138407576p = 2^256 + 2^192 + 2^96 - 2^224 - 1assert p^2 == modulusprint("modulus bits:", modulus.nbits())print("p bits :", p.nbits())
modulus bits: 512p bits : 256
The multiplicative order of in divides . 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.
large_p_minus_one_factor = 835945042244614951780389953367877943453916927241assert (p-1) % large_p_minus_one_factor == 0sub_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)
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 that is a product of two secret primes , after which encryptions are done modulo . The security of the system lies in the difficulty of factoring .
This challenge sounds like a paillier cryptosystem using only one prime (and with a fixed ). 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.
n = pnn = n^2lm = p - 1g = 2def L(x):# integer divisionreturn (ZZ(x) - 1) // nmu = 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
Paillier secret keylm: 115792089210356248762697446949407573530086143415290314195533631308867097853950mu: 78812824017716222166363941925380802771192279278247361315965095345324406579153Test pln: 7124Test enc: 5737727902519221468079395852768350568874602827815350243089325143035745759103407454635145636739342676688493617180231146002104121192021901346596740295748932Test dec: 7124
The one prime paillier cryptosystem with works! We can use this on the challenge ciphertext next.
from Crypto.Util.number import long_to_bytesdec = pow(enc, lm, nn)dec = L(dec)dec = ZZ(dec) * mu % nprint("dec :", dec)print("dec bytes:", long_to_bytes(int(dec)))
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 . Since the flag is 302 bits long while 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.
flag = CRT([dec, sub_pln], [n, sub_order])print("flag :", flag)print("flag bytes:", long_to_bytes(int(flag)))
flag : 13040004482819618304045499901471931824848159735015469323983519304523882287485236800384295549flag bytes: b'flag{1b8cdf523310e91a3790a5c938707f6b}'