Are there any "good" ways to get a permutation from a password/pass-phrase?

If one, for example, wanted to get a permutation of letters from a password, how might one do that in a smart way? I would be interested in a way that from one password word would generate a given number, for example 7, permutations for use in an Enigma machine.

I understand that if the password is password one could simply make the alphabet

paswordbcefghijklmnqtuvxyz so that the permutation would send a to p to w to o to etc.

But this doesn't seem like a very smart choice. It would obviously be nice if the permutation generated is very different for two very similar passwords.

What are better ways of doing this?

Edit: This does not need to be implementable mechanically.

• Does it need to be a way that one could imagine being implemented mechanically? $\hspace{1.63 in}$ – user991 Feb 20 '14 at 3:05
• @RickyDemer: No (even though I would be interested in knowing how this could be done as well). – Thomas Feb 20 '14 at 3:07
• Break the problem in two: generate a pseudo-random value from a password, using a password-based key derivation/stretching function; then generate a permutation from that using techniques of format-preserving encryption. – fgrieu Feb 20 '14 at 7:23
• @fgrieu: I think you should make that into an answer :) – Cryptographeur Feb 20 '14 at 23:10

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$ assigns a permutation over $L$, where $k \gt log_2(|L|!)$. For instance, $f(s) = g(BS2I(s) \bmod n!)$ and

function g
Input: Large integer
Output: array [L] of L
x := Input;
for i := 0 to (n-1) do
z[i] := i;
for i := n downto 1 do
begin
t := x mod i;
x := x div i;
y[n-i] := z[t];
for j := t+1 to i-1 do
z[j-1] := z[j];
end;
for a in L do
Output[a] := I2E(y[E2I(a)]);


will work, provided that $2^k$ is sufficiently much larger than $n!$ to make the bias insignificant. Note: Surjectivity follows from the observation that each $x$ in the range $0..n-1$ will result in a unique sequence of $t$ values. At each step, a change in $t$ will result in a different value from the remaining $z$ values being picked. The algorithm closely follows the conventional proof that the number of permutations of $n$ elements equals $n!$.

However, as pointed out by fgrieu in a comment below, a more efficient algorithm is:

function g
Input: Large integer
Output: array [L] of L
x := Input;
for i := 1 to n do
begin
t := x mod i;
x := x div i;
y[i-1] := i-1;
y[i-1] := y[t];
y[t] := i-1;
end;
for a in L do
Output[a] := I2E(y[E2I(a)]);


The second algorithm will also output unique permutations for $x \in \{0..n-1\}$. Informally, this is because each permutation of $n$ elements might be expressed as a sequence of at most $n$ pairwise substitutions. This algorithms happens to result in sequences of $n$ such pairwise substitutions that are guaranteed to result in unique permutations.

To ensure that two related input passwords will not map to two related permutations, you first pass the password through a PBKDF (as suggested by fgrieu in a comment) before applying $f$. If $|L| = 26$ then $k = 256$ will be sufficient (because $log_2(26!) \lt 89$ the bias of $f$ will be significantly less than $2^{-128}$).

Hence:

1. Pass the input password $p$ through a PBKDF to produce a bit string $s$ of bit length $256$.
2. Convert $s$ to a 256 bit integer $x$ using a standard $BS2I$ function.
3. Map $x$ to a permutation over the 26 element alphabet $L$ using function $g$
• What about replacing the first three loops (including one nested) with for i := 1 to n do begin t := x mod i; x := x div i; y[i-1] = i-1; y[i-1] = y[t]; y[t] = i-1; end; ? Also: a slow PBKDF is a must to make it hard to find the whole permutation from the image of a few elements (like half as much as there are letters in the password, for a typical choice of password). – fgrieu Feb 24 '14 at 8:27
• @fgrieu: Yes, that would be a more efficient algorithm. It requires a deeper understanding of permutation composition for the reader to deduce surjectivity, though, but it should be added to my answer. – Henrick Hellström Feb 24 '14 at 10:17
• @fgrieu: I am afraid using a slow PBKDF will not matter much unless a salt is used as well. If no salt is used, slowing the PBKDF down will just slow down the precomputations (generation of permutations corresponding to common passwords). – Henrick Hellström Feb 24 '14 at 10:43
• I find the new algorithm easier to grasp and prove: we start from one of the $(i-1)!$ permutations of $i-1$ elements $j\mapsto F(j)$ for $0\le j<i-1$; and a $t$ with $0\le t<i$. Then make a new function of $i$ elements defined by: $G(j)=F(j)$ for $0\le j<i-1$ with $j\ne t$; $G(t)=i-1$; $G(i-1)=t$. Each $(F,t)$ yields a distinct permutation $G$. Proof that we reach each of the $n!$ permutations of $n$ elements when $0\le x<n!$ follows by induction. You made a good point by noticing that a slow PBKDF only slows precomputation, unless there's a previously unknown salt. – fgrieu Feb 24 '14 at 10:59

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.

• Thank you for the answer. Would you elaborate a bit more? (I am not very familiar with cryptography.) – Thomas Feb 21 '14 at 2:25

