SharifCTF 2018 Crypto writeup

本文作者：HeartSky

之前的SharifCTF，其中密码学部分有许多有意思的题目，因此来分享下相关解题过程。

0x01 DES

See known_plaintexts.txt. There is a single unknown DES key K. All plain texts are encrypted under K, resulting in the corresponding cipher text. Can you find K? flag is SharifCTF{K}, where K is a 64-bit hexadecimal value, without the 0x prefix. (K includes the parity bits.)

下载下来是许多明密文对

plaintext -> ciphertext ------------------------------------ 89bc8acb348c1ecc -> 9e31e5f5a8cef654 102708d526ce86e3 -> 2c1268d98e66b343 f325c207d9562460 -> c35b2a05892c529b a87d70390084a3c3 -> 0cb354caa06c7190 24d5ce59b0522da8 -> 9f8976c9ae13387f 9b2debc8c31054b1 -> 0acc0f066a499584 3de1b1e8466f44ef -> 9b248c3d4ab19689 9ebf62892cdfed78 -> 330a8c38b7ea14f5 4cc53edc2032e7d3 -> d3d166309b4f13b2 2c2c9121e56a08b5 -> 0f0ef700d4ca4579 0960a1a053fc1ee9 -> 69b8ff981f5e0308 2a6c4a1cb1047fee -> ccddffdd954e2d59 fac2001584e40a24 -> 095429cdfe3290b8 d00b6e33b0f3ec19 -> c494852274b97316 9e754706e31c36dc -> 6adc6362a1db0547 881bb04ac3dffb14 -> 428f35ad196bf521 04c2ed5fd31dba47 -> f25a1c0bb005e04e bebc67b6c222c062 -> 057f79262c1f6268 2491d001204267fc -> d52a5507d3a53b96 890a65beda74e6d6 -> 5b3ed00964bdf967 ...... 18f23af0f55f5ef2 -> 0cba8de8c55f08ac b32b1d8f17cd1aa4 -> 100e2638ef72cf6c 7f6e54c0fac313a7 -> 3c1539d17d0b75bb 69c1e688560aa8ff -> 573eb948086191a4 79961a37cd9154e4 -> bf380172f6d62389 ee384e498a159676 -> 768c96e0f04ce204 ebc7839bb03e1fd9 -> cb43e96737eb7363 ddee67a9c07e9748 -> 38480adf9eb522c5 0952d749507bff96 -> e43e4af3b38ac9b8 6cb7a102a655dee2 -> e148c122acb727d7 f55d0aaadb90d3e4 -> 0320b175b5475f3c 70d43f917100c665 -> 976b14abc2767bf2 2c9ce7b7e700f891 -> 6fc2b3169e97a1bb 984ed278d76cb26f -> 387eefcf4b23e0a1 3f8df0799af80dac -> 21a3d429f48d7e9c 9c5a941fb670de9e -> 5adbc56f71cd9b18

给了有 1000 条数据，篇幅限制就不都放出来了

搜索了一番，没有发现能够通过已知明密文对来攻击 DES 密钥的

猜测可能是 DES 弱密钥问题，所谓 DES 弱密钥就是该密钥可以使 DES 生成的 16 个子密钥完全相同的情况。因为 DES 是采用的 Feistel 网络结构，如果所有子密钥都相同的话，加密解密的效果就是一样的，也就是满足

E(E(m)) = m

然后就是验证下有没有出现两次的数据，写个脚本

f = open('./known_plaintexts.txt')
 s = f.read().split('\r\n')[2:]
 arr = []
 
 for i in range(len(s)):
     s2 = s[i].split(' -> ')
     for j in s2:
         if arr.count(j) > 0:
             print j
         else:
             arr.append(j)

果然发现了两条数据

f084cae61e607b05 ef17ae3946ebae4c

下面就是根据已知的四条弱密钥逐一尝试即可

