4 ms·

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

by richm44 12y ago

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).

Someone1234 12y ago
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).
- tptacek 12y ago
  The canonical constant-time string compare function simply accumulates the XORs of each byte of the string: http://codahale.com/a-lesson-in-timing-attacks/ http://codahale.com/a-lesson-in-timing-attacks/
  - TheLoneWolfling 12y ago
    And that's still easily able to be optimized to non-constant time by a "sufficiently evil compiler".
- richm44 12y ago
  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 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...
- e12e 12y ago
  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).

by richm44 12y ago

Someone1234 12y ago

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).

tptacek 12y ago
The canonical constant-time string compare function simply accumulates the XORs of each byte of the string: http://codahale.com/a-lesson-in-timing-attacks/ http://codahale.com/a-lesson-in-timing-attacks/
- TheLoneWolfling 12y ago
  And that's still easily able to be optimized to non-constant time by a "sufficiently evil compiler".
richm44 12y ago
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 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...
e12e 12y ago
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).