6 ms·

Systematic Parsing of X.509: Eradicating Security Issues with a Parse Tree

146 points by snaky 8y ago

lsh 8y ago
see also langsec.org non-Turing complete languages, formal grammars and context-free parsing are fascinating and the current state of tooling is really sophisticated but sparse. So much boilerplate code and adhoc parsing exists in my code and I never really appreciated how much until I asked myself if I really needed a Turing complete language to tell me if an input really is an integer or a string of 4 chars, etc. I'm terrified what would happen if a fuzzer ever went to town on my python code.
- zvrba 8y ago
  The last couple of times I had to parse/generate string according to something that can be described with a grammar, I resisted the temptation to implement an ad-hoc parser just because it was "simple". So I took the time and started to use Boost Qi/Karma (C++) instead. Just BECAUSE the formats are simple, they are the perfect opportunity to start learning more powerful tools.
k-ian 8y ago
[comment about x509 being bad]
- Dylan16807 8y ago
  Sucks that you're being downvoted since at the time you posted "X.509" wasn't in the title and it was reasonable context on why "20% of HTTPS server cert are incorrect, half considered valid by libs"
jcranmer 8y ago
There's one thing that gives me pause here: The single most common error is listed as DNS/URI/email format violations. There is absolutely no discussion as to what kinds of violations these break into, nor is there even a discussion as to what the paper thinks the correct formats ought to be. This is unfortunate because the format of these parameters is one thing where specifications often have a view of the world which is completely incongruent with reality. As a simple case, you will sometimes come across documentation that thinks that DNS names cannot start with a digit, which does not match reality at all.
- tialaramex 8y ago
  If they don't discuss it, it seems reasonable to assume they mean as specified. PKIX and the Baseline Requirements are pretty clear on how this works, despite ignorance from the CAs and end users. Note in particular that SAN dnsNames in PKIX are host names, and not all DNS names are acceptable names for hosts per the specifications. In my experience "I wasn't sure of the format definition" is code for "I knew this was strictly forbidden but it's more convenient for me this way, now I can claim to be outraged when it's pointed out and demand extra time to correct it". This works up to a point, but these things pile up. One small mistake is very forgiveable, except in the context of having made lots of other (perhaps convenient for you) "mistakes" and then it looks like incompetence regardless of your actual motivation.
  - C1sc0cat 8y ago
    grin I have seen this working with x.400 mail - Sprint flat out ignored stuff. ICL decided to start an index at 0 when the spec said MUST start at 1 - and oops look a divide by zero error
- bluejekyll 8y ago
  > As a simple case, you will sometimes come across documentation that thinks that DNS names cannot start with a digit, which does not match reality at all. I wish that were true. It’s seriously annoying that DNS names are nearly indistinguishable from ipv4 addresses.
  - technion 8y ago
    To complicate this further, there are certificates issued with IP addresses as names. One of the early bugs in CT Advisor[0] involved not knowing what to do with such a thing. I'd be interested in whether those writing this report considered these a valid URI. An obvious example: https://1.1.1.1/ https://1.1.1.1/ [0] https://ctadvisor.lolware.net/ https://ctadvisor.lolware.net/
    - tialaramex 8y ago
nly 8y ago
My default position on parsing anything more complex than a couple of comma-separated non-string values these days is to write a grammar and pick up a tool. I wish more programmers felt this way.
- AllegedAlec 8y ago
  Event that is always highly annoying. How do you deal with (for example) Dutch decimal numbers, which use the comma for decimal separation, or numbers with a comma as a thousands separator?
  - LeonM 8y ago
    'Dutch' notation can usually be distinguished with enough context (i.e. if the number has decimals), or by comparing it to other numbers found in a file. But don't get me started on people mixing American date notation and ISO notation. Especially mixing the separators. If you ever have to work with date notations, use a hyphen as a separator for ISO, and use a forward slash (/) when using American notation. It's the only way to distinguish dates before the 13th day of the month.
    - riffraff 8y ago
      I am sorry to tell you the rest of the world also uses slash with dates, it's not just a US thing. But with same field order.
      - mattashii 8y ago
        Please note that in The Netherlands, the most commonly used date format using '/' is day/month/year, not month/day/year as seen in the US. See also https://en.wikipedia.org/wiki/Date_format_by_country https://en.wikipedia.org/wiki/Date_format_by_country
