Coppersmith’s Attack

WriteUp 2年前 (2022) admin
1,609 0 0

1.引言

可以毫不夸张地说,学习Coppersmith’s Attack的师傅们90%+是刷题刷到了强网杯2019的Copperstudy,本小师傅也不例外,借此机会好好study(研究)下Coppersmith叭~

2.原理分析

Coppersmith攻击,如wiki所指,大致有以下方式:低指数攻击;Coppersmith方法;Håstad 的广播攻击;Franklin-Reiter相关消息攻击 ;Coppersmith 的短填充攻击。

Coppersmith’s Attack

低公共指数攻击(Low public exponent attack):为减少签名验证时间会选取很小的e,容易恢复d(非完全破解)。如果公共指数很小并且明文 m很短,那么 RSA 函数可能很容易反转,这使得某些攻击成为可能。

Coppersmith方法(Coppersmith method):有整数N且 f ∈ Z[x] 是一个度数为d的单项多项式。对某些k ≥ 0,令 X = N 1/d −k ,那么 给定 (N,f), Marvin(攻击者) 可以很容易找出所有证书 |x0| < X 满足f (x0) = 0 (mod N)。运行时间由在维度为O(w)的网格上运行LLL算法所需的时间主导,w=min(1/k, log2> N)。

Håstad 的广播攻击(Håstad’s broadcast attack):在加密前对M进行线性填充并不能防止这种攻击。假设攻击者得知对于1<=i<=k和一些线性函数fi,i.e.,即Bob在加密前对信息M进行了一个填充,这样收件人就会收到略有不同的信息。例如,如果M是m比特长,Bob可能会加密并将其发送给第i个收件人。

Franklin–Reiter相关消息攻击(Franklin–Reiter related-message attack):如果两个信息之间只存在已知的固定差异,并且在相同的RSA模数N下进行RSA加密,那么就有可能恢复这两个信息。这种攻击最初是在公共指数e=3的情况下描述的,但它更普遍地起作用(随着e的增长,成本增加)。

Coppersmith 的短填充攻击(Coppersmith’s short-pad attack):与Håstad和Franklin-Reiter的攻击一样,这种攻击利用了公共指数e=3的RSA的一个弱点。Coppersmith表明,如果Håstad建议的随机填充被不当使用,那么RSA加密是不安全的。

需要看具体更深层原理的大佬可以移步文末:二十年以来对 RSA 密码系统攻击综述,原文Twenty Years of Attacks on the RSA Cryptosystem。再给一个介绍 LLL(Lenstra–Lenstra–Lovász 格基约简)算法的传送门。

3.例题

言归正传,出来吧强网杯2019 Copperstudy!

原题可以上github拉一下强网杯2019 Copperstudy;buu稍作改动后,本题有7关:level0-6,打通level 6会给出flag。

3.1 level 0

3.1.1 题目

