20220514-PWNHUB5月赛-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 17k Reading time ≈ 15 mins.

 

本次公开赛和内部赛的密码都比较简单

公开赛

myLCG

  • 考点：CopperSmith解多元小根

魔改的LCG（×），解方程（√）

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import *
from hashlib import sha256
f = open('flag.txt')
flag = f.read()
f.close()
assert flag[:5] == 'flag{'
seed = getPrime(256)


class my_LCG:
    def __init__(self):
        self.p = getPrime(512)
        self.a = getRandomNBitInteger(256)
        self.b = getRandomNBitInteger(256)
        self.c = getRandomNBitInteger(256)
        self.seed = seed

    def next(self):
        self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.p
        return self.seed >> 64

    def output(self):
        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())
cipher = []
for i in flag:
    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
# state1 = 664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507
# state2 = 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]

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#!/usr/bin/env sage
# coding: utf-8
from hashlib import sha256
from string import printable
from gmpy2 import invert


class my_LCG:
    def __init__(self):
        self.p = p
        self.a = a
        self.b = b
        self.c = c
        self.seed = seed

    def next(self):
        self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.p
        return self.seed >> 64


a = 68823589009570846705623113091430161477799561031575612135516351257937127579444
b = 76549169049080319489163980188997771079750670038002598167961495813084486794567
c = 99215492498952976642031024510129092308042391285395704888838178561670205468882
p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031
state1 = 664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507
state2 = 269639459994260392015105629865659210391196381140872041084737976688017858324308345528702533444116282512066085580909718347778743354754352
s1 = state1 << 64
s2 = state2 << 64

load('coppersmith.sage')
P.<x, y> = PolynomialRing(GF(p))

f = a * (s1 + x) ^ 2 + b * (s1 + x) + c - (s2 + y)
roots = small_roots(f, (2^64, 2^64), m=3)[0]
s1 += int(roots[0])
s2 += int(roots[1])

P.<s> = PolynomialRing(Zmod(p))
f = a * s ^ 2 + b * s + c - s1
seed = int(f.roots()[1][0])

lcg = my_LCG()
assert [lcg.next() for _ in range(2)] == [state1, state2]

brute_space = {}
for i in printable:
    tmp = int(sha256(i.encode()).hexdigest(), 16)
    brute_space[tmp % seed] = i

d = invert(3, seed - 1)
cipher = [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]

for i in range(len(cipher)):
    tmp = pow(cipher[i] ^^ (lcg.next() >> 192), d, seed)
    print(brute_space[tmp], end='')
print()
# flag{c47872f1-a99e-456c-cbe6-d08484f14ce1}

内部赛

unsafe nence

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from Crypto.Util.number import *
flag = 'hi there, this is 4xwi11'
import string
import hashlib
import random
import os

def keygen(ln):
    # Generate a independent key
    arr = [getPrime(ln) for i in range(ln)]
    return arr



