吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 4873|回复: 28
上一主题 下一主题
收起左侧

[CTF] Hex-Rays Challenge madame Solution

  [复制链接]
跳转到指定楼层
楼主
周易 发表于 2023-12-1 07:05 回帖奖励
本帖最后由 周易 于 2023-12-1 07:09 编辑

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。

免费评分

参与人数 16吾爱币 +17 热心值 +15 收起 理由
collinchen1218 + 1 可惜了,想推荐你优秀会员,可惜热心值小于100
Fuzz + 1 + 1 谢谢@Thanks!
1MajorTom1 + 1 热心回复!
Tianmoy + 1 + 1 我很赞同!
fengbolee + 2 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!
gcode + 1 + 1 谢谢@Thanks!
abc2018zh + 1 + 1 我很赞同!
yixi + 1 + 1 谢谢@Thanks!
janken + 1 + 1 感谢发布原创作品,吾爱破解论坛因你更精彩!
iokeyz + 3 + 1 谢谢@Thanks!
leaf0125 + 1 用心讨论,共获提升!
MakiseSatsuki + 1 热心回复!
朱朱你堕落了 + 3 + 1 老哥你这实力在这里,所以我严重怀疑...
zhczf + 1 + 1 我很赞同!
allspark + 1 + 1 用心讨论,共获提升!
Atnil + 1 谢谢@Thanks!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

沙发
52soft 发表于 2023-12-1 07:14
好好学习
3#
sjzdevin 发表于 2023-12-1 08:22
4#
wlq127 发表于 2023-12-1 09:17
5#
Archange 发表于 2023-12-1 09:44
感谢分享
6#
wdlcc 发表于 2023-12-1 10:24
我看不懂,但我大受震撼
7#
r_longbow 发表于 2023-12-1 10:29
太过高端了,看不懂
8#
Shirasawa 发表于 2023-12-1 10:54
看不懂但感谢楼主分享
9#
Hmily 发表于 2023-12-1 12:03
IDA拿到了吗
10#
027rainguai 发表于 2023-12-1 13:47
看不懂,好好学习
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-3-2 02:26

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表