the probability is about 0.06

From: BigWhiteMouse (dengyongze_at_hotmail-dot-com.no-spam.invalid)
Date: 03/28/05 

Date: 28 Mar 2005 03:35:41 -0600

According to David Wagner,

>
> Huh. Let me understand what you've got. Let's say we've got some
> choice of 41-bits for R1, part of R2, and part of R3, where you have

> not been able to find any special inner state (i.e., you haven't
found
> a way to use the process described in Section 5.1 to extend this to
a
> full special state that generates an output starting with \alpha).
>
> Could this be because there is no way to extend those 41-bits into a

> full 64-bit state whose output starts with \alpha?
>

I have written a program in C to implement the process described in
Section 5.1. Using the program, I tested 18657733 41-bits for R1,
part of R2, and part of R3, in which there are 1115189 41-bits that
can not be extended to a full special state. So this kind of 41-bits
will occur with propability 0.06.

Testing one 41-bits will cost 0.55 millisecond for PII 400MHz PC, so
it will take 59727 months for PII 400MHz PC to finish 2^48 special
states sampling! But the biased birthday attack only acquires 2^41
special states sampling.

>
> Do you have an estimate of the fraction of random 48-bit codes that

> run into this difficulty?
>

I have not an estimate of the fraction of random 48-bit codes that
run into this difficulty. But I guess it should be more than 0.1.
Posted at: http://www.groupsrv.com

 Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
    ** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
                http://www.usenet.com

Quantcast