This image has an empty alt attribute; its file name is attacksafe-software-logo-1024x213.png
  1. Deterministic signature schemes such as dECDSA are highly susceptible to fault attacks . Consequently, faultattacks can be mounted against unprotected white-box implementations of dECDSA with minimal reverse-engineering efforts.
    1. WhiteBox Attack on Bitcoin Fault Model implementations can be altered by attackers at will. Therefore, we extend the term “fault“ to include any kind of modification of a white-box implementation. We refer to the outputs of a modified dECDSA implementation as faulty signatures.
    2. Faulty signatures can provide information on the secrets embedded in the dECDSA implementation.In contrast to conventional fault attack settings (e.g. laser fault attacks against hardware implementations), faults can easily be induced in white-box implementations in a controlled and deterministic manner. A modified dECDSA implementation yields a deterministic function that maps given or chosen hash values to faulty signatures.We consider the following fault model: We assume that an
    1. intermediate value ∈ Fcomputed or stored by Algorithm 1, such as kk−1, rdrdh, or rd h, is replaced by a faulty value (value fault) or by (differential fault), where := (hos) for some function : {01}256 → Fq.In Section 4.2, we revisit a simple fault attack that works for almost any function (uncontrolled faults) and requires only one correct/faulty signature pair. Since is arbitrary, value faults and differential faults are equivalent in this case. In Section 4.3 and Section 4.4, we consider fault attacks with value faults and differential faults, respectively, that exploit collisions of . Collisions of can, for instance, easily be found if the image := ({01}256) is small. Unlike some previously proposed attacks that require the set to be known (controlled faults) or the fault value to be recovered by computation analysis, our attack variants are based on collisions of fault values and work without knowledge of .
    2. As before, we denote the secret key of the white-box implementation by d ∈ F∗. For a hash value hi ∈ Fq, we denote the corresponding ephemeral key by ki ∈ F∗ and the correctsignature, computed by the original implementation on input hi, by (rc,i, sc,i) ∈ F∗ × F∗.q qThe faulty signature, computed by the modified implementation on input hi, will be denoted by (rf,i, sf,i) ∈ Fq × Fq, and the corresponding fault value by ei ∈ Fq.
    3. Simple Fault AttackLet : {01}256 → Fq be an arbitrary function.Uncontrolled fault in (faulty returned). We assume that an uncontrolled fault is induced in such that the faulty value of is returned as part of the faulty signature. In our fault model, step S3 of Algorithm 1 is replaced byS3’. Set r ← f (hos).In particular, we assume that the ephemeral key computed in step S2 remains unchanged. This fault attack could by realized by inducing a fault in the elliptic-curve part of the signature generation algorithm, for instance, by changing the prime (if used explicitly) or the reduction modulo p, the curve coefficients a, b (if used explicitly), the base point G, the point operations, or the scalar multiplication algorithm. This shows that the attack surface for this fault attack is quite large.The signature equations (1) of the correct and faulty signature for hi give rise to theFq-linear system
      which can be solved for d, ki.rc,i d − sc,i ki = −hi , rf,i d − sf,i ki = −hi ,(8)This simple fault attack, using only one correct/faulty signature pair, is possible because the attacker obtains the fault value as first part of the faulty signature and knows that this value is related to the second part of the signature via the signature equation. In the following two sections we consider fault attacks in which the fault values are not revealed to the attacker.
    4. Collision Fault AttacksLet : {01}256 → Fq be a function. We assume that collisions of can easily be found,e.g. that collisions occur with high probability for random inputs or that collisions occur for special inputs such as bit strings of low Hamming weight. This is for instance the case if the image := ({01}256) is small or, in particular, if = {e} is a singleton. The function , however, can be unknown.
      Value fault in or k1. First, we assume that a value fault (hos) is induced in or k−1. A value fault in can happen before or after the computation of r. We model the first case by replacing step S2 of Algorithm 1 byS2’. Set (k, z) ← rand(z) and set ← (hos).This fault attack could be realized by fixing the input or output of seed in step S1 such that becomes constant, but remains unchanged when used in step S4.A value fault in after the computation of can be modeled by replacing step S4 of Algorithm 1 byS4’. Set s ← f (hos)−1(rd + h) mod q.Similarly, a value fault in k−1 can be modeled by replacing step S4 byS4’. Set s ← f (hos)(rd + h) mod q.These fault attacks could be realized by skipping the multiplication by k−1 in step S4(special case = 1).For a value fault in k, the signature equation (1) of the faulty signature for hi yields the Fq-linear equationrf,i d − sf,i ei = −hi (9)with unknowns d, ei. If we find two inputs hi hj with ei = ej, we can solve the combinedlinear system for (d, ei) = (d, ej). We call this a (value) fault collision.Note that this fault attack does not even require the correct signature. However, since we have rc,i /= rf,i if the fault happens before the computation of r and rc,i = rf,i otherwise, we can use the correct signature to narrow down the fault location.Similarly, for a value fault in k−1 we obtain the linear equationirf,i d − sf,i e−1 = −hi (10)with unknowns d, e−1. If we find two inputs hi /= hj with ei = ej, we can solve thecombined linear systiem for (d, e−1) = (d, e−1).i jNote that a combined system of (9) is solvable if and only if the combined systemof (10) is solvable (ei and ej are replaced by e−1 and e−1).i jFurthermore, faulty signatures (rf,i, sf,i) with a fault in k before the computation of r are valid ECDSA signatures, albeit not the ones intended by the implementation. In particular, those faults in k cannot be detected by trial signature verification.
      Value fault in (correct returned) or rd. Next, we assume that a value fault (hos) is induced in such that the correct value of is returned as part of the faulty signature or in rd. We model the first case by replacing step S4 of Algorithm 1 byS4’. Set s ← k−1 f (hos)d + h mod q.This fault attack could be realized by skipping the multiplication by in step S4 (special case = 1).A value fault in rd can be modeled by replacing step S4 of Algorithm 1 byS4’. Set s ← k−1 f (hos) + h mod q.This fault attack could be realized by skipping the addition of rd in step S4 (special case = 0).For a value fault in r, the signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + eid = −hi
      (11)with unknowns d, ki, eid. If we find two inputs hi /= hj with ei = ej, we can solve the combined linear system for (d, ki, kj, eid) = (d, ki, kj, ejd).Similarly, for a value fault in rd we obtain the linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + ei = −hi
      (12)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (11) is solvable if and only if the combined system of (12) is solvable (eid and ejd are replaced by ei and ej).
      Value fault in d. Now, we assume that a value fault (hos) is induced in d. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(rf (hos) + h) mod q.This fault attack could be realized by skipping the multiplication by in step S4 (special case = 1).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + rf,i ei = −hi(13)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
      Value fault in h. Here we assume that a value fault (hos) is induced in h. In our fault model, either step S1 of Algorithm 1 is replaced byS1’. Set ← (hos) and set ← seed(hos). or step S4 is replaced byS4’. Set s ← k−1(rd + f (hos)) mod q.In particular, we assume that the input of seed in step S1 remains unchanged. This fault attack could be realized by skipping the addition of in step S4 (special case = 0).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,rf,i d − sf,i ki + ei = 0(14)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
      Value fault in rd h. Finally, we assume that a value fault (hos) is induced in rd h. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1f (hos) mod q.This fault attack could be realized by skipping the multiplication by rd in step S4(special case = 1).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + ei = 0(15)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
    5. Differential Collision Fault AttacksqLet : {01}256 → F∗ be a function. As in Section 4.3, we assume that collisions of can easily be found, but the function can be unknown.
      Differential fault in k. First, we assume that a differential fault (hos) is induced in k. In our fault model, either step S2 of Algorithm 1 is replaced byS2’. Set (k, z) ← rand(z) and set ← (hos). or S4 is replaced byS4’. Set ← ((hos))−1(rd h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i − sf,i k− sf,i e= −hi(16)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej). We call this a differential fault collision.Note that we have rc,i /= rf,i if the fault happens before the computation of r, and rc,i =rf,i otherwise.
      Differential fault in k1. Next, we assume that a differential fault (hos) is induced in k−1. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set ← (k−1 + (hos))(rd h) mod q.iThe correct and faulty signature for hi satisfy the equations sc,i = k−1(rc,i d + hi)and s = (k−1 + e )(r d + h ). Since r = r , we get s − s = (r d + h ).f,i ii f,i ic,if,ic,if,ieic,i iRearranging yields the Fq-linear equationirc,i d + (sc,i − sf,i) e−1 = −hi (17) with unknowns d, e−1. If we find two inputs hi /= hj with ei = ej, we can solve thecombined linear systiem for (d, e−1) = (d, e−1).i j
      Differential fault in (correct returned). Now, we assume that a differential fault (hos) is induced in such that the correct value of is returned as part of the faulty signature. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1((r + f (hos))d + h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i d − sf,i ki + eid = −hi(18)with unknowns d, ki, eid. If we find two inputs hi /= hj with ei = ej, we can solve the combined linear system for (d, ki, kj, eid) = (d, ki, kj, ejd).
      Differential fault in d. Here we assume that a differential fault (hos) is induced in d. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(r(d + f (hos)) + h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i − sf,i krf,i e= −hi(19)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (13) is solvable if and only if the combined system of (19) is solvable (ei and ej are replaced by ei + d and ej + d).Differential fault in rdh, or rd h. Finally, we assume that a differential fault (hos) is induced in rdh, or rd h. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(rd + h + f (hos)) mod q.For a differential fault in h, we could also replace step S1 byS1’. Set ← os2int(hos) + (hos) and set ← seed(hos),where we assume that the input of seed in step S1 is unchanged.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,rf,i d − sf,i ki + ei = −hi(20)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (18) is solvable if and only if the combined system of (20) is solvable (eid and ejd are replaced by ei and ej).
    6. Comparison with Previous WorkSeveral differential fault attacks on deterministic ECDSA and EdDSA were introduced in [ABF+18], which form the foundation of our approach. In particular, attacks with uncontrolled faults in the base point and the scalar multiplication are presented there, which can be subsumed by an uncontrolled fault in (with faulty returned). They also consider uncontrolled faults that lead to a constant but unknown ephemeral key, which is a value fault collision in in our notation. Finally, they present controlled faults with fault values from a small and known set as well as faults induced by operation skipping during the computation of s.In this paper, we extend the fault attacks presented in [ABF+18]. We systematically consider value fault collisions and differential fault collisions at every step of Algorithm 1, which leads to additional attacks that do not require knowledge on the set of fault values. Operation skipping attacks are subsumed as special cases of value fault collisions in our framework (at the cost of generating an extra correct/faulty signature pair).In [CSC+22], lattice-based fault attacks on deterministic ECDSA and EdDSA are investigated. There, the authors consider a fixed hash value and induce several random faults, which result in a number of faulty signatures for the given hash value. Based on these faulty signatures, the problem of recovering the private key is then reduced to solving an instance of the Hidden Number Problem (see Section 3.3).By contrast, in this paper we investigate scenarios, where we consider deterministic faultsfor two distinct hash values hi hj and for different steps of the signature computation,and we exploit these faults by using simple linear algebra.
    1. WhiteBox Attack on Bitcoin Fault Model implementations can be altered by attackers at will. Therefore, we extend the term “fault“ to include any kind of modification of a white-box implementation. We refer to the outputs of a modified dECDSA implementation as faulty signatures.
    2. Faulty signatures can provide information on the secrets embedded in the dECDSA implementation.In contrast to conventional fault attack settings (e.g. laser fault attacks against hardware implementations), faults can easily be induced in white-box implementations in a controlled and deterministic manner. A modified dECDSA implementation yields a deterministic function that maps given or chosen hash values to faulty signatures.We consider the following fault model: We assume that an
      1. intermediate value ∈ Fcomputed or stored by Algorithm 1, such as kk−1, rdrdh, or rd h, is replaced by a faulty value (value fault) or by (differential fault), where := (hos) for some function : {01}256 → Fq.In Section 4.2, we revisit a simple fault attack that works for almost any function (uncontrolled faults) and requires only one correct/faulty signature pair. Since is arbitrary, value faults and differential faults are equivalent in this case. In Section 4.3 and Section 4.4, we consider fault attacks with value faults and differential faults, respectively, that exploit collisions of . Collisions of can, for instance, easily be found if the image := ({01}256) is small. Unlike some previously proposed attacks that require the set to be known (controlled faults) or the fault value to be recovered by computation analysis, our attack variants are based on collisions of fault values and work without knowledge of .
      2. As before, we denote the secret key of the white-box implementation by d ∈ F∗. For a hash value hi ∈ Fq, we denote the corresponding ephemeral key by ki ∈ F∗ and the correctsignature, computed by the original implementation on input hi, by (rc,i, sc,i) ∈ F∗ × F∗.q qThe faulty signature, computed by the modified implementation on input hi, will be denoted by (rf,i, sf,i) ∈ Fq × Fq, and the corresponding fault value by ei ∈ Fq.
      3. Simple Fault AttackLet : {01}256 → Fq be an arbitrary function.Uncontrolled fault in (faulty returned). We assume that an uncontrolled fault is induced in such that the faulty value of is returned as part of the faulty signature. In our fault model, step S3 of Algorithm 1 is replaced byS3’. Set r ← f (hos).In particular, we assume that the ephemeral key computed in step S2 remains unchanged. This fault attack could by realized by inducing a fault in the elliptic-curve part of the signature generation algorithm, for instance, by changing the prime (if used explicitly) or the reduction modulo p, the curve coefficients a, b (if used explicitly), the base point G, the point operations, or the scalar multiplication algorithm. This shows that the attack surface for this fault attack is quite large.The signature equations (1) of the correct and faulty signature for hi give rise to theFq-linear system
        which can be solved for d, ki.rc,i d − sc,i ki = −hi , rf,i d − sf,i ki = −hi ,(8)This simple fault attack, using only one correct/faulty signature pair, is possible because the attacker obtains the fault value as first part of the faulty signature and knows that this value is related to the second part of the signature via the signature equation. In the following two sections we consider fault attacks in which the fault values are not revealed to the attacker.
      4. Collision Fault AttacksLet : {01}256 → Fq be a function. We assume that collisions of can easily be found,e.g. that collisions occur with high probability for random inputs or that collisions occur for special inputs such as bit strings of low Hamming weight. This is for instance the case if the image := ({01}256) is small or, in particular, if = {e} is a singleton. The function , however, can be unknown.
        Value fault in or k1. First, we assume that a value fault (hos) is induced in or k−1. A value fault in can happen before or after the computation of r. We model the first case by replacing step S2 of Algorithm 1 byS2’. Set (k, z) ← rand(z) and set ← (hos).This fault attack could be realized by fixing the input or output of seed in step S1 such that becomes constant, but remains unchanged when used in step S4.A value fault in after the computation of can be modeled by replacing step S4 of Algorithm 1 byS4’. Set s ← f (hos)−1(rd + h) mod q.Similarly, a value fault in k−1 can be modeled by replacing step S4 byS4’. Set s ← f (hos)(rd + h) mod q.These fault attacks could be realized by skipping the multiplication by k−1 in step S4(special case = 1).For a value fault in k, the signature equation (1) of the faulty signature for hi yields the Fq-linear equationrf,i d − sf,i ei = −hi (9)with unknowns d, ei. If we find two inputs hi hj with ei = ej, we can solve the combinedlinear system for (d, ei) = (d, ej). We call this a (value) fault collision.Note that this fault attack does not even require the correct signature. However, since we have rc,i /= rf,i if the fault happens before the computation of r and rc,i = rf,i otherwise, we can use the correct signature to narrow down the fault location.Similarly, for a value fault in k−1 we obtain the linear equationirf,i d − sf,i e−1 = −hi (10)with unknowns d, e−1. If we find two inputs hi /= hj with ei = ej, we can solve thecombined linear systiem for (d, e−1) = (d, e−1).i jNote that a combined system of (9) is solvable if and only if the combined systemof (10) is solvable (ei and ej are replaced by e−1 and e−1).i jFurthermore, faulty signatures (rf,i, sf,i) with a fault in k before the computation of r are valid ECDSA signatures, albeit not the ones intended by the implementation. In particular, those faults in k cannot be detected by trial signature verification.
        Value fault in (correct returned) or rd. Next, we assume that a value fault (hos) is induced in such that the correct value of is returned as part of the faulty signature or in rd. We model the first case by replacing step S4 of Algorithm 1 byS4’. Set s ← k−1 f (hos)d + h mod q.This fault attack could be realized by skipping the multiplication by in step S4 (special case = 1).A value fault in rd can be modeled by replacing step S4 of Algorithm 1 byS4’. Set s ← k−1 f (hos) + h mod q.This fault attack could be realized by skipping the addition of rd in step S4 (special case = 0).For a value fault in r, the signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + eid = −hi
        (11)with unknowns d, ki, eid. If we find two inputs hi /= hj with ei = ej, we can solve the combined linear system for (d, ki, kj, eid) = (d, ki, kj, ejd).Similarly, for a value fault in rd we obtain the linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + ei = −hi
        (12)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (11) is solvable if and only if the combined system of (12) is solvable (eid and ejd are replaced by ei and ej).
        Value fault in d. Now, we assume that a value fault (hos) is induced in d. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(rf (hos) + h) mod q.This fault attack could be realized by skipping the multiplication by in step S4 (special case = 1).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + rf,i ei = −hi(13)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
        Value fault in h. Here we assume that a value fault (hos) is induced in h. In our fault model, either step S1 of Algorithm 1 is replaced byS1’. Set ← (hos) and set ← seed(hos). or step S4 is replaced byS4’. Set s ← k−1(rd + f (hos)) mod q.In particular, we assume that the input of seed in step S1 remains unchanged. This fault attack could be realized by skipping the addition of in step S4 (special case = 0).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,rf,i d − sf,i ki + ei = 0(14)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
        Value fault in rd h. Finally, we assume that a value fault (hos) is induced in rd h. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1f (hos) mod q.This fault attack could be realized by skipping the multiplication by rd in step S4(special case = 1).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + ei = 0(15)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
      5. Differential Collision Fault AttacksqLet : {01}256 → F∗ be a function. As in Section 4.3, we assume that collisions of can easily be found, but the function can be unknown.
        Differential fault in k. First, we assume that a differential fault (hos) is induced in k. In our fault model, either step S2 of Algorithm 1 is replaced byS2’. Set (k, z) ← rand(z) and set ← (hos). or S4 is replaced byS4’. Set ← ((hos))−1(rd h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i − sf,i k− sf,i e= −hi(16)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej). We call this a differential fault collision.Note that we have rc,i /= rf,i if the fault happens before the computation of r, and rc,i =rf,i otherwise.
        Differential fault in k1. Next, we assume that a differential fault (hos) is induced in k−1. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set ← (k−1 + (hos))(rd h) mod q.iThe correct and faulty signature for hi satisfy the equations sc,i = k−1(rc,i d + hi)and s = (k−1 + e )(r d + h ). Since r = r , we get s − s = (r d + h ).f,i ii f,i ic,if,ic,if,ieic,i iRearranging yields the Fq-linear equationirc,i d + (sc,i − sf,i) e−1 = −hi (17) with unknowns d, e−1. If we find two inputs hi /= hj with ei = ej, we can solve thecombined linear systiem for (d, e−1) = (d, e−1).i j
        Differential fault in (correct returned). Now, we assume that a differential fault (hos) is induced in such that the correct value of is returned as part of the faulty signature. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1((r + f (hos))d + h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i d − sf,i ki + eid = −hi(18)with unknowns d, ki, eid. If we find two inputs hi /= hj with ei = ej, we can solve the combined linear system for (d, ki, kj, eid) = (d, ki, kj, ejd).
        Differential fault in d. Here we assume that a differential fault (hos) is induced in d. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(r(d + f (hos)) + h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i − sf,i krf,i e= −hi(19)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (13) is solvable if and only if the combined system of (19) is solvable (ei and ej are replaced by ei + d and ej + d).Differential fault in rdh, or rd h. Finally, we assume that a differential fault (hos) is induced in rdh, or rd h. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(rd + h + f (hos)) mod q.For a differential fault in h, we could also replace step S1 byS1’. Set ← os2int(hos) + (hos) and set ← seed(hos),where we assume that the input of seed in step S1 is unchanged.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,rf,i d − sf,i ki + ei = −hi(20)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (18) is solvable if and only if the combined system of (20) is solvable (eid and ejd are replaced by ei and ej).
      6. Comparison with Previous WorkSeveral differential fault attacks on deterministic ECDSA and EdDSA were introduced in [ABF+18], which form the foundation of our approach. In particular, attacks with uncontrolled faults in the base point and the scalar multiplication are presented there, which can be subsumed by an uncontrolled fault in (with faulty returned). They also consider uncontrolled faults that lead to a constant but unknown ephemeral key, which is a value fault collision in in our notation. Finally, they present controlled faults with fault values from a small and known set as well as faults induced by operation skipping during the computation of s.In this paper, we extend the fault attacks presented in [ABF+18]. We systematically consider value fault collisions and differential fault collisions at every step of Algorithm 1, which leads to additional attacks that do not require knowledge on the set of fault values. Operation skipping attacks are subsumed as special cases of value fault collisions in our framework (at the cost of generating an extra correct/faulty signature pair).In [CSC+22], lattice-based fault attacks on deterministic ECDSA and EdDSA are investigated. There, the authors consider a fixed hash value and induce several random faults, which result in a number of faulty signatures for the given hash value. Based on these faulty signatures, the problem of recovering the private key is then reduced to solving an instance of the Hidden Number Problem (see Section 3.3).By contrast, in this paper we investigate scenarios, where we consider deterministic faultsfor two distinct hash values hi hj and for different steps of the signature computation,and we exploit these faults by using simple linear algebra.
      1. WhiteBox Attack on Bitcoin Fault Model implementations can be altered by attackers at will. Therefore, we extend the term “fault“ to include any kind of modification of a white-box implementation. We refer to the outputs of a modified dECDSA implementation as faulty signatures.
      2. Faulty signatures can provide information on the secrets embedded in the dECDSA implementation.In contrast to conventional fault attack settings (e.g. laser fault attacks against hardware implementations), faults can easily be induced in white-box implementations in a controlled and deterministic manner. A modified dECDSA implementation yields a deterministic function that maps given or chosen hash values to faulty signatures.We consider the following fault model: We assume that an
      1. intermediate value ∈ Fcomputed or stored by Algorithm 1, such as kk−1, rdrdh, or rd h, is replaced by a faulty value (value fault) or by (differential fault), where := (hos) for some function : {01}256 → Fq.In Section 4.2, we revisit a simple fault attack that works for almost any function (uncontrolled faults) and requires only one correct/faulty signature pair. Since is arbitrary, value faults and differential faults are equivalent in this case. In Section 4.3 and Section 4.4, we consider fault attacks with value faults and differential faults, respectively, that exploit collisions of . Collisions of can, for instance, easily be found if the image := ({01}256) is small. Unlike some previously proposed attacks that require the set to be known (controlled faults) or the fault value to be recovered by computation analysis, our attack variants are based on collisions of fault values and work without knowledge of .
      2. As before, we denote the secret key of the white-box implementation by d ∈ F∗. For a hash value hi ∈ Fq, we denote the corresponding ephemeral key by ki ∈ F∗ and the correctsignature, computed by the original implementation on input hi, by (rc,i, sc,i) ∈ F∗ × F∗.q qThe faulty signature, computed by the modified implementation on input hi, will be denoted by (rf,i, sf,i) ∈ Fq × Fq, and the corresponding fault value by ei ∈ Fq.
      3. Simple Fault AttackLet : {01}256 → Fq be an arbitrary function.Uncontrolled fault in (faulty returned). We assume that an uncontrolled fault is induced in such that the faulty value of is returned as part of the faulty signature. In our fault model, step S3 of Algorithm 1 is replaced byS3’. Set r ← f (hos).In particular, we assume that the ephemeral key computed in step S2 remains unchanged. This fault attack could by realized by inducing a fault in the elliptic-curve part of the signature generation algorithm, for instance, by changing the prime (if used explicitly) or the reduction modulo p, the curve coefficients a, b (if used explicitly), the base point G, the point operations, or the scalar multiplication algorithm. This shows that the attack surface for this fault attack is quite large.The signature equations (1) of the correct and faulty signature for hi give rise to theFq-linear system
        which can be solved for d, ki.rc,i d − sc,i ki = −hi , rf,i d − sf,i ki = −hi ,(8)This simple fault attack, using only one correct/faulty signature pair, is possible because the attacker obtains the fault value as first part of the faulty signature and knows that this value is related to the second part of the signature via the signature equation. In the following two sections we consider fault attacks in which the fault values are not revealed to the attacker.
      4. Collision Fault AttacksLet : {01}256 → Fq be a function. We assume that collisions of can easily be found,e.g. that collisions occur with high probability for random inputs or that collisions occur for special inputs such as bit strings of low Hamming weight. This is for instance the case if the image := ({01}256) is small or, in particular, if = {e} is a singleton. The function , however, can be unknown.
        Value fault in or k1. First, we assume that a value fault (hos) is induced in or k−1. A value fault in can happen before or after the computation of r. We model the first case by replacing step S2 of Algorithm 1 byS2’. Set (k, z) ← rand(z) and set ← (hos).This fault attack could be realized by fixing the input or output of seed in step S1 such that becomes constant, but remains unchanged when used in step S4.A value fault in after the computation of can be modeled by replacing step S4 of Algorithm 1 byS4’. Set s ← f (hos)−1(rd + h) mod q.Similarly, a value fault in k−1 can be modeled by replacing step S4 byS4’. Set s ← f (hos)(rd + h) mod q.These fault attacks could be realized by skipping the multiplication by k−1 in step S4(special case = 1).For a value fault in k, the signature equation (1) of the faulty signature for hi yields the Fq-linear equationrf,i d − sf,i ei = −hi (9)with unknowns d, ei. If we find two inputs hi hj with ei = ej, we can solve the combinedlinear system for (d, ei) = (d, ej). We call this a (value) fault collision.Note that this fault attack does not even require the correct signature. However, since we have rc,i /= rf,i if the fault happens before the computation of r and rc,i = rf,i otherwise, we can use the correct signature to narrow down the fault location.Similarly, for a value fault in k−1 we obtain the linear equationirf,i d − sf,i e−1 = −hi (10)with unknowns d, e−1. If we find two inputs hi /= hj with ei = ej, we can solve thecombined linear systiem for (d, e−1) = (d, e−1).i jNote that a combined system of (9) is solvable if and only if the combined systemof (10) is solvable (ei and ej are replaced by e−1 and e−1).i jFurthermore, faulty signatures (rf,i, sf,i) with a fault in k before the computation of r are valid ECDSA signatures, albeit not the ones intended by the implementation. In particular, those faults in k cannot be detected by trial signature verification.
        Value fault in (correct returned) or rd. Next, we assume that a value fault (hos) is induced in such that the correct value of is returned as part of the faulty signature or in rd. We model the first case by replacing step S4 of Algorithm 1 byS4’. Set s ← k−1 f (hos)d + h mod q.This fault attack could be realized by skipping the multiplication by in step S4 (special case = 1).A value fault in rd can be modeled by replacing step S4 of Algorithm 1 byS4’. Set s ← k−1 f (hos) + h mod q.This fault attack could be realized by skipping the addition of rd in step S4 (special case = 0).For a value fault in r, the signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + eid = −hi
        (11)with unknowns d, ki, eid. If we find two inputs hi /= hj with ei = ej, we can solve the combined linear system for (d, ki, kj, eid) = (d, ki, kj, ejd).Similarly, for a value fault in rd we obtain the linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + ei = −hi
        (12)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (11) is solvable if and only if the combined system of (12) is solvable (eid and ejd are replaced by ei and ej).
        Value fault in d. Now, we assume that a value fault (hos) is induced in d. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(rf (hos) + h) mod q.This fault attack could be realized by skipping the multiplication by in step S4 (special case = 1).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + rf,i ei = −hi(13)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
        Value fault in h. Here we assume that a value fault (hos) is induced in h. In our fault model, either step S1 of Algorithm 1 is replaced byS1’. Set ← (hos) and set ← seed(hos). or step S4 is replaced byS4’. Set s ← k−1(rd + f (hos)) mod q.In particular, we assume that the input of seed in step S1 remains unchanged. This fault attack could be realized by skipping the addition of in step S4 (special case = 0).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,rf,i d − sf,i ki + ei = 0(14)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
        Value fault in rd h. Finally, we assume that a value fault (hos) is induced in rd h. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1f (hos) mod q.This fault attack could be realized by skipping the multiplication by rd in step S4(special case = 1).The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,− sf,i ki + ei = 0(15)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).
      5. Differential Collision Fault AttacksqLet : {01}256 → F∗ be a function. As in Section 4.3, we assume that collisions of can easily be found, but the function can be unknown.
        Differential fault in k. First, we assume that a differential fault (hos) is induced in k. In our fault model, either step S2 of Algorithm 1 is replaced byS2’. Set (k, z) ← rand(z) and set ← (hos). or S4 is replaced byS4’. Set ← ((hos))−1(rd h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i − sf,i k− sf,i e= −hi(16)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej). We call this a differential fault collision.Note that we have rc,i /= rf,i if the fault happens before the computation of r, and rc,i =rf,i otherwise.
        Differential fault in k1. Next, we assume that a differential fault (hos) is induced in k−1. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set ← (k−1 + (hos))(rd h) mod q.iThe correct and faulty signature for hi satisfy the equations sc,i = k−1(rc,i d + hi)and s = (k−1 + e )(r d + h ). Since r = r , we get s − s = (r d + h ).f,i ii f,i ic,if,ic,if,ieic,i iRearranging yields the Fq-linear equationirc,i d + (sc,i − sf,i) e−1 = −hi (17) with unknowns d, e−1. If we find two inputs hi /= hj with ei = ej, we can solve thecombined linear systiem for (d, e−1) = (d, e−1).i j
        Differential fault in (correct returned). Now, we assume that a differential fault (hos) is induced in such that the correct value of is returned as part of the faulty signature. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1((r + f (hos))d + h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i d − sf,i ki + eid = −hi(18)with unknowns d, ki, eid. If we find two inputs hi /= hj with ei = ej, we can solve the combined linear system for (d, ki, kj, eid) = (d, ki, kj, ejd).
        Differential fault in d. Here we assume that a differential fault (hos) is induced in d. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(r(d + f (hos)) + h) mod q.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi , rf,i − sf,i krf,i e= −hi(19)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (13) is solvable if and only if the combined system of (19) is solvable (ei and ej are replaced by ei + d and ej + d).Differential fault in rdh, or rd h. Finally, we assume that a differential fault (hos) is induced in rdh, or rd h. In our fault model, step S4 of Algorithm 1 is replaced byS4’. Set s ← k−1(rd + h + f (hos)) mod q.For a differential fault in h, we could also replace step S1 byS1’. Set ← os2int(hos) + (hos) and set ← seed(hos),where we assume that the input of seed in step S1 is unchanged.The signature equations (1) of the correct and faulty signature for hi yield the Fq-linear systemrc,i d − sc,i ki = −hi ,rf,i d − sf,i ki + ei = −hi(20)with unknowns d, ki, ei. If we find two inputs hi hj with ei = ej, we can solve thecombined linear system for (d, ki, kj, ei) = (d, ki, kj, ej).Note that a combined system of (18) is solvable if and only if the combined system of (20) is solvable (eid and ejd are replaced by ei and ej).
      6. Comparison with Previous WorkSeveral differential fault attacks on deterministic ECDSA and EdDSA were introduced in [ABF+18], which form the foundation of our approach. In particular, attacks with uncontrolled faults in the base point and the scalar multiplication are presented there, which can be subsumed by an uncontrolled fault in (with faulty returned). They also consider uncontrolled faults that lead to a constant but unknown ephemeral key, which is a value fault collision in in our notation. Finally, they present controlled faults with fault values from a small and known set as well as faults induced by operation skipping during the computation of s.In this paper, we extend the fault attacks presented in [ABF+18]. We systematically consider value fault collisions and differential fault collisions at every step of Algorithm 1, which leads to additional attacks that do not require knowledge on the set of fault values. Operation skipping attacks are subsumed as special cases of value fault collisions in our framework (at the cost of generating an extra correct/faulty signature pair).In [CSC+22], lattice-based fault attacks on deterministic ECDSA and EdDSA are investigated. There, the authors consider a fixed hash value and induce several random faults, which result in a number of faulty signatures for the given hash value. Based on these faulty signatures, the problem of recovering the private key is then reduced to solving an instance of the Hidden Number Problem (see Section 3.3).By contrast, in this paper we investigate scenarios, where we consider deterministic faultsfor two distinct hash values hi hj and for different steps of the signature computation,and we exploit these faults by using simple linear algebra.

    This image has an empty alt attribute; its file name is attacksafe-software-logo-1024x213.png