Skip to content

Instantly share code, notes, and snippets.

@epistemologist
Created April 18, 2023 03:29
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save epistemologist/b2e3bc95c4489a8fe747f90fbdfbfd8c to your computer and use it in GitHub Desktop.
RC5 No Rotations
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])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment