| /* | |
| * Copyright (c) 2000, 2023, Oracle and/or its affiliates. All rights reserved. | |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| * | |
| * This code is free software; you can redistribute it and/or modify it | |
| * under the terms of the GNU General Public License version 2 only, as | |
| * published by the Free Software Foundation. Oracle designates this | |
| * particular file as subject to the "Classpath" exception as provided | |
| * by Oracle in the LICENSE file that accompanied this code. | |
| * | |
| * This code is distributed in the hope that it will be useful, but WITHOUT | |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| * version 2 for more details (a copy is included in the LICENSE file that | |
| * accompanied this code). | |
| * | |
| * You should have received a copy of the GNU General Public License version | |
| * 2 along with this work; if not, write to the Free Software Foundation, | |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| * | |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| * or visit www.oracle.com if you need additional information or have any | |
| * questions. | |
| */ | |
| package sun.security.provider.certpath; | |
| import java.io.IOException; | |
| import java.security.GeneralSecurityException; | |
| import java.security.InvalidAlgorithmParameterException; | |
| import java.security.PublicKey; | |
| import java.security.cert.*; | |
| import java.security.cert.CertPathValidatorException.BasicReason; | |
| import java.security.cert.PKIXReason; | |
| import java.util.ArrayList; | |
| import java.util.Arrays; | |
| import java.util.Collection; | |
| import java.util.Collections; | |
| import java.util.List; | |
| import java.util.LinkedList; | |
| import java.util.Set; | |
| import javax.security.auth.x500.X500Principal; | |
| import sun.security.provider.certpath.PKIX.BuilderParams; | |
| import static sun.security.x509.PKIXExtensions.*; | |
| import sun.security.x509.SubjectAlternativeNameExtension; | |
| import sun.security.x509.X509CertImpl; | |
| import sun.security.util.Debug; | |
| /** | |
| * This class builds certification paths in the forward direction. | |
| * | |
| * <p> If successful, it returns a certification path which has successfully | |
| * satisfied all the constraints and requirements specified in the | |
| * PKIXBuilderParameters object and has been validated according to the PKIX | |
| * path validation algorithm defined in RFC 5280. | |
| * | |
| * <p> This implementation uses a depth-first search approach to finding | |
| * certification paths. If it comes to a point in which it cannot find | |
| * any more certificates leading to the target OR the path length is too long | |
| * it backtracks to previous paths until the target has been found or | |
| * all possible paths have been exhausted. | |
| * | |
| * <p> This implementation is not thread-safe. | |
| * | |
| * @since 1.4 | |
| * @author Sean Mullan | |
| * @author Yassir Elley | |
| */ | |
| public final class SunCertPathBuilder extends CertPathBuilderSpi { | |
| private static final Debug debug = Debug.getInstance("certpath"); | |
| /* | |
| * private objects shared by methods | |
| */ | |
| private BuilderParams buildParams; | |
| private final CertificateFactory cf; | |
| private boolean pathCompleted = false; | |
| private PolicyNode policyTreeResult; | |
| private TrustAnchor trustAnchor; | |
| private PublicKey finalPublicKey; | |
| /** | |
| * Create an instance of <code>SunCertPathBuilder</code>. | |
| * | |
| * @throws CertPathBuilderException if an error occurs | |
| */ | |
| public SunCertPathBuilder() throws CertPathBuilderException { | |
| try { | |
| cf = CertificateFactory.getInstance("X.509"); | |
| } catch (CertificateException e) { | |
| throw new CertPathBuilderException(e); | |
| } | |
| } | |
| @Override | |
| public CertPathChecker engineGetRevocationChecker() { | |
| return new RevocationChecker(); | |
| } | |
| /** | |
| * Attempts to build a certification path using the Sun build | |
| * algorithm from a trusted anchor(s) to a target subject, which must both | |
| * be specified in the input parameter set. This method will | |
| * attempt to build in the forward direction: from the target to the CA. | |
| * | |
| * <p>The certification path that is constructed is validated | |
| * according to the PKIX specification. | |
| * | |
| * @param params the parameter set for building a path. Must be an instance | |
| * of <code>PKIXBuilderParameters</code>. | |
| * @return a certification path builder result. | |
| * @exception CertPathBuilderException Exception thrown if builder is | |
| * unable to build a complete certification path from the trusted anchor(s) | |
| * to the target subject. | |
| * @throws InvalidAlgorithmParameterException if the given parameters are | |
| * inappropriate for this certification path builder. | |
| */ | |
| @Override | |
| public CertPathBuilderResult engineBuild(CertPathParameters params) | |
| throws CertPathBuilderException, InvalidAlgorithmParameterException { | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.engineBuild(" + params + ")"); | |
| } | |
| buildParams = PKIX.checkBuilderParams(params); | |
| return build(); | |
| } | |
| private PKIXCertPathBuilderResult build() throws CertPathBuilderException { | |
| List<List<Vertex>> adjList = new ArrayList<>(); | |
| PKIXCertPathBuilderResult result = buildCertPath(false, adjList); | |
| if (result == null) { | |
| if (buildParams.certStores().size() > 1 || Builder.USE_AIA) { | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.engineBuild: 2nd pass; " + | |
| "try building again searching all certstores"); | |
| } | |
| // try again | |
| adjList.clear(); | |
| result = buildCertPath(true, adjList); | |
| if (result != null) { | |
| return result; | |
| } | |
| } | |
| throw new SunCertPathBuilderException("unable to find valid " | |
| + "certification path to requested target", | |
| new AdjacencyList(adjList)); | |
| } | |
| return result; | |
| } | |
| private PKIXCertPathBuilderResult buildCertPath(boolean searchAllCertStores, | |
| List<List<Vertex>> adjList) | |
| throws CertPathBuilderException | |
| { | |
| // Init shared variables and build certification path | |
| pathCompleted = false; | |
| trustAnchor = null; | |
| finalPublicKey = null; | |
| policyTreeResult = null; | |
| LinkedList<X509Certificate> certPathList = new LinkedList<>(); | |
| try { | |
| buildForward(adjList, certPathList, searchAllCertStores); | |
| } catch (GeneralSecurityException | IOException e) { | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.engineBuild() exception in " | |
| + "build"); | |
| e.printStackTrace(); | |
| } | |
| throw new SunCertPathBuilderException("unable to find valid " | |
| + "certification path to requested target", e, | |
| new AdjacencyList(adjList)); | |
| } | |
| // construct SunCertPathBuilderResult | |
| try { | |
| if (pathCompleted) { | |
| if (debug != null) | |
| debug.println("SunCertPathBuilder.engineBuild() " | |
| + "pathCompleted"); | |
| // we must return a certpath which has the target | |
| // as the first cert in the certpath - i.e. reverse | |
| // the certPathList | |
| Collections.reverse(certPathList); | |
| return new SunCertPathBuilderResult( | |
| cf.generateCertPath(certPathList), trustAnchor, | |
| policyTreeResult, finalPublicKey, | |
| new AdjacencyList(adjList)); | |
| } | |
| } catch (CertificateException e) { | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.engineBuild() exception " | |
| + "in wrap-up"); | |
| e.printStackTrace(); | |
| } | |
| throw new SunCertPathBuilderException("unable to find valid " | |
| + "certification path to requested target", e, | |
| new AdjacencyList(adjList)); | |
| } | |
| return null; | |
| } | |
| /* | |
| * Private build forward method. | |
| */ | |
| private void buildForward(List<List<Vertex>> adjacencyList, | |
| LinkedList<X509Certificate> certPathList, | |
| boolean searchAllCertStores) | |
| throws GeneralSecurityException, IOException | |
| { | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.buildForward()..."); | |
| } | |
| /* Initialize current state */ | |
| ForwardState currentState = new ForwardState(); | |
| currentState.initState(buildParams.certPathCheckers()); | |
| /* Initialize adjacency list */ | |
| adjacencyList.clear(); | |
| adjacencyList.add(new LinkedList<>()); | |
| currentState.untrustedChecker = new UntrustedChecker(); | |
| depthFirstSearchForward(buildParams.targetSubject(), currentState, | |
| new ForwardBuilder(buildParams, | |
| searchAllCertStores), | |
| adjacencyList, certPathList); | |
| } | |
| /* | |
| * This method performs a depth first search for a certification | |
| * path while building forward which meets the requirements set in | |
| * the parameters object. | |
| * It uses an adjacency list to store all certificates which were | |
| * tried (i.e. at one time added to the path - they may not end up in | |
| * the final path if backtracking occurs). This information can | |
| * be used later to debug or demo the build. | |
| * | |
| * See "Data Structure and Algorithms, by Aho, Hopcroft, and Ullman" | |
| * for an explanation of the DFS algorithm. | |
| * | |
| * @param dN the distinguished name being currently searched for certs | |
| * @param currentState the current PKIX validation state | |
| */ | |
| private void depthFirstSearchForward(X500Principal dN, | |
| ForwardState currentState, | |
| ForwardBuilder builder, | |
| List<List<Vertex>> adjList, | |
| LinkedList<X509Certificate> cpList) | |
| throws GeneralSecurityException, IOException | |
| { | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.depthFirstSearchForward(" + dN | |
| + ", " + currentState.toString() + ")"); | |
| } | |
| /* | |
| * Find all the certificates issued to dN which | |
| * satisfy the PKIX certification path constraints. | |
| */ | |
| Collection<X509Certificate> certs = | |
| builder.getMatchingCerts(currentState, buildParams.certStores()); | |
| List<Vertex> vertices = addVertices(certs, adjList, cpList); | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.depthFirstSearchForward(): " | |
| + "certs.size=" + vertices.size()); | |
| } | |
| /* | |
| * For each cert in the collection, verify anything | |
| * that hasn't been checked yet (signature, revocation, etc.) | |
| * and check for certs with repeated public key and subject. | |
| * Call depthFirstSearchForward() recursively for each good cert. | |
| */ | |
| vertices: | |
| for (Vertex vertex : vertices) { | |
| /* | |
| * Restore state to currentState each time through the loop. | |
| * This is important because some user-defined | |
| * checkers modify the state, which MUST be restored if | |
| * the cert eventually fails to lead to the target and | |
| * the next matching cert is tried. | |
| */ | |
| ForwardState nextState = (ForwardState) currentState.clone(); | |
| X509Certificate cert = vertex.getCertificate(); | |
| try { | |
| builder.verifyCert(cert, nextState, cpList); | |
| } catch (GeneralSecurityException gse) { | |
| if (debug != null) { | |
| debug.println("SunCertPathBuilder.depthFirstSearchForward()" | |
| + ": validation failed: " + gse); | |
| gse.printStackTrace(); | |
| } | |
| vertex.setThrowable(gse); | |
| continue; | |
| } | |
| /* | |
| * Certificate is good. | |
| * If cert completes the path, | |
| * process userCheckers that don't support forward checking | |
| * and process policies over whole path | |
| * and backtrack appropriately if there is a failure | |
| * else if cert does not complete the path, | |
| * add it to the path | |
| */ | |
| if (builder.isPathCompleted(cert)) { | |
| if (debug != null) | |
| debug.println("SunCertPathBuilder.depthFirstSearchForward()" | |
| + ": commencing final verification"); | |
| List<X509Certificate> appendedCerts = new ArrayList<>(cpList); | |
| /* | |
| * if the trust anchor selected is specified as a trusted | |
| * public key rather than a trusted cert, then verify this | |
| * cert (which is signed by the trusted public key), but | |
| * don't add it yet to the cpList | |
| */ | |
| PublicKey rootKey = cert.getPublicKey(); | |
| if (builder.trustAnchor.getTrustedCert() == null) { | |
| appendedCerts.add(0, cert); | |
| rootKey = builder.trustAnchor.getCAPublicKey(); | |
| if (debug != null) | |
| debug.println( | |
| "SunCertPathBuilder.depthFirstSearchForward " + | |
| "using buildParams public key: " + | |
| rootKey.toString()); | |
| } | |
| TrustAnchor anchor = new TrustAnchor | |
| (cert.getSubjectX500Principal(), rootKey, null); | |
| // add the basic checker | |
| List<PKIXCertPathChecker> checkers = new ArrayList<>(); | |
| BasicChecker basicChecker = new BasicChecker(anchor, | |
| buildParams.date(), | |
| buildParams.sigProvider(), | |
| true); | |
| checkers.add(basicChecker); | |
| Set<String> initExpPolSet = | |
| Collections.singleton(PolicyChecker.ANY_POLICY); | |
| PolicyNodeImpl rootNode = new PolicyNodeImpl(null, | |
| PolicyChecker.ANY_POLICY, null, false, initExpPolSet, false); | |
| PolicyChecker policyChecker | |
| = new PolicyChecker(buildParams.initialPolicies(), | |
| appendedCerts.size(), | |
| buildParams.explicitPolicyRequired(), | |
| buildParams.policyMappingInhibited(), | |
| buildParams.anyPolicyInhibited(), | |
| buildParams.policyQualifiersRejected(), | |
| rootNode); | |
| checkers.add(policyChecker); | |
| // add the constraints checker | |
| checkers.add(new ConstraintsChecker(appendedCerts.size())); | |
| // add the algorithm checker | |
| checkers.add(new AlgorithmChecker(builder.trustAnchor, | |
| buildParams.timestamp(), buildParams.variant())); | |
| buildParams.setCertPath(cf.generateCertPath(appendedCerts)); | |
| boolean revCheckerAdded = false; | |
| List<PKIXCertPathChecker> ckrs = buildParams.certPathCheckers(); | |
| for (PKIXCertPathChecker ckr : ckrs) { | |
| if (ckr instanceof PKIXRevocationChecker) { | |
| if (revCheckerAdded) { | |
| throw new CertPathValidatorException( | |
| "Only one PKIXRevocationChecker can be specified"); | |
| } | |
| revCheckerAdded = true; | |
| // if it's our own, initialize it | |
| if (ckr instanceof RevocationChecker) { | |
| ((RevocationChecker)ckr).init(builder.trustAnchor, | |
| buildParams); | |
| } | |
| } | |
| } | |
| // only add a RevocationChecker if revocation is enabled and | |
| // a PKIXRevocationChecker has not already been added | |
| if (buildParams.revocationEnabled() && !revCheckerAdded) { | |
| checkers.add(new RevocationChecker(builder.trustAnchor, | |
| buildParams)); | |
| } | |
| checkers.addAll(ckrs); | |
| // Why we don't need BasicChecker and RevocationChecker | |
| // if nextState.keyParamsNeeded() is false? | |
| for (int i = 0; i < appendedCerts.size(); i++) { | |
| X509Certificate currCert = appendedCerts.get(i); | |
| if (debug != null) | |
| debug.println("current subject = " | |
| + currCert.getSubjectX500Principal()); | |
| Set<String> unresCritExts = | |
| currCert.getCriticalExtensionOIDs(); | |
| if (unresCritExts == null) { | |
| unresCritExts = Collections.emptySet(); | |
| } | |
| for (PKIXCertPathChecker currChecker : checkers) { | |
| if (!currChecker.isForwardCheckingSupported()) { | |
| if (i == 0) { | |
| currChecker.init(false); | |
| // The user specified | |
| // AlgorithmChecker may not be | |
| // able to set the trust anchor until now. | |
| if (currChecker instanceof AlgorithmChecker) { | |
| ((AlgorithmChecker)currChecker). | |
| trySetTrustAnchor(builder.trustAnchor); | |
| } | |
| } | |
| try { | |
| currChecker.check(currCert, unresCritExts); | |
| } catch (CertPathValidatorException cpve) { | |
| if (debug != null) | |
| debug.println | |
| ("SunCertPathBuilder.depthFirstSearchForward(): " + | |
| "final verification failed: " + cpve); | |
| // If the target cert itself is revoked, we | |
| // cannot trust it. We can bail out here. | |
| if (buildParams.targetCertConstraints().match(currCert) | |
| && cpve.getReason() == BasicReason.REVOKED) { | |
| throw cpve; | |
| } | |
| vertex.setThrowable(cpve); | |
| continue vertices; | |
| } | |
| } | |
| } | |
| /* | |
| * Remove extensions from user checkers that support | |
| * forward checking. After this step, we will have | |
| * removed all extensions that all user checkers | |
| * are capable of processing. | |
| */ | |
| for (PKIXCertPathChecker checker : | |
| buildParams.certPathCheckers()) | |
| { | |
| if (checker.isForwardCheckingSupported()) { | |
| Set<String> suppExts = | |
| checker.getSupportedExtensions(); | |
| if (suppExts != null) { | |
| unresCritExts.removeAll(suppExts); | |
| } | |
| } | |
| } | |
| if (!unresCritExts.isEmpty()) { | |
| unresCritExts.remove(BasicConstraints_Id.toString()); | |
| unresCritExts.remove(NameConstraints_Id.toString()); | |
| unresCritExts.remove(CertificatePolicies_Id.toString()); | |
| unresCritExts.remove(PolicyMappings_Id.toString()); | |
| unresCritExts.remove(PolicyConstraints_Id.toString()); | |
| unresCritExts.remove(InhibitAnyPolicy_Id.toString()); | |
| unresCritExts.remove( | |
| SubjectAlternativeName_Id.toString()); | |
| unresCritExts.remove(KeyUsage_Id.toString()); | |
| unresCritExts.remove(ExtendedKeyUsage_Id.toString()); | |
| if (!unresCritExts.isEmpty()) { | |
| throw new CertPathValidatorException | |
| ("unrecognized critical extension(s)", null, | |
| null, -1, PKIXReason.UNRECOGNIZED_CRIT_EXT); | |
| } | |
| } | |
| } | |
| if (debug != null) | |
| debug.println("SunCertPathBuilder.depthFirstSearchForward()" | |
| + ": final verification succeeded - path completed!"); | |
| pathCompleted = true; | |
| /* | |
| * if the user specified a trusted public key rather than | |
| * trusted certs, then add this cert (which is signed by | |
| * the trusted public key) to the cpList | |
| */ | |
| if (builder.trustAnchor.getTrustedCert() == null) | |
| builder.addCertToPath(cert, cpList); | |
| // Save the trust anchor | |
| this.trustAnchor = builder.trustAnchor; | |
| /* | |
| * Extract and save the final target public key | |
| */ | |
| if (basicChecker != null) { | |
| finalPublicKey = basicChecker.getPublicKey(); | |
| } else { | |
| Certificate finalCert; | |
| if (cpList.isEmpty()) { | |
| finalCert = builder.trustAnchor.getTrustedCert(); | |
| } else { | |
| finalCert = cpList.getLast(); | |
| } | |
| finalPublicKey = finalCert.getPublicKey(); | |
| } | |
| policyTreeResult = policyChecker.getPolicyTree(); | |
| return; | |
| } else { | |
| // If successive certs are self-issued, don't continue search | |
| // on this branch. | |
| if (currentState.selfIssued && X509CertImpl.isSelfIssued(cert)) { | |
| if (debug != null) { | |
| debug.println("Successive certs are self-issued"); | |
| } | |
| return; | |
| } | |
| builder.addCertToPath(cert, cpList); | |
| } | |
| /* Update the PKIX state */ | |
| nextState.updateState(cert); | |
| /* | |
| * Append an entry for cert in adjacency list and | |
| * set index for current vertex. | |
| */ | |
| adjList.add(new LinkedList<>()); | |
| vertex.setIndex(adjList.size() - 1); | |
| /* recursively search for matching certs at next dN */ | |
| depthFirstSearchForward(cert.getIssuerX500Principal(), nextState, | |
| builder, adjList, cpList); | |
| /* | |
| * If path has been completed, return ASAP! | |
| */ | |
| if (pathCompleted) { | |
| return; | |
| } else { | |
| /* | |
| * If we get here, it means we have searched all possible | |
| * certs issued by the dN w/o finding any matching certs. | |
| * This means we have to backtrack to the previous cert in | |
| * the path and try some other paths. | |
| */ | |
| if (debug != null) | |
| debug.println("SunCertPathBuilder.depthFirstSearchForward()" | |
| + ": backtracking"); | |
| builder.removeFinalCertFromPath(cpList); | |
| } | |
| } | |
| } | |
| /* | |
| * Adds a collection of matching certificates to the | |
| * adjacency list. | |
| */ | |
| private static List<Vertex> addVertices(Collection<X509Certificate> certs, | |
| List<List<Vertex>> adjList, | |
| List<X509Certificate> cpList) | |
| { | |
| List<Vertex> l = adjList.get(adjList.size() - 1); | |
| for (X509Certificate cert : certs) { | |
| boolean repeated = false; | |
| for (X509Certificate cpListCert : cpList) { | |
| /* | |
| * Ignore if we encounter the same certificate or a | |
| * certificate with the same public key, subject DN, and | |
| * subjectAltNames as a cert that is already in path. | |
| */ | |
| if (repeated(cpListCert, cert)) { | |
| if (debug != null) { | |
| debug.println("cert with repeated subject, " + | |
| "public key, and subjectAltNames detected"); | |
| } | |
| repeated = true; | |
| break; | |
| } | |
| } | |
| if (!repeated) { | |
| l.add(new Vertex(cert)); | |
| } | |
| } | |
| return l; | |
| } | |
| /** | |
| * Return true if two certificates are equal or have the same subject, | |
| * public key, and subject alternative names. | |
| */ | |
| private static boolean repeated( | |
| X509Certificate currCert, X509Certificate nextCert) { | |
| if (currCert.equals(nextCert)) { | |
| return true; | |
| } | |
| return (currCert.getSubjectX500Principal().equals( | |
| nextCert.getSubjectX500Principal()) && | |
| currCert.getPublicKey().equals(nextCert.getPublicKey()) && | |
| altNamesEqual(currCert, nextCert)); | |
| } | |
| /** | |
| * Return true if two certificates have the same subject alternative names. | |
| */ | |
| private static boolean altNamesEqual( | |
| X509Certificate currCert, X509Certificate nextCert) { | |
| X509CertImpl curr, next; | |
| try { | |
| curr = X509CertImpl.toImpl(currCert); | |
| next = X509CertImpl.toImpl(nextCert); | |
| } catch (CertificateException ce) { | |
| return false; | |
| } | |
| SubjectAlternativeNameExtension currAltNameExt = | |
| curr.getSubjectAlternativeNameExtension(); | |
| SubjectAlternativeNameExtension nextAltNameExt = | |
| next.getSubjectAlternativeNameExtension(); | |
| if (currAltNameExt != null) { | |
| if (nextAltNameExt == null) { | |
| return false; | |
| } | |
| return Arrays.equals(currAltNameExt.getExtensionValue(), | |
| nextAltNameExt.getExtensionValue()); | |
| } else { | |
| return (nextAltNameExt == null); | |
| } | |
| } | |
| /** | |
| * Returns true if trust anchor certificate matches specified | |
| * certificate constraints. | |
| */ | |
| private static boolean anchorIsTarget(TrustAnchor anchor, | |
| CertSelector sel) | |
| { | |
| X509Certificate anchorCert = anchor.getTrustedCert(); | |
| if (anchorCert != null) { | |
| return sel.match(anchorCert); | |
| } | |
| return false; | |
| } | |
| } |