Add DER parsing for rsaPss signature algorithms.

net/cert/internal/signature_algorithm.cc

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/cert/internal/signature_algorithm.h"
 
 #include <stdint.h>
 
+#include "base/numerics/safe_math.h"
 #include "net/der/input.h"
+#include "net/der/parse_values.h"
 #include "net/der/parser.h"
 
 namespace net {
 
 namespace {
 
 // From RFC 3279 section 2.2.1:
 //  sha-1WithRSAEncryption OBJECT IDENTIFIER  ::=  {
 //              iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1)
 //                          pkcs-1(1) 5  }
@@ skipping 55 matching lines @@
 // In dotted notation: 1.2.840.10045.4.3.4
 const uint8_t kOidEcdsaWithSha512[] =
     {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x04, 0x03, 0x04};
 
 // From RFC 4055 section 3.1:
 //   id-RSASSA-PSS  OBJECT IDENTIFIER  ::=  { pkcs-1 10 }
 // In dotted notation: 1.2.840.113549.1.1.10
 const uint8_t kOidRsaSsaPss[] =
     {0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x0a};
 
+// From RFC 4055:
+//   id-sha1  OBJECT IDENTIFIER  ::=  { iso(1)
+//                        identified-organization(3) oiw(14)
+//                        secsig(3) algorithms(2) 26 }
+// In dotted notation: 1.3.14.3.2.26
+const uint8_t kOidSha1[] = {0x2B, 0x0E, 0x03, 0x02, 0x1A};
+
+// From RFC 4055:
+//   id-sha256  OBJECT IDENTIFIER  ::=  { joint-iso-itu-t(2)
+//                        country(16) us(840) organization(1) gov(101)
+//                        csor(3) nistalgorithm(4) hashalgs(2) 1 }
+// In dotted notation: 2.16.840.1.101.3.4.2.1
+const uint8_t kOidSha256[] =
+    {0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01};
+
+// From RFC 4055:
+//   id-sha384  OBJECT IDENTIFIER  ::=  { joint-iso-itu-t(2)
+//                        country(16) us(840) organization(1) gov(101)
+//                        csor(3) nistalgorithm(4) hashalgs(2) 2 }
+// In dotted notation: 2.16.840.1.101.3.4.2.2
+const uint8_t kOidSha384[] =
+    {0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02};
+
+// From RFC 4055:
+//   id-sha512  OBJECT IDENTIFIER  ::=  { joint-iso-itu-t(2)
+//                        country(16) us(840) organization(1) gov(101)
+//                        csor(3) nistalgorithm(4) hashalgs(2) 3 }
+// In dotted notation: 2.16.840.1.101.3.4.2.3
+const uint8_t kOidSha512[] =
+    {0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03};
+
+// From RFC 4055:
+//   id-mgf1  OBJECT IDENTIFIER  ::=  { pkcs-1 8 }
+// In dotted notation: 1.2.840.113549.1.1.8
+const uint8_t kOidMgf1[] =
+    {0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x08};
+
 // RFC 5280 section 4.1.1.2 defines signatureAlgorithm as:
 //
 //  AlgorithmIdentifier  ::=  SEQUENCE  {
 //       algorithm               OBJECT IDENTIFIER,
 //       parameters              ANY DEFINED BY algorithm OPTIONAL  }
 WARN_UNUSED_RESULT bool ParseAlgorithmIdentifier(const der::Input& input,
                                                  der::Input* algorithm,
                                                  der::Input* parameters) {
   der::Parser parser(input);
 
@@ skipping 91 matching lines @@
 WARN_UNUSED_RESULT bool ParseEcdsa(DigestAlgorithm digest,
                                    const der::Input& params,
                                    SignatureAlgorithm* out) {
   if (!IsNullOrEmpty(params))
     return false;
 
   out->AssignEcdsa(digest);
   return true;
 }
 
+// Parses an AlgorithmIdentifier representing an RFC 4055 "HashAlgorithm".
+// Examples of HashAlgorithms are:
+//
+//      sha1Identifier  AlgorithmIdentifier  ::=  { id-sha1, NULL }
+//      sha224Identifier  AlgorithmIdentifier  ::=  { id-sha224, NULL }
+//      sha256Identifier  AlgorithmIdentifier  ::=  { id-sha256, NULL }
+//      sha384Identifier  AlgorithmIdentifier  ::=  { id-sha384, NULL }
+//      sha512Identifier  AlgorithmIdentifier  ::=  { id-sha512, NULL }
+//
+// Note that the parameters needn't be NULL as in the examples above. RFC 4055
+// says that:
+//
+//    All implementations MUST accept both NULL and absent parameters as
+//    legal and equivalent encodings.
+WARN_UNUSED_RESULT bool ParseHashAlgorithm(const der::Input input,
+                                           DigestAlgorithm* out) {
+  der::Input oid;
+  der::Input params;
+  if (!ParseAlgorithmIdentifier(input, &oid, &params))
+    return false;
+
+  DigestAlgorithm hash;
+
+  if (oid.Equals(der::Input(kOidSha1))) {
+    hash = DigestAlgorithm::Sha1;
+  } else if (oid.Equals(der::Input(kOidSha256))) {
+    hash = DigestAlgorithm::Sha256;
+  } else if (oid.Equals(der::Input(kOidSha384))) {
+    hash = DigestAlgorithm::Sha384;
+  } else if (oid.Equals(der::Input(kOidSha512))) {
+    hash = DigestAlgorithm::Sha512;
+  } else {
+    // Unsupported digest algorithm.
+    return false;
+  }
+
+  if (!IsNullOrEmpty(params))
+    return false;
+
+  *out = hash;
+  return true;
+}
+
+// Parses a MaskGenAlgorithm as defined by RFC 4055. It is expected that the

[Ryan Sleevi, 2015/07/06 15:03:18]

Worth mentioning (somewhere) that MaskGenAlgorithm ::= AlgorithmIdentifier

[eroman, 2015/07/07 01:24:22]

Done.

+// mask gen is for MGF1, as this is the only function allowed for in RFC 4055.

[Ryan Sleevi, 2015/07/06 15:03:17]

Comment wise, this reads weird. RFC 4055 totally allows this to be extensible /
updated by future RFCs, so it 'allows' for more, and defines how to do that
allowance.

Perhaps
// It is expected that the algorithm is MGF1, as this is the only function
defined in RFC 4055.

[eroman, 2015/07/07 01:24:22]

How about this:

// Parses a MaskGenAlgorithm as defined by RFC 4055:
//
//     MaskGenAlgorithm  ::=  AlgorithmIdentifier
//
// This function currently only supports MGF1, as that is the only function
// defined in RFC 4055.

+//
+// RFC 4055 section 2.2:
+//
+//     One mask generation function is used with the RSASSA-PSS signature
+//     algorithm and the RSAES-OAEP key transport algorithm: MGF1 [P1v2.1].
+//     No other mask generation functions are supported by this
+//     specification.
+//
+//     MGF1 is identified by the following object identifier:
+//
+//        id-mgf1  OBJECT IDENTIFIER  ::=  { pkcs-1 8 }
+//
+//     The parameters field associated with id-mgf1 MUST have a
+//     hashAlgorithm value which identifies the hash function being used
+//     with MGF1.  This value MUST be sha1Identifier, sha224Identifier,
+//     sha256Identifier, sha384Identifier, or sha512Identifier, as specified
+//     in Section 2.1.  Implementations MUST support the default value,
+//     sha1Identifier, and MAY support the other four values.
+WARN_UNUSED_RESULT bool ParseMaskGenAlgorithm(const der::Input input,
+                                              DigestAlgorithm* mgf1_hash) {
+  der::Input oid;
+  der::Input params;
+  if (!ParseAlgorithmIdentifier(input, &oid, &params))
+    return false;
+
+  // MGF1 is the only supported mask generation algorithm.
+  if (!oid.Equals(der::Input(kOidMgf1)))
+    return false;
+
+  return ParseHashAlgorithm(params, mgf1_hash);
+}
+
+// Consumes an optional integer from |parser| using the indicated
+// (context-specific) tag number.

[Ryan Sleevi, 2015/07/06 15:03:18]

// Consumes an optional, explicitly-tagged INTEGER from |parser|, using the
indicated
// context-specific class number. Values greater than 32-bits will be rejected.

[eroman, 2015/07/07 01:24:23]

Done.

+//
+// Returns true on success and sets |*present| to true if the field was present.
+WARN_UNUSED_RESULT bool ReadOptionalContextSpecificUint32(der::Parser* parser,
+                                                          uint8_t tag_base,

[Ryan Sleevi, 2015/07/06 15:03:17]

naming nit: tag_base originally suggested to me some base-2/base-10/base-16
thing, until I realized it's meant to be the _class number_ (in ASN.1 terms)

[eroman, 2015/07/07 01:24:22]

Done.

+                                                          uint32_t* out,
+                                                          bool* present) {
+  der::Input value;
+  bool has_value;
+
+  // Read the context specific value.
+  if (!parser->ReadOptionalTag(der::ContextSpecificConstructed(tag_base),
+                               &value, &has_value)) {
+    return false;
+  }
+
+  if (has_value) {
+    // Parse the integer contained in it.
+    der::Parser number_parser(value);
+    uint64_t uint64_value;
+
+    if (!number_parser.ReadUint64(&uint64_value))
+      return false;
+    if (number_parser.HasMore())
+      return false;
+
+    // Cast the number to a uint32_t
+    base::CheckedNumeric<uint32_t> casted(uint64_value);
+    if (!casted.IsValid())
+      return false;
+    *out = casted.ValueOrDie();
+  }
+
+  *present = has_value;
+  return true;
+}
+
 // From RFC 4055:
 //    RSASSA-PSS-params  ::=  SEQUENCE  {
 //         hashAlgorithm     [0] HashAlgorithm DEFAULT
 //                                  sha1Identifier,
 //         maskGenAlgorithm  [1] MaskGenAlgorithm DEFAULT
 //                                  mgf1SHA1Identifier,
 //         saltLength        [2] INTEGER DEFAULT 20,
 //         trailerField      [3] INTEGER DEFAULT 1  }
 //
 //      HashAlgorithm  ::=  AlgorithmIdentifier
 //
 //      MaskGenAlgorithm  ::=  AlgorithmIdentifier
 WARN_UNUSED_RESULT bool ParseRsaPss(const der::Input& params,
                                     SignatureAlgorithm* out) {
-  // TODO(eroman): Implement.
-  return false;
+  // RFC 4055 says that the RSASSA-PSS-params must be present in signature
+  // algorithms. (However because each field is optional, the sequence could be
+  // empty when using all the defaults).
+  //
+  // Section 3.1:
+  //
+  //    When RSASSA-PSS is used in an AlgorithmIdentifier, the parameters
+  //    MUST employ the RSASSA-PSS-params syntax.  The parameters may be
+  //    either absent or present when used as subject public key information.
+  //    The parameters MUST be present when used in the algorithm identifier
+  //    associated with a signature value.
+  der::Parser parser(params);
+  der::Parser params_parser;
+  if (!parser.ReadSequence(&params_parser))
+    return false;
+
+  // There shouldn't be anything after the sequence.
+  if (parser.HasMore())
+    return false;
+
+  // Initialize parameters to their default values.
+  DigestAlgorithm hash = DigestAlgorithm::Sha1;
+  DigestAlgorithm mgf1_hash = DigestAlgorithm::Sha1;
+  uint32_t salt_length = 20;

[Ryan Sleevi, 2015/07/06 15:03:17]

pedantry: 20u

[eroman, 2015/07/07 01:24:23]

Done.

+  uint32_t trailer_field = 1;

[Ryan Sleevi, 2015/07/06 15:03:17]

pedantry: 1u

[eroman, 2015/07/07 01:24:23]

Done.

+
+  bool has_field;
+  der::Input field;
+
+  // Parse hashAlgorithm [0]
+  if (!params_parser.ReadOptionalTag(der::ContextSpecificConstructed(0), &field,

[Ryan Sleevi, 2015/07/06 15:03:17]

When Nick and I originally had discussed this, there was a question about
whether or not explicit class-tagging would be needed. Turns out, it is.

I'm wondering if this is the easiest API for it in understanding what was going
on. Thoughts?

[eroman, 2015/07/07 01:24:23]

My API suggestion depends on understanding a few things better.

 * tag.h contains method ContextSpecificPrimitive(). I haven't these in the
specs I have read so far, are you aware of when it would be used? Is this for
IMPLICIT tagging of a context-specific primitive?

  * Would we want to accept unrecognized stuff inside the context specific
contructed tag, or require it to contain at most 1 TLV. 

+                                     &has_field)) {
+    return false;
+  }
+  if (has_field) {
+    if (!ParseHashAlgorithm(field, &hash))

[Ryan Sleevi, 2015/07/06 15:03:18]

simplify

if (has_field && !ParseHashAlgorithm(field, &hash))
  return false;

[eroman, 2015/07/07 01:24:22]

Done.

+      return false;
+  }
+
+  // Parse maskGenAlgorithm [1]
+  if (!params_parser.ReadOptionalTag(der::ContextSpecificConstructed(1), &field,
+                                     &has_field)) {
+    return false;
+  }
+  if (has_field) {
+    if (!ParseMaskGenAlgorithm(field, &mgf1_hash))
+      return false;

[Ryan Sleevi, 2015/07/06 15:03:17]

Simplify

if (has_field && !ParseMaskGenAlgorithm(field, &mgf1_hash))
  return false;

[eroman, 2015/07/07 01:24:22]

Done.

+  }
+
+  // Parse saltLength [2]
+  if (!ReadOptionalContextSpecificUint32(&params_parser, 2, &salt_length,
+                                         &has_field)) {
+    return false;
+  }
+
+  // Parse trailerField [3]
+  if (!ReadOptionalContextSpecificUint32(&params_parser, 3, &trailer_field,
+                                         &has_field)) {
+    return false;
+  }
+
+  // The trailer field MUST be 1 per RFC 4055.
+  if (trailer_field != 1)
+    return false;
+
+  // There must not be any unconsumed data left.
+  if (params_parser.HasMore())

[Ryan Sleevi, 2015/07/06 15:03:17]

BUG: This is unnecessarily strict, since it's totally valid for this field to be
extended in the future.

[eroman, 2015/07/07 01:24:23]

Thanks.

I have some concerns with leaving unconsumed data that I would like understand
better before proceeding with that change.

Are the rules for unconsumed data enumerated somewhere I can review?
The closest I could find in RFC 5280 was the "critical" boolean specific to
extensions and not applicable here. And I didn't see anything obvious in RFC
4055. And I am searching through X.690 for answers.

(1) If new parameters are added which actually change the signature algorithm,
wouldn't it be more prudent to simply reject? In the best case scenario, the
subsequent signature verification will fail because we didn't use the right
algorithm parameters. In the worst case, I am concerned whether this opens an
opportunity to exploit a problem that the new (specified) parameter was meant to
solve, but Chrome discard.

The only type of new parameter I could imagine (one which doesn't actually
change the verification result) would be something to tweak the verification
performance.

If signature verification is doomed to fail anyway, I would expect it is
preferable to fail fast, and give an error message that calls out parameter
parsing. Rather than do the signature verification, and then fail it. How have
algorithm parameters historically been extended? Seems like in the model where
parameters are disregarded it would be more prudent to add new OIDs instead.

(2) Would we want to accept malformed DER when skipping unrecognized data?

The simplest implementation would be to simply remove the HasMore() check above.
A possible downside to this approach is we wouldn't do any validation of the
subsequence data. Maybe this is the goal. However it does mean the subsequent
data could be malformed DER (for instance bad tag lengths), or arbitrary bytes
for that matter.

(3) Should I change anything with regard to the interpretation of EXPLICIT tags?
saltLength, trailerField, and the like are also containers which could contain
more than one tag. I currently check for HasMore(), however if we are allowing
it at the end of the parameters sequence, should we similarly allow it within
those constructed tags?

I will see if I can find anything in the ASN.1 / DER spec to clarify things

[Ryan Sleevi, 2015/07/07 15:27:23]

This is all covered by the ASN.1 schema, which is that the schema is necessarily
extensible unless explicitly non-extensible.

For example, SEQUENCE OF (x...y) SOMETHING must always be a SOMETHING and never
have additional data. However, a 
SEQUENCE {
  foo foo;
  bar bar;
};

Can change over time. And if you run into situations where there are
optionals/ambiguity, you can introduce tagging (explicit or implicit)

Conceptually, if it helps, think of this a similar to protobuf schemas, all of
which are by definition extensible. Every field is implicitly required (think
https://developers.google.com/protocol-buffers/docs/proto#specifying-field-types
), unless explicitly optional, but they're all extensible.

Checking HasMore() and rejecting is a bit like prohibiting message types from
ever being extended (
https://developers.google.com/protocol-buffers/docs/proto#updating )
I understand these concerns, but this is valid DER. While unlikely to be done
(for just that reason), our parsing of DER should not be inconsistently
incorrect, which is what checking that there are no additional bytes would be.
Yes, that's correct. ASN.1's T/L/Vs generally provide sufficient context to know
whether or not you can continue to drill down into a field (c.f. constructed
types), although that's still not a perfect solution (somewhat might smuggle
data in an OCTET STRING or BITSTRING, which wouldn't necessarily be drillable)

In ASN.1 schema terms, we're talking about the '...' and EXTENSIBILITY IMPLIED.
You can use RFC 5912 for the ASN.1 2008 definition of tbsCertificate, whose
schema definition (truncated) includes

     [[3:               -- If present, version MUST be v3 --
      extensions      [3]  Extensions{{CertExtensions}} OPTIONAL
      ]], ... }

It's the last ... that explicitly states more fields may be added in the future.
You can also see the discussion on
https://tools.ietf.org/html/rfc6025#section-2.4

That said, having looked in 5912, AlgorithmIdentifier is in a module that
doesn't inherit EXTENSIBILITY IMPLIED and doesn't include the '...', so your
HasMore is likely fine here.
No, an explicitly tagged class includes the original tagged type.
You're wanting 31.2 of X.680 for implicit tags, 50.3 of X.680 for type
definitions of collections (ish), I.4 for constraint math on 50.3, and perhaps
more directly related to your general concerns, Section 7.

[eroman, 2015/07/08 00:22:39]

Thanks for the information, I will try to absorb that.

I am not sure I understand your concluding remark of "so your HasMore is likely
fine here."
Which "HasMore" is that in relation to?

If we don't consume all the data I should also remove
SignatureAlgorithm::Equals(), since it might be dangerous/wrong to conclude that
two algorithm identifiers with different unconsumed data are the same. As far as
just doing a byte-for-byte equality test, I read that there are existing certs
with mismatched parameters encoding (NULL vs missing) for the signature
algorithm, so a pure equality test would fail those.

+    return false;
+
+  out->AssignRsaPss(hash, mgf1_hash, salt_length);
+  return true;
 }
 
 }  // namespace
 
 RsaPssParameters::RsaPssParameters(DigestAlgorithm mgf1_hash,
                                    uint32_t salt_length)
     : mgf1_hash_(mgf1_hash), salt_length_(salt_length) {
 }
 
 bool RsaPssParameters::Equals(const SignatureAlgorithmParameters* other) const {
@@ skipping 106 matching lines @@
   return nullptr;
 }
 
 void SignatureAlgorithm::AssignInvalid() {
   algorithm_ = static_cast<SignatureAlgorithmId>(-1);
   digest_ = static_cast<DigestAlgorithm>(-1);
   params_.reset();
 }
 
 }  // namespace net