Re: Hyper-Threading Vulnerability

Re: Hyper-Threading Vulnerability

[linux]

The problem is with the *combination* of fine-grained multithreading,
a shared cache, *and* high-resolution timing via RDTSC.

A far easier fix would be to disable RDTSC.
(A third possibility would be to disable the cache, but I assume that's
too horrible to contemplate.)

When Intel implemented RDTSC, they were quite aware that it made a good
covert channel and provided an enable bit (bit 2 of CR4) to control
user-space access.

This attack is just showing that, with the tight coupling provided
by hyperthreading, it's possible to receive "interesting" data from a
process that is *not* deliberately transmitting.  (Whereas the classic
problem enfocing the Bell-Lapadula model comes from preventing
*deliberate* transmission.)


If you don't want to disable it universally, how about providing,
at the OS level, a way for a task to request that RDTSC be disabled
while it is running?  If another task tries to use it, it traps and one
of the two (doesn't matter which!) gets rescheduled later when the other
is not running.

If RDTSC is too annoying to disable, just interpret the same flag as a
"schedule me solo" flag that prevents scheduling anything else (at least,
not sharing the same ->mm) on the other virtual processor.  (Of course,
the time should count double for scheduler fairness purposes.)

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

On Fri, 2005-05-13 at 22:51 +0000, linux@horizon.com wrote:
> If RDTSC is too annoying to disable, just interpret the same flag as a
> "schedule me solo" flag that prevents scheduling anything else (at least,
> not sharing the same ->mm) on the other virtual processor.  (Of course,
> the time should count double for scheduler fairness purposes.)

rdtsc is so unreliable on current hardware that no userspace app should
be using it anyway; it's not synchronized on SMP, powermanagement
impacts the rate of the ticks all the time etc etc.
Basically it's worthless on modern machines for anything but in-kernel
busy loops.

Re: Hyper-Threading Vulnerability

[Bill Davidsen]

On Fri, 13 May 2005, Alan Cox wrote:

> > This is not a kernel problem, but a user space problem. The fix 
> > is to change the user space crypto code to need the same number of cache line
> > accesses on all keys. 
> 
> You actually also need to hit the same cache line sequence on all keys
> if you take a bit more care about it.
> 
> > Disabling HT for this would the totally wrong approach, like throwing
> > out the baby with the bath water.
> 
> HT for most users is pretty irrelevant, its a neat idea but the
> benchmarks don't suggest its too big a hit

This is one of those things which can give any result depending on the
measurement. For kernel compiles I might see a 5-30% reduction in clock
time, for threaded applications like web/mail/news not much, and for
applications which communicate via shared memory up to 50% because some
blocking system calls can be avoided and cache impact is lower.

In general I have to agree with the "too big," but I haven't seen any
indication that the hole can be exploited without being able to run a
custom application on the machine, so for single users machines and
servers the risk level seems low.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: Hyper-Threading Vulnerability

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 713 bytes --]

On Mon, 16 May 2005 13:14:23 MDT, Eric W. Biederman said:

> Interesting.  I think that is a problem for the hypervisor maintainer.
> Although that is about enough to convince me to request a
> OS flag that says "please give me privacy" and later that can be passed
> down to the hypervisor.  My gut feel is running under a hypervisor
> is when things will at their most vulnerable.

Not really, because....

> I think discovering a crypto process will simply be a matter
> finding a https sever.  As for getting the timing how about
> initiating a https connection?  Getting rid of the noise will certainly
> be a challenge but you will have multiple attempts.

And the hypervisor is, if anything, adding noise.

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: Hyper-Threading Vulnerability

[Eric W. Biederman]

Andi Kleen <ak@muc.de> writes:

> > The only solution I have seen proposed so far that seems to work
> > is to not schedule untrusted processes simultaneously with 
> > the security code.  With the current API that sounds like
> > a root process killing off, or at least stopping all non-root
> > processes until the critical process has finished.
> 
> With virtualization and a hypervisor freely scheduling it is quite 
> impossible to guarantee this. Of course as always the signal 
> is quite noisy so it is unclear if it is exploitable in practical 
> settings. On virtualized environments you cannot use ps to see
> if a crypto process is running. 

Interesting.  I think that is a problem for the hypervisor maintainer.
Although that is about enough to convince me to request a
OS flag that says "please give me privacy" and later that can be passed
down to the hypervisor.  My gut feel is running under a hypervisor
is when things will at their most vulnerable.

Where this is a threat is when there will be a lot of RSA
key transactions.  At which point it is likely that the attacker
can reproduce enough of the setup to figure out the fine details.

I think discovering a crypto process will simply be a matter
finding a https sever.  As for getting the timing how about
initiating a https connection?  Getting rid of the noise will certainly
be a challenge but you will have multiple attempts.

> > And those same processors will have the same problem if the share
> > significant cpu resources.  Ideally the entire problem set
> > would fit in the cache and the cpu designers would allow cache
> > blocks to be locked but that is not currently the case.  So a shared
> > L3 cache with dual core processors will have the same problem.
> 
> At some point the signal gets noisy enough and the assumptions
> an attacker has to make too great for it being an useful attack.
> For me it is not even clear it is a real attack on native Linux, at 
> least the setup in the paper looked highly artifical and quite impractical. 
> e.g. I suppose it would be quite difficult to really synchronize
> to the beginning and end of the RSA encryptions on a server that
> does other things too.

Possibly.  But then buffer overflow attacks when you don't know the exact
stack layout are similarly difficult and ways have been found.  And if
you have multiple chances things get easier.  And if you are aiming
at something easier then brute forcing a private key even the littlest
bit is a help.

When people mmap pages we zero them for the same reason so that
we don't have unintentional information leaks.

I agree that for now because little is known this is a highly specialized
attack.  However the trend is now towards increasingly big SMP's.
That increases the number of resources that can be shared so the
possibility of a problem increases.  At the rate Intel's cpus are
going we may see throttling of one cpu core when the other one
generates too much heat, because it is busy doing something else cpu
intensive.  And other optimizations lead to much easier to imagine
vulnerabilities.

As for noise with the area cpu designers are getting into things
are becoming increasingly fine grained so information is leaking
at an increasingly fine level.  As the L2 cache issue has shown
that information starts to leak below the level an application
designer has control of.  At which point things get very difficult
to manage.  

Information leaks are more difficult than simply gaining root on
the box where you can simply take the information you want.  But
that means that is exactly where a locked down well administered
box will be vulnerable if a way is not found to avoid the problem.
I don't know what the consequences of having your private key
discovered are, but I have never heard a case where identity theft
was something pleasant to fix.

Eric

Re: Hyper-Threading Vulnerability

[Linus Torvalds]

On Fri, 13 May 2005, Scott Robert Ladd wrote:
>
> Alan Cox wrote:
> > HT for most users is pretty irrelevant, its a neat idea but the
> > benchmarks don't suggest its too big a hit
> 
> On real-world applications, I haven't seen HT boost performance by more
> than 15% on a Pentium 4 -- and the usual gain is around 5%, if anything
> at all. HT is a nice idea, but I don't enable it on my systems.

HT is _wonderful_ for latency reduction. 

Why people think "performace" means "throughput" is something I'll never
understand. Throughput is _always_ secondary to latency, and really only
becomes interesting when it becomes a latency number (ie "I need higher
throughput in order to process these jobs in 4 hours instead of 8" -
notice how the real issue was again about _latency_).

Now, Linux tends to have pretty good CPU latency anyway, so it's not
usually that big of a deal, but I definitely enjoyed having a HT machine
over a regular UP one. I'm told the effect was even more pronounced on 
XP. 

Of course, these days I enjoy having dual cores more, though, and with
multiple cores, the latency advantages of HT become much less pronounced.

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, or necessarily seem all that
worrying in real life.

(HT and modern CPU speeds just means that the covert channel is _faster_
than it has been before, since you can test the L1 at core speeds. I doubt
it helps the key attack much, though, since faster in that case cuts both
ways: the speed of testing the cache eviction may have gone up, but so has
the speed of the operation you're trying to follow, and you'd likely have
a really hard time trying to catch things in real life).

It does show that if you want to hide key operations, you want to be 
careful. I don't think HT is at fault per se. 

		Linus

Re: Hyper-Threading Vulnerability

[Andrea Arcangeli]

On Fri, May 13, 2005 at 05:39:25PM -0700, dean gaudet wrote:
> same cache index -- and get an 8-fold reduction in exposure.  the trick 
> here is the L2 is physically indexed, and userland code can perform only 
> virtual allocations.  but it's not too hard to discover physical conflicts 
> if you really want to (using rdtsc) -- it would be done early in the 
> initialization of the program because it involves asking for enough memory 
> until the kernel gives you enough colliding pages.  (a system call could 
> help with this if we really wanted it.)

A 8-way set associative 1M cache is guaranteed to go at l2 speed only
up to 128K (no matter what the kernel does), but even if the secret
payload is larger than 128K as long as the load is still distributed
evenly at each pass for each page, there's not going to be any covert
channel, simply the process will run slower than it could if it had a
better page coloring.

So I don't see the need of kernel support, all it needs to do is to know
the page size, and that's provided to userland already.

Re: Hyper-Threading Vulnerability

[Tommy Reynolds]

[-- Attachment #1: Type: text/plain, Size: 1099 bytes --]

Uttered Linus Torvalds <torvalds@osdl.org>, spake thus:

> It does show that if you want to hide key operations, you want to be 
> careful. I don't think HT is at fault per se.

Trivially easy when two processes share the same FS namespace.
Consider two files:

$ ls -l /tmp/a /tmp/b
-rw------ 1 owner owner xxxxx /tmp/a
-rw------ 1 owner owner xxxxx /tmp/b

One file serves as a clock.  Note that the permissions deny all
access to everyone except the owner.  The owner user then does this,
intentionally or unintentionally:

for x in 0 0 0 1 0 0 0 0 0 1
do
	rm -f /tmp/a /tmp/b
	case "$x" in
	0 )	rm -f /tmp/a;;
	1 )	touch /tmp/a;;
	esac
	touch /tmp/b
	sleep	2
done

And the baddie does this:

let n=1
let char=0
while (($n < 8))
do
	while [ ! -f /tmp/b ]; do
		sleep 0.5
	done
	let char=((char << 1))
	if [ -f /tmp/a ]; do
		let char=((char + 1))
	done
done
printf "The letter was: %c\n" $char

This is one of the classic TEMPEST problems that secure systems have
long had to deal with.  See, at no time did HT ever raise its ugly
head ;-)

Cheers

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: Hyper-Threading Vulnerability

[Andi Kleen]

> The only solution I have seen proposed so far that seems to work
> is to not schedule untrusted processes simultaneously with 
> the security code.  With the current API that sounds like
> a root process killing off, or at least stopping all non-root
> processes until the critical process has finished.

With virtualization and a hypervisor freely scheduling it is quite 
impossible to guarantee this. Of course as always the signal 
is quite noisy so it is unclear if it is exploitable in practical 
settings. On virtualized environments you cannot use ps to see
if a crypto process is running. 

> And those same processors will have the same problem if the share
> significant cpu resources.  Ideally the entire problem set
> would fit in the cache and the cpu designers would allow cache
> blocks to be locked but that is not currently the case.  So a shared
> L3 cache with dual core processors will have the same problem.

At some point the signal gets noisy enough and the assumptions
an attacker has to make too great for it being an useful attack.
For me it is not even clear it is a real attack on native Linux, at 
least the setup in the paper looked highly artifical and quite impractical. 
e.g. I suppose it would be quite difficult to really synchronize
to the beginning and end of the RSA encryptions on a server that
does other things too.

-Andi

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

