I can't comment on the need for a timing-independent fix in any given location -- my instinct suggests HMAC with "strong enough" hashes doesn't need timing-resistant equality checks because brute forcing HMAC is bloody difficult -- but with the assumption that the analysis was done correctly, there's no easy way to speed up equality tests that don't leak timing information.
There are two possible solutions to this: - Fix the comparison to run more quickly - Change algorithms in whatever calls comparisons so often that comparisons are a major bottleneck Both options together may in fact lead to better performance than before, so it's worth investigating both. My suggestions for things to try to speed up the comparison: - Implement a similar comparison algorithm in C and call it via FFI methods - Implement a sip-hash for the strings and bail early if the hashes don't match. The choice of hashing function is important -- it can't be something that allows easily constructing strings that collide. One might almost suggest hmac-sha256, except that's apparently the thing that is already too slow. The siphash value could be computed ahead of time, perhaps for one of the inputs anyway, which may improve the user-visible latency. On the other hand, with the timing that you've reported, this looks like it'd be a real problem only if there's supposed to be ~10K comparisons per second; how likely is that? If it happens often, it sounds a lot like an O(N) algorithm is being used when an O(Lg(N)) algorithm should be used instead. Consider, if the code is searching linearly through a list to find a match it could probably be converted to a sorted array or a tree or a hash table to allow bisection searches or searching significantly fewer entries in a hash table. Maintaining a binary tree or sorted array could be cheaper than repeated linear searches, especially if enough lookups are performed between insertions / deletions. Algorithmic improvements are harder to discuss in the abstract -- and may require changing multiple interfaces -- but stand a better chance of addressing this regression head-on than trying to tweak the comparison code. -- You received this bug notification because you are a member of Ubuntu Server Team, which is subscribed to nova in Ubuntu. https://bugs.launchpad.net/bugs/1361357 Title: metadata service performance regression ~100x To manage notifications about this bug go to: https://bugs.launchpad.net/cloud-archive/+bug/1361357/+subscriptions -- Ubuntu-server-bugs mailing list Ubuntu-server-bugs@lists.ubuntu.com Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/ubuntu-server-bugs
