20210807-RAR & BSidesNoida-CryptoSecPartWritUp

 

RARCTF

注意：没有给数据的题目一般都是给了个nc连接

Crypto-minigen

exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)
g=f(id(f));print(*map(lambda c:ord(c)^next(g),list(open('f').read())))

281 547 54 380 392 98 158 440 724 218 406 672 193 457 694 208 455 745 196 450 724

提示：

A stream cipher in only 122 bytes!
Note: This has been tested on python versions 3.8 and 3.9

题目不长，但比较难读这样精简的python代码

要知道exec，yield，id主要这三个函数以及python中取反符号~的等价表达式

经过层层剖析，最后提取这样一个流密码算法，当然还要模上727

然后我在草稿纸上写着$(x+1)^2+(x+1)+1-x^2-x-1=2x+2$

尚师傅一眼看出，不同的id(f)内，一个id(f)，或者称为流密码的起始状态固定，那么后面两个迭代器g之间相差的值是固定的

比如举个栗子，比如id(f)=1，那每个g之间就依次相差4 6 8 10 12……，而且整个空间是在模727下的，所以要爆破也在爆破的范围内

但是没有爆破的必要，假设flag的开头就是’rarctf’，那么我们异或回去，g的前6个值分别是363 578 68 287 508，可以看出它们之间依次相差215 217 219 221 223，然后往后走就好了，求得g，异或回去还不简单

#!/usr/bin/env python
# -*- coding: utf-8 -*-
exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)
# print(*map(lambda c:ord(c)^next(g),list(open('f').read())))
# ((x:=-~x)*x+-~-x)%727
c = '281 547 54 380 392 98 158 440 724 218 406 672 193 457 694 208 455 745 196 450 724'
flag = ''
fi = []
for i in c.split(' '):
    fi.append(int(i))
flag = 'r'
s = 363
x = 0
for i in fi[1:]:
    flag += chr((s + 215 + 2 * x) % 727 ^ i)
    s = (s+215+2*x) % 727
    x += 1
print(flag)

Crypto-sRSA

from Crypto.Util.number import *

p = getPrime(256)
q = getPrime(256)
n = p * q
e = 0x69420

flag = bytes_to_long(open("flag.txt", "rb").read())
print("n =",n)
print("e =", e)
print("ct =",(flag * e) % n)

n = 5496273377454199065242669248583423666922734652724977923256519661692097814683426757178129328854814879115976202924927868808744465886633837487140240744798219
e = 431136
ct = 3258949841055516264978851602001574678758659990591377418619956168981354029697501692633419406607677808798749678532871833190946495336912907920485168329153735

用到ElGamal类似的思想，直接求逆元

from flag import flag

print(flag)

有手就行

Crypto-unrandompad

from random import getrandbits
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

def keygen(): # normal rsa key generation
  primes = []
  e = 3
  for _ in range(2):
    while True:
      p = getPrime(1024)
      if (p - 1) % 3:
        break
    primes.append(p)
  return e, primes[0] * primes[1]

def pad(m, n): # pkcs#1 v1.5
  ms = long_to_bytes(m)
  ns = long_to_bytes(n)
  if len(ms) >= len(ns) - 11:
    return -1
  padlength = len(ns) - len(ms) - 3
  ps = long_to_bytes(getrandbits(padlength * 8)).rjust(padlength, b"\x00")
  return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")

def encrypt(m, e, n): # standard rsa
  res = pad(m, n)
  if res != -1:
    print(f"c: {pow(m, e, n)}")
  else:
    print("error :(", "message too long")

menu = """
[1] enc()
[2] enc(flag)
[3] quit
"""[1:]

e, n = keygen()
print(f"e: {e}")
print(f"n: {n}")
while True:
  try:
    print(menu)
    opt = input("opt: ")
    if opt == "1":
      encrypt(int(input("msg: ")), e, n)
    elif opt == "2":
      encrypt(bytes_to_long(open("/challenge/flag.txt", "rb").read()), e, n)
    elif opt == "3":
      print("bye")
      exit(0)
    else:
      print("idk")
  except Exception as e:
    print("error :(", e)

