Re: [pkix] World's smallest well-formed certificate

[Sean Leonard <[e-mail]>]

Thank you all for the responses. Looks like Erwann's proposal is the 
smallest.

The reason for this inquiry a couple of weeks ago, was because I was 
working on draft-seantek-certspec-06 (recently uploaded; related topic), 
and was developing a suggested algorithm for a parser to pick out a 
certificate in arbitrary data. Arbitrary data means a fixed stream of 
octets that has no labeling or identifying information, i.e., what you 
would get when opening a file, or opening a MIME entity of Content-Type 
application/octet-stream.

If the data begins with "-----BEGIN ", then a parser can safely assume 
that the data is in textual encoding, i.e., RFC 7468, because "-----" is 
not valid DER.

If the data begins with SEQUENCE (30h) plus a length that is the length 
of the data blob minus the tag and length octets, it is likely that the 
data is DER encoded.

But I say "likely", because Erwann's 66-octet certificate starts with 
the bytes "0@06"; Rob Stradling's 99-octet certificate starts with the 
bytes "0a0W". These are also valid ASCII characters, and it's possible 
that a stream of text that contains a textually encoded certificate 
later in the stream. So, they are ambiguous.

I haven't tried yet, but even an outer length encoding greater than 127 
(0x7F) could be chosen to represent a valid UTF-8 sequence. (The length 
octet would have to be 0xC2 at a minimum, which decodes to 66 bytes of a 
length integer...and the next byte would have to be 0x80 to be valid 
UTF-8. For the smallest length, it would be 0x80 plus 65 0x00-octets. 
Basically a pathologically large certificate. But not a structurally 
invalid one per RFC 5280 or X.509. Most likely this would cause some 
integer overflow error in an ASN.1 decoder, if you go there.) The 
indefinite form, which is in BER but not DER, but a parser may want to 
handle anyway, would have a length octet of 0x80, which is not valid 
UTF-8. (However if it is in another unspecified character set, all bets 
are off.)

For details, see Appendix D of draft-seantek-certspec-06: 
<https://tools.ietf.org/html/draft-seantek-certspec-06>.

Comments welcome; thanks in advance!

Sean

PS There is also the possibility that the stream can start with Unicode 
BOM bytes (FE FF; FF FE; EF BB BF; 00 00 FE FF; FF FE 00 00), which I 
think needs to be a supported case for a robust parser. Fortunately none 
of those are valid DER or even BER sequences for the start of a 
certificate, so a parser can safely assume text mode.

