Get permutations from password

Question

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.

Answer 1

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$

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

Answer 3

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

Answer 4

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

Add 1 to each value

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