[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=235b85c0695a9d824064d887285b462c6e5bf11eb1521b24fcb72b320aa13ed1
[+]skr[0:5].encode('hex')=88d6b371c4
[-]skr.encode('hex')=

3.1.2 解析

对hashdump即可

from Crypto.Util.number import *
import hashlib

for i in range(10000,20000000):
tar = 0x88d6b371c4
payload = long_to_bytes(i)
payload = long_to_bytes(tar) + payload
if hashlib.sha256(payload).hexdigest() == '235b85c0695a9d824064d887285b462c6e5bf11eb1521b24fcb72b320aa13ed1' :
print(str(hex(tar))+str(hex(i))[2:])
break

3.2 level 1

3.2.1题目

[+]Generating challenge 1


[+]n=13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211

[+]e=3

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517

[+]((m>>72)<<72)=2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

[-]long_to_bytes(m).encode('hex')=

3.2.2 解析

直接求三次方的根:

from Crypto.Util.number import *
import gmpy2
c=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
m = gmpy2.iroot(c,3)[0]
#print(long_to_bytes(m))
print (hex(m))

3.3 level 2

3.3.1题目

[+]Generating challenge 2


[+]n=12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219

[+]e=65537

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778

[+]((p>>128)<<128)=97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672

[-]long_to_bytes(m).encode('hex')=

3.3.2 解析

知道了n,e,c以及p高位,还原p进而求出q、d、m即可。核心是SageMath求小根x0可解。

#Sagemath

n =
p4 =
#全位p的pbits与缺省p的kbits
pbits = 1024      
kbits = pbits - p4.nbits()
print (“the bits of p4 is:", p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
#求一个小根x0
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]

3.4 level 3

3.4.1题目

[+]Generating challenge 3


[+]n=92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183

[+]e=3

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=56164378185049402404287763972280630295410174183649054805947329504892979921131852321281317326306506444145699012788547718091371389698969718830761120076359634262880912417797038049510647237337251037070369278596191506725812511682495575589039521646062521091457438869068866365907962691742604895495670783101319608530

[+]d&((1<<512)-1)=787673996295376297668171075170955852109814939442242049800811601753001897317556022653997651874897208487913321031340711138331360350633965420642045383644955

[-]long_to_bytes(m).encode('hex')=

3.4.2 解析

已知:n、m为512位、c、d的低位512位。

知道d的低位可以通过简单推导(从e∗d=kϕ(n)+1消元q得到p关于d、e、k的表达式,且k<e)求出p的低位,进而用level 2求出p,之后便是有手就能做啦.

#Sagemath
def recover_p(p0, n):
   PR.<x> = PolynomialRing(Zmod(n))
   nbits = n.nbits()
   p0bits = p0.nbits()
   d0bits = d0.nbits()
   f = 2^p0bits*x + p0
   f = f.monic()
   roots = f.small_roots(X=2^(nbits//2-p0bits), beta=0.4)  
   if roots:
       x0 = roots[0]
       p = gcd(2^d0bits*x0 + p0, n)
       return ZZ(p)

   
def find_p0(d0, e, n):
   X = var('X')
   for k in range(1, e+1):
       results = solve_mod([e*d0*X == k*n*X + k*X + X-k*X**2 - k*n], 2^d0.nbits())
       for x in results:
           p0 = ZZ(x[0])
           p = recover_p(p0, n)
           if p and p != 1:
               return p

n =
e =
c =
d0 =
p = int(find_p0(d0, e, n))
q = n//int(p)

3.5 level 4

3.5.1题目

[+]Generating challenge 4
[+]e=3
[+]m=random.getrandbits(512)
[+]n1=78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
[+]c1=pow(m,e,n1)=23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
[+]n2==98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
[+]c2=pow(m,e,n2)=72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676
[+]n3=91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
[+]c3=pow(m,e,n3)=22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616
[-]long_to_bytes(m).encode('hex')=

3.5.2 解析

有三组n与c,广播攻击即可。

from gmpy2 import *
from functools import reduce


n1=
n2=
n3=

c1=
c2=
c3=

def CRT(n, a):
   sum = 0
   prod = reduce(lambda a, b: a * b, n)
   for n_i, a_i in zip(n, a):
       p = prod // n_i
       sum += a_i * invert(p, n_i) * p
   return int(sum % prod)

   
print(hex(iroot(CRT([n1,n2,n3],[c1,c2,c3]),3)[0]))

3.6 level 5

3.6.1题目


[+]Generating challenge 5


[+]n= 113604829563460357756722229849309932731534576966155520277171862442445354404910882358287832757024693652075211204635679309777620586814014894544893424988818766425089667672311645586528776360047956843961901352792631908859388801090108188344342619580661377758180391734771694803991493164412644148805229529911069578061


[+]e=7


[+]m=random.getrandbits(512)


[+]c=pow(m,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021533447981943498594790549326550460216939216988828130624120379925895123186121819609415184887470233938291227816332249857236198616538782622327476603338806349004620909717360739157545735826670038169284252348037995399308


[+]x=pow(m+1,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021552486915464025361447529153776277710423467951041523831865232164370127602772602643378592695459331174613894578701940837730590029577336924367384969935652616989527416027725713616493815764725131271563545176286794438175

3.6.2 解析

解法不止一种,可以看成是求多项式下的GCD,(f1(x)=a1x+b1,f2(x)=a2x+b2,其中a1=a2=1,b1=0,b2=1)

#sagemath
def franklinReiter(n,e,b,c1,c2):
   R.<X> = Zmod(n)[]
   f1 = X^e - c1
   f2 = (X + b)^e - c2
   m_ = GCD(f1,f2).coefficients()[0]
   # 返回的是首一多项式,coefficients()返回多项式各项式的系数,项式次数递增,所以第0项是常数
   return Integer(n - m_)
# 由于tmp其实是 -m % n,所以这里给他转换回去。

def GCD(a, b):
   if(b == 0):
       return a.monic()
   # 返回首一多项式,即多项式最高次的项式系数为1
   else:
       return GCD(b, a % b)
e =
n =
b =
c1 =
c2 =
M = franklinReiter(n,e,b,c1,c2)
print(hex(M))

3.7 level 6

3.7.1题目

[+]Generating challenge 6
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL
[-]long_to_bytes(m).encode('hex')=

3.7.2 解析

可以看出:

1)与以往不同的是e足够大(无法求低次根)

2)n为1024位二进制数,而d=random.getrandbits(1024*0.270),即d<N0.292

3)涉及多元coppersmith’s method,而‘Coppersmith’s algorithm uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to construct the polynomial f with small coefficients’(Coppersmith method使用LLL攻击),github传送门:https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage。将指数改一改带入SageMath

whenever delta < 1 - sqrt(2)/2 ~ 0.292

Coppersmith’s Attack

4.参考链接

https://paper.seebug.org/727/https://www.ams.org/notices/199902/boneh.pdf(二十年以来对 RSA 密码系统攻击综述中文尽力翻译版/英文原版)

https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage(github boneh_durfee SageMath版)

https://en.wikipedia.org/wiki/Coppersmith%27s_attackhttps://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm(维基百科Coppersmith’s attack、LLL算法)

https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch19.pdf(paper:Coppersmith’s Method和相关应用)

https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf(paper:Coppersmith’s Attack

https://github.com/851579181/qiangwangbei_2019_crypto_copperstudy(强网杯copperstudy环境)

https://jayxv.github.io/2020/08/13/%E5%AF%86%E7%A0%81%E5%AD%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E4%B9%8Bcoppersmith/(Van1sh师傅Coppersmith学习笔记)

https://blog.csdn.net/walker_feng/article/details/108889696(walker_feng师傅解题笔记)


原文始发于微信公众号(瑞不可当):Coppersmith’s Attack

版权声明:admin 发表于 2022年5月25日 下午3:52。
转载请注明:Coppersmith’s Attack | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...