Reversing decryption function involving XORs and bit rotations?

Question

I am trying to reverse this equation to find the encrypted number given to it. Here is the equation:

$$y = x \oplus n \oplus (x \ggg 3) \oplus (x \lll 7) $$

$\oplus$ is the bitwise exclusive or function
$a \lll b$ is $a$ bit rotated left by $b$ bits
$a \ggg b$ is $a$ bit rotated right by $b$ bits

$y$ is a known 32 bit integer
$n$ is a known 32 bit integer but unique for every $x$ and $y$
$x$ is the encrypted message and what I want to solve for, and it is an unknown 32 bit integer

You can trivially eliminate $n$. After that you have 32 linear equations modulo 2 and 32 unknowns. Apply standard techniques for solving a system of linear equations, or if you're lazy brute-force it (should only take a couple of seconds). — CodesInChaos, Jul 01 '17 at 12:31
Related: How to break an arbitrary XOR and Rotation based encryption? — CodesInChaos, Jul 01 '17 at 12:32
"$n$ is a known 32 bit integer but unique for every $x$ and $y$"; is $n$ a function of $x$, $y$, or both? If the latter, the system is under determined afaict. — Ruben De Smet, Jul 01 '17 at 17:14
Ok, then my answer should be alright. Give me a ping (or file an edit) if I misdid my indices... — Ruben De Smet, Jul 01 '17 at 18:08

score 6 · Answer 1 · edited Jul 01 '17 at 22:13

I'll demonstrate a "brute" way of doing it; should work for any XOR-rot system. Please note that indices are $\bmod 32$.

You basically write your equation in 32-vector and matrix notation:

$$ \bar{y} = M\bar{x} \oplus \bar{n}, $$ or in Einstein notation (which, in my opinion, can make stuff more readable) $$ y_i=M_{ij}x^j \oplus n_i, $$ where the sum goes from $i=1\dots32$.

Now, the magic part (to solve the rotation) lies in finding the $32\times32$ matrix $M_{ij}$:

$$ M_{ij}=\delta_{ij}\oplus\delta_{(i+3),j}\oplus\delta_{(i-7),j}, $$ where $\delta_{ij}$ is the Kronecker delta symbol (the unit matrix):

$$ \delta_{ij} = \begin{cases} 1, & \text{if } i=j,\\ 0, & \text{if } i\neq j. \end{cases} $$ Now your problem is reduced to inverting $M_{ij}$ (which is a one-time static thing), and calculating

$$ \bar{x}=M^{-1}(\bar{y}+\bar{n}) $$

I added a link about the Einstein summation convention as well as an inline definition of the Kronecker delta. Hope you don't mind! Also, \bmod is better with the spacing when you type \mod 32. — , Jul 01 '17 at 22:18

Reversing decryption function involving XORs and bit rotations?

1 Answers1