Optimisation Considered Harmful

[Dan Kaminsky]

>Suppose you have something that is inadvertently an
>oracle - it encrypts stuff from many different users
>preparatory to sending it out over the internet, and
>makes no effort to strongly authenticate a user.
>
>Have it encrypt stuff into a buffer, and on a timer
>event, send out the buffer.
>
>Your code is now of course multithreaded - very easy to
>get multithreading bugs that never show up during
>testing, but non deterministically show up in actual
>use. 
>  
>
The problem is with edges:

Suppose the timer goes off every 10ms.

You have an operation that takes either 5ms or 15ms, depending on
whether a chosen bit of the key is 1 or 0.

Whether or not a given time slot is occupied with results will emit
whether the bit was 1 or 0.

Now, suppose your timer goes off every 200ms.  No problem, right?

At time=190ms, you force an encryption.  If it's done by the time=200ms
deadline, you know.

Things get trickier when there's random noise in the timer, and it
matters whether the distribution of 1's and 0's is equal or not.  But
this is fundamentally a difficult problem to handle.

--Dan


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com