dnssec-verify tries all keys which results in poor performance

Summary

I noticed that for zones with many signatures (>= ~50'000) dnssec-verify can perform noticeably slower the more stand-by keys are included in the DNSKEY RR.

It looks like all ZSK keys in the DNSKEY RR are tried to verify the signatures until one is found which succeeds. It now depends on the DNSKEY RR data structure which key is tried first and whether the validation process is fast or slow. It would be good to first compare the RRSIG key-id with the DNSKEY key-id before attempting any cryptographic operations.

BIND version used

dnssec-verify 9.16.5

Steps to reproduce

# Create keys
# KSK
dnssec-keygen -a ECDSAP256SHA256 -f KSK foo.
Generating key pair.
Kfoo.+013+59071
# ZSK
dnssec-keygen -a ECDSAP256SHA256 foo.
Generating key pair.
Kfoo.+013+29053

# Add keys to foo.zone using an editor
$INCLUDE Kfoo.+013+59071.key
$INCLUDE Kfoo.+013+29053.key

# sign zone
dnssec-signzone -o foo. -P -t -x foo.zone Kfoo.+013+59071.private Kfoo.+013+29053.private 

# verify zone
time dnssec-verify -o foo. foo.zone.signed

What is the current bug behavior?

Depending on the key id and how many stand-by keys are present, the validation time of dnssec-verify slows down noticeably. Some examples below:

active ZSK: Kfoo.+013+39828, no stand-by ZSK

time dnssec-verify -o foo. foo.zone.signed 
Loading zone 'foo.' from file 'foo.zone.signed'
Verifying the zone using the following algorithms: ECDSAP256SHA256.
Zone fully signed:
Algorithm: ECDSAP256SHA256: KSKs: 1 active, 0 stand-by, 0 revoked
                            ZSKs: 1 active, 0 stand-by, 0 revoked

real	0m9.677s
user	0m9.645s
sys	0m0.026s

About ~9-10sec is the baseline

active ZSK: Kfoo.+013+59286 , stand-by ZSK: Kfoo.+013+39828

time dnssec-verify -o foo. foo.zone.signed 
Loading zone 'foo.' from file 'foo.zone.signed'
Verifying the zone using the following algorithms: ECDSAP256SHA256.
Zone fully signed:
Algorithm: ECDSAP256SHA256: KSKs: 1 active, 0 stand-by, 0 revoked
                            ZSKs: 1 active, 1 stand-by, 0 revoked

real	0m9.662s
user	0m9.630s
sys	0m0.026s

Result is correct and within the baseline.

active ZSK: Kfoo.+013+39828 , stand-by ZSK: Kfoo.+013+59286

time dnssec-verify -o foo. foo.zone.signed 
Loading zone 'foo.' from file 'foo.zone.signed'
Verifying the zone using the following algorithms: ECDSAP256SHA256.
Zone fully signed:
Algorithm: ECDSAP256SHA256: KSKs: 1 active, 0 stand-by, 0 revoked
                            ZSKs: 1 active, 1 stand-by, 0 revoked

real	0m14.210s
user	0m14.173s
sys	0m0.029s

Result is poor!

active ZSK: Kfoo.+013+39828 , stand-by ZSK: Kfoo.+013+59286, Kfoo.+013+51653

time dnssec-verify -o foo. foo.zone.signed 
Loading zone 'foo.' from file 'foo.zone.signed'
Verifying the zone using the following algorithms: ECDSAP256SHA256.
Zone fully signed:
Algorithm: ECDSAP256SHA256: KSKs: 1 active, 0 stand-by, 0 revoked
                            ZSKs: 1 active, 2 stand-by, 0 revoked

real	0m18.310s
user	0m18.274s
sys	0m0.029s

Result is poor!

What is the expected correct behavior?

No matter how many stand-by keys are present, the validation time is more or less constant.

Possible fixes

Check the key id before attempting to validate each signature with each key.