On 5/18/2016 6:01 AM, Erwann Abalea wrote:
> Bonjour,
>
> Your examples have serial numbers encoded with a zero length, this is 
> not DER compliant.
> The Name type used for issuer and subject is an unconstrained SEQUENCE 
> OF, so in theory it can be empty and be well-formed (from a DER point 
> of view).
>
> My proposal, 66 octets:
> -----BEGIN CERTIFICATE-----
> MEAwNgIBADADBgEAMAAwHhcNMTYwNTE4MDAwMDAwWhcNMTcwNTE4MDAwMDAwWjAA
> MAgwAwYBAAMBADADBgEAAwEA
> -----END CERTIFICATE-----
>
>
> 2016-05-18 11:25 GMT+02:00 Rob Stradling <[e-mail] 
> <mailto:[e-mail]>>:
>
>     Hi Sean. I can get OpenSSL to not barf in 99 bytes...
>
>     $ echo "-----BEGIN CERTIFICATE-----
>     MGEwVwIAMAMGAQAwCTEHMAUGAQATADAeFw0xNjA1MTgwMDAwMDBaFw0xNzA1MTgw
>     MDAwMDBaMAkxBzAFBgEAEwAwGDANBgkqhkiG9w0BAQEFAAMHADAEAgACADADBgEA
>     AwEA
>     -----END CERTIFICATE-----" | openssl x509 -text -noout
>     Certificate:
>         Data:
>             Version: 1 (0x0)
>             Serial Number: 0 (0x0)
>         Signature Algorithm: 0.0
>             Issuer: 0.0=
>             Validity
>                 Not Before: May 18 00:00:00 2016 GMT
>                 Not After : May 18 00:00:00 2017 GMT
>             Subject: 0.0=
>             Subject Public Key Info:
>                 Public Key Algorithm: rsaEncryption
>                     Public-Key: (0 bit)
>                     Modulus: 0
>                     Exponent: 0
>         Signature Algorithm: 0.0
>
>
>     I see what you mean about barfing on a "malformed" public key. 
>     This was my first attempt...
>
>     $ echo "-----BEGIN CERTIFICATE-----
>     MFEwRwIAMAMGAQAwCTEHMAUGAQATADAeFw0xNjA1MTgwMDAwMDBaFw0xNzA1MTgw
>     MDAwMDBaMAkxBzAFBgEAEwAwCDADBgEAAwEAMAMGAQADAQA=
>     -----END CERTIFICATE-----" | openssl x509 -text -noout
>     Certificate:
>         Data:
>             Version: 1 (0x0)
>             Serial Number: 0 (0x0)
>         Signature Algorithm: 0.0
>             Issuer: 0.0=
>             Validity
>                 Not Before: May 18 00:00:00 2016 GMT
>                 Not After : May 18 00:00:00 2017 GMT
>             Subject: 0.0=
>             Subject Public Key Info:
>                 Public Key Algorithm: 0.0
>                 Unable to load Public Key
>     3073144508 <tel:[phone]>:error:0609E09C:digital envelope
>     routines:PKEY_SET_TYPE:unsupported algorithm:p_lib.c:231:
>     3073144508 <tel:[phone]>:error:0B07706F:x509 certificate
>     routines:X509_PUBKEY_get:unsupported algorithm:x_pubkey.c:148:
>         Signature Algorithm: 0.0
>
>     P.S. OpenSSL barfs on an RDN Attribute of type NULL, so I used a
>     zero-length PrintableString instead.
>
>     On 18/05/16 08:29, Sean Leonard wrote:
>
>         I'm working on a problem that involves the DER encoding of the
>         smallest
>         well-formed (yet pathological) certificate. How many octets
>         can the
>         world's smallest well-formed certificate be?
>
>         A Certificate is a SEQUENCE of TBSCertificate,
>         AlgorithmIdentifier, and
>         BIT STRING (the signature). The world's smallest certificate
>         would be
>         version = 1 (therefore omitted), a serial number of 0, a
>         hypothetical
>         signature (AlgorithmIdentifier) that has the world's smallest
>         object
>         identifier (0.0) and no parameters, an issuer Name
>         (distinguished name)
>         that has one RDN that has one Attribute whose type is the world's
>         smallest object identifier (0.0) and whose value is the
>         ASN.1's smallest
>         value (NULL), with proper validity times, the same or similar
>         smallest
>         subject Name, a well-formed SubjectPublicKeyInfo, and none of the
>         optional fields: issuerUniqueID, subjectUniqueID, and extensions.
>
>         By "well-formed", I mean that an ASN.1 '88 parser (i.e., one
>         that does
>         not enforce information object classes) will parse it
>         (including the BIT
>         STRING contents) and not barf. Such a certificate could not
>         possibly be
>         "valid", since the signature block would not be a real digital
>         signature.
>
>         Sean
>
>         (PS For those who want to know "why", it's because I am trying
>         to test
>         some assumptions about how small a certificate can be.)
>
>
>     -- 
>     Rob Stradling
>     Senior Research & Development Scientist
>     COMODO - Creating Trust Online
>
>
>     _______________________________________________
>     pkix mailing list
>     [e-mail] <mailto:[e-mail]>
>     https://www.ietf.org/mailman/listinfo/pkix
>
>
>
>
> -- 
> Erwann.
>
>
> _______________________________________________
> pkix mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/pkix