Tag Info

Hot answers tagged

35

The initial and final permutation have no influence on security (they are unkeyed and can be undone by anybody). The usual explanation is that they make implementation easier in some contexts, namely a hardware circuit which receives data over a 8-bit bus: it can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit ...


11

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


8

The security of a block cipher is, based on what we know, invariant to the permutation cycles of the S-box. This is because the values are always transformed (by a fixed function or a keyed function) before going through the S-box again in the next round. Furthermore, many S-boxes are functions not permutations (i.e., output size is different from input ...


7

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


6

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


6

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


6

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


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


4

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


4

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


4

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


4

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


4

"$BW_N$ is a permutation over the squares $\mod N$". Does someone know what that means? You define your map $BW_N:\mathbb{QR}_N\rightarrow \mathbb{QR}_N$. Note that $$\mathbb{QR}_N:=\{r\in Z_N: r\equiv y^2 \pmod{N}, y\in Z_N\}$$ and a permutation is a one-to-one mapping (bijection) from a set into the same set. Basically, this map is a permutation if ...


4

This is purely a counting problem. We want the number $N(n,m)$ of possible permutations of $n$ things, with the constraint that only $m$ among these things can map to themselves ($0\le m\le n$). The values in the question are $n=11$, $m=5$. It holds that $N(n,n)=n!$ (that's the number of permutations of $n$ elements). It holds that ...


4

The permutations in your question are given in Cauchy's two-line notation, where the upper line gives the input index to the permutation function, and the lower line gives the resulting permuted index. For example, the definition $$\sigma = {1\ 2\ 3 \choose 3\ 1\ 2}$$ means the same as $$\sigma(1) = 3,\quad \sigma(2) = 1,\quad \sigma(3) = 2.$$ Thus, if we ...


3

In a strict sense, no. NP is about worst-case hardness. Cryptography requires average-case hardness. $P \ne NP$ implies the existence of problems that are hard in the worst-case (the worst-case running time is super-polynomial) but says nothing about average-case hardness. For block ciphers, we need average-case hardness. Therefore, there are good ...


3

At some level, there is no essential difference. Certainly, there is no difference in the distribution on the random variable $O$ vs $f$. However, there is a potential difference in how the terms are typically used. If we say that $O$ is a random (bijective) oracle, then we are usually implicitly hinting that it is available to everyone: the legitimate ...


3

If you take a pseudo random permutation permutation you usually get a hard to invert PRF. AES with its 128 bits is a bit narrow, but Salsa's 512 bits are certainly wide enough. Commonly used compression functions are built from block-ciphers with similar techniques: For example Davies–Meyer (used in popular hashes such as MD5, SHA-1 and SHA-2) uses: $H_i ...


3

There are so many possible solutions here. Without giving your requirements more carefully, it's just not possible to tell what would count as a valid solution. Here are a bunch of schemes that offer better security than simply truncating to $N/2$ bits and applying 4 rounds of Luby-Rackoff: For instance, one approach is to truncate the random function to ...


3

permutation is mapping a finite set to itself (a bijection from Set to itself) hash function is not a permutation, because it has tow different sets: input: infinite variable length output: finite fixed length


3

How secure is this cipher? At first glance, not very. It would appear to be vulnerable to a ciphertext-only attack, for example, the attacker can recover the plaintext given a ciphertext of about 10k (actually, he probably can deal with less), even assuming that all the attacker initially knows is that the plaintext is "ASCII English", and he has no ...


2

For Vigenère specifically, you can make it harder to break by increasing the size of the key and by making the key truly random. If the key is truly random, longer than the plaintext and never reused, then Vigenère becomes equivalent to a One Time Pad. Even without going that far, it is possible to strengthen many, though not all, cyphers by lengthening ...


2

All permutations have a cycle decomposition from which you may immediately read off your $P(n-2)$ and $P(n-1)$. There are trivial algorithms for doing this that run in either $O(n)$ time and $O(n)$ space (invert the permutation), or $O(n^2)$ time and $O(1)$ space (walk backwards by querying everybody repeatedly). You could adapt that invert the permutation ...


2

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


2

Sticking to monoalphabetic ciphers, Vigenere can be combined with a secret random-like substitution of the plaintext or/and ciphertext alphabet, making it significantly more resistant. If Vigenere encryption is $$x_j\mapsto (x_j+K[j\bmod k])\bmod{26}$$ where array $K$ is the key or length $k$, I'm discussing $$x_j\mapsto (S[x_j]+K[j\bmod k])\bmod{26}$$ ...


2

If you are asking about a truly theoretical limit for a theoretical block cipher (as opposed to a practically usable one, like AES), you could calculate the number of possible keys like this: A block cipher, together with a key $k$ ($|k|$ = $M$), describes one of many possible random permutations: For every plaintext block, there is exactly one ciphertext ...


2

There is a generic construction called Permutator, which can turn a seekable stream of random bits into a permutation. A "seekable stream" is obtained from a PRF by applying the PRF on an input index. This construction works with any target space (it generates a permutation of a space of size $n$ where $n$ is not necessarily a power of 2). Also it is ...


2

It means that it maps quadratic residues $\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ to quadratic residues. A quadratic residue is a number $x$ such that $x = y^2 \pmod N$ where $N=pq$. A trapdoor means that once you know the factorization of $N$ it is easy to break quadratic residuocity problem. $p=q=3 \pmod 4$ because you choose 'safe' primes $p,q$ such that ...


2

Each one of your first two sentences has a mistaken premise: you're starting from some assumptions that aren't actually true. DES does not use small PRPs for saving memory. It doesn't use small PRPs at all. The DES S-boxes are not PRPs. The DES F-function is not a PRP. A SPN does not use several small PRPs for saving memory. A SPN doesn't use PRPs at ...


2

You could 1. generate a key from the password, 2. seed a deterministic random number generator from the key, 3. use the random number to generate a permutation, using, e.g., Knuth's algorithm.



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