Re:Vulnerability in Microsoft TLS library could allow remote...
by richm44 on Tuesday November 11, 2014 @04:39PM
(#8592367)
Sure. The JIT's code generator isn't attempting to make code constant time, it's designed for optimising for the common case. To make the code constant time you need to be very close to the metal (and even then you really need tools like ctgrind to make sure you've got it right). A JIT isn't the right tool for this particular job (nothing wrong with them for other things of course).
[ Parent
| on HN ]
Re:Vulnerability in Microsoft TLS library could allow remote...
by Someone1234 on Tuesday November 11, 2014 @05:11PM
(#8592576)
Constant time just means that a fail and success state take the same amount of time to execute. They both go through the same level of computation regardless of if you know from the first instruction that it will eventually fail.
For example:
const string password = "password";
static bool isAllowed(string code)
{
if (code.Length != password.Length)
return false;
for (int x = 0; x < password.Length; x++)
{
if (code[x] != password[x])
return false;
}
return true;
}
Is not constant time because the failure state returns sooner than the success state. const string password = "password";
static bool isAllowed(string codex)
{
bool allowed = true;
char[] code = new char[Math.Max(password.Length, codex.Length)];
codex.CopyTo(0, code, 0, codex.Length);
for (int x = 0; x < password.Length; x++)
{
if (code[x] != password[x])
allowed = false;
}
return allowed;
}
This is an imperfect constant time function as both states (failure/success) return near after the same amount of time (although I fully admit that it might be possible to impose the length of the password constant).
Re:Vulnerability in Microsoft TLS library could allow remote...
by richm44 on Tuesday November 11, 2014 @05:49PM
(#8592789)
And the run-time of a managed language is 100% able to change all the timing of that if it's smart enough. It provides a guarantee of outcome not of timing. There are examples of unexpected optimisations even from static compilers such as gcc (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56888 for example). There's nothing stopping the jvm from bailing out early even in your second example. If you'd done something like xoring all the bytes together then checking the result then maybe we'd be approaching something that it's unlike a jit could handle, but the code as is seems ripe for a decent optimiser to me. And remember that according to the spec you're now coding for a perfect optimiser, not just a decent one...
Re:Vulnerability in Microsoft TLS library could allow remote...
by tptacek on Tuesday November 11, 2014 @05:47PM
(#8592773)
The canonical constant-time string compare function simply accumulates the XORs of each byte of the string:
Re:Vulnerability in Microsoft TLS library could allow remote...
by TheLoneWolfling on Tuesday November 11, 2014 @10:45PM
(#8593903)
And that's still easily able to be optimized to non-constant time by a "sufficiently evil compiler".
Re:Vulnerability in Microsoft TLS library could allow remote...
by e12e on Tuesday November 11, 2014 @08:54PM
(#8593569)
The typical timing attack in this case, would be leaking password length (the time taken in the for-loop), no? Then there's the possibility of assignment (allowed=false) taking enough time that guessing with, say "00000" and "x00000" might allow one to verify that password starts with x (and then build up to the full password).
But more fundamentally, what is string.Length? Are these Pascal-style strings, or is that a call to a method that walks the string (O(n))? Those kind of issues (along with the full nature of the code path taken by something like assignment and memory allocation) are abundantly more clear in assembler (or byte code, assuming a predictable vm. But a vm likely isn't -- as far as I know it would at least never be more predictable than machine code).