27

There are at most $n \cdot (n - 1)$ permutations of $\mathbb Z/n\mathbb Z$ of the form $x \mapsto ax + b$: if $n$ is prime, there are $n - 1$ choices for $a$ and $n$ choices for $b$ under which this is a permutation. There are $n!$ permutations of $\mathbb Z/n\mathbb Z$ altogether. So the probability that a uniform random permutation has this form is ...


20

Applied cryptographers often see one of the three variants of AES, say AES-256, as a function: $$\begin{align}E:\ \{0,1\}^{256}\times\{0,1\}^{128}&\to\{0,1\}^{128}\\ (k,p)\quad &\mapsto c=E(k,p)\end{align}$$ such that: for all $k\in\{0,1\}^{256}$, encryption with key $k$ defined as follows $$\begin{align}E_k:\ \{0,1\}^{128}&\to\{0,1\}^{128}\\ p\...


18

A three-round Feistel network is a good example of a realistic construction that is a secure "weak" PRP, but not a "strong" PRP. A Feistel network uses the permutation $P_f(L, R) = R, (L\oplus f(R))$, where $f$ is an element of a pseudorandom function family. This PRP will be keyed with three keys $k_1, k_2, k_3$, which will be used to key a PRF $F$ ...


17

In theory. No. The inverse of a secure PRP need not be a secure PRP. Here is what we can guarantee. The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP. Any secure sPRP is a secure PRP. Therefore, the inverse of a secure sPRP will be a secure PRP. FYI, if you are not familiar with PRP/sPRP, the difference ...


12

The proof is loosely as below. Lets assume a one round Feistel network, where $2n$ bits are divided into $n$ bits each $L_0, R_0$ The encryption is defined as $L_{1} = R_{0}, \\ R_{1} = L_0 \oplus f(R_0) $ where f is any random function (PRF) and $\oplus$ is XOR operation Now the cipher text is $L_{2} = R_{1}, R_{2} = L_1 $ Decryption is same as ...


10

If you applied a PRF directly to the message to obtain cipher-text, you would not have the guarantee that you could actually decrypt the message. Suppose the PRF maps $n$ bit inputs to some $m$ bit output. The mental model of a PRF is as follows. You have have a gnome in a black box. When you hand him a string from the input space, he flips a coin $m$ ...


7

Use format-preserving encryption. The current NIST standards-track mode FFX should be sufficiently fast for your purposes. For your domain size, you might also want to try the swap-or-not shuffle, a new construction that is also pretty fast and dead simple to implement. To get the absolute best speed form these schemes you should use a single AES call as ...


7

The CBC-MAC construction indeed can use a PRF instead of PRP. It is now based on PRP due to historical reasons: the blockciphers used for CBC-MAC were based on permutations. From the security point of view there will be no difference: the security proof for the CBC-MAC first converts PRP to PRF (which is indistinguishable up to $2^{n/2}$ queries) and then ...


7

Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. – xagawa @xagawa Yes, I want that :-) – Dingo13 I list the PRFs based on the number-theoretical assumptions. They are ``arithmetic or mathematical function.'' You can use the Feistel network to obtain (S)PRPs from PRFs in theory. From the DDH assumption The Naor-Reingold ...


7

Disclaimer: I'm one of the authors of the said permutation. Gimli does not aim to be used as a block cipher (in the traditional sense of it: $x \to (\sigma \circ K_{\mathit{add}})^{\mathit{nb}_{\mathit{rounds}}}$ with a block size of 384 bits or similar constructions); it is better to use it with a sponge construction such a Monkey-Duplex/Monkey-Wrap or ...


7

The Luby-Rackoff theorem says that a 3-4 round Feistel network is a pseudorandom permutation for some sufficiently large block size. As this paper by Patarin on Feistel networks with 5 or more rounds puts it: We will denote by $k$ the number of rounds and by $n$ the integer such that the Feistel cipher is a permutation of $2^n$ bits → $2^n$ bits. In [3] ...


6

