Paradigm CTF 2022: Fun Reversing Challenge

FunReversingChallenge.sol

// SPDX-License-Identifier: UNLICENSED

// Challenge author: stong (cts), Zellic Inc.
// Challenge prepared for Paradigm CTF 2022

pragma solidity ^0.8.13;

import "forge-std/console.sol";

library Rijndael {
    function gal_add(uint8 a, uint8 b) public pure returns (uint8) {
        return a ^ b;
    }

    function gal_mul(uint8 a, uint8 b) public pure returns (uint8) {
        uint8 res = 0;
        for (; b != 0; b >>= 1) {
            if ((b & 1) != 0)
                res ^= a;
            if ((a & 0x80) != 0)
                a = (a << 1) ^ 0x1b;
            else
                a <<= 1;
        }
        return res;
    }

    function mat_eq(uint8[6][6] memory a, uint8[6][6] memory b) public pure returns (bool) {
        for (uint i = 0; i < 6; i++) {
            for (uint j = 0; j < 6 ; j++) {
                if (a[i][j] != b[i][j])
                    return false;
            }
        }
        return true;
    }

    function mat_add(uint8[6][6] memory a, uint8[6][6] memory b) public pure returns (uint8[6][6] memory) {
        for (uint i = 0; i < 6; i++)
            for (uint j = 0; j < 6 ; j++)
                a[i][j] ^= b[i][j];
        return a;
    }

    function mat_mul(uint8[6][6] memory a, uint8[6][6] memory b) public pure returns (uint8[6][6] memory) {
        uint8[6][6] memory result;
        for (uint i = 0; i < 6; i++)
            for (uint j = 0; j < 6; j++)
                for (uint p = 0; p < 6; p++)
                    result[i][j] ^= gal_mul(a[i][p], b[p][j]);
        return result;
    }
}

contract OtherChal {
    event Solved();
    using Rijndael for uint8;
    using Rijndael for uint8[6][6];

    function check(bytes calldata flag) public {
        require (flag.length == 36+6, "invalid flag");
        require (flag[0] == "f" && flag[1] == "l" && flag[2] == "a" && flag[3] == "g" && flag[4] == "{", "invalid flag");
        require (flag[flag.length - 1] == "}", "invalid flag");

        uint8[6][6] memory X;
        for (uint i = 0; i < 6; i++)
            for (uint j = 0; j < 6; j++)
                X[i][j] = uint8(flag[5+i*6+j]);

        uint8[6][6] memory yummy1 = [
            [0xbe, 0x9a, 0xc2, 0x24, 0x7f, 0x4d],
            [0x59, 0xde, 0x3b, 0x61, 0x0a, 0x1a],
            [0xc8, 0x18, 0x96, 0x0e, 0x94, 0x4d],
            [0xe3, 0x64, 0x8c, 0x6d, 0x76, 0xfe],
            [0x16, 0xd1, 0x41, 0x8e, 0x0e, 0x50],
            [0xe7, 0x42, 0xa4, 0x87, 0x8e, 0x6b]
        ];
        uint8[6][6] memory yummy2 = [
            [0x23, 0xab, 0x1e, 0x4c, 0xe9, 0xe],
            [0xef, 0x53, 0xb4, 0xac, 0x18, 0xb1],
            [0x3c, 0xc2, 0x2f, 0x34, 0x4a, 0x18],
            [0x65, 0x94, 0x67, 0xd3, 0x59, 0x29],
            [0xa0, 0x27, 0x4a, 0x73, 0xcd, 0x88],
            [0x5e, 0x32, 0x50, 0x20, 0x80, 0xe]
        ];

        uint8[6][6] memory yummy3 = [
            [98, 98, 45, 87, 130, 42],
            [200, 184, 107, 102, 139, 25],
            [73, 139, 58, 136, 217, 129],
            [219, 21, 107, 204, 18, 219],
            [145, 192, 17, 86, 166, 217],
            [40, 248, 43, 71, 93, 226]
        ];

        // Despite multiple applications, this is still affine
        // y1^6*X + (y1^5*y2 + y1^4*y2 + y1^3*y2 + y1^2*y2 + y1*y2 + y2)
        // Can crack it blackbox with side channel like gas
        X = yummy2.mat_mul(X).mat_add(yummy1);
        X = yummy2.mat_mul(X).mat_add(yummy1);
        X = yummy2.mat_mul(X).mat_add(yummy1);
        X = yummy2.mat_mul(X).mat_add(yummy1);
        X = yummy2.mat_mul(X).mat_add(yummy1);
        X = yummy2.mat_mul(X).mat_add(yummy1);

        // NOT a constant time comparison.
        require(X.mat_eq(yummy3), "invalid flag");

        emit Solved();
        payable(msg.sender).transfer(address(this).balance);
    }

    // I can receive money. But how to get it out?
    receive() external payable {}
}

solve.sage

import numpy as np

# helpers
def i2f(i):
	asdf = 1
	res = 0
	while i:
	    if i&1:
	       res += asdf
	    i >>= 1
	    asdf *= a
	return res
f2i = lambda f: f.integer_representation()
ii2ff = lambda ii: list(map(lambda r: list(map(i2f, r)), ii))
ff2ii = lambda ff: list(map(lambda r: list(map(f2i, r)), ff))
asc = lambda xx: np.asarray(ff2ii(xx)).astype(np.uint8).view('S3')

# field
k.<a> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
M = MatrixSpace(k,6,6)

# def chal related constants
yummy1 = M(ii2ff([
    [0xbe, 0x9a, 0xc2, 0x24, 0x7f, 0x4d],
    [0x59, 0xde, 0x3b, 0x61, 0x0a, 0x1a],
    [0xc8, 0x18, 0x96, 0x0e, 0x94, 0x4d],
    [0xe3, 0x64, 0x8c, 0x6d, 0x76, 0xfe],
    [0x16, 0xd1, 0x41, 0x8e, 0x0e, 0x50],
    [0xe7, 0x42, 0xa4, 0x87, 0x8e, 0x6b]
]))

yummy2 = M(ii2ff([
    [0x23, 0xab, 0x1e, 0x4c, 0xe9, 0xe],
    [0xef, 0x53, 0xb4, 0xac, 0x18, 0xb1],
    [0x3c, 0xc2, 0x2f, 0x34, 0x4a, 0x18],
    [0x65, 0x94, 0x67, 0xd3, 0x59, 0x29],
    [0xa0, 0x27, 0x4a, 0x73, 0xcd, 0x88],
    [0x5e, 0x32, 0x50, 0x20, 0x80, 0xe]
]))

yummy3 = M(ii2ff([
    [98, 98, 45, 87, 130, 42],
    [200, 184, 107, 102, 139, 25],
    [73, 139, 58, 136, 217, 129],
    [219, 21, 107, 204, 18, 219],
    [145, 192, 17, 86, 166, 217],
    [40, 248, 43, 71, 93, 226]
]))

iyummy2 = yummy2.inverse()

iround = lambda x: iyummy2 * (x - yummy1)
flag = iround(iround(iround(iround(iround(iround(yummy3))))))

print(b''.join(asc(flag).flatten()))