1 /* 2 * Copyright (c) 2000, 2015, 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.List; 39 import java.util.LinkedList; 40 import java.util.Set; 41 import javax.security.auth.x500.X500Principal; 42 43 import sun.security.provider.certpath.PKIX.BuilderParams; 44 import static sun.security.x509.PKIXExtensions.*; 45 import sun.security.util.Debug; 46 47 /** 48 * This class builds certification paths in the forward direction. 49 * 50 * <p> If successful, it returns a certification path which has successfully 51 * satisfied all the constraints and requirements specified in the 52 * PKIXBuilderParameters object and has been validated according to the PKIX 53 * path validation algorithm defined in RFC 3280. 54 * 55 * <p> This implementation uses a depth-first search approach to finding 56 * certification paths. If it comes to a point in which it cannot find 57 * any more certificates leading to the target OR the path length is too long 58 * it backtracks to previous paths until the target has been found or 59 * all possible paths have been exhausted. 60 * 61 * <p> This implementation is not thread-safe. 62 * 63 * @since 1.4 64 * @author Sean Mullan 65 * @author Yassir Elley 66 */ 67 public final class SunCertPathBuilder extends CertPathBuilderSpi { 68 69 private static final Debug debug = Debug.getInstance("certpath"); 70 71 /* 72 * private objects shared by methods 73 */ 74 private BuilderParams buildParams; 75 private CertificateFactory cf; 76 private boolean pathCompleted = false; 77 private PolicyNode policyTreeResult; 78 private TrustAnchor trustAnchor; 79 private PublicKey finalPublicKey; 80 81 /** 82 * Create an instance of <code>SunCertPathBuilder</code>. 83 * 84 * @throws CertPathBuilderException if an error occurs 85 */ SunCertPathBuilder()86 public SunCertPathBuilder() throws CertPathBuilderException { 87 try { 88 cf = CertificateFactory.getInstance("X.509"); 89 } catch (CertificateException e) { 90 throw new CertPathBuilderException(e); 91 } 92 } 93 94 @Override engineGetRevocationChecker()95 public CertPathChecker engineGetRevocationChecker() { 96 return new RevocationChecker(); 97 } 98 99 /** 100 * Attempts to build a certification path using the Sun build 101 * algorithm from a trusted anchor(s) to a target subject, which must both 102 * be specified in the input parameter set. This method will 103 * attempt to build in the forward direction: from the target to the CA. 104 * 105 * <p>The certification path that is constructed is validated 106 * according to the PKIX specification. 107 * 108 * @param params the parameter set for building a path. Must be an instance 109 * of <code>PKIXBuilderParameters</code>. 110 * @return a certification path builder result. 111 * @exception CertPathBuilderException Exception thrown if builder is 112 * unable to build a complete certification path from the trusted anchor(s) 113 * to the target subject. 114 * @throws InvalidAlgorithmParameterException if the given parameters are 115 * inappropriate for this certification path builder. 116 */ 117 @Override engineBuild(CertPathParameters params)118 public CertPathBuilderResult engineBuild(CertPathParameters params) 119 throws CertPathBuilderException, InvalidAlgorithmParameterException { 120 121 if (debug != null) { 122 debug.println("SunCertPathBuilder.engineBuild(" + params + ")"); 123 } 124 125 buildParams = PKIX.checkBuilderParams(params); 126 return build(); 127 } 128 build()129 private PKIXCertPathBuilderResult build() throws CertPathBuilderException { 130 List<List<Vertex>> adjList = new ArrayList<>(); 131 PKIXCertPathBuilderResult result = buildCertPath(false, adjList); 132 if (result == null) { 133 if (debug != null) { 134 debug.println("SunCertPathBuilder.engineBuild: 2nd pass; " + 135 "try building again searching all certstores"); 136 } 137 // try again 138 adjList.clear(); 139 result = buildCertPath(true, adjList); 140 if (result == null) { 141 throw new SunCertPathBuilderException("unable to find valid " 142 + "certification path to requested target", 143 new AdjacencyList(adjList)); 144 } 145 } 146 return result; 147 } 148 buildCertPath(boolean searchAllCertStores, List<List<Vertex>> adjList)149 private PKIXCertPathBuilderResult buildCertPath(boolean searchAllCertStores, 150 List<List<Vertex>> adjList) 151 throws CertPathBuilderException 152 { 153 // Init shared variables and build certification path 154 pathCompleted = false; 155 trustAnchor = null; 156 finalPublicKey = null; 157 policyTreeResult = null; 158 LinkedList<X509Certificate> certPathList = new LinkedList<>(); 159 try { 160 buildForward(adjList, certPathList, searchAllCertStores); 161 } catch (GeneralSecurityException | IOException e) { 162 if (debug != null) { 163 debug.println("SunCertPathBuilder.engineBuild() exception in " 164 + "build"); 165 e.printStackTrace(); 166 } 167 throw new SunCertPathBuilderException("unable to find valid " 168 + "certification path to requested target", e, 169 new AdjacencyList(adjList)); 170 } 171 172 // construct SunCertPathBuilderResult 173 try { 174 if (pathCompleted) { 175 if (debug != null) 176 debug.println("SunCertPathBuilder.engineBuild() " 177 + "pathCompleted"); 178 179 // we must return a certpath which has the target 180 // as the first cert in the certpath - i.e. reverse 181 // the certPathList 182 Collections.reverse(certPathList); 183 184 return new SunCertPathBuilderResult( 185 cf.generateCertPath(certPathList), trustAnchor, 186 policyTreeResult, finalPublicKey, 187 new AdjacencyList(adjList)); 188 } 189 } catch (CertificateException e) { 190 if (debug != null) { 191 debug.println("SunCertPathBuilder.engineBuild() exception " 192 + "in wrap-up"); 193 e.printStackTrace(); 194 } 195 throw new SunCertPathBuilderException("unable to find valid " 196 + "certification path to requested target", e, 197 new AdjacencyList(adjList)); 198 } 199 200 return null; 201 } 202 203 /* 204 * Private build forward method. 205 */ buildForward(List<List<Vertex>> adjacencyList, LinkedList<X509Certificate> certPathList, boolean searchAllCertStores)206 private void buildForward(List<List<Vertex>> adjacencyList, 207 LinkedList<X509Certificate> certPathList, 208 boolean searchAllCertStores) 209 throws GeneralSecurityException, IOException 210 { 211 if (debug != null) { 212 debug.println("SunCertPathBuilder.buildForward()..."); 213 } 214 215 /* Initialize current state */ 216 ForwardState currentState = new ForwardState(); 217 currentState.initState(buildParams.certPathCheckers()); 218 219 /* Initialize adjacency list */ 220 adjacencyList.clear(); 221 adjacencyList.add(new LinkedList<Vertex>()); 222 223 // Android-removed: Android doesn't use this mechanism for checking untrusted certificates 224 // currentState.untrustedChecker = new UntrustedChecker(); 225 226 depthFirstSearchForward(buildParams.targetSubject(), currentState, 227 new ForwardBuilder(buildParams, 228 searchAllCertStores), 229 adjacencyList, certPathList); 230 } 231 232 /* 233 * This method performs a depth first search for a certification 234 * path while building forward which meets the requirements set in 235 * the parameters object. 236 * It uses an adjacency list to store all certificates which were 237 * tried (i.e. at one time added to the path - they may not end up in 238 * the final path if backtracking occurs). This information can 239 * be used later to debug or demo the build. 240 * 241 * See "Data Structure and Algorithms, by Aho, Hopcroft, and Ullman" 242 * for an explanation of the DFS algorithm. 243 * 244 * @param dN the distinguished name being currently searched for certs 245 * @param currentState the current PKIX validation state 246 */ depthFirstSearchForward(X500Principal dN, ForwardState currentState, ForwardBuilder builder, List<List<Vertex>> adjList, LinkedList<X509Certificate> cpList)247 private void depthFirstSearchForward(X500Principal dN, 248 ForwardState currentState, 249 ForwardBuilder builder, 250 List<List<Vertex>> adjList, 251 LinkedList<X509Certificate> cpList) 252 throws GeneralSecurityException, IOException 253 { 254 if (debug != null) { 255 debug.println("SunCertPathBuilder.depthFirstSearchForward(" + dN 256 + ", " + currentState.toString() + ")"); 257 } 258 259 /* 260 * Find all the certificates issued to dN which 261 * satisfy the PKIX certification path constraints. 262 */ 263 Collection<X509Certificate> certs = 264 builder.getMatchingCerts(currentState, buildParams.certStores()); 265 List<Vertex> vertices = addVertices(certs, adjList); 266 if (debug != null) { 267 debug.println("SunCertPathBuilder.depthFirstSearchForward(): " 268 + "certs.size=" + vertices.size()); 269 } 270 271 /* 272 * For each cert in the collection, verify anything 273 * that hasn't been checked yet (signature, revocation, etc) 274 * and check for loops. Call depthFirstSearchForward() 275 * recursively for each good cert. 276 */ 277 278 vertices: 279 for (Vertex vertex : vertices) { 280 /** 281 * Restore state to currentState each time through the loop. 282 * This is important because some of the user-defined 283 * checkers modify the state, which MUST be restored if 284 * the cert eventually fails to lead to the target and 285 * the next matching cert is tried. 286 */ 287 ForwardState nextState = (ForwardState) currentState.clone(); 288 X509Certificate cert = vertex.getCertificate(); 289 290 try { 291 builder.verifyCert(cert, nextState, cpList); 292 } catch (GeneralSecurityException gse) { 293 if (debug != null) { 294 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 295 + ": validation failed: " + gse); 296 gse.printStackTrace(); 297 } 298 vertex.setThrowable(gse); 299 continue; 300 } 301 302 /* 303 * Certificate is good. 304 * If cert completes the path, 305 * process userCheckers that don't support forward checking 306 * and process policies over whole path 307 * and backtrack appropriately if there is a failure 308 * else if cert does not complete the path, 309 * add it to the path 310 */ 311 if (builder.isPathCompleted(cert)) { 312 313 if (debug != null) 314 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 315 + ": commencing final verification"); 316 317 List<X509Certificate> appendedCerts = new ArrayList<>(cpList); 318 319 /* 320 * if the trust anchor selected is specified as a trusted 321 * public key rather than a trusted cert, then verify this 322 * cert (which is signed by the trusted public key), but 323 * don't add it yet to the cpList 324 */ 325 if (builder.trustAnchor.getTrustedCert() == null) { 326 appendedCerts.add(0, cert); 327 } 328 329 Set<String> initExpPolSet = 330 Collections.singleton(PolicyChecker.ANY_POLICY); 331 332 PolicyNodeImpl rootNode = new PolicyNodeImpl(null, 333 PolicyChecker.ANY_POLICY, null, false, initExpPolSet, false); 334 335 List<PKIXCertPathChecker> checkers = new ArrayList<>(); 336 PolicyChecker policyChecker 337 = new PolicyChecker(buildParams.initialPolicies(), 338 appendedCerts.size(), 339 buildParams.explicitPolicyRequired(), 340 buildParams.policyMappingInhibited(), 341 buildParams.anyPolicyInhibited(), 342 buildParams.policyQualifiersRejected(), 343 rootNode); 344 checkers.add(policyChecker); 345 346 // add the algorithm checker 347 checkers.add(new AlgorithmChecker(builder.trustAnchor)); 348 349 BasicChecker basicChecker = null; 350 if (nextState.keyParamsNeeded()) { 351 PublicKey rootKey = cert.getPublicKey(); 352 if (builder.trustAnchor.getTrustedCert() == null) { 353 rootKey = builder.trustAnchor.getCAPublicKey(); 354 if (debug != null) 355 debug.println( 356 "SunCertPathBuilder.depthFirstSearchForward " + 357 "using buildParams public key: " + 358 rootKey.toString()); 359 } 360 TrustAnchor anchor = new TrustAnchor 361 (cert.getSubjectX500Principal(), rootKey, null); 362 363 // add the basic checker 364 basicChecker = new BasicChecker(anchor, buildParams.date(), 365 buildParams.sigProvider(), 366 true); 367 checkers.add(basicChecker); 368 } 369 370 buildParams.setCertPath(cf.generateCertPath(appendedCerts)); 371 372 boolean revCheckerAdded = false; 373 List<PKIXCertPathChecker> ckrs = buildParams.certPathCheckers(); 374 for (PKIXCertPathChecker ckr : ckrs) { 375 if (ckr instanceof PKIXRevocationChecker) { 376 if (revCheckerAdded) { 377 throw new CertPathValidatorException( 378 "Only one PKIXRevocationChecker can be specified"); 379 } 380 revCheckerAdded = true; 381 // if it's our own, initialize it 382 if (ckr instanceof RevocationChecker) { 383 ((RevocationChecker)ckr).init(builder.trustAnchor, 384 buildParams); 385 } 386 } 387 } 388 // only add a RevocationChecker if revocation is enabled and 389 // a PKIXRevocationChecker has not already been added 390 if (buildParams.revocationEnabled() && !revCheckerAdded) { 391 checkers.add(new RevocationChecker(builder.trustAnchor, 392 buildParams)); 393 } 394 395 checkers.addAll(ckrs); 396 397 // Why we don't need BasicChecker and RevocationChecker 398 // if nextState.keyParamsNeeded() is false? 399 400 for (int i = 0; i < appendedCerts.size(); i++) { 401 X509Certificate currCert = appendedCerts.get(i); 402 if (debug != null) 403 debug.println("current subject = " 404 + currCert.getSubjectX500Principal()); 405 Set<String> unresCritExts = 406 currCert.getCriticalExtensionOIDs(); 407 if (unresCritExts == null) { 408 unresCritExts = Collections.<String>emptySet(); 409 } 410 411 for (PKIXCertPathChecker currChecker : checkers) { 412 if (!currChecker.isForwardCheckingSupported()) { 413 if (i == 0) { 414 currChecker.init(false); 415 416 // The user specified 417 // AlgorithmChecker may not be 418 // able to set the trust anchor until now. 419 if (currChecker instanceof AlgorithmChecker) { 420 ((AlgorithmChecker)currChecker). 421 trySetTrustAnchor(builder.trustAnchor); 422 } 423 } 424 425 try { 426 currChecker.check(currCert, unresCritExts); 427 } catch (CertPathValidatorException cpve) { 428 if (debug != null) 429 debug.println 430 ("SunCertPathBuilder.depthFirstSearchForward(): " + 431 "final verification failed: " + cpve); 432 // If the target cert itself is revoked, we 433 // cannot trust it. We can bail out here. 434 if (buildParams.targetCertConstraints().match(currCert) 435 && cpve.getReason() == BasicReason.REVOKED) { 436 throw cpve; 437 } 438 vertex.setThrowable(cpve); 439 continue vertices; 440 } 441 } 442 } 443 444 /* 445 * Remove extensions from user checkers that support 446 * forward checking. After this step, we will have 447 * removed all extensions that all user checkers 448 * are capable of processing. 449 */ 450 for (PKIXCertPathChecker checker : 451 buildParams.certPathCheckers()) 452 { 453 if (checker.isForwardCheckingSupported()) { 454 Set<String> suppExts = 455 checker.getSupportedExtensions(); 456 if (suppExts != null) { 457 unresCritExts.removeAll(suppExts); 458 } 459 } 460 } 461 462 if (!unresCritExts.isEmpty()) { 463 unresCritExts.remove(BasicConstraints_Id.toString()); 464 unresCritExts.remove(NameConstraints_Id.toString()); 465 unresCritExts.remove(CertificatePolicies_Id.toString()); 466 unresCritExts.remove(PolicyMappings_Id.toString()); 467 unresCritExts.remove(PolicyConstraints_Id.toString()); 468 unresCritExts.remove(InhibitAnyPolicy_Id.toString()); 469 unresCritExts.remove( 470 SubjectAlternativeName_Id.toString()); 471 unresCritExts.remove(KeyUsage_Id.toString()); 472 unresCritExts.remove(ExtendedKeyUsage_Id.toString()); 473 474 if (!unresCritExts.isEmpty()) { 475 throw new CertPathValidatorException 476 ("unrecognized critical extension(s)", null, 477 null, -1, PKIXReason.UNRECOGNIZED_CRIT_EXT); 478 } 479 } 480 } 481 if (debug != null) 482 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 483 + ": final verification succeeded - path completed!"); 484 pathCompleted = true; 485 486 /* 487 * if the user specified a trusted public key rather than 488 * trusted certs, then add this cert (which is signed by 489 * the trusted public key) to the cpList 490 */ 491 if (builder.trustAnchor.getTrustedCert() == null) 492 builder.addCertToPath(cert, cpList); 493 // Save the trust anchor 494 this.trustAnchor = builder.trustAnchor; 495 496 /* 497 * Extract and save the final target public key 498 */ 499 if (basicChecker != null) { 500 finalPublicKey = basicChecker.getPublicKey(); 501 } else { 502 Certificate finalCert; 503 if (cpList.isEmpty()) { 504 finalCert = builder.trustAnchor.getTrustedCert(); 505 } else { 506 finalCert = cpList.getLast(); 507 } 508 finalPublicKey = finalCert.getPublicKey(); 509 } 510 511 policyTreeResult = policyChecker.getPolicyTree(); 512 return; 513 } else { 514 builder.addCertToPath(cert, cpList); 515 } 516 517 /* Update the PKIX state */ 518 nextState.updateState(cert); 519 520 /* 521 * Append an entry for cert in adjacency list and 522 * set index for current vertex. 523 */ 524 adjList.add(new LinkedList<Vertex>()); 525 vertex.setIndex(adjList.size() - 1); 526 527 /* recursively search for matching certs at next dN */ 528 depthFirstSearchForward(cert.getIssuerX500Principal(), nextState, 529 builder, adjList, cpList); 530 531 /* 532 * If path has been completed, return ASAP! 533 */ 534 if (pathCompleted) { 535 return; 536 } else { 537 /* 538 * If we get here, it means we have searched all possible 539 * certs issued by the dN w/o finding any matching certs. 540 * This means we have to backtrack to the previous cert in 541 * the path and try some other paths. 542 */ 543 if (debug != null) 544 debug.println("SunCertPathBuilder.depthFirstSearchForward()" 545 + ": backtracking"); 546 builder.removeFinalCertFromPath(cpList); 547 } 548 } 549 } 550 551 /* 552 * Adds a collection of matching certificates to the 553 * adjacency list. 554 */ addVertices(Collection<X509Certificate> certs, List<List<Vertex>> adjList)555 private static List<Vertex> addVertices(Collection<X509Certificate> certs, 556 List<List<Vertex>> adjList) 557 { 558 List<Vertex> l = adjList.get(adjList.size() - 1); 559 560 for (X509Certificate cert : certs) { 561 Vertex v = new Vertex(cert); 562 l.add(v); 563 } 564 565 return l; 566 } 567 568 /** 569 * Returns true if trust anchor certificate matches specified 570 * certificate constraints. 571 */ anchorIsTarget(TrustAnchor anchor, CertSelector sel)572 private static boolean anchorIsTarget(TrustAnchor anchor, 573 CertSelector sel) 574 { 575 X509Certificate anchorCert = anchor.getTrustedCert(); 576 if (anchorCert != null) { 577 return sel.match(anchorCert); 578 } 579 return false; 580 } 581 } 582