4
votes
$\begingroup$

All sub-functions are referenced with respect to Keccak. It’s my understanding that the sub-function theta() would result in the largest resource allocation when attempting to invert Keccak. If this is incorrect please edit, comment, or answer. But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion. This question is asking specifically the estimated inversion time of theta^-1(o,n), when the inverting function is provided with some random output (o), and the number (n) of recursive iterations of theta(i,n) used to generate the output. Where theta(i,n) is initially seeded with what I will assume is some uniformly random 1600 bit input (i), and the number (n) of recursive iterations. See pseudo code provided.

def test_0(n):
    i=set_main_build(64,25)
    a_copy=list(i)
    for index in range(n):
        i=theta(i)
    o=list(i)
    return(o,'break',a_copy)

Now my serious curiosity is if someone can manage to execute theta^-1(o,n) where n > 10^6. But I fear finding theta^-1() in the wild is hard enough, but at last if someone has built a faster implementation I would most certainly like to see it. I'm trying to learn C, but even with the speed improvements over python I still think handling 5-bit pieces of information might prove to be be difficult in that language. If that is an incorrect statement please elaborate!

Use this script. Modify a single bit in ip (line 949-977)...then F5...it currently takes 2.1027 hours. I'll award the bounty to anyone silly enough to attempt this, and who posts their inversion.

$\endgroup$
3
  • $\begingroup$ You may need to indicate what you are missing from the existing answers. $\endgroup$
    – Maarten Bodewes
    Mar 4, 2018 at 17:41
  • $\begingroup$ @MaartenBodewes As the bounty states I want the actual calculation time. If it can't be provided I'll assume the code is not functional $\endgroup$
    – Q-Club
    Mar 4, 2018 at 19:20
  • $\begingroup$ I've put it on hold as it rendered itself into a coding question (which is underlined by the fact OP fishes for the used scripts via comments, and answers tend to contain code too). Also, the timing OP asks for is a rather problematic question for a Q&A site like CryptoSE, as OP does not assume a specific system. That renders thing into a too broad (read: endless) question where answers end up providing individual benchmark results… again, obviously with related code. $\endgroup$
    – e-sushi
    Mar 10, 2018 at 0:52

1 Answer 1

15
votes
$\begingroup$

But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion.

That is incorrect as you don't need a time limit to compute $\theta^{-1}$.

You are not using the correct representation. As follows are some intuitions of how to efficiently invert $\theta$.

I. Quick Reminder of $\theta$

II. Inverting the $\theta$-effect

Instead of seeing the parity $\mathscr{P}$ of the state $S$ as $5 \times w$ bit-array. You can see it as a $5w$-bit vector $W$. i.e. you have a unique mapping $\sigma$ between $x,z$ and $i^{th}$ the coordinate in that $5w$-bit vector $W$ : $i = x \times w + z$. $$\varphi(\mathscr{P}) = W$$

The $\theta$-effect can be seen as the result of a matrix multiplication: $$W' = W \cdot T$$ which gives us: $$E = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi$$ and the inverse: $$E^{-1} = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi$$ Note: this assumes that $T^{-1}$ exists.

Proof: \begin{array}{rl} E^{-1} \circ E &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi \circ \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi\\ &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ (\lambda x \mapsto x\cdot T) \circ \varphi\\ &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T \cdot T^{-1}) \circ \varphi\\ &= \varphi^{-1}\circ (\lambda x \mapsto x) \circ \varphi\\ &= \varphi^{-1}\circ \varphi\\ &= id \end{array}

As an example as follow is computed $T$ for $w = 4$:

i =  0 : 0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1
i =  1 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0
i =  2 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0
i =  3 : 0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0

i =  4 : 0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0
i =  5 : 1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0
i =  6 : 0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0
i =  7 : 0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0

i =  8 : 0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0
i =  9 : 0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 10 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0
i = 11 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0

