Rowhammer Attack on Bitcoin

• 1) The computation of cryptographically secure digital signatures is one of the cornerstones in public-key cryptography. This widely used cryptographic primitive is standardized in the digital signature standard . The popular version of the digital signature scheme which uses elliptic curves is denoted ECDSA and is a variant of the classic signature system introduced by ECDSA. This scheme (as we recall in Section) 

• 2) requires to compute a random number used only once (denoted nonce) when signing a message.Since it is non-trivial to obtain a good pool of entropy in practice and due to some noticeable failures people started to deploy deterministic signature schemes where such randomness is not required. One such proposal modi es the existing ECDSA algorithm while another popular digital signature approach uses recent developments in the eld of elliptic curve cryptography: this approach is called EdDSA and uses a new curve model for performance considerations. To illustrate, it is shown that the performance of using Curve25519 (which is used in the EdDSA proposal) is over twice as fast compared to state-of-the-art implementation of NIST P-256 as proposed in the digital signature standard at a comparable security level. See also .The main advantage of these new deterministic digital signature proposals is clear: they don’t need a good entropy pool during signing. However, when such schemes are standardized this means they need to be supported in other use-cases and settings which might have a di erent security model. Examples of such use-cases include (hardware) implementations as used in smart cards and for the Internet-of-Things (IoT). In these settings the adversary might own (or have access to) the target device and use meta-information when executing the cryptographic implementation. Besides such passive side-channel attacks  one also has to guard the implementation againstactive attacks like fault-injection attacks and use the potentially corrupted output to obtain information about the secret key used.Although this security model, where techniques such as faults and advanced side-channel attacks are considered, is often overlooked by the cryptographic software community (since they often do not directly apply) this is a very relevant area for industry dealing with cryptographic hardware implementations and embedded devices. The impact of this security model is expected to grow signi cantly in the next few years: to illustrate, the current forecasts expect 8.4 billion connectedthings in use worldwide in 2017 and will reach 20.4 billion by 2020 . If one wants to secure such devices then these need to perform, among others, cryptographically secure digital signatures. For IoT devices which deal with sensitive (e.g., medical or privacy related) information then such a higher level of security protection against active and passive attacks might become a requirement.There is an active research community which deals with such side-channel attacks and a broad amount of cryptanalytic work related to fault and side-channel attacks on ECDSA as we recall in Section 2. Surprisingly, there is not much work related to deterministic signatures. As far as we are aware the only published result related to cryptographic faults and deterministic signatures. It is demonstrated how with the help of a single correct-fault signature pair the secret key can be extracted from deterministic version of DSA and ECDSA while they conclude that the EdDSA algorithm shows structural resistance against such attacks .It should be noted that recently a side-channel attack was pointed in [23] against Curve25519 when no validation of input points is performed as recommended in the original paper. Rowhammer attacks on deterministic signatures. In a fault attack on EdDSA is described: the attack is performed in a cloud scenario, and assumes an attacker whose virtual machine is co-located with the victim’s virtual machine. The results of this paper were already announced in comments on FIPS 186-4 [32].Independently of this work, the authors of [36] also published a di erential fault attack against the deterministic signature scheme EdDSA. The presented attack is the same as the one we present in Section 3.6. It should be noted that the countermeasure described in [36] is not su cient since one could still succeed and extract the secret key by using the other di erential attacks outlined in Section 3. Another independent work [37] shows that electromagnetic leakage in the message schedule of the hash computation in the deterministic signature scheme EdDSA can be used to derive the secret key. This is the same attack as we describe in Section 3.9.
  Our contributions. In this work we study the impact of fault and side-channel attacks on deterministic digital signature schemes in more details. More speci cally, we use the popular scheme EdDSA [7] as a use-case and illustrate nine di erent attacks on this scheme (but also show how these apply similarly to the deterministic ECDSA algorithm) in Section 3. This contradicts the conclusions from [3] where structural resistance against such attacks is claimed. We apply (single) faults in a di erent manner (compared to [3]) which results in a family of fault attacks against these new types of deterministic signature schemes.In Section 4 we discuss practical countermeasures against these new fault attacks. However, these new safe-guards come at the price of a signi cant performance impact which completely annihilates the bene ts when using such new digital signature approaches. We also propose a countermeasure which is not fully compliant with the current speci cation of the signature. The idea is to add some random noise to the input of the hash computation on platforms where such fault attacks are relevant. The veri cation method of the signature scheme remains unchanged but the signature schemeis no longer deterministic (in the sense that two messages always generate the same signature). We hope that this proposal can serve as additional input to the ongoing discussion and preparations for a new digital signature standard.
