Erroneous comment and VERIFY_CHECK in ecdsa_sig_sign

[LLFourn]

I've been following along the ECDSA signing code and have come across what I think is an incorrect comment. In secp256k1_ecdsa_sig_sign the code makes the following recommendation:

secp256k1/src/ecdsa_impl.h

Lines 285 to 293 in 96d8ccb

	secp256k1_ecmult_gen(ctx, &rp, nonce);
	secp256k1_ge_set_gej(&r, &rp);
	secp256k1_fe_normalize(&r.x);
	secp256k1_fe_normalize(&r.y);
	secp256k1_fe_get_b32(b, &r.x);
	secp256k1_scalar_set_b32(sigr, b, &overflow);
	/* These two conditions should be checked before calling */
	VERIFY_CHECK(!secp256k1_scalar_is_zero(sigr));
	VERIFY_CHECK(overflow == 0);

However, these two conditions are not actually checked before calling. The main call doesn't:

secp256k1/src/secp256k1.c

Lines 491 to 510 in 96d8ccb

	while (1) {
	int koverflow;
	ret = noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count);
	if (!ret) {
	break;
	}
	secp256k1_scalar_set_b32(&non, nonce32, &koverflow);
	koverflow |= secp256k1_scalar_is_zero(&non);
	/* The nonce is still secret here, but it overflowing or being zero is is less likely than 1:2^255. */
	secp256k1_declassify(ctx, &koverflow, sizeof(koverflow));
	if (!koverflow) {
	ret = secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, NULL);
	/* The final signature is no longer a secret, nor is the fact that we were successful or not. */
	secp256k1_declassify(ctx, &ret, sizeof(ret));
	if (ret) {
	break;
	}
	}
	count++;
	}

Note that sigr is the nonce (R)'s x coordinate reduced modulo q as a scalar. The caller is only checking properties of the secret nonce not sigr (it doesn't even compute the point for R). Maybe this code was meant to check the secret nonce that's passed in instead?

There doesn't seem to be any problem with sigr overlfowing (the verification algorithm actually accounts for this possibility by adding the curve order to sigr if it doesn't work the first time!). sigr being 0 is a problem but the probability of this happening is so low I wouldn't bother accounting for it. I think this comment and VERIFY_CHECKS can be removed.

More generally there doesn't seem to be a problem with the secret nonce overflowing either but the while loop in the caller enforces that and that it's not 0.

[real-or-random]

Hm, this in indeed strange. I agree, this is not an issue. Both of these conditions are computationally unreachable, so this is not a problem and not at all exploitable. But we should still fix it.

This was introduced by @apoelstra in 25e3cfb. As I read this commit message, I think he really had the secret nonce k in mind instead r, which is the x-coord of the public nonce. A signature with a zero r is invalid by the spec, so we should return 0 to make the caller retry with a different nonce. Overflow is not an issue.

I think we should basically revert that commit, but then change the resulting code to fail late to be compliant with the new constant-time test (#710, #708).

@apoelstra Can you comment on this?

[apoelstra]

Yeah I have no idea what I was thinking here. These are cryptographically unreachable, and it doesn't make sense for the caller to have checked them. Possibly I ran into trouble with the exhaustive tests and put the comment in for that reason.

Agree with Tim's solution.