Certificate verification relies on undefined protobuf behavior

[titanous]

Protobuf does not guarantee that the encoding is canonical/repeatable into the exact same bytes (especially between protobuf versions), just that it will successfully decode into the expected data.

nebula/cert/cert.go

Lines 233 to 240 in d68a039

	// CheckSignature verifies the signature against the provided public key
	func (nc *NebulaCertificate) CheckSignature(key ed25519.PublicKey) bool {
	b, err := proto.Marshal(nc.getRawDetails())
	if err != nil {
	return false
	}
	return ed25519.Verify(key, b, nc.Signature)
	}

The code above verifies a certificate signature by encoding the certificate details into the protobuf representation and then verifying the signature across the message bytes that were encoded by the verifier. This means that if there is any meaningful skew between the encoder in the program that signed the certificate and the program that is verifying the certificate, it will not verify successfully.

The solution is to have the creator of the certificate encode it before signing and then send it in this representation as bytes:

message SignedCert {
  bytes data = 1;
  bytes signature = 2;
}

And then the verifier can decode the data into the RawNebulaCertificateDetails and separately run the signature algorithm across the data containing the encoded bytes from the signer to confirm that the certificate is properly signed.

[titanous]

Oh, forgot to mention that this should be a backwards compatible change, as embedded protobuf message fields are actually encoded in exactly the same format as bytes.

[nbrownus]

Thanks for raising this. The main reason we do this is to avoid duplication of data on handshakes. To use vanilla noise, the public key needed to be part of the noise portion of the handshake packet(s), while the remaining bits of the certificate needed to be in the payload. To properly avoid version/language incompatibilities we would need to double send that data or modify how the noise protocol worked. The last thing we wanted to do was modify the noise library to avoid this case (btw thank you for your great work there).

We do have tests to catch the case where signature verification would fail and are certainly open to other thoughts or suggestions, but as it stands this would be a complicated change to make.

[yilunzhang]

I think the test might not be enough to reveal the problem because pb marshal of the same object could be dependent on (pbversion, os) and it's really hard to cover all different os and pb versions in tests. Specifically, this problem seems to occur more for array data while the data you are signing here contains repeated xxx and bytes fields...

We actually faced the same problem at NKN and struggled for a while. AFAIK there is no pb-equivalent stuff that can provide canonical encoding. The solution we finally used is to replace proto.Marshal before ed25519.Verify with a customized encoding function and use it only for signature & verification 😂 I'm not familiar with the noise library and not sure if you can do the same thing without modifying the noise library...

[nbrownus]

Correct, it is not sufficient cross platform but will raise issues when updating the library within a platform.

Are you saying you hit this snag with nebula at NKN or with another project? I would be very interested to hear more if the compilation and deployment if it was directly related to nebula.

[yilunzhang]

Oh sorry for the confusion, it's not directly related to nebula but generally related to signing and verifying data encoded with protobuf (cross version/platform)...

[apognu]

Could this be the reason why Nebula certificates produced in another language (in my case, Rust) cannot be verified? nebula-cert print does display all the right info, but nebula-cert verify fails.

It indeed appears that the byte representation of the protobuf data is different between my program and Nebula, for the same source data, which explains why the signature verification would be an issue.

This would be quite important to be able to include Nebula into existing processes, like automate the creation of client certificates, where directly using the official command-line client is not possible or desired.

[wadey]

Could this be the reason why Nebula certificates produced in another language (in my case, Rust) cannot be verified? nebula-cert print does display all the right info, but nebula-cert verify fails.

@apognu can you share your implementation or an example of the generated bytes so we can see what the difference is? We would like to work towards finding a backwards compatible fix for this issue if we can.

[nbrownus]

Circling back on the rust specific issue, pb does not default to packing ints in rust. This protobuf definition fixes that:

syntax = "proto3";
package cert;

option go_package = "github.com/slackhq/nebula/cert";

message RawNebulaCertificate {
    RawNebulaCertificateDetails Details = 1;
    bytes Signature = 2;
}

message RawNebulaCertificateDetails {
    string Name = 1;

    // Ips and Subnets are in big endian 32 bit pairs, 1st the ip, 2nd the mask
    repeated uint32 Ips = 2 [packed = true];
    repeated uint32 Subnets = 3 [packed = true];

    repeated string Groups = 4;
    int64 NotBefore = 5;
    int64 NotAfter = 6;
    bytes PublicKey = 7;

    bool IsCA = 8;

    // sha-256 of the issuer certificate, if this field is blank the cert is self-signed
    bytes Issuer = 9;
}

While I agree that we exist in undefined behavior territory, we at least have confirmation of two languages being capable of working on the same byte representation of a nebula cert.

I'm closing this issue since any change here would ideally require bumping a major version and it appears likely that we can operate on the byte representation of a nebula cert in more than just go and rust.