Yeah I use randomized padding, it increases security!Note: This is a part 1 challenge of randompad. Take a look at the source for that one and compare the two for a hint on how to solve.

提示审计另外一道题目的代码，发现很有意思的地方，还是要看仔细

这道题虽然有pad函数，但是并没有作用到m上，直接给m加密了，所以题目的攻击点只能在e=3上（因为我从$p-1=3k+1$上没有获得任何线索）

然后我也很异或，一个广播攻击我给看了好久，注意力确实不集中，想得太复杂了；知道是广播后也就没什么好说的了

此外，这种类型的题目确实比直接给三组$(c_i,\ n_i)$要隐晦许多，还是挺不错的

from flag import flagprint(flag)

Crypto-babycrypt

from Crypto.Util.number import getPrime, bytes_to_long

flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())

def genkey():
    e = 0x10001
    p, q = getPrime(256), getPrime(256)
    if p <= q:
      p, q = q, p
    n = p * q
    pubkey = (e, n)
    privkey = (p, q)
    return pubkey, privkey

def encrypt(m, pubkey):
    e, n = pubkey
    c = pow(m, e, n)
    return c

pubkey, privkey = genkey()
c = encrypt(flag, pubkey)

hint = pubkey[1] % (privkey[1] - 1)
print('pubkey:', pubkey)
print('hint:', hint)
print('c:', c)

题目意思很清楚，攻击点只有一个$hint=n%(q-1)$且$p>=q$

下面开始复现

将$n$换成另外一种表达形式，根据同余的性质$a\equiv b\ (mod\ n)$且$c\equiv d\ (mod\ n)$， 则$a+b\equiv c+d\ (mod\ n)$，这里相当于反过来
$n\%(q-1)=((p-1)(q-1)+(p+q-1))\%(q-1)=(p+q-1)\%(q-1)=p%(q-1)$

再把hint带入
$$
hint=p\%(q-1)\notag
$$
即
$$
p=k(q-1)+hint\notag
$$
由条件已知p比q大，所以假设k是正的，而且相同位数的，k不会很大，可爆

已知n，将p替换
$$
n/q=k(q-1)+hint\notag
$$
$$
n=k(q^2-q)+hint\times q\notag
$$
显然可以解一个一元二次方程
$$
kq^2+(hint-k)q-n=0\notag
$$
判断$\Delta =(hint-k)^2+4kn$，或者直接用sage或者python的库解方程，好像k=1就解出来了

话说回来，我觉得泄漏nq也应该算是一种rsa的经典攻击，但网上现在鲜有见到

Crypto-Shamir’s Stingy Sharing

import random, sys
from Crypto.Util.number import long_to_bytes

def bxor(ba1,ba2):
	return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])

BITS = 128
SHARES = 30

poly = [random.getrandbits(BITS) for _ in range(SHARES)]
flag = open("/challenge/flag.txt","rb").read()

random.seed(poly[0])
print(bxor(flag, long_to_bytes(random.getrandbits(len(flag)*8))).hex())

try:
	x = int(input('Take a share... BUT ONLY ONE. '))
except:
	print('Do you know what an integer is?')
	sys.exit(1)
if abs(x) < 1:
	print('No.')
else:
	print(sum(map(lambda i: poly[i] * pow(x, i), range(len(poly)))))

异或，加密函数就是解密函数；需要知道random.getrandbits(len(flag)*8)，也就是需要知道随机种子poly[0]

给的SHARES比较小，所以应该不是梅森旋转随机数的复原；已知

sum(map(lambda i: poly[i] * pow(x, i), range(len(poly))))

