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
22 votes

Why is the permutation in AES (and other ciphers) not random or key-dependent?

You have clarified the question as asking about whether replacing ShiftRows with a random byte permutation would strengthen AES against differential attacks. It would not. ShiftRows and MixColumns ...
J.D.'s user avatar
  • 4,415
18 votes
Accepted

Are encryption algorithms with fixed-point free permutations inherently flawed?

Are all encryption algorithms with fixed-point free permutations inherently flawed? Yes - when fixed points, or the lack of them, is knowable and detectable. This is a violation of multiple ...
Natanael's user avatar
  • 369
16 votes

Are encryption algorithms with fixed-point free permutations inherently flawed?

Are all encryption algorithms with fixed-point free permutations inherently flawed? No, they are not inherently flawed. Consider the following cipher: Let $k_0$ be a key for AES-256, and let $k_1$...
Squeamish Ossifrage's user avatar
10 votes

Why is the permutation in AES (and other ciphers) not random or key-dependent?

I assume that you mean the S-box. The answer is NO! Randomly chosen S-boxes are not good choices for differential and linear cryptanalysis. When Biham and Shamir presented differential attacks on DES, ...
Yehuda Lindell's user avatar
9 votes
Accepted

Proving RSA is a permutation

First let's clarify notations. $f(x)=x^e \pmod N$ is non-standard, hesitating between $f(x)\equiv x^e\pmod N$ , meaning $N$ divides $x^e-f(x)$ $f(x)=x^e\bmod N$ , additionally specifying that $0\le ...
fgrieu's user avatar
  • 140k
9 votes
Accepted

Why not use a random permutation as a block cipher?

The issue is the lack of a compact representation. Assume you wanted to specify a 128-bit block cipher this way. A naive representation of a permutation on such blocks would consist of a sequence of $...
Morrolan's user avatar
  • 1,137
8 votes

Why is AES not a Feistel cipher?

The simple answer is "Because its an SPN cipher". What is difference between Feistel and SPN? SPN operates on whole data in one round, where as Feistel divides data into N parts where N>=2 , then ...
crypt's user avatar
  • 2,397
8 votes
Accepted

Parity attack on block cipher

When dealing with a block cipher of large block size, the text appearing as a quote in the question Most modern block ciphers have a 128-bit block size, but they operate on 32-bit words. They build ...
fgrieu's user avatar
  • 140k
8 votes
Accepted

Does there exist a universal one-way permutation?

To the best of my knowledge, this is unknown. That is, Levin's construction is a one-way function but most certainly not a one-way permutation. I don't see any way in which it can be modified to make ...
Yehuda Lindell's user avatar
7 votes

Can we exchange the permutation of a sponge construction?

The permutation should be as close to a random permutation as possible. This is essentially a block-cipher with a fixed key. A random permutation with given width $b$ is a permutation drawn ...
CodesInChaos's user avatar
  • 24.8k
7 votes
Accepted

When all shares of a secret are given to adversary as a permuted matrix

Let us first consider the problem without involving Shamir secret-sharing at all. Suppose that $n = 140$ and that the secret $\sigma$ is a 140-byte Twitter message. The space is thus restricted ...
Dilip Sarwate's user avatar
7 votes
Accepted

Periodic One Way Function

Security is clearly broken if there is a polynomial-length period with non-negligible probability (where by this I mean if a random point falls in a cycle with a poly-length period with non-negligible ...
Yehuda Lindell's user avatar
7 votes
Accepted

One-way permutation over a small interval?

How about this. Find an elliptic curve mod $p$, say $E:y^2=x^3+ax+b$ for some 256-bit prime $p$ such that the curve $E$ and its twist $E':dy^2=x^3+ax+b$ with $(\frac dp)_L=-1$ are both of prime order. ...
Daniel S's user avatar
  • 23k
7 votes
Accepted

Relationship between existence of OWFs and OWPs

Short answer: "No". The standard way to establish a statement of the form if a primitive $B$ exists then another primitive $A$ also exists is through a black-box reduction. This involves two steps: ...
ckamath's user avatar
  • 5,188
7 votes

Are encryption algorithms with fixed-point free permutations inherently flawed?

Block ciphers operators from $\{0,1\}^n \to \{0,1\}^n$. Each key selects one permutation among all possible permutations $n!$ and this is very small one if you compare $2^{128}$ to $128^{128}$ For ...
kelalaka's user avatar
  • 48.3k
7 votes

Randomness Testing

There is no such thing as randomness of a sequence (or of a permutation, or of a string, etc.). There is only randomness of a process for choosing sequences (permutations, strings, etc.), which is ...
Squeamish Ossifrage's user avatar
7 votes
Accepted

How strong is XooDoo vs AES?

Gimli is an unkeyed permutation, mapping a 384-bit input to a 384-bit output, $\{0,1\}^{384} \rightarrow \{0,1\}^{384}$. It is not a cipher by itself as you can reverse the output if you have it in ...
forest's user avatar
  • 15.2k
7 votes
Accepted

Are any block ciphers provably free of equivalent keys?

Yes, some block ciphers provably have no equivalent keys. For a start, it's very easy to exhibit such a block cipher, by restricting the key and message spaces to something enumerable. Granted, that ...
fgrieu's user avatar
  • 140k
6 votes

Shannon confusion and diffusion concept

I find the terms "confusion" and "diffusion" to be slightly nebulous and can lead to over-simplifications. Confusion For example, saying that "substitution" is responsible for "confusion" is not ...
Ella Rose's user avatar
  • 19.6k
6 votes
Accepted

Can we exchange the permutation of a sponge construction?

The security of the sponge construction rely on two parts: the size of the capacity. and the strength of the permutation used in the construction. This permutation is expected to have at least the ...
Biv's user avatar
  • 9,979
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....
poncho's user avatar
  • 146k
6 votes

DES: how does Richard Outerbridge's Initial Permutation operate?

By definition, applying the initial Permutation of DES is shuffling bits per ...
fgrieu's user avatar
  • 140k
6 votes

modified substitution permutation networks

Your construction is completely insecure: a single known plaintext / ciphertext block pair is sufficient to decrypt all blocks encrypted with the same key. Specifically, let me write your block ...
Ilmari Karonen's user avatar
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.1k
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
  • 48.3k
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's user avatar
  • 12.5k
5 votes

What is the importance of $f_k$ in a feistel network being a permutation

I assume that you are referring to the round function. This is false. The whole advantage of a Feistel network is that $f_k$ does not need to be a permutation. Indeed in DES, it is not a permutation. ...
Yehuda Lindell's user avatar
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
  • 140k
5 votes

Are encryption algorithms with fixed-point free permutations inherently flawed?

There are three nice answers here, each supported with well thought out arguments. It seems to me that not only is it difficult to distinguish between fixed point free and non fixed point free ...
kodlu's user avatar
  • 22.1k

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