6
$\begingroup$

Assuming that $m$ is a multiset of bitstrings where all bitstrings have the same length, let $D(m)$ denote the number of distinct elements in $m$. That is, $D(m)$ is equal to the dimension of $m$. For example, if $$m = \{00, 10, 11, 10, 11\},$$ then $D(m)=3$.

Let $F(x) = \text{Keccak-}f[1600](x)$, the block permutation function of SHA-3 (for $64$-bit words). We can define the following notation: $$\begin{array}{l} {F^0(x)} = x,\\ {F^1(x)} = F(x),\\ {F^2(x)} = F(F(x)),\\ {F^3(x)} = F(F(F(x))),\\ \ldots \end{array}$$

Assuming that $A$ and $B$ are two different natural numbers greater than or equal to $0$, let $G_{A, B}(x)$ denote a function defined as $$G_{A, B}(x) = F^A(x) \oplus F^B(x),$$

where $x$ denotes a $1600$-bit input and $\oplus$ denotes an XOR operation.

Assuming that $L = 2^{1600}$, let $S_i$ denote an $i$-th bitstring from a set of all possible $1600$-bit inputs:
$$\begin{array}{l} S_1 = 0^{1600},\\ S_2 = 0^{1599}1,\\ \ldots,\\ S_{L-1} = 1^{1599}0,\\ S_L = 1^{1600}.\\ \end{array}$$

Let $A$ and $B$ denote two arbitrarily large, but different natural numbers (one of them is allowed to be equal to $0$). For example, $$A = 0, B = 1$$ or $$A = 2^{3456789}, B = 9^{876543210}$$ are valid pairs.

Then

$$\begin{array}{l} S_{A, B}[i] = G_{A, B}(S_i),\\ C_{A, B} = \{S_{A, B}[1], S_{A, B}[2], \ldots, S_{A, B}[L-1], S_{A, B}[L]\}.\\ \end{array}$$

The question: can we assume that $D(C_{A, B})$ is expected to be approximately equal to $$(1-1/e) \times 2^{1600} = 10^{481} \times 2,810560755\ldots$$ for all (or almost all) pairs of $A$ and $B$?

$\endgroup$
  • 1
    $\begingroup$ $F$ is a permutation, so you can use $y = F(x)$ and simplify $G$ using $G'(y) = y \oplus F(y)$. Because $F$ is bijective, the number of possible $x$ is the same as the number of possible $y$. $\endgroup$ – Future Security Jun 14 '18 at 17:09
  • $\begingroup$ What does the notation Keccak-f[1600](x) mean? $\endgroup$ – kodlu Jun 15 '18 at 0:30
  • $\begingroup$ @FutureSecurity: Of course, $F(x)$ and $G(x)$ have equal number of possible inputs (they operate on 1600-bit blocks). Basically, we are xoring a 1600-bit block with another (almost independently pseudo-random) 1600-bit block. I think that this leads to $(1-1/e)\times 2^{1600}$ different 1600-bit blocks, so I am asking the question to verify this. $\endgroup$ – lyrically wicked Jun 15 '18 at 4:22
  • 2
    $\begingroup$ @kodlu: $\text{Keccak-}f[1600](x)$ is the underlying function of SHA-3. It transforms any 1600-bit input to a 1600-bit output. $\endgroup$ – lyrically wicked Jun 15 '18 at 4:25
  • $\begingroup$ Perhaps you should define it as $G_{A,B}(x)$, and then you are asking $|G_{A,B}(\cdot)|$, in other words, how many unique $G$ functions are there? $\endgroup$ – MotiN Aug 20 '18 at 9:59
1
$\begingroup$

Let $\pi$ and $\sigma$ be two independent uniform random permutations, and $f$ a uniform random function. The best advantage of any $q$-query algorithm to distinguish $\pi + \sigma$ from $f$ is bounded by $(q/2^n)^{1.5}$[1]. In this case, the expected fraction of distinct outputs of $\pi + \sigma$ can't be too far from the expected fraction of distinct outputs from $f$, which is $1 - e^{-1} \approx 63\%$.

