| /* |
| * Copyright (c) 2000, 2015, 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.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.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 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 (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) { |
| 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<Vertex>()); |
| |
| 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); |
| 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 loops. 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 of the 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 |
| */ |
| if (builder.trustAnchor.getTrustedCert() == null) { |
| appendedCerts.add(0, cert); |
| } |
| |
| Set<String> initExpPolSet = |
| Collections.singleton(PolicyChecker.ANY_POLICY); |
| |
| PolicyNodeImpl rootNode = new PolicyNodeImpl(null, |
| PolicyChecker.ANY_POLICY, null, false, initExpPolSet, false); |
| |
| List<PKIXCertPathChecker> checkers = new ArrayList<>(); |
| PolicyChecker policyChecker |
| = new PolicyChecker(buildParams.initialPolicies(), |
| appendedCerts.size(), |
| buildParams.explicitPolicyRequired(), |
| buildParams.policyMappingInhibited(), |
| buildParams.anyPolicyInhibited(), |
| buildParams.policyQualifiersRejected(), |
| rootNode); |
| checkers.add(policyChecker); |
| |
| // add the algorithm checker |
| checkers.add(new AlgorithmChecker(builder.trustAnchor, |
| buildParams.date())); |
| |
| BasicChecker basicChecker = null; |
| if (nextState.keyParamsNeeded()) { |
| PublicKey rootKey = cert.getPublicKey(); |
| if (builder.trustAnchor.getTrustedCert() == null) { |
| 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 |
| basicChecker = new BasicChecker(anchor, buildParams.date(), |
| buildParams.sigProvider(), |
| true); |
| checkers.add(basicChecker); |
| } |
| |
| 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.<String>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 { |
| 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>()); |
| 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<Vertex> l = adjList.get(adjList.size() - 1); |
| |
| for (X509Certificate cert : certs) { |
| Vertex v = new Vertex(cert); |
| l.add(v); |
| } |
| |
| return l; |
| } |
| |
| /** |
| * 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; |
| } |
| } |
