Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:05
John Kelsey (kelsey@plnet.net)
Sat, 23 Jan 1999 00:18:40 -0600
-----BEGIN PGP SIGNED MESSAGE-----
[ To: Greg Rose ## CC: CodherPlunks ## Date: 01/22/99 ##
Subject: Re: Short blocksize ciphers ]
>Date: Sat, 09 Jan 1999 06:16:26 +1000
>To: bram <bram@gawth.com>, Greg Rose <ggr@qualcomm.com>
>From: Greg Rose <ggr@qualcomm.com>
>Subject: Re: Short blocksize ciphers
>Cc: CodherPlunks@toad.com
>X-UIDL: 396b65efe04e01f5dce74bd04d49a949
>At 11:25 8/01/99 -0800, bram wrote:
>On Fri, 8 Jan 1999, Greg Rose wrote:
>> I'm looking for any existing block ciphers with short (2
>> and 4 byte) block sizes. ISTR something going past me a few
>> months ago on this subject, but can't remember where it
>> was.
>At that point, why not just use a dictionary?
>Thank you for this keen and insighful comment. My first
>reaction was "I've thought about dictionary attacks" (which
>I had and they are inapplicable to my intended application
>(which I can't say more about)), but my worldview was
>shifted by this comment. Of course! For 256K bytes of
>memory, I can create a 16-bit key dependent permutation
>table.
>(For 16 gigabytes I could do a 32-bit one, but I don't think
>that would be useful. It isn't clear that we could afford
>the 256K for this application either... but maybe.)
Have you looked at the construction used in Skipjack?
If you have a fixed 8 bit wide table, you can use it to
build a 16 bit wide keyed permutation like
x[0] = x[0] XOR s[x[1] XOR sk[0]]
x[1] = x[1] XOR s[x[0] XOR sk[1]]
x[0] = x[0] XOR s[x[1] XOR sk[0]]
x[1] = x[1] XOR s[x[0] XOR sk[1]]
where x[0,1] and sk[0,1] are bytes and s[] is a fixed byte
permutation.
The nice thing about this is that you don't have to store a
16 bit wide table. In fact, you can have many of these
16 bit wide permutations, as Skipjack does. If you have a
16 bit wide permutation, you can use this construction to
build key-dependent 32 bit wide permutations. You can even
use this construction to recursively build very large block
ciphers, though I am not sure what weird security properties
you get as a result. Matsui's Misty design is based on a
recursive construction of that kind, I believe.
Anyway, the number of ``rounds'' of the construction you
need are determined by your requirements. If we just need
to have the permutation be selected from 2^{8 N} possible
permutations, when x[0,1] are bytes, we do N rounds. If we
need both bytes of output from the permutation to be
affected by all 2^{8 N} possible permutation choices, we
need N+2 rounds.
If we need to resist attacks where someone can get a
relatively small number of plaintext/ciphertext pairs, we
more-or-less need to double the number of rounds, to deal
with meet-in-the-middle attacks. That is, to get 8 N bits
of security, we need 2 N rounds. I think we may need to
extend this to 2 N + 2 rounds to deal with with a more
clever version of meet-in-the-middle attack, when the
attacker gets to choose inputs.
Resistance to differential and linear attacks will be based
on the properties of the S-box with respect to those
attacks. Since the S-box is bijective, the iterative
differential and linear characteristics with the fewest
active rounds will cover six rounds and have four active
rounds. There may be other ways to attack this that are
more specific to the S-box chosen, e.g., if the S-box always
maps low hamming-weight values to low hamming-weight values
or something.
>Greg.
>Greg Rose INTERNET:
ggr@Qualcomm.com
>Qualcomm Australia VOICE: +61-2-9181-4851 FAX:
+61-2-9181-5470
>Suite 410, Birkenhead Point,
http://people.qualcomm.com/ggr/
>Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081
A37C
Comments? Is this at all helpful?
- --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
iQCVAwUBNqlpkSZv+/Ry/LrBAQFxHgQAvBJebjqtmC251cQe4OfV8J4w4FJMTSch
SrwD7G/tq0j2D13WnBeDilG/bifUf4xK5E3bXknzZ349KYp/xZu2RZn01lWeLhJ8
Uvqp9aGJIvyY4v3IR0vDTVRZMC5/8UbP5IrwZGSdIGhPFE2LcqNqOeqRi1IHtfgT
uUiEquC850s=
=HlUS
-----END PGP SIGNATURE-----
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:05