What about $\sigma = \pi^2$, or $\sigma = \pi^k$ for $k > 2$? Then $\pi$ and $\sigma$ are not independent. Nevertheless, it would be rather surprising if this situation were substantially different.

What about $\pi^{2^{3456789}} + \pi^{2^{987654321}}$ instead of $\pi + \pi^2$? This is the same as $\pi + \pi^{2^{987654321 - 3456789}}$. It's not clear why you would be worried about uncomputably large exponents like this unless you were flailing around without principle trying to make a design that looks complicated.

$\endgroup$
  • 1
    $\begingroup$ $\pi \oplus \pi^2$ is what we called single-permutation EDMD. We conjectured it is about as indistinguishable as the two-permutation case, but much harder to show that is the case. The $\pi + \sigma$ case is expected to have slightly more collisions than a random function: $\pi(x) \oplus \sigma(x) = \pi(y) \oplus \sigma(y)$ implies $\pi(x) \oplus \pi(y) = \sigma(x) \oplus \sigma(y)$, neither side of which can be 0. But this does not move the needle in any significant way. $\endgroup$ – Samuel Neves 2 days ago
-1
$\begingroup$

Assumptions:

Let $F(x) = \text{Keccak-}f[1600](x)$ contain the entire state without truncation, and assume the upper bounds on both $A$ and $B$ is 21600.

And $x$ is a random 1600-bit Keccak input.

For the single function case, where you're passing $x$ into $F$($x$) and recursively calling the function n number of times, would require 21600 calls to $F$($x$) before there would be a repeated value.

For the dual function case where you $\oplus$ both function's outputs. There would be a fixed point where $A$ = $B$ resulting in $G$($x$) = $0$. To capture all combinations of $A$ and $B$ would require 23200 calls to $G$($x$). Since there will be 21600 instances where $A$ = $B$ , the total number different outputs should be 23200 - 21600. The issues is that 23200 - 21600 > 21600 which would violate maximum number of state values.

And things start to get strange:

There would be $0$ unique outputs in the entire set of values output by $G$($x$).

I'm going to sleep on this and return tomorrow as I've confused myself.

$\endgroup$
  • 1
    $\begingroup$ We are XORing the outputs of two almost independent permutations, so collisions are inevitable. Here is one simple example. Let $S$ denote Rijndael S-box. It defines a permutation over 8-bit inputs. Representing bytes as decimal numbers up to 255, we have $S[0] = 99$ and $S[99] = 251$. We observe that $99 \oplus 251 = 152$. Then $S[26] = 162$ and $S[162] = 58$. We observe that $162 \oplus 58 = 152$. Thus $S[0] \oplus S[S[0]] = S[26] \oplus S[S[26]] = 152$ (collision). $\endgroup$ – lyrically wicked Jun 16 '18 at 19:27
  • $\begingroup$ @lyricallywicked Yes the keccak sbox has fixed points, but iota prevents collisions $\endgroup$ – Q-Club Jun 16 '18 at 19:31
  • 2
    $\begingroup$ $F(x)$ is a fixed pseudo-random permutation (that has no collisions). But this question is about the function defined as $G(x) = F(x) \oplus F(F(x))$. $\endgroup$ – lyrically wicked Jun 16 '18 at 19:42
  • 1
    $\begingroup$ @lyricallywicked and I think 2^1600 is correct $\endgroup$ – Q-Club Jun 16 '18 at 20:02
  • 3
    $\begingroup$ Secondly, see the quote from this answer: "a random permutation has at least one fixed point with probability approximately $1 - 1/e \approx 0.6321$; assuming that $\text{Keccak-}f$ does, in fact, act like a random permutation, then it's more likely than not that there is such a fixed point." Then consider the possibility that there exist at least two fixed points, that is $F(x) = x$ and $F(y) = y$. Then $F(x) \oplus x = 0^{1600}$ and $F(y) \oplus y = 0^{1600}$, which is a collision. Thus the number of different outputs is less than $2^{1600}$. $\endgroup$ – lyrically wicked Jun 18 '18 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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