Alternating ones + zeros (0x0101010101010101) Alternating 'F' + 'E' (0xFEFEFEFEFEFEFEFE) '0xE0E0E0E0F1F1F1F1' '0x1F1F1F1F0E0E0E0E'

选择其中一组符合上述条件的明密文对

f084cae61e607b05 -> ef17ae3946ebae4c ef17ae3946ebae4c -> f084cae61e607b05

获取密钥脚本

from Crypto.Cipher import DES keys = ["0101010101010101", "FEFEFEFEFEFEFEFE", "E0E0E0E0F1F1F1F1", "1F1F1F1F0E0E0E0E"] for key in keys: key = key.decode('hex') cipher = DES.new(key, DES.MODE_ECB) plaintext = 'f084cae61e607b05'.decode('hex') if 'ef17ae3946ebae4c'.decode('hex') == cipher.encrypt(plaintext): print key.encode('hex')

最终 flag 就是 SharifCTF{key}

SharifCTF{E0E0E0E0F1F1F1F1}

0x02 OSS-Service(easy)

In this question, you are asked to generate an OSS (Ong-Schnorr-Shamir) signature on some message, given a pair of known signatures. Further description can be found here. You can verify the validity of your signature using this Python script locally, prior to submitting it here. Upon submitting a valid signature, you’ll receive the flag.

网址：http://ctf.sharif.edu:8086/

根据题目描述是 OSS 签名，并且给了一份文档 简单介绍一下这个算法 p 和 q 是两个大素数，且 n = p*q，公钥是 pk = (n, k)，那么明文 m 的 OSS 签名就是 (s1, s2)，满足下面的关系

m = (s1**2 + s2**2) % n

m = 53 m'= 97, 对应的签名为 (s1,s2) 和 (s1’,s2’) 给出了下面的数据

n= 25002746673023214443255611415004163622813167852050923858455529030203886977840435991633024079845736335150468784530123301961464111492802951263984843039164056430832125163123383805713707250515254073169424707009359341759806003392594138294458167902830484152672696274313541002376076183872266230285338817553110422277895445022423407252341583782719664554600485831653496762352727294140410862007839241034826246409937408317586016100320118339304493568308875379717324497727750190898854014202895798781129867240530387323567711557244359201718574163779140769622702892937997637399632813759046725913242153879394145202439145824342609530733 k= 23362339402422379817772327315061502761593494363846640180372992347552364432329220756030231112957778618810078666762974577247225709089334422591782884749584385632941885055318288495081651413041625183693553233252837243762098828064089396976796784829512691690456121528386778151445275489241471824325584238311939845541912403985291213425145453729490975518843542282785674261698826757381575038415836220944506894913500128933084291790059465445840440895339431303999096861113452752000364738364437105439080665770770436241486563132717407593776498512206813885900089036806429313524876146779148195897063040217695170237733473446418668779916 s1= 499696562667781847089949703619257292895338346804998149221505294748696857646916006953104584740660286730099834971758000131674648522576269899326168421335360299674834318209233550930757308824762496895442789679441261183042770468679986067311649872783079228224295184322123205954141361025476561004116044051357744131137740279448366471840309172081266074019554720174114370072554900441 96527350569773313437105547331241515716525604301492268657755586190938586265947367522921813698603847151625881131098032431190975920711377012137155839366204869205993663573232084527465728306732531071378794321276304228712618173043121942149396615492478 s2= 9339264669983291900327820828270098016379861097267077744514708712834641173057650202534710250765922313741944462789942785478170212231431727070626211785081581216011869498431598197306917945956602966039228580868647572114697339953682091890878192717124657001319847969571764996539075871196135114129827099959218903704028739118783540539731484487013859564619154565781303034838767726419327010072827695144834838584650689215227715966068273968350448794571951839296494120274908108873597642627135960002648616376004036368059928510282972523844522428329769439534207771320850592847756802766651250916352633401119949553102145237888877557923 s1'= 11753106345254288737361588513147237177750400928549963607707054166942720184532870164663313254526876864287114091403255773460126703446364096215167350117522512230363460796882926739640334786094541017927436061884032962475855870728763342865282312282570446248990619133180907228013976489639609306879272823217110322646001510606842229170558446836122206078351382968253970864143597110461965175850834817665875538033799957519184628621445302484228100263431427032089411665137733848416897797243448068873485701775788341820346935946117424174847849626391662223056950725043721907635990009814375453736359471825015817067334839806235435545448 s2'= 123161662006626173257658155440995758077644133106347955053437070384032327643606006182254293736352951669348486229126066051376766187014326742185279158572916190461546072737951070108429999738567695487322683707128747508390535278084645507888594491053352777437956961443390580531224529649715922983302553733302183680229442684930688384434263064437787360809879785644243721569717854769078822729636598856450665397631653853730111259561536552440955558062554764155674810156999963831490288009516842695456063350428308329590519170386751067328029955975084626546467505376469180883230078097302660456279461037373526104913049876100168770958

