Signature padding improvements #3315

randombit · 2023-02-22T08:52:37Z

@reneme review is optional but I figure you would be interested. It is probably easier to review commit-by-commit. Also important note: Dilithium X.509 is still broken. The old tests used Botan::get_sig_paddings to get the padding parameters, but this returned an empty list for Dilithium. If I enable the tests for Dilithium, things fail.

#3319 captures some followup items.

Previously if RFC 6979 was enabled, we would test only that file. And if it was disabled, we would test only the CAVS file. Now test signature *generation* using whichever method is enabled, but also test verification of the signatures from the other method.

Remove support for message prefixes from the PK_Ops base classes, since it was only used for ECKCDSA.

Only RSA still supports this now that Rabin-Williams and NR have been removed; it's easier to move that logic to the RSA specific impl.

The behavior of EMSA1 and BigInt::from_bytes_with_max_bits were fighting with each other, which led to weird corner cases. Note the change to ecdsa_rfc6979.vec is a reversion of the change made in ffaa805 Fixes GH #2841 and GH #3313

This effectively sidelines the EMSA1/EMSA_Raw code for (EC)DSA, GOST, and company.

At least keeping parity with what is done on master currently.

codecov-commenter · 2023-02-22T21:39:18Z

Codecov Report

Base: 87.99% // Head: 88.02% // Increases project coverage by +0.03% 🎉

Coverage data is based on head (2c23729) compared to base (892988d).
Patch coverage: 76.70% of modified lines in pull request are covered.

❗ Current head 2c23729 differs from pull request most recent head d99eef1. Consider uploading reports for the commit d99eef1 to get more accurate results

📣 This organization is not using Codecov’s GitHub App Integration. We recommend you install it so Codecov can continue to function properly for your repositories. Learn more

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #3315      +/-   ##
==========================================
+ Coverage   87.99%   88.02%   +0.03%     
==========================================
  Files         608      608              
  Lines       68680    68758      +78     
  Branches     6845     6850       +5     
==========================================
+ Hits        60436    60526      +90     
+ Misses       5395     5368      -27     
- Partials     2849     2864      +15

Impacted Files	Coverage Δ
src/lib/asn1/oid_maps.cpp	`100.00% <ø> (ø)`
src/lib/pk_pad/emsa.cpp	`65.15% <ø> (-6.68%)`	⬇️
src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.cpp	`79.36% <0.00%> (+1.94%)`	⬆️
src/lib/pk_pad/emsa_pssr/pssr.cpp	`90.16% <0.00%> (+8.56%)`	⬆️
src/lib/pk_pad/iso9796/iso9796.cpp	`96.00% <ø> (+2.97%)`	⬆️
src/lib/pubkey/gost_3410/gost_3410.cpp	`79.27% <0.00%> (-0.55%)`	⬇️
src/lib/x509/x509_dn_ub.cpp	`100.00% <ø> (ø)`
src/lib/prov/pkcs11/p11_mechanism.cpp	`74.32% <30.00%> (-2.39%)`	⬇️
src/lib/pubkey/ecgdsa/ecgdsa.cpp	`81.63% <33.33%> (-1.06%)`	⬇️
src/lib/pubkey/dsa/dsa.cpp	`82.14% <37.50%> (-1.39%)`	⬇️
... and 35 more

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

☔ View full report at Codecov.
📢 Do you have feedback about the report comment? Let us know in this issue.

reneme

I skimmed over the changes and didn't find any obvious blunder. But frankly I'm lacking a good enough overview of the EMSA implementations to give a decent review.

Anything we can do to help with Dilithium, though?

reneme · 2023-02-23T09:02:01Z

src/lib/tls/tls_signature_scheme.cpp

