1 /* 2 * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.security.provider.certpath; 27 28 import java.io.IOException; 29 import java.security.GeneralSecurityException; 30 import java.security.InvalidAlgorithmParameterException; 31 import java.security.PublicKey; 32 import java.security.cert.*; 33 import java.security.cert.CertPathValidatorException.BasicReason; 34 import java.security.cert.PKIXReason; 35 import java.util.ArrayList; 36 import java.util.Collection; 37 import java.util.Collections; 38 import java.util.HashSet; 39 import java.util.Iterator; 40 import java.util.List; 41 import java.util.LinkedList; 42 import java.util.Set; 43 import javax.security.auth.x500.X500Principal; 44 45 import sun.security.provider.certpath.PKIX.BuilderParams; 46 import static sun.security.x509.PKIXExtensions.*; 47 import sun.security.util.Debug; 48 49 /** 50 * This class is able to build certification paths in either the forward 51 * or reverse directions. 52 * 53 * <p> If successful, it returns a certification path which has successfully 54 * satisfied all the constraints and requirements specified in the 55 * PKIXBuilderParameters object and has been validated according to the PKIX 56 * path validation algorithm defined in RFC 3280. 57 * 58 * <p> This implementation uses a depth-first search approach to finding 59 * certification paths. If it comes to a point in which it cannot find 60 * any more certificates leading to the target OR the path length is too long 61 * it backtracks to previous paths until the target has been found or 62 * all possible paths have been exhausted. 63 * 64 * <p> This implementation is not thread-safe. 65 * 66 * @since 1.4 67 * @author Sean Mullan 68 * @author Yassir Elley 69 */ 70 public final class SunCertPathBuilder extends CertPathBuilderSpi { 71 72 private static final Debug debug = Debug.getInstance("certpath"); 73 74 /* 75 * private objects shared by methods 76 */ 77 private BuilderParams buildParams; 78 private CertificateFactory cf; 79 private boolean pathCompleted = false; 80 private PolicyNode policyTreeResult; 81 private TrustAnchor trustAnchor; 82 private PublicKey finalPublicKey; 83 84 /** 85 * Create an instance of <code>SunCertPathBuilder</code>. 86 * 87 * @throws CertPathBuilderException if an error occurs 88 */ 89 public SunCertPathBuilder() throws CertPathBuilderException { 90 try { 91 cf = CertificateFactory.getInstance("X.509"); 92 } catch (CertificateException e) { 93 throw new CertPathBuilderException(e); 94 } 95 } 96 97 @Override 98 public CertPathChecker engineGetRevocationChecker() { 99 return new RevocationChecker(); 100 } 101 102 /** 103 * Attempts to build a certification path using the Sun build 104 * algorithm from a trusted anchor(s) to a target subject, which must both 105 * be specified in the input parameter set. By default, this method will 106 * attempt to build in the forward direction. In order to build in the 107 * reverse direction, the caller needs to pass in an instance of 108 * SunCertPathBuilderParameters with the buildForward flag set to false. 109 * 110 * <p>The certification path that is constructed is validated 111 * according to the PKIX specification. 112 * 113 * @param params the parameter set for building a path. Must be an instance 114 * of <code>PKIXBuilderParameters</code>. 115 * @return a certification path builder result. 116 * @exception CertPathBuilderException Exception thrown if builder is 117 * unable to build a complete certification path from the trusted anchor(s) 118 * to the target subject. 119 * @throws InvalidAlgorithmParameterException if the given parameters are 120 * inappropriate for this certification path builder. 121 */ 122 @Override 123 public CertPathBuilderResult engineBuild(CertPathParameters params) 124 throws CertPathBuilderException, InvalidAlgorithmParameterException { 125 126 if (debug != null) { 127 debug.println("SunCertPathBuilder.engineBuild(" + params + ")"); 128 } 129 130 buildParams = PKIX.checkBuilderParams(params); 131 return build(); 132 } 133 134 private PKIXCertPathBuilderResult build() throws CertPathBuilderException { 135 List<List<Vertex>> adjList = new ArrayList<>(); 136 PKIXCertPathBuilderResult result = buildCertPath(false, adjList); 137 if (result == null) { 138 if (debug != null) { 139 debug.println("SunCertPathBuilder.engineBuild: 2nd pass"); 140 } 141 // try again 142 adjList.clear(); 143 result = buildCertPath(true, adjList); 144 if (result == null) { 145 throw new SunCertPathBuilderException("unable to find valid " 146 + "certification path to requested target", 147 new AdjacencyList(adjList)); 148 } 149 } 150 return result; 151 } 152 153 private PKIXCertPathBuilderResult buildCertPath(boolean searchAllCertStores, 154 List<List<Vertex>> adjList) 155 throws CertPathBuilderException 156 { 157 // Init shared variables and build certification path 158 pathCompleted = false; 159 trustAnchor = null; 160 finalPublicKey = null; 161 policyTreeResult = null; 162 LinkedList<X509Certificate> certPathList = new LinkedList<>(); 163 try { 164 if (buildParams.buildForward()) { 165 buildForward(adjList, certPathList, searchAllCertStores); 166 } else { 167 buildReverse(adjList, certPathList); 168 } 169 } catch (GeneralSecurityException | IOException e) { 170 if (debug != null) { 171 debug.println("SunCertPathBuilder.engineBuild() exception in " 172 + "build"); 173 e.printStackTrace(); 174 } 175 throw new SunCertPathBuilderException("unable to find valid " 176 + "certification path to requested target", e, 177 new AdjacencyList(adjList)); 178 } 179 180 // construct SunCertPathBuilderResult 181 try { 182 if (pathCompleted) { 183 if (debug != null) 184 debug.println("SunCertPathBuilder.engineBuild() " 185 + "pathCompleted"); 186 187 // we must return a certpath which has the target 188 // as the first cert in the certpath - i.e. reverse 189 // the certPathList 190 Collections.reverse(certPathList); 191 192 return new SunCertPathBuilderResult( 193 cf.generateCertPath(certPathList), trustAnchor, 194 policyTreeResult, finalPublicKey, 195 new AdjacencyList(adjList)); 196 } 197 } catch (CertificateException e) { 198 if (debug != null) { 199 debug.println("SunCertPathBuilder.engineBuild() exception " 200 + "in wrap-up"); 201 e.printStackTrace(); 202 } 203 throw new SunCertPathBuilderException("unable to find valid " 204 + "certification path to requested target", e, 205 new AdjacencyList(adjList)); 206 } 207 208 return null; 209 } 210 211 /* 212 * Private build reverse method. 213 */ 214 private void buildReverse(List<List<Vertex>> adjacencyList, 215 LinkedList<X509Certificate> certPathList) 216 throws GeneralSecurityException, IOException 217 { 218 if (debug != null) { 219 debug.println("SunCertPathBuilder.buildReverse()..."); 220 debug.println("SunCertPathBuilder.buildReverse() InitialPolicies: " 221 + buildParams.initialPolicies()); 222 } 223 224 ReverseState currentState = new ReverseState(); 225 /* Initialize adjacency list */ 226 adjacencyList.clear(); 227 adjacencyList.add(new LinkedList<Vertex>()); 228 229 /* 230 * Perform a search using each trust anchor, until a valid 231 * path is found 232 */ 233 Iterator<TrustAnchor> iter = buildParams.trustAnchors().iterator(); 234 while (iter.hasNext()) { 235 TrustAnchor anchor = iter.next(); 236 237 /* check if anchor satisfies target constraints */ 238 if (anchorIsTarget(anchor, buildParams.targetCertConstraints())) { 239 this.trustAnchor = anchor; 240 this.pathCompleted = true; 241 this.finalPublicKey = anchor.getTrustedCert().getPublicKey(); 242 break; 243 } 244 245 // skip anchor if it contains a DSA key with no DSA params 246 X509Certificate trustedCert = anchor.getTrustedCert(); 247 PublicKey pubKey = trustedCert != null ? trustedCert.getPublicKey() 248 : anchor.getCAPublicKey(); 249 250 if (PKIX.isDSAPublicKeyWithoutParams(pubKey)) { 251 continue; 252 } 253 254 /* Initialize current state */ 255 currentState.initState(buildParams); 256 currentState.updateState(anchor, buildParams); 257 258 currentState.algorithmChecker = new AlgorithmChecker(anchor); 259 currentState.untrustedChecker = new UntrustedChecker(); 260 try { 261 depthFirstSearchReverse(null, currentState, 262 new ReverseBuilder(buildParams), 263 adjacencyList, certPathList); 264 } catch (GeneralSecurityException | IOException e) { 265 // continue on error if more anchors to try 266 if (iter.hasNext()) 267 continue; 268 else 269 throw e; 270 } 271 272 // break out of loop if search is successful 273 if (pathCompleted) { 274 break; 275 } 276 } 277 278 if (debug != null) { 279 debug.println("SunCertPathBuilder.buildReverse() returned from " 280 + "depthFirstSearchReverse()"); 281 debug.println("SunCertPathBuilder.buildReverse() " 282 + "certPathList.size: " + certPathList.size()); 283 } 284 } 285 286 /* 287 * Private build forward method. 288 */ 289 private void buildForward(List<List<Vertex>> adjacencyList, 290 LinkedList<X509Certificate> certPathList, 291 boolean searchAllCertStores) 292 throws GeneralSecurityException, IOException 293 { 294 if (debug != null) { 295 debug.println("SunCertPathBuilder.buildForward()..."); 296 } 297 298 /* Initialize current state */ 299 ForwardState currentState = new ForwardState(); 300 currentState.initState(buildParams.certPathCheckers()); 301 302 /* Initialize adjacency list */ 303 adjacencyList.clear(); 304 adjacencyList.add(new LinkedList<Vertex>()); 305 306 currentState.untrustedChecker = new UntrustedChecker(); 307 308 depthFirstSearchForward(buildParams.targetSubject(), currentState, 309 new ForwardBuilder(buildParams, 310 searchAllCertStores), 311 adjacencyList, certPathList); 312 } 313 314 /* 315 * This method performs a depth first search for a certification 316 * path while building forward which meets the requirements set in 317 * the parameters object. 318 * It uses an adjacency list to store all certificates which were 319 * tried (i.e. at one time added to the path - they may not end up in 320 * the final path if backtracking occurs). This information can 321 * be used later to debug or demo the build. 322 * 323 * See "Data Structure and Algorithms, by Aho, Hopcroft, and Ullman" 324 * for an explanation of the DFS algorithm. 325 * 326 * @param dN the distinguished name being currently searched for certs 327 * @param currentState the current PKIX validation state 328 */ 329 private void depthFirstSearchForward(X500Principal dN, 330 ForwardState currentState, 331 ForwardBuilder builder, 332 List<List<Vertex>> adjList, 333 LinkedList<X509Certificate> cpList) 334 throws GeneralSecurityException, IOException 335 { 336 if (debug != null) { 337 debug.println("SunCertPathBuilder.depthFirstSearchForward(" + dN 338 + ", " + currentState.toString() + ")"); 339 } 340 341 /* 342 * Find all the certificates issued to dN which 343 * satisfy the PKIX certification path constraints. 344 */ 345 Collection<X509Certificate> certs = 346 builder.getMatchingCerts(currentState, buildParams.certStores()); 347 List<Vertex> vertices = addVertices(certs, adjList); 348 if (debug != null) { 349 debug.println("SunCertPathBuilder.depthFirstSearchForward(): " 350 + "certs.size=" + vertices.size()); 351 } 352 353 /* 354 * For each cert in the collection, verify anything 355 * that hasn't been checked yet (signature, revocation, etc) 356 * and check for loops. Call depthFirstSearchForward() 357 * recursively for each good cert. 358 */ 359 360 vertices: 361 for (Vertex vertex : vertices) { 362 /** 363 * Restore state to currentState each time through the loop. 364 * This is important because some of the user-defined 365 * checkers modify the state, which MUST be restored if 366 * the cert eventually fails to lead to the target and 367 * the next matching cert is tried. 368 */ 369 ForwardState nextState = (ForwardState) currentState.clone(); 370 X509Certificate cert = vertex.getCertificate(); 371 372 try { 373 builder.verifyCert(cert, nextState, cpList); 374 } catch (GeneralSecurityException gse) { 375 if (debug != null) { 376 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 377 + ": validation failed: " + gse); 378 gse.printStackTrace(); 379 } 380 vertex.setThrowable(gse); 381 continue; 382 } 383 384 /* 385 * Certificate is good. 386 * If cert completes the path, 387 * process userCheckers that don't support forward checking 388 * and process policies over whole path 389 * and backtrack appropriately if there is a failure 390 * else if cert does not complete the path, 391 * add it to the path 392 */ 393 if (builder.isPathCompleted(cert)) { 394 395 if (debug != null) 396 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 397 + ": commencing final verification"); 398 399 List<X509Certificate> appendedCerts = new ArrayList<>(cpList); 400 401 /* 402 * if the trust anchor selected is specified as a trusted 403 * public key rather than a trusted cert, then verify this 404 * cert (which is signed by the trusted public key), but 405 * don't add it yet to the cpList 406 */ 407 if (builder.trustAnchor.getTrustedCert() == null) { 408 appendedCerts.add(0, cert); 409 } 410 411 Set<String> initExpPolSet = 412 Collections.singleton(PolicyChecker.ANY_POLICY); 413 414 PolicyNodeImpl rootNode = new PolicyNodeImpl(null, 415 PolicyChecker.ANY_POLICY, null, false, initExpPolSet, false); 416 417 List<PKIXCertPathChecker> checkers = new ArrayList<>(); 418 PolicyChecker policyChecker 419 = new PolicyChecker(buildParams.initialPolicies(), 420 appendedCerts.size(), 421 buildParams.explicitPolicyRequired(), 422 buildParams.policyMappingInhibited(), 423 buildParams.anyPolicyInhibited(), 424 buildParams.policyQualifiersRejected(), 425 rootNode); 426 checkers.add(policyChecker); 427 428 // add the algorithm checker 429 checkers.add(new AlgorithmChecker(builder.trustAnchor)); 430 431 BasicChecker basicChecker = null; 432 if (nextState.keyParamsNeeded()) { 433 PublicKey rootKey = cert.getPublicKey(); 434 if (builder.trustAnchor.getTrustedCert() == null) { 435 rootKey = builder.trustAnchor.getCAPublicKey(); 436 if (debug != null) 437 debug.println( 438 "SunCertPathBuilder.depthFirstSearchForward " + 439 "using buildParams public key: " + 440 rootKey.toString()); 441 } 442 TrustAnchor anchor = new TrustAnchor 443 (cert.getSubjectX500Principal(), rootKey, null); 444 445 // add the basic checker 446 basicChecker = new BasicChecker(anchor, buildParams.date(), 447 buildParams.sigProvider(), 448 true); 449 checkers.add(basicChecker); 450 } 451 452 buildParams.setCertPath(cf.generateCertPath(appendedCerts)); 453 454 boolean revCheckerAdded = false; 455 List<PKIXCertPathChecker> ckrs = buildParams.certPathCheckers(); 456 for (PKIXCertPathChecker ckr : ckrs) { 457 if (ckr instanceof PKIXRevocationChecker) { 458 if (revCheckerAdded) { 459 throw new CertPathValidatorException( 460 "Only one PKIXRevocationChecker can be specified"); 461 } 462 revCheckerAdded = true; 463 // if it's our own, initialize it 464 if (ckr instanceof RevocationChecker) { 465 ((RevocationChecker)ckr).init(builder.trustAnchor, 466 buildParams); 467 } 468 } 469 } 470 // only add a RevocationChecker if revocation is enabled and 471 // a PKIXRevocationChecker has not already been added 472 if (buildParams.revocationEnabled() && !revCheckerAdded) { 473 checkers.add(new RevocationChecker(builder.trustAnchor, 474 buildParams)); 475 } 476 477 checkers.addAll(ckrs); 478 479 // Why we don't need BasicChecker and RevocationChecker 480 // if nextState.keyParamsNeeded() is false? 481 482 for (int i = 0; i < appendedCerts.size(); i++) { 483 X509Certificate currCert = appendedCerts.get(i); 484 if (debug != null) 485 debug.println("current subject = " 486 + currCert.getSubjectX500Principal()); 487 Set<String> unresCritExts = 488 currCert.getCriticalExtensionOIDs(); 489 if (unresCritExts == null) { 490 unresCritExts = Collections.<String>emptySet(); 491 } 492 493 for (PKIXCertPathChecker currChecker : checkers) { 494 if (!currChecker.isForwardCheckingSupported()) { 495 if (i == 0) { 496 currChecker.init(false); 497 498 // The user specified 499 // AlgorithmChecker may not be 500 // able to set the trust anchor until now. 501 if (currChecker instanceof AlgorithmChecker) { 502 ((AlgorithmChecker)currChecker). 503 trySetTrustAnchor(builder.trustAnchor); 504 } 505 } 506 507 try { 508 currChecker.check(currCert, unresCritExts); 509 } catch (CertPathValidatorException cpve) { 510 if (debug != null) 511 debug.println 512 ("SunCertPathBuilder.depthFirstSearchForward(): " + 513 "final verification failed: " + cpve); 514 // If the target cert itself is revoked, we 515 // cannot trust it. We can bail out here. 516 if (buildParams.targetCertConstraints().match(currCert) 517 && cpve.getReason() == BasicReason.REVOKED) { 518 throw cpve; 519 } 520 vertex.setThrowable(cpve); 521 continue vertices; 522 } 523 } 524 } 525 526 /* 527 * Remove extensions from user checkers that support 528 * forward checking. After this step, we will have 529 * removed all extensions that all user checkers 530 * are capable of processing. 531 */ 532 for (PKIXCertPathChecker checker : 533 buildParams.certPathCheckers()) 534 { 535 if (checker.isForwardCheckingSupported()) { 536 Set<String> suppExts = 537 checker.getSupportedExtensions(); 538 if (suppExts != null) { 539 unresCritExts.removeAll(suppExts); 540 } 541 } 542 } 543 544 if (!unresCritExts.isEmpty()) { 545 unresCritExts.remove(BasicConstraints_Id.toString()); 546 unresCritExts.remove(NameConstraints_Id.toString()); 547 unresCritExts.remove(CertificatePolicies_Id.toString()); 548 unresCritExts.remove(PolicyMappings_Id.toString()); 549 unresCritExts.remove(PolicyConstraints_Id.toString()); 550 unresCritExts.remove(InhibitAnyPolicy_Id.toString()); 551 unresCritExts.remove( 552 SubjectAlternativeName_Id.toString()); 553 unresCritExts.remove(KeyUsage_Id.toString()); 554 unresCritExts.remove(ExtendedKeyUsage_Id.toString()); 555 556 if (!unresCritExts.isEmpty()) { 557 throw new CertPathValidatorException 558 ("unrecognized critical extension(s)", null, 559 null, -1, PKIXReason.UNRECOGNIZED_CRIT_EXT); 560 } 561 } 562 } 563 if (debug != null) 564 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 565 + ": final verification succeeded - path completed!"); 566 pathCompleted = true; 567 568 /* 569 * if the user specified a trusted public key rather than 570 * trusted certs, then add this cert (which is signed by 571 * the trusted public key) to the cpList 572 */ 573 if (builder.trustAnchor.getTrustedCert() == null) 574 builder.addCertToPath(cert, cpList); 575 // Save the trust anchor 576 this.trustAnchor = builder.trustAnchor; 577 578 /* 579 * Extract and save the final target public key 580 */ 581 if (basicChecker != null) { 582 finalPublicKey = basicChecker.getPublicKey(); 583 } else { 584 Certificate finalCert; 585 if (cpList.isEmpty()) { 586 finalCert = builder.trustAnchor.getTrustedCert(); 587 } else { 588 finalCert = cpList.getLast(); 589 } 590 finalPublicKey = finalCert.getPublicKey(); 591 } 592 593 policyTreeResult = policyChecker.getPolicyTree(); 594 return; 595 } else { 596 builder.addCertToPath(cert, cpList); 597 } 598 599 /* Update the PKIX state */ 600 nextState.updateState(cert); 601 602 /* 603 * Append an entry for cert in adjacency list and 604 * set index for current vertex. 605 */ 606 adjList.add(new LinkedList<Vertex>()); 607 vertex.setIndex(adjList.size() - 1); 608 609 /* recursively search for matching certs at next dN */ 610 depthFirstSearchForward(cert.getIssuerX500Principal(), nextState, 611 builder, adjList, cpList); 612 613 /* 614 * If path has been completed, return ASAP! 615 */ 616 if (pathCompleted) { 617 return; 618 } else { 619 /* 620 * If we get here, it means we have searched all possible 621 * certs issued by the dN w/o finding any matching certs. 622 * This means we have to backtrack to the previous cert in 623 * the path and try some other paths. 624 */ 625 if (debug != null) 626 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 627 + ": backtracking"); 628 builder.removeFinalCertFromPath(cpList); 629 } 630 } 631 } 632 633 /* 634 * This method performs a depth first search for a certification 635 * path while building reverse which meets the requirements set in 636 * the parameters object. 637 * It uses an adjacency list to store all certificates which were 638 * tried (i.e. at one time added to the path - they may not end up in 639 * the final path if backtracking occurs). This information can 640 * be used later to debug or demo the build. 641 * 642 * See "Data Structure and Algorithms, by Aho, Hopcroft, and Ullman" 643 * for an explanation of the DFS algorithm. 644 * 645 * @param dN the distinguished name being currently searched for certs 646 * @param currentState the current PKIX validation state 647 */ 648 private void depthFirstSearchReverse(X500Principal dN, 649 ReverseState currentState, 650 ReverseBuilder builder, 651 List<List<Vertex>> adjList, 652 LinkedList<X509Certificate> cpList) 653 throws GeneralSecurityException, IOException 654 { 655 if (debug != null) 656 debug.println("SunCertPathBuilder.depthFirstSearchReverse(" + dN 657 + ", " + currentState.toString() + ")"); 658 659 /* 660 * Find all the certificates issued by dN which 661 * satisfy the PKIX certification path constraints. 662 */ 663 Collection<X509Certificate> certs = 664 builder.getMatchingCerts(currentState, buildParams.certStores()); 665 List<Vertex> vertices = addVertices(certs, adjList); 666 if (debug != null) 667 debug.println("SunCertPathBuilder.depthFirstSearchReverse(): " 668 + "certs.size=" + vertices.size()); 669 670 /* 671 * For each cert in the collection, verify anything 672 * that hasn't been checked yet (signature, revocation, etc) 673 * and check for loops. Call depthFirstSearchReverse() 674 * recursively for each good cert. 675 */ 676 for (Vertex vertex : vertices) { 677 /** 678 * Restore state to currentState each time through the loop. 679 * This is important because some of the user-defined 680 * checkers modify the state, which MUST be restored if 681 * the cert eventually fails to lead to the target and 682 * the next matching cert is tried. 683 */ 684 ReverseState nextState = (ReverseState) currentState.clone(); 685 X509Certificate cert = vertex.getCertificate(); 686 try { 687 builder.verifyCert(cert, nextState, cpList); 688 } catch (GeneralSecurityException gse) { 689 if (debug != null) 690 debug.println("SunCertPathBuilder.depthFirstSearchReverse()" 691 + ": validation failed: " + gse); 692 vertex.setThrowable(gse); 693 continue; 694 } 695 696 /* 697 * Certificate is good, add it to the path (if it isn't a 698 * self-signed cert) and update state 699 */ 700 if (!currentState.isInitial()) 701 builder.addCertToPath(cert, cpList); 702 // save trust anchor 703 this.trustAnchor = currentState.trustAnchor; 704 705 /* 706 * Check if path is completed, return ASAP if so. 707 */ 708 if (builder.isPathCompleted(cert)) { 709 if (debug != null) 710 debug.println("SunCertPathBuilder.depthFirstSearchReverse()" 711 + ": path completed!"); 712 pathCompleted = true; 713 714 PolicyNodeImpl rootNode = nextState.rootNode; 715 716 if (rootNode == null) 717 policyTreeResult = null; 718 else { 719 policyTreeResult = rootNode.copyTree(); 720 ((PolicyNodeImpl)policyTreeResult).setImmutable(); 721 } 722 723 /* 724 * Extract and save the final target public key 725 */ 726 finalPublicKey = cert.getPublicKey(); 727 if (PKIX.isDSAPublicKeyWithoutParams(finalPublicKey)) { 728 finalPublicKey = 729 BasicChecker.makeInheritedParamsKey 730 (finalPublicKey, currentState.pubKey); 731 } 732 733 return; 734 } 735 736 /* Update the PKIX state */ 737 nextState.updateState(cert); 738 739 /* 740 * Append an entry for cert in adjacency list and 741 * set index for current vertex. 742 */ 743 adjList.add(new LinkedList<Vertex>()); 744 vertex.setIndex(adjList.size() - 1); 745 746 /* recursively search for matching certs at next dN */ 747 depthFirstSearchReverse(cert.getSubjectX500Principal(), nextState, 748 builder, adjList, cpList); 749 750 /* 751 * If path has been completed, return ASAP! 752 */ 753 if (pathCompleted) { 754 return; 755 } else { 756 /* 757 * If we get here, it means we have searched all possible 758 * certs issued by the dN w/o finding any matching certs. This 759 * means we have to backtrack to the previous cert in the path 760 * and try some other paths. 761 */ 762 if (debug != null) 763 debug.println("SunCertPathBuilder.depthFirstSearchReverse()" 764 + ": backtracking"); 765 if (!currentState.isInitial()) 766 builder.removeFinalCertFromPath(cpList); 767 } 768 } 769 if (debug != null) 770 debug.println("SunCertPathBuilder.depthFirstSearchReverse() all " 771 + "certs in this adjacency list checked"); 772 } 773 774 /* 775 * Adds a collection of matching certificates to the 776 * adjacency list. 777 */ 778 private static List<Vertex> addVertices(Collection<X509Certificate> certs, 779 List<List<Vertex>> adjList) 780 { 781 List<Vertex> l = adjList.get(adjList.size() - 1); 782 783 for (X509Certificate cert : certs) { 784 Vertex v = new Vertex(cert); 785 l.add(v); 786 } 787 788 return l; 789 } 790 791 /** 792 * Returns true if trust anchor certificate matches specified 793 * certificate constraints. 794 */ 795 private static boolean anchorIsTarget(TrustAnchor anchor, 796 CertSelector sel) 797 { 798 X509Certificate anchorCert = anchor.getTrustedCert(); 799 if (anchorCert != null) { 800 return sel.match(anchorCert); 801 } 802 return false; 803 } 804 } 805
