> That seems like a lot of functions to artificially slow down. Well, in most cases it shouldn't slow it down by a non-trivial margin.
It's not like comparison which removes the ability to short circuit, where it can be extremely significantly longer. When doing things like encoding or decoding, the real difference is ensuring that cache access patterns are consistent and that the amount of time spent inside the conversion is consistent. In the example of bin2hex http://lxr.php.net/xref/PHP_TRUNK/ext/standard/string.c#130 the repeated lookup of hexconvtab results in cache lookups which can vary in time depending on the index. In this case, it *might* be OK, since hexconvtab is small enough to pretty much always be in L1 cache (in its entirety), but this is generally not true. So one of the recommendations is to never use secrets in the indexes of table lookups. Instead, do mathematical operations. The PR cited in this thread does just that. It replaces the table lookup with result->val[j++] = (char) (87 + b + (((b - 10) >> 31) & -39)); On the surface, that is more operations (2 addition, one subtraction, one shift and one bitwise and) vs the table lookup. But it shouldn't be much slower since they are all register operations vs the table lookup that has to go to cache every time. I did a quick POC microbench in C comparing the two (outside of PHP), and they were within a margin of error of each other. Code at the end of the mail. hex2bin is a bit more complicated due to the error checks: http://lxr.php.net/xref/PHP_TRUNK/ext/standard/string.c#149 But it also leaks far more information due to the conditional branching. There is an alternative method which would still allow for error checking and short-circuiting on error: https://github.com/Sc00bz/ConstTimeEncoding/blob/master/hex.cpp#L30 The problem with hex2bin isn't that it short circuits on error, that's fine. It's that it branches on data in non-error contexts. But there should be ways around that without sacrificing performance. I did a quick benchmark of an unoptimized (but correct) version, and it's about 20-30% slower on my machine. Code at the end of the mail. Now 20-30% isn't trivial. In reality, the difference is about 1/2 microsecond on a test string that's about 40 characters long. Longer strings may have worse performance, but we could look at optimizing that operation further to cut the difference down. Looking at the function list: * bin2hex() * hex2bin() * base64_encode() * base64_decode() * mcrypt_encrypt() * mcrypt_decrypt() The first two I've already shown can be done without a massive performance penalty (none in the case of bin2hex). base64_encode and decode should be quite similar to hex2bin and bin2hex, since the same fundamental operations are happening under the hood (just different table size). So without doing the benchmark, I'd imagine quite similar results should be possible (penalty free encode, and minor penalty on decode). The two mcrypt functions, IMHO **MUST** be made timing safe, no matter what, since they **always** deal with sensitive information. That should have happened when they were first written. But it's all good. As far as whether the other 4 *need* to be made TS, I don't know. I think if the performance hit is small enough (1/2 micro-second is small enough IMHO), then there isn't much cost to doing so, but potentially some win in the cases they are used in security contexts. If the performance hit is 0 (as with the encode side), then I think it's a no brainer to do. The POC code, dirty, unoptimized, but works: https://gist.github.com/ircmaxell/c26ff31a80ac69b1349a Anthony On Wed, Nov 26, 2014 at 9:51 AM, Rasmus Lerdorf <ras...@lerdorf.com> wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > On 11/25/2014 07:37 AM, Scott Arciszewski wrote: >> I would like to, at the minimum, suggest making the following >> functions run in constant time: >> >> * bin2hex() * hex2bin() * base64_encode() * base64_decode() * >> mcrypt_encrypt() -- requires delving into libmcrypt, which has >> been collecting dust since 2007 and probably doesn't support >> AES-NI * mcrypt_decrypt() -- ditto >> >> This is only the ones I'm aware of; there are probably many others >> that may be used that could benefit from similar enhancements. > > That seems like a lot of functions to artificially slow down. Many of > these exist in code that is quite performance sensitive and not > timing-attack sensitive in any way. If we start down this path then > eventually every string-handling function in PHP would need to run in > constant time and there we would slow down every PHP application in > existence artificially. I don't see this happening. You will need to > find another solution. > > Perhaps it is a naive solution, but as long as you have a crypto-safe > source of entropy, why can't you insert a random delay into the flow > that is vulnerable to a timing attack. I suppose the attacker could > average over many runs to try to account for this added randomness, > but if the potential magnitude of the random delay was far greater > than the magnitude of the operation being shielded then it would take > a lot of observations before the attacker would have any chance of > picking the signal out of the noise. > > Or, write yourself an extension and mirror the implementations of all > these functions. pecl/ts_string or something like that and provide > ts_bin2hex() and/or have the extension override the built-in versions > if you really want to slow down every instance of these. > > - -Rasmus > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v1 > > iEYEARECAAYFAlR16NYACgkQlxayKTuqOuAh+gCfcFW5mIPYOONp7WV6umwg1Tu1 > r8IAn20lcVHHaBkn9gxKAfYikJAz56Py > =wqOS > -----END PGP SIGNATURE----- > > -- > PHP Internals - PHP Runtime Development Mailing List > To unsubscribe, visit: http://www.php.net/unsub.php > -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
