[Haskell-cafe] Tor project

[Wojciech Narczyński]

W dniu 2014-08-01 12:26, Tobias Dammers pisze:
> On Fri, Aug 01, 2014 at 12:03:34PM +0200, Wojciech Narczyński wrote:
>> W dniu 2014-08-01 11:56, Tobias Dammers pisze:
>>> On Fri, Aug 01, 2014 at 09:35:37AM +0200, Wojtek Narczyński wrote:
>>>> Why the gimmick, for each and every piece of crypto code? Why not just use
>>>> the clock for timing? The crypto lib would probably have to tune itself on
>>>> startup.
>>> Sorry, I didn't mean use the crypto function to cause the delay; I meant
>>> using a cryptographic hash to determine how long the delay should be.
>>> Once we have a number, the system clock should of course be used to
>>> actually delay things.
>>>
>>>
>> This is poinlessly complicated.
>>
>> Just measure how much each execution takes, remove outliers, take the upper
>> bound, wait appropriate amount of time on each call so that the attacker
>> sees constant time for each call.
>>
> I think you are underestimating the statistical aspect to this. In order
> to do this in a useful way, you'd have to sample your own code on a
> regular basis, for a large number of inputs, and you better get the
> padding exactly right, because if it's off by a tiny amount, that tiny
> amount will remain after averaging. It will basically boil down to a
> sampling war between you and the attacker - if your sampling is really
> good, your error may be really small, but the attacker can counter this
> by sampling more. To make matters worse, you are playing this game
> blindly: you don't know how much sampling is enough, or how much the
> attacker can afford to sample.
I would sample a little during startup to derive a rough upper bound of 
WCET, and then sample randomly during runtime to lower the bound. The 
attacker runs would be sampled opportunistically, too. Okay, this is not 
very simple.
> I also think you are over-estimating the complexity of the crypto-hash
> solution: suitable hashing functions are there for the taking (it
> doesn't even have to be a time-hard function like bcrypt/scrypt/...
> AFAIK, just one that's cryptographically sound), converting a hash into
> a delay value is trivial, and you need to implement a delay mechanism
> anyhow. The most "challenging" part, I think, is managing a secret to
> seed the hash function.
>
Okay, this is indeed simpler. I think the hash function just has to be 
deterministic. But the downside will always be more delay then needed. 
Note that worst case execution time is a (degenerate) deterministic hash 
function.