+   switch(m_code)
+      {
+      case RSA_PKCS1_SHA1:
+         return AlgorithmIdentifier(OID::from_string("RSA/EMSA3(SHA-1)"), AlgorithmIdentifier::USE_NULL_PARAM);
+      case RSA_PKCS1_SHA256:
+         return AlgorithmIdentifier(OID::from_string("RSA/EMSA3(SHA-256)"), AlgorithmIdentifier::USE_NULL_PARAM);
+      case RSA_PKCS1_SHA384:
+         return AlgorithmIdentifier(OID::from_string("RSA/EMSA3(SHA-384)"), AlgorithmIdentifier::USE_NULL_PARAM);
+      case RSA_PKCS1_SHA512:
+         return AlgorithmIdentifier(OID::from_string("RSA/EMSA3(SHA-512)"), AlgorithmIdentifier::USE_NULL_PARAM);
+
+      case ECDSA_SHA1:
+         return AlgorithmIdentifier(OID::from_string("ECDSA/EMSA1(SHA-1)"), AlgorithmIdentifier::USE_EMPTY_PARAM);
+      case ECDSA_SHA256:
+         return AlgorithmIdentifier(OID::from_string("ECDSA/EMSA1(SHA-256)"), AlgorithmIdentifier::USE_EMPTY_PARAM);
+      case ECDSA_SHA384:
+         return AlgorithmIdentifier(OID::from_string("ECDSA/EMSA1(SHA-384)"), AlgorithmIdentifier::USE_EMPTY_PARAM);
+      case ECDSA_SHA512:
+         return AlgorithmIdentifier(OID::from_string("ECDSA/EMSA1(SHA-512)"), AlgorithmIdentifier::USE_EMPTY_PARAM);
+
+      case RSA_PSS_SHA256:
+         return AlgorithmIdentifier(OID::from_string("RSA/EMSA4"),
+                                    hex_decode("3039A00F300D06096086480165030402010500A11C301A06092A864886F70D010108300D06096086480165030402010500A203020120A303020101"));
+      case RSA_PSS_SHA384:
+         return AlgorithmIdentifier(OID::from_string("RSA/EMSA4"),
+                                    hex_decode("3039A00F300D06096086480165030402020500A11C301A06092A864886F70D010108300D06096086480165030402020500A203020130A303020101"));
+      case RSA_PSS_SHA512:
+         return AlgorithmIdentifier(OID::from_string("RSA/EMSA4"),
+                                    hex_decode("3039A00F300D06096086480165030402030500A11C301A06092A864886F70D010108300D06096086480165030402030500A203020140A303020101"));
+
+      default:
+         // Note that Ed25519 and Ed448 end up here
+         return AlgorithmIdentifier();
+      }


Same as last year: Sad that we need to scatter those mappings around the code. But then again: it feels like every protocol has their own particularities that make it hard to abstract this.

Anyway: Maybe at least add a comment to the hex_decode-ed EMSA4 parameters explaining what's inside the magic strings?
In the linked comment, I regenerated those for every invocation. Less efficient but easier to understand:

