Security Issues in Matrix's Olm Library • Hacker News Board

Re: Security Issues in Matrix's Olm Library

#21

Post by ghostpepper » Fri, Aug 16, 2024, 6:26 PM UTC

some_furry wrote: post #13

ghostpepper wrote: post #12

Earlier quoted context omitted.

Unless I misunderstood (which is entirely possible, not a crypto expert) that article is answering a different question: whether adding random delays can thwart timing attacks. The GP was asking about implementing a constant-time delay.

Ok, let's assume you know how long an operation is supposed to take, but want to stop it from leaking if it returns faster. To accomplish this, you would need a high-resolution timer that runs before the operation, after the operation, and then you can subtract the two and wait. And maybe that might work. But you're not running in kernel space. The resolution of timing information you'd get from this tactic would be…

is a constant-time algorithm just an algorithm that completes the entire calculation before returning even if it knows the correct answer sooner?

Re: Security Issues in Matrix's Olm Library

#22

Post by some_furry » Fri, Aug 16, 2024, 7:11 PM UTC

ghostpepper wrote: post #21

some_furry wrote: post #13

Earlier quoted context omitted.

Ok, let's assume you know how long an operation is supposed to take, but want to stop it from leaking if it returns faster. To accomplish this, you would need a high-resolution timer that runs before the operation, after the operation, and then you can subtract the two and wait. And maybe that might work. But you're not running in kernel space. The resolution of timing information you'd get from this tactic would be…

is a constant-time algorithm just an algorithm that completes the entire calculation before returning even if it knows the correct answer sooner?

"constant-time" isn't a literally technically correct descriptor, it's a short-hand

What matters is that the variance of execution time, which memory addresses are accessed, etc. is independent of any secret inputs.

Re: Security Issues in Matrix's Olm Library

#23

Post by ghostpepper » Fri, Aug 16, 2024, 10:06 PM UTC

some_furry wrote: post #22

ghostpepper wrote: post #21

Earlier quoted context omitted.

is a constant-time algorithm just an algorithm that completes the entire calculation before returning even if it knows the correct answer sooner?

"constant-time" isn't a literally technically correct descriptor, it's a short-hand What matters is that the variance of execution time, which memory addresses are accessed, etc. is independent of any secret inputs.

so theoretically using timers and adding sleeps could solve the problem but practically there are better ways to achieve the goal of no timing information leakage?

Re: Security Issues in Matrix's Olm Library

#24

Post by some_furry » Sat, Aug 17, 2024, 7:04 AM UTC

ghostpepper wrote: post #23

some_furry wrote: post #22

Earlier quoted context omitted.

"constant-time" isn't a literally technically correct descriptor, it's a short-hand What matters is that the variance of execution time, which memory addresses are accessed, etc. is independent of any secret inputs.

so theoretically using timers and adding sleeps could solve the problem but practically there are better ways to achieve the goal of no timing information leakage?

Yes. I wrote this a few years ago as an introduction to how to write constant-time algorithms

https://soatok.blog/2020/08/27/soatoks-guide-to-side-channel...