ECDH Key-Extraction via Low-Bandwidth Electromagnetic Attacks on PCs
ECDH Key-Extraction via Low-Bandwidth Electromagnetic Attacks on PCs
 This web page contains an overview of, and Q&A
      about our recent results that were presented at the RSA
          Conference Cryptographers' Track (CT-RSA) 2016 on March 3rd.
       This research was conducted at the Laboratory
          for Experimental Information Security (LEISec).
      
      In March 2016 we
          published a follow-up paper, "ECDSA Key
            Extraction from Mobile Devices via Nonintrusive Physical
            Side Channels", about extracting ECDSA secret keys from mobile
          phones.
      Paper
      
        Daniel Genkin, Lev Pachmanov, Itamar Pipman, Eran Tromer, ECDH
            key-extraction via low-bandwidth electromagnetic attacks on PCs,
          proc. RSA Conference Cryptographers' Track (CT-RSA) 2016, LNCS 9610,
          219-235, Springer, 2016
        Latest version: [PDF]
        
        Archived on [eprint]
      
      Summary
      We show that the secret decryption keys can be extracted from PCs
        running the the ECDH encryption algorithm, using the electromagnetic
        emanations generated during the decryption process. By measuring the
        target's electromagnetic emanations, the attack extracts the secret
        decryption key within seconds, from a target located in an adjacent room
        across a wall. 
      ECDH (Elliptic Curve Diffie Hellman) is a standard public-key
        encryption algorithm used in OpenPGP,
        as specified in RFC 6637
        and NIST
          SP800-56A. We attacked the ECDH implementation of GnuPG's
        libgcrypt 1.6.3 (the latest version at the time the paper was written).
        The attack asks for decryption of a single carefully-chosen ciphertext,
        iterated a few dozen times, and then uses  time-frequency signal
        analysis techniques in order to extract from the electromagnetic leakage
        emitted by the target laptop during execution of ECDH decryptions.
      
         Attacker's setup for capturing EM emanations.
            Left to right: power supply, antenna on a stand, amplifiers,
            software defined radio (white box), analysis computer.
        
        Target laptop performing ECDH decryption using
            its secret key , on the other side of the wall.
        
      
      
      
      Q&A
      
       Q1: How vulnerable are GnuPG and other applications that use
        libgcrypt now?
      We have disclosed our attack to GnuPG developers under CVE-2015-7511
      and worked with the developers to implement countermeasures. GnuPG's
      Libgcrypt 1.6.5, containing these countermeasures and resistant to the
      key-extraction attack described here, was released concurrently with the
      public posting of these results.
      
      Specifically, Libgcrypt 1.6.5 completely changed their implementation of
      the elliptic-point curve multiplication, to the "double-and-always-add"
      algorithm. This is slower than the prior implementation, but more
      resistant to side-channel attack since the sequence of high-level
      arithmetic operations does not the depend on the secret key.
      
      Application-level status is as follows:
        On Linux:
        
           GnuPG 2.1.x typically
            use the system's libgcrypt library installation, so updating
            libgcrypt to 1.6.5 or newer is sufficient.
           GnuPG 1.x and 2.0.x
            does not support elliptic-curve cryptography.
        
        On Windows:
        
          Gpg4Win does not support
            elliptic-curve cryptography.
          Cygwin
            packages only the vulnerable libgcrypt 1.6.4, and does not package a
            GnuPG version that supports elliptic-curve cryptography (as of
            Feburary 16, 2016)
        
        On Mac:
        
          GnuPG for
              OS X 2.1.11-002 includes libgcrypt 1.6.5.
           Mac GPG in GPGTools does
            not support elliptic-curve cryptography.
        
      
      Q2: What does the measured signal look like?
      
      We measure the electromagnetic signal with suitable analog and digital
      filter, and then apply FM demodulation. The resulting signal looks like
      this:A segment of the electromagnetic signal obtained
            during a single decryption (after FM demodulation and filtering).
        
      
      In order to obtain a clearer trace and remove the interrupts, we aggregate
      several dozen recorded decryption traces. The resulting aggregate trace
      looks like this:A segment of the electromagnetic signal, after
            aggregating multiple measurements.
        
      The information required for successful key extraction is the sequence
      arithmetic operations done on the elliptic curve: doubling (marked as D
      above) and additions (marked as 1 or
      -1). 
      These operations can be gleaned above, but we can detect them much more
      reliably by analyzing the frequency components of the aggregated trace:Distinguishing between elliptic-point doubling
            and additions. Top: a segment aggregated trace. Middle: the
            spectrogram of the aggregated segment, where blue denotes
            frequencies with low-energy and red denotes frequencies with high
            energy. The bottom figure gives the final result of the processing,
            clearly showing the locations of the addition operations.
        
      
      From the identified elliptic-curve operations, the secret key can be
      completely reconstructed.
      Q3: You attacked ECDH. What about other cryptographic schemes?
      Other cryptographic schemes, running on PC-class computers, are also
      vulnerable to non-invasive
        physical side-channel key-extraction attacks. In prior works we
      attacked:
        RSA implementations using sliding-window and fixed-window
          exponentiation (shown at CHES'15),
          as well as square-and-always-multiply exponentiation (at
            CHES'14 and at CRYPTO'14)
        ElGamal implementations using sliding-window and fixed-window
          exponentiation (at CHES'15),
          as well as square-and-always-multiply exponentiation (at
            CHES'14).
      
      ECDH is faster than RSA and ElGamal, so it was harder to attack it using
      low-bandwidth measurements.
      
      Ongoing works evaluates the security of additional cryptographic schemes. Q4: What if I can't get physically close enough to the target
        computer?
      For RSA and ElGamal (though not yet for ECDH), similar attacks
        have been demonstrated from large distances:
      
        Laptop-chassis potential, measured from the far end
          of virtually any shielded cable connected to the laptop (such as
          Ethernet, USB, HDMI and VGA cables) can be used for key-extraction, as
          we demonstrated in a paper presented at
            CHES'14.
        Acoustic emanations (sound), measured via a microphone, can
          also be used to extract keys from a range of several meters, as we
          showed in a paper presented at CRYPTO'14.
      
      Q5: Is there a realistic way to perform a chosen-ciphertext attack on
        GnuPG?
      GnuPG is often invoked to decrypt externally-controlled inputs, fed
        into it by numerous frontends, via emails, files, chat and web pages.
        The list
of
          GnuPG frontends contains dozens of such applications, each of them
        can be potentially used in order to make the target decrypt the chosen
        ciphertexts required by our attack. As a concrete example, Enigmail
        (a popular plugin to the Thunderbird e-mail client) automatically
        decrypts incoming e-mail (for notification purposes) using GnuPG. An
        attacker can e-mail suitably-crafted messages to the victims (using the
        OpenPGP and PGP/MIME
        protocols), wait until they reach the target computer, and observe the
        target's EM emanations during their decryption (as shown above),
        thereby closing the attack loop. We have empirically verified that such
        an injection method does not have any noticeable effect on the leakage
        signal produced by GnuPG running on the target laptop. GnuPG's Outlook
        plugin, GpgOL also did not seem to alter the target's leakage signal. 
      Q6: How realistic is the attack? What is its cost in practice?
      The attack, in its current form, uses lab equipment that costs about
        $3000 and, as shown in the photo, is somewhat unwieldy. 
      However, experience shows that once the physical phenomena are
        understood in the lab, the attack setup can be miniaturized and
        simplified. This is especially true for low-banwidth attacks,
        such as ours, which measures frequencies that are three orders of
        magnitudes lower than the clock rate of the target computer. For
        example, in a we showed a compact for electromagnetic attacks on RSA and
        ElGamal encryption, called PITA: ostensibly Portable
            Instrument for Trace Acquisition, but aptly named after its
        portable form factor which fits inside typical pita bread. The PITA is
        improvised out of commodity parts and costs about $300. Other physical
        side channel attacks, such as acoustic
          attacks, can even be performed by a plain smartphone.
        
        Thus, it is likely that the new attack on ECDH can also be performed
        clandestinely and at at even lower cost. Most adversaries would not go
        through the trouble of using such techniques, given the sorry state of
        security vulnerabilities at the software level (after all, a thief will
        not bother climbing through a window if the front door is left
        unlocked). Thus, our work is most pertinent to systems that are
        carefully protected against software attacks, but � as we show � may be
        wide open to inexpensive physical attacks.
      
      
      Acknowledgments 
      We thank Werner
          Koch, Yutaka Niibe,
        developers of GnuPG, for the prompt response to our disclosure and the
        productive collaboration in adding suitable countermeasures.
        
        This work was sponsored by the Check
          Point Institute for Information Security; by the European
          Union's Tenth Framework Programme (FP10/2010-2016) under grant
        agreement 259426 ERC-CaC; by a Google
          Faculty Research Award; by the Israeli
          Ministry of Science and Technology; by the Israeli
          Centers of Research Excellence I-CORE Program (center 4/11); by
        the Leona M. & Harry B. Helmsley Charitable Trust; and by NATO's
          Public Diplomacy Division in the Framework of "Science for
        Peace".
       