2023 ImaginaryCTF

admin 2024年9月28日11:57:18评论38 views字数 11232阅读37分26秒阅读模式

上周打的 ImaginaryCTF,比赛期间只做出了几道相对简单的密码学赛题,菜菜。复现的时候更是被狠狠的打击了。

rsa

题目给了三个文件,分别是 flag.enc;private.pem;public.pem;所以我们直接从 private.pem 里面导出私钥然后解密就可以了,基础操作题。

1234567
from Crypto.PublicKey import RSAfrom Crypto.Util.number import bytes_to_long, long_to_byteskey = RSA.importKey(open('private.pem', "rb").read())flag = bytes_to_long(open("flag.enc", "rb").read())print(long_to_bytes(pow(flag, key.d, key.n)))

emoticons

1234567891011
import randomemojis = [n for n in "🌸🍔🐳🚀🌞🎉🍦🎈🐶🍕🌺🎸⚡️🦋🌼🎁"]m = open("text.txt", "rb").read().hex()random.shuffle(emojis)for e, c in zip(emojis, "0123456789abcdef"):  m = m.replace(c, e)open("out.txt", "w").write(m)

题目逻辑很简单,就是将明文编码成十六进制,然后使用类似于简单替换密码,将十六个字符随机映射到十六个emoji图案上。可以看到题目给的输出密文的数据量还是比较大的,所以其实考点应该就是简单的词频分析。

