4 ms·

Flush+Reload: a High Resolution, Low Noise, L3 Cache Side-Channel Attack [pdf]

51 points by pedro84 13y ago

IbJacked 13y ago
So, according to this paper, "GnuPG in its current form is not safe for a multi-user system or for any system that may run untrusted code." The attack is against the RSA implementation specifically. Is there a gpg asymmetric encryption that would be considered safe? If not, is there a reasonable gpg alternative?
- lelf 13y ago
  http://lists.gnupg.org/pipermail/gnupg-announce/2013q3/000330.html http://lists.gnupg.org/pipermail/gnupg-announce/2013q3/00033... GnuPG 1.4.14 released What's New =========== * Mitigate the Yarom/Falkner flush+reload side-channel attack on RSA secret keys. See http://eprint.iacr.org/2013/448 Edit: and Libgcrypt 1.5.3 contains fix for GnuPG 2.x
- alcari 13y ago
  With their same logic, your software based CSPRNG isn't safe, and your browser isn't safe, and your full disk encryption isn't safe and all it requires is the trivial feat of being able to run arbitrary code as arbitrary users on your system without your knowledge.
  - tlb 13y ago
    GPG RSA is much leakier than the other things you mention, because it iterates through the bits of the plaintext doing either a lot of work or a little work at each bit if it's 1 or 0. Smarter implementations of RSA do the same amount of work every time, discarding it when the bit is 0.
  - bigiain 13y ago
    From the article: "Furthermore, as virtual machine hypervisors transparently share memory pages between VMs [5,19], the attack is applicable across the isolation layer between VMs" It's saying your VMs aren't safe - your Amazon/Linode/Rackspace/DigitalOcean/NineFold/Hertzner cloud instances _do_ have arbitrary users running arbitrary code on them – and the hypervisor can't protect you against what they do (in terms of manipulating the shared cache).
    - bcoates 13y ago
      The only reason for these operators to do memory sharing would be if it allowed them to oversubscribe RAM--is there any reason to believe any of them are doing that? It seems like it would lead to extremely noticeable and severe performance or stability issues in edge cases unless the provider required you to run a specific image on your instance.
  - earthrise 13y ago
    CSPRNGs and full disk encryption are probably safe, at least from this attack. Symmetric crypto usually doesn't use code whose execution depends on the secrets. There have been cache side-channels demonstrated against some AES implementations, but this attack requires some bit of code whose "execution-or-not" (for lack of a better term) reveals some information the user would like to keep secret. It is actually very worrying, since it might affect compression software (leak info about the file being compressed), text editors and other software that executes code based on key presses (cross-user keylogger), code whose execution depends on mouse actions e.g. button hover/click events (track another user's mouse), and so on. Essentially, it turns all "if", "while", and "for" statements into information leaks. I've written more about it here: https://defuse.ca/flush-reload-side-channel.htm https://defuse.ca/flush-reload-side-channel.htm
- hosay123 13y ago
  This is probably a naive solution.. What is to stop creating a statically linked build of GPG, create a new user account, chmod 0700 the new uid's homedir, copy the new binary into the private user account, and perform all your encryption work in there. So long as you're not running on a VM using tech like kernel samepage merging, pages from the binary should never be shared
  - mh- 13y ago
    for those unfamiliar with kernel samepage merging (KSM): http://lwn.net/Articles/330589/ http://lwn.net/Articles/330589/
nn3 13y ago
The key part is the first line in the abstract "Flush+Reload is a cache side-channel attack that monitors access to data in shared pages" The OS does not allow arbitary programs to share pages with gpg. If you share pages with gpg you can already read the key directly, no need for any side channels. As far as I can tell the paper is completely pointless, a variant of this fallacy http://blogs.msdn.com/b/oldnewthing/archive/2009/01/21/9353310.aspx http://blogs.msdn.com/b/oldnewthing/archive/2009/01/21/93533...
- tlb 13y ago
  It does this with code pages, to trace the control flow. All modern OSes let you map code read-only (either static or shared libraries) into multiple processes while sharing the physical memory.
  - nn3 13y ago
    The paper describes flushing the data pages. I don't see anything about the code pages in their algorithm.
    - tlb 13y ago
      It's confusing, but the "data" is instructions. It's explained in the first 4 paragraphs of section 5.
    - ris 13y ago
      It's a von neumann cache. The code is data. These people aren't idiots.
