SSS crypto challenge from HexionCTF 2020. This was the only crypto chall (out of 3) that I found interesting. The first one was a standard XOR challenge, and the other one was an RSA LSB oracle.
Math is so beautiful and can always be used for cryptographic encryption!
nc challenges1.hexionteam.com 5001
from Crypto.Util.number import bytes_to_long, getPrime from random import randint from secret import flag MIN = randint(0x30, 0x40) P = 2**521 - 1 def eval_at(poly, x, prime): """Evaluates polynomial (coefficient tuple) at x""" accum = 0 for coeff in reversed(poly): accum *= x accum += coeff accum %= prime return accum def main(): poly = [bytes_to_long(flag.encode())] poly.extend(set([randint(1, P - 1) for i in range(MIN)])) print("┌───────────────┐") print("│ SSS Encryptor │") print("└───────────────┘") print("Enter text to encrypt, leave empty to quit.") while True: data = input(">>> ") if bytes_to_long(data.encode()) % P == 0: break print(eval_at(poly, bytes_to_long(data.encode()), P)) if __name__ == "__main__": main()
We are presented with some cryptosystem that encrypts a message by evaluating the polynomial with . The polynomial's constant term is the flag, and the polynomial will have up to 64 terms. The oracle gives us the ability to encrypt any number of messages, with the constraint that the message cannot be the value of or a multiple of . If we were allowed to send , the evaluation of the polynomial at this value would simply return the constant term (i.e. the flag).
We can then set the coefficients of the polynomial as our unknowns. We write
where is the flag.
It is clear that if we have as many pairs of messages and their encryptions as the number of coefficients in the polynomial, we can solve the system of equations and recover the coefficients. For example, if we know , then we can write
similarly, if we know , then we can write
We can then write the equations in matrix form:
So once we get the values , we simply need to solve for the coefficient vector. This can easily be done by taking the inverse of the big matrix on the left and left multiplying it with the values matrix on the right hand side of the equation. That is,
Implementing this with sage is the way to go as we can easily specify that values are elements of and it'll automatically perform all operations within the field.
Note: I was having issues asking for the decryption of the newline byte so in the implementation, I ask for the encryption of
\x0e up to
\x4d. The theory is the exact same.
We use this script to get the value pairs:
from pwn import remote from Crypto.Util.number import long_to_bytes conn = remote('challenges1.hexionteam.com', 5001) V =  for i in range(0xe, 0x40+0xe): conn.recvuntil(b'>>> ') conn.sendline(long_to_bytes(i)) enc = int(conn.recvline().strip()) print(enc) V.append(enc) open('vs.py', 'w').write('V = ' + str(V))
And then to solve the challenge:
from Crypto.Util.number import * from vs import V P = pow(2,521) - 1 F = GF(P) xvals = list(range(0xe, 0x40+0xe)) V = vector(F, V) M = Matrix(F, [[pow(x, i) for i in range(0x40)] for x in xvals]) poly = M.inverse()*V print(long_to_bytes(poly))