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

24

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

18

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 modern semantic security definitions. For example, this means that plaintexts with repeating symbols are distinguishable with high probability from plaintexts that ...

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

16

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$ be a key for a hypothetical Advanced Derangement Standard, ADS-256. To encrypt the $n^{\mathit{th}}$ message $m$, the ciphertext is $$c = m \oplus \bigl[\... 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 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,... 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 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 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 block ciphers like AES; One of them is identity, which key selects, we don't know. We don't know even it is selectable by one of the key spaces 2^{128},2^{196},... 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 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 ... 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 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 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 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 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 ... 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

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

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