Artifact Description for Fault Attacks on ECC Signature Verification

This artifact contains Sage scripts that showcase the attacks on ECSDSA and ECGDSA we presented in our paper. They can be used to forge signatures for arbitrary messages and a given public key in a matter of minutes, provided that a specific bit is flipped in the x-coordinate of an elliptic curve point.

Dependencies

SageMath (https://www.sagemath.org/). The scripts were tested with version 10.6 but older versions should also work up to a certain point.

Contents:

• ecc_affine.py/ecc_jacobian.py/ecc_projective.py: Python implementations of points on an elliptic curve in short Weierstraß form. Can be used to perform additions, doubling and scalar multiplication of elliptic curve points. These are the primitives we need for implementing the signature schemes. For the attack it does not matter which one is used meaning that they can freely be swapped out in the scripts importing them.
• secp192r1.py: Constants defining the secp192r1 curve.
• ecsdsa.sage: A sage implementation of the regular and optimized variants of the ECSDSA signature scheme as described in ISO 14888-3. The standard defines how the inputs and outputs should be encoded which is not implemented here for the sake of simplicity.
• ecgdsa.sage: A sage implementation of the ECGDSA signature scheme as described in ISO 14888-3. The standard defines how the inputs and outputs should be encoded which is not implemented here for the sake of simplicity.
• find_best_fault.sage: This script is used to find the bit-flip in the x-coordinate of a given point such that the faulted point has the smoothest order possible. We are not testing bit-flips in the y-coordinate since the results are already good enough to perform an attack.
• solve_ecsdsa.sage: A sage implementation of our attack on ECSDSA.
• solve_ecgdsa.sage: A sage implementation of our attack on ECGDSA.

Usage:

The scripts mentioned in this section will parse cli arguments. You can open the help by executing the scripts with the "-h" flag. We provide default values for all arguments so you can just run them right away. We suggest you start by running the examples with the default values first.

To do this, simply execute sage solve_ecgdsa.sage to forge and sage ecgdsa.sage to verify the signature with the default parameters we provide. You can do the same respectively for ECSDSA with sage solve_ecsdsa.sage and sage ecsdsa.sage.

If you want to play around with some values, you can run the run_ecgdsa_attack.sh and run_ecsdsa_attack.sh scripts that demonstrate how to use different keys, messages, and faults. A brief description on the relationships between the sage scripts and how they are used can be found below:

ECSDSA

1. Execute ecsdsa.sage with a custom seed to generate a new key pair.
   • sage ecsdsa.sage --seed ...
2. Execute solve_ecsdsa.sage with the newly generated public key and a custom message.
   • sage solve_ecsdsa.sage --public_x 0x... --public_y 0x... -m "..."
   • You could also try another bit flip with --fault-index .., however, the default value has already been set to the ideal fault for the secp192r1 generator. Setting random values here will likely not yield a solution within an acceptable timeframe.
   • Since not all values for the x-coordinate of point Q can be used to forge a signature you might need to try a few by specifying random values for it with --qx ...
3. After 5-15 minutes, a forged signature will be printed to stdout. You can now execute ecsdsa.sage again to verify that signature.
   • sage ecsdsa.sage --seed ... -r ... -s ... -m "..."

ECGDSA

Applying the attack on ECGDSA is very similar. Since we fault the public key in this case we need to perform an additional step.

1. Execute ecgdsa.sage with a custom seed to generate a new key pair.
   • sage ecsdsa.sage --seed ...
2. Execute find_best_fault.sage to find the best fault for the newly generated public key.
   • sage find_best_fault.sage --point_x 0x... --point_y 0x...
   • The script will return which bit-flip in the x-coordinate results in the point that generates the group with the smoothest order (i.e. the one for which the ECDLP is easiest to solve)
3. Execute solve_ecgdsa.sage with the generated public key, a custom message and specify which bit to flip in the public key point.
   • sage solve_ecgdsa.sage --public_x 0x... --public_y 0x... -m "..." --fault-index ...
   • Since not all values for the x-coordinate of point Q can be used to forge a signature you might need to try a few by specifying random values for it with -r ...
4. After 5-15 minutes, a forged signature will be printed to stdout. You can now execute ecgdsa.sage again to verify that signature.
   • sage ecgdsa.sage --seed ... -r ... -s ... -m "..." --fault-index ...