[rc5] Blocks

Eric Gindrup gindrup at okway.okstate.edu
Thu Oct 9 10:46:11 EDT 1997


     It's not clear that the delay will be trivial.  Let's posit a 
     request-only client that requests 5 blocks per second.  Currently, the 
     entire effort is completing ~20 blocks per second.  So this client can 
     tie up 20% of the outstanding keyspace.  So in ~80 days, this client 
     will (putatively) possess 12% of the keyspace and still be requesting 
     blocks.
     Assuming that this malignant client is scaled up to always run ~20% of 
     the effort's rate and that the target block has not already been 
     misreported to not contain the key, then there is a 20% chance that 
     the effort will not find the key on the first pass.  Similarly, there 
     is a 20% chance the effort will not find the key on the second pass.
     
     It'd be nice to say that the amount of time for doing all of this 
     would be the same as if the malignant client were not active, but this 
     is not the case.  At some point, a minimum limit for the amount of 
     time that a client is allowed to work on a block before that block is 
     reassigned has to be set else the entire effort will be working on the 
     same last block.  Before that happens, the expectation will be that 
     the block containing the key was misreported.  Since some lower limit 
     on the time-to-reassign will likely be implemented, the malignant 
     client can (possibly) request the block containing the key (~20%) and 
     make it appear that no block contains the key (because there are no 
     blocks that are neither reported nor assigned).  This will necessitate 
     re-searching the entire keyspace.
     
     As has been pointed out, though, a great deal more interference would 
     result from a client that reported those blocks to not contain the 
     key.  Then, using the above analysis, there's a 20% chance of starting 
     the second pass, a 20% chance of then having to start the third pass, 
     ...  This would be terribly time consuming.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu
     
     


______________________________ Reply Separator _________________________________
Subject: Re: [rc5] Blocks 
Author:  <rc5 at llamas.net > at SMTP
Date:    10/9/97 8:13 AM


On 08 Oct 1997 18:33:24 -0700, Darrell Fuhriman wrote:
     
>Which means that all the 'bogus block' protections are basically 
>moot since one can just sit down and request blocks and never 
>process them.  It may not prevent the key from being found, but 
>it could make it take much longer.
     
No, it won't, or at least the delay will be trivial.  Every block has an equal 
likelihood of containing the key.  It does not matter whether the block has been
assigned once, twice or fifty times, so long as unchecked blocks exist to be 
assigned the chance of each block containing the key is exactly 
1/(#UncheckedBlocks)  no more, no less.  The only additional time is the time 
spent actually assigning the block, a few milliseconds.
     
On the other hand if someone is requesting blocks and then returning them as 
checked, without actually checking them, then this will cause major delays.  But
this is a malicious act.
     
Skip Huffman
Carreker-Antinori
Atlanta Office
Quality Group
"A penny saved may be a penny earned, but it's a waste of
 a deposit slip and it really pisses off the tellers."
     
     
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
body.
     


----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list