Is there a way I can enforce verification of an EC signature at design-time rather than implementation-time?

Question

Let's assume I'm designing a cryptographic interaction that relies on digital signatures to maintain security. It is trivial for me to write in my documentation "Alice then verifies the signature provided by Bob" - but when it comes to implementation time e.g. writing code to automate this cryptographic interaction, the engineer that writes this code could accidentally or intentionally not verify the digital signature.

This would hopefully be caught during review, but could also slip through the cracks. Ideally I'd like to have something baked into the core design of the interaction that requires the signature to be verified correctly or subsequent steps would fail. I'm thinking of something akin to:

• XORing hashes of handshaking payloads with shared secrets to ensure both parties experienced the same handshake.
• Adding message length as authenticated data in an AEAD to guarantee both parties see the message length the same.

Is there anything in a similar vein to ensure the signature is verified?

Answer 1

One option is using a signature scheme with message-recovery. That produces a cryptogram containing both the (short) message and the signature. Getting the message from that requires applying the public key, and making at least a large fraction of the work towards verifying the signature. It's darn difficult to accidentally miss that verification (for total message recovery, that is the whole message embedded in the cryptogram; and for partial message recovery, if the fraction of the message included in the cryptogram is functionally indispensable for operation).

For RSA and Rabin cryptosystems (assuming hardness of factorization), standard schemes with message recovery are in ISO/IEC 9796-2 (paywalled with preview). Scheme 1 is very much in use in bank Smart Cards (see EMVCo's Integrated Circuit Card Specifications for Payment Systems, Book 2 v4.4, A2.1; requires click-thru approval of license terms) and also possibly ICAO passports, despite a (mostly theoretical) weakness. Schemes 2 and 3 do not have this issue, use principles similar to RSASSA-PSS, and are increasingly used in fare collection. Advantages of these scheme is fast verification, and moderate signing overhead (e.g. 34 bytes for messages at least 222 bytes, with 2048-bit keys).

Message recovery also exists for DLP-based schemes, including using Elliptic Curves groups. That's standardized in ISO/IEC 9796-3 (paywalled with preview). Elliptic curve schemes include ECNR (Nyberg-Rueppel), ECMR (Miyaji), ECAO (Abe-Okamoto), ECPV (Pintsov-Vanstone), ECKNR (Nyberg-Rueppel variant of KCDSA). But I know no field use, except perhaps for ECPV also known as ECPVS of ANSI X9.92-1-2009 (R2017) (paywalled with preview).

Answer 2

First of all, note that the idea I am presenting can be complex to implement. You will need to look at the signature verification routine for your selected signature schemes and modify them in a manner that doesn't break security.

Here's a generic idea for signature schemes. If you have a deterministic set of values that has to be computed to verify the signature, you can use those values as "proof" that at least part of the signature verification routine was executed. You can then mix this with the current secret using a KDF. Doing so basically ensures that every time a signature is verified in the handshake the shared secret changes unpredictably, breaking any implementation that does not compute these witness[1] values. Message recovery may be useful as well for this purpose.

Next, you can embed into the signed data for your signature an ephemeral signature public key, a chunk of random data, and two signatures. Both signatures are supposed to be signed using the corresponding ephemeral signature private key. However, one of them is valid and the other one is invalid[2]. The two ephemeral signatures are shuffled randomly each time so the implementing programmer can not assume which one is valid or invalid. You then also include as part of the full set of witness values the validity of both signatures(in order) and their corresponding witness values.

Now you have done two things: 1- Fuzzed the signature verification routine(it should accept valid signatures and reject invalid ones). This prevents someone from incorrectly implementing the verification routine and not noticing. 2- Require for each signature verification the storage of intermediate outputs in the algorithm. This means that they actually have to implement at least part of the verification routine for all the signatures involved. Because all three signatures(2 ephemeral fuzzing signatures and the security critical one) all need to have their witness values generated to correctly update the shared secret, it becomes difficult for the programmer to avoid implementing the verification routine. Once they create the verification routine that also outputs the witness values, it becomes the path of least effort to just use it to verify the security critical signature.

There is only one last problem and that's ensuring that the implementation actually acts on the signature verification result for the security critical signature. Unfortunately, there's not much we can do for a programmer that decides to not abort upon receiving a bad signature. We have at least however forced them to implement a correct verification routine and apply it to the security critical signature.

[1] Witness because they act as proof that some part of the complete signature verification routine was computed.

[2] Look at Project Wycheproof for ideas on how to generate the invalid signature. The goal is to forcibly fuzz the verification routine for each signature sent in the protocol.