即
$$
\sum_{i=0}^{29}poly{[i]}\times x^i\notag
$$
x为我们的输入，显然当x=1，输出的就是poly的和
$$
poly[0]+poly[1]+poly[2]+poly[3]+…+poly[29]\notag
$$
如果我们知道
$$
poly[0]+poly[1]\times 2+poly[2]\times 2^2+poly[3]\times 2^3+…+poly[29]\times 2^{29}\notag
$$
等一系列的，估计可以搞点事情；可惜同一组poly只能求到关于一个x的多项式

找了许久才在la佬博客里找到关于Shamir的攻击

设poly[0]为$s_1$，poly[0]+2为$s_2$，$poly[1]+poly[2]+poly[3]+…+poly[29]$为A，p我们整一个256位的素数
$$
s_1+A-f(x)_1\equiv 0\ (mod\ p)\notag
$$
$$
s_2+A-f(x)_2\equiv 0\ (mod\ p)\notag
$$
$$
s_1+2-s_2\equiv 0\ (mod\ p)\notag
$$

#Sage
a = 1
b = 2


y1 = 4597744014826739716773723494617979066503
y2 = y1 + 2
PR.<s1,s2,A> = PolynomialRing(Zmod(p))
f1 = s1 + A - y1
f2 = s2 + A - y2
f3 = a * s1 + b - s2
Fs = [f1, f2, f3]
I = Ideal(Fs)
B = I.groebner_basis()
print('s1 =', ZZ(-B[0](0, 0, 0)))
print('s2 =', ZZ(-B[1](0, 0, 0)))

不太行，只有一个方程，再怎么变也不可能变成方程组

然后尚师傅说不是要知道第一位吗，不妨我们给的x是100000000000000000000000000000000000000000000，差不多凑到128位多点，这样就会得到

没错，poly的每一个值都暴露在眼前

最终的exp如下

import random
from Crypto.Util.number import *


def bxor(ba1, ba2):
    return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])


cipher = '6068879a5da40b08757b59a3924302244a52c2162505e531ccd061739e03d2'

ploy0 =  324624027062034109200467879481074306259
for k in range(10, 1000):
    random.seed(ploy0)
    print(bxor(long_to_bytes(int(cipher, 16)), long_to_bytes(random.getrandbits(k * 8))))

Crypto-rotoRSA（not solve)

from sympy import poly, symbols
from collections import deque
import Crypto.Random.random as random
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

def build_poly(coeffs):
    x = symbols('x')
    return poly(sum(coeff * x ** i for i, coeff in enumerate(coeffs)))

def encrypt_msg(msg, poly, e, N):
    return long_to_bytes(pow(poly(msg), e, N)).hex()

p = getPrime(256)
q = getPrime(256)
N = p * q
e = 11

flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())

coeffs = deque([random.randint(0, 128) for _ in range(16)])


welcome_message = f"""
Welcome to RotorSA!
With our state of the art encryption system, you have two options:
1. Encrypt a message
2. Get the encrypted flag
The current public key is
n = {N}
e = {e}
"""

print(welcome_message)

while True:
    padding = build_poly(coeffs)
    choice = int(input('What is your choice? '))
    if choice == 1:
        message = int(input('What is your message? '), 16)
        encrypted = encrypt_msg(message, padding, e, N)
        print(f'The encrypted message is {encrypted}')
    elif choice == 2:
        encrypted_flag = encrypt_msg(flag, padding, e, N)
        print(f'The encrypted flag is {encrypted_flag}')
    coeffs.rotate(1)

Re-verybabyrev

checksec一下，发现是小端序，这点很重要，后面我在s1的每一个地方都逆序了

