K3RN3LCTF 2021 - Total Encryption

pubkey_1 = {'e': 65537, 'nbit': 58, 'n': 195726826191354833}

pubkey_2 = {'e': 5, 'nbit': 1024, 'n': 147644180901082431168100755763554209140656121867352800930388594244396103618687665207495245297961709320402901550367810523324658918735482375563565444213406852148814309689694185359009235747549600651556682274722870284313750781375949649763784991789624132099041080448664730169011034436480887454107506927945601698107}

pubkey_3 = {'e': 127, 'nbit': 1470, 'n': 19245689335632446943762710195965658569430278438134217413263502921095274121678529390885316775906032947432051029798982324888526187325540039122096616131667142134701120897318593592934282056722729236708120776116667510638358541869631050311417708558092657167130040781658501061177345127748428272527278709216890098330854887219590276165180740630918902624682116819167776194862822329141878096956774085562315641976952391602707594555560645211968197019320867}

#!/usr/bin/env python3
#
# Polymero
#

# Imports
import os, time, base64
from Crypto.Util.number import getPrime, inverse, GCD, long_to_bytes

# Shorthand
def b64enc(x):
    return base64.urlsafe_b64encode(long_to_bytes(x)).rstrip(b'=')

class LTET:
    """ Layered Totally Encrypted Terminal. """
    def __init__(self, max_bit_length):
        self.maxlen = max_bit_length
        
        # Set bit lengths
        self.bitlen = {
            'inner block' : self.maxlen,
            'inner clock' : (7 * self.maxlen) // 125
        }
        self.bitlen['outer block'] = 16 + (4 * (self.bitlen['inner block'] + self.bitlen['inner clock'] + 9)) // 3
        self.bitlen['outer blind'] = 8 + (4 * self.bitlen['inner clock']) // 3
        
        # Key generation
        self.public  = { 'n' : [], 'e' : [65537, 5, 127]}
        self.private = { 'p' : [], 'q' : [], 'd' : []}
        for i in range(3):
            nbit = [self.bitlen[j] for j in ['inner clock', 'inner block', 'outer block']][i]
            while True:
                p, q = [getPrime((nbit + 1) // 2) for _ in range(2)]
                if GCD(self.public['e'][i], (p-1)*(q-1)) == 1:
                    d = inverse(self.public['e'][i], (p-1)*(q-1))
                    break
            self.private['p'] += [p]
            self.private['q'] += [q]
            self.private['d'] += [d]
            self.public['n']  += [p * q]
            
    def encrypt(self, msg):
        assert len(msg) * 8 <= self.maxlen
        clock = pow(int(time.time()), self.public['e'][0], self.public['n'][0])
        block = b64enc(pow(int.from_bytes(msg, 'big') ^ int(clock), self.public['e'][1], self.public['n'][1]))
        blind = int.from_bytes(os.urandom((self.bitlen['outer blind'] + 7) // 8), 'big') >> (8 - (self.bitlen['outer blind'] % 8))
        block = pow(int.from_bytes(block + b'.' + b64enc(clock) ,'big') ^ blind, self.public['e'][2], self.public['n'][2])
        return (b64enc(blind) + b'.' + b64enc(block)).decode()

#!/usr/bin/env sage
#
# Polymero
#

def PolyGCD(g1, g2):
    """ Straightforward GCD function for polynomials. """
    return g1.monic() if g2 == 0 else PolyGCD(g2, g1 % g2)

def FranklinReiter(C1, C2, DIF, e, n):
    """ Simple Franklin-Reiter related message attack to recover the plaintext from two encrypted messages with KNOWN linear difference. """
    P.<x> = PolynomialRing(Zmod(n))
    g1,g2 = [x**e - C1, (x + DIF)**e - C2]
    return -PolyGCD(g1, g2).coefficients()[0]

FLAG = b'flag{this is an example flag but what do I put here}'
bitlimit = 36

L2_IVS = []
L2_CIP = []

T0 = time.time()

while True:
    
    time.sleep(1)
    print('len(IVS) = {}'.format(len(L2_IVS)), end='\r', flush=True)

    CIPS = []
    IVS  = []
    PTS  = []

    try:
        
        # Gather two LTET encryptions of the same unique message
        for _ in range(2):

            stamp = b'.' + b64enc(pow(int(time.time()), ltet.public['e'][0], ltet.public['n'][0]))
            iv, cip = [i for i in ltet.encrypt(FLAG).split(b'.')]

            CIPS += [(stamp, int.from_bytes(base64.urlsafe_b64decode(cip+b'==='),'big'))]
            IVS  += [int.from_bytes(base64.urlsafe_b64decode(iv+b'==='),'big')]

            bytiv = base64.urlsafe_b64decode(iv+b'===')
            PTS  += [int.from_bytes(bytes([stamp[-len(bytiv):][i] ^^ bytiv[i] for i in range(len(bytiv))]), 'big')]

        # Make sure they containt the same timestamp (otherwise we cannot set up a correct linear relation)
        assert CIPS[0][0] == CIPS[1][0]
    
    except: continue

    # Commence Franklin-Reiter related message attack
    C1, C2 = [i[1] for i in CIPS]
    DIF = PTS[1] - PTS[0]

    rec_1 = FranklinReiter(C1, C2, DIF, ltet.public['e'][2], ltet.public['n'][2])

    if rec_1 == ltet.public['n'][2] - 1: continue

    else:

        # Recover inner layer
        recovered_layer = [int.from_bytes(base64.urlsafe_b64decode(i+b'==='),'big') for i in long_to_bytes(int(rec_1) ^^ int(IVS[0])).split(b'.')]
        
        # Do we have small enough padding to be able to apply a short-pad attack?
        reslst = [(i>>bitlimit) == (recovered_layer[1]>>bitlimit) for i in L2_IVS]

        if any(reslst):

            # If found, break
            iv1 = recovered_layer[1]
            iv2 = L2_IVS[reslst.index(True)]
            c1  = recovered_layer[0]
            c2  = L2_CIP[reslst.index(True)]
            break

        else:

            # Else, keep going
            L2_CIP += [recovered_layer[0]]
            L2_IVS += [recovered_layer[1]]
    
# Set up for Coppersmith short-pad attack        
N = ltet.public['n'][1]
G.<x,y> = PolynomialRing(Zmod(N))

# Ciphertext polynomials
g1 = x^ltet.public['e'][1] - c1
g2 = (x + y)^ltet.public['e'][1] - c2

# Sage needs univariate polynomial rings, sigh...
F.<y> = PolynomialRing(Zmod(N))
g1 = g1.change_ring(F)
g2 = g2.change_ring(F)

f = g1.resultant(g2, x)
f = f.univariate_polynomial().change_ring(Zmod(N))

ivbits = ltet.bitlen['inner clock']
print('\niv1 = {:0{x}b}'.format(iv1, x=ivbits))
print('iv2 = {:0{x}b}'.format(iv2, x=ivbits))

print('\nTrying to find a root...', end='\r', flush=True)

try:

    # Try to find a root below the set bitlimit (acts as time constraint)
    root = f.small_roots(epsilon=1/200, X=2**bitlimit)[0]
    print('Found min root :', min(root, -root % N))

except:

    print('Nope :C' + ' '*32)
    
T1 = time.time()

print('It took me {} seconds :)'.format(int(T1-T0)))

# Print original message!
print(long_to_bytes( int(FranklinReiter(c1,c2,min(root, -root % N)),ltet.public['e'][1],N)) ^^ iv1 )