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

[Erwann Abalea]

Le 05/02/2014 13:36, Rob Stradling a écrit :
[...]
> 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)

We're moving again away from ASN.1.
Save 2 more bits by having the sct_version set by the extension OID.
Later, change the encoding of the transmitted certificates from DER to 
UPER (change it internally back to DER to verify the signature).

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

This is not between Ed25519 and ECDSA, but between ASN.1+DER encoding 
and pure binary.
An ECDSA P256 signature is also 64 bytes long (2 integers modulo a 256 
bits quantity), but they are both encoded as INTEGERs (+2 or +3 each), 
enclosed in a SEQUENCE (+2), and encapsulated in a BITSTRING (+3).

> 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.
That's also doable in ECDSA. You're just trading flexibility with space.