verify cert run long time when given one faked cert with large intermediate_certs that can't be verified by any anchors

[stanal]

give one cert that can't be verified by any ca in all anchors, the check_signatures can nerver be called
the verify logical will take long time to ended (may be expotent or quradic time)
`

  match loop_while_non_fatal_error(trust_anchors, |trust_anchor: &TrustAnchor| {
    let trust_anchor_subject = untrusted::Input::from(trust_anchor.subject);
    if cert.issuer != trust_anchor_subject { // always emitted
        println!("cert's issuer is not anchor's subject, return err");
        return Err(Error::UnknownIssuer.into());
    }
   check_signatures(supported_sig_algs, cert, trust_anchor_spki, signatures)?;  // will never do 

`

[stanal]

example: use self-signed cert for server-side, and client-side not load root cert which signed the server cert, client-side just use webpki-roots as anchors.
then client-side will nerver can verify the server certificate, and will loop to do build_chain again and again for long long time to end

[briansmith]

Which version of webpki are you using? If 0.22.1, did it work with 0.22.0?

[stanal]

Which version of webpki are you using? If 0.22.1, did it work with 0.22.0?

0.22.1

[briansmith]

Thanks. What happens if you use 0.22.0?

[stanal]

Thanks. What happens if you use 0.22.0?

it has the same problem
i think the rustls-webpki also has this problem, the verify_cert.rs are same to each other
i test that when given 10 intermidiates certs, the build_chain_inner function will be called 2060312 times and elp 22s to end ,
i guess the time is releative to n! where n is num of intermidiates

[stanal]

the counter signatures just limit the called times of verify_signed_data, but not limit the total recursion times of call build_chain_inner

[stanal]

I'm not sure whether need to limit the total recursion times, because when given one right chians that has large number of intermidiates certs, although it will take long time to verify, but it will verify successfully finnally

[ctz]

i test that when given 10 intermidiates certs, the build_chain_inner function will be called 2060312 times and elp 22s to end ,

could you clarify exactly what this test case looks like? because trying to reproduce with a ten-deep untrusted chain doesn't do that for me. though i can reproduce this issue with other shapes of chains.

It seems like a mistake to allow the same certificate to appear multiple times in the intermediates list (AFAIK that cannot, by definition, ever make an invalid chain become valid?)

[briansmith]

It seems like a mistake to allow the same certificate to appear multiple times in the intermediates list (AFAIK that cannot, by definition, ever make an invalid chain become valid?)

That's right. See https://github.com/nss-dev/nss/blob/bb4a1d38dd9e92923525ac6b5ed0288479f3f3fc/lib/mozpkix/lib/pkixbuild.cpp#L160.

See also buildForwardCallBudget in the same code base.

[stanal]

i test that when given 10 intermidiates certs, the build_chain_inner function will be called 2060312 times and elp 22s to end ,

could you clarify exactly what this test case looks like? because trying to reproduce with a ten-deep untrusted chain doesn't do that for me. though i can reproduce this issue with other shapes of chains.

see https://github.com/stanal/tlsserver/tree/main

It seems like a mistake to allow the same certificate to appear multiple times in the intermediates list (AFAIK that cannot, by definition, ever make an invalid chain become valid?)