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

Yoav Nir <ynir.ietf@gmail.com> Wed, 18 May 2016 13:15 UTC

Return-Path: <ynir.ietf@gmail.com>
X-Original-To: pkix@ietfa.amsl.com
Delivered-To: pkix@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0BD6212D189 for <pkix@ietfa.amsl.com>; Wed, 18 May 2016 06:15:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.393
X-Spam-Level:
X-Spam-Status: No, score=-1.393 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, TRACKER_ID=1.306] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id qko0tVDonqMV for <pkix@ietfa.amsl.com>; Wed, 18 May 2016 06:15:33 -0700 (PDT)
Received: from mail-wm0-x230.google.com (mail-wm0-x230.google.com [IPv6:2a00:1450:400c:c09::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E6AC812D1D5 for <pkix@ietf.org>; Wed, 18 May 2016 06:15:25 -0700 (PDT)
Received: by mail-wm0-x230.google.com with SMTP id r12so34243925wme.0 for <pkix@ietf.org>; Wed, 18 May 2016 06:15:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:subject:from:in-reply-to:date:cc:message-id:references :to; bh=LjFp480vIKT2EuTassikeJVbxauunJR2lD3lEzdQlY4=; b=Kw/H2hbFdleqkymjhpvWKqbtYLL1t8R7MERlltppltxrRgwT+5uV7LYVxwX/2xR8wG r7+jcSO63Hp3W5rRnv2+RwMBJTy9yFwxcYkVBA5i3J8t6cZ2Lcc/Do0dEOTrtTUXXP41 /7KtnFquUu7L7SbpkYa1SdUA6SwhZHfWkcVh3Uz8684hHIOM5sxwrbuNon6I+lmv/lhX +eVhMTg9hoeXJgDkcLDQuDvanZ9KVqCUoirImK//oFYkKqZW/qn3kMRoQJqYMxPEWNHZ tEVX8xqG4gx7CxCISJtUS8gBxDeBQ4SB5gOaufy1v4TwKIcQFLUZd9ONrIW65UhcDIoa 6NaA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :message-id:references:to; bh=LjFp480vIKT2EuTassikeJVbxauunJR2lD3lEzdQlY4=; b=KYzLbNYmNb1cUAEIYIFKrBLeXg74i01ra0IWI2hxaP757QjzZ7EKXgXbewtK/qJxiy VVLS8Aea4wO9kh7N7mDcbUUdcTUJ+4KSi1bD48YniFPYhoqu8maEccfBT5XEs5K47lWC BGy4cV+RJkgL1C5qXFuB/l7mnk7J76+75cWMEb0YhQUfXIRH5wDkXiFzS1FsYTLqEqKS qyDTapW937DawY2Poq3U249oksuXtBF9VK8WsDmim0dhKvmpaaC1TsUuKfOqSpLYnyxW gAFfF5rm2580vjAfgVuzQdqd3xgqQrI6fUk4ue21mgaj+dq9duQMgb5bmtWzWPIzmKEW IVvA==
X-Gm-Message-State: AOPr4FW0YhwdMNsxWMoasNtx/o95x3/c+SiSe0/NkqUdrwioHM7H0zLZ20mNou8PlRZ/Mg==
X-Received: by 10.28.44.87 with SMTP id s84mr7210211wms.61.1463577324427; Wed, 18 May 2016 06:15:24 -0700 (PDT)
Received: from [172.24.248.41] (dyn32-131.checkpoint.com. [194.29.32.131]) by smtp.gmail.com with ESMTPSA id ib1sm8625482wjb.48.2016.05.18.06.15.22 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 18 May 2016 06:15:23 -0700 (PDT)
Content-Type: multipart/alternative; boundary="Apple-Mail=_C292EF3F-BDCF-4A05-8021-9AC6791B60CF"
Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\))
From: Yoav Nir <ynir.ietf@gmail.com>
In-Reply-To: <CA+i=0E78phJHizoOniU3+wrJBWKbLhCKwZKVF5oLC0xwqV74GQ@mail.gmail.com>
Date: Wed, 18 May 2016 16:15:21 +0300
Message-Id: <79530CBF-898A-45D9-A68D-76AB0F3BEDBC@gmail.com>
References: <7b8c0b5a-2133-b094-2d09-e37efae98994@seantek.com> <af723bb1-9cf6-d18d-7d0a-3c709daa0a94@comodo.com> <CA+i=0E78phJHizoOniU3+wrJBWKbLhCKwZKVF5oLC0xwqV74GQ@mail.gmail.com>
To: Erwann Abalea <eabalea@gmail.com>
X-Mailer: Apple Mail (2.3124)
Archived-At: <http://mailarchive.ietf.org/arch/msg/pkix/DbakdwwW1xp9-PFg-zUUrnhFmJ8>
Cc: "pkix@ietf.org" <pkix@ietf.org>, Sean Leonard <dev+ietf@seantek.com>
Subject: Re: [pkix] World's smallest well-formed certificate
X-BeenThere: pkix@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: PKIX Working Group <pkix.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/pkix>, <mailto:pkix-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/pkix/>
List-Post: <mailto:pkix@ietf.org>
List-Help: <mailto:pkix-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/pkix>, <mailto:pkix-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 18 May 2016 13:15:35 -0000

$ 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-----
MEAwNgIBADADBgEAMAAwHhcNMTYwNTE4MDAwMDAwWhcNMTcwNTE4MDAwMDAwWjAA
MAgwAwYBAAMBADADBgEAAwEA
-----END CERTIFICATE——

> On 18 May 2016, at 4:01 PM, Erwann Abalea <eabalea@gmail.com> 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 <rob.stradling@comodo.com <mailto:rob.stradling@comodo.com>>:
> 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: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.
> 
> 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
> pkix@ietf.org <mailto:pkix@ietf.org>
> https://www.ietf.org/mailman/listinfo/pkix <https://www.ietf.org/mailman/listinfo/pkix>
> 
> 
> 
> -- 
> Erwann.
> _______________________________________________
> pkix mailing list
> pkix@ietf.org
> https://www.ietf.org/mailman/listinfo/pkix