Sign SubjectPublicKeyInfo instead of the raw public key

[Demi-Marie]

The SubjectPublicKeyInfo contains not only the key, but also the algorithm. It is theoretically possible for two different keys to have the same public key, but different algorithms, and one should not be accepted where the other was intended.

[marten-seemann]

What would be the plan for rolling this out? Making this change will break code that’s already deployed.

[Demi-Marie]

We can allocate a different extension that uses the SubjectPublicKeyInfo instead. For a transitional period, we can include both extensions, and eventually we can deprecate and remove support for the original extension.

[marten-seemann]

For a transitional period, we can include both extensions, and eventually we can deprecate and remove support for the original extension.

Including both extensions will increase the size of the handshake significantly. But can roll out the parsing code for the new extension, and switch the serialization code over to the new extension once we're confident that most peers have deployed the parsing code.

The SubjectPublicKeyInfo contains not only the key, but also the algorithm.

I'm wondering if it really makes sense to reuse the SubjectPublicKeyInfo here. As far as I can see, this would complicate things quite a bit in Go, since you don't have access to the serialized SubjectPublicKeyInfo bytes before you actually serialize the certificate. Could we achieve the same security properties by appending / prepending the algorithm to the public key?

[Demi-Marie]

@marten-seemann which implementations support this?

Current plan:

1. Create a list of X.509 algorithm IDs that are acceptable for libp2p when the current extension is used, and specify that any algorithm not on this list MUST be rejected. This prevents attacks similar to CVE-2020-0602 (“Whose Curve Is It Anyway”), although I do not believe any current implementation is vulnerable.
2. Add a new certificate extension that includes a signature of the full SubjectPublicKeyInfo.
3. Specify that if that extension is present, it MUST be used, and the existing one ignored.
4. Patch the existing implementations to use the new extension.
5. Eventually, deprecate and remove support for the old extension.

[Demi-Marie]

@marten-seemann For a given algorithm and key size, the SubjectPublicKeyInfo is actually the key plus a fixed prefix and suffix. Given that an implementation only needs to support one signature algorithm, this makes serialization trivial.

ASN.1 DER is prefix-free (no two distinct valid messages have a common prefix), so prepending the ASN.1 DER AlgorithmId to the public key bytes is enough for security. That said, SubjectPublicKeyInfo is just a two-element ASN.1 SEQUENCE, so it should not be hard to generate it. It is also significantly easier to verify.

[Demi-Marie]

In fact, the suffix is actually empty, so that means that only a prefix is needed. So there is actually not much more effort needed than is needed today ― merely some magic strings.

[Demi-Marie]

For libp2p-quic, the easiest approach would be to prepend the serialized AlgorithmId to the public key (encoded as an ASN.1 BIT STRING) before signing, but I suspect that is incredibly ad-hoc.

[marten-seemann]

@marten-seemann For a given algorithm and key size, the SubjectPublicKeyInfo is actually the key plus a fixed prefix and suffix.

Can you point me to the specification please?

For libp2p-quic, the easiest approach would be to prepend the serialized AlgorithmId to the public key (encoded as an ASN.1 BIT STRING) before signing, but I suspect that is incredibly ad-hoc.

QUIC uses the same code as TLS does.

[Demi-Marie]

@marten-seemann For a given algorithm and key size, the SubjectPublicKeyInfo is actually the key plus a fixed prefix and suffix.

Can you point me to the specification please?

It’s not part of any specification, but rather a consequence of ASN.1 DER works: changing the value of a BIT STRING does not change anything else. Only changing its length does.

Furthermore, in the specific case of SubjectPublicKeyInfo, the suffix turns out to be the empty string. That makes serializing a SubjectPublicKeyInfo simply string concatenation, and parsing it simply string matching.

[marten-seemann]

Sorry if this is a stupid question, but given an algorithm and a public key, how do I construct the bytes that I need to sign?

[Demi-Marie]

Various RFCs specify algorithm identifiers (OIDs) for various algorithms, as well as how their parameters (if any) should be encoded. That information, along with the public key, is then ASN.1 DER encoded.

Alternatively, one can do this encoding at compile-time: for a given algorithm and key length, the prefix that needs to be prepended to the public key is fixed. This can be computed at compile-time.

[Demi-Marie]

The following Rust source code provides the prefixes for P-256, P-384, and Ed25519. I have not generated the prefixes for RSA, but as RSA key generation is slow I do not believe that anyone will use RSA for libp2p. I did not include Ed448, P-521, DSA, or other curves as ring does not support them and DSA is deprecated.

The prefixes include the string libp2p-tls-handshake:.

