Hyper-Threading, Linus Torvalds vs. Colin Percival

OutsideIn writes "The recent Hyper-Threading vulnerability announcement has generated a fair amount of discussion since it was released. KernelTrap has an interesting article quoting Linux creator Linus Torvalds who recently compared the vulnerability to similar issues with early SMP and direct-mapped caches suggesting, "it doesn't seem all that worrying in real life." Colin Percival, who published a recent paper on the vulnerability, strongly disagreed with Linus' assessment saying, "it is at times like this that Linux really suffers from having a single dictator in charge; when Linus doesn't understand a problem, he won't fix it, even if all the cryptographers in the world are standing against him.""

Comments

Paper author just wants attention.

[tezza]

"even if all the cryptographers in the world are standing against him.""

All said cyrptographers should buy a non hyperthreaded cpu, or turn it off.

I mean if you use GPG on most machines, it will issue you a warning about Insecure Memory. That is someone could potentially harvest data from disused pages in memory.
These cryptographers would use a secure memory system. I'm happy hoping that MI6 isn't running a remote memory exploit on my box.

Re:Dictator?

[squiggleslash]

The guy was refering to the oft-quoted observation that Linus is a "benevolent dictator", or rather than Linux's development model is one of benevolent dictatorship. It wasn't an insult aimed at Torvalds. It's a comment about the development model used by many FOSS projects. See also Larry Wall and Perl, or Guido Van Rossem and Python. In all these cases contributors to the projects defer to a project figurehead who makes the final decisions as to what goes into the official version of the project, and where that project goes.

The most common alternative model is community development, where a - usually but not always elected - committee of developer 'elders' steer the project. Apache and Mozilla would be good examples of the latter.

I appreciate some people have heard about this comment first today, people are joining the Free Software and Open Source communities all the time, but it kind of surprises me that so many are criticising Colin for this without anyone explaining this.

Fix the applications

[Tom7]

Why should this be fixed in the Kernel?

This appears to be an application bug, not a kernel one. The kernel never claims to completely isolate processes from one another; though there are memory protections, there are loads of ways that processes can observer each other's actions. This is just a particularly high-resolution one.

The real "bug" here, IMO, is that openSSL believes that no other process can observe anything about its secret computations. Timing attacks against RSA have been known for some time, particularly with regard to modular exponentiation.

It wouldn't be too hard to make RSA encryption take the same amount of time no matter what code path is used, and to make its memory access patterns uncorrelated with the keys (perhaps by using randomization during allocation). They should do this--the fact that their application leaks information has nothing to do with the processor it's running on; it's just that HT makes it particularly easy to measure that information. This would have a performance penalty, and I think the OpenBSD folks are too obsessed with performance, and that's why they've not done this. The performance obsession is a serious problem in the Unix world, and software systems in general.

If implementing openSSL effectively means adding special kernel support for things like constant-length timeslices or cache invalidation between context switches, that's fine. But this is not a bug in the kenel unless the kernel purports to enforce total separation between processes, which it certainly does not.

Re:At least Linus....

[squiggleslash]

There is no such exploitable vulnerability, most of the people on LKML can tell you that, and they certainly wouldn't fix it inside kernelspace would there be one. The fact that the guy STILL holds on to the issue was explained by the top poster.

Absolute rubbish, from start to finish. Even Linus Torvalds claims no such thing.

"As to the HT 'vulnerability', it really seems to be not a whole lot different than what people saw with early SMP and (small) direct-mapped caches. Thank God those days are gone.

"I'd be really surprised if somebody is actually able to get a real-world attack on a real-world pgp key usage or similar out of it (and as to the covert channel, nobody cares). It's a fairly interesting approach, but it's certainly neither new nor HT-specific, [nor does it] necessarily seem all that worrying in real life.

Torvalds is arguing it's unlikely to ever be exploited, not that it's unexploitable or that it's not a vulnerability. The position of those, excluding yourself, who dismiss this is that it's unlikely to be usefully exploited, not that it doesn't exist. We can see it exists!

As to your last sentence, no the top poster doesn't explain it. The top poster simply describes the guy as an obsessive because he's put a lot of time into it, far more than a reasonable person might reasonably be considered to do. That's different from saying he's wrong.

In your last paragraph you clearly demonstrated what is an ad hominem attack, and what is the difference between the top post and your post

My last paragraph was a comment about irony. It had nothing whatsoever to do with attacking your argument on the basis of who you are rather than your argument. It did, however, attack your argument. Your argument was that nothing this guy says should be taken seriously because of an accusation of being mentally off-the-wall. Nash is a perfectly good counter-example. The irony is that you unwittingly brought him up. There's no ad-hominem in there, I wasn't attacking you or your credibility, I was attacking your argument.