userbinator 8y ago
Interesting how Apple's SecureTransport seems to be the most permissive of them all, rejecting 0 certificates that all the others complained about syntactic errors with in the dataset.
sneak 8y ago
It constantly underscores how early we are in the development of reliable tooling that such basic errors as these are still regularly being made. I am glad this sort of research is being done to uncover and identify our societal technical debt.
- nailer 8y ago
  There's a lot of debt from just ASN1 and X509 parsing itself. The formats are only popular because of their popularity: their payloads are what matters.
  - wahern 8y ago
    The formats are popular because they were popular in closed-source software. And they were popular in closed-source software because there were (and still are) good commercial parser generators for ASN.1. ASN.1 has been a failure in open source because there weren't any good parser generators. The only open source ASN.1 generator for C code I'm familiar with is asn1c[1], which was published long after OpenSSL and other projects added their ad hoc certificate parsing code. I think there may be one or two for Java, but that's about it. Moreover, open source projects have historically disfavored using parser generators. They don't like the dependency, and there's still the sense that good protocols shouldn't need parser generators--contrast commercial protocols like X.whatever with SMTP, HTTP, etc. ASN.1-based formats were never intended to be parsed using hand written code. Abstraction Syntax Notation refers to the grammar for specifying the wire-line formats. ASN.1 is solid technology. The technical debt exists because open source tooling never developed around it. At first the community thought it was too complicated and unnecessary. Then when the need arose the community simply reinvented the wheel (Protocol Buffers, etc). [1] asn1c is amazing, BTW. Not only will it generate encoders and decoders given the ASN.1 specification, but it can generate streaming encoders and decoders, something that most open source alternatives (e.g. Protocol Buffers) can't do. (And by streaming I mean streaming a single message, which is important for low-memory environments, either because of minimal hardware resources, as a performance optimization, or as a security constraint.)
    - 8y ago

146 points by snaky 8y ago

lsh 8y ago

see also langsec.org non-Turing complete languages, formal grammars and context-free parsing are fascinating and the current state of tooling is really sophisticated but sparse. So much boilerplate code and adhoc parsing exists in my code and I never really appreciated how much until I asked myself if I really needed a Turing complete language to tell me if an input really is an integer or a string of 4 chars, etc. I'm terrified what would happen if a fuzzer ever went to town on my python code.

zvrba 8y ago
The last couple of times I had to parse/generate string according to something that can be described with a grammar, I resisted the temptation to implement an ad-hoc parser just because it was "simple". So I took the time and started to use Boost Qi/Karma (C++) instead. Just BECAUSE the formats are simple, they are the perfect opportunity to start learning more powerful tools.

k-ian 8y ago

[comment about x509 being bad]

Dylan16807 8y ago
Sucks that you're being downvoted since at the time you posted "X.509" wasn't in the title and it was reasonable context on why "20% of HTTPS server cert are incorrect, half considered valid by libs"

jcranmer 8y ago

There's one thing that gives me pause here: The single most common error is listed as DNS/URI/email format violations. There is absolutely no discussion as to what kinds of violations these break into, nor is there even a discussion as to what the paper thinks the correct formats ought to be. This is unfortunate because the format of these parameters is one thing where specifications often have a view of the world which is completely incongruent with reality. As a simple case, you will sometimes come across documentation that thinks that DNS names cannot start with a digit, which does not match reality at all.

tialaramex 8y ago
If they don't discuss it, it seems reasonable to assume they mean as specified. PKIX and the Baseline Requirements are pretty clear on how this works, despite ignorance from the CAs and end users. Note in particular that SAN dnsNames in PKIX are host names, and not all DNS names are acceptable names for hosts per the specifications. In my experience "I wasn't sure of the format definition" is code for "I knew this was strictly forbidden but it's more convenient for me this way, now I can claim to be outraged when it's pointed out and demand extra time to correct it". This works up to a point, but these things pile up. One small mistake is very forgiveable, except in the context of having made lots of other (perhaps convenient for you) "mistakes" and then it looks like incompetence regardless of your actual motivation.
- C1sc0cat 8y ago
  grin I have seen this working with x.400 mail - Sprint flat out ignored stuff. ICL decided to start an index at 0 when the spec said MUST start at 1 - and oops look a divide by zero error
