Skip to main content
29 votes
Accepted

How to check whether the permutation is random or not

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 ...
Squeamish Ossifrage's user avatar
23 votes
Accepted

Formally, what is AES?

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,...
fgrieu's user avatar
  • 143k
10 votes

Nexor, an encryption algorithm that promises unlimited key sizes: Is it safe?

Looking very briefly at the source, it's just using the output of /dev/urandom to generate keys, then using that as a (poor) One-Time Pad. /dev/urandom is just a ChaCha20-based RNG with some decent ...
SAI Peregrinus's user avatar
10 votes
Accepted

Is there a 32 bit block cipher that is also a permutation over all 4bn elements?

A block cipher with any given key is always a permutation. It will map all possible inputs to all possible outputs. If it didn't, and multiple inputs mapped to a single output, then it wouldn't be ...
forest's user avatar
  • 15.4k
9 votes

Any advantage to a block cipher which is not efficiently invertible?

I would argue that for many cryptographers the argument goes even further. Given that block cipher streaming modes are favoured for bulk encryption, is invertibility needed at all? If one follows this ...
Daniel S's user avatar
  • 24.2k
8 votes

What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

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 ...
Squeamish Ossifrage's user avatar
7 votes
Accepted

How to build disk encryption system using forward permutations like Gimli?

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}_{\...
Biv's user avatar
  • 10k
7 votes

Creating single-cycle permutations

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....
poncho's user avatar
  • 149k
7 votes
Accepted

How random are permutations generated from Feistel networks with a small number of rounds?

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 ...
Luis Casillas's user avatar
7 votes
Accepted

Two Round Feistel network

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: ...
fgrieu's user avatar
  • 143k
7 votes
Accepted

Are sponges inherently inefficient when compared to other constructions?

Are sponges inherently inefficient when compared to other constructions? In a way, yes. The sponge/duplex is serial rather than parallelisable. However, there are ways of making permutation-based ...
samuel-lucas6's user avatar
6 votes
Accepted

Why are stream ciphers not PRPs?

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 ...
Thomas Prest's user avatar
  • 1,080
6 votes

How to check whether the permutation is random or not

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 ...
Mikero's user avatar
  • 13.9k
6 votes
Accepted

What makes AES look like an ideal cipher?

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 ...
Maarten Bodewes's user avatar
  • 93.5k
6 votes
Accepted

Why I can't permutate an email and get away with it?

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, ...
kelalaka's user avatar
  • 49.1k
6 votes

Why I can't permutate an email and get away with it?

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 ...
Mark Schultz-Wu's user avatar
  • 13.6k
6 votes

Any advantage to a block cipher which is not efficiently invertible?

Indeed, a PRF is suited better than a PRP for various modes such as CTR. The problem is that we don't know how construct good PRFs other than from a PRP. One way is simply to pretend that our PRP is ...
Fractalice's user avatar
  • 3,097
6 votes

Any advantage to a block cipher which is not efficiently invertible?

A PRP is Pseudo-Random Permutation and we want them to be indistinguishable from random permutations. AES and all block cipher are supposed to be PRP. The permutation means there is an inverse and ...
kelalaka's user avatar
  • 49.1k
6 votes
Accepted

Is this pseudo random function any good and/or original?

The code in the question implements any one of the $2^{65\times64}\approx2^{(2^{12.02})}$ "affine" functions from $\{0,1\}^{64}$ to itself, that is functions with the property $$\forall u,v,...
fgrieu's user avatar
  • 143k
5 votes

Pseudo-random permutation of a range

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 ...
fgrieu's user avatar
  • 143k
5 votes
Accepted

Is 3 rounds of Feistel enough for making a PRP?

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 ...
5 votes
Accepted

Permutation for which an inverse is a hard problem

It is obviously possible; one simple example is the function $f(x) = g^x - 1 \bmod p$, where $p$ is a large prime, and $g$ generates the entire group $\mathbb{Z}_p^*$; this is permutation over the ...
poncho's user avatar
  • 149k
5 votes
Accepted

Can we use a PRF as a PRP?

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 ...
Yehuda Lindell's user avatar
5 votes
Accepted

PRP vs PRF for the F-function of a Feistel network

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 ...
SEJPM's user avatar
  • 46.2k
5 votes
Accepted

Sponge with PRF instead of PRP

I sent a mail to the Keccak team asking about this, and I got a response from one of the authors (Joan Daemen to be specific). According to him, we actually can instantiate Sponge functions and ...
DannyNiu's user avatar
  • 9,519
5 votes

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

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 ...
Paul Uszak's user avatar
  • 15.6k
5 votes

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

The other answer actually says that you need 2527 bits of input for each 256 bits of hash output. That's 9.9 bits per bit, not much worse than 7. The same calculations gives 849 input bits per output ...
benrg's user avatar
  • 777
5 votes
Accepted

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

I will take a slightly different approach, a side step to a simpler problem to gain intuition. Let's say we have a fair 6 sided die. And we wish to draw a number uniformly from 1 to 4. It can't be ...
Meir Maor's user avatar
  • 11.9k
5 votes
Accepted

How are the keys used in cryptography generated?

Cryptographic keys should generally be generated secretly and uniformly at random in the cryptosystem's key domain; that is in the set of valid keys for the cryptosystem. What makes a key valid ...
fgrieu's user avatar
  • 143k
4 votes
Accepted

help with cryptanalysis of a sponge permutation

I don't think there is a way to check the period of such a sequence without actually computing it. That being said, having a long period like that is not desirable in cryptography. A psuedorandom ...
Ella Rose's user avatar
  • 19.7k

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