int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
{
  __int64 s1[12]; // [rsp+0h] [rbp-100h] BYREF
  char v4; // [rsp+60h] [rbp-A0h]
  char s[140]; // [rsp+70h] [rbp-90h] BYREF
  int i; // [rsp+FCh] [rbp-4h]

  setvbuf(stdout, 0LL, 2, 0LL);
  memset(s, 0, 0x80uLL);
  s1[0] = 'EH\x1D\x12\x17\x11\x13\x13';
  s1[1] = '\t_B,&\vAE';
  s1[2] = 'T\x1BVV=l_\v';
  s1[3] = 'X\\\v<)EA_';
  s1[4] = '@*lT\t]_\0';
  s1[5] = 'K_BH\'j\x06\x06';
  s1[6] = 'l^]C,-BV';
  s1[7] = 'k1^CG\aA-';
  s1[8] = '^TI\x1Cn;\nZ';
  s1[9] = '((G^\x054+\x1A';
  s1[10] = '\x06\x04P\a;&\x11\x1F';
  s1[11] = '\nwH\x03\x05\v\r\x04';
  v4 = 0;
  printf("Enter your flag: ");
  fgets(s, 128, stdin);
  i = 0;
  if ( s[0] != 114 )
  {
    puts("Nope!");
    exit(0);
  }
  while ( i <= 126 )
  {
    s[i] ^= s[i + 1];
    ++i;
  }
  if ( !memcmp(s1, s, 97uLL) )
  {
    puts("Correct!");
    exit(1);
  }
  puts("Nope!");
  exit(0);
}

然后也很像有一个初始状态的流密码，依次异或回去就好了

#!/usr/bin/env python
# -*- coding: utf-8 -*-
s1 = b''
s1 += b'EH\x1D\x12\x17\x11\x13\x13'[::-1]
s1 += b'\t_B,&\vAE'[::-1]
s1 += b'T\x1BVV=l_\v'[::-1]
s1 += b'X\\\v<)EA_'[::-1]
s1 += b'@*lT\t]_\0'[::-1]
s1 += b'K_BH\'j\x06\x06'[::-1]
s1 += b'l^]C,-BV'[::-1]
s1 += b'k1^CG\aA-'[::-1]
s1 += b'^TI\x1Cn;\nZ'[::-1]
s1 += b'((G^\x054+\x1A'[::-1]
s1 += b'\x06\x04P\a;&\x11\x1F'[::-1]
s1 += b'\nwH\x03\x05\v\r\x04'[::-1]
s1 = s1.decode()
flag = 'r'
t = chr(ord(s1[0]) ^ ord('r'))
for i in s1[1:]:
    flag += t
    t = chr(ord(i) ^ ord(t))
print(flag)

Bsides Noida CTF

Crypto-Xoro

#!/usr/bin/env python3
import os

FLAG = open('flag.txt','rb').read()

def xor(a, b):
    return bytes([i^j for i,j in zip(a,b)])