i = 12 : 0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0
i = 13 : 0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0
i = 14 : 0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0
i = 15 : 0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1

i = 16 : 1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0
i = 17 : 0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0
i = 18 : 0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 19 : 0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0

If we take point at coordinates $(x = 0, z = 3)$ or $i = 0\times 4 + 3 = 3$ (thus the fourth column).

The $\theta$-effect gives us:

$(x-1, z) + (x+1,z+1) = (4,3) + (1,0)$ as we are with $w = 4$.

In other words we need:

$i = 4 \times 4 + 3 = 19$ and $i = 1 \times 4 + 0 = 4$.

You can check that these coordinates are set in the $4^{th}$ column.

Fun fact, $T$ is not invertible.

For $T$ to be invertible, the determinant should not be null. Using sage we notice that $det(T) = 0$, proving that $T$ is not invertible.

III. Going back to $\theta$

Sadly inverting the (non-invertible) $\theta$-effect does not gives us the inverse of $\theta$ as it is added back to the state. However we can notice multiple things.

   +---+       +---+
  /   /|      /   /|
 /   / +     /   / +
+---+ /     +---+ /
| S |/ ---> | S'|/
+---+       +---+
  |           ^
  v           |
  P  ------> E(P)

Notice that:

  • $\bigoplus_{y=0}^4 S[x,y,z] = \mathscr{P}$
  • $\bigoplus_{y=0}^4 S'[x,y,z] = \mathscr{P} + 5 \times E(\mathscr{P}) = P + E(\mathscr{P})$

In the same way as in [II], $P + E(\mathscr{P})$ can be seen as a matrix transformation (i.e. a multiplication by $(id + T)$).

Thus if we inverse this $(id + T)$ matrix, we will be able to find the initial parity $\mathscr{P}$ of the state, compute the $\theta$-effect and add it back to $S'$, canceling the itself ($\forall s, s \oplus \theta\text{-effect} \oplus \theta\text {-effect} = s$). And in such way, computing the inverse of $\theta$.

   +---+                              +---+
  /   /|                             /   /|
 /   / +                            /   / +
+---+ /        theta^-1            +---+ /
| S'|/ --------------------------> | S |/
+---+                              +---+
  |                                  ^
  v                                  |
P + E(P) ---------------> P ----- > E(P)
          *(id + T)^-1        *T

Going back to our $w= 4$ example we have:

id + T =
[1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1]

Which happens to be invertible:

(id+T)^-1=
[1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1]

Because of the associativity of the matrix group. You can just compute: $(id + T)^{-1} \cdot T$ giving you a slightly faster computation of the $\theta$-effect from $S'$ (as opposed to do the 2 matrix multiplications):

(id + T)^-1 * T =
[0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0]
$\endgroup$
13
  • $\begingroup$ Allright @Biv! For my education: In part II. you prove why the theta effect can't be inverted? (You state that very clearly in part III., No?) Also will you elaborate on what you mean when you say sum_on_col(S/S`)? And $\endgroup$
    – Q-Club
    Nov 7, 2017 at 2:28
  • $\begingroup$ @back_seat_driver the theta-effect (which is the part that is added back to the state !) can be seen as a matrix multiplication. This matrix has a null determinant, thus by linear algebra is non-invertible. $\endgroup$
    – Biv
    Nov 7, 2017 at 11:31
  • $\begingroup$ @back_seat_driver as for the sum_on_col, I edited to make it a bit more clear, using the xor formula provided in the first picture. $\endgroup$
    – Biv
    Nov 7, 2017 at 11:31
  • $\begingroup$ Where S' is XOR of S?, and if you wrap theta twice would you agree on 320 or 160? Neither? $\endgroup$
    – Q-Club
    Nov 8, 2017 at 3:47
  • $\begingroup$ @back_seat_driver in don't understand your question. Where does that 160 or 320 come from?? $\endgroup$
    – Biv
    Nov 8, 2017 at 8:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.