# Tag Info

26

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

16

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

13

Our Professor, Christof Paar, sat together on lunch a few years ago with one of the main designers of DES. He said that for getting it as specification, they had to build a piece of hardware which encrypts via DES. Shortly before finishing the project, they discovered that their wiring into the box was somewhat intermingled. Building such hardware stuff was ...

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

9

Yes, an additional bit permutation of pseudo-random data from a secure Pseudo-Random Number Generator is secure, subject to the condition that this bit permutation is independent of the key material of the PRNG and of any data derived from that (including the pseudo-random data). An argument is that if this permutation is public, the adversary can do/undo ...

9

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

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

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

Something I wrote years ago to describe the IP and Inverse IP. With a copy of the FIPS Pub in hand you can see the correlation between registers and bits. Essentially the data is shifted in serially (for an interface smaller than 64 bits, in this case 8 bits wide) and used in a parallel fashion. In hardware and an 8 bit interface the IP and Inverse IP ...

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

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

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 $f(x)$ is a particular member of a finite set of $N$ elements, equivalently integers in range $[0,N)$ or $\mathbb Z_N$ . What's meant is $f(x)=x^e\bmod N$. A ...

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

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

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

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]{\... 5 If I understand correctly, you want a function that for each input string$p$assigns a permutation over an alphabet$L$. If the number of elements in$L$is small enough, the permutation set$P(L)$will be enumerable. More precisely,$|P(L)| = |L|!$. There exists a surjective function$f:\{0,1\}^k \to P(L)$that for each bit string$s$of length$k$... 5 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\$,...

5

By definition, applying the initial Permutation of DES is shuffling bits per 01 02 03 04 05 06 07 08 58 50 42 34 26 18 10 02 09 10 11 12 13 14 15 16 60 52 44 36 28 20 12 04 17 18 19 20 21 22 23 24 \ 62 54 46 38 30 22 14 06 25 26 27 28 29 30 31 32 ----\ 64 56 48 40 32 24 16 08 33 34 35 36 37 38 39 40 ----/ 57 49 41 33 25 ...

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