6
$\begingroup$

In the accepted answer to a question in Computer Science Stack Exchange, it was mentioned that a block cipher in counter mode makes a random number generator with a large bitspace, which visits every element of the domain exactly once before cycling.

Of course, with usual block cipher block sizes (of 128 bits and more), you'll never reach that cycling point. In the comments to another answer, the question came up whether we can do the same with a much smaller domain size.

Is there a cryptographic way of constructing a keyed permutation with a "small" domain size, such that even given all the input-output pairs, it's computationally impossible to derive the key?

Or would a small-domain permutation always allow brute-forcing of the key?

(The purpose of such a function would be to build a PRNG which cycles through all values once, and then again in a different order: use this keyed permutation with a fixed key and a counter input, and when the counter overflows, increment the key.)

$\endgroup$
2
  • $\begingroup$ Cycle length and security do not necessary correlate. This is shown by the bad security but long cycle length of LFSRs (not directly relevant for this, but one doesn't guarantee the other). $\endgroup$
    – tylo
    Jul 26, 2022 at 16:15
  • $\begingroup$ Here we are looking for high security and (relatively) low cycle length. $\endgroup$ Jul 26, 2022 at 22:46

3 Answers 3

5
$\begingroup$

No, small domain keyed permutations are not inherently unsafe, for some definition of unsafe adapted to the inherent limitations of a small domain. We can construct keyed permutation with a small domain that are computationally indistinguishable from a random such permutation. That's standard in Format Preserving Encryption. Several constructions are known.

In the following I'll assume a domain of $v$ values (of $w$ bits with $w=\log_2v$), and $k$ keys ($\ell$ bits with $\ell=\log_2k$).

Would a small-domain permutation always allow brute-forcing of the key?

No, but for a small enough domain (including $v\lesssim 24$, that is $w\lesssim4.6$) it is possible to tabulate all input/output pairs and find a working key (not necessarily the key), regardless of how large $k$ is. Notice there must be equivalent keys when $v!<k$.


The purpose of such a function would be to build a PRNG which cycles through all values once, and then again in a different order: use this keyed permutation with a fixed key and a counter input, and when the counter overflows, increment the key.

Fine, if it's OK that this PRNG is distinguishable with sizable advantage given less than $\sqrt v=2^{w/2}$ outputs, by the very fact that it does not repeat often.

For $w=32$ as asked in this comment, and in a use case where inherently the whole message space will eventually get exhausted, we must not use a pure Feistel cipher, with at each round $(L_{i+1},\,R_{i+1}):=(R_i,\,L_i\oplus F_i(K,R_i))$. That's because this implements an even permutation, which allows to predict the $(2^{32}-1)^{\text{th}}$ and $(2^{32})^{\text{th}}$ values generated with certainty, from the previous $2^{32}-2$. We can fix the parity issue by adding a component of a key modulo $2^{32}$; the resulting permutation will be odd or even depending on if that key component is odd or even.


Here is an example reaching the (low) "I don't see how to attack it right after writing it" security level:

// a 32-bit PRP with 192-bit key
uint32_t prp32(const uint64_t k[3], uint32_t b) {
  uint64_t u = k[0], v = k[1], w = k[2];
  uint32_t r = 48;
  do {
    b ^= b<<1 | b<<5;              // Xor with non-linear function
    u += v ^ r;
    b += b<<4;                     // Add
    v ^= w;
    b = b<<13 | b>>19;             // Rotate
    w += u<<27 | u>>37;
    b = (b>>3 ^ b) + (uint32_t)u;  // Xor and enter round key
  } while(--r!=0);
  return b;
}

Rationale:

  • This is an iterated block cipher transforming the whole block $b$ at each round, meanwhile deriving the round keys (entered as the low 32 bits of $u$).
  • Each of the 4 sub-transformations of $b$ is a permutation (for constant $u$), hence the whole construction is a permutation.
  • The 4 sub-transformations of $b$ are ARX, with an extra non-linear first one. The small shift constants (1, 5, 4, 3) relatively to the word width (32) are such that the Add and Xor steps operate on nearly the full width.
  • $(u,v,w)$ are initialized per the key and evolve per a reversible ARX transformatiion (in the three non-commented lines of the round; these could be moved at start of round without changing the outcome: they are interleaved only in the interest of pipelining).
  • On most modern CPUs, every operation has a straightforward hardware implementation. Compiler-generated code can be close to optimal, with minimal opportunity for data-dependent or key-dependent timing variation.
  • Combining the round key with $u$ by addition modulo $2^{32}$ leads to non-constant parity of the permutation (further, this was verified experimentally).
  • Entering the round number in the transformation of $u$ prevents the all-zero key to be special (e.g. have $b=0$ as fixed point).
  • It's entirely debatable if the 48 rounds are adequate to compensate the slow diffusion in the block $b$ (which would need to be quantified). My hope is that it's more conservative than in Simon. That's based on a guestimate that each round is worth at least 1.5 rounds of Simon32, because the 3 operative transformations (ignoring the rotate) are at least that much wider, and slightly more complex.

The above methodology (or a more conservative Feistel cipher) is adequate for integer $w$ from like 8 to 64 bits. For $v$ not a power of two, we can make a cipher for the next power of two, then reduce the domain by cycle walking, which at worse (when $v$ is just above a power of two) will about double the average work. Beware there will be a data-dependent timing variation, and in some contexts it can be harmful (but I don't see that it can be in the context of the question's PRNG).

$\endgroup$
5
  • $\begingroup$ For this class of PRNG we were looking at, I see "all output values are produced once, then again in a different order" as a given, so one would need to compare it to "an actual random permutation in counter mode, then switched to a different one after all values are produced" when looking for a distinguisher, not to a fully random sequence. $\endgroup$ Jul 26, 2022 at 22:41
  • $\begingroup$ Thanks for the example, I'll have to draw a diagram of the round function to understand it. Is there a straightforward way to extend this to non-power-of-2 domain sizes? $\endgroup$ Jul 26, 2022 at 22:43
  • 1
    $\begingroup$ Ah, actually reading the linked Wikipedia entry helps. We can use cycle walking (iterate until the result lands in the domain) here, which usually won't take that many steps if the domain size is not too far below the bit size. $\endgroup$ Jul 26, 2022 at 22:52
  • $\begingroup$ Err, how is a 192 bit key a small domain? $\endgroup$
    – Paul Uszak
    Jul 27, 2022 at 13:51
  • $\begingroup$ @PaulUszak the "domain" corresponds to the block size (32 bit blocks in fgrieu's example make a domain size of $2^{32}$), and not to the key size. $\endgroup$ Jul 27, 2022 at 18:17
1
$\begingroup$

Since "small" is relative, conceptually we could use the AES with say 256 bit key and 128 bit blocksize. All of the below are impractical but illustrate the point:

Building a codebook given all P/C pairs for a fixed key will "break the cipher", but will not expose the key due to the $2^{256-128}$ degrees of freedom, no such attack is known to the best of my knowledge.

Therefore one could use this key in counter mode, and then choose a fresh key and repeat, again and again.

As for more realistic domain sizes, say you wanted a 64 bit domain instead. Now it will be trickier, say you use AES with 128 bit keylength.

If you want to take a projection of the blocks, say the 64 lower order bits, this will no longer cycle through each of the $2^{64}$ states one by one. If it did, this would be a weakness in the cipher design.

However, I don't see why the following should not work, without introducing a weakness. Let $Pi(\cdot)$ be the projection to the first 64 bits of $\{0,1\}^{128}.$

Pick a random key $K$. Operate in counter mode, start with a list $L$ of size $2^{64}$ initialized to zeroes.

For $x \in \{0,1\}^{128}$ do

$\quad y=E_K(x)$ If $L[y]$ is zero, output $y$ and let $L[y]\leftarrow 1;$

Otherwise move up in the list (cyclically if necessary) to the first position $y'$ which is zero

$\quad$ output $y'$ and let $L[y']\leftarrow 1;$

end for;

Afterwards choose a fresh key $K'$ and repeat.

$\endgroup$
2
  • 3
    $\begingroup$ Hmm, I was thinking more about something in the area of 32 bits (but not necessarily a power of two), and efficiently computable (not "make a list of all values"). $\endgroup$ Jul 25, 2022 at 22:50
  • $\begingroup$ With a cipher like AES-256, finding some key which produces the same codebook (not necessarily the key originally used) I would count as breaking the cipher (though it would not necessarily break my PRNG). $\endgroup$ Jul 26, 2022 at 22:34
-2
$\begingroup$

No, of course not(ish). That's why cryptographic keys and their underlying blocks get bigger and bigger though time.

Or would a small-domain permutation always allow brute-forcing of the key?

In a deterministic cipher yes, as successful decryption can be validated from the semantic context of the messages. Does it matter whether we decrypt via brute force or frequency analysis if the message is revealed in a few seconds on an NVIDIA graphics card GPU?


Just imagine if the "key" was physical and not mathematical. A Western Union telegram only used 6 bits of encoding. Yet overlay that with a true one time pad and a 6 bit encryption becomes unbreakable.

What's the question?

$\endgroup$
5
  • 1
    $\begingroup$ This is gibberish. $\endgroup$
    – Maeher
    Jul 26, 2022 at 12:58
  • $\begingroup$ The semantic validation is not really relevant, as I said that the attacker can get arbitrarily many plaintext-ciphertext pairs. The key space can be a lot larger than the message space (up to $k = m!$ before you have to get different keys which act the same way on every block). (For example, you could have a cipher on 26 characters with > 80 bits of key space (i.e. $> 2^{80}$ different keys).) Of course, I didn't specify "small" here, my bad. $\endgroup$ Jul 26, 2022 at 22:28
  • $\begingroup$ @PaŭloEbermann Err, how can an arbitrarily long message space be smaller that a very small key space (which is what I think you were asking about)? Am I missing something obvious? Semantic context is absolutely relevant here. "The semantic validation is not really relevant, as I said that the attacker can get arbitrarily many plaintext-ciphertext pairs. " has a known frequency distribution as it's English. English does not follow an exponential distribution. Think of the monkeys. $\endgroup$
    – Paul Uszak
    Jul 27, 2022 at 13:42
  • 1
    $\begingroup$ A keyed permutation (aka block cipher) has not an arbitrary long message space, but a fixed one (e.g. 128 bits = $2^{128}$ different messages for AES, or 26 different messages for classical monoalphabetic ciphers). You can use a mode of operation to use it to encrypt arbitrary messages, but that's not what I'm asking about, as I want to use it as a PRNG, not to encrypt things. $\endgroup$ Jul 27, 2022 at 18:12
  • $\begingroup$ My question was asking about a permutation where "even given all the input-output pairs, it's computationally impossible to derive the key". Frequency analysis is not needed if you already know all plaintext-ciphertext pairs. $\endgroup$ Jul 27, 2022 at 18:15

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.