2
$\begingroup$

E.g. given a $n$-bit message $m_0$ and an encryption function $f$

After applying the function $c$ times it will result in $m_0$ again.

$f^1(m_0) = f(m_0) = m_1$

$f^2(m_0) = f(f(m_0)) = f(m_1) = m_2$

..

$f^c(m_0) = m_c = m_0 $

On top of that an inverse function $f^{-1}$ with about equal computation time should exist as well. Also no short-cut in computing $m_i$ is allowed. It always either require the knowledge of $m_{i-1}$ or $m_{i+1}$. Given two messages $m_i$, $m_j$ there should be no easy way to compute the difference $|i-j|$

Some example but with unknown cycle size would be AES. I'm looking for an encryption method with known cycle size $c$ for all $m_0 \in \{0,1\}^n$

.

Further notes:

  • $m_0$ will be a random number. An additional (fast) function is allowed which select only numbers with certain properties

  • instead of $m_0$ a small known offset $k$ is allowed as well. With this $m_c$ can be different to $m_0$ but $m_{c+k} = m_{k}$

  • 'hacking'-time should scale linear with cycle size $c$


(Edit) Update: Additional requirements

  • an attacker has full access to the source code and runtime variables. All computations done at the local computer
  • given two valid random messages $m'$ the chance should be high they are part of the same cycle (lets say $>10\%$ or at least $>0.4\%$). Or in other words different cycles are allowed but not much more than $10$ or $256$ as max limit (lower is better, except $<20$ would even be better than just $1$)
  • exact cycle size don't need to be known. An approximation $\pm 50\%$ is sufficient (but if it contains multiple cycles those should be similar to each other ($\pm5\%$) )

Other than in most cryptography problems the relation in between should be encrypted not the messages themselves.

$\endgroup$
1
  • 1
    $\begingroup$ I'm pretty sure such a cipher wouldn't be secure because it would allow a distinguishing attack if the attacker had an encryption oracle. $\endgroup$ – bk2204 Feb 28 at 2:33
2
$\begingroup$

CAUTION: The following matches the requirement "no short-cut in computing $m_i$ is allowed. It always either require the knowledge of $m_{i-1}$ or $m_{i+1}$. Given two messages $m_i$, $m_j$ there should be no easy way to compute the difference $|i-j|$" only with respect to an adversary not knowing the key. That goes straight against the added requirement that an adversary has "access to runtime variables".


Well make an explicit construction from an $n$‑bit block cipher $E$ with the desired keyspace. Note $D$ the matching decryption.

Make a public partition of the blockspace $\{0,1\}^n$, assimilated to $[0,2^n)$ by e.g. big-endian convention, into intervals of size $c$ or slightly more according to the allowance for $k$. When $c$ is a power of two (e.g. $c=2^n/8$), that can be $2^n/c$ intervals of size $c$. When $\left\lfloor2^n/c\right\rfloor\ge(2^n\bmod c)$ [thus including any case with $c\le2^{n/2}$ ], that can be $\left\lfloor2^n/c\right\rfloor-(2^n\bmod c)$ intervals of size $c$, and $2^n\bmod c$ intervals of size $c+1$.

Define $h$ the bijection on $\{0,1\}^n$ that, to $x$ in a certain interval of said partition, associates the next integer in said interval if that's still in said interval, or the first integer in said interval otherwise. When $c$ is a power of two, that can be $h(x)\underset{\text{def}}=c\left\lfloor x/c\right\rfloor+(x+1\bmod c)$.

Define $f\underset{\text{def}}=D\circ h\circ E$. That is $f$ the bijection on $\{0,1\}^n$ with $f(x)=D(h(E(x)))$. That $f$ has the property "After applying the function $c$ times (within allowance) it will result in $m_0$ again" thought in the question, and has matching decryption $f^{-1}=D\circ h^{-1}\circ E$.


I conjecture that under the ideal cipher model for $E$, the resulting block cipher $f$ is secure when the number of (adaptive) queries an adversary can make remains negligible compared to $c$.

One slight implementation difficulty is avoiding side-channels in the implementation of $h$ and $h^{-1}$.

$\endgroup$
3
  • $\begingroup$ ty4answer, I'm not 100% sure if I understood it correct so I better ask. $c$ could also just be $2^n$, $2^{n-1}$ or $2^{n-2}$, right? $\endgroup$ – J. Doe Feb 28 at 15:07
  • $\begingroup$ @J.Doe: yes, $c$ could be $2^n$, $2^{n-1}$, $2^{n-2}$, $2^{n-3}$, and any of these matches "given two valid random messages the chance should be >10% they are part of the same cycle". However the new requirement that an adversary "has access to runtime variables" plain kills my construction, for it allows a shortcut. $\endgroup$ – fgrieu Feb 28 at 17:40
  • $\begingroup$ ye, sorry about changing. However interesting answer. Maybe it can be combined with homomorphic encryption. That could lead to unknown value of $x$ in $h$. $\endgroup$ – J. Doe Feb 28 at 18:08

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.