In this challenge, we are given a file called lowdown.sage. The challenge implements a custom signature scheme. If we are able to forge a signature for a given message, we get the flag. The challenge first generates the key and the random message to sign:

def makey(k):
    while True:
        g = random_matrix(F, k)
        if g.is_invertible():
            ng = 1 << 192 # g.order()
            break
    r, a = [randint(2, ng - 2) for _ in '01']
    gg = g ** r
    pkey, skey = (g, gg ** a), r
    return(pkey, skey)

global F, k
F = GF(256)
k = 10
pkey, skey = makey(k)

msg = ''.join([string.printable[randint(0, 85)] for _ in range(40)]).encode()

It picks a random matrix $g \in GL(10, F)$ (invertible 10$\times$10 matrix with elements on the field $F$) and generates two random numbers $r$ and $a$. The private key is the random number $r$ and the public key is composed by the matrix $g$ and the matrix $g^{ra}$.

Note that elements of the field $F$ are represented as polynomials of degree 7 with binary coefficients:

sage: [F.random_element() for _ in range(5)]
[z8^6 + z8^5 + z8^3 + 1,
 z8^6 + z8 + 1,
 z8^7 + z8^6 + z8^4 + z8^3,
 z8^7 + z8^5 + z8^4 + z8^3 + z8^2 + z8 + 1,
 z8^5 + z8^4 + z8^2]

Then, in the main loop, we have:

while True:
		pr("| Options: \n|\t[G]et the flag \n|\t[P]ublic Key \n|\t[S]ign a message \n|\t[V]erify signature \n|\t[Q]uit")
		ans = sc().decode().lower().strip()

We can sign short messages:

elif ans == 's':
    pr(border, 'Send your message to sign: ')
    _msg = sc().strip()
    if len(_msg) >= 10:
        die(border, 'Sorry, I sign only short messages! :/')
    _s, _t = sign(pkey, skey, _msg)
    pr(border, f's = {M2i(_s)}')
    pr(border, f't = {M2i(_t)}')

We can verify the signature for any message:

elif ans == 'v':
    pr(border, 'Send your signature to verify: ')
    _sgn = sc().split(b',')
    try:
        _s, _t = [int(_) for _ in _sgn]
        _sgn = (Hinv(_s, k), Hinv(_t, k))
        pr(border, 'Send your message: ')
        _msg = sc().strip()
        if verify(_sgn, pkey, _msg):
            pr(border, 'Your message successfully verified :)')
        else:
            pr(border, 'Verification failed :(')
    except:
        pr(border, 'Try to send valid signature!')
        continue

We can get the public key:

elif ans == 'p':
    _g, _ga = pkey
    pr(border, f'g  = {M2i(_g)}')
    pr(border, f'ga = {M2i(_ga)}')

And we can get the flag, supplying a valid signature for the random message:

if ans == 'g':
    pr(border, 'You should send the valid signature for my given message!')
    pr(border, f'Message = {msg}')
    pr(border, 'Send the signature of the above message: ')
    _sgn = sc().split(b',')
    try:
        _s, _t = [int(_) for _ in _sgn]
        sgn = (Hinv(_s, k), Hinv(_t, k))
        if verify(sgn, pkey, msg) and str(_s).startswith('13') and str(_t).startswith('37'):
            pr(border, f'Congratulation! You got the flag!')
            die(border, f'flag = {flag}')
        else:
          pr(border, 'Your signature is not correct!')
    except:
        die(border, 'Exiting...')

Besides the signature being correct, the s value needs to start with 13 and the t value needs to start with 37.

The challenge has several functions to transform a matrix into a integer and the other way around. These are just helper functions:

def h(a):
    if a == 0:
        return 0
    else:
        g = F.gen()
        for _ in range(1, 256):
            if g ** _ == a:
                return _

def H(M):
    assert M.nrows() == M.ncols()
    k, _H = M.nrows(), []
    for i in range(k):
        for j in range(k):
            _h = h(M[i, j])
            _H.append(bin(_h)[2:].zfill(8))
    return ''.join(_H)