auto pss_params = [](const std::string hash_name) { const AlgorithmIdentifier hash_id(hash_name, AlgorithmIdentifier::USE_NULL_PARAM); const AlgorithmIdentifier mgf_id("MGF1", hash_id.BER_encode()); std::vector<uint8_t> parameters; DER_Encoder(parameters) .start_sequence() .start_context_specific(0).encode(hash_id).end_cons() .start_context_specific(1).encode(mgf_id).end_cons() .start_context_specific(2).encode(HashFunction::create(hash_name)->output_length()).end_cons() .start_context_specific(3).encode(size_t(1)).end_cons() // trailer field .end_cons(); return parameters; };

Still wondering whether DER_Encoder could do this as a constexpr generation. Purely academic question though.

In this instance though, the specific values we're encoding don't even matter. That is, TLS 1.3 could have just as easily mandated that the parameters be empty, or be the raw binary ASCII "I_PINKY_SWEAR_THIS_IS_PSS". In the context of TLS 1.3, no additional information is conveyed; there is a 1:1 mapping between the signature_algorithm enumeration, and the DER-encoded PssParams.

This could probably be cleaned up a bit by adding an explicit type for PssParams.

randombit · 2023-02-23T22:42:55Z

@reneme A lot of code in this area is more complicated than it needed to be, as a result of some historical blunders

For signature padding in general, and its interactions with signatures schemes, following the approach of IEEE 1363, which turned out to be kind of a dead end as standards go.
Trying to be overly general, leading to us supporting combinations that are definitely not a good idea (like supporting RSA with unpadded hashes - that's been deprecated for some time and I'm hoping to kill it for good for 3.0)
Supporting multiple signatures schemes with message recovery (namely Rabin-Williams and Nyberg-Rueppel, along with RSA), which made certain generalizations seem more beneficial.

This PR (and followup work in #3319) will hopefully address a lot of these

lieser · 2023-02-24T10:13:38Z

src/lib/pk_pad/raw_hash/raw_hash.cpp

+   if(m_output_length > 0 && m_bits.size() != m_output_length)
+      {
+      m_bits.resize(0);
+      throw Invalid_Argument("EMSA_Raw was configured to use a " +


I guess this is a copy and paste error and EMSA_Raw should probably be RawHashFunction.

Ah thank you, yes

randombit requested a review from reneme February 22, 2023 08:57

randombit added 22 commits February 22, 2023 08:36

ECKCDSA is a special case so treat it as one

c341188

Remove support for message prefixes from the PK_Ops base classes, since it was only used for ECKCDSA.

Remove support for message recovery from the pk_ops_impl classes

91c4150

Only RSA still supports this now that Rabin-Williams and NR have been removed; it's easier to move that logic to the RSA specific impl.

Add GH 3313 testcase

162c006

Bypass EMSA1's shifting mechanism for DSA/ECDSA/etc

f8a4331

The behavior of EMSA1 and BigInt::from_bytes_with_max_bits were fighting with each other, which led to weird corner cases. Note the change to ecdsa_rfc6979.vec is a reversion of the change made in ffaa805 Fixes GH #2841 and GH #3313

Remove strange unlock call

8fc6897

Rename {Signature,Verification}_with_EMSA to _with_Hash

6d3ceff

Ensure RFC6979 hash exists

24f0e41

Use just a hash function in the _with_Hash public key impls

544b8d7

This effectively sidelines the EMSA1/EMSA_Raw code for (EC)DSA, GOST, and company.

Move RawHashFunction to its own module

0983431

Deprecation note

a27f53e

Convert EKCDSA to use hash instead of EMSA1

ed73f1a

Remove bogus dependencies and includes

de60db4

Remove hash_for_emsa

dab6ffe

For TLS hardcode algorithm IDs instead of going through EMSA

6ee0298

Add AlgorithmIdentifier::empty

a5a8d83

Remove padding.h and associated machinery

0b146d0

Fix X.509 tests

7907aff

Remove unnecessary max_input_bits function

4c22d12

Fix memory leak in ECKCDSA

0209d6d

Avoid unnecessary EMSA1 annotations on keypair checks

23bd0cd

Re-enable partial Dilithium X509 testing

9eb96f3

At least keeping parity with what is done on master currently.

randombit force-pushed the jack/emsa-improvements branch from 5a42882 to 9eb96f3 Compare February 22, 2023 13:36

Remove obsolete/unecessary EMSA interfaces

2c23729

reneme reviewed Feb 23, 2023

View reviewed changes

Add comment on PSS parameters for TLS

d99eef1

randombit mentioned this pull request Feb 23, 2023

Signature/Padding Cleanups and Fixes #3319

Closed

5 tasks

randombit merged commit 2e51792 into master Feb 23, 2023

lieser reviewed Feb 24, 2023

View reviewed changes

randombit deleted the jack/emsa-improvements branch February 24, 2023 16:14

randombit mentioned this pull request Feb 25, 2023

Improve (internal) handling of Signature Schemes that don't require an EMSA #3227

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Signature padding improvements #3315

Signature padding improvements #3315

Uh oh!

randombit commented Feb 22, 2023 •

edited

Loading

Uh oh!

codecov-commenter commented Feb 22, 2023 •

edited

Loading

Uh oh!

reneme left a comment

Uh oh!

reneme Feb 23, 2023

Uh oh!

randombit Feb 23, 2023

Uh oh!

randombit commented Feb 23, 2023

Uh oh!

lieser Feb 24, 2023 •

edited

Loading

Uh oh!

randombit Feb 24, 2023

Uh oh!

Uh oh!

Signature padding improvements #3315

Signature padding improvements #3315

Uh oh!

Conversation

randombit commented Feb 22, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov-commenter commented Feb 22, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

reneme left a comment

Choose a reason for hiding this comment

Uh oh!

reneme Feb 23, 2023

Choose a reason for hiding this comment

Uh oh!

randombit Feb 23, 2023

Choose a reason for hiding this comment

Uh oh!

randombit commented Feb 23, 2023

Uh oh!

lieser Feb 24, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

randombit Feb 24, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

randombit commented Feb 22, 2023 •

edited

Loading

codecov-commenter commented Feb 22, 2023 •

edited

Loading

lieser Feb 24, 2023 •

edited

Loading