python-level time padding

[zooko]

Experts like DJB and Brian Warner tell me that it is kind of hopeless to try to mask a computation whose time varies depending on secret inputs by adding time-padding. But I'm not ready to give up just yet. It is surprisingly tricky and my first several designs all turned out to be fatally flawed. I forget if the following is one of the fatally flawed ones or the one I came up with after the most recent time that I learned of a fatal flaw:

Run the function with random dummy inputs instead of the real secret input, then run it again with other random dummy inputs. In parallel (e.g. using a separate thread) compute the function with the real secret input. If the latter hasn't completed by the time the first sequence of two completes (that is, it is taking more than twice as long to do the real function as the average dummy function), then abort.

CAVEATS:

This technique seems like it should defend against the attacker who can see only the time that elapses between you beginning your computation and you finishing. It does not protect against attackers who can see other sorts of "side channels" about you, such as which CPU cores you use at what times, how much energy you draw at what times, or even (intriguingly!) how many computations you can complete per time! (See, how much time it takes you to do one computation does not imply how many computations you can do per time if you are idling some of your resources some of the time!)

[davidsarah]

Replying to zooko:

Run the function with random dummy inputs instead of the real secret input, then run it again with other random dummy inputs. In parallel (e.g. using a separate thread) compute the function with the real secret input.

"Using a separate thread" does not guarantee parallel execution.

[zooko]

Replying to davidsarah:

"Using a separate thread" does not guarantee parallel execution.

Good point — thanks!

We could make it so that if the execution is not sufficiently parallel, then the failure mode is abort rather than leak-secrets.

However, that would be very unsatisfying. Users would either stop using the software, or they would figure out how to automatically retry in response to abort, thus moving the failure mode back into the "leak-secrets" side. ☺

I should mention that my motivation for this is mostly to avoid C/C++/asm code in order to have easier packaging, deployment, and portability. Wouldn't it be great if you could do all of your crypto in pure Python?

[davidsarah]

Replying to zooko:

Replying to davidsarah:

"Using a separate thread" does not guarantee parallel execution.

Good point — thanks!

We could make it so that if the execution is not sufficiently parallel, then the failure mode is abort rather than leak-secrets.

That's easier said than done. If the implementation of threading uses interleaving, then the time to execute the two dummy executions may include all or part of the time taken to do the real operations. How do you detect that reliably without depending on unspecified details of the threading implementation (and underlying OS)?

[daira]

Zooko wrote:

Experts like DJB and Brian Warner tell me that it is kind of hopeless to try to mask a computation whose time varies depending on secret inputs by adding time-padding.

Please add me to the set of experts who say this is hopeless :-p