0
$\begingroup$

There was a recent question answered where the accepted solution was a double Pearson hash. It consisted of the following pseudo code:- h = T1[h ^ x[i]] followed immediately by h = T2[h ^ x[i]] so effectively you run one lookup table into the other. Tables T1 and T2 are unique random 8 bit permutations. Output collisions can occur at the classic $ 1 \over e $ rate given the presence of the 2nd table, with the hash behaving as a pseudo random function.

Developing this construction further, assume that the permutation tables are $ \pi $, giving a more general form for hashing a message $m$ with multiple consecutive but unique permutations:-

$$ h_{i} = \pi_j [h_{i-1} \oplus m[i]]; recursive $$

creating a functional composite as in:-

$$ h = \pi_3[(\pi_2[(\pi_1 [h \oplus m[i]]) \oplus m[i])]) \oplus m[i]] $$

if $j=3$ . And let's call each calculation of $h$ for any given $\pi$ a 'step'. Overall, we get $ output = H_N(m) $ for this cool/weird hash consisting of $N$ tables/steps. As an example, it might be that $ H_3(3512)=110 $ for a hash with 3 permutation tables. In the linked question we used 2 tables.

  1. Can a new $\pi$ or set of $\pi$s be constructed to arrive at an identical output for all messages with $<N$ steps? In other words can multiple $\pi$ permutations be reduced or merged somehow into new ones, even theoretically? Clearly they can in the special and trivial case of $|m| = 1$. What about generally for $|m| > 1$?
  2. Considering the trivial case mentioned above, is there some relationship between $N$ and $|m|$ that determines the answer?
  3. If a reduced set of new $\pi$s might theoretically exist, how might it found in practice?

Notes:

  1. Some of this question is clearly on topic here, but not sure about it's entirely.

  2. I see small parallels with permutations and non linearity, construction of S boxes, and their combinations.

  3. Whilst hallucinating one might assume values of $\pi_j$ be likened to multiple keys $k_j$, so the answer to Security of a block cipher if double encryption $E_{K_2} \circ E_{K_1}$ is always single encryption $E_{f(K_1,K_2)}$ comes to mind as there is an attempt at a similar(?) reduction.

  4. I'm happy to be migrated outa here.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Claim: A $\pi$ permutation table can be found such that applying it to a message $m$ will yield the same output as applying multiple, different permutations to that message $m$.

i.e. For any number of permutation steps $\phi_n$, $m_{initial}\rightarrow\phi_1\rightarrow\phi_2\rightarrow...\rightarrow\phi_n\rightarrow m_{permuted}$

$\exists$ a single permutation $\pi$ such that: $m_{initial}\rightarrow\pi\rightarrow m_{permuted}$

Where both $m_{permuted}$'s are identical.

Proof:

Assume we have two permutation tables, $\phi_1$ and $\phi_2$ s.t.

$\phi_1= \begin{bmatrix} m_{1} & m_{2} & m_{3} & m_{4} \\ a & b & c & d \end{bmatrix} $ $\phi_2= \begin{bmatrix} m_{1\phi_1} & m_{2\phi_1} & m_{3\phi_1} & m_{4\phi_1} \\ e & f & g & h \end{bmatrix} $

Where the first row contains the input broken into bits and the second row contains the positions that each bit will be mapped to. (For $\phi_2$ notice that each bit of $m$ is now $m_{0\phi_1}$, indicating that it is the first bit of the message after being permuted by $\phi_1$). For example:

$ m=3512 $

\begin{bmatrix} 3 & 5 & 1 & 2 \\ 4 & 2 & 3 & 1 \end{bmatrix}

yields a $m_{permuted}=2513$, and then this new permuted message can be permuted again (as many times as desired).

Right, so back to our earlier example using $m$, $\phi$, and $a,b,c,...$.

Going through the first permutation, we will have the message $m_{\phi_1}=m_{a}m_{b}m_{c}m_{d}$

Going through the second permutation, we will have the message $m_{\phi_2}=m_em_fm_gm_h$

So, it is sufficient to find a permutation matrix that directly maps $m_1,m_2$ etc. to the locations that $m_1,m_2,...$ end up in the final permutation matrix. Finding such a permutation matrix is quite simple, as you can pass a message $m$ through the multiple permutations $\phi_n$, observe where they end up, and create the mapping based on that. This is best illustrated by and example, but proof by example is not acceptable, so I added the other info in before this. Also note that this works for any size of $m$ assuming the permutation has mappings that include all bits in $m$ (So each bit gets assigned a new place).

Example:

$m=m_1m_2m_3m_4$

$\rightarrow$$\phi_1= \begin{bmatrix} m_{1} & m_{2} & m_{3} & m_{4} \\ 3 & 2 & 4 & 1 \end{bmatrix} $$\rightarrow m_{\phi_1}=m_3m_2m_4m_1$

$\rightarrow$$\phi_2= \begin{bmatrix} m_{3} & m_{2} & m_{4} & m_{1} \\ 4 & 2 & 3 & 1 \end{bmatrix} $$\rightarrow m_{\phi_2}=m_1m_2m_4m_3$

$\therefore$ It is sufficient to have a permutation table to complete the mapping $m_1m_2m_3m_4 \rightarrow m_1m_2m_4m_3$

This matrix is $\pi= \begin{bmatrix} m_{1} & m_{2} & m_{3} & m_{4} \\ 1 & 2 & 4 & 3 \end{bmatrix} $$\rightarrow \pi(m)=m_1m_2m_4m_3$

And $\phi_2(\phi_1(m))=\pi(m)$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi. Re. "Claim:" I'm having difficulty in matching this to my question. I appreciate the reduction of simple multiple permutations. But these are part of a hash. So in your example, $m=3512$, and therefore as an example $H_4(m) = 110$ for a hash with 4 permutation tables. In the linked question we used 2 tables. $\endgroup$ Commented Mar 27, 2019 at 10:46
  • $\begingroup$ I'm trying to find out whether such a composition of permutation tables can be reduced to fewer tables, and thus less memory to store all of them. It's a functional composition reduction thingie job, but I'm not really sure what to call it... $\endgroup$ Commented Mar 27, 2019 at 10:47

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.