Crypto:FlagHash (497pts ,4 solves) - vsCTF2023

这周末看的Neobeo出的一道题，但是没做出来，有限域上的知识差太远了。跟着writeups复现了一遍，但是还有点不是很清楚的地方，回头再来补一下这点内容。

description

By Neobeo

I wrote a hash function in under ten lines! It uses finite fields to prevent any leakage of the flag.

Hint:
Use the first 20 coefficients of x^2286 and x^2304 (plus the known 20 bytes of the flag), to solve the remaining 9 bytes as a linear system.

题目附件如下：

import string
flag = open('flag.txt').read().strip().encode()
F = GF(127^29, 'x', modulus=list(flag))
FlagHash = lambda s: bytes((F(list(s.encode()))^128).polynomial()[:20]).hex()
    
for _ in range(1337):
    s = ''.join(sample(string.ascii_letters + string.digits, randint(13,37)))
    print(s, FlagHash(s))

随机生成13-37长度的明文，并且计算出他的FlagHash

Analysis

看到题目一开始，感觉很神奇，把他直接转换成稍微复杂点，好理解的代码，如下

import string
flag = b'vsctf{Fake_Flag_with_Padding_}'
PR.<x> = PolynomialRing(GF(127^29))
Q = PR.quo(PR(list(flag)))
x = Q.gens()[0]
def FlagHash(s):
    tmp = list(Q(list(s.encode()))^128)[:20]
    rec = ""
    for _ in range(len(tmp)):
        rec+=hex(int(tmp[_]))[2:].rjust(2,"0")
    return rec

由于他截断了，因此得到这样的值，如果让他 %x^20，可以消掉前面未知部分的系数，那么就变成了，然鹅这样貌似并没有什么卵用。

如果是没有截断的直接最后GCD即可，代码如下

import string
flag = b'vsctf{Fake_Flag_with_Padding_}'

PR.<x> = PolynomialRing(GF(127))
Q = PR.quo(PR(list(flag)))
x = Q.gens()[0]
def FlagHash(s):
    tmp = list(Q(list(s.encode()))^128)# [:20]
    rec = ""
    for _ in range(len(tmp)):
        rec+=hex(int(tmp[_]))[2:].rjust(2,"0")
    return rec

def trans(msg):
    return PR(list(bytes.fromhex(msg)))

fs = {}
for _ in range(4):
    s = ''.join(sample(string.ascii_letters + string.digits, randint(13,37)))
    print(s, FlagHash(s))
    fs[s] = FlagHash(s)

tmp = PR(list(s.encode()))^128 - trans(FlagHash(s))
for s in fs.keys():
    tmp = gcd(tmp,PR(list(s.encode()))^128-trans(FlagHash(s)))
list(tmp*125) == list(flag)

在比赛过程中，并没有求解出来这道题，Hint也没有用上，于是赛后根据 Author’s write-up for FlagHash - HedgeDoc进行学习复现…

Part 1: Recovering the forward map

这里涉及到一个映射是quadratic，由于是一个线性的 Frobenius map。Frobenius map是啥我也具体不清楚，但是在这里field theory - Frobenius Automorphism as a linear map - Mathematics Stack Exchange给出了一个理论

Let be the Frobenius automorphism on . We can view as ab n-dimensional vector space over . In this case, is a linear transformation.

本题中给出的p=127,n=29，那么当这个映射时，是产生了一个线性变换的，即

其中M是一个29*29的矩阵。

那么原映射

这里是如何表达上的转换思路，暂时没啥想法，当然可能存在一点点小问题我的解释(欢迎来锤)。

由此我们可以得到与这一群矩阵，这里我的想法是把矩阵当成1 *（29^2）的空间上使用841条已知值（因为比较困难去表示，只有展平了会相对好弄），可以求解出来，但是我的脚本写的慢，

