Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

[Timothy Miller (miller@techsource.com)]

Ingo Molnar wrote:

> i'd suggest to use the jhash for the following additional kernel entities:  
> pagecache hash, inode hash, vcache hash.
>
> the buffer-cache hash and the pidhash should be hard (impossible?) to
> attack locally.


Maybe this is what someone is saying, and I just missed it, but...

Coming late into this discussion (once again), I am making some 
assumptions here.  A while back, someone came up with a method for 
breaking encryption (narrowing the brute force computations) by 
determining how long it took a given host to compute encryption keys or 
hashes or something.

If you have a situation where a lot of hashes are to be computed, and 
you want to decouple the computation time from the response time, then 
do this:

1) A kernel thread requests a hash to be computed.  That hash is 
computed and put into a queue.  The kernel thread is put into the task 
queue.
2) Other kernel threads do the same.
3) Threads get woken up only when their hash is pulled off the queue.


This way, the only added overhead is kernel context switch from one 
thread to another.  The algorithm doesn't waste CPU time trying to hide 
the complexity of the computation, because the time between request and 
receipt of a hash is dependent on whatever other random hashed are also 
being computed.  That is, receipt is much later than request, but you 
haven't wasted time.

The only case where this doesn't deal with the problem in a low-cost way 
is when the queue starts out empty when you make a request, and then 
it's the only one on the queue when it's pulled off.  In that case, you 
do have to waste time.  However, given that the kernel thread will go to 
sleep anyhow, the time between sleeping and waking up is somewhat random 
due to whatever other kernel and user threads might get executed in the 
mean time.

In fact, one solution to this problem would be for the hash computing 
function to just yield the CPU before or after the computation of the 
hash.  Even in a system with absolutely no other load, the fact that we 
have to go into and out of the scheduler will add some randomness to the 
computation time, perhaps.

Have I just completely left the topic here?  :)

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/