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.

$\endgroup$

1 Answer 1

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)$

$\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$
    – Paul Uszak
    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$
    – Paul Uszak
    Mar 27, 2019 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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