cryptographic ergodic sequence generators?

[Tim Dierks]

At 06:54 PM 9/6/2003, Perry E. Metzger wrote:
>Tim Dierks <tim at dierks.org> writes:
> > I'm sure that it would be possible to design a Feistel-based block
> > cipher with variable block size, supporting some range of even values
> > of n.
>
>Perhaps -- I don't know of a good one.

I'm not a cryptographer, so I can only make a tentative proposal, but I 
believe you could make use of any secure keyed one-way function as the 
function f() in a 2-round Feistel cipher and end up with a secure 
construction. For example, let's use DES.

Let's say we wanted a 16-bit block cipher. Then f() must take a round # and 
a 8-bit input and translate it into an 8-bit output. It doesn't have to be 
a unique or reversible mapping.

Using DES, we could lay out the plaintext block as:
   round # | input
with the round # in the first 32 bits and the input in the last 32 bits 
(padded with zero bits), then encrypt and take the low byte of the output 
as the output of f().

Thus, to encrypt a 16-bit block:
  - Divide it into 2 halves, L0 & R0
  - L1 = R0
  - R1 = L0 ^ DES(1 | R0)
  - L2 = R1
  - R2 = L1 ^ DES(1 | R1)

Output = R2 | L2

This will take two DES operations per iteration, so it's not super-speedy, 
but it's pretty fast for most operations. It's reversible, so you know it 
will generate all values. And the construction works for any even-length 
value of n. If you want, you can probably use a faster function for f(), 
depending on your security requirements.

Here's a simple Perl script I wrote just to make sure I had it right:

use Crypt::DES;

$n = shift @ARGV;
if (!defined($n) || $n < 2 || $n % 2 != 0 || $n > 32 || $#ARGV > 0) {
         die "Usage: $0 n\n2 <= n <= 32 && n even\n";
}

$key = pack("A8", rand());

$cipher = new Crypt::DES $key;

$hn = $n/2;
$fmask = (1 << ($n/2)) - 1;

sub f($$) {
         my ($round, $v) = @_;

         my $pt = pack("LL", $round, $v);
         my $ct = $cipher->encrypt($pt);
         my ($high, $low) = unpack("LL", $ct);
         return $low & $fmask;
}

sub E($) {
         my ($p) = @_;
         my $L = $p >> $hn;
         my $R = $p & $fmask;
         my $round;

         for $round (1..2) {
                 $Ln = $R;
                 $Rn = $L ^ f($r, $R);
                 $L = $Ln;
                 $R = $Rn;
         }

         return ($R << $hn) | $L;
}

foreach $v (0..(1<<$n)-1) {
         $o = E($v);
         print "$v => $o\n";
         if ($o >= 1<<$n) {
                 die "Too big";
         }
         if ($retvals{$o}++) {
                 die "Duplicate";
         }
}

This takes the length of the sequence in bits as a parameter.

This will take a while to run for any value of n much larger than 10 or so, 
but I've tested it for up to n = 16 and it works fine: generates a random 
ordering of the values 0..2^n-1.

  - Tim



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com