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$

closed as off-topic by e-sushi Mar 10 '18 at 0:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm, protocol or side-channel (mitigation) works, you should look into asking on Stack Overflow instead." – e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

locked by e-sushi Apr 22 '18 at 10:59

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

Read more about locked posts here.

  • $\begingroup$ You may need to indicate what you are missing from the existing answers. $\endgroup$ – Maarten Bodewes Mar 4 '18 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 '18 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 '18 at 0:52
-1
votes
+200
$\begingroup$

As requested:

Time: 7314.2699134 seconds

_answer=['0111100111100101100011111111100010100010110110011011110110100001',
       '0110000001000100110010111100111010111100001010000001001111111011',
       '1010001000110111000000000110001011101100111011111100100100111100',
       '0001101001100010001110010001110001111100010110000010110000000010',
       '1001101111010001111110001001000001111101001111110000011110001000',
       '0011011000000010011100001001010101001010011001110011110001111010',
       '1011100101100111010001110111101010010001100010001100011110100110',
       '0101110010011010110010001100011100110011001011100000010001100100',
       '0001001100000110101111001000101001110000100110110010011001011010',
       '1011100001111110000001110000111100111100011110010000000100111011',
       '1111101000011001011100001100000000010100100111110001011101011111',
       '1101010110100100001101010100100100101000111000110111010011011001',
       '1100101101110110100110000111111010010001110100100100011000000111',
       '1011101011100010010010110101010010100101111000110100100011001011',
       '0010101011101111110111000101110110011111001011111011100110011111',
       '0011010111110010010110110010100110010100000111100010101110100011',
       '1111110001100001010101001110001100011010100111001000000110101111',
       '1111001111111101010100100010000001001011010011111110000011000110',
       '1100100101101111000000001000010000110101101111111111011110000010',
       '1110101111101011010111000111111010011111001111100111100000000011',
       '0110010011111010101000001110101101101001110101101111100011110101',
       '0110111001110100111101100000111000001010011110000100010001001101',
       '0111011111000000100100011101011010100001110100111101000111011011',
       '0011101011011111110111011111011101110011110100011100010011110000',
       '1011111000011010100101100110110011100000110100111110100000111100']
$\endgroup$
  • $\begingroup$ Would you consider posting the script that performed the benchmark? $\endgroup$ – DannyNiu Mar 8 '18 at 3:21
  • $\begingroup$ @DannyNiu The requested script $\endgroup$ – user55634 Mar 8 '18 at 3:31
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$
  • $\begingroup$ Wow, did you use the entire 13 hours between question and answer to come up with that? $\endgroup$ – Maarten Bodewes Nov 6 '17 at 15:06
  • $\begingroup$ @MaartenBodewes Nope. I just saw the question this morning. It took me something like 2 hours to write the thing (sage helped for the inversion). $\endgroup$ – Biv Nov 6 '17 at 15:27
  • 7
    $\begingroup$ @MaartenBodewes: What you should realize by now is that Biv eats sponges for breakfast, sometimes with sage seasoning. $\endgroup$ – Squeamish Ossifrage Nov 6 '17 at 15:34
  • $\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 '17 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 '17 at 11:31
1
vote
$\begingroup$

Keccak is in fact fully invertible.

https://github.com/gvanas/KeccakTools/blob/master/Sources/main.cpp

keccakF.inverse(state)

You can probably figure out how they do it from there.

Edit: Inversion here: https://github.com/gvanas/KeccakTools/blob/master/Sources/Keccak-f.h

void KeccakF::inverse(vector<Lane>& state) const
{
    for(int i=startRoundIndex+nrRounds-1; i>=startRoundIndex; i--)
        inverseRound(state, i);
}

void KeccakF::inverseRound(vector<Lane>& state, int roundIndex) const
{
    iota(state, roundIndex);
    inverseChi(state);
    inversePi(state);
    inverseRho(state);
    inverseTheta(state);
}

void KeccakF::inverseChi(vector<Lane>& A) const
{
    for(unsigned int y=0; y<5; y++) {
        unsigned int length = 5;
        vector<Lane> C(length);
        for(unsigned int x=0; x<length; x++) C[index(x)] = A[index(x,y)];
        for(unsigned int x=0; x<(3*(length-1)/2); x++) {
            unsigned int X = (length-2)*x;
            A[index(X,y)] = C[index(X)] ^ (A[index(X+2,y)] & (~C[index(X+1)]));
        }
    }
}

void KeccakF::inverseTheta(vector<Lane>& A) const
{
    vector<Lane> C(5);
    for(unsigned int x=0; x<5; x++) {
        C[x] = A[index(x,0)];
        for(unsigned int y=1; y<5; y++){
            C[x] ^= A[index(x,y)];
        }
    }
    const LaneValue inversePositions64[5] = {
        0xDE26BC4D789AF134ULL,
        0x09AF135E26BC4D78ULL,
        0xEBC4D789AF135E26ULL,
        0x7135E26BC4D789AFULL,
        0xCD789AF135E26BC4ULL };
    vector<LaneValue> inversePositions(5, 0);
    for(unsigned int z=0; z<64; z+=laneSize)
        for(unsigned int x=0; x<5; x++)
            inversePositions[x] ^= inversePositions64[x] >> z;
    for(unsigned int z=0; z<laneSize; z++) {
        for(unsigned int xOff=0; xOff<5; xOff++)
           for(int x=0; x<5; x++)
               for(unsigned int y=0; y<5; y++)
                   if ((inversePositions[xOff] & 1) != 0)
                      A[index(x, y)] ^= C[index(x-xOff)];
        for(unsigned int xOff=0; xOff<5; xOff++) {
            ROL(C[xOff], 1);
            inversePositions[xOff] >>= 1;
        }
    }
}

void KeccakF::inversePi(vector<Lane>& A) const
{
    vector<Lane> a(A);
    for(unsigned int X=0; X<5; X++)
    for(unsigned int Y=0; Y<5; Y++) {
        unsigned int x, y;
        inversePi(X, Y, x, y);
        A[index(x,y)] = a[index(X,Y)];
    }
}

void KeccakF::inverseRho(vector<Lane>& A) const
{
    for(unsigned int x=0; x<5; x++)
    for(unsigned int y=0; y<5; y++)
        ROL(A[index(x,y)], -rhoOffsets[index(x,y)]);
}

void KeccakF::iota(vector<Lane>& A, int roundIndex) const
{
    unsigned int ir = (unsigned int)(((roundIndex % 255) + 255) % 255);
    A[index(0,0)] ^= roundConstants[ir];
}
$\endgroup$
  • $\begingroup$ The code is interesting but can you explain to me why there are constants in the theta inversion? $\endgroup$ – Q-Club Dec 24 '17 at 18:14
  • $\begingroup$ I do not know. The Keccak team wrote it. This repo is what they were using and still are to analyze their creation. I expect it's the simplification of some cumbersome inversion. $\endgroup$ – user10653 Dec 24 '17 at 19:30
  • $\begingroup$ Thanks for the code, I'll be reaching out to the designers. $\endgroup$ – Q-Club Dec 24 '17 at 19:54
  • $\begingroup$ It looks like there are brackets missing on some of the nested for loops. I don't write in C/C++ but this might not compile. $\endgroup$ – Q-Club Jan 29 '18 at 18:58
  • 2
    $\begingroup$ @Q-Club this is not a question one can answer. Run time means nothing , especially for un-optimized C code. Number of cycles is a better measure for what you want. But again this is not compiled so it is difficult to evaluate. This is why we talk in term of complexity and number of operations to compare speed. $\endgroup$ – Biv Mar 4 '18 at 10:49

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