def pad(text, size):
    return text*(size//len(text)) + text[:size%len(text)]

def encrypt(data, key):
    keystream = pad(key, len(data))
    encrypted = xor(keystream, data)
    return encrypted.hex()


if __name__ == "__main__":
    print("\n===== WELCOME TO OUR ENCRYPTION SERVICE =====\n")
    try:
        key = os.urandom(32)
        pt = input('[plaintext (hex)]>  ').strip()
        ct = encrypt(bytes.fromhex(pt) + FLAG, key)
        print("[ciphertext (hex)]>", ct)
        print("See ya ;)")
    except Exception as e:
        print(":( Oops!", e)
        print("Terminating Session!")

不会，一个pad给我整蒙了，看了CTFTIME上的WP

pad不深究，就是将key填充至和pt+flag一样的长度，那么这样想就很简单了吧

根据cipher以及我们自己定的pt是完全可以得到key的

就是要知道一个字节相当于两个字符，所以要知道key，pt的长度起码是有64个字符长

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def xor(a, b):
    return bytes([i ^ j for i, j in zip(a, b)])


def pad(text, size):
    return text*(size//len(text)) + text[:size % len(text)]


def encrypt(data, key):
    keystream = pad(key, len(data))
    encrypted = xor(keystream, data)
    return encrypted

pt = '4'*64
cipher = 'b4547524f42baec143f1d9cb57e3d35eff4b7f3e13f551a2cb0eb73600d6ac1bb2437f0fd90b8bfe6fdaead070c6f945c2604e2535c37087e415a73a01cdb010a24f0e418f4e97'
key = xor(bytes.fromhex(pt), bytes.fromhex(cipher)[:32])
print(encrypt(bytes.fromhex(cipher), key))

Crypto-MACAW

#!/usr/bin/env python3
from topsecrets import iv, key, secret_msg, secret_tag, FLAG
from Crypto.Cipher import AES

iv = bytes.fromhex(iv)

menu = """
/===== MENU =====\\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/
"""

def MAC(data):    
    assert len(data) % 16 == 0, "Invalid Input"
    assert data != secret_msg, "Not Allowed!!!"

    cipher = AES.new(key, AES.MODE_CBC, iv)
    tag = cipher.encrypt(data)[-16:]
    return tag.hex()

def AUTH(tag):
    if tag == secret_tag:
        print("[-] Successfully Verified!\n[-] Details:", FLAG)
    else:
        print("[-] Verification Flaied !!!")

if __name__ == "__main__":
    print(secret_msg)
    try:
        for _ in range(3):
            print(menu)
            ch = input("[?] Choice: ").strip().upper()
            if ch == 'M':
                data = input("[+] Enter plaintext(hex): ").strip()
                tag = MAC(bytes.fromhex(data))
                print("[-] Generated tag:", tag)
                print("[-] iv:", iv.hex())
            elif ch == 'A':
                tag = input("[+] Enter your tag to verify: ").strip()
                AUTH(tag)
            else:
                print("[!] Invalid Choice")
                exit()
    except Exception as e:
        print(":( Oops!", e)
        print("Terminating Session!")

Why are MACAWS becoming Another Endangered Species?

AES，CBC；拿出DAS签到的图

只要data == secret_msg就好了

assert data != secret_msg, "Not Allowed!!!"

那么显然看主函数的第一段，secret_msg就是Welcome to BSidesNoida!! Follow us on Twitter...，然后转一下十六进制编码；不是很懂代码的逻辑，但是将得到的tag发过去就得到flag了BSNoida{M4c4w5_4r3_4d0r4b13}

等等

我收回我刚才的话，上面的分析是不对的，不是只要data == secret_msg就好了，而是要data != secret_msg，但真正的secret_msg还有一个/n，而且如果加上\n又不满足第一个条件

Crypto-Macaw_Revenge

继续上一题

#!/usr/bin/env python3
from Crypto.Cipher import AES
import os

with open('flag.txt') as f:
    FLAG = f.read()


menu = """
/===== MENU =====\\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/
"""

def MAC(data, check=False):    
    assert len(data) % 16 == 0, "Invalid Input"

    if check:
        assert data != secret_msg, "Not Allowed!!!"

    cipher = AES.new(key, AES.MODE_CBC, iv)
    tag = cipher.encrypt(data)[-16:]
    return tag.hex()

def AUTH(tag):
    if tag == secret_tag:
        print("[-] Successfully Verified!\n[-] Details:", FLAG)
    else:
        print("[-] Verification Flaied !!!")

if __name__ == "__main__":
    iv = os.urandom(16)
    key = os.urandom(16)
    secret_msg = os.urandom(48)
    secret_tag = MAC(secret_msg)

    print(f"[+] Forbidden msg: {secret_msg.hex()}")
    try:
        for _ in range(3):
            print(menu)
            ch = input("[?] Choice: ").strip().upper()
            if ch == 'M':
                data = input("[+] Enter plaintext(hex): ").strip()
                tag = MAC(bytes.fromhex(data), check=True)
                print("[-] Generated tag:", tag)
                print("[-] iv:", iv.hex())
            elif ch == 'A':
                tag = input("[+] Enter your tag to verify: ").strip()
                AUTH(tag)
            else:
                print("[!] Invalid Choice")
                exit()
    except Exception as e:
        print(":( Oops!", e)
        print("Terminating Session!")

考点CBC，无攻击手法，完全是对流程图的改造

有两种做法，pwntools用的不太熟，直接手动交互了

这是第一次secret_tag = MAC(secret_msg)的流程

已知明文，要求密文块2；如果我们能得到第三次加密偏移量IV’，这样放进AES加密就能得到密文块2

第一种做法

第一次送明文块0去异或，将得到的密文块0与已知的IV以及明文块1异或，再将得到的结果拼接上明文块2送去AES加密，将得到密文块2在第三次verify时输入，得到flag

还有一种做法类似，将明文块0和1和起来进行第一次加密

脚本写得太捞就不贴了

Crypto-baby_crypto

from functools import reduce
from operator import mul
from secrets import token_bytes
from sys import exit

from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes


def main():
	a = getPrime(512)
	b = reduce(mul, [getPrime(64) for _ in range(12)])
	flag = open("flag.txt", 'rb').read()
	flag_int = bytes_to_long(flag + token_bytes(20))
	if flag_int > b:
		print("this was not supposed to happen")
		exit()
	print("Try decrypting this =>", pow(flag_int, a, b))
	print("Hint =>", a)
	print("Thanks for helping me test this out,")
	print("Now try to break it")
	for _ in range(2):
		inp = int(input(">>> "))
		if inp % b in [0, 1, b - 1]:
			print("No cheating >:(")
			exit()
		res = pow(flag_int, inp * a, b)
		print(res)
		if res == 1:
			print(flag)


if __name__ == "__main__":
	try:
		main()
	except Exception:
		print("oopsie")

很像RSA的n未知，参考CTF Wiki-RSA选择明文攻击

现在摆在我们面前的就有两条路子，因为只能循环两遍，所以用了选择明文攻击后，就不能继续按照题目的思路将res变成1了

yafu和椭圆曲线分解都能出来

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from functools import reduce
from operator import mul
from Crypto.Util.number import long_to_bytes
from gmpy2 import *


c = 20203085489987560014293976792631284029865794716340199579184268249383267835221417646400206440280554986191046482410144704655493648278552773961629440429092902828200586765600142014056717474264892592819336816357109261631354026033919601
a = 9199145544343906785257237030819067819650706729960940719583789075672838085664891493875966859020683165873915514690329495098632224089726035146839813982911647
res1 = 11556035784052138857307507506198973288367411883788209466242603646975181772393709048116382813114147667439254757077994923530326940311774811806341624846606432421390147764067475588289999480688178793625567838893122456687987320482961046
res2 = 31851104354654545190670904771335276903093012765843101980283420984000643289499190154554669289569530261009163188908584430876887966331849339667406478926717953660650120468017201255286785290943940825754781159249398489654218469154878634
# b = gcd(c**2-res1, c**3-res2)
b = 35928904747031491940426212169291743107379982701504027058404714745969854722708017688279836779414010447803620033738718602141821905862755021890356381265244649437631255336699627199559173294827426763360743177116198238833752565119866603
p1 = 9663156357322877677
p2 = 17687198236208397641
p3 = 13483379498110779557
p4 = 9827362203600815249
p5 = 16048195073366111129
p6 = 9608504155966563959
p7 = 17592003464121633761
p8 = 16940133308409174757
p9 = 10013743477508178887
p10 = 18085688756284030699
p11 = 15237723747921143731
p12 = 12510206954070273583
p = []
for i in range(1, 13):
    p.append(eval('p'+str(i)))
assert b == reduce(mul, [_ for _ in p])
phi = reduce(mul, [_-1 for _ in p])
d = invert(a, phi)
flag_int = long_to_bytes(pow(c, d, b))
print(flag_int)

---

最后，学到一种Python字节与十六进制编码转化的方法，以及用pwntools里的xor进行字节的异或操作

from pwn import xor

xor(bytes.fromhex(STRING1), bytes.fromhex(STRING2)).hex()