Hex-Rays Challenge madame Solution
一、背景
北京时间2023年12月1日7时，Hex-Rays的madame挑战提交落下帷幕。是时候给出题解了。
比赛介绍在这里查看。
比赛附件在这里下载。
文件SHA-256为557e35b4f76a5816ded40961e6b43f81a9bcc3da9a6402157681934b852b412f。
运行文件，初步得知挑战分为四关。
二、第一关：Hastad广播攻击
第一关考查Hastad广播攻击。由于涉及公钥密码数学知识，实际上这一关最靠前但也最困难。
这一关给出$c_1$、$n_1$、$c_2$、$n_2$、$c_3$、$n_3$，并且有公共的$e = 3$。
我们需要掌握以下数学知识。
$N = n_1n_2n_3$
$N_1 = \frac{N}{n_1}$
$N_2 = \frac{N}{n_2}$
$N_3 = \frac{N}{n_3}$
$d_1 = N_1^{-1} \pmod{n_1}$
$d_2 = N_2^{-1} \pmod{n_2}$
$d_3 = N_3^{-1} \pmod{n_3}$
$c = c_1N_1d_1 + c_2N_2d_2 + c_3N_3d_3 \pmod{N}$
$m = \sqrt[e]{c}$
不难编写解题脚本。
import gmpy2
from Crypto.Util.number import long_to_bytes
c1 = 0x7D9E6B093218080A5A34349C0DB3C3C986B102D98C14CDA70BB241B5A838394CABB132D9789DEADE34CA28A3967B77E1DA56C428F40C7D601BE4AE2CB98FEE1B8C8DCB22EEEDFC4BB6462A9C24D4FD45854D5DC04F58E5BC701B6CAC9ED6D02BA05B8935C7FE26F84086CD49D0D66BCB6575AAA791F81BE84768B5961F3FF105EE5EC56FCDAF46A1C7369DD4D58ECD2CE28C7ABB0F35E0DC0752A11B8916969AF491F6BAAFBFFE0877FAE05BA18D6DAF385BCCD88951D72E6B8A4CCCA00FA3BF451F512EAEBF8A20BAAD68E04CAAE68B8FA1DBCBD1AE377B5CF26A7C90B6348569036D76D838B5BCD0E6C423581265EDCCF32279A0B629FAB0FCD485A38B4205
n1 = 0x8E449627141446D50A3BFAB5D9FC0D58C6B9F64630D011CB5C831C5989402DE1F553AE70C9F8DDEFB42F001E553FE7D852BB08CEC6EFEBE490EB40C91955B020159C66836A5D7D5364DA7CAB32DEFF4EA6EC1E41BDDA7B7C298DA68D4BE77E4750BF86D5D24ED67511BB37A105BC4DA0E3EC0CD4960A1AE2986FD402101061D290F292030BCF21A38D77DBDE760D01A3FAAA210E34A4E471FA0EAC5518D2F01FAA70659F582A9E211FF6B438B0BB1ABB49F4BB458ACEFD7BBCC8F68ED7CD121BF16AD1D5E0CD5384B4E3441DE7D5EC3C10C52ED9263FFE3C6AF5BA508F0B774E932DECE2F84C053F972CA31A68C1CD13668DB6ADB3E2320C93A0B06AE1737AD9
c2 = 0x67512E54FF9CD853AB645A69EC8F64009FAD60EEE84CE5D9A5DB8754813D5F9C9C038DA9476CAF9F1B543A289613D02A4ADDC2948B94A965B2DCE0CB93B771236A7F1CF879C86C4F9C07F26BBBD773A7D9EDF6B3981E4F96F355ECDD7407506672E5025EC2C915CA1D5F35D1CCC35679AFF91B833A07FC6BFAD06C9ACF053870E5F52D3DC8F1757355EA4C8DA81D88C37D4B68EBE50274566CB683C19CF5FA6D8851F92D9F9ABD5FD0CBB67551C3FA2018555B9A2995DA96443D9746399FBB86ACA121FE4EBE97D8468DB22A0BD087A1E3FC289C5633157BDC0BCD677FAA26B1FA4BE84285A408EDD28E48AB47535465DCE281111B0B70855CAE188AA6FDAA85
n2 = 0x678DCC64CCF7C29FFE64838A80196BD90B2D6247E4D712CB60C6A4A3A09AC088B9D1B19518451CE1A295CA6134A65CB5176083849E11CEA23CF5D6C303EE95D02F1AF26F741131D03C4E86866E26B09069C0BE5C718298ED1CFC01493D78520957E25C2D921F6B6518EF5EF608E209D4D9AD613FDB6A2EB4156C906C89583949CA076312C6A258F14794EE852A61F27FE2A6B17B1EA85DE3E40A2636FC4430E920ED8DC688AEBDB6F5E63140F7844F3597C82704545C308A36E20EB94E00B35EAEE860835C2F213956BFB79BB17D9B914524A5B133BE5AF4667CA0710420CA6BD90C28761BA1D52ED7D83D927245F53D45B35F2F1729FF602271ABB0EBF7CE5B
c3 = 0x1B48F3DE27DB0A80FFA291B161FFE9CA6CEE79DB559C8047579920CB23C130311A366F8561EE5966EE0A72293671C3587074011759DE78B837B676303C0179DB6CFC6E5D883835738249BC61F8EBC6A6CADE877EEE27F2F74C510F9AC6C723E53F76A8D45DB5D6918CEE530DB1A2102781A481CD0930875B5F40C61A35E685364C5EC883BF5899238EDDC22BA12CB58FCEE49E943C58B13F5CD893FF4C02CDB583EA3359CD26B8360A1873498B4D650C580E5F2EA31F2472A7F8D9A5EE30237C4ADDC4876961AB80F2923E807DBC319D7E4AAEC4C63E1402F68D9D11FF0365A70328E62AA5DA8F1D1B62035381B1A05744E78AB06D1D69BFD45EB41E4E902338
n3 = 0xB1B751BDEF5727862C0F6BDDCAA9802722B2499C760E02D7BB4C38629339194431DBEB41A6222E01DCA0FA8E792562CCC9BCF9C57549037A44EB4945DAF4440AC4F4AAB3BDF1566A3961C88E8CDB925870E68E9064354568335EEFC62344FDAC06593BDD8C4DC63C0AF932F5DAB986919F4ACB4B602896BA1896C3D0BC00A9BD6408A85E3E8766BFD44AF0AB151D3537C2B2955EEBE9CBCD6871146524253E14E374CDDA166E8B298932695C774AB8F8AC332A92FA49C91F65CE1A01B12E3D056990C954A3C6FA9346A67819BBC76D9CFBEBFF9810841810CCFDD3A3773CC24EAD32665B8E667B1B0B817F0BB3D8D7CA17342E6B2D024762E2ECBF897AF9CB15
e = 3
N = n1 * n2 * n3
N1 = N // n1
N2 = N // n2
N3 = N // n3
d1 = pow(N1, -1, n1)
d2 = pow(N2, -1, n2)
d3 = pow(N3, -1, n3)
c = (c1 * N1 * d1 + c2 * N2 * d2 + c3 * N3 * d3) % N
m, _ = gmpy2.iroot(c, e)
print("`" + long_to_bytes(m).decode() + "`")
得到第一关答案。
Head to the library. Upon entering, politely ask the librarian if they are aware of any extra documents refering to Madame De Maintenon.
三、第二关：按位异或运算
第二关考查按位异或运算。难度实际上比第一关简单。
我们需要掌握以下数学知识。
$c \oplus k = (m \oplus k) \oplus k = m$
因此直接按位异或即可。当然，也存在密文短于或长于密钥的情况。我们这里属于前者，直接丢弃多余的密钥即可。
不难编写解题脚本。
k = [0x44, 0x36, 0x63, 0xC8, 0x1C, 0x28, 0x84, 0xA0, 0x8D, 0x3A, 0x2F, 0x39, 0xF7, 0xEE, 0x92, 0x4F, 0xA7, 0xD5, 0xD3, 0x6C, 0x81, 0x8C, 0x4F, 0xCD, 0x37, 0x17, 0x89, 0xFC, 0xF9]
c = [0x07, 0x5E, 0x06, 0xAB, 0x77, 0x08, 0xE6, 0xCF, 0xE2, 0x51, 0x5C, 0x19, 0x98, 0x80, 0xB2, 0x3B, 0xCF, 0xB0, 0xF3, 0x02, 0xE4, 0xF4, 0x3B, 0xED, 0x44, 0x7F, 0xEC, 0x90, 0x9F]
m = [chr(c[i] ^ k[i]) for i in range(len(c))]
print("`" + "".join(m) + "`")
得到第二关答案。
Check books on the next shelf
四、第三关：算术和按位操作
第三关考查算术和按位操作。难度实际上比第二关多了小学数学。
我们需要掌握以下数学知识。
若$a + b = c$，则$a = c - b$。
若$a - b = c$，则$a = c + b$。
若$a \oplus b = c$，则$a = c \oplus b$。
不难编写解题脚本。
m = [98 - 15, 94 ^ 59, 154 - 57, 74 ^ 56, 23 ^ 116, 83 ^ 59, 35 - 3, 49 + 67, 113 - 9, 113 - 12, 122 - 90, 82 + 16, 234 - 123, 70 ^ 41, 236 + 127, 34 ^ 2, 186 - 84, 223 ^ 176, 216 - 102, 179 + 109, 67 ^ 32, 219 - 111, 141 - 24, 110 - 9, 163 - 48, 237 + 19, 195 + 61, 147 + 109, 138 + 118, 126 - 126, 42 - 42, 92 ^ 92]
print("`" + "".join([chr(i % 256) for i in m]) + "`")
得到第三关答案。
Search the book for clues
五、第四关：AES分组密码解密
第四关考查算术和按位操作。难度位居第二。
我们需要掌握以下数学知识。
$E_k(m) = c$
$D_k(c) = m$
这里的密钥实际上是第三关的答案。
不难编写解题脚本。
from Crypto.Cipher import AES
k = b"Search the book for clues".ljust(32, b"\0")
c = b"\x42\xBC\x23\x27\x0F\xF2\x36\x8C\x92\x17\xD9\xEF\x20\xAE\xDE\x57\x5D\x8E\xA4\x05\xFD\x0C\xCE\x09\xEA\x88\x43\xFE\x93\x3A\x99\x02"
m = AES.new(k, AES.MODE_ECB).decrypt(c)
print("`" + m.decode() + "`")
得到第四关答案。
Turn over the page
六、madame全貌
完整的输出如下。
You have heard rumours that the diary of Madame de Maintenon contained the secrets to a legendary plot.
Good luck on your journey to uncovering the truth behind this mystery!
You have heard that a rival historian recently discovered a copy of a chapter of the diary of Madame de Maintenon at the local library. But being unable to solve the mystery, returned it in frustration. Having long been fascinated by her history, you can't wait to investigate. What do you do?
You locate the section of the library where the diary was rumoured to have been stored, but its place is empty. After a few minutes browsing, you find it! A single page, but one that holds the key to a fascinating mystery.
The page reads:
_______________
21 October 1684
Dear Diary,
Today, an unsettling discovery came my way. A letter, it was, with ominous tidings of a plot against our cherished Louis XIV. The message was unlike any other, its meaning hidden behind unfamiliar symbols.
Within the letter lay a clue, 01000010, a piece of the puzzle. It hinted at more secrets, and I felt compelled to uncover them. But where to find the next piece?
Yours in devotion,
Madame De Maintenon
_______________
The page was lying on the shelf in the open, maybe it fell from somewhere. You see a few more loose pages sticking out of some other books around you. What happened here?
What do you do?
What luck! While going through the books on the next shelf over, you find another page stuck under them, similarly weathered to the first one. The message is hard to decipher due to it's age, but after some careful analysis you manage to decode it.
It reads:
_______________
24 October 1684
Beloved Diary,
As I delved into the code, a new piece surfaced, 00110111. It whispered of hidden truths, yet it also hinted that there was more to uncover. The puzzle remained incomplete.
Yours eternally,
Madame De Maintenon
_______________
Another clue, what could it mean? And where are the rest?
What do you do?
From the lack of dust on the book you found, it's clear these were recently borrowed. Maybe the pages got mixed up with the books when being reshelved?
You look up the name of the last borrower, and look up what other books they may have checked out. There you find the diary records mentioned, as well as one other book.
Finding that book on the shelves yields another page!
_______________
30 October 1684
Dearest Diary,
Another fragment emerged, 10110010. It was a step closer to the full picture, but it also held a hint. The rest of the location, it suggested, was not far away.
Yours eternally,
Madame De Maintenon
_______________
What do you do?
Turning the page over, you find the final entry to the diary!
_______________
9 November 1684
Beloved Diary,
Today, the last piece fell into place, 00000101. With it came the realization that the remaining location lay elsewhere, a mystery yet to be unraveled. Our mission is clear, my dear diary; we must decipher the rest to protect our homeland.
Yours in devotion,
Madame de Maintenon
_______________
What does this mean? You've worked so hard but yet still don't have the information you seek? What now?
You have all four pages your rival claimed to have found, and yet are no closer to the truth.
After several hours of fruitlessly searching for meaning in the messages, you give up and turn to leave in defeat.
As you move to leave, the librarian comes running!
'I found this in the back room for you, it was a page we found lying around after procesing the most recent batch of new books but we weren't sure what it was for! But look at the signature!'
She hands you a fifth, almost completely blank new page. The aging of the paper looks near identical to the other four pages you found from the diary!
All the page says on it is:
_______________
The other key:
01000000110111000011011000000000
M d. M
_______________
You thank the librarian, and take your leave. You have much to think on. All these 1's and 0's, how do they encode the location of the final target???
#########################
Congratulations! If you've found all 5 pages of the diary you have everything you need! Convert the values you found into coordinates, (hint: IEEE-754 Floating Point), and send those coordinates in an email to marketing@hex-rays.com!
To locally verify your coordinates, the md5 of the coordinates, with 4 decimal places, (including potential leading zeros) in the form:
xx.xxxx, yy.yyyy
Has an md5 of fe72f3730186f24d983a1c2ed1bc1da7 when pasted as a 16 character string into https://www.md5hashgenerator.com/
什么？IEEE-754浮点数是什么鬼？没关系即使我们不知道也不要紧。$10^{12}$完全在暴力枚举范围之内。
不难编写解题脚本。
import hashlib
for i in range(10**12):
s = "{:012}".format(i)
t = s[0:2] + "." + s[2:6] + ", " + s[6:8] + "." + s[8:12]
if hashlib.md5(t.encode()).hexdigest() == "fe72f3730186f24d983a1c2ed1bc1da7":
print(t)
break
开玩笑的。上述脚本不知道得算到什么时候呢，还得是正经做法。我们注意到题目里给了5组数字。
01000010
00110111
10110010
00000101
01000000110111000011011000000000
题目提示分别是x和y，那么便是32位浮点数了。因此将前4个8位二进制数依次拼起来，我们得到两个数。
01000010001101111011001000000101
01000000110111000011011000000000
转成十进制即可。答案便是45.9238, 06.8815。
至于怎么转换……
既可以机算。
不难编写解题脚本。
struct.unpack("f", struct.pack("i", x))[0]
也可以手算。
以01000010001101111011001000000101为例。
最左侧1位0代表符号。0也即正数。
中间8位10000100代表指数。10000100对应132，由于是移码，减去127得到指数为5，因此之后的假数要乘$2^5$也即32。
剩余23位01101111011001000000101代表假数。由于省略了“1.”，实际是1.01101111011001000000101对应1.43512022495269775390625。
最终结果便是+32×1.43512022495269775390625也即45.923847198486328125。
[复制链接]
发表于 2023-12-1 07:05