On Sun, 2005-05-15 at 19:10 -0400, Lee Revell wrote:
> On Sun, 2005-05-15 at 18:55 -0400, Dave Jones wrote:
> > On Sun, May 15, 2005 at 05:10:59PM -0400, Lee Revell wrote:
> >  > On Sun, 2005-05-15 at 22:48 +0200, Arjan van de Ven wrote:
> >  > > On Sun, 2005-05-15 at 21:41 +0100, Alan Cox wrote:
> >  > > > On Sul, 2005-05-15 at 08:30, Arjan van de Ven wrote:
> >  > > > > stop entirely.... (and that is also happening more and more and linux is
> >  > > > > getting more agressive idle support (eg no timer tick and such patches)
> >  > > > > which will trigger bios thresholds for this even more too.
> >  > > > 
> >  > > > Cyrix did TSC stop on halt a long long time ago, back when it was worth
> >  > > > the power difference.
> >  > > 
> >  > > With linux going to ACPI C2 mode more... tsc is defined to halt in C2...
> >  > 
> >  > JACK doesn't care about any of this now, the behavior when you
> >  > suspend/resume with a running jackd is undefined.  Eventually we should
> >  > handle it, but there's no point until the ALSA drivers get proper
> >  > suspend/resume support.
> > 
> > suspend/resume are S states, not C states. C states are occuring
> > during runtime.
> 
> It should never go into C2 if jackd is running, because you're getting
> interrupts from the audio interface at least every 100ms or so (usually
> much more often) which will wake up jackd and any clients.

you're not guaranteed to not enter C2 in that case. C2 can happen after
a few ms already

Re: Hyper-Threading Vulnerability

[Eric W. Biederman]

Andi Kleen <ak@muc.de> writes:

> On Fri, May 13, 2005 at 02:26:20PM -0700, Andy Isaacson wrote:
> > On Fri, May 13, 2005 at 09:05:49PM +0200, Andi Kleen wrote:
> > > On Fri, May 13, 2005 at 02:38:03PM -0400, Richard F. Rebel wrote:
> > > > Why?  It's certainly reasonable to disable it for the time being and
> > > > even prudent to do so.
> > > 
> > > No, i strongly disagree on that. The reasonable thing to do is
> > > to fix the crypto code which has this vulnerability, not break
> > > a useful performance enhancement for everybody else.
> > 
> > Pardon me for saying so, but that's bullshit.  You're asking the crypto
> > guys to give up a 5x performance gain (that's my wild guess) by giving
> > up all their data-dependent algorithms and contorting their code wildly,
> > to avoid a microarchitectural problem with Intel's HT implementation.
> 
> And what you're doing is to ask all the non crypto guys to give
> up an useful optimization just to fix a problem in the crypto guy's
> code. The cache line information leak is just a information leak
> bug in the crypto code, not a general problem.

It is not a problem in the crypto code, it is a mis-feature of
the hardware/kernel combination.  As such you must know be intimate
about each and every flavor of the hardware to attempt to avoid
it in the software, and that way lies madness.

First this is a reminder that prefect security requires an audit
of the hardware as well as the software.  As we are neither
auditing the hardware not locking it down we obviously will not
achieve perfection.  The question then becomes what can be done
to decrease the likely hood that an application will inadvertently
and unavoidably leak information from timing attacks due to unknown
hardware optimizations?  Attacks that do not result from hardware
micro-architecture are another problem and one an application can
anticipate and avoid.

Ideally a solution will be proposed that will allow this problem
to be avoided using the existing POSIX API or at least the current
linux kernel API.  But that problem may not be the case.

The only solution I have seen proposed so far that seems to work
is to not schedule untrusted processes simultaneously with 
the security code.  With the current API that sounds like
a root process killing off, or at least stopping all non-root
processes until the critical process has finished.

Potentially the scheduler can be modified to do this at a finer
grain but I don't know if this would impact the scheduler fast
path.  Given the rarity and uncertainty of this it should probably
be something that the process that is worried about security should
asks for instead of simply getting by default.

So it looks to me like the sanest way to handle this is to
allocate a pool of threads/processes one per cpu.  Set the
affinity of each process to a particular cpu.  And set priority
of the threads to run at the highest priority.  And during the
critical time ensure none of the threads are sleeping.

Can someone see a better way to prevent an accidental information
leak to do to hardware architecture details?   

I wish there was a better way to ensure all of the threads were
running simultaneously and other then giving them the highest priority 
in the system but I don't currently see an alternative.

> There is much more non crypto code than crypto code around - you
> are proposing to screw the majority of codes to solve a relatively
> obscure problem of only a few functions, which seems like the totally
> wrong approach to me.
> 
> BTW the crypto guys are always free to check for hyperthreading
> themselves and use different functions.  However there is a catch
> there - the modern dual core processors which actually have
> separated L1 and L2 caches set these too to stay compatible
> with old code and license managers.

And those same processors will have the same problem if the share
significant cpu resources.  Ideally the entire problem set
would fit in the cache and the cpu designers would allow cache
blocks to be locked but that is not currently the case.  So a shared
L3 cache with dual core processors will have the same problem.

In addition a flavor of this attack may be made by repeatedly doing
multiplies or other activities that access functional units and seeing
how long they have to be waited for.  So even hyperthreading without
sharing a L2 cache may see this problem.

Eric

Re: Hyper-Threading Vulnerability

[andrea]

On Sun, May 15, 2005 at 03:38:22PM +0200, Mikulas Patocka wrote:
> Another possibility to get timing is from direct-io --- i.e. initiate
> direct io read, wait until one cache line contains new data and you can be
> sure that the next will contain new data in certain time. IDE controller
> bus master operation acts here as a timer.

There's no way to do direct-io through seccomp, all the fds are pipes
with twisted userland listening the other side of the pipe. So disabling
the tsc is more than enough to give to CPUShare users a peace of mind
with HT enabled and without having to flush the l2 cache either.
CPUShare is the only case I can imagine where an untrusted and random
bytecode running at 100% system load is the normal behaviour.

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Sun, 2005-05-15 at 18:55 -0400, Dave Jones wrote:
> On Sun, May 15, 2005 at 05:10:59PM -0400, Lee Revell wrote:
>  > On Sun, 2005-05-15 at 22:48 +0200, Arjan van de Ven wrote:
>  > > On Sun, 2005-05-15 at 21:41 +0100, Alan Cox wrote:
>  > > > On Sul, 2005-05-15 at 08:30, Arjan van de Ven wrote:
>  > > > > stop entirely.... (and that is also happening more and more and linux is
>  > > > > getting more agressive idle support (eg no timer tick and such patches)
>  > > > > which will trigger bios thresholds for this even more too.
>  > > > 
>  > > > Cyrix did TSC stop on halt a long long time ago, back when it was worth
>  > > > the power difference.
>  > > 
>  > > With linux going to ACPI C2 mode more... tsc is defined to halt in C2...
>  > 
>  > JACK doesn't care about any of this now, the behavior when you
>  > suspend/resume with a running jackd is undefined.  Eventually we should
>  > handle it, but there's no point until the ALSA drivers get proper
>  > suspend/resume support.
> 
> suspend/resume are S states, not C states. C states are occuring
> during runtime.

It should never go into C2 if jackd is running, because you're getting
interrupts from the audio interface at least every 100ms or so (usually
much more often) which will wake up jackd and any clients.

Lee

Re: Hyper-Threading Vulnerability

[Dave Jones]

On Sun, May 15, 2005 at 05:10:59PM -0400, Lee Revell wrote:
 > On Sun, 2005-05-15 at 22:48 +0200, Arjan van de Ven wrote:
 > > On Sun, 2005-05-15 at 21:41 +0100, Alan Cox wrote:
 > > > On Sul, 2005-05-15 at 08:30, Arjan van de Ven wrote:
 > > > > stop entirely.... (and that is also happening more and more and linux is
 > > > > getting more agressive idle support (eg no timer tick and such patches)
 > > > > which will trigger bios thresholds for this even more too.
 > > > 
 > > > Cyrix did TSC stop on halt a long long time ago, back when it was worth
 > > > the power difference.
 > > 
 > > With linux going to ACPI C2 mode more... tsc is defined to halt in C2...
 > 
 > JACK doesn't care about any of this now, the behavior when you
 > suspend/resume with a running jackd is undefined.  Eventually we should
 > handle it, but there's no point until the ALSA drivers get proper
 > suspend/resume support.

suspend/resume are S states, not C states. C states are occuring
during runtime.

		Dave

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Sun, 2005-05-15 at 22:48 +0200, Arjan van de Ven wrote:
> On Sun, 2005-05-15 at 21:41 +0100, Alan Cox wrote:
> > On Sul, 2005-05-15 at 08:30, Arjan van de Ven wrote:
> > > stop entirely.... (and that is also happening more and more and linux is
> > > getting more agressive idle support (eg no timer tick and such patches)
> > > which will trigger bios thresholds for this even more too.
> > 
> > Cyrix did TSC stop on halt a long long time ago, back when it was worth
> > the power difference.
> 
> With linux going to ACPI C2 mode more... tsc is defined to halt in C2...

JACK doesn't care about any of this now, the behavior when you
suspend/resume with a running jackd is undefined.  Eventually we should
handle it, but there's no point until the ALSA drivers get proper
suspend/resume support.

Lee

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

On Sun, 2005-05-15 at 21:41 +0100, Alan Cox wrote:
> On Sul, 2005-05-15 at 08:30, Arjan van de Ven wrote:
> > stop entirely.... (and that is also happening more and more and linux is
> > getting more agressive idle support (eg no timer tick and such patches)
> > which will trigger bios thresholds for this even more too.
> 
> Cyrix did TSC stop on halt a long long time ago, back when it was worth
> the power difference.

With linux going to ACPI C2 mode more... tsc is defined to halt in C2...

Re: Hyper-Threading Vulnerability

[Alan Cox]

On Sul, 2005-05-15 at 08:30, Arjan van de Ven wrote:
> stop entirely.... (and that is also happening more and more and linux is
> getting more agressive idle support (eg no timer tick and such patches)
> which will trigger bios thresholds for this even more too.

Cyrix did TSC stop on halt a long long time ago, back when it was worth
the power difference.

Alan

Re: Hyper-Threading Vulnerability

[Dr. David Alan Gilbert]

* David Schwartz (davids@webmaster.com) wrote:
> 
> Andi Kleen wrote:
> 
> > And what you're doing is to ask all the non crypto guys to give
> > up an useful optimization just to fix a problem in the crypto guy's
> > code. The cache line information leak is just a information leak
> > bug in the crypto code, not a general problem.
> 
> 	Portable code shouldn't even have to know that there is such a thing as a
> cache line. It should be able to rely on the operating system not to let
> other tasks with a different security context spy on the details of its
> operation.

I find it interesting to compare this thread with a thread from about
a week ago talking about how /proc/cpuinfo wasn't consistent
across architectures - where we come round to the view of whether
the application writers shouldn't care/are too dumb/shouldn't need
to know about/can't be trusted  with knowing about what the real
hardware is.

Personally I think this is a good case of where the application
should take care of it - with whatever support the OS can really
give.

(That is if this is actually a real problem and not just
purely theoretical - my crypto knowledge isn't good enough
to answer that - but it feels very very abstract).

Dave
 -----Open up your eyes, open up your mind, open up your code -------   
/ Dr. David Alan Gilbert    | Running GNU/Linux on Alpha,68K| Happy  \ 
\ gro.gilbert @ treblig.org | MIPS,x86,ARM,SPARC,PPC & HPPA | In Hex /
 \ _________________________|_____ http://www.treblig.org   |_______/

RE: Hyper-Threading Vulnerability

[David Schwartz]

Andi Kleen wrote:

> And what you're doing is to ask all the non crypto guys to give
> up an useful optimization just to fix a problem in the crypto guy's
> code. The cache line information leak is just a information leak
> bug in the crypto code, not a general problem.

	Portable code shouldn't even have to know that there is such a thing as a
cache line. It should be able to rely on the operating system not to let
other tasks with a different security context spy on the details of its
operation.

> There is much more non crypto code than crypto code around - you
> are proposing to screw the majority of codes to solve a relatively
> obscure problem of only a few functions, which seems like the totally
> wrong approach to me.

	That I do agree with.

> BTW the crypto guys are always free to check for hyperthreading
> themselves and use different functions.  However there is a catch
> there - the modern dual core processors which actually have
> separated L1 and L2 caches set these too to stay compatible
> with old code and license managers.

	This is just a recipe for making it impossible to write correct code. If
you don't believe the operating system or the hardware is at all at fault
for this problem, then it would follow that they could repeat this same
problem with some new mechanism and still not be at fault. So even if the
program checked for hyper-threading, it would still not be correct. It would
have to check for every possible future way this same type of problem could
arise and hide every type of trace that they could create, even if that
trace is in optimization mechanisms and potential channels over which the
programmer has no knowledge because they don't exist yet.

	Let's try a rudctio ad absurdum. Surely you would agree that something
other than than the crypto software is at fault if the operating system or
hardware allowed another process with a different security context to see
every instruction the code executed. The crypto authors shouldn't be
expected to make the instruction flows look identical. How different is
monitoring the memory accesses?

	Portable, POSIX-compliant C software shouldn't even have to know that there
is such a thing as a cache line.

	I'm not going to be unreasonable though. Hyper-threading is here, and now
that we know the potential problems, it's not unreasonable to ask developers
of crypto code to work around it. But it's not a bug in their code that they
need to fix. In fact, they can't even fix it yet because there is no
portable way to determine if you're on a machine that has hyper-threading or
not.

	DS

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

> > They turned it off by default, which according to disk vendors
> > lowers the MTBF of your disk to a fraction of the original value.
> > 
> > I bet the total amount of valuable data lost for FreeBSD users because
> > of broken disks is much much bigger than what they gained from not losing
> > in the rather hard to hit power off cases.
> 
>  Aren't I/O barriers a way to safely use write cache?

yes they are. However of course they also decrease the mtbf somewhat,
although less so than entirely disabling the cache....

Re: Hyper-Threading Vulnerability

[Tomasz Torcz]

On Sun, May 15, 2005 at 04:12:07PM +0200, Andi Kleen wrote:
> > > > However they've patched the FreeBSD kernel to "workaround?" it:
> > > > ftp://ftp.freebsd.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch
> > >
> > > That's a similar stupid idea as they did with the disk write
> > > cache (lowering the MTBFs of their disks by considerable factors,
> > > which is much worse than the power off data loss problem)
> > > Let's not go down this path please.
> > 
> > What wrong did they do with disk write cache?
> 
> They turned it off by default, which according to disk vendors
> lowers the MTBF of your disk to a fraction of the original value.
> 
> I bet the total amount of valuable data lost for FreeBSD users because
> of broken disks is much much bigger than what they gained from not losing
> in the rather hard to hit power off cases.

 Aren't I/O barriers a way to safely use write cache?

-- 
Tomasz Torcz                 "God, root, what's the difference?"
zdzichu@irc.-nie.spam-.pl         "God is more forgiving."

Re: Hyper-Threading Vulnerability

[Andi Kleen]

> There are three places to cut off the side channel, none of which is
> obviously the right one.
> 1. The HT implementation could do the cache tricks Colin suggested in
>    his paper.  Fairly large performance hit to address a fairly small
>    problem.

As Dean pointed out that is probably not true.

> 2. The OS could do the scheduler tricks to avoid scheduling unfriendly
>    threads on the same core.  You're leaving a lot of the benefit of HT
>    on the floor by doing so.

And probably still lose badly in some workloads.

> 3. Every security-sensitive app can be rigorously audited and re-written
>    to avoid *ever* referencing memory with the address determined by
>    private data.

Sure after it was demonstrated that this attack is actually feasible
in practice. If yes then fix the crypto code, otherwise do nothing.

I have no problem with crypto people being paranoid (that is their
job after all), as long as they don't try to affect non crypto code
in the process. But the later seems to be clearly the case here :-(
> 
> (3) is a complete non-starter.  It's just not feasible to rewrite all
> that code.  Furthermore, there's no way to know what code needs to be
> rewritten!  (Until someone publishes an advisory, that is...)
> 
> Hmm, I can't think of any reason that this technique wouldn't work to
> extract information from kernel secrets, as well... 
> 
> If SHA has plaintext-dependent memory references, Colin's technique
> would enable an adversary to extract the contents of the /dev/random
> pools.  I don't *think* SHA does, based on a quick reading of
> lib/sha1.c, but someone with an actual clue should probably take a look.
> 
> Andi, are you prepared to *require* that no code ever make a memory
> reference as a function of a secret?  Because that's what you're
> suggesting the crypto people should do.

No, just not do it frequently enough that you leak enough data.
Or add dummy memory references to blend your data.

And then nobody said writing crypto code was easy. It just got a bit
harder today.

It is basically like writing smart card code, where you need
to care about such side channels. The other crypto code writers
just need to care about this too.  They will probably avoid
other timing attacks on cache misses too with this approach. Although 
it is doubtful enough signal is leaked in this way, e.g. if you time the 
performance of a network server with RSA answering over the network -
but you see some data is always leaked - the question is just
if it is enough and accurate data to aid an attacker. The paper
has shown that it is feasible in some cases, but so far the proof
is still out this could be actually replicated in not very controlled
loads. With more noise in the data it becomes harder. And the question
is is the small amount of data with normal background workload
is really useful enough to lead to useful real world attacks. I have
severe doubts on that. Certainly the effidence is not clear enough
for a serious step like disabling an  useful performance enhancement like
HT.

-Andi

P.S.: My personal opinion is that we have a far bigger crypto security
problem on many system due to weak /dev/random seeding on many systems. 
If anything is done it would be better to attack that.

Re: Hyper-Threading Vulnerability

[Mikulas Patocka]

On Sun, 15 May 2005, Andi Kleen wrote:

> On Sun, May 15, 2005 at 03:51:05PM +0200, Mikulas Patocka wrote:
> >
> >
> > On Sun, 15 May 2005, Andi Kleen wrote:
> >
> > > On Fri, May 13, 2005 at 09:16:09PM +0200, Diego Calleja wrote:
> > > > El Fri, 13 May 2005 20:03:58 +0200,
> > > > Andi Kleen <ak@muc.de> escribi?:
> > > >
> > > >
> > > > > This is not a kernel problem, but a user space problem. The fix
> > > > > is to change the user space crypto code to need the same number of cache line
> > > > > accesses on all keys.
> > > >
> > > >
> > > > However they've patched the FreeBSD kernel to "workaround?" it:
> > > > ftp://ftp.freebsd.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch
> > >
> > > That's a similar stupid idea as they did with the disk write
> > > cache (lowering the MTBFs of their disks by considerable factors,
> > > which is much worse than the power off data loss problem)
> > > Let's not go down this path please.
> >
> > What wrong did they do with disk write cache?
>
> They turned it off by default, which according to disk vendors
> lowers the MTBF of your disk to a fraction of the original value.
>
> I bet the total amount of valuable data lost for FreeBSD users because
> of broken disks is much much bigger than what they gained from not losing
> in the rather hard to hit power off cases.
>
> -Andi

BTW. Is there any blacklist of disks with broken FLUSH CACHE command? Or a
list of companies that cheat in implementation of it?

Mikulas

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Sun, May 15, 2005 at 03:51:05PM +0200, Mikulas Patocka wrote:
> 
> 
> On Sun, 15 May 2005, Andi Kleen wrote:
> 
> > On Fri, May 13, 2005 at 09:16:09PM +0200, Diego Calleja wrote:
> > > El Fri, 13 May 2005 20:03:58 +0200,
> > > Andi Kleen <ak@muc.de> escribi?:
> > >
> > >
> > > > This is not a kernel problem, but a user space problem. The fix
> > > > is to change the user space crypto code to need the same number of cache line
> > > > accesses on all keys.
> > >
> > >
> > > However they've patched the FreeBSD kernel to "workaround?" it:
> > > ftp://ftp.freebsd.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch
> >
> > That's a similar stupid idea as they did with the disk write
> > cache (lowering the MTBFs of their disks by considerable factors,
> > which is much worse than the power off data loss problem)
> > Let's not go down this path please.
> 
> What wrong did they do with disk write cache?

They turned it off by default, which according to disk vendors
lowers the MTBF of your disk to a fraction of the original value.

I bet the total amount of valuable data lost for FreeBSD users because
of broken disks is much much bigger than what they gained from not losing
in the rather hard to hit power off cases.

-Andi

Re: Hyper-Threading Vulnerability

[Mikulas Patocka]

On Fri, 13 May 2005, Andy Isaacson wrote:

> On Fri, May 13, 2005 at 09:05:49PM +0200, Andi Kleen wrote:
> > On Fri, May 13, 2005 at 02:38:03PM -0400, Richard F. Rebel wrote:
> > > Why?  It's certainly reasonable to disable it for the time being and
> > > even prudent to do so.
> >
> > No, i strongly disagree on that. The reasonable thing to do is
> > to fix the crypto code which has this vulnerability, not break
> > a useful performance enhancement for everybody else.
>
> Pardon me for saying so, but that's bullshit.  You're asking the crypto
> guys to give up a 5x performance gain (that's my wild guess) by giving
> up all their data-dependent algorithms and contorting their code wildly,
> to avoid a microarchitectural problem with Intel's HT implementation.

That information leak can be exploited not only on HT or SMP, but on any
CPU with L2 cache. Without HT it's much harder to get information about L2
cache footprint, but it's still possible. If an attacker can make
unlimited number of connections to ssh or http server and manages to get 1
bit in 100 connections, it's still a problem.

Possible solutions:
1) don't use branches and data-dependent memory accesses depending on
secret data
2) flush cache completely when switching to process with different EUID
(0.2ms on Pentium 4 with 1M cache, even worse on CPUs with more cache).

Disabling HT/SMP is not a solution. A year later someone may come with
something like this:
* prefill L2 cache with known pattern
* sleep on some precious timer
* make connection to security application (ssh, https)
* on wakeup, read what's in L2 cache --- get one bit with small
probability --- but when repeated many times, it's still a problem

Mikulas

> There are three places to cut off the side channel, none of which is
> obviously the right one.
> 1. The HT implementation could do the cache tricks Colin suggested in
>    his paper.  Fairly large performance hit to address a fairly small
>    problem.
> 2. The OS could do the scheduler tricks to avoid scheduling unfriendly
>    threads on the same core.  You're leaving a lot of the benefit of HT
>    on the floor by doing so.
> 3. Every security-sensitive app can be rigorously audited and re-written
>    to avoid *ever* referencing memory with the address determined by
>    private data.
>
> (3) is a complete non-starter.  It's just not feasible to rewrite all
> that code.  Furthermore, there's no way to know what code needs to be
> rewritten!  (Until someone publishes an advisory, that is...)
>
> Hmm, I can't think of any reason that this technique wouldn't work to
> extract information from kernel secrets, as well...
>
> If SHA has plaintext-dependent memory references, Colin's technique
> would enable an adversary to extract the contents of the /dev/random
> pools.  I don't *think* SHA does, based on a quick reading of
> lib/sha1.c, but someone with an actual clue should probably take a look.
>
> Andi, are you prepared to *require* that no code ever make a memory
> reference as a function of a secret?  Because that's what you're
> suggesting the crypto people should do.
>
> -andy
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: Hyper-Threading Vulnerability

[Mikulas Patocka]

On Sun, 15 May 2005, Andi Kleen wrote:

> On Fri, May 13, 2005 at 09:16:09PM +0200, Diego Calleja wrote:
> > El Fri, 13 May 2005 20:03:58 +0200,
> > Andi Kleen <ak@muc.de> escribi?:
> >
> >
> > > This is not a kernel problem, but a user space problem. The fix
> > > is to change the user space crypto code to need the same number of cache line
> > > accesses on all keys.
> >
> >
> > However they've patched the FreeBSD kernel to "workaround?" it:
> > ftp://ftp.freebsd.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch
>
> That's a similar stupid idea as they did with the disk write
> cache (lowering the MTBFs of their disks by considerable factors,
> which is much worse than the power off data loss problem)
> Let's not go down this path please.

What wrong did they do with disk write cache?

Mikulas

> -Andi
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: Hyper-Threading Vulnerability

[Mikulas Patocka]

On Sat, 14 May 2005 andrea@cpushare.com wrote:

> On Sat, May 14, 2005 at 04:23:10PM +0100, Alan Cox wrote:
> > You cannot use rdtsc for anything but rough instruction timing. The
> > timers for different processors run at different speeds on some SMP
> > systems, the timer rates vary as processors change clock rate nowdays.
> > Rdtsc may also jump dramatically on a suspend/resume.
>
> x86-64 uses it for vgettimeofday very safely (i386 could do too but it
> doesn't).
>
> Anyway I believe at least for seccomp it's worth to turn off the tsc,
> not just for HT but for the L2 cache too. So it's up to you, either you
> turn it off completely (which isn't very nice IMHO) or I recommend to
> apply this below patch. This has been tested successfully on x86-64
> against current cogito repository (i686 compiles so I didn't bother
> testing ;). People selling the cpu through cpushare may appreciate this
> bit for a peace of mind. There's no way to get any timing info anymore
> with this applied (gettimeofday is forbidden of course).

Another possibility to get timing is from direct-io --- i.e. initiate
direct io read, wait until one cache line contains new data and you can be
sure that the next will contain new data in certain time. IDE controller
bus master operation acts here as a timer.

Mikulas

> The seccomp
> environment is completely deterministic so it can't be allowed to get
> timing info, it has to be deterministic so in the future I can enable a
> computing mode that does a parallel computing for each task with server
> side transparent checkpointing and verification that the output is the
> same from all the 2/3 seller computers for each task, without the buyer
> even noticing (for now the verification is left to the buyer client
> side and there's no checkpointing, since that would require more kernel
> changes to track the dirty bits but it'll be easy to extend once the
> basic mode is finished).
>
> Thanks.
>
> Signed-off-by: Andrea Arcangeli <andrea@cpushare.com>
>
> Index: arch/i386/kernel/process.c
> ===================================================================
> --- eed337ef5e9ae7d62caa84b7974a11fddc7f06e0/arch/i386/kernel/process.c  (mode:100644)
> +++ uncommitted/arch/i386/kernel/process.c  (mode:100644)
> @@ -561,6 +561,25 @@
>  }
>
>  /*
> + * This function selects if the context switch from prev to next
> + * has to tweak the TSC disable bit in the cr4.
> + */
> +static void disable_tsc(struct thread_info *prev,
> +			struct thread_info *next)
> +{
> +	if (unlikely(has_secure_computing(prev) ||
> +		     has_secure_computing(next))) {
> +		/* slow path here */
> +		if (has_secure_computing(prev) &&
> +		    !has_secure_computing(next)) {
> +			clear_in_cr4(X86_CR4_TSD);
> +		} else if (!has_secure_computing(prev) &&
> +			   has_secure_computing(next))
> +			set_in_cr4(X86_CR4_TSD);
> +	}
> +}
> +
> +/*
>   *	switch_to(x,yn) should switch tasks from x to y.
>   *
>   * We fsave/fwait so that an exception goes off at the right time
> @@ -639,6 +658,8 @@
>  	if (unlikely(prev->io_bitmap_ptr || next->io_bitmap_ptr))
>  		handle_io_bitmap(next, tss);
>
> +	disable_tsc(prev_p->thread_info, next_p->thread_info);
> +
>  	return prev_p;
>  }
>
> Index: arch/x86_64/kernel/process.c
> ===================================================================
> --- eed337ef5e9ae7d62caa84b7974a11fddc7f06e0/arch/x86_64/kernel/process.c  (mode:100644)
> +++ uncommitted/arch/x86_64/kernel/process.c  (mode:100644)
> @@ -439,6 +439,25 @@
>  }
>
>  /*
> + * This function selects if the context switch from prev to next
> + * has to tweak the TSC disable bit in the cr4.
> + */
> +static void disable_tsc(struct thread_info *prev,
> +			struct thread_info *next)
> +{
> +	if (unlikely(has_secure_computing(prev) ||
> +		     has_secure_computing(next))) {
> +		/* slow path here */
> +		if (has_secure_computing(prev) &&
> +		    !has_secure_computing(next)) {
> +			clear_in_cr4(X86_CR4_TSD);
> +		} else if (!has_secure_computing(prev) &&
> +			   has_secure_computing(next))
> +			set_in_cr4(X86_CR4_TSD);
> +	}
> +}
> +
> +/*
>   * This special macro can be used to load a debugging register
>   */
>  #define loaddebug(thread,r) set_debug(thread->debugreg ## r, r)
> @@ -556,6 +575,8 @@
>  		}
>  	}
>
> +	disable_tsc(prev_p->thread_info, next_p->thread_info);
> +
>  	return prev_p;
>  }
>
> Index: include/linux/seccomp.h
> ===================================================================
> --- eed337ef5e9ae7d62caa84b7974a11fddc7f06e0/include/linux/seccomp.h  (mode:100644)
> +++ uncommitted/include/linux/seccomp.h  (mode:100644)
> @@ -19,6 +19,11 @@
>  		__secure_computing(this_syscall);
>  }
>
> +static inline int has_secure_computing(struct thread_info *ti)
> +{
> +	return unlikely(test_ti_thread_flag(ti, TIF_SECCOMP));
> +}
> +
>  #else /* CONFIG_SECCOMP */
>
>  #if (__GNUC__ > 2)
> @@ -28,6 +33,7 @@
>  #endif
>
>  #define secure_computing(x) do { } while (0)
> +#define has_secure_computing(x) 0
>
>  #endif /* CONFIG_SECCOMP */
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Sat, May 14, 2005 at 08:01:33PM +0200, Arjan van de Ven wrote:
> On Sat, 2005-05-14 at 13:56 -0400, Lee Revell wrote:
> > On Sat, 2005-05-14 at 18:44 +0200, Arjan van de Ven wrote:
> > > then JACK is terminally broken if it doesn't have a fallback for non-
> > > rdtsc cpus. 
> > 
> > It does have a fallback, but the selection is done at compile time.  It
> > uses rdtsc for all x86 CPUs except pre-i586 SMP systems.
> > 
> > Maybe we should check at runtime,
> 
> it's probably a sign that JACK isn't used on SMP systems much, at least
> not on the bigger systems (like IBM's x440's) where the tsc *will*
> differ wildly between cpus...

It does not even need SMP, just use a Centrino laptop.

I suppose what the Jack guys are doing is to recommend to disable
frequency scaling then the sound guys complain again
that sound on linux is so hard to use. I wonder where this comes from? :)

-Andi

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Sat, May 14, 2005 at 12:30:28PM -0400, Lee Revell wrote:
> On Sat, 2005-05-14 at 16:23 +0100, Alan Cox wrote:
> > On Sad, 2005-05-14 at 00:38, Lee Revell wrote:
> > > Well yes but you would still have to recompile those apps.  And take the
> > > big performance hit from using gettimeofday vs rdtsc.  Disabling HT by
> > > default looks pretty good by comparison.
> > 
> > You cannot use rdtsc for anything but rough instruction timing. The
> > timers for different processors run at different speeds on some SMP
> > systems, the timer rates vary as processors change clock rate nowdays.
> > Rdtsc may also jump dramatically on a suspend/resume.
> > 
> > If the app uses rdtsc then generally speaking its terminally broken. The
> > only exception is some profiling tools.
> 
> That is basically all JACK and mplayer use it for.  They have RT
> constraints and the tsc is used to know if we got woken up too late and
> should just drop some frames.  The developers are aware of the issues
> with rdtsc and have chosen to use it anyway because these apps need
> every ounce of CPU and cannot tolerate the overhead of gettimeofday(). 

I would consider jack broken then. For once it breaks
on Centrinos and on AMD systems with PowerNow and some others which all
have frequency scaling with non pstate invariant TSC.

As an additional problem the modern Opterons which support SMP
powernow can even have completely different TSC frequencies
on different CPUs.

All I can recommend is to use gettimeofday() for this. The kernel
goes to considerable pains to make gettimeofday() fast, and when
it is not fast then the system in general cannot do it better.

-Andi

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Fri, May 13, 2005 at 09:16:09PM +0200, Diego Calleja wrote:
> El Fri, 13 May 2005 20:03:58 +0200,
> Andi Kleen <ak@muc.de> escribi?:
> 
> 
> > This is not a kernel problem, but a user space problem. The fix 
> > is to change the user space crypto code to need the same number of cache line
> > accesses on all keys. 
> 
> 
> However they've patched the FreeBSD kernel to "workaround?" it:
> ftp://ftp.freebsd.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch

That's a similar stupid idea as they did with the disk write
cache (lowering the MTBFs of their disks by considerable factors,
which is much worse than the power off data loss problem) 
Let's not go down this path please.

-Andi

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Sat, May 14, 2005 at 05:33:07PM +0200, Andrea Arcangeli wrote:
> On Sat, May 14, 2005 at 03:37:18AM -0400, Lee Revell wrote:
> > The apps that bother to use rdtsc vs. gettimeofday need a cheap high res
> > timer more than a correct one anyway - it's not guaranteed that rdtsc
> > provides a reliable time source at all, due to SMP and frequency scaling
> > issues.
> 
> On x86-64 the cost of gettimeofday is the same of the tsc, turning off

It depends, on many systems it is more costly. e.g. on many SMP
systems we have to use HPET or even the PM timer, because TSC is not
reliable.

> tsc on x86-64 is not nice (even if we usually have HPET there, so
> perhaps it wouldn't be too bad). TSC is something only the kernel (or a
> person with some kernel/hardware knowledge) can do safely knowing it'll
> work fine. But on x86-64 parts of the kernel runs in userland...

Agreed. It is quite complicated to decide if TSC is reliable or not
and I would not recommend user space to do this.

[hmm actually I already have constant_tsc fake cpuid bit, but 
it only refers to single CPUs. I wonder if I should add another
one for SMP "synchronized_tsc". The latest mm code already has
this information, but it does not export it yet] 


> 
> Preventing tasks with different uid to run on the same physical cpu was
> my first idea, disabled by default via sysctl, so only if one is
> paranoid can enable it.

The paranoid should just fix their crypto code. And if they're
clinically paranoid they can always boot with noht or disable
it in the BIOS. But really I think they should just fix OpenSSL. 

> 
> But before touching the kernel in any way it would be really nice if
> somebody could bother to demonstrate this is real because I've an hard
> time to believe this is not purely vapourware. On artificial

Similar feeling here.

> Nobody runs openssl -sign thousand of times in a row on a pure idle
> system without noticing the 100% load on the other cpu for months (and
> he's not root so he can't hide his runaway 100% process, if he was root
> and he could modify the kernel or ps/top to hide the runaway process,
> he'd have faster ways to sniff).

Exactly.

> 
> So to me this sounds a purerly theoretical problem. Cache covert

Perhaps not purely theoretical, but it is certainly not something
that needs drastic action like disabling HT in general.

> This was an interesting read, but in practice I'd rate this to have
> severity 1 on a 0-100 scale, unless somebody bothers to demonstrate it
> in a remotely realistic environment.

Agreed.

-Andi

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Fri, May 13, 2005 at 02:26:20PM -0700, Andy Isaacson wrote:
> On Fri, May 13, 2005 at 09:05:49PM +0200, Andi Kleen wrote:
> > On Fri, May 13, 2005 at 02:38:03PM -0400, Richard F. Rebel wrote:
> > > Why?  It's certainly reasonable to disable it for the time being and
> > > even prudent to do so.
> > 
> > No, i strongly disagree on that. The reasonable thing to do is
> > to fix the crypto code which has this vulnerability, not break
> > a useful performance enhancement for everybody else.
> 
> Pardon me for saying so, but that's bullshit.  You're asking the crypto
> guys to give up a 5x performance gain (that's my wild guess) by giving
> up all their data-dependent algorithms and contorting their code wildly,
> to avoid a microarchitectural problem with Intel's HT implementation.

And what you're doing is to ask all the non crypto guys to give
up an useful optimization just to fix a problem in the crypto guy's
code. The cache line information leak is just a information leak
bug in the crypto code, not a general problem.

There is much more non crypto code than crypto code around - you
are proposing to screw the majority of codes to solve a relatively
obscure problem of only a few functions, which seems like the totally
wrong approach to me.

BTW the crypto guys are always free to check for hyperthreading
themselves and use different functions.  However there is a catch
there - the modern dual core processors which actually have
separated L1 and L2 caches set these too to stay compatible
with old code and license managers.

-Andi

Re: Hyper-Threading Vulnerability

[Andi Kleen]

> I was under the impression that P4 and later processors do not vary the
> TSC rate when doing frequency scaling.  This is mentioned in the
> documentation for the high res timers patch.

Prescott and later do not vary TSC, but P4s before that do.
On x86-64 it is true because only Nocona is supported which has a 
pstate invariant TSC.

The latest x86-64 kernel has a special X86_CONSTANT_TSC internal
CPUID bit, which is set in that case. If some other subsystem
uses it I would recommend to port that to i386 too.

-Andi

Re: Hyper-Threading Vulnerability

[Adrian Bunk]

On Sat, May 14, 2005 at 01:56:36PM -0400, Lee Revell wrote:
> On Sat, 2005-05-14 at 18:44 +0200, Arjan van de Ven wrote:
> > then JACK is terminally broken if it doesn't have a fallback for non-
> > rdtsc cpus. 
> 
> It does have a fallback, but the selection is done at compile time.  It
> uses rdtsc for all x86 CPUs except pre-i586 SMP systems.
> 
> Maybe we should check at runtime, but this has always worked.

If this is critical for JACK, runtime selection was an improvement for 
distributions like Debian that support both pre-i586 SMP systems and 
current hardware.

> Lee

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: Hyper-Threading Vulnerability

[Adrian Bunk]

On Fri, May 13, 2005 at 12:02:44PM -0700, Andy Isaacson wrote:
> On Fri, May 13, 2005 at 11:30:27AM -0700, Vadim Lobanov wrote:
> > On Fri, 13 May 2005, Andy Isaacson wrote:
> > > It's a side channel timing attack on data-dependent computation through
> > > the L1 and L2 caches.  Nice work.  In-the-wild exploitation is
> > > difficult, though; your timing gets screwed up if you get scheduled away
> > > from your victim, and you don't even know, because you can't tell where
> > > you were scheduled, so on any reasonably busy multiuser system it's not
> > > clear that the attack is practical.
> > 
> > Wouldn't scheduling appear as a rather big time delta (in measuring the
> > cache access times), so you would know to disregard that data point?
> > 
> > (Just wondering... :-) )
> 
> Good question.  Yes, you can probably filter the data.  The question is,
> how hard is it to set up the conditions to acquire the data?  You have
> to be scheduled on the same core as the target process (sibling
> threads).  And you don't know when the target is going to be scheduled,
> and on a real-world system, there are other threads competing for
> scheduling; if it's SMP (2 core, 4 thread) with perfect 100% utilization
> then you've only got a 33% chance of being scheduled on the right
> thread, and it gets worse if the machine is idle since the kernel should
> schedule you and the OpenSSL process on different cores...
>...

But if you start 3 processes in the idle case you might get a 100% 
chance?

> -andy

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

On Sat, 2005-05-14 at 19:40 -0400, Lee Revell wrote:
> > it's a matter of time (my estimate is a year or two) before processors
> > get variable frequencies based on temperature targets etc...
> > and then rdtsc is really useless for this kind of thing..
> 
> I was under the impression that P4 and later processors do not vary the
> TSC rate when doing frequency scaling.  This is mentioned in the
> documentation for the high res timers patch.

seems not the case, and worse, during idle time the clock is allowed to
stop entirely.... (and that is also happening more and more and linux is
getting more agressive idle support (eg no timer tick and such patches)
which will trigger bios thresholds for this even more too.

Re: Hyper-Threading Vulnerability

[dean gaudet]

On Sat, 14 May 2005, Arjan van de Ven wrote:

> it's a matter of time (my estimate is a year or two) before processors
> get variable frequencies based on temperature targets etc...
> and then rdtsc is really useless for this kind of thing..

what do you mean "a year or two"?  processors have been doing this for 
many years now.

i'm biased, but i still think transmeta did this the right way... the tsc 
operates at the top frequency of the processor always.

i do a hell of a lot of microbenchmarking on various processors and i 
always use tsc -- but i'm just smart enough to take multiple samples and i 
try to make each sample smaller than a time slice... which avoids most of 
the pitfalls, and would even work on smp boxes with tsc differences.

-dean

Re: Hyper-Threading Vulnerability

[Christer Weinigel]

Andrea Arcangeli <andrea@suse.de> writes:

> Nobody runs openssl -sign thousand of times in a row on a pure idle
> system without noticing the 100% load on the other cpu for months

Well, actually one does.  On a normal https server, each https request
results in an operation on the private key.  So if the attacker shares
the same web server as the victim it's probably rather easy for the
attacker to see when the machine is idle and launch an attack giving
him thousands of chances to spy on the victim.

But I do agree that this probably isn't all that serious, for those
who really have secrets to hide, they won't run their https server on
a machine shared with anybody else.

  /Christer

-- 
"Just how much can I get away with and still go to heaven?"

Freelance consultant specializing in device driver programming for Linux 
Christer Weinigel <christer@weinigel.se>  http://www.weinigel.se

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Sat, 2005-05-14 at 21:48 +0200, Arjan van de Ven wrote:
> On Sat, 2005-05-14 at 15:21 -0400, Lee Revell wrote:
> > On Sat, 2005-05-14 at 20:01 +0200, Arjan van de Ven wrote:
> > > On Sat, 2005-05-14 at 13:56 -0400, Lee Revell wrote:
> > > > On Sat, 2005-05-14 at 18:44 +0200, Arjan van de Ven wrote:
> > > > > then JACK is terminally broken if it doesn't have a fallback for non-
> > > > > rdtsc cpus. 
> > > > 
> > > > It does have a fallback, but the selection is done at compile time.  It
> > > > uses rdtsc for all x86 CPUs except pre-i586 SMP systems.
> > > > 
> > > > Maybe we should check at runtime,
> > > 
> > > it's probably a sign that JACK isn't used on SMP systems much, at least
> > > not on the bigger systems (like IBM's x440's) where the tsc *will*
> > > differ wildly between cpus...
> > 
> > Correct.  The only bug reports we have seen related to the use of the
> > TSC is due to CPU frequency scaling.  The fix is to not use it - people
> > who want to use their PC as a DSP for audio probably don't want their
> > processor slowing down anyway. 
> 
> it's a matter of time (my estimate is a year or two) before processors
> get variable frequencies based on temperature targets etc...
> and then rdtsc is really useless for this kind of thing..

I was under the impression that P4 and later processors do not vary the
TSC rate when doing frequency scaling.  This is mentioned in the
documentation for the high res timers patch.

Lee

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

On Sat, 2005-05-14 at 15:21 -0400, Lee Revell wrote:
> On Sat, 2005-05-14 at 20:01 +0200, Arjan van de Ven wrote:
> > On Sat, 2005-05-14 at 13:56 -0400, Lee Revell wrote:
> > > On Sat, 2005-05-14 at 18:44 +0200, Arjan van de Ven wrote:
> > > > then JACK is terminally broken if it doesn't have a fallback for non-
> > > > rdtsc cpus. 
> > > 
> > > It does have a fallback, but the selection is done at compile time.  It
> > > uses rdtsc for all x86 CPUs except pre-i586 SMP systems.
> > > 
> > > Maybe we should check at runtime,
> > 
> > it's probably a sign that JACK isn't used on SMP systems much, at least
> > not on the bigger systems (like IBM's x440's) where the tsc *will*
> > differ wildly between cpus...
> 
> Correct.  The only bug reports we have seen related to the use of the
> TSC is due to CPU frequency scaling.  The fix is to not use it - people
> who want to use their PC as a DSP for audio probably don't want their
> processor slowing down anyway. 

it's a matter of time (my estimate is a year or two) before processors
get variable frequencies based on temperature targets etc...
and then rdtsc is really useless for this kind of thing..

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Sat, 2005-05-14 at 20:01 +0200, Arjan van de Ven wrote:
> On Sat, 2005-05-14 at 13:56 -0400, Lee Revell wrote:
> > On Sat, 2005-05-14 at 18:44 +0200, Arjan van de Ven wrote:
> > > then JACK is terminally broken if it doesn't have a fallback for non-
> > > rdtsc cpus. 
> > 
> > It does have a fallback, but the selection is done at compile time.  It
> > uses rdtsc for all x86 CPUs except pre-i586 SMP systems.
> > 
> > Maybe we should check at runtime,
> 
> it's probably a sign that JACK isn't used on SMP systems much, at least
> not on the bigger systems (like IBM's x440's) where the tsc *will*
> differ wildly between cpus...

Correct.  The only bug reports we have seen related to the use of the
TSC is due to CPU frequency scaling.  The fix is to not use it - people
who want to use their PC as a DSP for audio probably don't want their
processor slowing down anyway.  And JACK is targeted at desktop and
smaller systems, it would be kind of crazy to run it on a big iron.
Well, maybe there are people who like to record sessions or practice
guitar in the server room...

If gettimeofday is really as cheap as rdtsc on x86_64, we should use it.
But it's too expensive for slower x86 systems.  Anyway, Andi's fix
disables *all* high res timing including gettimeofday.  Obviously no
multimedia app can tolerate this, so discussing rdtsc is really a red
herring.  But multimedia apps aren't much in seccomp environments
either.

Lee

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Sat, 2005-05-14 at 19:04 +0200, Jindrich Makovicka wrote:
> AFAIK, mplayer actually uses gettimeofday(). rdtsc is used in some
> places for profiling and debugging purposes and not compiled in by default.
> 

OK.  The comments in the JACK code say it was copied from mplayer.  I
guess the usage is not the same.

Lee

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

On Sat, 2005-05-14 at 13:56 -0400, Lee Revell wrote:
> On Sat, 2005-05-14 at 18:44 +0200, Arjan van de Ven wrote:
> > then JACK is terminally broken if it doesn't have a fallback for non-
> > rdtsc cpus. 
> 
> It does have a fallback, but the selection is done at compile time.  It
> uses rdtsc for all x86 CPUs except pre-i586 SMP systems.
> 
> Maybe we should check at runtime,

it's probably a sign that JACK isn't used on SMP systems much, at least
not on the bigger systems (like IBM's x440's) where the tsc *will*
differ wildly between cpus...

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Sat, 2005-05-14 at 18:44 +0200, Arjan van de Ven wrote:
> then JACK is terminally broken if it doesn't have a fallback for non-
> rdtsc cpus. 

It does have a fallback, but the selection is done at compile time.  It
uses rdtsc for all x86 CPUs except pre-i586 SMP systems.

Maybe we should check at runtime, but this has always worked.

Lee

Re: Hyper-Threading Vulnerability

[Jindrich Makovicka]

Lee Revell wrote:
> On Sat, 2005-05-14 at 16:23 +0100, Alan Cox wrote:
> 
>>On Sad, 2005-05-14 at 00:38, Lee Revell wrote:
>>
>>>Well yes but you would still have to recompile those apps.  And take the
>>>big performance hit from using gettimeofday vs rdtsc.  Disabling HT by
>>>default looks pretty good by comparison.
>>
>>You cannot use rdtsc for anything but rough instruction timing. The
>>timers for different processors run at different speeds on some SMP
>>systems, the timer rates vary as processors change clock rate nowdays.
>>Rdtsc may also jump dramatically on a suspend/resume.
>>
>>If the app uses rdtsc then generally speaking its terminally broken. The
>>only exception is some profiling tools.
> 
> 
> That is basically all JACK and mplayer use it for.  They have RT
> constraints and the tsc is used to know if we got woken up too late and
> should just drop some frames.  The developers are aware of the issues
> with rdtsc and have chosen to use it anyway because these apps need
> every ounce of CPU and cannot tolerate the overhead of gettimeofday(). 

AFAIK, mplayer actually uses gettimeofday(). rdtsc is used in some
places for profiling and debugging purposes and not compiled in by default.

-- 
Jindrich Makovicka

Re: Hyper-Threading Vulnerability

[Arjan van de Ven]

On Sat, 2005-05-14 at 12:30 -0400, Lee Revell wrote:
> On Sat, 2005-05-14 at 16:23 +0100, Alan Cox wrote:
> > On Sad, 2005-05-14 at 00:38, Lee Revell wrote:
> > > Well yes but you would still have to recompile those apps.  And take the
> > > big performance hit from using gettimeofday vs rdtsc.  Disabling HT by
> > > default looks pretty good by comparison.
> > 
> > You cannot use rdtsc for anything but rough instruction timing. The
> > timers for different processors run at different speeds on some SMP
> > systems, the timer rates vary as processors change clock rate nowdays.
> > Rdtsc may also jump dramatically on a suspend/resume.
> > 
> > If the app uses rdtsc then generally speaking its terminally broken. The
> > only exception is some profiling tools.
> 
> That is basically all JACK and mplayer use it for.  They have RT
> constraints and the tsc is used to know if we got woken up too late and
> should just drop some frames.  The developers are aware of the issues
> with rdtsc and have chosen to use it anyway because these apps need
> every ounce of CPU and cannot tolerate the overhead of gettimeofday(). 


then JACK is terminally broken if it doesn't have a fallback for non-
rdtsc cpus. 

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Sat, 2005-05-14 at 16:23 +0100, Alan Cox wrote:
> On Sad, 2005-05-14 at 00:38, Lee Revell wrote:
> > Well yes but you would still have to recompile those apps.  And take the
> > big performance hit from using gettimeofday vs rdtsc.  Disabling HT by
> > default looks pretty good by comparison.
> 
> You cannot use rdtsc for anything but rough instruction timing. The
> timers for different processors run at different speeds on some SMP
> systems, the timer rates vary as processors change clock rate nowdays.
> Rdtsc may also jump dramatically on a suspend/resume.
> 
> If the app uses rdtsc then generally speaking its terminally broken. The
> only exception is some profiling tools.

That is basically all JACK and mplayer use it for.  They have RT
constraints and the tsc is used to know if we got woken up too late and
should just drop some frames.  The developers are aware of the issues
with rdtsc and have chosen to use it anyway because these apps need
every ounce of CPU and cannot tolerate the overhead of gettimeofday(). 

Lee

Re: Hyper-Threading Vulnerability

[Paul Jakma]

On Sat, 14 May 2005, Paul Jakma wrote:

> http://www.openssl.org/news/secadv_20030317.txt
>
> This is old news it seems, a timing attack that has long been known 
> about and fixed.

I've now been told it's a new, more involved, timing attack to the 
one the URL above describes a defence against.

regards,
-- 
Paul Jakma	paul@clubi.ie	paul@jakma.org	Key ID: 64A2FF6A
Fortune:
Weinberg's First Law:
 	Progress is only made on alternate Fridays.

Re: Hyper-Threading Vulnerability

[andrea]

On Sat, May 14, 2005 at 04:23:10PM +0100, Alan Cox wrote:
> You cannot use rdtsc for anything but rough instruction timing. The
> timers for different processors run at different speeds on some SMP
> systems, the timer rates vary as processors change clock rate nowdays.
> Rdtsc may also jump dramatically on a suspend/resume.

x86-64 uses it for vgettimeofday very safely (i386 could do too but it
doesn't).

Anyway I believe at least for seccomp it's worth to turn off the tsc,
not just for HT but for the L2 cache too. So it's up to you, either you
turn it off completely (which isn't very nice IMHO) or I recommend to
apply this below patch. This has been tested successfully on x86-64
against current cogito repository (i686 compiles so I didn't bother
testing ;). People selling the cpu through cpushare may appreciate this
bit for a peace of mind. There's no way to get any timing info anymore
with this applied (gettimeofday is forbidden of course). The seccomp
environment is completely deterministic so it can't be allowed to get
timing info, it has to be deterministic so in the future I can enable a
computing mode that does a parallel computing for each task with server
side transparent checkpointing and verification that the output is the
same from all the 2/3 seller computers for each task, without the buyer
even noticing (for now the verification is left to the buyer client
side and there's no checkpointing, since that would require more kernel
changes to track the dirty bits but it'll be easy to extend once the
basic mode is finished).

Thanks.

Signed-off-by: Andrea Arcangeli <andrea@cpushare.com>

Index: arch/i386/kernel/process.c
===================================================================
--- eed337ef5e9ae7d62caa84b7974a11fddc7f06e0/arch/i386/kernel/process.c  (mode:100644)
+++ uncommitted/arch/i386/kernel/process.c  (mode:100644)
@@ -561,6 +561,25 @@
 }
 
 /*
+ * This function selects if the context switch from prev to next
+ * has to tweak the TSC disable bit in the cr4.
+ */
+static void disable_tsc(struct thread_info *prev,
+			struct thread_info *next)
+{
+	if (unlikely(has_secure_computing(prev) ||
+		     has_secure_computing(next))) {
+		/* slow path here */
+		if (has_secure_computing(prev) &&
+		    !has_secure_computing(next)) {
+			clear_in_cr4(X86_CR4_TSD);
+		} else if (!has_secure_computing(prev) &&
+			   has_secure_computing(next))
+			set_in_cr4(X86_CR4_TSD);
+	}
+}
+
+/*
  *	switch_to(x,yn) should switch tasks from x to y.
  *
  * We fsave/fwait so that an exception goes off at the right time
@@ -639,6 +658,8 @@
 	if (unlikely(prev->io_bitmap_ptr || next->io_bitmap_ptr))
 		handle_io_bitmap(next, tss);
 
+	disable_tsc(prev_p->thread_info, next_p->thread_info);
+
 	return prev_p;
 }
 
Index: arch/x86_64/kernel/process.c
===================================================================
--- eed337ef5e9ae7d62caa84b7974a11fddc7f06e0/arch/x86_64/kernel/process.c  (mode:100644)
+++ uncommitted/arch/x86_64/kernel/process.c  (mode:100644)
@@ -439,6 +439,25 @@
 }
 
 /*
+ * This function selects if the context switch from prev to next
+ * has to tweak the TSC disable bit in the cr4.
+ */
+static void disable_tsc(struct thread_info *prev,
+			struct thread_info *next)
+{
+	if (unlikely(has_secure_computing(prev) ||
+		     has_secure_computing(next))) {
+		/* slow path here */
+		if (has_secure_computing(prev) &&
+		    !has_secure_computing(next)) {
+			clear_in_cr4(X86_CR4_TSD);
+		} else if (!has_secure_computing(prev) &&
+			   has_secure_computing(next))
+			set_in_cr4(X86_CR4_TSD);
+	}
+}
+
+/*
  * This special macro can be used to load a debugging register
  */
 #define loaddebug(thread,r) set_debug(thread->debugreg ## r, r)
@@ -556,6 +575,8 @@
 		}
 	}
 
+	disable_tsc(prev_p->thread_info, next_p->thread_info);
+
 	return prev_p;
 }
 
Index: include/linux/seccomp.h
===================================================================
--- eed337ef5e9ae7d62caa84b7974a11fddc7f06e0/include/linux/seccomp.h  (mode:100644)
+++ uncommitted/include/linux/seccomp.h  (mode:100644)
@@ -19,6 +19,11 @@
 		__secure_computing(this_syscall);
 }
 
+static inline int has_secure_computing(struct thread_info *ti)
+{
+	return unlikely(test_ti_thread_flag(ti, TIF_SECCOMP));
+}
+
 #else /* CONFIG_SECCOMP */
 
 #if (__GNUC__ > 2)
@@ -28,6 +33,7 @@
 #endif
 
 #define secure_computing(x) do { } while (0)
+#define has_secure_computing(x) 0
 
 #endif /* CONFIG_SECCOMP */
 

Re: Hyper-Threading Vulnerability

[Andrea Arcangeli]

On Sat, May 14, 2005 at 03:37:18AM -0400, Lee Revell wrote:
> The apps that bother to use rdtsc vs. gettimeofday need a cheap high res
> timer more than a correct one anyway - it's not guaranteed that rdtsc
> provides a reliable time source at all, due to SMP and frequency scaling
> issues.

On x86-64 the cost of gettimeofday is the same of the tsc, turning off
tsc on x86-64 is not nice (even if we usually have HPET there, so
perhaps it wouldn't be too bad). TSC is something only the kernel (or a
person with some kernel/hardware knowledge) can do safely knowing it'll
work fine. But on x86-64 parts of the kernel runs in userland...

Preventing tasks with different uid to run on the same physical cpu was
my first idea, disabled by default via sysctl, so only if one is
paranoid can enable it.

But before touching the kernel in any way it would be really nice if
somebody could bother to demonstrate this is real because I've an hard
time to believe this is not purely vapourware. On artificial
environments a computer can recognize the difference between two faces
too, no big deal, but that doesn't mean the same software is going to
recognize million of different faces at the airport too. So nothing has
been demonstrated in practical terms yet.

Nobody runs openssl -sign thousand of times in a row on a pure idle
system without noticing the 100% load on the other cpu for months (and
he's not root so he can't hide his runaway 100% process, if he was root
and he could modify the kernel or ps/top to hide the runaway process,
he'd have faster ways to sniff).

So to me this sounds a purerly theoretical problem. Cache covert
channels are possible too as the paper states, next time somebody will
find how to sniff a letter out of a pdf document on a UP no-HT system by
opening and closing it some million of times on a otherwise idle system.
We're sure not going to flush the l2 cache because of that (at least not
by default ;).

This was an interesting read, but in practice I'd rate this to have
severity 1 on a 0-100 scale, unless somebody bothers to demonstrate it
in a remotely realistic environment.

Even if this would be real if they sniff a openssl key, unless they also
crack the dns the browser will complain (not very different from not
having a certificate authority signature on a fake key). And if the
server is remotely serious they'll notice the 100% runaway process way
before he can sniff the whole key (the 100% runaway load cannot be
hidden). Most servers have some statistics so a 100% load for weeks or
months isn't very likely to be overlooked.

Re: Hyper-Threading Vulnerability

[Alan Cox]

On Sad, 2005-05-14 at 00:38, Lee Revell wrote:
> Well yes but you would still have to recompile those apps.  And take the
> big performance hit from using gettimeofday vs rdtsc.  Disabling HT by
> default looks pretty good by comparison.

You cannot use rdtsc for anything but rough instruction timing. The
timers for different processors run at different speeds on some SMP
systems, the timer rates vary as processors change clock rate nowdays.
Rdtsc may also jump dramatically on a suspend/resume.

If the app uses rdtsc then generally speaking its terminally broken. The
only exception is some profiling tools.

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Fri, 2005-05-13 at 19:44 -0400, Dave Jones wrote:
> On Fri, May 13, 2005 at 07:38:08PM -0400, Lee Revell wrote:
>  > On Fri, 2005-05-13 at 19:27 -0400, Dave Jones wrote:
>  > > On Fri, May 13, 2005 at 07:00:12PM -0400, Lee Revell wrote:
>  > >  > On Fri, 2005-05-13 at 23:47 +0100, Alan Cox wrote:
>  > >  > > On Gwe, 2005-05-13 at 22:59, Matt Mackall wrote:
>  > >  > > > It might not be much of a problem though. If he's a bit off per guess
>  > >  > > > (really impressive), he'll still be many bits off by the time there's
>  > >  > > > enough entropy in the primary pool to reseed the secondary pool so he
>  > >  > > > can check his guesswork.
>  > >  > > 
>  > >  > > You can also disable the tsc to user space in the intel processors.
>  > >  > > Thats something they anticipated as being neccessary in secure
>  > >  > > environments long ago. This makes the attack much harder.
>  > >  > 
>  > >  > And break the hundreds of apps that depend on rdtsc?  Am I missing
>  > >  > something?
>  > > 
>  > > If those apps depend on rdtsc being a) present, and b) working
>  > > without providing fallbacks, they're already broken.
>  > > 
>  > > There's a reason its displayed in /proc/cpuinfo's flags field,
>  > > and visible through cpuid. Apps should be testing for presence
>  > > before assuming features are present.
>  > > 
>  > 
>  > Well yes but you would still have to recompile those apps.
> 
> Not if the app is written correctly. See above.