I don't care if the guy's obsessive. I care if there's an exploitable vulnerability. Until someone writes code either way, the issue is unproven, but it's clear there's a potential, if unlikely (not impossible, just unlikely) to be useful, vulnerability there. Your comments and those of the thread originator are not convincing because they attack the proponent than explain why the argument itself is false.

Re:strcmp vulnerability.

[/ASCII]

Easy to miss, huh? Adding a random delay only means that the precision of the meassurments decrese, so you have to do more repeats to get an accurate result. The real solution is to make sure that the data access pattern is always identical.

The normal solution is to store both the the real password and the password supplied by the user in a memory area that is as large as the maximum password length and zero padded and do something like this:

int verify( const char *s )
{
int i, ok=1;
for( i=0; i<MAX_PASSWORD_LENGTH; i++ )
ok &= real_password[i]==s[i];
return ok;
}

Note that it is also vital thet the password supplied by the user is zero padded and the calculation time can not depend on how long that password is. If it did, it opens up to man in the middle attacks. Evil, huh?

Re:Great

[cperciva]

He ran the bloddy "exploit" well over 1000 time to retrieve 30% of an RSA key.

Did you read a paper other than the one I read? I ran the exploit once, taking under one second, and I retrieved enough information to factor the RSA modulus N.

A possible solution

[jesup]

This issue exists with AES implementations as well (search for AES SBOX cache timing on google). The AES vulnerability is, if anything, more worrying in a way. It can be made to be constant-time, but at a serious cost in performance.

Here's another option: since this vulnerability depends on using the L1/L2 cache states to ferret out information, remove that from consideration. When processing an RSA (etc) key, have the code temporarily lock out context switches, AND have it take a fixed period of time to compute the result (or portion of the result), followed by flushing the cache. No data is left in the cache to analyze. The execution time of the code is fixed, so no dat leaks there. You don't have to make the algorithm a constant-time calculation if you can pad it at the end to the maximum (or close enough to the theoretical maximum that there's no true information leakage in practice). This helps avoid the potentially very slow algorithms that are truely constant-time. And flushing the cache at the end of each (portion of the) calculation removes that as a leak. (You need to flush it before waiting for the allocated time to elapse, note, and include max flush time in your calculation, and if possible factor into your calculation possible interrupt effects.)

A pain? yes. Requires extensive mods to crypto algorithm implementation? Yes (though perhaps not to the core calculation.) Requires OS support? Almost certainly. Requires HW support? Would be helpful but probably not required. Loss of performance? Yes, though far lower than disabling HT I imagine in normal cases (when not decrypting/encrypting).

Also, some of the restrictions above can probably be eased if the crypto algorithm is carefully designed and matched to the hardware.

Disclaimer: I am NOT a crypto geek! I have worked in processor and cache design, though.

Fixing is easier done than said: WBINVD

[redelm]

Look: if anybody is seriously concerned about cache snooping, just patch in a WBINVD instruction as part of return-from-interrupt. That will flush the dirty cache lines back to RAM and invalidate the rest. Yes, there's a horrible cost. Perhaps higher than doing without HT. But you will be secure against the boogyman! FWIW, I agree with Linus -- this is a theoretical, negligible threat, vulnerability. It doesn't yield data, and most crypto has fixed (rather than revealing) access patterns.

Re:probably easy to fix

[cperciva]

I wonder why Colin didnt' spend his 3 months of unemployment making a user space fix for this issue...

Two reasons: First, I was busy informing vendors -- Intel, Microsoft, the *BSDs, and Linux vendors -- about the problem and explaining the possible solutions. Second, because fixing every application in the world (this doesn't only affect cryptography) would take far more than 3 months.

Re:He won't fix it?

[IIH]

I mean, c'mon, think about things before you say them. Even REAL TIME SYSTEMS AT NASA don't run with enough consistency to be able to tell WHICH CHARACTER IN A STRCMP OPERATIONS fails.

Maybe the original poster was referring to the DEC-10 page fault password insecutity that was based on strcmp returing as soon as it encountered once wrong character, based roughly on the following idea:

1) Place Password with 1st/2nd character on a page boundry.
2) Clear cache
3) Call Password check.
4) If no page fault occurred, then the 1st char must be wrong, change it and goto 3
5) if page fault occurred, 1st character is correct (as 2nd char was checked), move password so 2/3 char is on page boundry and repeat.

In this way, you can reduce the attack by a huge amount, for a n length password the brute force attack needed goes down from 256^n to 256*n.

So, yes, attacks based on which character in strcmp fails have worked in the past, so it is valid to try and not make the same type of mistake again!