• Preliminaries
  The main idea behind fault attacks is to introduce a fault during the execution of the cryptographic algorithm and hope that this incorrect behavior leaks information about the secret key used. Examples related to digital signatures include introducing a fault in one of the coe cients of the elliptic curve equation such that computations are performed on a di erent (weak) curve or using a di erent base point [16,20]. Another possibility is a sign change attack where the sign change of intermediate points can be used to recover the secret scalar factor [12,38,2].Another type of fault attack is known as di erential fault attack (DFA) where the idea is to use the di erence between a faulty and a correct result to determine information about the secret key used (see [10] for the application of DFA to the elliptic curve scalar multiplication). This is the type of attack we are concerned with in this paper. The interested reader is referred to [26] and the surveys [19, Section 4] and [14] for more references and related work.We consider two types of fault: either an uncontrolled or a controlled fault during some target operation. With a controlled fault we mean the ability to inject a fault in a target memory range. For instance, ipping a bit in a byte, word or any range. These types of attacks are more di cult and expensive but still realistic (cf. [1]).
  1. (Deterministic) ECDSA
     In the digital signature standard [31] the randomized version of ECDSA is outlined together with some pseudo-random curves of prime order n. These curves are de ned in their a = −3 short Weierstrass form Eb : y2 = x3 − 3x + b. These curves are de ned over prime eld Fp where p > 3. Agenerator G ∈ Eb(Fp) of order n is speci ed. The private key is a uniform random non-zero residued ∈ Zn, in the range [1, n − 1], which de nes the public key point Q = dG. The exact algorithm is outlined in Algorithm 1 where H is a cryptographic hash function. If we refer to ECDSA we mean this version which uses randomized nonces as selected in Line 5 in Algorithm 1.
     Algorithm 1 ECDSA signature generation of a message m with the secret key d. The signaturerelated parameters are as recalled in Section 2.1.1: function ECDSA_sign(m, d) 2: e = H(m)3: repeat4: repeat5: Select u ∈ [1, n — 1] uniform random6: (x, y) = uG ∈ Eb(Fp)7: r = x mod n8: until r /= 09: s = u−1(e + dr) mod n10: until s /= 011: return (r, s)
     Algorithm 2 Deterministic ECDSA signature generation of a message m with the secret key d. The signature related parameters are as recalled in Section 2.1.1: function DetECDSA_sign(m, d) 2: e = H(m)3: repeat4: repeat5: u = GenerateU(d, e) using HMAC as building block (stateful) 6: (x, y) = uG ∈ Eb(Fp)7: r = x mod n8: until r /= 09: s = u−1(e + dr) mod n10: until s /= 011: return (r, s)
     A deterministic variant of ECDSA is described in an Internet Engineering Task Force (IETF) request for comments (RFC) [35]. The keys used are the same as in the randomized version of ECDSA and signatures remain valid with ECDSA: hence, no change to the veri cation is needed. The only change is how the nonce u is generated; in the deterministic variant this is done by a (complicated) procedure using HMAC as building block which ensures that given the same message and secret key the same value u is generated.We note that this RFC [35] explicitly acknowledges side-channel attacks as a serious threat and states that the implementer should use defensive measures to avoid leaking the private key through a side channel without stating how this should be done. Active attacks such as fault attacks are not addressed or considered.
  2. EdDSA
     The Edwards-curve Digital Signature Algorithm (EdDSA) is a variant of a Schnorr signature system [39] and speci es a deterministic digital signature algorithm using Edwards curves [17,9]. A generalized description of EdDSA takes the following eleven parameters [8]. One needs an odd prime(power) q which is used to de ne the nite eld Fq. Two elements a, d ∈ Fq which de ne the twisted Edwards curve Ea,d : ax2 + y2 = 1 + dx2y2 with an element B ∈ Ea,d(Fq) di erent from the neutral element. An integer c and odd prime l which de ne the cardinality of the curve (2cl = #Ea,d), aninteger n which determines the scalar size, an encoding of the nite eld elements, and a prehash function H1. Moreover, an integer parameter b is chosen such that 2b−1 > q. This determines the size of the signature (2b bits) and the length of the output of a cryptographic hash function H2(2b bits). How to properly choose these parameters is outside the scope of this document. It shouldbe noted that besides the encoding of nite eld elements (which we denote with EncInt) one also encodes elliptic curve points (in order to reduce the number of bytes required to represent elliptic curve points) which we denote with EncPoint.ΣAn EdDSA secret key is a b-bit value k while the public key is the b-bit EncPoint(A). The elliptic curve point is de ned as A = sB ∈ Ea,d(Fq), the scalar s = 2n + c≤i<n 2ihi where the hi are in turn obtained from the output of the hashed secret key as H2(k) = (h0, h1, . . . , h2b−1).The deterministic signature generation procedure is outlined in Algorithm 3.
     Algorithm 3 EdDSA signature generation of a message m with the secret key k. The signature related parameters are as recalled in Section 2.2.1: function EdDSA_sign((m, k)) 2: m′ = H1(m)3: Retrieve or compute (hb, . . . , h2b−1) from H2(k) = (h0, h1, . . . , h2b−1)4: r = H2(hb, . . . , h2b−1, m′) mod l5: R = rB ∈ Ea,d(Fq)6: t = H2(EncPoint(R), EncPoint(A), m′)7: S = (r + ts) mod l8: return (EncPoint(R), EncInt(S))
• Attacks against Deterministic Signature Schemes
  In this section we describe several di erential fault attacks and one side-channel attack on the deterministic signature scheme EdDSA. It should be noted that these attacks are not EdDSA speci c but apply to any deterministic signature scheme (following the same design approach). The main di erence between the deterministic and randomized signature schemes is how the nonce is generated. While this is done using a (truly) random number generator when using a randomized version this is typically a function of the input message and the private key for deterministic schemes. This immediately highlights the problems between the typical hardware and software platforms: randomness is di cult to get and expensive from a performance point of view in software while not a problem in hardware (with some notable exceptions [6]). While computing a function on the secret key can be done trivially in software this needs very careful and expensive countermeasures in the security model used in cryptographic hardware implementations.There are sophisticated lattice attacks on signature schemes which only require that the attacker is able to recover some bits of the ephemeral key for a certain number of signatures [33]. Typically one tries to recover the three least signi cant bits of the ephemeral key for, say, 300 signatures and one is then able to compute the victim’s secret key.Our high-level idea when performing a fault attack against EdDSA is to introduce a single fault at some point in the computation. Depending on the attack scenario this could be an uncontrolled fault somewhere during the computation or a controlled fault introduced in a pre-determined range (e.g., multiple bits, byte, or word). This fault alters the output of the signature generation procedure and allows an attacker to solve a (simple) system of equations and extract the secret key. We also present a passive attack where based on the power or electromagnetic information a side-channel attack might be mounted on the hash-function used in the deterministic signature scheme.An overview of the points of attack, the type of attack and the number of faults needed to extract the secret key against EdDSA is given in Table 1. Similar attacks can be mounted on deterministic ECDSA as listed in Table 2 These attacks are outlined in more detail in the next subsections.
  1. DFA on Base Point B During Import
     At some stage in the cryptographic implementation the generator or base point B, which is public and given in the EdDSA signature de nition, is loaded in order to perform the elliptic curve scalar multiplication with the deterministic nonce. If a fault is introduced in this generator (potentially resulting in a value which is not a valid point on the curve anymore) then one could obtain a validTable 1. Overview of the di erent proposed attacks against EdDSA which result in extracting the private key s.
     where attack type number of faultsImport point B fault uncontrolled ≥ 1, ,Import point A fault controlled ≥ 1 Hash computation of r fault controlled ≥ 1 Hash computation of r fault uncontrolled ≥ 1with xed (unknown) output, ,Scalar multiplication rB fault uncontrolled ≥ 1 Hash computation of t fault controlled ≥ 1 Hash computation of t fault controlled ≥ 2with xed (unknown) outputComputation of S fault controlled ≥ 1Hash computation of r DPA/DEMA
     Table 2. Overview of the di erent possible attacks against deterministic ECDSA which result in extracting the private key d.
     where attack type number of faults, ,Import point G fault uncontrolled ≥ 1 Hash computation of u fault controlled ≥ 1 Hash computation of u fault uncontrolled ≥ 1with xed (unknown) outputScalar multiplication uG fault uncontrolled ≥ 1Computation of s fault controlled ≥ 1Generation of u DPA/DEMA
     signature values (R, S) and an invalid one (Rr, Sr) for the same input message which represent(R, S) = (rB, r + ts mod l) (Rr, Sr) = (rBr, r + trs mod l)where tr = H2(EncPoint(Rr), EncPoint(A), mr). All input values for the hash computation of t andtr are either known (A and mr) or output by the algorithm (R and Rr). Hence, both t and tr areknown as well. This means the adversary can compute the secret key s fromS − Sr ≡ s(t − tr) mod lwhere all other values are known.
  2. DFA on Public Key A During ImportThe idea here is similar to the one described in Section 3.1 but requires additional e ort. The point of attack is the public key A during the import in the digital signature computation. If one can introduce a controlled fault in A in a restricted range, say ranging from bits i to j (where0 ≤ i ≤ j ≤ [log2(q)♩) then one could generate two signatures (R, S) and (R, Sr), one with theoriginal public key A and one with another (modi ed) public key Ar for the same input messagewhich represent(R, S) = (rB, r + ts mod l) (R, Sr) = (rB, r + trs mod l)where tr = H2(EncPoint(R), EncPoint(Ar), mr). If the number of bits j − i + 1 in the range where we introduced a fault is small enough (can be computationally enumerated) then the adversary cantry all possible values for Ar and hence tr. Hence, the adversary can compute the candidate secret key s fromS − Sr ≡ s(t − tr) mod land check if the right Ar was used by verifying if A = sB. If so, the secret key has been successfully extracted.
  3. DFA on Hash Computation of rThe point of attack is the hash computation of the nonce value r. Similar as in Section 3.2 the assumption is that the adversary can introduce a fault in the hash function computation which modi es only a limited number of bits in the digest value. More speci cally, we assume the introduced fault eˆ results in a nonce rr = r + eˆ. Hence, if one manages to generate two signatures (R, S) and (Rr, Sr), one with the original scalar r and one with such scalar rr, for the same input message then we have the following equations(R, S) = (rB, r + ts mod l) (Rr, Sr) = (rrB, rr + trs mod l)with tr = H2(EncPoint(Rr), EncPoint(A), mr). If the introduces error eˆ in rr is limited then one could exhaustively try all possibilities for eˆ and hence Rr = R + eˆB and tr. This results (again) ina simple system of equations which can be solved and checked if the right eˆ was used (by checkingA = sB). If so, the secret key has been extracted successfully.
  4. DFA on Hash Computation of r with Fixed OutputThe fault attack described here is a variation of the one described in Section 3.3. The point of attack is still the deterministic nonce r but now we assume an adversary can introduce one or more faults which result in the same value of rr which could be unknown to the adversary. One can think of multiple scenarios to achieve this in practice: examples include skipping the call of the hash function, during loading of the hash input, update of the hash state or copy of the hash result. Once this has been achieved the adversary has the equations(Rr, S1) = (rrB, rr + t1s mod l) (Rr, S2) = (rrB, rr + t2s mod l)2with t2 = H2(EncPoint(Rr), EncPoint(A), mr ). Again one can compute the secret key from S1 − S2since all other values except s are known.
  5. DFA on Scalar MultiplicationAnother possible point for a fault attack is the elliptic curve scalar multiplication rB. If the adversary could introduce an uncontrolled fault during this computation then it could generate two signatures with the same input(R, S) = (rB, r + ts mod l) (Rr, Sr) = (rrB, r + trs mod l)with tr = H2(EncPoint(Rr), EncPoint(A), mr) and some Rr. Please note that we have the correct r in the equation of Sr instead of rr since the fault was introduced in the scalar multiplication and not in the value of r. Again the secret key can be extracted from S − Sr since all values are known in this equation except s.
  6. DFA on Hash Computation of tOne could also introduce a controlled fault in the computation of the value t. If one can introduce this fault such that the faulty tr di ers in a restricted range, say ranging from bit i to j (where0 ≤ i ≤ j ≤ [log2(q)♩) then one could generate two signatures (R, S) and (R, Sr) as follows(R, S) = (rB, r + ts mod l)(R, Sr) = (rrB, r + trs mod l) .Hence, the adversary can compute the candidate secret key s from S − Sr ≡ s(t − tr) mod l and check if the right tr was used by verifying if A = sB. If so, the secret key has been successfullyextracted.
  7. DFA on Hash Computation of t with Fixed OutputIn the same vein as in Section 3.4 one could introduce two controlled faults to generate digital signatures (R1, S1) and (R2, S2) for two di erent messages m1 and m2, both with an unknown butxed value tr. Such faults could be introduced in multiple places: for example, skipping the call of the hash function, during loading of the hash input, update of the hash state or copy of the hash result. Next, generate the original two signatures (R3, S3) and (R4, S4) for the same messages m1 and m2. Then one obtains the following four equationsS1 = r1 + trs S2 = r2 + trs.S3 = r1 + t1sS4 = r2 + t2sGiven this information one can computeS3 − S4 − (S1 − S2) = (r1 − r2) + (t1 − t2)s − (r1 − r2) = (t1 − t2)sand the secret key s can be extracted.
  8. DFA on Computation of SIf the adversary manages to generate two signatures (R, S) and (R, Sr), one with the correct computation of S and one with faulty computation of S, then the secret key can be extracted. The faulty value Sr is obtained by skipping one of the elementary arithmetic operations in S = r + ts. Hence, depending on the fault one obtainsSr = tsSr = r + t . Sr = r + sDepending on the case the adversary can compute S − Sr = r, S − Sr = t(s − 1) or S − Sr = (t − 1)s, respectively. In all three cases one can compute r or s (and then s or r).
  9. DPA/DEMA on hb, . . . , h2b−1 during Hash Computation of rInstead of using an active attack, such as inserting fault(s), one could mount a passive attack based on either power consumption (such as the di erential power analysis (DPA) attack [28]) or electromagnetic usage (such as di erential electromagnetic analysis (DEMA) attacks [21]). In order for such an attack to be successful one needs to target a point in the algorithm where computation is performed on the secret together with some known data such that a di erential attack can be mounted.The main idea for such a passive attack is to target the computation of the message digest H2(hb, . . . , h2b—1, mr) where both secret key derived material and user provided data are used as input. If such a passive attack is feasible depends on the exact choice of the hash function and the value of b. In EdDSA the hash function H used is SHA-512 and b = 256, hence the input to the hash function is processed in chunks of 128 bytes (or 1024 bits). Since 256 bits of secret-key derivedmaterial is used as input this means the rst 1024-bit chunk processed by the SHA-512 contains both secret key and user controlled input. Hence, a DPA/DEMA attack in the usual way should be possible and the bits hb, . . . , h2b—1 can be extracted one at-a-time. This seems indeed feasible since a similar approach on HMAC based on SHA-256 is presented in [4].
• Countermeasures for EdDSAIn this section we describe two di erent sets of countermeasures against the attacks we presented in Section 3. The rst countermeasure does fully comply to the EdDSA speci cation while the second one does not: however, this last set of countermeasures does generate valid EdDSA signatures. This can only be distinguished from fully compliant signatures by the signer or by seeing the same message with two di erent signatures.
  1. Fully Compliant CountermeasuresFor some of the proposed attacks it might be su cient to check if the targeted elliptic curve points are valid by checking the curve equation: this is true for the attacks from Section 3.1, Section 3.2, and Section 3.5. However, in order to protect against the other fault attacks (from Section 3.3, Section 3.4, and Section 3.6 to Section 3.8) it seems double computation and a comparison of results seems the only practical countermeasure. In order to protect against the side-channel attack from Section 3.9 one needs to harden the hash computation, which will result on much slower hash computation. A guesstimate, based on our experience implementing such countermeasures, of the practical impact of these countermeasures on the performance is around two to three times slower.
  2. Not Fully Compliant CountermeasuresIn this section we outline e ective countermeasures against our proposed attacks. These attacks do not fully comply with the way how the deterministic signature algorithm states one needs to generate the nonces (see Algorithm 3). However, the proposed techniques are signi cantly faster compared to the compliant countermeasures considered in Section 4.1.A much simpler countermeasure, which randomized the signature algorithm, is to include some noise in the computation of r = H2(hb, . . . , h2b—1, mr) mod l. By adding some uniform random noise one ensures some variable unknown data is introduced in the various equations from Section 3. Oneway of achieving this is by splitting the input to the hash function into three hash input blocks:
     1. random noise (and/or counter),
     2. secret input (hb, . . . , h2b—1) and
     3. prehashed message mr.The amount of random noise depends on the needs and the targeted security level: hence, for SHA-512 noise with 256 bit of entropy is needed, but also less might be su cient to actually protect against collisions for practical real world attacks. If there is no random source available but non-volatile memory, one could also use an unknown counter. This of course leads to a stateful signing operation, but still stateless veri cation. This way the rst input block to the hash function generatesunique unknown (random) data to combine with the secret second block. The second block only consists of unknown secret data (hb, . . . , h2b—1) and known public xed (padding zeros) data. After processing the second block the hash state has full entropy coming from the secret data (but same for all signatures) and is di erent for each signature including some entropy coming from the noise. That means no easy collisions can be obtained and one cannot predict values easily.This countermeasure protects against DFA and DPA/DEMA attacks but of course one is still vulnerable against SPA and template attacks on the hash computation of r. One possible solution to this would be to simply use a fully random nonce r provided by an RNG. For this solution an RNG of su cient good quality is required, which might not be available on all platforms. However, in settings where such a level of security is often mandatory, e.g. on smart cards, one typically has access to a high-quality-RNG on board. This makes it signi cantly easier and faster to use the RNG instead of doing any hash computation.Hence, the best solution (in terms of performance) would actually be an adaptive solution depending on the availability of a high-quality-RNG. Such a solution would o er high-security garantuess on platforms where active and passive attacks can be expected (and where often acquiring good entropy is not a problem) while it o ers the same performance and security advantages in the pure software setting for the deterministic schemes as used today.
• Conclusions and Future Work

We have presented a number of active and one passive side-channel attack against deterministic signature schemes. This highlights that removing randomness from the equation does necessarily eliminate all attack vectors. Countermeasures which need to comply with the current speci cation of, for instance, EdDSA seem to have a signi cant performance impact: the resulting protected schemes seem to have no real performance bene ts over the current standardized (randomized) ECDSA algorithm. However, if one is willing to slightly deviate from the speci cation and introduce high-quality randomness on platforms where this is possible then relatively cheap countermeasures can be constructed without a ecting either the key generation and signature veri cation procedures. In this work we only looked at simple single di erential fault attacks. Future work include more advanced attacks (active and passive attacks) as well as introducing multiple faults. Of course it would be very interesting to study other more advanced countermeasures which either do comply directly with the current deterministic signature speci cation or can be computed more e ciently. We hope this work serves as valuable input when the community and the various standardization bodies start to de ne new cryptographic digital signature algorithms. In our opinion such a hybrid scheme (where the user can choose to include randomness or not) is a valuable addition to achieve a higher level of security.