在比赛的时候有点猪脑过载,我就是一点点人工分析过来的,首先考虑 flag 的格式,”ictf{“.hex() == ‘696374667b’,然后我们在密文中找第0,2,6,7个字符相同,第4,8个字符相同的子串,会发现刚好只有一个,于是我们就能确定下来一些字符。然后根据已知的碎片信息一点点分析,在解题代码的注释中我列出了字符替换的逻辑。

1234567891011121314151617181920212223242526272829303132333435
with open("outs.txt","r",encoding = "utf-8") as f:data = f.read()#print(len(data))emojis = [n for n in "🌸🍔🐳🚀🌞🎉🍦🎈🐶🍕🌺🎸⚡🦋🌼🎁"]# "ictf{".hex() ==  '696374667b'for i in range(len(data)):sli = data[i:i+10]if sli[0] == sli[2] == sli[6] == sli[7] and sli[4] == sli[8]:print(i,sli)🎈🐳🎈🌸🍕🎉🎈🎈🍕🎸with open("outs.txt","r") as f:data = f.read()data = data.replace("🎈","6").replace("🍕","7").replace("🐳","9").replace("🌸","3").replace("🎉","4").replace("🎸","b")data = data.replace("🍦","a")# 0a \mdata = data.replace("🎁","2").replace("🐶","0")# 20 " "data = data.replace("🦋","1").replace("🚀","c")# 74797069636🦋6🚀6🚀79 typicallydata = data.replace("🌼","5").replace("⚡","e")# 77726974746🌼6⚡ writtendata = data.replace("🌺","f")# 6🌺6e6c696e65 onlinedata = data.replace("🍔","d")# 656e7669726f6e6🍔656e742e environment.data = data.replace("🌞","8")

PS:赛后看了官方解,只需要随便找一篇英文文章样例,十六进制编码后统计里面出现字符的频率,然后将这一题密文中各个emoji根据出现的频率排列,然后一一替换即可。

signer

12345678910111213141516171819202122232425262728293031323334353637383940414243
import textwrapfrom binascii import crc32from Crypto.Util.number import getPrimep, q = getPrime(1024), getPrime(1024)n = p*qe = 65537d = pow(e, -1, (p-1)*(q-1))PASSWORD = b"give me the flag!!!"print("--------------------------------------------------------------")print("               Welcome to the secure signing app!             ")print("  I will sign whatever you want, except the secret password.  ")print("--------------------------------------------------------------")print()print("--------------------------------------------------------------")print("\n".join(textwrap.wrap(f"{n = }", len("-------------------------------------------------------------"))))print("--------------------------------------------------------------")print()while True:  print("1. Sign")  print("2. Get flag")  choice = int(input())  if choice == 1:    print("Enter message:")    message = input().encode()    # crc32 is secure and has no collisions, but just in case    if message == PASSWORD or crc32(message) == crc32(PASSWORD):      print("Stop this trickery!")      exit()    print("Signature:", pow(crc32(message), d, n))  elif choice == 2:    print("Enter the signature for the password:")    s = int(input())    if pow(s, e, n) == crc32(PASSWORD):      print("You win! The flag is", open("flag.txt").read())      exit()    else:      print("Wrong.")      exit()

题目基于 RSA 签名系统,需要我们给出 PASSWORD = b"give me the flag!!!" 的签名,另外这里的签名不是对消息进行哈希,而是使用 crc32 来表示。我们知道 crc32 只有 4 个字节,因此这样一个多对一的映射在明文输入大于4个字节的时候是非常好碰撞的。所以这里首先计算 crc32(PASSWORD) 得到值 3542523789,不过由于限制

123
if message == PASSWORD or crc32(message) == crc32(PASSWORD):  print("Stop this trickery!")  exit()

我们不能直接输入PASSWORD,也不能输入和 PASSWORD 的 crc32 相等的消息。但是由于 RSA 具有乘法同态,所以我们可以先将 3542523789 分解为 13477 * 262857,然后分别碰撞出 crc32 等于 13477 和 262857 的两个消息,例如 2i_pQM22p6NE。(crc32 碰撞的脚本还是比较好找的,毕竟是 MISC 中 zip 破解的一个考点)然后让服务器给这两条消息签名得到 $sig_1,sig_2$,然后计算 $sig_1\cdot sig_2 \pmod n$ 就是 PASSWORD 的签名了。发送给服务器就可以获得 flag 了。

tan

12
print(tan(int.from_bytes(open("flag.txt", "rb").read().strip(), "big")).n(1024))# -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714

来自maple的 oneline crypto, $tan(flag) = c$,原本是 $tan$ 是可以由 $arctan$ 逆回去的,不过因为 $tan$ 函数的周期是 $2\pi$,所以 $arctan(c) \equiv flag \pmod{2\pi}$,写成等式有 $arctan(c) = flag + 2k \pi,k \in \mathbb{Z}$,

考虑构造格 $M =\begin{bmatrix} arctan(c)& 1 & 0 & 0\newline\pi&0&1 & 0\newline 1&0&0 & 1 \newline\end{bmatrix}$,会存在向量 $l = [-1 \ 2k \ flag]$ 使得 $l \times M = [0 \ -1 \ 2k \ flag]$,其实跟背包问题格子差不多。为了保证得到目标向量,我们也考虑给格子的第一列都乘上一个比较大的数,比如 $10^{307}$ 这样(刚好 $c$ 的小数点后面有307位)

1234567891011121314
c = -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714ac = atan(c)shift = 10^307 m=[[ac * shift,             1,0,0],   [(pi.n(1024)) * shift,   0,1,0],   [1  * shift,             0,0,1]]M = matrix(QQ,m)L = M.LLL()long_to_bytes(abs(L[0][-1]))# b'ictf{can_you_break_sin_or_cos_too?}'

PS:由于取整会导致误差,所以格基规约后矩阵的第一行向量的第一个元素并不是 0 。

wasteful

123456789101112131415161718192021222324252627282930313233
from Crypto.Util.number import *from math import gcddef keygen(sz):    p = getPrime(sz // 2)    q = getPrime(sz // 2)    n = p * q    phi = (p - 1) * (q - 1)    e_fast = getPrime(sz // 2)    # to make encryption more time consuming :P    e_slow = e_fast + getPrime(sz // 3) * phi    d = pow(e_fast, -1, phi)    return (n, e_slow), (n, e_fast), (n, d)def encrypt(pub, m):    n, e = pub    return pow(m, e, n)def decrypt(priv, c):    n, d = priv    return pow(c, d, n)pub, pub_fast, priv = keygen(2048)m = bytes_to_long(open("flag.txt", "rb").read().strip())c = encrypt(pub, m)assert c == encrypt(pub_fast, m)assert decrypt(priv, c) == mprint(f"{pub = }")print(f"{c = }")

题目基于 RSA 公钥加密系统,$c \equiv m^e \pmod n$,给出了公钥对和密文 $c$。区别于正常的 RSA,这里给出的公钥指数是 $e’ = e + prime \cdot phi$,$prime$ 是一个 682 比特的素数。而 $e$ 本身也是一个 1024 比特的素数。

考虑组成 $e’$ 两项的大小关系,计算 $\frac{e’}{n}$,由于 $\varphi(n) \approx n$,所以 $\frac{e’}{n} \approx prime$,我们只需要在附近 $\pm10$ 的地方找一下就能找到 $prime$ 了。

随后我们计算 $e’//prime$ ( // 表示整除 ),由于 $phi$ 是2048 比特 $e$ 是 1024 比特,所以 $phi = e’//prime + \epsilon $ 其中 $\epsilon$ 可以看作一个 342比特的噪声。也就意味着我们能够知道 $phi$ 的高 1706 比特。根据 $phi = n + 1 - (p+q)$ 我们即可获取 $p+q$ 的高位,在使用一下平方差公式 $(p+q)^2 - 4n = (p-q)^2$,就能得到 $p-q$ 的高位,从而 $p = ((p+q)+(p-q))/2$ 得到 $p$ 的高位,然后利用 coppersmith 就能得到完整的 $p$,从而分解 $n$,解密得到 flag

123456789101112131415161718192021222324
from Crypto.Util.number import *from gmpy2 import irootn,e = (, )c = pr = e // n + 1print(pr)print(isPrime(pr))phibar = e // prp_a_qbar = n+1-phibarp_s_qbar = iroot((p_a_qbar**2-4*n),2)[0]pbar = int((p_a_qbar+p_s_qbar)//2)R.<x> = Zmod(n)[]f = pbar + xp0 = f.small_roots(X=2^400,beta=0.4)[0]p = int(pbar+p0)q = int(n//p)d = inverse(e,(p-1)*(q-1))m = pow(c,d,n)print(long_to_bytes(int(m)))# b'ictf{just_an_obligatory_coppersmith_challenge}'

以上就是比赛期间搞出来的五道题目了,猜牌游戏比赛的时候看了一半不太会,赛后对着官方 exp 尝试复现了下。

blind_guess

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
#!/usr/bin/env python3from random import getrandbitsfrom galois import GFimport numpy as npDECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"F = GF(13) # lucky numbern = 10# Let's not use a singular matrix, please.# We do quality random over here.M = [[0]]while np.linalg.det(M) == 0:    M = F.Random((n, n))money = 15000cards = F.Random(n)while all(int(c) == 0 for c in cards):    cards = F.Random(n)while money > 0:    print('balance:', money)    choice = input('> ')    if choice == 'buy flag':        if money < 1_000_000_000:            print("You're too poor!")            continue        from redacted import FLAG        money -= 1_000_000_000        print("What a guess god! Here's your flag:", FLAG)    elif choice == 'play':        bet = int(input('bet: '))        assert money >= bet > 0        print("Can you blindly guess my cards?")        cards = np.linalg.matrix_power(M, getrandbits(32)) @ cards  # shuffle cards        guess = M @ F([*map(DECK.index, input('guess: ').split())]) # blind guess        total = sum(cards == guess)        print(f'You guessed {total} cards! My hand was:', *[DECK[c] for c in cards])        money += 2*(total - 5)*bet    elif choice == 'exit':        print("Chickened out, huh? No flag for you.")        exit()print("Woops... Looks like you guessed your way out of money :>")

题目是一个猜牌游戏,初始的拥有 15000 的 money,每一次猜牌可以自定义下注 bet,随后根据猜对的数量进行获利,获利规则为 2*(total - 5)*bet,即猜对六张及以上才可以获利。到 money 大于 1_000_000_000 后就可以获取 flag。

注意到每一次使用 $M^{random} \cdot cards$ 来“洗牌”,$cards$ 是上一轮的手牌,并且会在猜完后展示出来;$M$ 是一个行列式不为 0 的随机矩阵。$random$ 是由 getrandbits(32) 生成而来。那么思路就比较清晰了。

刚开始我们设 $bet=1$,然后就乱猜,主要目的就是看他的手牌,然后根据前后手牌的变化来 “想办法” 搞到这个 $random$,搞到 624 个之后我们就能够预测后续的 $random$,那个时候我们就一直 all in 就行了。

那么这个 “想办法” 该想什么样的办法呢,这是解题的关键,也是比赛的时候没想通的2333。如果我们能够知道 $M$ 和 $M^{random}$,那么我们就需要解一个矩阵的离散对数问题;这个好像可以取行列式来做,这样就转化为有限域下的离散对数问题了。那怎么搞到 $M$ 或者 $M$ 的行列式呢?

哎?注意到这个guess不是说你输入啥猜的就是啥,他会有一步处理,$guess = M \times input$,所以要满足的是 $M \times input = M ^{random} \times cards$。

那么,如果我们在输入的时候,构造的特殊一点,比如 input = [1 0 0 0 ...],那么在经过 $M \times input$ 后,guess 的值就是 $M$ 第一列。不过我们不能直接获取到自己的 guess,只能根据最后展示的手牌和猜对的牌数来判断 guess 的值。那么怎么搞呢?撞!

guess 每个位置的牌都有 13 种可能,当前仅当猜对的总数为 0 的时候,我们就能够进行一次否定,可以保证每一个位置都不是所展示手牌的对应位置的牌。

当每个位置的可能都只剩 1 的时候,我们就获取了 $M$ 的一列值,然后进行下一列的撞。

(由于远程环境挂了,本地起 process 遇到点问题,就稍微改了改源代码在本地验证了)

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
from operator import lshift, rshiftfrom tqdm import trangefrom random import getrandbitsfrom galois import GFimport numpy as npDECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"F = GF(13) # lucky numbern = 10# Let's not use a singular matrix, please.# We do quality random over here.global MM = [[0]]while np.linalg.det(M) == 0:    M = F.Random((n, n))global moneymoney = 15000global cardscards = F.Random(n)while all(int(c) == 0 for c in cards):    cards = F.Random(n)def local_game(choice,bet,inputs):    global money    global cards    while money > 0:        #print('balance:', money)        if choice == 'buy flag':            if money < 1_000_000_000:                print("You're too poor!")                continue            from redacted import FLAG            money -= 1_000_000_000            print("What a guess god! Here's your flag:", FLAG)        elif choice == 'play':            assert money >= bet > 0            #print("Can you blindly guess my cards?")            cards = np.linalg.matrix_power(M, getrandbits(32)) @ cards  # shuffle cards            guess = M @ F([*map(DECK.index, inputs.split())]) # blind guess            total = sum(cards == guess)            #print(f'You guessed {total} cards! My hand was:', *[DECK[c] for c in cards])            money += 2*(total - 5)*bet            return [int(c) for c in cards],total        elif choice == 'exit':            print("Chickened out, huh? No flag for you.")            exit()#print("Woops... Looks like you guessed your way out of money :>")n = 10hands = []col = [set(range(13)) for _ in range(n)]MM = []i = 0while i < n:    guesscard = i*[0] + [1] + (n-i-1)*[0]    hand, total = local_game('play',1, ' '.join(DECK[int(c)] for c in guesscard))    hands.append(hand)    if total == 0:        for r, c in zip(col, hand):            r.discard(c)        if all(len(r) == 1 for r in col):            MM.append([c for r in col for c in r])            col = [set(range(13)) for _ in range(n)]            i += 1            print('i =', i)print('M =', MM)print(f"Collected {len(hands)} hands")# M = [[2, 4, 3, 2, 5, 7, 9, 11, 7, 10], [12, 0, 7, 9, 1, 3, 0, 5, 5, 10], [0, 4, 1, 5, 10, 10, 5, 11, 2, 3], [4, 6, 5, 4, 2, 8, 0, 11, 0, 0], [12, 10, 8, 7, 12, 4, 10, 12, 3, 1], [6, 11, 2, 11, 7, 11, 10, 7, 12, 12], [2, 10, 1, 7, 2, 7, 0, 8, 1, 10], [10, 0, 8, 10, 12, 5, 4, 10, 5, 12], [10, 11, 8, 9, 11, 1, 9, 7, 5, 3], [11, 1, 8, 4, 3, 8, 6, 2, 11, 9]]# Collected 1403 hands

在大约经过1400 次暴力后我们能够拿到 $M$ ,不过想通过解离散对数获取 $random$ 的话,也还得获取到 $M^{random}$。根据题目我们有式子 $card_2 = M^{random} \cdot card_1$,由于线性代数学的一团糟,并不太知道接下来怎么搞,于是选择先“逃课”。根据 github 里巨人提供的板子

12345678910111213141516171819202122232425262728293031
# https://github.com/jvdsn/crypto-attacks/blob/master/shared/matrices.pydef dlog_equation(A, x, y):    """    Computes l such that A^l * x = y, in GF(p).    :param A: the matrix A    :param x: the vector x    :param y: the vector y    :return: l, or None if l could not be found    """    assert A.is_square()    # TODO: extend to GF(p^k) if necessary?    J, P = A.jordan_form(transformation=True)    x = P ** -1 * x    y = P ** -1 * y    r = 0    for s1, s2 in zip(*J.subdivisions()):        S = J.subdivision(s1, s2)        assert S.is_square()        n = S.nrows()        r += n        if n >= 2:            x1 = x[r - 1]            x2 = x[r]            y1 = y[r - 1]            y2 = y[r]            l = S[n - 1, n - 1] * (y1 - x1 * y2 / x2) / y2            return int(l)    return None

利用我们前面一千四百多次的手牌和撞出来的 $M$ 直接调 dlog_equation 就能获取所有 $random$ 了,然后就是一个基础的 MT19937 状态恢复然后预测,这里就不过多赘述了。

不好意思,就到底为止了,后面的题目连题面都看不懂了,elf 文件,so 文件,factor 文件,wtf??????也许以后能看懂呢?也许叭…

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081,也可以邮件至 [email protected] - source:Van1sh的小屋

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年9月28日11:57:18
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   2023 ImaginaryCTFhttps://cn-sec.com/archives/3093673.html

发表评论

匿名网友 填写信息