def gen_keystream(key):
    keystream = [[0,key[i]] for i in range(len(key))]
    iv = getPrime(LN//2)
    for i in range(LN-1):
        keystream[i][0] = key[i]^key[i+1]
    keystream[LN-1][0]  = key[LN-1]^iv
    random.shuffle(keystream)
    return keystream


def encrypto(key,m):
    cip =1
    for i in range(len(m)):
        if(m[i]==1):
            cip*=key[i]
    return cip

def proof_of_work():
    s = "".join(random.sample(string.ascii_letters + string.digits, 20))
    prefix = s[:4]
    print("sha256(xxxx + %s) == %s " % (s[4:],hashlib.sha256(s.encode()).hexdigest()))
    print("give me xxxx:")
    ans = input().strip()
    if len(ans) == 4 and ans == prefix:
        return True
    else:
        return False
try:

    if not proof_of_work():
        exit()
except:
    exit()


# init
secret = os.urandom(8)

m = [int (i) for i in list(bin(bytes_to_long(secret))[2:].rjust(len(secret)*8,'0'))] 
LN = len(m)
key = keygen(LN)
keystream = gen_keystream(key)


menu = """
[1] Encrypt and get cipherText
[2] Check you answer
[3] My gift
[4] exit
"""
while 1:
    print(menu)
    op = input(">")
    if(op=='1'):
        cip = encrypto(key,m)
        print(cip)
        continue
    if(op=='2'):
        YourSecretHex = input('give me secret in HEX:')
        YourSecret = bytes.fromhex(YourSecretHex)
        if(YourSecret == secret):
            print("you did it!!unbelievable!!")
            print(flag)
        else:
            print("try again")
        continue
    if(op=='3'):
        print("here are you:")
        print(keystream)
        continue
    if(op == '4'):
        print("bye!!")
        break

我的做法是先确定最后一个，然后依次遍历往前找

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import *


def decrypt(key, key_seq):
    m = []
    for i in key:
        if i in key_seq:
            m.append('1')
        else:
            m.append('0')
    m = int(''.join(m), 2)
    print(long_to_bytes(m).hex())


key_stream = [[8779582278268986568, 13972447072333016717], [2835921688996422960, 13399390213922803289], [2972409776130309532, 16559329861009939963], [1033763475380874170, 12718043069307240271], [14518345776863828700, 14518345781028613351], [3594736753648488302, 16556792243215240193], [2920878919724938340, 12736435585789788179], [1428541050429491416, 10358834156010643157], [1268208453518006040, 13276414912962398789], [9113004782712964334, 11102773719072440869], [432329273352093334, 15287074050624177007], [6942433427262517692, 15121233721483378169], [3697581427774504474, 9990181203579400259], [258166246112909708, 16587601807931780257], [6627525136794168270, 12412544559944377193], [6684243938812889796, 9744991320816487597], [1803935490195559424, 16508419663583149481], [4826520667649813430, 10065209613001787539], [4372180482202183080, 17622260286929220133], [8876839085812793576, 11390663903781585557], [5751539233457914060, 16457028586634856139], [1836484817807711118, 18210599645956675471], [7318815736519327028, 17236939324015480183], [6029822704859535140, 18441128104321479757], [618181373323940462, 10556650214702682187], [7281107314188002400, 14507765834006962981], [2440649095282677440, 15852140222260708969], [6009553007025357374, 17841915322455125371], [8108357868642599946, 17851008316317599911], [8837992241624284328, 12081450737853266699], [1695635503484119714, 10973551872446870647], [2661390343339298182, 16511069682831770237], [6538201270686099842, 16548423095865111853], [3557376979829441730, 11246273648570095117], [6979839776983904698, 12224697773647469917], [8523959602484753600, 13964591584802246651], [2082684913461012782, 15929008069799020451], [7839528782052360990, 11191637010989706853], [5545266207423011378, 18197690351643272573], [3453626818702163380, 13770763335134370991], [8063552728968536124, 13303373687545948007], [3387950048990474816, 13701984912510588149], [5558131541688098228, 16114638404839345663], [3542546840365140738, 16686116803788883931], [3630426494960614130, 15526280242707122011], [3319501829037603628, 14421584453923837837], [3346153664282028922, 11434364198579333993], [6068659120328552598, 11580704128296125107], [6527437612922589722, 18023670557697626281], [6391429115601860172, 13224541131631377211], [3930164041727827390, 10458290927061214901], [2661353548507038800, 15472496154249710809], [3967370278962719008, 12420435944394721093], [4858804803266586782, 11888676089983790917], [4181640118414759568, 12462430910276960563], [8301778622336617048, 10879387637052495779], [656963133086067490, 12790525991712394309], [7804492847900751508, 10445583672503001371], [6050292517786733624, 14739877198024482919], [6819907064055335354, 17462249837089654921], [4673283453097206176, 11491045269336812639], [43420844401216724, 18163419661266446761], [2801893311188048476, 12487529381913793231], [6079439990157701706, 12372107513836504583]]
c = 248989084975279954530446836187742260957464300571462773588456663949016643230510464543511459928583572807089450199912563182507696384583461748946818877790890833787976928042941582962480484928204346903330773117645824916689806456224546576491363960352805243729130006879143274931033742096269219412413483369744418405994456845747843492443615095091040028459038822533077065396480961075744563084128188136369847545720850903783595992035389582552870395168288052488886873290247545662095337543626052711637168589058325880633931884880718419421190578986090522834555126398496232907268338531658654840865853876273393196175836323813262165790569865768435667663526298122251221172688546949592040884434661997750300546641
ps = [15526280242707122011, 16587601807931780257, 12420435944394721093, 16457028586634856139, 11102773719072440869, 13224541131631377211, 12372107513836504583, 9744991320816487597, 18197690351643272573, 10065209613001787539, 15287074050624177007, 12081450737853266699, 11491045269336812639, 17622260286929220133, 16556792243215240193, 16548423095865111853, 12487529381913793231, 12224697773647469917, 13303373687545948007, 11191637010989706853, 16114638404839345663, 17851008316317599911, 15929008069799020451, 12736435585789788179, 10358834156010643157, 12412544559944377193, 18163419661266446761, 10973551872446870647, 12790525991712394309, 16686116803788883931, 15121233721483378169, 14739877198024482919, 17462249837089654921, 16508419663583149481, 18441128104321479757, 16559329861009939963]

# from re import findall
# c = ''''''
# a = []
# ps = findall(r'\d+', c)
# for i in range(len(ps)):
#     if i % 2 == 1:
#         a.append(int(ps[i]))
# print(a)
true_key = []
for i in range(len(key_stream)):
    if (key_stream[i][0] ^ key_stream[i][1]).bit_length() < 50:
        iv = key_stream[i][0] ^ key_stream[i][1]
        # 3255281413
        true_key.append(key_stream[i][1])
        key_stream.pop(i)
        break

for i in range(63):
    j = 0
    while 1:
        if key_stream[j][0] ^ key_stream[j][1] == true_key[i]:
            true_key.append(key_stream[j][1])
            key_stream.pop(j)
            break
        j += 1

decrypt(true_key[::-1], ps)

image-20220515231155556