Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

X86 is a high-level language

blog.erratasec.com

Post reply on HN
Print view View original

121–125 of 125 posts

Re: X86 is a high-level language

#121

Post by mreiland »

TheLoneWolfling wrote: post #117
mreiland wrote: post #102

Earlier quoted context omitted.

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.

You haven't explained why it doesn't solve the problem. My experience has been if I can't understand it, it's because it's bullshit.

So why not take another crack at explaining why that wouldn't solve the problem? And don't complain to me about DDOS, people specifically code cryptographic functions to take longer than they absolutely have to. If they're not worried about DDOS, neither are we for the purposes of this conversation.

Re: X86 is a high-level language

#122

Post by mreiland »

matthewmacleod wrote: post #115
mreiland wrote: post #95

Earlier quoted context omitted.

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.

It isn't the idea of a timing attack I take issue with. I can understand how that could be possible.

I don't understand why purposefully having everything related to cryptography taking a predetermined time doesn't solve it. That's where my skepticism occurs.

I've had people mention OS page faults, ping requests, and DDOS concerns and I don't buy any of it. if the timing is really so tight that a page fault can throw you off, there's no way an outside attacker could possibly glean anything useful from the timing. The timings by definition have to be varying more than that.

I don't buy the DDOS because cryptographic functions are designed to be slow, we're not trying to make them slower, we're trying to make them even between requests. Choose a reasonable delta and anything that blows that delta starts over with another delta instead of just returning.

I don't understand why that wouldn't solve the problem reasonably. At this point I feel like it's an academic exercise rather than a practical one.

I'll openly admit a lot of these points become moot if the attacker has access to the machine itself where something like latency cannot dwarf the timings of the functions themselves (when they're specifically made to wait for a delta).

Re: X86 is a high-level language

#123

Post by maleadt »

pascal_cuoq wrote: post #63
riscy wrote: post #53

Earlier quoted context omitted.

Something interesting to note is that at least in the Pentium 4, the number of cycles spent on integer division instructions varies depending on the values of the operands [1]. [1] https://gmplib.org/~tege/x86-timing.pdf (pages 4 & 6)

This same property was also advertised as an improvement in a new generation of Intel processors a few years ago. I am pretty sure it was Haswell.

A colleague of mine mentioned how this has been the case for quite a bit longer than Haswell, see "Compiler mitigations for time attacks on modern x86 processors" (from 2012). Or Agner Fog's timings pages, where many DIV instructions list widely ranging latencies, with the comment "[l]ow values are for small results, high values for high results".

Re: X86 is a high-level language

#124

Post by nkurz »

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…

For what it's worth, I mostly[1] agree with you. You should consider should writing this up more formally as a challenge. Figure out some some of money you can afford to lose, and award it as a cash prize to anyone who can disprove you.

show how measuring the execution time as often as you like lets you discern between one input buffer version and the other

I think you can simplify this even further: is there any set of two inputs that can be distinguished from each other by measurement of execution time? One does not even need to identify which input is which --- merely show that there is some measurable property that is different for hashing A vs hashing B.

[1] I think the weakness is the reference to a "reasonable C compiler". It seems likely to me that at least one of GCC/Clang/MSVC/ICC with some combination of legal flags will generate assembly that defeats the obvious intent of your algorithm. This would be a disappointing way to lose your bet.

Re: X86 is a high-level language

#125

Post by pascal_cuoq »

maleadt wrote: post #123
pascal_cuoq wrote: post #63

Earlier quoted context omitted.

This same property was also advertised as an improvement in a new generation of Intel processors a few years ago. I am pretty sure it was Haswell.

A colleague of mine mentioned how this has been the case for quite a bit longer than Haswell, see "Compiler mitigations for time attacks on modern x86 processors" (from 2012). Or Agner Fog's timings pages, where many DIV instructions list widely ranging latencies, with the comment "[l]ow values are for small results, high values for high results".

Thanks for the reference, that is much better than my vague recollections.

What I remembered having seen advertised (presented as an improvement, of course) is new early-exit paths for the easier arguments to division. The marketing brochure emphasised the novelty, so I must have wrongly inferred that division took constant time before that.

Considering paragraph 2.2 in http://users.elis.ugent.be/~brdsutte/research/publications/2... , I may have been remembering a new division algorithm in Nehalem. I will cite that article from now on.

Post reply on HN