RC5 No Rotations

rc5_no_rotations.py

from math import ceil
from typing import *
from itertools import product, count
from collections import namedtuple
from random import randrange, seed
from tqdm import tqdm

seed(42)

ROTL = lambda x,y: (((x)<<(y&(w-1))) | ((x)>>(w-(y&(w-1)))))%(1<<w)

w = 16 # word size
r = 4 # number of rounds
b = 16 # len(key)
c = ceil(8*b/w) # number of words in key
u = w // 8 # number of bytes per word
t = 2*(r+1) # size of S[t]

# Key expansion
def gen_data(K):
    assert len(K) == b
    P,Q = 0xb7e1, 0x9e37
    c = ceil(max(b,1)/u)
    L = [0 for i in range(c)]
    for i in reversed(range(b)):
        L[i // u] = (L[i//u] << 8) + K[i]
    S = [P]
    for i in range(1, t):
        S.append((S[i-1]+Q) % (2 ** w))
    A = B = i = j = 0
    for k in range(3*max(t,c)):
        A = S[i] = ROTL((S[i] + A + B),3)
        B = L[j] = ROTL((L[j] + A + B),(A+B))
        i = (i+1) % t
        j = (j+1) % c
    return S

def enc_no_rotation(pt, S_):
    A,B = pt
    A = A+S_[0]
    B = B+S_[1]
    for i in range(1, r+1):
        A = A^B + S_[2*i]
        B = B^A + S_[2*i+1]
    return (A % (1<<w),B % (1<<w))

# Generate a list of equations
Equation = namedtuple("Equation", ["pt", "ct"])
S = gen_data(b"\x00" * 16)
equations = []
for i in range(200):
    pt = (randrange(2**w), randrange(2**w))
    ct = enc_no_rotation(pt, S_=S)
    equations.append(Equation(pt=pt, ct=ct))

def recover_subkeys(known_equations: List[Equation]):
    # Does encryption mod 2^k for some k < w
    def _encrypt_mod(pt: Tuple, S_: List[int], k: int) -> Tuple:
        A, B = pt
        A += S_[0]
        B += S_[1]
        for i in range(1, r+1):
            A = A^B + S_[2*i]
            B = B^A + S_[2*i+1]
        return (A % (1<<k), B % (1<<k))
    def _test_S(S_in: List[int], equations: List[Equation], nth_bit: int) -> bool:
        for equation in equations:
            pt = equation.pt
            ct_expected = _encrypt_mod(equation.pt, S_in, nth_bit)
            ct_actual = tuple(i % (1 << nth_bit) for i in equation.ct)
            if ct_expected != ct_actual:
                return False
        return True
    def _gen_S(Ss_in: List[List[int]], nth_bit: int) -> Generator[List[int], None, None]:
        for S_ in Ss_in:
            for bits in product([0,1], repeat = t):
                yield [n | (bit * (1 << nth_bit)) for n, bit in zip(S_, bits)]
    S_potentials = [[0]*t]
    for bit in range(w):
        # Generate potential values for subkeys
        S_potentials = _gen_S(S_potentials, bit)
        # Filter out the ones that don't satisfy the equations
        S_potentials = [S_ for S_ in tqdm(S_potentials) if _test_S(S_, known_equations, bit+1)]
        print(bit, len(S_potentials))
    return S_potentials

potential_subkeys = recover_subkeys(equations)

for S_ in potential_subkeys:
    assert all([enc_no_rotation(eq.pt, S_) == eq.ct for eq in equations])