The apps that bother to use rdtsc vs. gettimeofday need a cheap high res
timer more than a correct one anyway - it's not guaranteed that rdtsc
provides a reliable time source at all, due to SMP and frequency scaling
issues.

I'll try to benchmark the difference.  Maybe it's not that big a deal.

Lee

Re: Hyper-Threading Vulnerability

[dean gaudet]

On Fri, 13 May 2005, Andy Isaacson wrote:

> On Fri, May 13, 2005 at 09:05:49PM +0200, Andi Kleen wrote:
> > On Fri, May 13, 2005 at 02:38:03PM -0400, Richard F. Rebel wrote:
> > > Why?  It's certainly reasonable to disable it for the time being and
> > > even prudent to do so.
> > 
> > No, i strongly disagree on that. The reasonable thing to do is
> > to fix the crypto code which has this vulnerability, not break
> > a useful performance enhancement for everybody else.
> 
> Pardon me for saying so, but that's bullshit.  You're asking the crypto
> guys to give up a 5x performance gain (that's my wild guess) by giving
> up all their data-dependent algorithms and contorting their code wildly,
> to avoid a microarchitectural problem with Intel's HT implementation.

i think your wild guess is way off.  i can think of several approaches to 
fix these problems which won't be anywhere near 5x.

the problem is that an attacker can observe which cache indices (rows) are 
in use.  one workaround is to overload the possible secrets which each 
index represents.

you can overload the secrets in each cache line:  for example when doing 
exponentiation there is an array of bignums x**(2*n).  bignums themselves 
are arrays (which span multiple cache lines).  do a "row/column transpose" 
on this array of arrays -- suddenly each cache line contains a number of 
possible secrets.  if you're operating with 32-bit words in a 64 byte line 
then you've achieved a 16-fold reduction in exposed information by this 
transpose.  there'll be almost no performance penalty.

you can overload the secrets in each cache index:  abuse the associativity 
of the cache.  the affected processors are all 8-way associative.  
ideally you'd want to arrange your data so that it all collides within the 
same cache index -- and get an 8-fold reduction in exposure.  the trick 
here is the L2 is physically indexed, and userland code can perform only 
virtual allocations.  but it's not too hard to discover physical conflicts 
if you really want to (using rdtsc) -- it would be done early in the 
initialization of the program because it involves asking for enough memory 
until the kernel gives you enough colliding pages.  (a system call could 
help with this if we really wanted it.)

my not-so-wild guess is a 128-fold reduction for less than 10% perf hit...

i think there's possibly another approach involving a permuted array of 
indirection pointers... which is going to affect perf a bit due to the 
extra indirection required, but we're talking <10% here.  (i'm just not 
convinced yet you can select a permutation in a manner which doesn't leak 
information when the attacker can view multiple invocations of the crypto 
for example.)


