HT Vulnerability CAN-2005-0109

HT Vulnerability CAN-2005-0109

[Nils Toedtmann]

Sorry if this is a dupe. I quickly checked the lists and the bitkeeper
changesets but found no reference. If i missed it, ignore this mail.


Just stumbled on /. upon CAN-2005-0109 and wonder if xen is affected:

  <http://cve.mitre.org/cgi-bin/cvename.cgi?name=CAN-2005-0109>
  <http://www.daemonology.net/hyperthreading-considered-harmful/>

I have _no_clue_ about OS internals, processors or programming, but as i
understood the abstract this is a bug on some intel pentium/xeon cpus in
their hyperthreading implementation (i read it "ht threads share cpu
cache in a way that information leaks from one thread to another"). The
author states that the OS kernel (here: the xen kernel) could workaround
that bug.

Is it possible that two domain kernels running on the same physical core
but on different ht threads leak information to each other exploiting
this covert/side channels?

I apologize in advance if all this does not make sense ...

/nils.

Re: HT Vulnerability CAN-2005-0109

[Mark Williamson]

> Sorry if this is a dupe. I quickly checked the lists and the bitkeeper
> changesets but found no reference. If i missed it, ignore this mail.

No, this hasn't been mentioned on the lists yet.

> Just stumbled on /. upon CAN-2005-0109 and wonder if xen is affected:
>
>   <http://cve.mitre.org/cgi-bin/cvename.cgi?name=CAN-2005-0109>
>   <http://www.daemonology.net/hyperthreading-considered-harmful/>

This vulnerability could (in principle) affect isolation between Xen VMs.  
It's not clear how exploitable it is, though.

> I have _no_clue_ about OS internals, processors or programming, but as i
> understood the abstract this is a bug on some intel pentium/xeon cpus in
> their hyperthreading implementation (i read it "ht threads share cpu
> cache in a way that information leaks from one thread to another"). The
> author states that the OS kernel (here: the xen kernel) could workaround
> that bug.

Yes, it's possible to imagine various strategies to work around this problem.

> Is it possible that two domain kernels running on the same physical core
> but on different ht threads leak information to each other exploiting
> this covert/side channels?

Theoretically possible but not necessarily a problem in practice.

Covert channels will *always* be there.  The problem with this channel is that 
it is potentially rather high bandwidth and that it can be used as a side 
channel to try to capture crypto keys from OpenSSL.

Someone has yet to release code that'll actually exploit these theoretical 
holes, so it's not clear how big a problem is in practice.

Cheers,
Mark

> I apologize in advance if all this does not make sense ...
>
> /nils.
>
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel

Re: HT Vulnerability CAN-2005-0109

[David Hopwood]

Mark Williamson wrote:
>>Just stumbled on /. upon CAN-2005-0109 and wonder if xen is affected:
>>
>>  <http://cve.mitre.org/cgi-bin/cvename.cgi?name=CAN-2005-0109>
>>  <http://www.daemonology.net/hyperthreading-considered-harmful/>
> 
> This vulnerability could (in principle) affect isolation between Xen VMs.  
> It's not clear how exploitable it is, though.

It's clear that it is very exploitable.

> Covert channels will *always* be there.

Yes. As you say, the problem is the side channel attack, not the covert
channel.

> Someone has yet to release code that'll actually exploit these theoretical 
> holes, so it's not clear how big a problem is in practice.

Huh? That sounds like something I would expect to hear from a Microsoft
marketroid. The paper includes code for the side channel attack (Figure 1
in <http://www.daemonology.net/papers/htt.pdf>), and even if it didn't, it
would be easy to replicate.

-- 
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

Re: HT Vulnerability CAN-2005-0109

[Mark Williamson]

> > This vulnerability could (in principle) affect isolation between Xen VMs.
> > It's not clear how exploitable it is, though.
>
> It's clear that it is very exploitable.

On a real world system?

"To ensure that the two processes run simultaneously, we start running the Spy 
process before we start OpenSSL, and stop it after OpenSSL has finished, while 
minimizing the number of other processes running"

That's fine as a proof of concept but it's not the real world.  Note that I'm 
not denying a persistent attacker may still capture a key eventually, even in 
a very "noisy" environment.  The barrier to successful exploit may be 
substantially increased, however.

> > Covert channels will *always* be there.
>
> Yes. As you say, the problem is the side channel attack, not the covert
> channel.

The covert channel is still a problem if it's substantially higher bandwidth 
than the inevitable pre-existing channels.  For the XenSE work with mandatory 
access control we can't eliminate covert channels but we'd like them not to 
be high bandwidth.

> > Someone has yet to release code that'll actually exploit these
> > theoretical holes, so it's not clear how big a problem is in practice.
>
> Huh? That sounds like something I would expect to hear from a Microsoft
> marketroid.

Thank you for your insight, David.

> The paper includes code for the side channel attack (Figure 1 
> in <http://www.daemonology.net/papers/htt.pdf>), and even if it didn't, it
> would be easy to replicate.

I admit I hadn't noticed the code included could be used in the side channel 
attack - it's a fair cop guv!  It's worrying - we should watch what the other 
OS communities do on this.

Regards,
Mark

Re: HT Vulnerability CAN-2005-0109

[Nils Toedtmann]

Am Donnerstag, den 19.05.2005, 03:46 +0100 schrieb Mark Williamson:
> > The paper includes code for the side channel attack (Figure 1 
> > in <http://www.daemonology.net/papers/htt.pdf>), and even if it didn't, it
> > would be easy to replicate.
> 
> I admit I hadn't noticed the code included could be used in the side channel 
> attack - it's a fair cop guv!  It's worrying - we should watch what the other 
> OS communities do on this.

At the moment, they release quick workarounds like hardening crypto libs
against timing attacks

  <https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=157631>

or disabling HT

  <ftp://ftp.freebsd.org/pub/FreeBSD/CERT/advisories/FreeBSD-
SA-05:09.htt.asc>

 "V.   Solution

  Disable Hyper-Threading Technology on processors that support it.

  NOTE:  It is expected that future work in cryptographic libraries and
  operating system schedulers may remedy this problem for many or most
  users, without necessitating the disabling of Hyper-Threading
  Technology.  Future advisories will address individual cases."


In case i'd be so paranoiac (as the freebsd sec team) to consider the HT 
prob a real world threat: Would the xen boottime option "noht" be a 
workaround (diabling HT, but not SMP) until this gets fixed properly?

/nils.

Re: HT Vulnerability CAN-2005-0109

[David Hopwood]

Mark Williamson wrote:
>>>This vulnerability could (in principle) affect isolation between Xen VMs.
>>>It's not clear how exploitable it is, though.
>>
>>It's clear that it is very exploitable.
> 
> On a real world system?

Yes.

> "To ensure that the two processes run simultaneously, we start running the Spy 
> process before we start OpenSSL, and stop it after OpenSSL has finished, while 
> minimizing the number of other processes running"

The only critical issue is that the crypto code and the Spy process run
simultaneously on different threads of an HT processor. In a real situation,
there are any number of ways this could be arranged. The simplest way to get
the timing right would probably be for the attacker to initiate an SSL
connection himself.

In the case where the attack is performed between hypervisor domains, it's
easy for the attacker to ensure that the Spy is the only code running in
his domain.

> That's fine as a proof of concept but it's not the real world.

The author is not attempting to do a real world attack. He's simplifying the
situation as much as possible, in order to get clean data, simple exploit
code, and a set-up that is easy to describe and reproduce. That's what you
always do (speaking from experience) when trying to demonstrate attacks
that depend on timing. Unfortunately there is the hazard that people may
think that restrictions you introduced just as a simplification, are actually
necessary preconditions for the attack.

A real attack would be a bit more complicated, but no less feasible.

> Note that I'm not denying a persistent attacker may still capture a key
> eventually, even in a very "noisy" environment.

I think you're overestimating how noisy a real environment would be. There
would be no interference from other processes, because an OS time slice in
the victim domain is long enough to almost always run the whole of the crypto
operation (in this case a modular exponentiation). Even if it wasn't, it
would be easy to recognize when a context switch occurred. Within a time
slice the crypto code and the Spy are the only two processes using the
shared cache.

>>The paper includes code for the side channel attack (Figure 1 
>>in <http://www.daemonology.net/papers/htt.pdf>), and even if it didn't, it
>>would be easy to replicate.
> 
> I admit I hadn't noticed the code included could be used in the side channel 
> attack - it's a fair cop guv!  It's worrying - we should watch what the other 
> OS communities do on this.

I think the FreeBSD fix implements the approach suggested in the paper of
not scheduling threads with different privileges on the same HT processor.

In Xen, this would correspond to only giving any particular domain a whole
HT processor. I'm not sure how that would affect performance; it could result
in only one thread of an HT processor being used in some cases, but OTOH cache
utilization might improve in others.

-- 
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

Re: HT Vulnerability CAN-2005-0109

[Mark Williamson]

Sorry I've taken so long to respond!

> >>It's clear that it is very exploitable.
> >
> > On a real world system?
>
> Yes.

I'd be more convinced by a record of a successful exploit on a less restricted 
workload.  A simplified example for exposition of the problem can still be 
provided.

> I think the FreeBSD fix implements the approach suggested in the paper of
> not scheduling threads with different privileges on the same HT processor.

For now I think they've just disabled HT (by default) whilst figuring out what 
the best fix is for the long term.  This is arguably worth considering for 
anyone who thinks their configuration may be vulnerable to this attack.

> In Xen, this would correspond to only giving any particular domain a whole
> HT processor. I'm not sure how that would affect performance; it could
> result in only one thread of an HT processor being used in some cases, but
> OTOH cache utilization might improve in others.

Yeah, I'd agree with that.  HT is always a bit of a mixed bag wrt performance

I suspect it's actually more useful from a performance PoV to give a domain 
two HT threads so it at least has the option of doing some clever scheduling 
(rather than two domains that don't know about each other).  Ideally, we'd 
export CPU topology info to the domains so that they can be aware of this (I 
don't know if we do this right now?  Linux Scheddomains would be able to use 
this).

The other option is to give one thread to a domU and the other thread to a 
driver domain (e.g. dom0).  This is safe (in the sense it doesn't make things 
any worse) since domains that control real hardware can abuse DMA to read 
memory anyway (plus at the moment they have the ability to map domain memory 
directly).  It is also known to improve performance, presumably because of 
improved cache usage, and cheaper IPIs.

Cheers,
Mark

Re: HT Vulnerability CAN-2005-0109

[David Hopwood]

Mark Williamson wrote:
> Sorry I've taken so long to respond!
> 
>>>>It's clear that it is very exploitable.
>>>
>>>On a real world system?
>>
>>Yes.
> 
> I'd be more convinced by a record of a successful exploit on a less restricted 
> workload.  A simplified example for exposition of the problem can still be 
> provided.

Note that Adi Shamir also independently came up with an exploit for this
problem (reported at the Cryptographer's Panel at the RSA security conference
in February 2005), although I don't know the details. See Olin Sibert's
RISKS post at <http://catless.ncl.ac.uk/Risks/23.88.html#subj4>.

>>I think the FreeBSD fix implements the approach suggested in the paper of
>>not scheduling threads with different privileges on the same HT processor.
> 
> For now I think they've just disabled HT (by default) whilst figuring out what 
> the best fix is for the long term.

Yes, you're right:
<ftp://ftp.FreeBSD.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch>

>>In Xen, this would correspond to only giving any particular domain a whole
>>HT processor. I'm not sure how that would affect performance; it could
>>result in only one thread of an HT processor being used in some cases, but
>>OTOH cache utilization might improve in others.
> 
> Yeah, I'd agree with that.  HT is always a bit of a mixed bag wrt performance
> 
> I suspect it's actually more useful from a performance PoV to give a domain 
> two HT threads so it at least has the option of doing some clever scheduling 
> (rather than two domains that don't know about each other).  Ideally, we'd 
> export CPU topology info to the domains so that they can be aware of this (I 
> don't know if we do this right now?  Linux Scheddomains would be able to use 
> this).

I would think that as long as "cpuid" works (or is replaced by a hypercall),
a domain running an HT-aware OS should be able to figure this out in the same
way it does for real hardware.

> The other option is to give one thread to a domU and the other thread to a 
> driver domain (e.g. dom0).  This is safe (in the sense it doesn't make things 
> any worse) since domains that control real hardware can abuse DMA to read 
> memory anyway (plus at the moment they have the ability to map domain memory 
> directly).

However, the domU could spy on the driver domain in that case. How significant
this is depends on what device it is, and whether the driver domain is running
any code vulnerable to side channel analysis.

-- 
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

Re: HT Vulnerability CAN-2005-0109

[Mark Williamson]

> Note that Adi Shamir also independently came up with an exploit for this
> problem (reported at the Cryptographer's Panel at the RSA security
> conference in February 2005), although I don't know the details. See Olin
> Sibert's RISKS post at <http://catless.ncl.ac.uk/Risks/23.88.html#subj4>.

Very interesting - particularly as it's a different exploit!  I wonder what 
he's come up with.  Hopefully some details will be forthcoming.

> > I suspect it's actually more useful from a performance PoV to give a
> > domain two HT threads so it at least has the option of doing some clever
> > scheduling (rather than two domains that don't know about each other). 
> > Ideally, we'd export CPU topology info to the domains so that they can be
> > aware of this (I don't know if we do this right now?  Linux Scheddomains
> > would be able to use this).
>
> I would think that as long as "cpuid" works (or is replaced by a
> hypercall), a domain running an HT-aware OS should be able to figure this
> out in the same way it does for real hardware.

I don't think we use cpuid for HT info at the moment, although that might 
work.  In general, we'd in any case need a notification from Xen to alert 
domains to CPU topology changes (due repinning, etc.).  This is also an issue 
for migration, but that can hook into the existing notification for that.

I suspect this isn't so much an issue now but may become more important as a) 
Xen runs on larger systems and b) Linux integrates a more topology-aware 
scheduling scheme.

> > The other option is to give one thread to a domU and the other thread to
> > a driver domain (e.g. dom0).  This is safe (in the sense it doesn't make
> > things any worse) since domains that control real hardware can abuse DMA
> > to read memory anyway (plus at the moment they have the ability to map
> > domain memory directly).
>
> However, the domU could spy on the driver domain in that case. How
> significant this is depends on what device it is, and whether the driver
> domain is running any code vulnerable to side channel analysis.

Yes, that's true.  Hopefully for most cases this won't be a big issue as long 
as the driver isn't running crypto on behalf of the domains.  I've seen IPSec 
suggested as one potential worry and I guess VLANs, etc could be a problem 
also.

As long as you're not running a crypto service in the driver domain I suspect 
you're (reasonably) safe.  This is another reason to run a slim dom0!

Cheers,
Mark

Re: HT Vulnerability CAN-2005-0109

[Jonathan S. Shapiro]

> Is it possible that two domain kernels running on the same physical core
but on different ht threads leak information to each other exploiting
this covert/side channels?

It is possible. When exploited, this is a fairly high bandwiidth channel. It is possible for the nucleus to prevent this through page coloring. 

All that being said, future processors are moving from HT to multicore. The problem then migrates to the L2 cache, where coloring is much less effective. It is unlikely that there exists any satisfsactory solution short of flushing or disabling the cache, neither of which is pragmatically viable.

Current high assurance requirements don't require that you solve  the channel problem. They require that you characterize them and make a reasonable efffort to minimize them.

Shap

Re: HT Vulnerability CAN-2005-0109

[Mark Williamson]

> All that being said, future processors are moving from HT to multicore. The
> problem then migrates to the L2 cache, where coloring is much less
> effective. It is unlikely that there exists any satisfsactory solution
> short of flushing or disabling the cache, neither of which is pragmatically
> viable.

But the bandwidth for L2 cache channel using this technique will also be lower 
than for the L1.  Additionally, I think the dual core CPUs coming from AMD 
and Intel don't actually share any cache (yet), unlike the dual-core POWER 
products from IBM.

Cheers,
Mark

>
> Current high assurance requirements don't require that you solve  the
> channel problem. They require that you characterize them and make a
> reasonable efffort to minimize them.
>
> Shap
>
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel

Re: HT Vulnerability CAN-2005-0109

[Jonathan S. Shapiro]

On Wed, 2005-05-18 at 17:44 +0100, Mark Williamson wrote:
> > All that being said, future processors are moving from HT to multicore. The
> > problem then migrates to the L2 cache, where coloring is much less
> > effective. It is unlikely that there exists any satisfsactory solution
> > short of flushing or disabling the cache, neither of which is pragmatically
> > viable.
> 
> But the bandwidth for L2 cache channel using this technique will also be lower 
> than for the L1....

This isn't immediately obvious. It depends on how effectively the
transmitter can achieve "line resident in L2 but not in L1".

Re: HT Vulnerability CAN-2005-0109

[Mark Williamson]

> > But the bandwidth for L2 cache channel using this technique will also be
> > lower than for the L1....
>
> This isn't immediately obvious. It depends on how effectively the
> transmitter can achieve "line resident in L2 but not in L1".

OK, I should have qualified that statement :-)  It's a fair cop...

The L2 bandwidth for this channel is lower on current Intel CPUs because you 
have the added complication of TLB misses whilst trying to exploit the covert 
channel.  This is a significant issue because the TLB on the P4 apparently 
can only map half of the address space the cache can hold...

On current P4s the associativity of the L2 is 8 way, rather than 4 way, which 
also reduces the efficiency of the miss-generating technique.

My original statement implicitly assumes that these factors will continue to 
be present as the chips evolve.  If Intel change the TLB size relative to the 
L2 cache, or the associativity of the L1 / L2 caches, then this situation 
could still change.

It's not entirely clear to me how much code for exploiting this channel was 
produced by Colin Percival vs. how much of his data is based on calculated 
estimates.  Does anyone know of a proof-of-concept exploit?

Cheers,
Mark

RE: HT Vulnerability CAN-2005-0109

[Ian Pratt]

 
> At the moment, they release quick workarounds like hardening 
> crypto libs against timing attacks
> 
>   <https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=157631>

This is the correct soloution. I was rather shocked to find the crypto
libs weren't already hardened for such attacks. It's not as though this
is anything new, just a higher bandwidth version of something that has
been known about for years.

> or disabling HT

This is not necessary on Xen. Just allocate domains to CPUs such that
you don't put potentially non-cooperative domains on the same core. E.g.
if you're using dom0 just for running the control tool and device
drivers, just give it one hyperthread and don't allow any other domain
to use it. This is a pretty sensible way to use HT with Xen anyhow.

Ian

RE: HT Vulnerability CAN-2005-0109

[Nils Toedtmann]

Am Donnerstag, den 19.05.2005, 11:59 +0100 schrieb Ian Pratt: 
>  > At the moment, they release quick workarounds like hardening 
> > crypto libs against timing attacks
> > 
> >   <https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=157631>
> 
> This is the correct soloution. I was rather shocked to find the crypto
> libs weren't already hardened for such attacks. It's not as though this
> is anything new, just a higher bandwidth version of something that has
> been known about for years.

This sounds like the arguments i once heard "Since we assume xen runs in
a secure envir protected by a properly configured firewall, it's ok that
xend services listen on 0.0.0.0. Since we assume dom0 only has trusted
local users, it's ok that any user can administer domains through xm". I
consider that approach being wrong.

You are right: crypto libs _should_ be resistant against timing attacks.
But an OS _should_ also eliminate side channels if possible as another
line of defense in case there is some userland/domain-kernel which is
not.

BTW: There are timing attacks against symmetric algorithms like AES:

  <http://www.schneier.com/blog/archives/2005/05/aes_timing_atta_1.html>

Does anybody know, if linux' in-kernel encryption (eg. AES for ipsec or
dm-crypt) is resistant against that ...? 


> > or disabling HT
> 
> This is not necessary on Xen. Just allocate domains to CPUs such that
> you don't put potentially non-cooperative domains on the same core. E.g.
> if you're using dom0 just for running the control tool and device
> drivers, just give it one hyperthread and don't allow any other domain
> to use it. This is a pretty sensible way to use HT with Xen anyhow.

Good point! 

Regards, /nils.