X86 is a high-level language • Hacker News Board

Re: X86 is a high-level language

#111

Post by sdevlin » Thu, Mar 26, 2015, 11:44 AM UTC

raverbashing wrote: post #106

sdevlin wrote: post #80

Earlier quoted context omitted.

Are you talking about this paper? https://gmplib.org/~tege/x86-timing.pdf I only saw evidence of data-dependent timing with respect to the div operation, but maybe I missed something. Of course, I am not suggesting other operations are inherently immune to data-dependent timing leaks. EDIT: I see there are also some notes on adc and sbb in some situations, i.e. chains of instructions that all light up the carry flag.

Don't worry about the instruction, worry about dest, src. If they: - Are in cache - Were touched by a previous instruction (regardless of cache) - Their cache line was touched by a previous instruction - Will be read/write (immediately) after that instruction - You're accessing data shared by multiple cores (lock prefix) timing will vary

That's the whole point, though - the algorithm is very straightforward to implement without data-dependent look-ups. So while any of those could affect execution time, none should do so in a way that leaks data.

Re: X86 is a high-level language

#112

Post by sdevlin » Thu, Mar 26, 2015, 12:10 PM UTC

pbsd wrote: post #108

sdevlin wrote: post #104

Earlier quoted context omitted.

> They also added the PCLMULQDQ instruction to efficiently implement ECC. Isn't this more typically used in GHASH implementations? Maybe it's applicable to both.

PCLMULQDQ is a godsend to both (GCM and binary elliptic curves), since both rely heavily on multiplication performance over F_{2^n}. The current fastest elliptic curve implementations are over binary fields using this instruction: http://eprint.iacr.org/2013/131 .

Ah, interesting - so this applies in particular to elliptic curves over binary fields.

I may have missed this, but did they note how performance fared in the absence of hardware support?

Also, have binary curves (this or the NIST ones or any others) seen widespread deployment anywhere? I was under the impression that prime field curves were more widely used.

Re: X86 is a high-level language

#113

Post by pbsd » Thu, Mar 26, 2015, 12:32 PM UTC

sdevlin wrote: post #112

pbsd wrote: post #108

Earlier quoted context omitted.

PCLMULQDQ is a godsend to both (GCM and binary elliptic curves), since both rely heavily on multiplication performance over F_{2^n}. The current fastest elliptic curve implementations are over binary fields using this instruction: http://eprint.iacr.org/2013/131 .

Ah, interesting - so this applies in particular to elliptic curves over binary fields. I may have missed this, but did they note how performance fared in the absence of hardware support? Also, have binary curves (this or the NIST ones or any others) seen widespread deployment anywhere? I was under the impression that prime field curves were more widely used.

As far as I know they didn't try to make a good implementation without CLMUL. However, the older endomorphism-free curve2251 implementation [2, 3] is eye-opening:

- the SSSE3 implementation is ~2.7 times slower than with CLMUL - the generic (using mpfq, which should actually be pretty good) implementation is 5-6 times slower than with CLMUL

Binary curves used to be a lot more popular than they are now, before we all had fat multipliers in CPUs. The patent situation is worse for binary fields too, I think. That said, I'm pretty sure there are deployments somewhere using them; Dan Boneh's TLS survey [1] shows an overwhelming 96% of TLS clients using NIST's P-256, but the second most popular curve is NIST's B-233, at 3.6%. I would guess that this is due to hardware accelerators.

[1] http://www.w2spconf.com/2014/papers/TLS.pdf

[2] http://bench.cr.yp.to/web-impl/amd64-titan0-crypto_dh.html

[3] https://eprint.iacr.org/2011/170

Re: X86 is a high-level language

#114

Post by sdevlin » Thu, Mar 26, 2015, 1:40 PM UTC

pbsd wrote: post #113

sdevlin wrote: post #112

Earlier quoted context omitted.

Ah, interesting - so this applies in particular to elliptic curves over binary fields. I may have missed this, but did they note how performance fared in the absence of hardware support? Also, have binary curves (this or the NIST ones or any others) seen widespread deployment anywhere? I was under the impression that prime field curves were more widely used.

