Multiplying by a co-factor in [batch]verification

[valerini]

I have a question around batch/single signature verification. As dalek is not multiplying by a co-factor in verifications (which in my opinion is ok for security, as well as multiplying by a co-factor is ok for security), this might create discrepancies when parties need to agree whether a batch of signatures is valid or not.

Imagine, a malicious user injects in a batch a signature sig = (S, R) with non-empty small-subgroup component in R (where the public key A is clean of small-subgroup components), where the small order subgroup component is of order 2, then batch verification with this signature will fail with probability 1/2 and succeed with probability 1/2. This will cause some problems for using batch-verification in consensus. I believe multiplying by 8 in verifications should resolve this issue, but would be very appreciative to see other opinions or to be corrected!

P.S. Thank you for the great work on this library!

[tarcieri]

I believe the ambiguities of “cofactorless” verification are inherent to batch verification. See this thread for some background:

https://moderncrypto.org/mail-archive/curves/2016/000836.html

The effects of this on a consensus protocol are that consensus participants need to perform a full verification of all signatures, but that batch verification is still useful for non-consensus nodes and light clients (since the consensus participants have verified the absence of these ambiguities in advance).

[burdges]

Appears @isislovecruft provided a batch_deterministic feature for deterministic delinearization, presumably to address this.

I think an argument works works better than a feature here, so maybe

fn verify_batch(
    messages: &[&[u8]],
    signatures: &[Signature],
    public_keys: &[PublicKey],
    deterministic: bool,
) -> Result<(), SignatureError> 

or if bools bother you then

fn verify_batch_rng<R: RngCore>(
    messages: &[&[u8]],
    signatures: &[Signature],
    public_keys: &[PublicKey],
    rng: R,
) -> Result<(), SignatureError> 
{
    ...
}

pub fn verify_batch(
    messages: &[&[u8]],
    signatures: &[Signature],
    public_keys: &[PublicKey],
) -> Result<(), SignatureError>
{
    verify_batch_rng(messages,signatures,public_keys,thread_rng())
}

pub fn verify_batch_deterministic(
    messages: &[&[u8]],
    signatures: &[Signature],
    public_keys: &[PublicKey],
) -> Result<(), SignatureError>
{
    verify_batch_rng(messages,signatures,public_keys,ZeroRng)
}

As an aside, rand_core alone provides system randomness, so I put a feature gate on rand being a dependency and using thread_rng like https://github.com/w3f/schnorrkel/blob/master/src/lib.rs#L226-L234 but not really sure if that's the best choice.

[kchalkias]

@burdges @tarcieri deterministic batch verification was proposed and implemented for many reasons:

• to ensure correctness even in clients with low or zero entropy. Otherwise, one can target such devices to falsely pass an invalid signature (i..e, imagine if all z values are zero or the same for some reason).
• In blockchain smart contracts (Libra, Ethereum, Corda) you might not have access to rng at all. Then you cannot take advantage of non-deterministic batch verification anyway, you need a deterministic one for one-shot multi-sig contracts.
• If for some reason a blockchain decides to support non-deterministic batch verification, one can exploit it using what @valerini mentioned and cause inconsistency to DLT states as well. In fact, it's the same as if you had an RNG available.
• Multiplying by the cofactor (or set the last 3 bits of z values to zero) will make batch verification compatible with NIST's standardization effort on single signature EdDSA, where (wisely IMO) they eventually chose to multiply by 8 and not allow optionality.

Note: there is a common misconception that NIST should have picked between multiplying and not multiplying by the cofactor and any choice would be acceptable. This is not correct, because if an application accepts both single and batch verification, multiplying by the cofactor is safer to ensure compatibility between those two (if a sig does not pass the batch verification, it shouldn't pass the iterative single verification too and vice versa).

[isislovecruft]

Note that we currently multiply by the cofactor in verify_strict() but we do not yet have an equivalent verify_batch_strict() function yet.

[rozbb]

Discussion about verify_batch_strict seems dead. Original topic, which was cofactor multiplication for batch verification, is a dupe of https://github.com/dalek-cryptography/ed25519-dalek/issues/152 . Closing