- bigiain 13y ago
  The OS isn't actually in control of that on a lot of cases these days - "Furthermore, as virtual machine hypervisors transparently share memory pages between VMs [5,19], the attack is applicable across the isolation layer between VMs"
  - bcoates 13y ago
contingencies 13y ago
Gentoo bug @ https://bugs.gentoo.org/show_bug.cgi?id=478184 https://bugs.gentoo.org/show_bug.cgi?id=478184
sspiff 13y ago
Can someone knowledgeable about security tell me if there is anything about their claim (98% in one round) that is exaggerated or "best edge case only"? I wonder how these attacks would fare against NaCl[1] or Sodium[2], who were designed to be secure against side-channel attacks. [1]: http://nacl.cr.yp.to http://nacl.cr.yp.to [2]: http://labs.umbrella.com/2013/03/06/announcing-sodium-a-new-cryptographic-library http://labs.umbrella.com/2013/03/06/announcing-sodium-a-new-...
- mrich 13y ago
  They have quite some preconditions that need to be in place: - You must know the code locations of the instructions that you target exactly. I.e. you will need to get down to the exact cache line of the operation in the compiled binary of the attacked program. They solve this by using a binary with debug symbols, in practice this will be harder as the binary will likely be stripped from debug symbols. - You can bet that there will be differences in the attack depending on the model of processor, let alone the manufacturer that will make it very hard to generalize this attack, increasing its cost. I think there are cheaper attacks for criminals/government agencies. Also, as mentioned below it is already mitigated by a GPG fix. But I found the paper quite interesting as I never considered such an attack before.
- Scaevolus 13y ago
  NaCl has neither data-dependent branches, nor data-dependent array indices.[1] This attack targets data-dependent branches. In NaCl, every cryptographic function executes in the same order, regardless of input data-- leaking no information about the input. [1]: http://nacl.cr.yp.to/features.html http://nacl.cr.yp.to/features.html
daemon13 13y ago
So, practical question I am on Ubuntu LTS 12.04 with GnuPG 1.4.11 (Linux version 3.2.0-32-virtual (buildd@batsu) (gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)). Q1. Do I need to fix this potential attack? Q2. Assuming this fix is not backported [now] - if I compile fresh gpg and swap the binary with the old gpg - will this fix it?
- mrich 13y ago
  Q1: Yes, it is fixed in 1.4.14 only. Q2: Cleanest would be to uninstall GnuPG and install latest from source. Make sure to backup relevant directories containing GnuPG related data (probably in your home - sorry I'm not familiar with Ubuntu)
  - e12e 13y ago
    BIG WARNING - THIS IS NOT THE BEST WAY TO INSTALL GNUPG! IT DOES NOT VERIFY ANY (REAL) SIGNATURES!! FYI - Debian unstable (aka sid) has a pacakge, and there is a backport to Ubuntu Saucy. I'm not sure what the best/easiest way to automatically pull down sources for a newer release than the release you're running in Ubuntu (there might be some apt-add magick for source mirrors?) -- but since it is up at launchpad[1], you can: a) try the binaries b) build the debs yourself (aka manually "backport"): mkdir tmp/gnupg -p cd tmp/gnupg sudo apt-get build-dep gnupg sudo aptitude install dpkg-dev #This might get pulled #in by the line above wget https://launchpad.net/ubuntu/saucy/+source/gnupg/1.4.14-1ubuntu1/+files/gnupg_1.4.14.orig.tar.gz \ https://launchpad.net/ubuntu/saucy/+source/gnupg/1.4.14-1ubuntu1/+files/gnupg_1.4.14-1ubuntu1.debian.tar.gz \ https://launchpad.net/ubuntu/saucy/+source/gnupg/1.4.14-1ubuntu1/+files/gnupg_1.4.14-1ubuntu1.dsc tar xzf gnupg_1.4.14.orig.tar.gz cd gnupg-1.4.14 tar xzf gnupg_1.4.14-1ubuntu1.debian.tar.gz cd debian dpkg-buildpackage cd .. sudo dpkg -i gpgv_1.4.14-1ubuntu1_amd64.deb \ gnupg_1.4.14-1ubuntu1_amd64.deb \ gnupg-curl_1.4.14-1ubuntu1_amd64.deb Note: This might not be a good idea with a package that is as imprtant as gnupg (among other things apt package lists are signed with gnupg!). And as you can also see above, the packages are not signed (explicitly, even if they do come in via https...). At least this built fine under wheezy -- but I haven't tried installing them (I'm not that worried that someone will snoop my workstation cache..). So not really meant for advice on how to get an upstream gnupg -- but useful with a few other well-behaved programs. So big warning, practice safe hex and all that!

