Idea for a slow block cipher with adjustable block length
Antti Louko
There is a need for a reversible mapping function eg. block cipher.
In this appliacation the mappings are done infrequently, so the speed
is not an issue. Instead, it would be nice to have an implementation
in pure Perl or Python. And relatively time consuming algorithm might
be a bonus in this case. Key length should be adjustable as well.
Does the following idea have serious problems in your opionion?
Construct a Feistel structure where left and right part are of equal
length (as normally) and half of the length of the block. Lets have
about 20 rounds to be safe. The function F might be truncated SHA-1
of round number, key string and right half. SHA-1 makes the cipher
quite slow but it doesn't harm in this case.
If you think that SHA-1 is overkill, what would be a suitable
alternative?
I think this could be used to implement usable mappings with
relatively short block lengths (24 bits). After all, this cipher is
not intended to be used in any other mode that pure ECB.
Paul Rubin
> Construct a Feistel structure where left and right part are of equal
> length (as normally) and half of the length of the block. Lets have
> about 20 rounds to be safe. The function F might be truncated SHA-1
> of round number, key string and right half. SHA-1 makes the cipher
> quite slow but it doesn't harm in this case.
This is fine and I've done things like it in Python several times.
You only need 4 rounds, not 20, if the F function is pseudorandom like
SHA-1 (approximately) is.
> I think this could be used to implement usable mappings with
> relatively short block lengths (24 bits). After all, this cipher is
> not intended to be used in any other mode that pure ECB.
Such short block lengths are subject to codebook attacks.
Antti Louko
> Antti Louko <a...@iki.fi.invalid> writes:
> This is fine and I've done things like it in Python several times.
> You only need 4 rounds, not 20, if the F function is pseudorandom like
> SHA-1 (approximately) is.
Thank you.
> > I think this could be used to implement usable mappings with
> > relatively short block lengths (24 bits). After all, this cipher is
> > not intended to be used in any other mode that pure ECB.
> Such short block lengths are subject to codebook attacks.
In this case the only requirement is that if any number of mappings
are revealed, this doesn't make arbitrary reverse (or direct) mappings
easy to find.
In practice the weaker parts are going to be elsewhere in the system.
If I will get permission, I will describe later what my friend is
trying to accomplish.
Paul Rubin
> In this case the only requirement is that if any number of mappings
> are revealed, this doesn't make arbitrary reverse (or direct) mappings
> easy to find.
OK. Note if you use a pseudorandom function as F, with such a small
block size (24 bits), you can get birthday collisions, which can make
their way to the output, so you may want to add a couple more rounds.
There have been some old sci.crypt threads about this but I don't
think it's really been analyzed much, since such small block sizes
are generally considered insecure to begin with.
The Feistel cipher you're describing is called the Luby-Rackoff
construction, by the way.
Gregory G Rose
Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>Antti Louko <a...@iki.fi.invalid> writes:
>> In this case the only requirement is that if any number of mappings
>> are revealed, this doesn't make arbitrary reverse (or direct) mappings
>> easy to find.
>
>OK. Note if you use a pseudorandom function as F, with such a small
>block size (24 bits), you can get birthday collisions, which can make
>their way to the output, so you may want to add a couple more rounds.
>There have been some old sci.crypt threads about this but I don't
>think it's really been analyzed much, since such small block sizes
>are generally considered insecure to begin with.
There was a paper at one of the major conferences
in the last 18 months or so... ummm... Oh, how
embarrasing, it was the one I ran! Anyway, Jacques
Patarin, "Luby Rackoff: 7 rounds are enough ...",
Crypto 2003. If I'm remembering the result
correctly, 6 rounds is enough for non-adaptive
attacks and 7 for adaptive attacks. The original
Luby-Rackov proofs were for four rounds, but
subject to birthday attacks, so the security
provided was lower. See also Zully Ramzan's work.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
Antti Louko
>Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> >OK. Note if you use a pseudorandom function as F, with such a small
> >block size (24 bits), you can get birthday collisions, which can make
> >their way to the output, so you may want to add a couple more rounds.
> >There have been some old sci.crypt threads about this but I don't
> >think it's really been analyzed much, since such small block sizes
> >are generally considered insecure to begin with.
The use I have in mind is to map Ethernet (MAC) addresses (which are
48 bit) or the last 24 bits of that into device serial numbers in a
way that doesn't need keeping database but which doesn't immediately
reveal MAC address / serial number relation to anyone not knowing the
key.
> There was a paper at one of the major conferences
> in the last 18 months or so... ummm... Oh, how
> embarrasing, it was the one I ran! Anyway, Jacques
> Patarin, "Luby Rackoff: 7 rounds are enough ...",
> Crypto 2003. If I'm remembering the result
> correctly, 6 rounds is enough for non-adaptive
> attacks and 7 for adaptive attacks. The original
> Luby-Rackov proofs were for four rounds, but
> subject to birthday attacks, so the security
> provided was lower. See also Zully Ramzan's work.
Thank you for your feedback, Paul and Gregory. The result is now at
<URL:http://www.louko.com/alo/feistel-0.3.py>. After a while (a month
at most), I will put the code under GPL or BSD license. Most of you
are probably brave enough to use it now, because it is actually quite
silly to claim copyright for such a simple piece of code.
The paper you mention by Patarin is not freely available anywhere, I
suppose. It would be of course nice to add a link to the paper to the
comments in the code if the paper is reachable somewhere.
Gregory G Rose
It's available online but only if you subscribe to
Springer's Link service, which is very expensive.
If it was me, I'd just put in a reference to the
Crypto paper. It isn't *that* hard to get to. You
should be able to get it from a library, for
example. To check the paper itself, you could
probably write to Jacques (see
www.prism.uvsq.fr/administration/personnel/jap_fr.html),
I imagine he'd send you a copy.
Antti Louko
> The result is now at
> <URL:http://www.louko.com/alo/feistel-0.3.py>.
There was a bug in the F function calculation. So please use the
newer version <URL:http://www.louko.com/alo/feistel-0.4.py>.
I also added another kind of algorithm where the permutation is not
in [0 .. n^2-1] but in [0 .. m*m-1]. The XOR is replaced with
addition or subtraction and the binary and by mod function.
This could be useful in mapping decimal serial numbers if one wants to
keep the number space in range 0..99, 0..9999 etc.
Paul Rubin
> There was a bug in the F function calculation. So please use the
> newer version <URL:http://www.louko.com/alo/feistel-0.4.py>.
>
> I also added another kind of algorithm where the permutation is not
> in [0 .. n^2-1] but in [0 .. m*m-1]. The XOR is replaced with
> addition or subtraction and the binary and by mod function.
Why is it so important for your application that the cipher output
be the same length as the input? If you can store 64 bits instead
of 24, then just use 3DES or something.