2001-04-24

Steak – Inverse of Decryption algorithm

Notation:
[<index>] denotes index of a vector. A reference to a vector without index is a typecast to an integer variable.
[<row>,<col>] denotes index of a two dimensional matrix.
xor denotes bitwise xor.
ror denotes bitwise rotation right.
** denotes "to the power of".
+ denotes addition modulo 2**32
- denotes subtraction modulo 2**32
/ denotes integer division
* denotes integer multiplication
:= denotes assignment
= denotes integer identity comparison, returns Boolean
DWORD a 4-vector of bytes.

Purpose:
The n-vector V_k is calculated given V_k+1, a plain text byte P_k and a 32-bit value guess.

INPUT:
One byte of plain text P_k, a 4x256-matrix D of DWORDs, an n-vector A of DWORDs, an n-vector V_k+1 of DWORDs, a DWORD Guess.

OUTPUT:
A Boolean variable Success, an n-vector V_k of DWORDs.

VARIABLES:
An integer I, a DWORD B, a DWORD PV, a DWORD E, a byte F, an n-vector V of DWORDS.  

--- Feedback process:
   (1) C_k := V_k+1[n][3]
   (2) F := P_k xor C_k
   (3) V := (256*V_k+1 + ((Guess+ F) mod 256)) mod 2^32*n
--- End of Feedback process    (4) PV := Guess
   (5) For I := n downto 2 do
--- Main function:
   (5.1)   B := A[I] + PV
   (5.2)   E := D[0,B[0]] xor D[1,B[1]] xor D[2,B[2]] xor D[3,B[3]]
   (5.3)   PV := V[I]
   (5.4)   V_k[I] := (PV ror 4) – E
--- End of Main function
--- Main function, last round
   (6) B := A[1] + PV
   (7) E := D[0,B[0]] xor D[1,B[1]] xor D[2,B[2]] xor D[3,B[3]]
   (8) Success := (Guess = (V[1] - E))
   (9) V_k[1] := Guess
--- End of Main function last round

Remark 1 (The value of V[1]):
At step (3) the least significant byte of V is set to ((Guess + F) mod 256). Note that the value of the second least significant byte of V is equal to the least significant byte of V_k+1 and does not depend on whether or not there is a carry from the addition (Guess[0] + F). The comparison at step (8) yields True only if (E[0] = F), as it should given step (5) of the encryption algorithm.

Remark 2 (Guess):
Eliminating Guess would be an achievement. D is invertible so steps (5)-(5.4) could be reversed, but it would not suffice. We would simply have to enter Guess at the equivalent of step (8) instead of at the present step (4).