As far as I know they didn't try to make a good implementation without CLMUL. However, the older endomorphism-free curve2251 implementation [2, 3] is eye-opening: - the SSSE3 implementation is ~2.7 times slower than with CLMUL - the generic (using mpfq, which should actually be pretty good) implementation is 5-6 times slower than with CLMUL Binary curves used to be a lot more popular than they are now, before we all…

Great info - thanks!

Re: X86 is a high-level language

#115

Post by matthewmacleod » Thu, Mar 26, 2015, 3:58 PM UTC

mreiland wrote: post #95

matthewmacleod wrote: post #84

Earlier quoted context omitted.

The basic cause of a timing attack is that if cryptographic operations can take different amounts of time depending on the content, then we can potentially be leaking information to an attacker. If we try to solve this by padding our work using sleep() or similar, we might reveal less information directly – but the performance characteristics of our machine will still be different when we complete and operation quick…

I don't see it. I get what you're saying, but how does latency not swallow that difference? Or load balancing, or routing through the internal network behind the router. It's really hard for me to buy that an attacker can determine the execution characteristics of your crypographic functions via ping over the internet.

It's not much of a stretch from the Lucky 13 attack (http://www.isg.rhul.ac.uk/tls/TLStiming.pdf) to something like I described – it might be worth having a look at that paper if you're interested in seeing how much information can be extracted from delicate timing changes!

I understand your scepticism, but there have been a fair few timing attacks showing the viability of this approach.

Re: X86 is a high-level language

#116

Post by TheLoneWolfling » Thu, Mar 26, 2015, 4:11 PM UTC

pascal_cuoq wrote: post #105

TheLoneWolfling wrote: post #99

Earlier quoted context omitted.

Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time? Also, what about context switches in general? Stack memory can be zeroed to start. If you're writing zeros to the stack on a context switch I could see that being a different amount of time taken than if it's not zero. Due to the CPU not having to publish the memory write.…

> Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time? One only needs to trust the timings of instructions that one actually needs to implement cryptography. I admit I had not even considered whether an interruption and a visit through the scheduler could take an amount of time that depended of secrets; on some architectures…

> You need to keep track of what register values depend on secrets. This is what ctgrind does. ctgrind warns when a register that has been computed from a secret is used for branching or memory access:

I don't see how keeping track of register values that depend on secrets helps. All registers that contain secrets can potentially be written to memory, and as such leak information. Due to context switching. So saying "don't use registers that contain secrets for memory accesses" doesn't help, because the only way to accomplish that is either to never have registers that contain secrets or guarantee that the kernel also does the same thing. And I don't see how the kernel can context-switch without doing so.

Re: X86 is a high-level language

#117

Post by TheLoneWolfling » Thu, Mar 26, 2015, 4:13 PM UTC

mreiland wrote: post #102

TheLoneWolfling wrote: post #98

Earlier quoted context omitted.

Your operating system hits memory pressure and pages your RAM page to disk. Some time later it restores it. Hey, look, you've suddenly had an arbitrarily long delay. So you can't always finish early. Also, even assuming you can always finish early, that plan won't prevent, for example, measuring the delay of other responses. (As your process sleeping will have an impact on how fast other responses are sent. Due to ca…

Why is it people can't ever respond to sanity, but instead assume idiocy? You measure page faults in terms of milliseconds, I was not suggesting you even out the cryptographic timings to the tune of milliseconds, especially when you consider most cryptographic functions are setup specifically to take longer than that. There is a delta that you can come up with such that things like page faults fall within it and it w…

You completely missed my second point there - that even if you can afford to take the performance hit it still doesn't solve the problem.

And most of the cryptographic functions we're talking about here are things for webservers, where low performance leaves you open to easy (D)DOSing.

Re: X86 is a high-level language

#118

Post by pascal_cuoq » Thu, Mar 26, 2015, 7:22 PM UTC

TheLoneWolfling wrote: post #116

pascal_cuoq wrote: post #105

Earlier quoted context omitted.

> Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time? One only needs to trust the timings of instructions that one actually needs to implement cryptography. I admit I had not even considered whether an interruption and a visit through the scheduler could take an amount of time that depended of secrets; on some architectures…

> You need to keep track of what register values depend on secrets. This is what ctgrind does. ctgrind warns when a register that has been computed from a secret is used for branching or memory access: I don't see how keeping track of register values that depend on secrets helps. All registers that contain secrets can potentially be written to memory, and as such leak information. Due to context switching. So saying…

I simply do not understand what you mean.

Here is a proposal: I have verified that when the Skein cryptographic hash function is computed on a buffer of length n, using the reference implementation, then out of the program inputs, the computation time only depends on:

- n, the length of the buffer

- one, a static const variable used to determine endianness

and NOT on the contents of the buffer.

Please take any widespread processor of your choice, any widespread OS of your choice, any reasonable C compiler (not a C compiler that transforms constant-time operations into non-constant-time, I can write one of these as well as you, this is not the goal of the exercise), the length n of your choice, two input buffer contents of length n of your choice, and show how measuring the execution time as often as you like lets you discern between one input buffer version and the other.

Do as much statistic analysis as you need. Launch Skein a billion times if you need to. Have a device on the USB port that causes interrupts if that helps. Disable all cores except one. Disable hyperthreading. Enable hyperthreading.

But only come back when you have concrete proof of your claim.

Deal?

NOTE: you may think it's too much work just to satisfy some dude on Hacker News, but I'm sure you can become quite famous if you know how to do this. You are not doing this to convince only me. The people behind Skein think that its execution time does not depend on secrets, the fools, and since I followed Adam Langley's methodology to verify that property, you'll be proving him wrong too.

Re: X86 is a high-level language

#119

Post by TheLoneWolfling » Thu, Mar 26, 2015, 7:38 PM UTC

pascal_cuoq wrote: post #118

TheLoneWolfling wrote: post #116

Earlier quoted context omitted.

> You need to keep track of what register values depend on secrets. This is what ctgrind does. ctgrind warns when a register that has been computed from a secret is used for branching or memory access: I don't see how keeping track of register values that depend on secrets helps. All registers that contain secrets can potentially be written to memory, and as such leak information. Due to context switching. So saying…

I simply do not understand what you mean. Here is a proposal: I have verified that when the Skein cryptographic hash function is computed on a buffer of length n, using the reference implementation, then out of the program inputs, the computation time only depends on: - n, the length of the buffer - one, a static const variable used to determine endianness and NOT on the contents of the buffer. Please take any widesp…

Nope.

I have neither the time nor the expertise to be able to do this myself.

You're not trying to defend against people with my level of expertise (or rather, lack thereof). You're trying to defend against people who are a whole lot smarter than me, and have a whole lot more time on their hands.

I was hoping you either had something showing it wasn't a problem, or a workaround. Instead you've basically gone "I don't think it's a problem" and dismissed it. Normally, that would be ok. But it's cryptography. That's not good enough.

Re: X86 is a high-level language

#120

Post by pascal_cuoq » Thu, Mar 26, 2015, 7:52 PM UTC

TheLoneWolfling wrote: post #119

pascal_cuoq wrote: post #118

Earlier quoted context omitted.

I simply do not understand what you mean. Here is a proposal: I have verified that when the Skein cryptographic hash function is computed on a buffer of length n, using the reference implementation, then out of the program inputs, the computation time only depends on: - n, the length of the buffer - one, a static const variable used to determine endianness and NOT on the contents of the buffer. Please take any widesp…

Nope. I have neither the time nor the expertise to be able to do this myself. You're not trying to defend against people with my level of expertise (or rather, lack thereof). You're trying to defend against people who are a whole lot smarter than me, and have a whole lot more time on their hands. I was hoping you either had something showing it wasn't a problem, or a workaround. Instead you've basically gone "I don't…

That is one way of putting it.

The other way of putting it is that you are arguing about things that you may not fully understand, or perhaps you are not able to put your ideas into words that others can understand.

You are right, I have given up on understanding what you meant. I will look forward to the proof of concept.