51 points by pedro84 13y ago

So, according to this paper, "GnuPG in its current form is not safe for a multi-user system or for any system that may run untrusted code." The attack is against the RSA implementation specifically. Is there a gpg asymmetric encryption that would be considered safe? If not, is there a reasonable gpg alternative?

lelf 13y ago
http://lists.gnupg.org/pipermail/gnupg-announce/2013q3/000330.html http://lists.gnupg.org/pipermail/gnupg-announce/2013q3/00033... GnuPG 1.4.14 released What's New =========== * Mitigate the Yarom/Falkner flush+reload side-channel attack on RSA secret keys. See http://eprint.iacr.org/2013/448 Edit: and Libgcrypt 1.5.3 contains fix for GnuPG 2.x
alcari 13y ago
With their same logic, your software based CSPRNG isn't safe, and your browser isn't safe, and your full disk encryption isn't safe and all it requires is the trivial feat of being able to run arbitrary code as arbitrary users on your system without your knowledge.
- tlb 13y ago
  GPG RSA is much leakier than the other things you mention, because it iterates through the bits of the plaintext doing either a lot of work or a little work at each bit if it's 1 or 0. Smarter implementations of RSA do the same amount of work every time, discarding it when the bit is 0.
- bigiain 13y ago
  From the article: "Furthermore, as virtual machine hypervisors transparently share memory pages between VMs [5,19], the attack is applicable across the isolation layer between VMs" It's saying your VMs aren't safe - your Amazon/Linode/Rackspace/DigitalOcean/NineFold/Hertzner cloud instances _do_ have arbitrary users running arbitrary code on them – and the hypervisor can't protect you against what they do (in terms of manipulating the shared cache).
  - bcoates 13y ago
    The only reason for these operators to do memory sharing would be if it allowed them to oversubscribe RAM--is there any reason to believe any of them are doing that? It seems like it would lead to extremely noticeable and severe performance or stability issues in edge cases unless the provider required you to run a specific image on your instance.
- earthrise 13y ago
  CSPRNGs and full disk encryption are probably safe, at least from this attack. Symmetric crypto usually doesn't use code whose execution depends on the secrets. There have been cache side-channels demonstrated against some AES implementations, but this attack requires some bit of code whose "execution-or-not" (for lack of a better term) reveals some information the user would like to keep secret. It is actually very worrying, since it might affect compression software (leak info about the file being compressed), text editors and other software that executes code based on key presses (cross-user keylogger), code whose execution depends on mouse actions e.g. button hover/click events (track another user's mouse), and so on. Essentially, it turns all "if", "while", and "for" statements into information leaks. I've written more about it here: https://defuse.ca/flush-reload-side-channel.htm https://defuse.ca/flush-reload-side-channel.htm
hosay123 13y ago
This is probably a naive solution.. What is to stop creating a statically linked build of GPG, create a new user account, chmod 0700 the new uid's homedir, copy the new binary into the private user account, and perform all your encryption work in there. So long as you're not running on a VM using tech like kernel samepage merging, pages from the binary should never be shared
- mh- 13y ago
  for those unfamiliar with kernel samepage merging (KSM): http://lwn.net/Articles/330589/ http://lwn.net/Articles/330589/

nn3 13y ago

The key part is the first line in the abstract "Flush+Reload is a cache side-channel attack that monitors access to data in shared pages" The OS does not allow arbitary programs to share pages with gpg. If you share pages with gpg you can already read the key directly, no need for any side channels. As far as I can tell the paper is completely pointless, a variant of this fallacy http://blogs.msdn.com/b/oldnewthing/archive/2009/01/21/9353310.aspx http://blogs.msdn.com/b/oldnewthing/archive/2009/01/21/93533...

tlb 13y ago
It does this with code pages, to trace the control flow. All modern OSes let you map code read-only (either static or shared libraries) into multiple processes while sharing the physical memory.
- nn3 13y ago
  The paper describes flushing the data pages. I don't see anything about the code pages in their algorithm.
  - tlb 13y ago
    It's confusing, but the "data" is instructions. It's explained in the first 4 paragraphs of section 5.
  - ris 13y ago
    It's a von neumann cache. The code is data. These people aren't idiots.
bigiain 13y ago
The OS isn't actually in control of that on a lot of cases these days - "Furthermore, as virtual machine hypervisors transparently share memory pages between VMs [5,19], the attack is applicable across the isolation layer between VMs"
- bcoates 13y ago

