Simulation

pyecsca is able to simulate computation of key generation, ECDH and ECDSA while tracing particular actions performed by the implementation as well as intermediate values. These traces are collected by the context (see the Context and DefaultContext classes). There is always one context active. For performance reasons, by default it is a NullContext instance, which does not trace anything.

These traces are useful for attacks which rely on computing particular intermediate values during the ECC computation.

Initialisation

from binascii import hexlify
from copy import copy

from pyecsca.ec.key_generation import KeyGeneration
from pyecsca.ec.key_agreement import ECDH_SHA1
from pyecsca.ec.signature import ECDSA_SHA1
from pyecsca.ec.params import get_params
from pyecsca.ec.mult import LTRMultiplier
from pyecsca.ec.context import DefaultContext, local

p256 = get_params("secg", "secp256r1", "projective")
model = p256.curve.model
coords = p256.curve.coordinate_model

add = coords.formulas["add-2007-bl"]
dbl = coords.formulas["dbl-2007-bl"]

mult = LTRMultiplier(add, dbl, None)

Key generation

keygen = KeyGeneration(copy(mult), p256, False)

with local(DefaultContext()) as keygen_ctx:
    private, public = keygen.generate()
print(private)
print(public)
print(keygen_ctx.actions)

Signing

ecdsa = ECDSA_SHA1(copy(mult), p256, add, public, private)
data = b"something"

with local(DefaultContext()) as sign_ctx:
    signature = ecdsa.sign_data(data)
print(data)
print(signature)
print(sign_ctx.actions)

with local(DefaultContext()) as verify_ctx:
    verified = ecdsa.verify_data(signature, data)
print(verified)
print(verify_ctx.actions)

Key agreement

other_private, other_public = keygen.generate()

ecdh_a = ECDH_SHA1(copy(mult), p256, public, other_private)
ecdh_b = ECDH_SHA1(copy(mult), p256, other_public, private)
with local(DefaultContext()) as ecdh_ctx:
    ecdh_a_result = ecdh_a.perform()
    ecdh_b_result = ecdh_b.perform()
print(hexlify(ecdh_a_result))
print(hexlify(ecdh_b_result))
print(ecdh_a_result == ecdh_b_result)
print(ecdh_ctx.actions)

Walking the trace

As visible from the outputs above, DefaultContext traces the actions performed by the implementation in an ordered tree where the child relationship means that some actions happened during another action and order of children gives the order of operations. In the above example of ECDH, two ECDH executions are visible, each consisting of one scalar multuplication which consists of several applications of add and dbl formulas.

We can examine this tree in the first ECDH execution and see that the scalar multiplier used was not setup to be regular (see LTRMultiplier argument always) and that the order of operations leaks bits of the scalar. This fact will be easily exploitable on a power trace via SPA.

tree = ecdh_ctx.actions

ecdh_action, subtree = tree.get_by_index([0])

scalarmult_action, subtree = subtree.get_by_index([0])
recovered_private = 1
for formula_call in subtree:
    if formula_call.formula.shortname == "add":
        recovered_private |= 1
    elif formula_call.formula.shortname == "dbl":
        recovered_private <<= 1
    print(formula_call.formula.shortname)

print(bin(int(other_private)))
print(bin(int(recovered_private)))
print(other_private == recovered_private)

One can navigate the tree by indices, to get the second formula call of the second ECDH scalar multiplication:

action, subtree = tree.get_by_index([1, 0, 1])
print(repr(action))

The [1,0,1] path given above represented a walk through the execution trace, taking the second child of the root, then the first child then the second again.