> If SHA has plaintext-dependent memory references, Colin's technique
> would enable an adversary to extract the contents of the /dev/random
> pools.  I don't *think* SHA does, based on a quick reading of
> lib/sha1.c, but someone with an actual clue should probably take a look.

the SHA family do not have any data-dependencies in their memory access 
patterns.

-dean

Re: Hyper-Threading Vulnerability

[Dave Jones]

On Fri, May 13, 2005 at 07:38:08PM -0400, Lee Revell wrote:
 > On Fri, 2005-05-13 at 19:27 -0400, Dave Jones wrote:
 > > On Fri, May 13, 2005 at 07:00:12PM -0400, Lee Revell wrote:
 > >  > On Fri, 2005-05-13 at 23:47 +0100, Alan Cox wrote:
 > >  > > On Gwe, 2005-05-13 at 22:59, Matt Mackall wrote:
 > >  > > > It might not be much of a problem though. If he's a bit off per guess
 > >  > > > (really impressive), he'll still be many bits off by the time there's
 > >  > > > enough entropy in the primary pool to reseed the secondary pool so he
 > >  > > > can check his guesswork.
 > >  > > 
 > >  > > You can also disable the tsc to user space in the intel processors.
 > >  > > Thats something they anticipated as being neccessary in secure
 > >  > > environments long ago. This makes the attack much harder.
 > >  > 
 > >  > And break the hundreds of apps that depend on rdtsc?  Am I missing
 > >  > something?
 > > 
 > > If those apps depend on rdtsc being a) present, and b) working
 > > without providing fallbacks, they're already broken.
 > > 
 > > There's a reason its displayed in /proc/cpuinfo's flags field,
 > > and visible through cpuid. Apps should be testing for presence
 > > before assuming features are present.
 > > 
 > 
 > Well yes but you would still have to recompile those apps.