def Hinv(m, k):
    B = bin(m)[2:].zfill(8 * k**2)
    g = F.gen()
    _H = [int(B[8*i:8*i + 8], 2) for i in range(k**2)]
    _M = [0 if _h == 0 else g ** _h for _h in _H]
    M = Matrix(F, [[a for a in _M[k*i:k*i + k]] for i in range(k)])
    return M

def M2i(M):
    _H = H(M)
    return int(_H, 2)

Now, for the signature scheme (the fun part), these are the sign and verify functions:

def random_oracle(msg):
    _h = sha1(msg).digest()
    return bytes_to_long(_h)

def sign(pkey, skey, msg):
	  g, ga = pkey
    ng = 1 << 192 # g.order()
    _h = random_oracle(msg)
    assert _h <= ng
    _g = g ** skey
    n = randint(2, ng - 2)
    s, t = ga * (_g.inverse()) ** (n * _h), _g ** n
    return (s, t)

def verify(sgn, pkey, msg):
    _, ga = pkey
    s, t = sgn
    _h = random_oracle(msg)
    return s * t ** _h == ga

The signature generation first computes _h, which is the sha1 hash of the message (not random at all despite the name of the function). It generates a random number n and computes the signature as the pair $(s, t)$ given by:

$$s = g^{ra} \left(g^{-r}\right)^{n H(m)} = g^{ra - rnH(m)}$$

$$t = \left(g^{r}\right)^n = g^{rn}$$

And the verify function checks that

$$s t^{H(m)} = g^{ra}$$

Verifying the correctness of the scheme is pretty straightforward: suppose that $(s, t)$ is a valid signature for a message $m$, generated with that algorithm. Then,

$$s t^{H(m)} = g^{ra - rnH(m)} \cdot \left(g^{rn}\right)^{H(m)} = g^{ra - rnH(m) + rnH(m)} = g^{ra}$$

However, note that the signature is completely broken: given a public key $g^{ra}$ and a message $m$, all of the parameters in the verification equation are either known or controlled by an attacker: $s, t, H(m), g^{ra}$. If an attacker computes a random matrix $t$, then he can choose $s$ to be:

$$s = g^{ra} t^{-H(m)}$$

and the signature would be a valid one. The strategy in this challenge is to generate random matrices $t$ and compute the corresponding matrix $s$ until they satisfy the 13 and 37 restrictions:

while True:
    max_tries = 100
    try:
        r.sendlineafter(b"[Q]uit\n", b"P", timeout=5)

        r.recvuntil(b"g  = ", timeout=5)
        g = Hinv(int(r.recvline(timeout=5).strip()))

        r.recvuntil(b"ga = ", timeout=5)
        ga = Hinv(int(r.recvline(timeout=5).strip()))

        r.sendlineafter(b"[Q]uit\n", b"G", timeout=5)

        r.recvuntil(b"Message = b", timeout=5)
        msg = r.recvline(timeout=5).strip()[1:-1]
        print(f"Message to sign: {msg}")
        r.recvline(timeout=5)

    except (EOFError, TimeoutError, PwnlibException):
        r.close()
        continue
    _h = random_oracle(msg)
    
    s = Matrix(F, k)
    while not str(M2i(s)).startswith("13") and max_tries > 0:
        t = random_matrix(F, k)
        while not str(M2i(t)).startswith("37"):
            t = random_matrix(F, k)

        s = ga*(t**(-_h))
        max_tries -= 1
	
    r.sendline(f"{M2i(s)},{M2i(t)}".encode())
    r.interactive()
    r.close()

When executing that:

$ python get_flag.py
[+] Starting local process './lowdown.sage': pid 1076973
Message to sign: b"1+i:twQZmW3>=vvy5:WC@B.XSKc8a')e)FCZMSyl"
[*] Switching to interactive mode
┃ Congratulation! You got the flag!
┃ flag = flag{flag_for_testing}
┃ Exiting...
[*] Got EOF while reading in interactive