Re: [Haskell-cafe] Tor project
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 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.
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.
participants (2)
-
Tobias Dammers -
Wojciech Narczyński