Not if the app is written correctly. See above.

		Dave

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Fri, 2005-05-13 at 19:27 -0400, Dave Jones wrote:
> On Fri, May 13, 2005 at 07:00:12PM -0400, Lee Revell wrote:
>  > On Fri, 2005-05-13 at 23:47 +0100, Alan Cox wrote:
>  > > On Gwe, 2005-05-13 at 22:59, Matt Mackall wrote:
>  > > > It might not be much of a problem though. If he's a bit off per guess
>  > > > (really impressive), he'll still be many bits off by the time there's
>  > > > enough entropy in the primary pool to reseed the secondary pool so he
>  > > > can check his guesswork.
>  > > 
>  > > You can also disable the tsc to user space in the intel processors.
>  > > Thats something they anticipated as being neccessary in secure
>  > > environments long ago. This makes the attack much harder.
>  > 
>  > And break the hundreds of apps that depend on rdtsc?  Am I missing
>  > something?
> 
> If those apps depend on rdtsc being a) present, and b) working
> without providing fallbacks, they're already broken.
> 
> There's a reason its displayed in /proc/cpuinfo's flags field,
> and visible through cpuid. Apps should be testing for presence
> before assuming features are present.
> 

Well yes but you would still have to recompile those apps.  And take the
big performance hit from using gettimeofday vs rdtsc.  Disabling HT by
default looks pretty good by comparison.

