0
$\begingroup$

I'm thinking of cryptographic implementations on garbage-collected (gc) languages/runtimes and that the gc process can be potentially dangerous for an implementation even if the implementation has the "constant-time" property. Imagine the following code for example:

{
    x = {big chunk data that are not referenced anywhere else}
    if (expression that depends on sensitive data) {
       do something that takes A time.
       go to L1
    }
}
{
    do something that takes A time.
}
L1:
   rest of the code

If gc is executed after the first block the $x$ variable will have to get freed and this time interval can reveal an information bit of sensitive data for example.

My question is have there been any such cases in the bibliography? If they do how developers can defend against such attacks? I did a bit of research and I couldn't find anything interesting except for this thread in HackerNews.

$\endgroup$
2
  • 2
    $\begingroup$ Best practice to avoid timing attack and some other kinds of side-channel attacks is not to try to make code branches depending on sensitive data the same duration. It's to avoid any code branch depending on sensitive data. See this question. $\endgroup$
    – fgrieu
    Jan 12 at 16:28
  • $\begingroup$ Does the line of code that begins x = allocate that memory? If so it isn't constant-time even without considering gc. You would need to consider code where all cases allocate the same amount of data, but some input values result in different amounts of garbage. And consider that the same algorithm in a non-gc language would still need to deallocate the memory, which suggests that it's not gc that's the problem. $\endgroup$
    – bmm6o
    Jan 12 at 16:55

2 Answers 2

4
$\begingroup$

Now, constant time code can't have conditional jumps based on secret data, or access memory locations based on secret data - either of those can cause timing variations. Your example violates this (because of the conditional jump).

The only way I can see how constant time code could have a leak due to Garbage collection is if the constant time code either had a reference to a data structure or didn't have a reference, and whether it did would depend on secret data. The constant time code could conditionally clear out the reference (without violating the constant time requirements).

If it did that, then whether that data structure is GC'ed would depend on the secret data and that would be a leak.

However, the constant time code couldn't access that memory structure (because of the prohibition on accessing secret-based memory locations), and so it's a bit unclear to me how that would arise in practice; conditionally clearing out a reference that cannot be used doesn't strike me as something that a naive (but honest) programmer would do...


Now, one thing that occurs to me is that Garbage Collection could more plausibly amplify the leakage in code that already has some.

Consider this pseudocode:

 A, B are the only references to data structures
 if (secret_condition)
     B := A    /* Have B refer to A's data structure, leaving no */
               /* reference to what B used to refer to */
 do computations on the data structures referred to by A, B

That code is at least somewhat plausible.

It also has a timing leak (because on what memory locations that B refers to is based on secret data), however depending on what those references are, it might be fairly quiet.

On the other hand, if Garbage Collection happens, then either one of the data structures will be cleaned up or not, based on secret data. Garbage Collection could plausibly be louder (that is, easier to detect by an attacker).

On the other hand, I haven't heard of someone using this 'amplification' effect in a practical attack.

$\endgroup$
1
$\begingroup$

It's funny, this question caught my eye and it turns out that I replied to that HN thread 10 years ago. I agree with everything Poncho says and just wanted to expand on the idea that GC is mostly a distraction here.

Remember that GC is just one way of returning unused memory to the runtime; the other major ways being manual memory management and reference counting. Importantly, if your implementation is not leaking memory, then memory is being reclaimed one way or another. If the GC has variable amount of work to do, then the equivalent implementation written in C will have a variable number of calls to free. So the GC is not the root cause of the of the information leak, it's really the memory usage and release patterns of the algorithm.

There are programming techniques that we could use to avoid leaking this signal. For instance, if our program is short-lived enough, we can get away with never freeing memory. We can also allocate all of our memory in a single "arena" to be freed at once. But all of this is moot if your secret-dependent memory access patterns are already leaking memory like Poncho describes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.