[therightkey] Thoughts on reducing SCT sizes (was Re: [cabfpub] Updated Certificate Transparency + Extended Validation plan)

[Rob Stradling <[e-mail]>]

On Tue, Feb 4, 2014 at 12:33 PM, Jeremy Rowley wrote:
> Three or four proofs for a 27 month certificate is way too many.
<snip>
> Adding 400 bytes per certificate will make EV certificates unusable by entities concerned with performance.

The updated CT+EV plan requires three SCTs for a (maximum length) 
27-month EV certificate, not four.  400 bytes for three SCTs is about 
right though.

Assuming RFC6962-compliant v1 SCTs that contain no SCT extensions and 
are signed using ECDSA and a P-256 private key, then, including all of 
the ASN.1 fluff for the SCT List certificate extension, I calculate that 
it'll be...

140 or 141 bytes to embed 1 SCT

261 to 263 bytes to embed 2 SCTs

380 to 383 bytes to embed 3 SCTs

For (non-EV) validity periods between 27 and 39 months:
499 to 503 bytes to embed 4 SCTs

On 04/02/14 17:52, Adam Langley wrote:
<snip>
> We should make the SCTs as small as possible

Agreed.  Time for some back-of-an-envelope sums.  For SCT v2, if we were 
to pack in the data as tightly as possible I reckon we could cut it down 
to as little as...

84 bytes to embed 1 SCT

159 bytes to embed 2 SCTs

231 bytes to embed 3 SCTs

303 bytes to embed 4 SCTs

Here's how...

1. Use a shorter OID for the SCT List extension.  Perhaps CABForum could 
define 2.23.140.n (with n < 128).  Save 6 bytes.

2. The first 2 bytes of the SignedCertificateTimestampList structure are 
its total length.  Since this can be calculated from the OCTET STRING 
length, these 2 bytes could be omitted.  Save 2 bytes.

3. Pack the SCT fields into as few bytes as possible for the common 
case, whilst retaining options for future expansion.  Save 37 bytes per SCT.
Replace...
   (1 byte)    Version sct_version;
   (32 bytes)  LogID id;
   (8 bytes)   uint64 timestamp;
   (2+? bytes) CtExtensions extensions;
...with...
   (2 bits)    sct_version    (00=v1; 01=v2; 10,11=unassigned)
   (2 bits)    log_id_type    (00=SHA-256(log_public_key);
                               01=1-byte Registered Log ID;
                               10=2-byte Registered Log ID;
                               11=4-byte Registered Log ID)
   (2 bits)    timestamp_size (00=8-bytes;
                               01=6-bytes;
                               10=5-bytes;
                               11=4-bytes)
   (1 bit)     extensions     (0=CtExtensions is present;
                               1=CtExtensions is absent)
   (1 bit)     signature_type (0=digitally-signed struct;
                               1=raw Ed25519 signature)
   For the common case:
   (1 byte)    Registered Log ID
   (4 bytes)   Timestamp (seconds, not milliseconds)

4. Use the Ed25519 signature scheme instead of ECDSA.  ECDSA signatures 
using a P-256 key seem to be 72 or 73 bytes, whereas Ed25519 signatures 
are 64 bytes.  Save 8 or 9 bytes per SCT.
Also, for Ed25519, omit the 2 bytes containing the hash algorithm and 
signature algorithm from the "digitally-signed struct" header.  Save 2 
bytes per SCT.

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