# What is the difference between a hash and a permutation?

As defined by Wikipedia a hash function is

[...] any algorithm or subroutine that maps large data sets of variable length to smaller data sets of a fixed length. For example, a person's name, having a variable length, could be hashed to a single integer. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.

and when you search for a permutation you find:

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order.

Interestingly none of the pages mention the other term when you quick-search for it.

As I understand it, a hash function will map a universe of preimages into a fixed set of outputs (fixed because they have a fixed length, therefore the group is finite) where a permutation will rearrange the input producing something of arbitrary length.

How fair is it to say that a hash is a limited permutation or that a permutation is an unbounded hash? I ask this because I haven't seen the comparison between the two anywhere so far and from my understanding, a permutation is more of a theoretical concept while a hash is more of a practical one.

-

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:

1. no two inputs are mapped to the same output: $f(x) = f(y) \implies x = y$, and
2. some input is mapped to every output: for all $y \in S$ there exists $x \in S$ such that $f(x) = y$.

For finite sets $S$, these two conditions are in fact equivalent: either one implies the other. This is easy to see using a counting argument: since the number of possible inputs equals the number of possible outputs, if any two inputs are mapped to the same output, there must be at least one output which is left without any corresponding input, and vice versa.

(In fact, some mathematicians prefer to reserve the word "permutation" only for the case where the domain is finite, and use the word "bijection" for the more general case described above; others treat the two words as more or less synonymous. Also, in some branches of mathematics, a permutation of an $n$-element set $S$ is commonly defined as a function from the set $\{1, 2, \dotsc, n\}$ to $S$, rather than from $S$ to $S$. However, these variations in usage don't really make any significant difference for most purposes, certainly not in cryptography.)

A useful mathematical property of permutations is that they are uniquely invertible: that is, given a permutation $f: S \to S$, there exists a unique permutation $g: S \to S$ such that $g(f(x)) = x$ for all $x \in S$.

The number of different permutations of an $n$-element set $S$ — that is, functions $f: S \to S$ which satisfy the definition above — is $k! = 1 \times 2 \times 3 \times \dotsb \times n$. A random permutation of a set $S$ is simply a function chosen uniformly at random from the set of these $n!$ possible permutations of $S$.

For cryptography, the significance of random permutations is that they are ideal ciphers for messages in the set $S$: the invertibility means that a message encrypted using the permutation $f$ can be decrypted using the corresponding inverse permutation $g$, and if $f$ is chosen randomly from the set of all permutations of $S$, the encryption $y = f(x)$ of any given message $x \in S$ will also be uniformly random, and thus provides no information about the original message $x$ to anyone who does not know $f$.

For small sets $S$, it's possible to examine all the possible permutations of $S$ one by one, but as the size of the set grows, the number of possible permutations quickly becomes truly enormous, and it becomes meaningful to speak of pseudorandom permutations. These are functions chosen from some smaller (but still very large) subset of the full set of permutations of $S$, but in such a way that there is (hopefully) no way for anyone to efficiently distinguish a permutation randomly chosen from the subset from a truly random permutation chosen from the full set of permutations of $S$.

A common type of pseudorandom permutations in cryptography are block ciphers. These are permutations of $b$-bit bitstrings, for some fixed number $b$, where the mapping of inputs to output is determined in some complicated way by a $k$-bit bitstring called the key. (Block ciphers are normally also constructed in such a way that the inverse permutation can also be easily computed based on the key.)

Typical values for $b$ and $k$ might be, say, 128 bits each. Now, clearly, the number of possible keys, $2^{128}$ (which generally equals the number of distinct permutations achievable using a given cipher algorithm, assuming that the cipher has no equivalent keys) is a vanishingly small fraction of the total number $(2^{128})! \approx 2^{2^{133}} \approx 2^{1.3 \times 10^{40}}$ of possible permutations of 128-bit bitstrings. However, it's still a huge number: if we had a billion ($10^9$) computers, each running at 1 THz with one instruction per cycle, it would still take 10 billion years for these computers just to execute $2^{128}$ instructions. Thus, it's completely impossible to tell if a permutation is chosen from a $2^{128}$-element subset or from the full set of $(2^{128})!$ permutations of $128$-bit bitstrings just by comparing it with each of the permutations in the subset in turn; and we hope that, for modern block ciphers like AES, there is also no other, significantly more efficient way to distinguish them from a random permutation than such a "brute force" attack.

OK, so that's what a permutation is and how they're used in cryptography. What about hashes? A hash function is a map from the infinite set of all bitstrings of any length to the finite set of bitstrings of length $b$ for some fixed number $b$. Thus, a hash cannot be a permutation (in any sense of the word): the set of possible inputs of a hash is strictly larger than the set of possible outputs, and thus it must map multiple inputs (in fact, infinitely many of them) to the same output.

In particular, this means that a hash function cannot be invertible, since, at least for some outputs, there's no way to tell which of the many possible equivalent inputs produced that output. Even if we restrict the inputs to bitstrings of some constant length $\ell$, this holds whenever $\ell > b$ (and is likely to hold even for somewhat shorter inputs).

Hashes are closely related to message authentication codes (MACs), which can, in some ways, be viewed as families of hash functions, where the choice of the specific function from the family is determined by some secret key — just like a block cipher is a family of permutations, from which one permutation of chosen by a key. In this sense, secure MACs can be seen as pseudorandom functions, which resemble truly randomly chosen functions from their respective input set to their output set in the same way as pseudorandom permutations resemble truly random permutations.

(Actually, the usual definition of a secure MAC doesn't really require complete pseudorandomness, but merely "unforgeability". However, any pseudorandom function from the set of all bitstrings to a set of fixed-length ones does satisfy the definition of a secure MAC, even if not all MACs are necessarily pseudorandom functions.)

However, what we normally require from cryptographic hash functions is both something more and something less than pseudorandomness. This is because hash functions differ from MACs in that they have no secret key, and so anyone can calculate the same hash for a given input equally well. In particular, this means that it's trivially easy to distinguish any given hash from a random function just by comparing the outputs to those of a known instance of the same hash function.

Instead, what we typically require from cryptographic hash functions is resistance to collision and preimage attacks. That is, even an attacker who knows how the hash function is calculated, and can calculate the hash for any input they want, should be practically unable to either:

• find an input that hashes to a given output value (first preimage resistance),
• find another input that hashes to the same output as a given input (second preimage resistance), or
• find any two inputs that hash to the same output (collision resistance).

So, no, a hash is never a permutation — and, other than that, the two concepts really don't have much to do with each other at all.

-
Your analysis is certainly extensive and detailed, but I must object to the statement that a "hash cannot be a permutation". Generally speaking you are correct, but given appropriate constraints a hash can be a permutation. Consider, for example, a hash function H(x) that one-to-one maps from every possible 16-bit integer to some other 16-bit integer by reversing the bits of the input (or, alternatively, XORs the incoming integer with the 16-bit value 0x029A). –  Nik Bougalis Mar 22 '13 at 20:24
@Nik: While there are various definitions of what constitutes a hash function, I don't think your example would qualify under most of them. Certainly it's not a hash function in the sense we usually use in cryptography. Still, you do have a point: if we restrict our hash to a set of inputs equal to its set of possible outputs, the thus restricted function could be a permutation. Most cryptographic hashes still won't be, though. –  Ilmari Karonen Mar 22 '13 at 21:26
Right - I agree with both your points: it's not a hash function in the cryptographic sense, and cryptographic hash functions aren't just be mere permutations of the input. –  Nik Bougalis Mar 22 '13 at 21:50

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 restrictions on keeping the output the same size as the input. In fact, it usually won't be the same size. There is also no requirement to use only characters that appear in the input.

A hash might sometimes look like a permutation, but I would treat them as separate concepts.

-
Right, a permutation will permute it's input and give you back something that is exactly the same length and has exactly the same elements as the input - just jumbled up. A hash function is a compression function - it takes something of arbitrary length and squeezes it down (or stretches it up) to a fixed length. Nothing stops you from treating a permutation as a hash function if you want to map fixed sized inputs to the same size output, but a permutation and a hash are different things. –  Nik Bougalis Mar 22 '13 at 5:02
@NikBougalis that does it. Please repost your comment as an answer so I can accept it. –  rath Mar 22 '13 at 5:20
@rath - Thanks, but that's alright. I think that my comment nicely supplements Oleksi's existing answer and works better in this context than as a standalone answer. –  Nik Bougalis Mar 22 '13 at 17:22

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]{\rightarrow}[0..31]$ that is used to construct a function $P:[0,1]^{32}{\rightarrow}[0,1]^{32}$, such that $P(b_0b_1...b_{31}) = b_{\sigma(0)}b_{\sigma(1)}...b_{\sigma(31)}$.

A note on terminology: Both the function $\sigma$ and the function $P$ above are permutations, since both are bijective functions. It is however important to note that permutations don't have to be on the same form as $P$, i.e. permutations don't necessarily have to have a set of string element indicies as their domain. Permutations can have any domain.

In cryptography you might also encounter the term Pseudo Random Permutation (PRP), where "Permutation" basically just means a bijective function. The term PRP is sometimes used in contrast to the term Pseudo Random Function (PRF), which is a function that is not necessarily (and probably not) bijective. For instance, a keyed hash might be a PRF, while a block cipher primitive might be a PRP.

-

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

-