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

From: Sean Leonard <[email-masked]>
Date: Wed, 18 May 2016 00:29:11 -0700

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.)

---

From: Rob Stradling <[email-masked]>
Date: Wed, 18 May 2016 10:25:55 +0100

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:error:0609E09C:digital envelope 
routines:PKEY_SET_TYPE:unsupported algorithm:p_lib.c:231:
3073144508: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.

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Erwann Abalea <[email-masked]>
Date: Wed, 18 May 2016 15:01:51 +0200

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 <[email-masked]>:

> _______________________________________________
> pkix mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/pkix
>

-- 
Erwann.

---

From: Yoav Nir <[email-masked]>
Date: Wed, 18 May 2016 16:15:21 +0300

$ openssl x509 -in smallest.crt -text
Certificate:
    Data:
        Version: 1 (0x0)
        Serial Number: 0 (0x0)
    Signature Algorithm: 0.0
        Issuer: 
        Validity
            Not Before: May 18 00:00:00 2016 GMT
            Not After : May 18 00:00:00 2017 GMT
        Subject: 
        Subject Public Key Info:
            Public Key Algorithm: 0.0
            Unable to load Public Key
140735154757712:error:0609E09C:digital envelope routines:PKEY_SET_TYPE:unsupported algorithm:p_lib.c:231:
140735154757712:error:0B07706F:x509 certificate routines:X509_PUBKEY_get:unsupported algorithm:x_pubkey.c:148:
    Signature Algorithm: 0.0
-----BEGIN CERTIFICATE-----
-----END CERTIFICATE——

> On 18 May 2016, at 4:01 PM, Erwann Abalea <[email-masked]> 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:
> 2016-05-18 11:25 GMT+02:00 Rob Stradling <[email-masked] <mailto:[email-masked]>>:
> I see what you mean about barfing on a "malformed" public key.  This was my first attempt...
> 
> 3073144508 <tel:3073144508>:error:0609E09C:digital envelope routines:PKEY_SET_TYPE:unsupported algorithm:p_lib.c:231:
> 3073144508 <tel:3073144508>: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.
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/pkix <https://www.ietf.org/mailman/listinfo/pkix>
> 
> 
> 
> -- 
> Erwann.

---

From: Rob Stradling <[email-masked]>
Date: Wed, 18 May 2016 14:20:27 +0100

On 18/05/16 14:01, Erwann Abalea wrote:
> 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).

Good points.

> -----END CERTIFICATE-----

Erwann wins.  ;-)

---

From: Annie <[email-masked]>
Date: Thu, 19 May 2016 15:14:03 +0200

There are many and not only one smallest certificate, any serial number
less than 128 give a same length cert. The same applies for the validity
time.

Note that my cert
-----BEGIN CERTIFICATE-----
MDwwMgIBfzADBgEAMAAwGhcLMTYwNTE4MDEwMVoXCzE3MDUxODAyMDJaMAAwCDAD
BgEAAwEAMAMGAQADAQA=
-----END CERTIFICATE-----

is only 60 bytes log, therefore Ann wins.
Explanation: the seconds in UTC time are optional.

/Ann.

---

From: "David A. Cooper" <[email-masked]>
Date: Thu, 19 May 2016 09:31:45 -0400

On 05/19/2016 09:14 AM, Annie wrote:

Actually, this isn't correct. According to Clause 11 of X.690
(Restrictions on BER employed by both CER and DER):

11.8  UTCTime

11.8.1 The encoding shall terminate with "Z", as
described in the ITU-T X.680 | ISO/IEC 8824-1 clause on UTCTime.

11.8.2  The seconds
element shall always be present.

11.8.3  Midnight (GMT) shall be represented in the form:

"YYMMDD000000Z"

where "YYMMDD" represents the day following the midnight in
question.

11.8.4 Examples of valid representations

"920521000000Z"

"920622123421Z"

"920722132100Z"

11.8.5 Examples of invalid representations

"920520240000Z"      (midnight represented
incorrectly)

"9207221321Z"
(seconds of "00" omitted)

---

From: Annie <[email-masked]>
Date: Thu, 19 May 2016 15:38:34 +0200

> (Restrictions on BER employed by both CER and DER):
*OK, Erwann wins.
*