BlackHat MEA CTF Quals 2022 | nothing up my sbox

#!/usr/local/bin/python
#
# Polymero
#

# Imports
import os, time
from secrets import randbelow
from hashlib import sha256

# Local imports
FLAG = os.environ.get('FLAG').encode()


class NUMSBOX:
    def __init__(self, seed, key):
        self.sbox = self.gen_box('SBOX :: ' + seed)
        self.pbox = self.gen_box(str(time.time()))
        self.key = key

    def gen_box(self, seed):
        box = []
        i = 0
        while len(box) < 16:
            i += 1
            h = sha256(seed.encode() + i.to_bytes(2, 'big')).hexdigest()
            for j in h:
                b = int(j, 16)
                if b not in box:
                    box += [b]
        return box
    
    def subs(self, x):
        return [self.sbox[i] for i in x]
    
    def perm(self, x):
        return [x[i] for i in self.pbox]
    
    def kxor(self, x, k):
        return [i ^ j for i,j in zip(x, k)]
    
    def encrypt(self, msg):
        if len(msg) % 16:
            msg += (16 - (len(msg) % 16)) * [16 - (len(msg) % 16)]
        blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]
        cip = []
        for b in blocks:
            x = self.kxor(b, self.key)
            for _ in range(4):
                x = self.subs(x)
                x = self.perm(x)
                x = self.kxor(x, self.key)
            cip += x
        return ''.join([hex(i)[2:] for i in cip])
    
    
KEY = [randbelow(16) for _ in range(16)]

OTP = b""
while len(OTP) < len(FLAG):
    OTP += sha256(b" :: ".join([b"OTP", str(KEY).encode(), len(OTP).to_bytes(2, 'big')])).digest()
    
encflag = bytes([i ^ j for i,j in zip(FLAG, OTP)]).hex()

print("|\n|  ~ In order to prove that I have nothing up my sleeve, I let you decide on the sbox!")
print("|    I am so confident, I will even stake my flag on it ::")
print("|    flag = {}".format(encflag))

print("|\n|  ~ Now, player, what should I call you?")
seed = input("|\n|  > ")

oracle = NUMSBOX(seed, KEY)

print("|\n|  ~ Well {}, here are your s- and p-box ::".format(seed))
print("|    s-box = {}".format(oracle.sbox))
print("|    p-box = {}".format(oracle.pbox))


MENU = """|
|  ~ Menu ::
|    [E]ncrypt
|    [Q]uit
|"""

while True:

    try:

        print(MENU)
        choice = input("|  > ")

        if choice.lower() == 'e':
            msg = [int(i, 16) for i in input("|\n|  > (hex) ")]
            print("|\n|  ~ {}".format(oracle.encrypt(msg)))

        elif choice.lower() == 'q':
            print("|\n|  ~ Sweeping the boxes back up my sleeve...\n|")
            break

        else:
            print("|\n|  ~ Sorry I do not know what you mean...")

    except KeyboardInterrupt:
        print("\n|  ~ Sweeping the boxes back up my sleeve...\n|")
        break

    except:
        print("|\n|  ~ Hey, be nice to my code, okay?")

sboxの問題

全探索で線形なS-Boxを求める方法

#include <omp.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>


#include <openssl/sha.h>
std::array<char,16> build(char* seed)
{
    bool seen[16] {};
    std::array<char,16> ret {};
    int p = 0;
    int i = 0;
    while(true)
    {
        i += 1;
        char buf[32]; memcpy(buf,seed,30);
        *(uint16_t*)(buf+30) = __builtin_bswap16(i);
        unsigned char hash[SHA256_DIGEST_LENGTH];
        SHA256_CTX sha256;
        SHA256_Init(&sha256);
        SHA256_Update(&sha256, buf, 32);
        SHA256_Final(hash, &sha256);
        for(uint8_t c0 : hash)
        {
            int cs[2] { c0 / 16, c0 % 16 };
            for(uint8_t c : cs)
            {
                if(seen[c]) continue;
                seen[c] = true;
                ret[p++] = c;
                if(p == 16) return ret;
            }
        }
    }
}
bool is_lin(const std::array<char,16>& vec)
{
    bool bad = false;
    for(int x = 0; x < 16; x++)
    {
        for(int i = 0; i < 16; i++)
        {
            if((vec[i] ^ vec[i^x]) != (vec[0] ^ vec[x]))
                bad = true;
        }
    }
    return !bad;
}

int main()
{
#pragma omp parallel
    {
        //        01234567
        char buf[32] = "SBOX :: ";
        std::mt19937 mt(omp_get_thread_num());
#pragma omp for
        for(int j = 0; j < 1000000000; j++)
        {
            for(int i = 8; i < 30; i++) buf[i] = mt() % 26 + 'a';
            buf[30] = buf[31] = 0;
            auto s = build(buf);
            bool lin = is_lin(s);
            //printf("%s\n", buf);
            //for(char c : s) printf("%d ", c); printf("\n");
            if(lin)
            {
                printf("j=%d: %s\n", j, buf);
            }
        }
    }
}

Z3

from z3 import *
from hashlib import sha256

FLAG = bytes.fromhex('0115f4505a2d7fa3178a5e77262665e6d4d3efc8d477320f9c1a292fbfc39af3f3558145fe15946d4c1b4a00f8316dc19bb54babecd94def374a3b1a')
# send any name
sbox = [1, 7, 0, 6, 3, 5, 2, 4, 15, 14, 12, 9, 13, 11, 8, 10]
pbox = [6, 1, 11, 14, 2, 4, 7, 9, 8, 0, 10, 13, 12, 15, 5, 3]
# send '00000000000000001111111111111111'
data = '2f6127b46d968ad01e3466903a81bfc5'

key = [BitVec(f'k{i}', 4) for i in range(16)]
z3sbox = Array('sbox', BitVecSort(4), BitVecSort(4))

def encrypt(x):
    x = [i^k for i,k in zip(x,key)]
    for _ in range(4):
        x = [Select(z3sbox,i) for i in x] # sub
        x = [x[i] for i in pbox]
        x = [i^k for i,k in zip(x,key)]
    return x

s = Solver()
s.add([Select(z3sbox, i) == n for i, n in enumerate(sbox)])
s.add([e==int(c,16) for e,c in zip(encrypt([0]*16), data[:16])])
s.add([e==int(c,16) for e,c in zip(encrypt([1]*16), data[16:])])
assert s.check() == sat
KEY = [s.model()[k].as_long() for k in key]
print(f'{KEY=}')

OTP = b""
while len(OTP) < len(FLAG):
    OTP += sha256(b" :: ".join([b"OTP", str(KEY).encode(), len(OTP).to_bytes(2, 'big')])).digest()
print(bytes(o^f for o,f in zip(OTP, FLAG)))