1
$\begingroup$

I would like to verify my system by running ECDSA NIST test vectors, but I am not getting expected output. I am able to calculate signature, but it is not right or at least "r" and "s" components contains different values than in nist vectors. What I am doing wrong?

Test vectors: NIST: FIPS 186-4 ECDSA - 186-3ecdsasiggencomponenttestvectors.zip

#include <mbedtls/ecdsa.h>
#include <mbedtls/ecp.h>
#include <mbedtls/bignum.h>
#include <mbedtls/entropy.h>
#include <mbedtls/ctr_drbg.h>

//All error checks removed

//The first of [P-256,SHA-256]-vectors
uint8_t ecc_d_p256[] = "\x51\x9b\x42...";
uint8_t ecc_hash_p256[] = "\x44\xac\xf6...":

const char *pers = "test";
mbedtls_mpi r, s, d;
mbedtls_ecp_group grp;
mbedtls_ctr_drbg_context ctr_drbg;
mbedtls_entropy_context mbedtls_entropy;

//Init
mbedtls_mpi_init(&r);
mbedtls_mpi_init(&s);
mbedtls_mpi_init(&d);
mbedtls_ecp_group_init(&grp);
mbedtls_ctr_drbg_init(&ctr_drbg);
mbedtls_entropy_init(&mbedtls_entropy);

//Setup values
mbedtls_ctr_drbg_seed(&ctr_drbg, mbedtls_entropy_func, &mbedtls_entropy, pers, 4);
mbedtls_mpi_read_binary(&d, ecc_d_p256, (sizeof(ecc_d_p256)-1));
mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_SECP256R1); 

//Sign
mbedtls_ecdsa_sign_det_ext(&grp, &r, &s, &d,
                           ecc_hash_p256, sizeof(ecc_hash_p256)-1,
                           MBEDTLS_MD_SHA256,
                           mbedtls_ctr_drbg_random,
                           &ot_mbedtls_ctr_drbg);

//Output
//"r" and "s" contains 32 byte outputs, but not "correct" ones
New contributor
KaljaTolkki is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
4
  • $\begingroup$ If you are testing the internal implementation then you would undoubtedly be able to test it by supplying the randomized values as input. If you cannot do that from the API then I'd say that you cannot really test it directly against the test vectors unfortunately. $\endgroup$
    – Maarten Bodewes
    Jan 14 at 14:43
  • $\begingroup$ Gilles is right, you are using the deterministic ECDSA, there are test vectors in RFC 6979 appendix-A.2 $\endgroup$
    – kelalaka
    2 days ago
  • $\begingroup$ The test vectors from FIPS CAVP do not support deterministic ECDSA mode. Deterministic ECDSA is now supported by test vectors provided by NIST's ACVP. The standardization of deterministic mode is being drafted in FIPS 186-5 (nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5-draft.pdf, see 6.3.2). You would need to connect your implementation to ACVP server to test it. Detailed description of the test vector structure can be found here: pages.nist.gov/ACVP/draft-fussell-acvp-ecdsa.html $\endgroup$ 2 days ago
  • $\begingroup$ One way to get those vectors from ACVP is to use the acvpproxy github.com/smuellerDD/acvpproxy $\endgroup$ 2 days ago
2
$\begingroup$

There are two variants of ECDSA: randomized or deterministic. The calculation of a signature involves a number $k$ which must not ever be repeated for distinct messages with the same key. There are two ways to implement that: generating $k$ randomly, or generating $k$ in a deterministic way from the key and the message. (I am omitting details here, just focusing on what's relevant for this question.) The two variants produce compatible signatures: it's impossible to tell which variant was used to produce a given signature. (Of course you can tell by asking an implementation to sign the same message twice and comparing the outputs.)

The original definition of ECDSA only considered the randomized variant, and this is the only one that NIST allows, as of FIPS 186-4 (see §6.3 and §6.4). RFC 6979 is a specification for the deterministic variant.

NIST test vectors were generated using randomized ECDSA. A consequence of using a randomized algorithm is that you cannot have known-answer tests for it. Every time you run a signature calculation, you get a different result. All you can do for testing is to test that the output of the signature calculation is a valid signature, not that it's a particular sequence of bytes.

mbedtls_ecdsa_sign_det_ext implements deterministic ECDSA. You can use known-answer tests for deterministic ECDSA. But NIST doesn't provide test vectors for it since NIST doesn't standardize deterministic ECDSA.

If you stretch this a bit, you could say that it's possible to have known-answer tests if you fully specify how the algorithm consumes the output of the random generator. But then as a theoretical matter, you're now testing a deterministic algorithm that's taking some input which in the real world is supposed to come from a random generator. And as a practical matter, in an actual implementation, it isn't always possible to swap out the random generator for testing. And in any case, FIPS 184-4 allows some variation in how the output of the random generator is consumed when generating $k$ for an ECDSA signature.

$\endgroup$
2
  • $\begingroup$ Nice catch about the det. I want add that NIST provides $k$ values so that one can replace random $k$ with given $k$ so that they can see their algorithm is working, then replace this code with random generated $k$s. Also, in RFC 6979, Thomas Pornin also provides test vectors. $\endgroup$
    – kelalaka
    2 days ago
  • $\begingroup$ Thank you for a great answer @Gilles 'SO- stop being evil'! Also I would like to say thanks to everyone else in this thread for help! I am not implementing algorithm nor am I aware whether I could provide "k" value without any implementation changes. For me RFC 6979 test vectors are enough. I was able to verify my pipe! $\endgroup$ 22 hours ago

Your Answer

KaljaTolkki is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.