pub const LIBP2P_P_256_SIGNING_PREFIX: [u8; 47] = [
    0x6c, 0x69, 0x62, 0x70, 0x32, 0x70, 0x2d, 0x74, 0x6c, 0x73, 0x2d, 0x68, 0x61, 0x6e, 0x64, 0x73,
    0x68, 0x61, 0x6b, 0x65, 0x3a, 0x30, 0x59, 0x30, 0x13, 0x06, 0x07, 0x2a, 0x86, 0x48, 0xce, 0x3d,
    0x02, 0x01, 0x06, 0x08, 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07, 0x03, 0x42, 0x00,
];
pub const LIBP2P_P_384_SIGNING_PREFIX: [u8; 44] = [
    0x6c, 0x69, 0x62, 0x70, 0x32, 0x70, 0x2d, 0x74, 0x6c, 0x73, 0x2d, 0x68, 0x61, 0x6e, 0x64, 0x73,
    0x68, 0x61, 0x6b, 0x65, 0x3a, 0x30, 0x76, 0x30, 0x10, 0x06, 0x07, 0x2a, 0x86, 0x48, 0xce, 0x3d,
    0x02, 0x01, 0x06, 0x05, 0x2b, 0x81, 0x04, 0x00, 0x22, 0x03, 0x62, 0x00,
];
pub const LIBP2P_ED25519_SIGNING_PREFIX: [u8; 33] = [
    0x6c, 0x69, 0x62, 0x70, 0x32, 0x70, 0x2d, 0x74, 0x6c, 0x73, 0x2d, 0x68, 0x61, 0x6e, 0x64, 0x73,
    0x68, 0x61, 0x6b, 0x65, 0x3a, 0x30, 0x2a, 0x30, 0x05, 0x06, 0x03, 0x2b, 0x65, 0x70, 0x03, 0x21,
    0x00,
];

And here is the script used to generate the prefixes:

#!/bin/bash --
set -euo pipefail
shopt -s extglob
export LC_ALL=C
tmpdir=$(mktemp -d)
trap 'rm -rf -- "$tmpdir"' EXIT

gen_ecdsa_bytes () {
   if [ $# != 3 ]; then
      printf 'Usage: CONST_NAME CURVE LEN\n'>&2;exit 1
   fi
   openssl ecparam -genkey -name "$2" |
   openssl ec -pubout -outform der > "$tmpdir/$1.dat" 2>/dev/null
   gen_der_bytes "$1" "$3"
}

gen_ed25519_key () {
   name=ED25519
   openssl genpkey -algorithm ed25519 |
   openssl pkey -pubout -outform der -out "$tmpdir/$name.dat"
   gen_der_bytes "$name" 32
}

gen_der_bytes () {
   if [ $# != 2 ]; then
      printf 'Usage: CONST_NAME LEN\n'>&2;exit 1
   fi
   case $2 in
      ([1-9]*([0-9])) :;;
      (*) echo 'Bad number'>&2; exit 1;;
   esac
   prefix=libp2p-tls-handshake: len=$(stat '-c%s' "$tmpdir/$1.dat")
   : "$((len -= "$2"))"
   printf 'pub const LIBP2P_%s_SIGNING_PREFIX: [u8; %d] = [\n' "$1" "$(( len + "${#prefix}" ))"
   { printf %s "$prefix" && head -c "$len" -- "$tmpdir/$1.dat"; } | xxd -i
   echo '];'
}

{
gen_ecdsa_bytes P_256 P-256 65
gen_ecdsa_bytes P_384 P-384 97
gen_ed25519_key
} | rustfmt

[Demi-Marie]

Including both extensions will increase the size of the handshake significantly. But can roll out the parsing code for the new extension, and switch the serialization code over to the new extension once we're confident that most peers have deployed the parsing code.

@marten-seemann Can you allocate a new OID for the new extension?

I'm wondering if it really makes sense to reuse the SubjectPublicKeyInfo here. As far as I can see, this would complicate things quite a bit in Go, since you don't have access to the serialized SubjectPublicKeyInfo bytes before you actually serialize the certificate. Could we achieve the same security properties by appending / prepending the algorithm to the public key?

If you mean the ASN.1 DER serialized AlgorithmIdentifier, then yes, although it would need to be extracted from the SubjectPublicKeyInfo when deserializing. You will need some (trivial) ASN.1 handling code either way.

[Demi-Marie]

@marten-seemann can we get this into the specification?

[DemiMarie]

What would be the plan for rolling this out? Making this change will break code that’s already deployed.

As it turns out, the Go implementation already signs the SubjectPublicKeyInfo, and the upcoming Rust implementation will as well. So this is just a case where the spec needs to be updated.