bluejekyll 8y ago
> As a simple case, you will sometimes come across documentation that thinks that DNS names cannot start with a digit, which does not match reality at all. I wish that were true. It’s seriously annoying that DNS names are nearly indistinguishable from ipv4 addresses.
- technion 8y ago
  To complicate this further, there are certificates issued with IP addresses as names. One of the early bugs in CT Advisor[0] involved not knowing what to do with such a thing. I'd be interested in whether those writing this report considered these a valid URI. An obvious example: https://1.1.1.1/ https://1.1.1.1/ [0] https://ctadvisor.lolware.net/ https://ctadvisor.lolware.net/
  - tialaramex 8y ago

nly 8y ago

My default position on parsing anything more complex than a couple of comma-separated non-string values these days is to write a grammar and pick up a tool. I wish more programmers felt this way.

AllegedAlec 8y ago
Event that is always highly annoying. How do you deal with (for example) Dutch decimal numbers, which use the comma for decimal separation, or numbers with a comma as a thousands separator?
- LeonM 8y ago
  'Dutch' notation can usually be distinguished with enough context (i.e. if the number has decimals), or by comparing it to other numbers found in a file. But don't get me started on people mixing American date notation and ISO notation. Especially mixing the separators. If you ever have to work with date notations, use a hyphen as a separator for ISO, and use a forward slash (/) when using American notation. It's the only way to distinguish dates before the 13th day of the month.
  - riffraff 8y ago
    I am sorry to tell you the rest of the world also uses slash with dates, it's not just a US thing. But with same field order.
    - mattashii 8y ago
      Please note that in The Netherlands, the most commonly used date format using '/' is day/month/year, not month/day/year as seen in the US. See also https://en.wikipedia.org/wiki/Date_format_by_country https://en.wikipedia.org/wiki/Date_format_by_country

userbinator 8y ago

Interesting how Apple's SecureTransport seems to be the most permissive of them all, rejecting 0 certificates that all the others complained about syntactic errors with in the dataset.

sneak 8y ago

It constantly underscores how early we are in the development of reliable tooling that such basic errors as these are still regularly being made. I am glad this sort of research is being done to uncover and identify our societal technical debt.

nailer 8y ago
There's a lot of debt from just ASN1 and X509 parsing itself. The formats are only popular because of their popularity: their payloads are what matters.
- wahern 8y ago
  The formats are popular because they were popular in closed-source software. And they were popular in closed-source software because there were (and still are) good commercial parser generators for ASN.1. ASN.1 has been a failure in open source because there weren't any good parser generators. The only open source ASN.1 generator for C code I'm familiar with is asn1c[1], which was published long after OpenSSL and other projects added their ad hoc certificate parsing code. I think there may be one or two for Java, but that's about it. Moreover, open source projects have historically disfavored using parser generators. They don't like the dependency, and there's still the sense that good protocols shouldn't need parser generators--contrast commercial protocols like X.whatever with SMTP, HTTP, etc. ASN.1-based formats were never intended to be parsed using hand written code. Abstraction Syntax Notation refers to the grammar for specifying the wire-line formats. ASN.1 is solid technology. The technical debt exists because open source tooling never developed around it. At first the community thought it was too complicated and unnecessary. Then when the need arose the community simply reinvented the wheel (Protocol Buffers, etc). [1] asn1c is amazing, BTW. Not only will it generate encoders and decoders given the ASN.1 specification, but it can generate streaming encoders and decoders, something that most open source alternatives (e.g. Protocol Buffers) can't do. (And by streaming I mean streaming a single message, which is important for low-memory environments, either because of minimal hardware resources, as a performance optimization, or as a security constraint.)
  - 8y ago