Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
Does it need to be a way that one could imagine being implemented mechanically? $\hspace{1.63 in}$ –  Ricky Demer Feb 20 at 3:05
    
@RickyDemer: No (even though I would be interested in knowing how this could be done as well). –  Thomas Feb 20 at 3:07
2  
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 at 7:23
1  
@fgrieu: I think you should make that into an answer :) –  figlesquidge Feb 20 at 23:10
add comment

3 Answers

up vote 5 down vote accepted
+50

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$
share|improve this answer
    
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 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 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 at 10:43
1  
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 at 10:59
add comment

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.

share|improve this answer
    
Thank you for the answer. Would you elaborate a bit more? (I am not very familiar with cryptography.) –  Thomas Feb 21 at 2:25
add comment

This was covered on scicomp (http://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

share|improve this answer
    
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 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 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 at 18:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.