[Cryptography] Simple key derivation function based on card shuffling

Jerry Leichter leichter at lrw.com
Fri Jul 23 22:22:50 EDT 2021


> ...The purpose [of this algorithm] is to turn a variable-length key (and usually a nonce) into a fixed-size binary buffer.... [Desired properties include]...
> - The output should be a more uniform bitstring that doesn't have the
> same patterns as the input....
> The state is initialized as an array of alternating `0` and `1` bits.
> The length of the array is twice the number of output bits.
> 
> Every round, the state is split into two halves. One bit is taken from
> the key. If the bit is set, an element from the first, and then the
> second half is appended to the new state. If the bit is 0, the second
> and then the first half is used instead.
> 
> After enough iterations, it is hoped that the state is shuffled
> sufficiently. The output buffer is the first half of the state....
You're iterating a permutation on a fixed input.  In general, that can be a good construction - but your permutation is rather limited.

Suppose the input is standard ASCII, and you read the bits of each byte with most significant bit first.  Then the first bit of the key, and every 8th bit, is always 0.  So in the first round, we will certainly set the first output bit to 0.  But if the output size is a multiple of 8, every time we loop around and look at that bit, we're looking at the top bit of a key byte, and we keep the 0.  So the first bit of the output is 0.  Something similar happens with every 8th bit though it's harder to follow on a quick look.

More fundamentally, if twice the output size and the input size (in bits) share a common divisor, then it looks as if blocks of that size in the output don't interact.

Again, kind of hard to follow, but this seems as if it retains too much structure.

Also, since you're applying the same permutation over and over again, I'd worry about the order of the permutations you're getting.  Could they have an order well below the 2^16 you're specifying, so that you return to the starting state one or more times, making the effective number of repetitions much smaller?

Alternating the permutation passes with substitution passes might help.

Fundamentally, though ... there are plenty of algorithms for this kind of thing that are easily implementable and are likely close to as efficient.  If you want something for serious use, I'd strongly suggest using them.
                                                        -- Jerry



More information about the cryptography mailing list