让 m''=m*m'= 5141，求 m’’ 的 OSS 签名

可以搜到一篇论文，https://webcourse.cs.technion.ac.il/236612/Spring2007/ho/WCFiles/adv-crypto-slides-09-sig-oss.1x1.pdf

里面介绍了 OSS 签名及相关的几种攻击方法，其中 Pollard’s Solution 就是用来解决上面的问题的，基于以下等式

(x1**2 + k*y1**2) * (x2**2 + k*y2**2) == X**2 + k*Y**2 X = x1*x2 + k*y1*y2 Y = x1*y2 - y1*y2

根据已知条件

m1 = x1**2 + k*y1**2 m2 = x2**2 + k*y2**2 m = m1*m2

所以

m = X**2 + k*Y**2 = (x1*x2 + k*y1*y2)**2 + k*(x1*y2 - y1*y2)**2

得出 X 和 Y 的值，(X,Y) 即为 m’’ 的签名，提交即可得到 flag

0x03 fHash

We designed a hash function called “fHash”. fHash takes a message (M), as well as two initialization values, designated as left (hl) and right (hr). You can find the implementation of fHash here. Let M1 = ‘7368617269666374’. Notice that fHash(‘7575’, ‘A8A8’, M1) = ‘260c01da’. Find M2 ≠ M1, as well as two initialization values hl and hr, such that fHash(hl, hr, M2) = ‘260c01da’. That is, find a second-preimage for M1. Each of hl and hr must be two bytes, while M2 must be 8 bytes.

网址：http://ctf.sharif.edu:8087/

题目要求很明确，自定义了一个哈希函数 fHash，已经给定了一组明密文对，要求找出一个不同的明文使得密文相同。那我们来分析下这个自定义哈希函数

from hashlib import md5
 
 def foo(h, m):
     return md5(h.encode('utf-8') + m.encode('utf-8')).hexdigest()[:4]
 
 def round(hl, m, hr):
     return foo(hl, m), foo(hr, m)
 
 def fHash(hl, hr, M):
     message = list(map(''.join, zip(*[iter(M)] * 4)))
     for m in message:
         hl, hr = round(hl, m, hr)
     return (hl, hr)
 
 if __name__ == '__main__':
     print(fHash('7575', 'A8A8', '7368617269666374'))

在 fHash 函数中，把明文分成了 4*4 的分组，进行 4 次 round，每一轮 round 都对明文的一部分和 hl 或者 hr 进行了哈希后再相加作为新一轮的 hl 或 hr 值，我们先输出每一轮的 hl 和 hr 值看下

hl hr dcd0 a6ea 9989 7629 3507 149e 260c 01da

最后一轮的 hl 和 hr 值也就是最后的密文。先来考虑下两轮的情况，要使得第二轮 hl 和 hr 的值也就是密文仍然相等，那么前一轮 hl 和 hr 的值和第二部分明文的值要相等，然后第一轮的值如果也要想相等，就得初始 hl 和 hr 的值以及第一部分明文相等，但是题目要求需要使用不同的明文，那么我们改变第一部分明文值，这时 hl 和 hr 的值也会发生变化，因为只要前四位相等即可，所以这里可以爆破。