Ms = []
for _ in range(1):
    F = PolynomialRing(GF(127),29*29,'x')
    xs = F.gens()
    Mtmp = Matrix(F,29,29,xs)

    s_mat = []
    v_tar = []
    coefs = []
    for i in trange(29*29):
        s_mat = vector(F,vs[i][0])
        ti = s_mat*Mtmp*s_mat
        coef = [0 for _ in range(29*29)]
        for __ in ti.variables():
            coef[xs.index(__)] = ti.coefficient(__)
        coefs.append(coef)
        v_tar.append(vs[i][1][_])
    coefs_ = Matrix(GF(127),29*29,29*29,coefs)
    targe_ = Matrix(GF(127),29*29,  1  ,v_tar)
    M_ = coefs_.solve_right(targe_)
    Ms.append(M_)

出题人的脚本又快又简洁….tnbl

1 2	mat = matrix(GF(127), [[x*y for x in v_in for y in v_in] + v_out for v_in, v_out in vs]) soln = mat[:,:841].solve_right(mat[:,841:])

这些矩阵可以完全确定映射，因此现在可以对想要的任何字符串进行哈希处理（只要它不超过 29 个字符）。

Part 2: Recovering first 20 bytes of flag

我们发现前五行如下

sage: soln[:5]
[  1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[ 37  89  83 121   2  50  93  14  75  68 108  32  52  58  53  30  65 102 103  33]
[108   3  88  52  51  88  10 118 109 106  37  94  55  88  54  74  24  85  39  54]
[  1  66  18 100  90 102  44 116  57  23   9   4  56  73   6  31  31  87  74   6]
[ 14  59  74  30 121  50   0  20  45  11  37  47  31  96  99 124  32  63  18  54]

下面是我的代码跑的，M1就是第一列的841个参数的前5个，可以check一下

sage:M_[0:5]
[  1]
[ 37]
[108]
[  1]
[ 14]

这些行对应于多项式（的前 20 个系数）：

事实上，对于任意的，可以通过这个矩阵的行得到的前20项。

这是咋推出来的（好奇.jpg，因为x^p+x是kernel吗？）

感谢来自utaha的解答其中可以发现这个Frobenius Automorphism满足在GF(127)情况下满足

那么很容易就可以得到的值，而这个又包含了的多项式，因此如果把他的系数弄出来的话，就可以得到一个类似上面这样的矩阵，然后求解线性方程组，即可以得到每一行应该是的值了。

可以通过第二条计算x^127%flag的前20个的值；当的时候得到的的值；那么可以得知和

x127 = soln[1] - vector([i==1 for i in range(20)])
x128 = soln[30]
# x127 = (37, 88, 83, 121, 2, 50, 93, 14, 75, 68, 108, 32, 52, 58, 53, 30, 65, 102, 103, 33)
# x128 = (66, 125, 124, 79, 8, 116, 64, 63, 56, 124, 91, 65, 125, 2, 15, 76, 22, 26, 125, 87)

其中，只是右移了一位，因此可以知道模的值是的倍数，同时flag是以’v’开头的，可以计算出来前20bytes

first20 = x128 - vector([0]+list(x127)[:-1])
first20 *= ord('v') / first20[0]
first20 = bytes(first20)
# first20 = b'vsctf{fl4g_ha5h_is_S'

由于位移，我们可以通过

1	-mod(66,127) * ord('}') / ord('v')

来计算出最后一位的时候移了多少，直接用Neobeo的图来看，这个用在第三步中

Part 3: Recovering the last 9 bytes

现在剩下九个byte需要去恢复。需要了解上面和下面的内容才能从中获得一些信息，或者通过转换，我们可以将一个系数与其右下角的系数联系起来。

在这种情况下，我们实际上可以通过 19 个连续的幂来弥补这9个的差距。Neobeo是使用和，因为是可以很容易得到的。无论如何，对于 2286 和 2304 的情况，我们并不容易获得介于两者之间的所有内容，但是很容易插值，因为我们知道差异是模数移位的线性和。

x2286 = soln[18] - vector([i==18 for i in range(20)])
x2304 = soln[30*18]
# x2286 = (23, 112, 120, 3, 4, 72, 80, 57, 124, 88, 84, 122, 71, 28, 110, 96, 122, 3, 12, 105)
# x2304 = (44, 54, 26, 29, 27, 99, 44, 41, 87, 118, 13, 89, 3, 22, 1, 31, 66, 10, 57, 24)