Lee

Re: Hyper-Threading Vulnerability

[Paul Jakma]

On Fri, 13 May 2005, Andi Kleen wrote:

> No, i strongly disagree on that. The reasonable thing to do is to 
> fix the crypto code which has this vulnerability, not break a 
> useful performance enhancement for everybody else.

Already done:

http://www.openssl.org/news/secadv_20030317.txt

This is old news it seems, a timing attack that has long been known 
about and fixed.

regards,
-- 
Paul Jakma	paul@clubi.ie	paul@jakma.org	Key ID: 64A2FF6A
Fortune:
What happens when you cut back the jungle?  It recedes.

Re: Hyper-Threading Vulnerability

[Dave Jones]

On Fri, May 13, 2005 at 07:00:12PM -0400, Lee Revell wrote:
 > On Fri, 2005-05-13 at 23:47 +0100, Alan Cox wrote:
 > > On Gwe, 2005-05-13 at 22:59, Matt Mackall wrote:
 > > > It might not be much of a problem though. If he's a bit off per guess
 > > > (really impressive), he'll still be many bits off by the time there's
 > > > enough entropy in the primary pool to reseed the secondary pool so he
 > > > can check his guesswork.
 > > 
 > > You can also disable the tsc to user space in the intel processors.
 > > Thats something they anticipated as being neccessary in secure
 > > environments long ago. This makes the attack much harder.
 > 
 > And break the hundreds of apps that depend on rdtsc?  Am I missing
 > something?

If those apps depend on rdtsc being a) present, and b) working
without providing fallbacks, they're already broken.

There's a reason its displayed in /proc/cpuinfo's flags field,
and visible through cpuid. Apps should be testing for presence
before assuming features are present.

		Dave

Re: Hyper-Threading Vulnerability

[Jim Crilly]

