Bug in modadd

[rdubois-crypto]

Description

Modular addition return false results on some input

Your environment

• Ubuntu23
• main
• Device NanoSplus

Steps to reproduce

run this code: (ZKN_CHECK is CX_CHECK)

ZKN_CHECK(cx_bn_lock(32, 0));

uint8_t out[32];
uint8_t n[32]={0x06, 0x0c, 0x89, 0xce, 0x5c, 0x26, 0x34, 0x05, 0x37, 0x0a, 0x08, 0xb6, 0xd0, 0x30, 0x2b, 0x0b, 0xab, 0x3e, 0xed, 0xb8, 0x39, 0x20, 0xee, 0x0a, 0x67, 0x72, 0x97, 0xdc, 0x39, 0x21, 0x26, 0xf1};
uint8_t a[32] = {
0x05, 0xa0, 0xc0, 0x91, 0x56, 0x83, 0x8b, 0x98,
0x28, 0xaf, 0x3f, 0x12, 0x67, 0xe1, 0x75, 0xe6,
0xe2, 0x84, 0xc7, 0x9d, 0x1b, 0x6d, 0x8a, 0xd0,
0xcd, 0x0a, 0xe0, 0xd9, 0x57, 0x90, 0x33, 0x6e
};

uint8_t b[32] = {
0x05, 0x81, 0xfb, 0x4a, 0x6e, 0x4a, 0xb5, 0xa8,
0x12, 0x0b, 0x82, 0x26, 0xdf, 0x95, 0x1e, 0x10,
0xd7, 0x94, 0xd8, 0xb7, 0x70, 0x5d, 0x1f, 0xb3,
0x6b, 0x99, 0x8e, 0xb9, 0x1a, 0x4b, 0x38, 0xe5
};

cx_bn_t bn_n;
cx_bn_t bn_a;
cx_bn_t bn_b;
cx_bn_t bn_r;

ZKN_CHECK(cx_bn_alloc_init(&bn_n,32,n,32));
ZKN_CHECK(cx_bn_alloc_init(&bn_a,32,a,32));
ZKN_CHECK(cx_bn_alloc_init(&bn_b,32,b,32));
ZKN_CHECK(cx_bn_alloc(&bn_r,32));

ZKN_CHECK(cx_bn_mod_add(bn_r,bn_a,bn_b,bn_n));
ZKN_CHECK(cx_bn_export(bn_r, out, 32));

io_send_response_pointer( out, 32, SW_OK);

Expected behaviour

/*
Fonction: cx_bn_mod_add(r, a, b, q)

a=0x05a0c09156838b9828af3f1267e175e6e284c79d1b6d8ad0cd0ae0d95790336e
b=0x0581fb4a6e4ab5a8120b8226df951e10d794d8b7705d1fb36b998eb91a4b38e5
q=0x060c89ce5c263405370a08b6d0302b0bab3eedb83920ee0a677297dc392126f1
r (attendu) = 0x0516320d68a80d3b03b0b882774668ec0edab29c52a9bc79d131d7b638ba4562
r (obtenu)= 0x0b22bbdbc4ce41403abac139477693f7ba19a0548bcaaa8438a46f9271db6c53

Diagnostic: absence de réduction modulaire, le résultat est a+b en place de (a+b)%q*/

Actual behaviour

r (obtenu)= 0xb22bbdbc4ce41403abac139477693f7ba19a0548bcaaa8438a46f9271db6c53 is
the non reduced value (a+b prior to reduction modulo q).

Proposed solution

return the reduced value. implement more intensive tests and formal verification.

[tdejoigny-ledger]

ty @rdubois-crypto for this feedback.
@srasoamiaramanana-ledger for visibility

[srasoamiaramanana-ledger]

Hi @rdubois-crypto, this is known and not a bug. It is due to a hardware optimization that I decided to keep. In that case, my proposed solution is to add a subtraction by 0 if the modular addition is the last operation of a sequence.

[rdubois-crypto]

Where is it documented ?

In that case what is the goal of the function compared to cx_bn_add if no reduction is performed? Why bother providing the modulus to the function ?

The behavior is not compliant to the https://github.com/LedgerHQ/ledger-secure-sdk/blob/master/include/ox_bn.h

/**

• @brief Performs a modular addition r = a + b mod n.
• @details r, a, b and n shall have the same BN size.

•      The values of *a* and *b* must be strictly smaller
  

•      than modulus value.
  

[rdubois-crypto]

Note also that speculos is returning the expected value, because it calls the openSSL BNMODADD compliant to the https://github.com/LedgerHQ/ledger-secure-sdk/blob/master/include/ox_bn.h header.

This means that the error only triggers during integration in hardware.

Most probable case is that the modadd is wrapping a function provided by the SE lib that implements some kind of "lazy reduction" (reduce when necessary, avoiding multiple reductions when several additions are chained). In that case it would be cleaner to either implement "modadd" as expected, or even better provide both the "lazy" and "regular" reductions with specification for the first one.