This was covered on scicomp (https://scicomp.stackexchange.com/questions/4923/random-access-random-permutations), but I'll copy the answer here (not sure if that's appropriate but it definitely belongs in both places). You are looking for

1. Black and Rogaway, Ciphers with Arbitrary Finite Domains, 2001.
2. http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers

Summary: Pick $2^k$ slightly larger than $n$, generate a block cypher $f \in S_{2^k}$ operating on $k$ bit blocks, and construct a permutation on $[0,n)$ by walking along cycles of $f$ until we get back in the desired range. Specifically, given $x < n$ we set $$g(x) = f^p(x) = f(f(f(...x...)))$$ where $p$ is the least positive integer s.t. $f^p(x) < n$.

If $2^k = O(n)$, and the block cypher is good, the walk takes $O(1)$ expected time. Note that $p$ is necessarily finite, since eventually we will walk back around the cycle and find $f^p(x) = x$.

Here is a (likely very weak, so sufficient only for noncryptographic purposes) example implementation using a truncated TEA block cypher as described in (2):

https://github.com/otherlab/core/blob/f09fbd19dbaa7b9033eb0888594273a6a3d592a5/random/permute.cpp

• This answer is not very practical for small $n$, like $n=26$ in the question. Also it does not tell how we go from password to key of the block cipher, and that's NOT trivial. – fgrieu Feb 24 '14 at 7:33
• I agree about the small $n$, but going from the password to the key is easy: just run the password through a strong cryptographic hash. If the cipher isn't strong enough then, it won't ever be strong enough. – Geoffrey Irving Feb 24 '14 at 17:47
• This way of going from password to key is suboptimal, in particular makes it easier than necessary to deduce the whole permutation from part of it by enumerating likely passwords. A better solution uses key stretching. – fgrieu Feb 24 '14 at 18:56

A while ago, I spent time playing with modern field ciphers, especially with Card-Chameleon. Card-Chameleon uses a 52 card deck, assigning a letter to each red and each black card and needs two separate full alphabet permutations as a key. As it's a field I tried to find a computer-less, math-less, way to generate permutations from passwords.

My solution is a three steps process.

Let's assume the current password is PASSWORD

# Step 1 : Create a base permutation

Write down the letters of the password without repetition

P A S W O R D

Fill in a matrix under the written down password with the remaining letters, leaving spaces for letters already present in the password

P A S W O R D
B C   E F G
H I J K L M N
Q     T U
V   X Y Z


Read the matrix column by column ignoring the spaces to get a base permutation

base permutation : P H V A B I S C J Q X W K Y O E L Z R F M T D G N U

It looks nice but related passwords (eg. PASSWORD, PASWWORD, PASSWORDS, PASSWORDA, PAASSWORD, ...) will produce the very same base permutation. So I needed to do something more to the base permutation, something which takes into account the whole password

# Step 2 : Create a sequence of values based on the whole password

Assign to each letter a value equal to its rank in the alphabet minus 1

A B C D E F G ...  Y  Z
0 1 2 3 4 5 6 ... 24 25


Convert this rank to base 3, using 3 digits for each letter

 A   B   C   D   E   F   G  ...  Y   Z
000 001 002 010 011 012 020 ... 220 221


Write down the base 3 digits corresponding to the password

 P   A   S   S   W   O   R   D
120 000 200 200 211 112 122 010


Group these digits by 2 instead of 3 (if the password has an odd number of letters, append 0 to the base 3 digits of the last character of the password to be able to make pairs)

12 00 00 20 02 00 21 11 12 12 20 10


Convert the resulting pairs back to base 10

5  0  0  6  2  0  7  4  5  5  6  3


6  1  1  7  3  1  8  5  6  6  7  4


resulting sequence: 6 1 1 7 3 1 8 5 6 6 7 4

# Step 3 : mix up the base permutation using the sequence just created.

Taking advantage of having a card deck handy, setup a 26 cards deck (using red cards or black cards as you wish), order these 26 cards in the order of the base permutation, face up (remember, each card is assigned a letter, eg. $1\diamondsuit$=A, $2\diamondsuit$=B, $...$, $Q\diamondsuit$=L, $K\diamondsuit$=M, $1\heartsuit$=N, $2\heartsuit$=O, $...$, $Q\heartsuit$=Y, $K\heartsuit$=Z).

P H V A B I S C J Q X W K Y O E L Z R F M T D G N U

For each value of the resulting sequence of step 2, deal that many cards, face up, one at a time, to make a pile in reverse order (You may create the pile on the table or better, in your other hand. The only important thing is that the cards must be face up and be in reverse order). Then, put the resulting pile under the remaining cards of the deck. Repeat until the sequence is exhausted.

### first round

pile: I B A V H P
remainder of the deck: S C J Q X W K Y O E L Z R F M T D G N U
new deck: S C J Q X W K Y O E L Z R F M T D G N U I B A V H P

# Experimental results

The final permutations for the related passwords quoted in step 1 are:

PASSWORD    V A B W K Y O C S E L Z J Q X T D G N U I R H P F M
PASWWORD    C S P Z J Q X W K F M T D E L U I B A V H R O Y G N
PASSWORDS   S E L Z J Q X T D G N U I R H P F M O Y K W B A V C
PASSWORDA   B W K Y O C S E L Z J Q X T D G N U I R H P F M V A
PAASSWORD   G S P H V A R F K Q X W J C B M T D Y O E L Z U I N