On 05/13/05 01:18:40PM -0700, Barry K. Nathan wrote:
> On Fri, May 13, 2005 at 03:14:43PM -0400, Jim Crilly wrote:
> > And what if you have more than one physical HT processor? AFAIK there's no
> > way to disable HT and still run SMP at the same time.
> 
> Actually, there is; read my post earlier in this thread:
> http://marc.theaimsgroup.com/?l=linux-kernel&m=111598859708620&w=2
> 
> To elaborate on the "check dmesg" part of that e-mail:
> 
> After you reboot with "maxcpus=2" (or however many physical CPU's you
> have), you need to make sure you have messages like this, which indicate
> that it really worked:
> 
> WARNING: No sibling found for CPU 0.
> WARNING: No sibling found for CPU 1.
> 
> (and so on, if you have more than 2 CPU's)

But what about machines that don't enumerate physical processors before
logical? The comment in setup.c implies that the order that the BIOS
presents CPUs is undefined and if you're unlucky enough to have a machine
that presents the CPUs as physical, logical, physical, logical, etc you're
screwed.

Jim.

Re: Hyper-Threading Vulnerability

[Lee Revell]

On Fri, 2005-05-13 at 23:47 +0100, Alan Cox wrote:
> On Gwe, 2005-05-13 at 22:59, Matt Mackall wrote:
> > It might not be much of a problem though. If he's a bit off per guess
> > (really impressive), he'll still be many bits off by the time there's
> > enough entropy in the primary pool to reseed the secondary pool so he
> > can check his guesswork.
> 
> You can also disable the tsc to user space in the intel processors.
> Thats something they anticipated as being neccessary in secure
> environments long ago. This makes the attack much harder.

And break the hundreds of apps that depend on rdtsc?  Am I missing
something?

Lee

Re: Hyper-Threading Vulnerability

[Alan Cox]

On Gwe, 2005-05-13 at 22:59, Matt Mackall wrote:
> It might not be much of a problem though. If he's a bit off per guess
> (really impressive), he'll still be many bits off by the time there's
> enough entropy in the primary pool to reseed the secondary pool so he
> can check his guesswork.

You can also disable the tsc to user space in the intel processors.
Thats something they anticipated as being neccessary in secure
environments long ago. This makes the attack much harder.

Re: Hyper-Threading Vulnerability

[Matt Mackall]

On Fri, May 13, 2005 at 02:26:20PM -0700, Andy Isaacson wrote:
> On Fri, May 13, 2005 at 09:05:49PM +0200, Andi Kleen wrote:
> > On Fri, May 13, 2005 at 02:38:03PM -0400, Richard F. Rebel wrote:
> > > Why?  It's certainly reasonable to disable it for the time being and
> > > even prudent to do so.
> > 
> > No, i strongly disagree on that. The reasonable thing to do is
> > to fix the crypto code which has this vulnerability, not break
> > a useful performance enhancement for everybody else.
> 
> Pardon me for saying so, but that's bullshit.  You're asking the crypto
> guys to give up a 5x performance gain (that's my wild guess) by giving
> up all their data-dependent algorithms and contorting their code wildly,
> to avoid a microarchitectural problem with Intel's HT implementation.
> 
> There are three places to cut off the side channel, none of which is
> obviously the right one.
> 1. The HT implementation could do the cache tricks Colin suggested in
>    his paper.  Fairly large performance hit to address a fairly small
>    problem.
> 2. The OS could do the scheduler tricks to avoid scheduling unfriendly
>    threads on the same core.  You're leaving a lot of the benefit of HT
>    on the floor by doing so.
> 3. Every security-sensitive app can be rigorously audited and re-written
>    to avoid *ever* referencing memory with the address determined by
>    private data.
> 
> (3) is a complete non-starter.  It's just not feasible to rewrite all
> that code.  Furthermore, there's no way to know what code needs to be
> rewritten!  (Until someone publishes an advisory, that is...)
> 
> Hmm, I can't think of any reason that this technique wouldn't work to
> extract information from kernel secrets, as well... 
> 
> If SHA has plaintext-dependent memory references, Colin's technique
> would enable an adversary to extract the contents of the /dev/random
> pools.  I don't *think* SHA does, based on a quick reading of
> lib/sha1.c, but someone with an actual clue should probably take a look.

SHA1 should be fine, as are the pool mixing bits. Much more
problematic is the ability to do timing attacks against the entropy
gathering itself. If an attacker can guess the TSC value that gets
mixed into the pool, that's a problem.

It might not be much of a problem though. If he's a bit off per guess
(really impressive), he'll still be many bits off by the time there's
enough entropy in the primary pool to reseed the secondary pool so he
can check his guesswork.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Hyper-Threading Vulnerability

[Andy Isaacson]

On Fri, May 13, 2005 at 09:05:49PM +0200, Andi Kleen wrote:
> On Fri, May 13, 2005 at 02:38:03PM -0400, Richard F. Rebel wrote:
> > Why?  It's certainly reasonable to disable it for the time being and
> > even prudent to do so.
> 
> No, i strongly disagree on that. The reasonable thing to do is
> to fix the crypto code which has this vulnerability, not break
> a useful performance enhancement for everybody else.

Pardon me for saying so, but that's bullshit.  You're asking the crypto
guys to give up a 5x performance gain (that's my wild guess) by giving
up all their data-dependent algorithms and contorting their code wildly,
to avoid a microarchitectural problem with Intel's HT implementation.

There are three places to cut off the side channel, none of which is
obviously the right one.
1. The HT implementation could do the cache tricks Colin suggested in
   his paper.  Fairly large performance hit to address a fairly small
   problem.
2. The OS could do the scheduler tricks to avoid scheduling unfriendly
   threads on the same core.  You're leaving a lot of the benefit of HT
   on the floor by doing so.
3. Every security-sensitive app can be rigorously audited and re-written
   to avoid *ever* referencing memory with the address determined by
   private data.

(3) is a complete non-starter.  It's just not feasible to rewrite all
that code.  Furthermore, there's no way to know what code needs to be
rewritten!  (Until someone publishes an advisory, that is...)

Hmm, I can't think of any reason that this technique wouldn't work to
extract information from kernel secrets, as well... 

If SHA has plaintext-dependent memory references, Colin's technique
would enable an adversary to extract the contents of the /dev/random
pools.  I don't *think* SHA does, based on a quick reading of
lib/sha1.c, but someone with an actual clue should probably take a look.

Andi, are you prepared to *require* that no code ever make a memory
reference as a function of a secret?  Because that's what you're
suggesting the crypto people should do.

-andy

Re: Hyper-Threading Vulnerability

[Barry K. Nathan]

On Fri, May 13, 2005 at 10:10:36AM -0400, Jeff Garzik wrote:
> Barry K. Nathan wrote:
> >On Fri, May 13, 2005 at 07:51:20AM +0200, Gabor MICSKO wrote:
> >
> >>Is this flaw affects the current stable Linux kernels? Workaround?
> >>Patch?
> 
> Simple.  Just boot a uniprocessor kernel, and/or disable HT in BIOS.
> 
> 
> >Some pages with relevant information:
> >http://www.ussg.iu.edu/hypermail/linux/kernel/0403.2/0920.html
> >http://bugzilla.kernel.org/show_bug.cgi?id=2317
> 
> These pages have zero information on the "flaw."  In fact, I can see no 
> information at all proving that there is even a problem here.

I meant that those two URL's have relevant information regarding
disabling HT for those of us who can't simply boot a UP kernel or
disable HT in the BIOS, not that they had information on the flaw.

-Barry K. Nathan <barryn@pobox.com>

Re: Hyper-Threading Vulnerability

[Barry K. Nathan]

On Fri, May 13, 2005 at 03:14:43PM -0400, Jim Crilly wrote:
> And what if you have more than one physical HT processor? AFAIK there's no
> way to disable HT and still run SMP at the same time.

Actually, there is; read my post earlier in this thread:
http://marc.theaimsgroup.com/?l=linux-kernel&m=111598859708620&w=2

To elaborate on the "check dmesg" part of that e-mail:

After you reboot with "maxcpus=2" (or however many physical CPU's you
have), you need to make sure you have messages like this, which indicate
that it really worked:

WARNING: No sibling found for CPU 0.
WARNING: No sibling found for CPU 1.

(and so on, if you have more than 2 CPU's)

-Barry K. Nathan <barryn@pobox.com>

Re: Hyper-Threading Vulnerability

[Frank Denis (Jedi/Sector One)]

On Fri, May 13, 2005 at 09:16:09PM +0200, Diego Calleja wrote:
> However they've patched the FreeBSD kernel to "workaround?" it:
> ftp://ftp.freebsd.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch

  This patch just disables hyperthreading by default.
  

Re: Hyper-Threading Vulnerability

[Grant Coady]

On Fri, 13 May 2005 14:49:25 -0400, Scott Robert Ladd <lkml@coyotegulch.com> wrote:

>Alan Cox wrote:
>> HT for most users is pretty irrelevant, its a neat idea but the
>> benchmarks don't suggest its too big a hit
>
>On real-world applications, I haven't seen HT boost performance by more
>than 15% on a Pentium 4 -- and the usual gain is around 5%, if anything
>at all. HT is a nice idea, but I don't enable it on my systems.

P4-HT is great for winxp, a runaway process only gets half the CPU 
resources, keeps the system responsive.  I like HT for that reason, 
perhaps that's what it was designed for?  Hardware fix for msft 'OS' :o)

Recently on single AMD CPU box, 2.6.latest-mm, diff got stuck, no 
disk activity, 100% CPU, started another terminal, recompiled kernel 
with 8K stacks and rebooted, the whole time the unkillable 'diff' 
was using just over 1/2 of resources.  top showed all 1GB RAM in use, 
no swap activity, nothing odd in /proc/whatever -- only happened once.

I suspected 4k stacks as only change before 'crash' was turning on 
samba server day before, but I didn't trace 'problem' as it wasn't 
really a crash.  Impressive -- seeing 2.6 handling a stupid process, 
business as usual for everything else.  Haven't had a problem since 
changing to 8K stacks.  nfs, samba and ssh terminals on reiserfs 3.6
on via sata.  May have had nvidia driver installed at the time, I 
now load that only when X running (rare), mostly headless use.

--Grant.

Re: Hyper-Threading Vulnerability

[Diego Calleja]

El Fri, 13 May 2005 20:03:58 +0200,
Andi Kleen <ak@muc.de> escribió:


> This is not a kernel problem, but a user space problem. The fix 
> is to change the user space crypto code to need the same number of cache line
> accesses on all keys. 


However they've patched the FreeBSD kernel to "workaround?" it:
ftp://ftp.freebsd.org/pub/FreeBSD/CERT/patches/SA-05:09/htt5.patch

Re: Hyper-Threading Vulnerability

[Jim Crilly]

On 05/13/05 02:38:03PM -0400, Richard F. Rebel wrote:
> On Fri, 2005-05-13 at 20:03 +0200, Andi Kleen wrote:
> > This is not a kernel problem, but a user space problem. The fix 
> > is to change the user space crypto code to need the same number of cache line
> > accesses on all keys. 
> > 
> > Disabling HT for this would the totally wrong approach, like throwing
> > out the baby with the bath water.
> > 
> > -Andi
> 
> Why?  It's certainly reasonable to disable it for the time being and
> even prudent to do so.

And what if you have more than one physical HT processor? AFAIK there's no
way to disable HT and still run SMP at the same time.

> 
> -- 
> Richard F. Rebel
> 
> cat /dev/null > `tty`

Jim.

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Fri, May 13, 2005 at 02:49:25PM -0400, Scott Robert Ladd wrote:
> Alan Cox wrote:
> > HT for most users is pretty irrelevant, its a neat idea but the
> > benchmarks don't suggest its too big a hit
> 
> On real-world applications, I haven't seen HT boost performance by more
> than 15% on a Pentium 4 -- and the usual gain is around 5%, if anything
> at all. HT is a nice idea, but I don't enable it on my systems.

I saw better improvement in some cases.  It always depends on the workload.
And on the generation of HT (there are three around). And lots of other
factors.

Even for your workload only it does not seem to me to be very rational
to throw away a 15% speedup with open eyes.

-Andi

Re: Hyper-Threading Vulnerability

[Andi Kleen]

On Fri, May 13, 2005 at 02:38:03PM -0400, Richard F. Rebel wrote:
> On Fri, 2005-05-13 at 20:03 +0200, Andi Kleen wrote:
> > This is not a kernel problem, but a user space problem. The fix 
> > is to change the user space crypto code to need the same number of cache line
> > accesses on all keys. 
> > 
> > Disabling HT for this would the totally wrong approach, like throwing
> > out the baby with the bath water.
> > 
> > -Andi
> 
> Why?  It's certainly reasonable to disable it for the time being and
> even prudent to do so.

No, i strongly disagree on that. The reasonable thing to do is
to fix the crypto code which has this vulnerability, not break
a useful performance enhancement for everybody else.

-Andi

Re: Hyper-Threading Vulnerability

[Andy Isaacson]

On Fri, May 13, 2005 at 11:30:27AM -0700, Vadim Lobanov wrote:
> On Fri, 13 May 2005, Andy Isaacson wrote:
> > It's a side channel timing attack on data-dependent computation through
> > the L1 and L2 caches.  Nice work.  In-the-wild exploitation is
> > difficult, though; your timing gets screwed up if you get scheduled away
> > from your victim, and you don't even know, because you can't tell where
> > you were scheduled, so on any reasonably busy multiuser system it's not
> > clear that the attack is practical.
> 
> Wouldn't scheduling appear as a rather big time delta (in measuring the
> cache access times), so you would know to disregard that data point?
> 
> (Just wondering... :-) )

Good question.  Yes, you can probably filter the data.  The question is,
how hard is it to set up the conditions to acquire the data?  You have
to be scheduled on the same core as the target process (sibling
threads).  And you don't know when the target is going to be scheduled,
and on a real-world system, there are other threads competing for
scheduling; if it's SMP (2 core, 4 thread) with perfect 100% utilization
then you've only got a 33% chance of being scheduled on the right
thread, and it gets worse if the machine is idle since the kernel should
schedule you and the OpenSSL process on different cores...

Getting the conditions right is challenging.  Not impossible, but
neither is it a foregone conclusion.

-andy

Re: Hyper-Threading Vulnerability

[Scott Robert Ladd]

Alan Cox wrote:
> HT for most users is pretty irrelevant, its a neat idea but the
> benchmarks don't suggest its too big a hit

On real-world applications, I haven't seen HT boost performance by more
than 15% on a Pentium 4 -- and the usual gain is around 5%, if anything
at all. HT is a nice idea, but I don't enable it on my systems.

..Scott

Re: Hyper-Threading Vulnerability

[Richard F. Rebel]

[-- Attachment #1: Type: text/plain, Size: 502 bytes --]

On Fri, 2005-05-13 at 20:03 +0200, Andi Kleen wrote:
> This is not a kernel problem, but a user space problem. The fix 
> is to change the user space crypto code to need the same number of cache line
> accesses on all keys. 
> 
> Disabling HT for this would the totally wrong approach, like throwing
> out the baby with the bath water.
> 
> -Andi

Why?  It's certainly reasonable to disable it for the time being and
even prudent to do so.

-- 
Richard F. Rebel

cat /dev/null > `tty`

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Hyper-Threading Vulnerability

[Alan Cox]

> This is not a kernel problem, but a user space problem. The fix 
> is to change the user space crypto code to need the same number of cache line
> accesses on all keys. 

You actually also need to hit the same cache line sequence on all keys
if you take a bit more care about it.

> Disabling HT for this would the totally wrong approach, like throwing
> out the baby with the bath water.

HT for most users is pretty irrelevant, its a neat idea but the
benchmarks don't suggest its too big a hit

Re: Hyper-Threading Vulnerability

[Eric Rannaud]

On Fri, 2005-05-13 at 20:03 +0200, Andi Kleen wrote:
> This is not a kernel problem, but a user space problem. The fix 
> is to change the user space crypto code to need the same number of cache line
> accesses on all keys. 

Well, this might not be trivial in general, and as pointed out by Colin
Perceval, this would require a major rewrite of OpenSSL RSA key
generation procedure. He also notes that other applications, a priori
less sensible, might also be targeted. And obviously, it would be
impractical to ensure this property in all application code.


> Disabling HT for this would the totally wrong approach, like throwing
> out the baby with the bath water.

Colin also mentions another work-around, at the level of the scheduler:

"[...] action must be taken to ensure that no pair of threads execute
simultaneously on the same processor core if they have different
privileges. Due to the complexities of performing such privilege checks
correctly and based on the principle that security fixes should be
chosen in such a way as to minimize the potential for new bugs to be
introduced, we recommend that existing operating systems provide the
necessary avoidance of inappropriate co-scheduling by never scheduling
any two threads on the same core, i.e., by only scheduling threads on
the first thread associated with each processor core. The more complex
solution of allowing certain "blessed" pairs of threads to be scheduled
on the same processor core is best delayed until future operating
systems where it can be extensively tested. In light of the potential
for information to be leaked across context switches, especially via the
L2 and larger cache(s), we also recommend that operating systems provide
some mechanism for processes to request special "secure" treatment,
which would include flushing all caches upon a context switch. It is not
immediately clear whether it is possible to use the occupancy of the
cache across context switches as a side channel, but if an unprivileged
user can cause his code to pre-empt a cryptographic operation
(e.g., by operating with a higher scheduling priority and being
repeatedly woken up by another process), then there is certainly a
strong possibility of a side
channel existing even in the absence of Hyper-Threading."

Is that relevant to the Linux kernel?

  /er.
-- 
"Sleep, she is for the weak"
http://www.eleves.ens.fr/home/rannaud/

Re: Hyper-Threading Vulnerability

[Vadim Lobanov]

On Fri, 13 May 2005, Andy Isaacson wrote:

> On Fri, May 13, 2005 at 10:32:48AM -0400, Jeff Garzik wrote:
> > Daniel Jacobowitz wrote:
> > >  http://www.daemonology.net/hyperthreading-considered-harmful/
> >
> > Already read it.  This link provides no more information than either of
> > the above links provide.
>
> He's posted his paper now.
>
> http://www.daemonology.net/papers/htt.pdf
>
> It's a side channel timing attack on data-dependent computation through
> the L1 and L2 caches.  Nice work.  In-the-wild exploitation is
> difficult, though; your timing gets screwed up if you get scheduled away
> from your victim, and you don't even know, because you can't tell where
> you were scheduled, so on any reasonably busy multiuser system it's not
> clear that the attack is practical.
>
> -andy
> -

Wouldn't scheduling appear as a rather big time delta (in measuring the
cache access times), so you would know to disregard that data point?

(Just wondering... :-) )

-Vadim

Re: Hyper-Threading Vulnerability

[Andi Kleen]

Gabor MICSKO <gmicsko@szintezis.hu> writes:

> Hi!
>
> From http://kerneltrap.org/node/5103
>
> ``Hyper-Threading, as currently implemented on Intel Pentium Extreme
> Edition, Pentium 4, Mobile Pentium 4, and Xeon processors, suffers from
> a serious security flaw," Colin explains. "This flaw permits local
> information disclosure, including allowing an unprivileged user to steal
> an RSA private key being used on the same machine. Administrators of
> multi-user systems are strongly advised to take action to disable
> Hyper-Threading immediately."
>
> ``More'' info here:
> http://www.daemonology.net/hyperthreading-considered-harmful/
>
> Is this flaw affects the current stable Linux kernels? Workaround?
> Patch?

This is not a kernel problem, but a user space problem. The fix 
is to change the user space crypto code to need the same number of cache line
accesses on all keys. 

Disabling HT for this would the totally wrong approach, like throwing
out the baby with the bath water.

-Andi

Re: Hyper-Threading Vulnerability

[Gabor MICSKO]

[-- Attachment #1: Type: text/plain, Size: 267 bytes --]


More info in this paper:

http://www.daemonology.net/papers/htt.pdf

 
> > FYI:
> >   http://www.daemonology.net/hyperthreading-considered-harmful/
> 
> Already read it.  This link provides no more information than either of 
> the above links provide.


[-- Attachment #2: Ez az üzenetrész digitális aláírással van ellátva --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Hyper-Threading Vulnerability

[Andy Isaacson]

On Fri, May 13, 2005 at 10:32:48AM -0400, Jeff Garzik wrote:
> Daniel Jacobowitz wrote:
> >  http://www.daemonology.net/hyperthreading-considered-harmful/
> 
> Already read it.  This link provides no more information than either of 
> the above links provide.

He's posted his paper now.

http://www.daemonology.net/papers/htt.pdf

It's a side channel timing attack on data-dependent computation through
the L1 and L2 caches.  Nice work.  In-the-wild exploitation is
difficult, though; your timing gets screwed up if you get scheduled away
from your victim, and you don't even know, because you can't tell where
you were scheduled, so on any reasonably busy multiuser system it's not
clear that the attack is practical.

-andy

Re: Hyper-Threading Vulnerability

[Jeff Garzik]

Daniel Jacobowitz wrote:
> On Fri, May 13, 2005 at 10:10:36AM -0400, Jeff Garzik wrote:
> 
>>Barry K. Nathan wrote:
>>
>>>On Fri, May 13, 2005 at 07:51:20AM +0200, Gabor MICSKO wrote:
>>>
>>>
>>>>Is this flaw affects the current stable Linux kernels? Workaround?
>>>>Patch?
>>
>>Simple.  Just boot a uniprocessor kernel, and/or disable HT in BIOS.
>>
>>
>>
>>>Some pages with relevant information:
>>>http://www.ussg.iu.edu/hypermail/linux/kernel/0403.2/0920.html
>>>http://bugzilla.kernel.org/show_bug.cgi?id=2317
>>
>>These pages have zero information on the "flaw."  In fact, I can see no 
>>information at all proving that there is even a problem here.
>>
>>Classic "I found a problem, but I'm keeping the info a secret" security 
>>crapola.
> 
> 
> FYI:
>   http://www.daemonology.net/hyperthreading-considered-harmful/

Already read it.  This link provides no more information than either of 
the above links provide.


> I don't much agree with Colin about the severity of the problem, but
> I've read his paper, which should be generally available later today.
> It's definitely a legitimate issue.

We'll see...

As of this moment, there continues to be _zero_ information proving that 
a problem exists.

	Jeff

Re: Hyper-Threading Vulnerability

[Daniel Jacobowitz]

On Fri, May 13, 2005 at 10:10:36AM -0400, Jeff Garzik wrote:
> Barry K. Nathan wrote:
> >On Fri, May 13, 2005 at 07:51:20AM +0200, Gabor MICSKO wrote:
> >
> >>Is this flaw affects the current stable Linux kernels? Workaround?
> >>Patch?
> 
> Simple.  Just boot a uniprocessor kernel, and/or disable HT in BIOS.
> 
> 
> >Some pages with relevant information:
> >http://www.ussg.iu.edu/hypermail/linux/kernel/0403.2/0920.html
> >http://bugzilla.kernel.org/show_bug.cgi?id=2317
> 
> These pages have zero information on the "flaw."  In fact, I can see no 
> information at all proving that there is even a problem here.
> 
> Classic "I found a problem, but I'm keeping the info a secret" security 
> crapola.

FYI:
  http://www.daemonology.net/hyperthreading-considered-harmful/

I don't much agree with Colin about the severity of the problem, but
I've read his paper, which should be generally available later today.
It's definitely a legitimate issue.

-- 
Daniel Jacobowitz
CodeSourcery, LLC

Re: Hyper-Threading Vulnerability

[Jeff Garzik]

Barry K. Nathan wrote:
> On Fri, May 13, 2005 at 07:51:20AM +0200, Gabor MICSKO wrote:
> 
>>Is this flaw affects the current stable Linux kernels? Workaround?
>>Patch?

Simple.  Just boot a uniprocessor kernel, and/or disable HT in BIOS.


> Some pages with relevant information:
> http://www.ussg.iu.edu/hypermail/linux/kernel/0403.2/0920.html
> http://bugzilla.kernel.org/show_bug.cgi?id=2317

These pages have zero information on the "flaw."  In fact, I can see no 
information at all proving that there is even a problem here.

Classic "I found a problem, but I'm keeping the info a secret" security 
crapola.

	Jeff

Re: Hyper-Threading Vulnerability

[Barry K. Nathan]

On Fri, May 13, 2005 at 07:51:20AM +0200, Gabor MICSKO wrote:
> Is this flaw affects the current stable Linux kernels? Workaround?
> Patch?

Some pages with relevant information:
http://www.ussg.iu.edu/hypermail/linux/kernel/0403.2/0920.html
http://bugzilla.kernel.org/show_bug.cgi?id=2317

AFAICT, the workaround is something like this:
1. If possible, disable HyperThreading in BIOS.
2. If you have only one CPU, boot a UP kernel rather than SMP.
3. If you have 2 or more CPU's and you can't disable HT in the BIOS,
   boot with "maxcpus=n", where "n" is the number of physical CPU's
   in the computer (e.g. "maxcpus=2"). If you are running a kernel
   earlier than 2.6.5 or 2.4.26, this probably isn't going to work.
   If you try this, check dmesg afterward to make sure it worked
   properly (see the bugzilla.kernel.org URL for details).
4. If you would try #3 except you are running a 2.4.xx *vendor* kernel
   (not mainline), where xx < 26, try "noht".
5. If #3 and #4 don't work, try "acpi=off".

Option #3 ("maxcpus=2") is what I expect to be deploying in the next
several hours, FWIW...

-Barry K. Nathan <barryn@pobox.com>

Hyper-Threading Vulnerability

[Gabor MICSKO]

[-- Attachment #1: Type: text/plain, Size: 684 bytes --]

Hi!

From http://kerneltrap.org/node/5103

``Hyper-Threading, as currently implemented on Intel Pentium Extreme
Edition, Pentium 4, Mobile Pentium 4, and Xeon processors, suffers from
a serious security flaw," Colin explains. "This flaw permits local
information disclosure, including allowing an unprivileged user to steal
an RSA private key being used on the same machine. Administrators of
multi-user systems are strongly advised to take action to disable
Hyper-Threading immediately."

``More'' info here:
http://www.daemonology.net/hyperthreading-considered-harmful/

Is this flaw affects the current stable Linux kernels? Workaround?
Patch?

Thanks.

-
MG

[-- Attachment #2: Ez az üzenetrész digitális aláírással van ellátva --]
[-- Type: application/pgp-signature, Size: 189 bytes --]