Optimisation Considered Harmful

[Jerrold Leichter]

| >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....
| 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....
thus bringing us back to an observation that goes back maybe 30 years:  Timing
channels are usually impractical to eliminate, but you can lower the bit rate
(or decrease the S/N ratio, which comes down to the same thing).  For the case
at hand, we've lowered the bit rate by a factor of 20.

If you're willing to change the protocol a bit, you can do better:  Never send
a block whose encryption crossed the boundary.  Instead, send a special "ignore
me" block.  (Obviously, the "ignore me" marker is *inside* the encrypted
envelope.)  Depending on the nature of the protocol - is the size of a response
invarient, or is the number of exchanges invarient? - you then continue either
by sending the real block, or by the sender returning an "ignore me" block
which you "reply to" with the encrypted block that crossed the boundary.  This
still doesn't completely remove the timing channel - there are differences in
the data stream depending on whether you cross the boundary - but they are
much subtler, so again you've decreased the bit rate.  (It's not clear how to
quantify in this case, though.)

							-- Jerry

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