Re: "Small" problem

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 08/15/03 

Date: 15 Aug 2003 12:55:14 -0700

[I'm replying to both Alex's and Mike's posts,
having never received Mike's.]

In article <W7a%a.732212$ro6.15056543@news2.calgary.shaw.ca>,
Alex Flanagan <spiffy43@hotmail.com> wrote:
>Mike Amling wrote:
>> Greg Rose wrote:
>[snip]
>> > A fake sender can send a state that will be
>> > accepted as valid with probability about 2^-18,
>> > although he won't know what state he sent.
>> >
>> > There's also a probability of about 2^-19 that
>> > you'll get the wrong state at the remote machine.
>>
>> You mean if two states for the same date hashed to the same value,
>> and the wrong one is found first by the 0..255 loop?

Yes, exactly.

>> You can avoid this possibility by choosing a k for which it doesn't
>> happen. 2**18 messages have to be checked to make sure than no two
>> states for a given date produce the same hash. It should take only a few
>> seconds on a PC to vet a given k.

Not really; that will be true for any given
*date*, but you won't be able to choose such a k
that will work for arbitrary dates.

>> Nevertheless, I think your Luby-Rackov idea is better.

Agree; I don't know why I thought of the other one
first.

>> Of course, all of these schemes are subject to replay attack.

Only sort-of; the date defines the window of
vulnerability to replay; it automatically forms a
kind of "freshness".

>I wondered how vetting keys like this limits the keyspace, so I figured it
>out.
>
>My reasoning is that the original block cypher has 2^26 possible keys. From

That's a common misconception. There's nothing
stopping the keyspace being significantly larger
than the block size. Remember that the b-bit block
cipher effectively defines a codebook, that is a
permutation of the 2^b possible inputs. There are
(2^b)! such permutations. This is a huge number,
even for 26-bit blocks; you could have a 1000-bit
key and still not get a significant fraction of
the possible different b-bit block ciphers.

>above, there is approximately a 2^-19 chance for each key that it would be
>vetted out. So:
>
>2^26 * 2^-19 = 2^7 = 128 keys would be vetted out.
>
>Losing 128 keys from the keyspace sounds pretty insignificant, and my
>(completely undeveloped) intuition says that it doesn't substantially affect
>the cypher's security.

Of course, I got to here before I realised you
were referring to the hash-based scheme. The same
thing is true, although the number of possible
distinct output functions is now ((2^b)^(2^b)) (I
think), not (2^b)!, and is even bigger, so the
keys could be b*2^b bits in length (ie. huge).

So, what you've written generalizes down to the
fact that a constant *proportion* of keys will be
vetted out, where the proportion is one in
(2^blocksize)/(2^statesize)/2.

>Like I said, I'm just getting into cryptology, so forgive me if I'm far, far
>out of my depth :)

Not at all... a good question.

Greg. 

-- 
Greg Rose                                       INTERNET: ggr@qualcomm.com
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/ 
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

Relevant Pages

  • Re: AES 256 key and anti-key
    ... For any actually file regardless of length not sure how many keys ... only allowing a single cycle is also bad for the way its used.. ... have there characteristics I don;t know how you know that AES has ... key is supposed to select a block permutation pseudo-randomly. ...
    (sci.crypt)
  • Re: AES 256 key and anti-key
    ... So there are much more permutations than keys. ... mapping of the character set of 128 bit characters to a permutation of ... permutation, then the probability that a two ... ZERO chance of two keys producing the same permutation. ...
    (sci.crypt)
  • Re: AES 256 key and anti-key
    ... So there are much more permutations than keys. ... permutation of that set. ... Fact is pseudo-random means its not a random permutation ... Are they single cycle or what is the cycle structure of the ...
    (sci.crypt)
  • Re: commuting?/non-group cipher?
    ... the property that a double encryption under two keys is ... I can only think of three ciphers which have the property - Caesar, ... permutations ...
    (sci.crypt)
  • Re: commuting?/non-group cipher?
    ... the property that a double encryption under two keys is ... I can only think of three ciphers which have the property - Caesar, ... permutations ...
    (sci.math)