那么解题思路很明确了，通过爆破第一轮明文和初始 hl hr 值使得获得的第一轮的 hl hr 值等同于 dcd0 a6ea，之后的明文值不变即可得到相同的密文，无论这个函数有几轮皆可成立。

附上代码

from hashlib import md5
 from itertools import permutations
 
 s = '0123456789abcde'
 
 def foo(h, m):
     return md5(h.encode('utf-8') + m.encode('utf-8')).hexdigest()[:4]
 
 def blast():
     for i in permutations(s, 4):
         m = ''.join(i)
         for j in permutations(s, 4):
             hl = ''.join(j)
             if foo(hl, m) == 'dcd0':
                 for k in permutations(s, 4):
                     hr = ''.join(k)
                     if foo(hr, m) == 'a6ea':
                         print m, hl, hr
                         return 0
 
 if __name__ == '__main__':
     blast()

基本几秒钟就可以跑出结果

012c 0e28 bd71

提交上去便可得到 flag

0x04 OSS-Service(Hard)

This challenge is similar to “OSS Signature - Easy”; but this time, it’s much harder! This time, you should find the OSS signature on a given message, but you are not given any known message-signature pairs. The public key (n and k), as well as the message on which you should generate a valid signature, are defined here. You are also give a Python script to verify your signatures locally.

网址：http://ctf.sharif.edu:8088/

这次是 OSS-Service(easy) 的升级版，不再提供原先两组已知明密文对，直接给出了 n、k、m 的值，如下

n = 108504503412454373447900779392896455789182908920252767679102572784833248190682207737154598741166656146295499891768592408962529857168166275863130804227243036676846199142906617137007877378696363607314850559328607693669984310189715960464177540321389050644453028598966277046571994650300388605135199566812211180551 k = 96418402323876864512491639972930583881318685814783562179751981420110811774390896080021079024657494752001051891183358590923934531389848653055409236592228196204683162829359099715583891741617111941684481041179057606706801620321693724317614343290846702947941240579335556736392623484157714059707148044213280632330 m = 9045418907335068770268779849124564950219260545189341826614770092040336019517687130751801431148236418688112027601673969058529643735762961447504773552645699712014099935774980274016297241177481291819364059206708658744657881196289540965565219550846730216720833999741328972855594202081834339846728109

我们根据论文中所说的 Pollard 解决方法，写出相应的代码 注意论文中并没有给出 s3、t3 和 s4、t4 的方程式，这里实际上是通过 OSS-Service(easy) 中的解法来求出的 这里我写了一个 python 版本的解决代码，因为一些语言特性，python 无法处理非常大的数字，导致最后一步会报错，这里感兴趣的可以搜索相关 sage 版本。了解相关解决思想即可