contingencies 13y ago

Gentoo bug @ https://bugs.gentoo.org/show_bug.cgi?id=478184 https://bugs.gentoo.org/show_bug.cgi?id=478184

sspiff 13y ago

Can someone knowledgeable about security tell me if there is anything about their claim (98% in one round) that is exaggerated or "best edge case only"? I wonder how these attacks would fare against NaCl[1] or Sodium[2], who were designed to be secure against side-channel attacks. [1]: http://nacl.cr.yp.to http://nacl.cr.yp.to [2]: http://labs.umbrella.com/2013/03/06/announcing-sodium-a-new-cryptographic-library http://labs.umbrella.com/2013/03/06/announcing-sodium-a-new-...

mrich 13y ago
They have quite some preconditions that need to be in place: - You must know the code locations of the instructions that you target exactly. I.e. you will need to get down to the exact cache line of the operation in the compiled binary of the attacked program. They solve this by using a binary with debug symbols, in practice this will be harder as the binary will likely be stripped from debug symbols. - You can bet that there will be differences in the attack depending on the model of processor, let alone the manufacturer that will make it very hard to generalize this attack, increasing its cost. I think there are cheaper attacks for criminals/government agencies. Also, as mentioned below it is already mitigated by a GPG fix. But I found the paper quite interesting as I never considered such an attack before.
Scaevolus 13y ago
NaCl has neither data-dependent branches, nor data-dependent array indices.[1] This attack targets data-dependent branches. In NaCl, every cryptographic function executes in the same order, regardless of input data-- leaking no information about the input. [1]: http://nacl.cr.yp.to/features.html http://nacl.cr.yp.to/features.html

daemon13 13y ago

So, practical question I am on Ubuntu LTS 12.04 with GnuPG 1.4.11 (Linux version 3.2.0-32-virtual (buildd@batsu) (gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)). Q1. Do I need to fix this potential attack? Q2. Assuming this fix is not backported [now] - if I compile fresh gpg and swap the binary with the old gpg - will this fix it?

mrich 13y ago
Q1: Yes, it is fixed in 1.4.14 only. Q2: Cleanest would be to uninstall GnuPG and install latest from source. Make sure to backup relevant directories containing GnuPG related data (probably in your home - sorry I'm not familiar with Ubuntu)
- e12e 13y ago
  BIG WARNING - THIS IS NOT THE BEST WAY TO INSTALL GNUPG! IT DOES NOT VERIFY ANY (REAL) SIGNATURES!! FYI - Debian unstable (aka sid) has a pacakge, and there is a backport to Ubuntu Saucy. I'm not sure what the best/easiest way to automatically pull down sources for a newer release than the release you're running in Ubuntu (there might be some apt-add magick for source mirrors?) -- but since it is up at launchpad[1], you can: a) try the binaries b) build the debs yourself (aka manually "backport"): mkdir tmp/gnupg -p cd tmp/gnupg sudo apt-get build-dep gnupg sudo aptitude install dpkg-dev #This might get pulled #in by the line above wget https://launchpad.net/ubuntu/saucy/+source/gnupg/1.4.14-1ubuntu1/+files/gnupg_1.4.14.orig.tar.gz \ https://launchpad.net/ubuntu/saucy/+source/gnupg/1.4.14-1ubuntu1/+files/gnupg_1.4.14-1ubuntu1.debian.tar.gz \ https://launchpad.net/ubuntu/saucy/+source/gnupg/1.4.14-1ubuntu1/+files/gnupg_1.4.14-1ubuntu1.dsc tar xzf gnupg_1.4.14.orig.tar.gz cd gnupg-1.4.14 tar xzf gnupg_1.4.14-1ubuntu1.debian.tar.gz cd debian dpkg-buildpackage cd .. sudo dpkg -i gpgv_1.4.14-1ubuntu1_amd64.deb \ gnupg_1.4.14-1ubuntu1_amd64.deb \ gnupg-curl_1.4.14-1ubuntu1_amd64.deb Note: This might not be a good idea with a package that is as imprtant as gnupg (among other things apt package lists are signed with gnupg!). And as you can also see above, the packages are not signed (explicitly, even if they do come in via https...). At least this built fine under wheezy -- but I haven't tried installing them (I'm not that worried that someone will snoop my workstation cache..). So not really meant for advice on how to get an upstream gnupg -- but useful with a few other well-behaved programs. So big warning, practice safe hex and all that!