# Tag Info

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 ...

25

Well, AES is not a Feistel cipher because it's a substitution-permutation network instead. If I were taking a test that asked me why AES was not a Feistel cipher, this would be my argument: namely, that the structure of substitution-permutation networks is fundamentally different from that of Feistel networks. (Here one could elaborate on invertibility and ...

21

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 were carefully selected to work in tandem, such that every byte affects every other byte in the state within just two rounds. MixColumns ensures that every ...

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 ...

13

By definition, a Feistel network uses a series of rounds that split the input block into two sides, uses one side to permute the other side, then swaps the sides. As always, Wikipedia has a nice diagram. AES doesn't do this. Performing a round necessarily permutes the entire state. Each round consists of the SubBytes, ShiftRows, MixColumns, and AddRoundKey ...

10

First of all, we need to review what they mean by "parity of a permutation"; they don't mean whether the input block had a even number of 1's. Instead, they view the $n$ bit cipher (with a specific key) as a permutation on $2^n$ objects; that is, it can be review as a way of rearranging that set of $2^n$ objects onto itself. Now, permutations on a finite ...

10

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, one of the things that they showed was that if you replace the S-boxes in DES with randomly chosen ones, then the differential attack becomes much more ...

8

As Henrick notes, permutation is a mathematical term for a function (or map; these two words are essentially synonymous in mathematics) that rearranges the elements of its domain so that exactly one input is mapped to each output. In other words, a function $f$ from a set $S$ to $S$ is a permutation if and only if: no two inputs are mapped to the same ...

8

I think that you missed a pivotal point in the concept, which is the small blocks that are used to compose a secure PRF (or PRP), i.e. when you permute one bit, you actually change the value of the small block of that bit, i.e. the whole small-block is effected and thus prepared to be confused in the next round, this way you will reach a confusion of the ...

8

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 f(x)<N$. What's meant in RSA encryption is the later. A permutation of a set is a bijection from that set to that same set. Any injective function from a ...

7

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 operate upon X parts where 0 Image Sources: FEISTEL, SPN In balanced, data is divided in Two parts i.e N = 2, and X=1 (example is camellia cipher) In Unbalanced,...

7

a permutation will rearrange the input producing something of arbitrary length. I'm not sure about this. My understanding of a permutation is that it will always produce an output of the same length as the input. That is, a permutation simply reorders all the parts of the input without adding or removing any elements. A hash function does not have ...

7

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 probability). In order to find a preimage, just go forward until you get back to the starting point, keeping the previous value each time.

7

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 considerably, from all possible $256$ byte values to the printable characters permitted to be used in Twitter messages, and the distribution in this restricted space ...

7

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: Constructing an instance $\alpha$ of $A$ given black-box access to an instance $\beta$ of $B$ --- this is denoted by $\alpha^\beta$, where $\beta$ in the ...

7

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 intrinsically not something you can test by looking at its outputs. What you can do is write a decision procedure that will, with some probability, return a ...

7

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 makes the cipher insecure. But we can also construct such a block cipher secure under chosen-plaintext attack. Assume a secure block cipher with the same key ...

7

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 the encryption function from many 32-bit operations.This has proved to be a very successful method, but it has one side effect. It is rather hard to build an odd ...

6

I thought you were using a block cipher, i.e. a pseudorandom permutation. Instead as per your comment you are only permuting the order of the plaintext bits. This is not secure. For example, you can imagine the bit permutation is an n-by-n square matrix, where each row and column has a single 1 and the rest 0s. The input and output are then vectors of size ...

6

There is no uniform permutation; there is a permutation uniformly chosen from the set of all possible permutations over $Z_2^{128}$. It is evident that AES is not a uniformly chosen permutation, since its permutation is fixed for any key. One can consider a family $\{AES_K\}$ of AES permutations under all possible keys $K$. Even if the key is chosen ...

6

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 following requirement: provide a strong diffusion (in Keccak this is provided by $\rho$ and $\pi$). provide confusion ($\theta$ and $\chi$). In the case of ...

6

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 randomly and uniformly from the set of all $2^b!$ $b$-bit permutations. Unfortunately realizing random permutations suffers from similar problems as realizing random ...

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

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 encryption function $E_K$ as $$c = E_K(p) = P^{(n)}(S^{(n)}(p \oplus K_1 \oplus K_2 \oplus \dots \oplus K_n)),$$ where $p$ is the plaintext block, $c$ is the ...

6

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 its entirety, so it is not sufficient for security by itself. Instead, it is used to create a secure construction, e.g. using the sponge function. This function ...

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

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 it a permutation, since the way it works is by running arbitrary machines and then amplifying. Since there is no efficient way of checking if something is a ...

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 In Algebra, a Permutation of a set$X$is a bijective function$\sigma:X{\rightarrow}X$that for each element$x \in X$assigns a unique value$\sigma(x) \in X$. In practice, this could mean a lot of things. For instance, in DES a permutation is used that rearranges the position of the bits of the half block. This is a permutation$\sigma:[0..31]{\...

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