import random
 import gmpy2
 import math
 
 
 def isqrt(n):
     i = int(math.sqrt(n) + 0.5)
     if i**2 == n:
         return i
     else:
         return 0
 
 def OssEasy(x1, y1, x2, y2, k, n):
     return (x1 * x2 + k * y1 * y2) % n, (x1 * y2 - y1 * x2) % n
 
 def Pollard(k, m, n):
     # Find m0 and x0
     while 1:
         u = random.randrange(n)
         v = random.randrange(n)
         m0 = (m * (u**2 + k*v**2)) % n
         if m0 % 4 == 3:
             x0 = pow(-k, (m0 + 1)/4, m0)
             if (x0**2) % m0 == -k % m0:
                 break
 
     # Generate series of m and x
     setm = [0, m0]
     setx = [0, x0]
     while 1:
         if setx[-2] <= setm[-1] and setm[-1] <= setm[-2]:
             break
         else:
             setm.append( ((setx[-1]**2 + k) * gmpy2.invert(setm[-1], n)) % n )
             setx.append( (min(setx[-1] % setm[-1], (setm[-1] - setx[-1]) % setm[-1])) % n )
 
     # Find s0 and t0
     s0 = setx[1]
     t0 = 1
     for x in setx[2:-1]:
         s0 = s0 * x - k * t0
         t0 = s0 + x * t0
 
     # Find s1 and t1
     M = 1
     for mm in setm[2:]:
         M *= mm
     M = M % n
     s1 = (s0*gmpy2.invert(M, n)) % n
     t1 = (t0*gmpy2.invert(M, n)) % n
 
     # Find s2 and t2
     mI = setm[-1]
     print mI - int(math.sqrt(mI))**2
     if isqrt(mI):
         s2, t2 = math.sqrt(mI), 0
     elif mI == k:
         s2, t2 = 0, 1
     else:
         temps, tempt = Pollard(-mI, -k, n)
         t2 = gmpy2.invert(tempt, n)
         s2 = temps * t2
 
     # Find s3 and t3
     s3, t3 = OssEasy(u, v, s1, t1, k, n)
 
     # Find s4 and t4
     s4, t4 = OssEasy(s3, t3, s2, t2, k, n)
 
     # Find the solution of the oss problem
     inv = gmpy2.invert(m0, n)
 
     return (s4 * m * inv) % n, (t4 * m * inv) % n
 
 def main():
     n = 108504503412454373447900779392896455789182908920252767679102572784833248190682207737154598741166656146295499891768592408962529857168166275863130804227243036676846199142906617137007877378696363607314850559328607693669984310189715960464177540321389050644453028598966277046571994650300388605135199566812211180551
     k = 96418402323876864512491639972930583881318685814783562179751981420110811774390896080021079024657494752001051891183358590923934531389848653055409236592228196204683162829359099715583891741617111941684481041179057606706801620321693724317614343290846702947941240579335556736392623484157714059707148044213280632330
     m = 9045418907335068770268779849124564950219260545189341826614770092040336019517687130751801431148236418688112027601673969058529643735762961447504773552645699712014099935774980274016297241177481291819364059206708658744657881196289540965565219550846730216720833999741328972855594202081834339846728109
     print Pollard(k, m, n)
 
 if __name__ == '__main__':
     main()

最终可求出满足

(x**2 + k * y**2) % n = m % n

中 x 和 y 的值

100164299324510193497432597291207658763645549041976403139505946013739519955271632614149596227239262809355865866587686015792173637566123940020008160379117719946025790046385789957283625632664492383257700240863208794403164722402493333597435826525628614537659086037844661150860981017880733753769533938655509300861381735600229588496320358900236614746772689627759046300513978676664419681529311594222617824653360204563884153534516477719849663595827223953388637494190945191278593770139263378432718557546253916151280694358320402917258018509799097620453857008155480952831486394948127967736074112800408155948586190623654989220848055909177021075557760902182745631373572521233732924912909632229443242557195892992192523667682764151682823940851283524437977807675638283826127162281941446660667552606947406152029004494205436014955860187472512663851961016080723908049274989558745427843715457442664208952320281138912518376785101062 101480731397450514024182078340737525920172466003110558347059261024784461593990751945066940831091659814949389063035218100282206743785477912534694355841093678787295571116615123815693839794689684883029410636058142359016412597091296151234665140061035136952828255746964241266744832100691158336847466845918869134427956926308632062107391642371990760529660133852666448970719839275226546710576586942292959451195989301244182454379839890206454407741419175689957637965017892775286343359328649572168293171946596087744322673209749843845627851211781766870491780096813503113071611105726030646044959179159051429367520257321282073378103271417679586000096888304159582016903050391572597723144140580194558609989104480294653610036456436152945609394576522359841076636233976605899040472980145812513710849044719068782066928870850157708036534653948936094766930420572783651925130446316086934754677577660464982131390905148751182894683157806

提交至平台上便可得到最终 flag

SharifCTF{f5b773a1bd527761a26aaee333d62d3c}