DER SET ordering: enforce it in the walk, not in a check afterwards
A SET in ASN.1 is unordered by definition: the arrangement of its components carries no meaning. DER still fixes exactly one arrangement on the wire, ascending by encoding, compared as octet strings. A parser that accepts any other arrangement has made many byte strings decode to one value, and only one of those byte strings was ever signed. That is the whole problem in one sentence. The rest of this is about where the fix belongs: in the walk over a SET's children, or in a validation pass that runs once they are all in hand.
I maintain a DER reader called derstrict (https://github.com/polycratia/derstrict) whose only job is to refuse encodings DER already forbids. SET ordering is one of the rules it carries, and it is the rule where the placement decision is most visible, because it is the only one that needs to remember something about the element before.
Why order is an encoding property, not a cosmetic one
Signature verification is over bytes. It pins exactly one byte string and says nothing about any other. Everything else your parser is willing to accept as "the same value" is a byte string nobody signed.
That gap only hurts once some part of the system treats the decoded value as the authority: you compare two subject names, you cache a pin keyed by a decoded name, you re-serialize a name to hand to a downstream service, you decide a name constraint is satisfied. A lenient reader has handed you a value with more than one preimage. The signature covered one preimage, and you are now reasoning about the others on its credit.
The second failure is more mundane: disagreement. One implementation accepts a permuted SET and another refuses it, so the same signed document is valid over here and invalid over there. In X.509 the SETs a reader actually meets are mostly inside names (a relative distinguished name is a set of attribute-and-value pairs), which is to say they sit precisely in the fields that two parties later compare with each other. This is the same inversion of Postel's law that applies to every other spelling DER forbids: tolerance of a second encoding buys you nothing except a second, equally well-signed meaning.
So order has to be refused, and the question is where.
What a check afterwards actually costs
To verify ordering after the walk, you need every child's complete encoding at the same time. Three things follow from that, and none of them are good.
First, you hold them. The buffer is sized by attacker-controlled input, in the part of the system that runs before anything has been authenticated. A streaming reader that used to be a cursor over borrowed bytes has acquired an allocation whose size the document chooses.
Second, and this is the one that decides it for me, you now have every child's encoding and a comparator over encodings sitting in one place. The distance from there to "we will just sort them and move on" is one line of code, and that line gets written eventually, probably by someone holding a certificate from a real issuer that fails in production on a Friday. Sorting is repair. A repaired document is not the document the signature covered, so the thing you checked and the thing you verified have come apart. Refusing is the only treatment of a malformed encoding that keeps those two the same document.
Third, the diagnosis degrades. A post-pass tells you that a SET was unsorted. The walk tells you which read refused, in document order, and the first refusal is the one that describes the document: everything after it is a consequence. derstrict keeps that property everywhere, the first failure wins and describe() names the rule that broke. A validation pass bolted onto the end reports its verdict out of sequence with every other verdict in the run.
There is a fourth cost that is easy to miss. A post-pass over a parsed tree only sees the nodes your schema walk chose to visit. Ordering is not a schema rule: it holds for every DER document, including the parts of a certificate your schema skips, and including bytes a fuzzer invented that match no schema at all. Push a universal rule into a schema-driven pass and you have made it conditional on the schema. The corpus walk in derstrict reads documents with no schema at all for exactly this reason: strip the schema and what is left is the encoding rules, which is what lets the same walk read a corpus vector and a fuzzer's output.
Where the rule lives
In derstrict the ordering obligation belongs to the reader, acquired at the moment it descends:
/// Descend into a constructed element. A SET's children carry DER's
/// ordering rule with them, so a descent written by hand is no less strict
/// than one that went through `set()`.
[[nodiscard]] parser into(const element& e) const noexcept {
return parser{e.content, e.length, e.is(tag::set)};
}
/// Read a SET and hand back a reader over its children, which have to
/// arrive in the order DER sorts them into.
[[nodiscard]] std::optional<parser> set() noexcept {
const auto e = expect(tag::set);
if (!e) return std::nullopt;
return into(*e);
}And the enforcement is the last thing next() does, after the length is settled and the content is taken, before the element goes back to the caller:
out.content = content;
out.length = *length;
if (sorted_ && !in_order(out)) return std::nullopt;
return out;That placement is worth a moment. The rule does not sit in set(). It sits in into(), which set() happens to call. The difference shows up the first time a caller needs the element itself rather than a reader over it, which in certificate work is immediately: verifying a signature means hashing the exact bytes of the signed structure, so real code calls expect(), keeps the element, and descends by hand. Strictness that lives only in the convenience helper is strictness you lose the moment the convenience stops fitting.
One element of memory
The comparison is against the previous sibling, not against the first one and not against a collected list. That is all the state the rule needs, and it is what makes enforcement during the walk cheap enough that I see no argument for the alternative:
// Each element is measured against the one before it, not against the first, so
// a set that starts in order does not earn the rest of the walk.
void ordering_is_measured_against_the_element_before() {
// SET { INTEGER 1, INTEGER 3, INTEGER 2 }
const auto data = bytes({0x31, 0x09, 0x02, 0x01, 0x01, 0x02, 0x01, 0x03, 0x02, 0x01, 0x02});
auto p = over(data);
const auto opened = p.set();
CHECK(opened.has_value());
if (!opened) return;
auto children = *opened;
CHECK(children.unsigned_integer() == 1u);
CHECK(children.unsigned_integer() == 3u);
CHECK(!children.unsigned_integer().has_value());
CHECK(children.failure() == error::unsorted_set);
}The refusal lands on the read that met the out-of-order child, and the two well-formed reads before it have already succeeded. A caller that stops at the first std::nullopt (the shape every read in this library pushes you into) stops at the right byte, and the error names the rule:
void a_set_out_of_order_is_refused() {
const auto data = bytes({0x31, 0x06, 0x02, 0x01, 0x02, 0x02, 0x01, 0x01});
auto p = over(data);
const auto opened = p.set();
auto children = *opened;
CHECK(children.unsigned_integer() == 2u);
CHECK(!children.unsigned_integer().has_value());
CHECK(children.failure() == error::unsorted_set);
}Note what is being compared: encodings, as octet strings. Not decoded values, not magnitudes. The tag byte is the first octet of the encoding, so it takes part in the comparison before any content does. Comparing decoded values would require knowing what the children are, which drags the schema back in and makes the rule conditional again. Comparing bytes needs nothing but bytes.
The rule the walk makes possible
Enforcing order during the walk has a sibling benefit that justifies the design on its own. The same per-level walk is what makes leftover bytes detectable at every level, not only at the end of the document:
// A whole element the caller did not ask for is trailing data all the same.
void a_child_the_caller_did_not_read_is_trailing_data() {
// SEQUENCE { INTEGER 1, INTEGER 2 } read as if it held one integer.
const auto data = bytes({0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0x02});
auto p = over(data);
auto children = *p.sequence();
CHECK(children.unsigned_integer() == 1u);
CHECK(!children.at_end());
CHECK(children.failure() == error::trailing_data);
}Both rules, ordering and nothing-left-over, are statements about a single level of a document, made as the level is traversed. Neither can be stated at all about a tree that has already been flattened into objects.
What I would do differently
The ordering obligation is carried as a boolean derived from the tag, and that is the part I would revisit. A tag tells you the element is a SET, it does not tell you whether the schema meant SET or SET OF, and those two do not sort by quite the same justification even though both end up ordered. Deriving the obligation from the tag keeps the reader schema-free, which is the property I wanted most, but it does mean the strictest possible reading of the rule is not available without letting a schema speak. I took that trade and I would take it again, and I would not pretend it is free.
The other thing I would keep deliberately: a child reader is a value, not a handle into shared mutable state. auto children = *opened; copies a cursor with its own ordering state, which is why ordering can be per-level without a stack of saved comparison state, and why abandoning a descent cannot leak order state into a sibling. That was not foresight so much as a consequence of keeping the reader a plain object over borrowed bytes, but it is the detail that made the per-level rules cheap.
I have been shipping payment and crypto systems since 2018, and the recurring shape of this bug is not cryptographic at all. It is a signer hashing bytes while a verifier reasons about values, with a serializer in between that nobody treats as part of the protocol. Signed request bodies on payment rails have the same disease, usually resolved by a field-order convention that was never written down and gets discovered during integration. DER has the advantage of having written it down. A reader's only job is to not be more generous than the document it was handed.