密码学LCG—PWNHUB—mylcg

t01625cc8081f5a1a02
t01b81b8e4b099cef8b

0x01 题目背景及介绍

本篇题目来自于PWNHUB五月公开赛的一道Crypto,题目叫做mylcg。

CTF的技术有一部分提示来自于题目,题目中带lcg,可能和LCG相关。

来自 Crypto.Util.number import *

从 hashlib import sha256

f = open(’flag.txt’)

flag = f.read()

f.关闭()

assert flag[:5] == ‘flag{‘

种子 = getPrime(256)

打开文件flag.txt,assert断言flag格式应该为“flag{}”

my_LCG类:

def __init__(自我):

self.p = getPrime(512)

self.a = getRandomNBitInteger(256)

self.b = getRandomNBitInteger(256)

self.c = getRandomNBitInteger(256)

self.seed = seed

定义类my_LCG

def next(自我):

self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.p

返回自我.种子 >> 64

定义输出(自输出):

print(“a =”, self.a)

print(“b =”, self.b)

print(“c =”, self.c)

print(“p =”, self.p)

lcg = my_LCG()

lcg.output()

print(“state1 =”, lcg.next())

print(“state2 =”, lcg.next())

密码 = []

对于标志中的 i:

tmp = int(sha256(i.encode()).hexdigest(), 16)

cipher.append(pow(tmp, 3, seed) ^ (lcg.next() >> 192))

print(cipher)

# a = 68823589009570846705623113091430161477799561031575612135516351257937127579444

# b = 76549169049080319489163980188997771079750670038002598167961495813084486794567

# c = 99215492498952976642031024510129092308042391285395704888838178561670205468882

# p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031

# 状态 1 = 664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507

# 状态 2 = 269639459994260392015105629865659210391196381140872041084737976688017858324308345528702533444116282512066085580909718347778743354754352

# [104612880565354761070267231258959974017713136013091552542621012009434344223091, 75867315122609665862412321569592448016548595925558860261941234225747875658355, 106901597652387441116797426235259979167755542628252028460970918870852084813985, 22282265919236743389726915885827434932651977730848876965702592028838506934802, 113663688553403244683128957504190135685760214545373190153400188368329624810824,16387987427743919688629484112748920627537972533590712542304182257404148095432, 42660781848852863873070244368035358673436082124276647936063403560054320824947, 31162780219880567100421404229662317404195331726681121575505050872412728752846, 4387263209760294127327273998365291139136756172378440265726369942465661809226, 9486548512905762310741629559650376499881990751841396019470492813536817972788,48175096956218645396129797881617184816956038092368660196837813749510220209020, 44832999096333655680734980423005605365074861714291594434259782779054037518357, 91949111038768792853022977677056688517414191501656202462769670180011454736134, 84362160451115508526234487916725793664590119636637539810168371139175756722218, 37991151261861388606427583658548923882501719664397171054526120281654768250027,76502569176155441262877857713986290804857527394931115027371407239085302418015, 69004590108972326779999503375035935629144187797049165946644383062664912505793, 4882509736578426220928083701456224217596136409513934115208162112269124095036, 43923135793747042362291047632803354256532285967402459802384563909906286571537, 60099118217689452210082521471087211926434931778809056323284225098458442535387,41772186654628607473153061053630877342481864865985327695842922897386493117840, 79556569085671906788310296380605892417410665990711208999213184300355584627493, 113368724525353223298893326950045576507359981373213697703045622403941359594816, 59568498228965811827206375159844085215141410061444029744235874177744506595963, 5813871055160958965491186951684884799390692165774935048726620511285107065171,101481471612354001038968281423076176339698400003836978206153754002016784653117, 96713934756979037100616702408060142461624534046186352589457317850269578096978, 50360544372106359495068645870868114000049436655822775857718387298804448386259, 74343018392522018803983491192044402773734077434586754153316411931268932053849, 85064649783728020457864819723803995069342386266325766064354175704654032312470,35444692928369969109775411420972206587166544062593932622816977149910920025593, 88364976585873094910882074779610461514853793492269703066264952338524869329015, 57171789241051208558861663926443006215165105080980300229007074324952708746414, 53398702677161874182117493992247921340773468735882139055903326524685751323223, 22084022599630141597766375557874162908749682780683228274573161676243137075985,67811375554342446963928136891489894009025011339123405492350978811178609371520, 54279152372926754185972096972067394007518618911313269898203907795172124806761, 71337965908378379886587542454943435140109212437982933800558803691194797247858, 91631795365993438211094618411930046881699597378889861280702841447103987549686, 55725715889928044127700572038972949057067144434626788557169321659022938298621,68379770126152524442093415542514227284857840135092144556912468864495685413179, 40664875356285535027116296315063139118439996515430069978781752466656941376294]

0x02 题目分析

cipher.append(pow(tmp, 3, seed) ^ (lcg.next() >> 192))

其中

pow(tmp, 3, seed)为,tmp的3次方对seed取余

pow(tmp, 3, seed) ^ (lcg.next() >> 192)为pow(tmp, 3, seed)与(lcg.next() >> 192)的二进制异或

getPrime(512)

t01792a899176feecb9

getRandomNBitInteger(256)

t0197b72a67607a388e

知识点

思路应该是先推导出seed再进行flag的判断,尝试下的结果:

t015c12f26ce6f638ea

尝试了一下发现

t014b42b404b0d1067a
t01ffb614e21cdf8509

state1不是state2的输入,只是输出,原因在于对>>符号的理解

比特右移(>>)运算符可以是算术(左端补最高有效位)或是逻辑(左端补 0)位移。例如,将 11100011 右移 3 比特,算术右移后成为 11111100

如果再移回来就是

a = 0b10001

a>>2 = 0b100

(a>>2)<<2 = 0b10000

知识点

“(a ^ b)^b = a”

a = 0b10000110

b = 0b110100101

a ^ b = 0b100100011

(a ^ b)^b = 0b10000110

t013264950ab1012e94

0x03 错误思路

一开始本想通过爆破逆推,尝试后发现,较短的数据可以做到,较长的效果极其不好,所以换为官方的思路

来自 Crypto.Util.number import *

从 hashlib import sha256

a = 68823589009570846705623113091430161477799561031575612135516351257937127579444

b = 76549169049080319489163980188997771079750670038002598167961495813084486794567

c = 99215492498952976642031024510129092308042391285395704888838178561670205468882

p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031

状态 1 = 664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507

状态 2 = 269639459994260392015105629865659210391196381140872041084737976688017858324308345528702533444116282512066085580909718347778743354754352

对于范围 (2**64) 中的 i:

s = 状态1<<64

s += i

if ((a*s*s+b*s+c)%p)>>64 == state2:

s2 = (a*s*s+b*s+c)%p

print(s2)

0x04 题目思路

这道题的关键在于Coppersmith一元、二元攻击

import itertools

def small_roots(f, bounds, m=1, d=None):

if not d:

d = f.degree()

R = f.base_ring()

N = R.cardinality()

f /= f.coefficients().pop(0)

f = f.change_ring(ZZ)

G = Sequence([], f.parent())

for i in range(m + 1):

base = N ^ (m – i) * f ^ i

for shifts in itertools.product(range(d), repeat=f.nvariables()):

g = base * prod(map(power, f.variables(), shifts))

G.append(g)

B, monomials = G.coefficient_matrix()

monomials = vector(monomials)

factors = [monomial(*bounds) for monomial in monomials]

for i, factor in enumerate(factors):

B.rescale_col(i, factor)

B = B.dense_matrix().LLL()

B = B.change_ring(QQ)

for i, factor in enumerate(factors):

B.rescale_col(i, 1 / factor)

H = Sequence([], f.parent().change_ring(QQ))

for h in filter(None, B * monomials):

H.append(h)

I = H.ideal()

if I.dimension() == -1:

H.pop()

elif I.dimension() == 0:

roots = []

for root in I.variety(ring=ZZ):

root = tuple(R(root[var]) for var in f.variables())

roots.append(root)

return roots

return []

a = 68823589009570846705623113091430161477799561031575612135516351257937127579444

b = 76549169049080319489163980188997771079750670038002598167961495813084486794567

c = 99215492498952976642031024510129092308042391285395704888838178561670205468882

p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031

state1 = 664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507

state2 = 269639459994260392015105629865659210391196381140872041084737976688017858324308345528702533444116282512066085580909718347778743354754352

PR. < s1_low, s2_low > = PolynomialRing(Zmod(p))

f = a * ((state1 << 64) + s1_low) ^ 2 + b * ((state1 << 64) + s1_low) + c – (state2 << 64) – s2_low

state1 = small_roots(f, (2 ^ 64, 2 ^ 64), m=3)[0][0] + (state1 << 64)

state2 = small_roots(f, (2 ^ 64, 2 ^ 64), m=3)[0][1] + (state2 << 64)

print(state2)

此段代码的目的是用于输出之后的state,之前有推测过,知道flag需要知道seed

求seed方程:

P.<x> = PolynomialRing(Zmod(p))

f = a * x * x + b * x + c – state1

f = f.monic()

print(f.roots())

得到种子:

种子 = 931619026756858577869325713310380185951406212494138341790364440

通过seed,求解flag:

种子 = 93161902675685857786932571331038018595140621249413834179036444009740278201203

哈希表 = []

标志 = ”

lcg = my_LCG()

对于 i 在可打印中:

tmp = int(sha256(i.encode()).hexdigest(), 16)

hashtable.append(pow(tmp, 3, seed))

对于 i in range(len(cipher)):

tmp = lcg.next() >> 192

ind = hashtable.index(tmp ^ cipher[i])

标志 += 可打印[ind]

打印(标志)

引用:

https://mp.weixin.qq.com/s/yDFu4S7fBaxI5HmWrxrduA

本文由Tide安全团队原创发布
转载,请参考转载声明,注明出处: https://www.anquanke.com/post/id/273719

主题测试文章,只做测试使用。发布者:1869,转转请注明出处:https://community.anqiangkj.com/archives/18798

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022年7月3日 下午3:22
下一篇 2022年7月4日 下午3:09

相关推荐