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 ...
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,...
19
votes
Accepted
Example of a PRP that is not a strong PRP
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))$,...
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 ...
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 ...
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 ...
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 ...
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}_{\...
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 ...
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: ...
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 ...
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 ...
6
votes
Example of a PRP that is not a strong PRP
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} \...
6
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....
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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,...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
pseudo-random-permutation × 181pseudo-random-function × 57
permutation × 27
block-cipher × 26
pseudo-random-generator × 24
hash × 15
encryption × 14
algorithm-design × 14
feistel-network × 12
random-number-generator × 11
randomness × 11
sponge × 10
aes × 9
cryptanalysis × 8
provable-security × 8
authenticated-encryption × 7
format-preserving × 6
symmetric × 5
one-way-function × 5
des × 4
chosen-plaintext-attack × 4
distinguisher × 4
protocol-design × 3
collision-resistance × 3
key-derivation × 3