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}

原文发布于微信公众号 - 安恒网络空间安全讲武堂(gh_fa1e45032807)

原文发表时间:2018-03-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

在.NET Core 里使用 BouncyCastle 的DES加密算法

.NET Core上面的DES等加密算法要等到1.2 才支持,我们可是急需这个算法的支持,文章《使用 JavaScriptService 在.NET Core ...

33970

.NET中的密钥加密

本教程将演示如何通过System.Security.Cryptography在.NET Framework 1.1中实现对称加密/密钥加密。

63280
来自专栏hrscy

RxSwift - API

在某些情况,由于不同平台/实现方式,相同的操作符有多个别名,有时相同的操作命名也不一样,有些是因为历史的原因,但是还有一些是因为语言的预留关键字。

18920
来自专栏小灰灰

利用Crypto++实现RSA加密算法

之前做一个项目用到crypto++加密库,可以从官网下载对应的源码,其中有一个test.c文件,详细的演示了各种加密算法的使用方法,因此,在其基础上,我将ae...

47670
来自专栏ImportSource

自己动手写区块链-发起一笔交易(Java版)

本文我们将会做以下事情: 1、创建一个钱包(wallet)。 2、使用我们的前面创建的区块链发送一笔签名的交易出去。 3、还有其他更叼的事情等等。 听起来是不是...

2.2K100
来自专栏酷玩时刻

微信支付之企业付款

付款之前需要充值: 在调用API接口付款或通过微信支付商户平台网页功能操作付款之前需要登录微信支付商户平台,通过网页充值功能充值(商户平台-交易中心)

19640
来自专栏一个会写诗的程序员的博客

【Kotlin 反应式编程】第1讲 你好,Reactive Programming

【Kotlin 反应式编程】第1讲 你好,Reactive Programming

9220
来自专栏Java与Android技术栈

Scrypt 不止是加密算法,也是莱特币的挖矿算法

Scrypt不仅计算所需时间长,而且占用的内存也多,使得并行计算多个摘要异常困难,因此利用rainbow table进行暴力攻击更加困难。Scrypt 没有在生...

14740
来自专栏蓝鸟资源分享网

muduo网络库学习之EventLoop(四):EventLoopThread 类、EventLoopThreadPool 类

muduo并发模型one loop per thread + threadpool(计算线程池)

13140
来自专栏开发与安全

muduo网络库学习之EventLoop(四):EventLoopThread 类、EventLoopThreadPool 类

1、EventLoopThread(IO线程类) 任何一个线程,只要创建并运行了EventLoop,都称之为IO线程 IO线程不一定是主线程 muduo并发模型...

42760

扫码关注云+社区

领取腾讯云代金券