Salsa20 is a stream cipher based on a pseudorandom function, not a pseudorandom permutation. For a fixed key $k$ and nonce $n$, the mapping $PRF^{S20}_{k,n}: \{0,1\}^{64} \to \{0,1\}^{512}$, which maps a "Stream position" to "keystream block", is supposed to be a pseudorandom function. It is not supposed to be injective (i.e. a permutation, even less since ...


6

For convenience, let's assume that $\mathcal{K} = \mathcal{D}$ so that the key $k \in \mathcal{D}$. Define $E$ to be some strong PRP, and let $D$ be its inverse. Now, define a PRP $E' : \mathcal{D} \times \mathcal{D} \to \mathcal{D}$ such that $E'_k(x) = E_k(x)$ for all values of $k$ and $x$, but with the following adjustments: Define $E'_k(k) = 0$ for ...


6

I assume that for a fixed key $K$, you are asking why $f(m) \overset{\underset{\mathrm{def}}{}}{=} <STREAM> \oplus\ m $ is not a PRP, where $<STREAM>$ is the stream that is generated from the key $K$. $f$ verifies at least two properties that PRP in general do not verify: $f(m_1) \oplus f(m_2) = m_1 \oplus m_2$ $f(f(m_1)) = m_1$


6

The obvious way to construct such a pseudorandom single-cycle permutation is to take a pseudorandom permutation $P$ (which need not be single-cycle), a simple fixed single-cycle permutation $Inc$ (e.g. just increment the value by 1), and construct: $$S = P^{-1} \ \circ Inc \ \circ P $$ That is, to evaluate $S(x)$, you first apply the permutation $P$ to $x$,...


6

This precise issue recently arose in light of suspicious patterns in the S-box of a Russian cipher Kuznyechik. See: Xavier Bonnetain and Léo Perrin and Shizhu Tian: Anomalies and Vector Space Search: Tools for S-Box Analysis, Asiacrypt 2019 One way the authors chose to quantify how unlikely such a permutation could have occurred by chance is to find the ...


6

I read that two-round Feistel network is not a secure PRP That's easily seen:                                     It holds $P_L\oplus C_L=F_0(P_R)$. That implies a distinguishable property: for any fixed $P_R$ and whatever the round function $F_0$, when we flip bit(s) in $P_L$, that flips the corresponding bit(s) in $C_L$ and leaves the other bit(s)...


6

I can understand why a simple substitution cipher can be broken easily due to English letter frequencies can be used and even English diagrams like th can be used, also a complete random substitution will have a key length of 26! which can be done(around 2^88 maybe NSA) The first part is correct. A thousand years old Frequency analyses can break this very ...


6

It's worth mentioning that permuting things can still leak a lot of information. For example, imagine you see an email with some (small) number of numerals (say 3 or 4), and a symbol such as $. From that, it wouldn't be too difficult to get a narrow list of possible quantities of money that were discussed. Similarly, the presence of certain accented ...


5

I explain, criticize and try to improve the technique in the question (which asks for speed by using cryptographic techniques for arguably satisfactory functionality in a statistical simulation). Shuffling, and full-blown Format-Preserving Encryption aim at perfect or demonstrable cryptographic security, a different goal. Under the assumption that the (...


5

Patarin's proof isn't about distinguishing ciphertext from "random text", it's about distinguishing a Feistel cipher from a random permutation. That proof is also in the information theoretic world, which means that the Adversary is computationally unbounded, and as such can deduce everything about the cipher (the 'key', all remaining ciphertexts, etc). In ...


5

Ciphers with Arbitrary Finite Domains by Black and Rogaway have some options like Prefix Ciphers, Generalized Feistel networks , Cycle walking etc. Also Format preserving encryption has traits that you are looking for , but NIST standardized ones are patented by Voltage Inc. In general Feistel networks + Cycle walking would give a good option for any ...


5

You are quite correct. A PRP in counter mode is, in fact, distinguishable from a random sequence if you approach the "birthday bound". We get around this by never generating that much output at once. With a 128 bit block cipher, an output of $2^{40}$ bytes (which is a lot of output) gives us a distinguishing advantage of about $2^{-56}$ (the probability ...


5

Wel'll consider a symmetric Feistel cipher with $n$-bit block using ideal independent random functions at each round. Making it computationally indistinguishable from a random permutation requires some number of rounds depending on the attack model; and on if we are content with asymptotic security for $O(2^{n/2})$ work, or want asymptotic security with ...


5

The problem is small enough that the desired PRP can be implemented as a small array of 16 values initialized using the Fisher-Yates shuffle, with a pseudo-random generator deciding the indexes of the shuffles. That's probably the simplest, thus the best except perhaps when side channels (such as cache-induced timing variations) are a consideration. ...


5

If the output domain is large enough so that the probability of getting a collision in the PRF is negligible, then the output of a PRP and PRF are indistinguishable. Thus, in principle, the answer is yes - you can interchange these freely (under the above condition). Having said that, it's unclear to me why you would want a non-invertible PRP rather than a ...


5

Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions? No. What are the theoretical cryptographic implications of using a PRP instead of a PRF? We have a bound for the security of Luby-Rackoff based on the PRF-Security of F. We have a bound on the PRF-security of a PRP ("PRP/PRF-Switching-Lemma"). ...


5

All three are families of functions. For example, $f_k(x) = k \oplus x$, where $\oplus$ is xor and $k$ and $x$ are 256-bit strings, is a family of functions; for any 256-bit string $k$, there is a function $f_k$ which given another 256-bit string $x$ returns the xor of $k$ and $x$. The input and output spaces need not be the same; we could imagine a family ...


5

AES is not an ideal cipher, nor is it intended to be an ideal cipher. AES is meant to be a practical cipher that offers a strength close to the key size. That means it is computationally infeasible to find the key even if given the plaintext and the ciphertext. AES - when correctly used with a strong mode of operation - produces ciphertext is ...


5

Entropy and bias are not the same. Yes, total entropy is additive so as you suggest 7 bits of badrand() produce a total of 1.064 bits of entropy. So? How would you use that? In cryptography we aim to use some source to produce a stream of independently and identically distributed random bits. Assume a plaintext ($p$) of octets XORed with an octet keystream (...


Only top voted, non community-wiki answers of a minimum length are eligible