Back to index...

	/*
	* Copyright (c) 2000, 2017, 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(), buildParams.variant()));

	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;
	}
	}

Back to index...