001 /*
002 * $HeadURL: http://juliusdavies.ca/svn/not-yet-commons-ssl/tags/commons-ssl-0.3.11/src/java/org/apache/commons/ssl/X509CertificateChainBuilder.java $
003 * $Revision: 134 $
004 * $Date: 2008-02-26 21:30:48 -0800 (Tue, 26 Feb 2008) $
005 *
006 * ====================================================================
007 * Licensed to the Apache Software Foundation (ASF) under one
008 * or more contributor license agreements. See the NOTICE file
009 * distributed with this work for additional information
010 * regarding copyright ownership. The ASF licenses this file
011 * to you under the Apache License, Version 2.0 (the
012 * "License"); you may not use this file except in compliance
013 * with the License. You may obtain a copy of the License at
014 *
015 * http://www.apache.org/licenses/LICENSE-2.0
016 *
017 * Unless required by applicable law or agreed to in writing,
018 * software distributed under the License is distributed on an
019 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
020 * KIND, either express or implied. See the License for the
021 * specific language governing permissions and limitations
022 * under the License.
023 * ====================================================================
024 *
025 * This software consists of voluntary contributions made by many
026 * individuals on behalf of the Apache Software Foundation. For more
027 * information on the Apache Software Foundation, please see
028 * <http://www.apache.org/>.
029 *
030 */
031
032 package org.apache.commons.ssl;
033
034 import java.io.FileInputStream;
035 import java.security.InvalidKeyException;
036 import java.security.NoSuchAlgorithmException;
037 import java.security.NoSuchProviderException;
038 import java.security.PublicKey;
039 import java.security.SignatureException;
040 import java.security.cert.Certificate;
041 import java.security.cert.CertificateException;
042 import java.security.cert.CertificateFactory;
043 import java.security.cert.X509Certificate;
044 import java.util.Arrays;
045 import java.util.Collection;
046 import java.util.Iterator;
047 import java.util.LinkedList;
048
049 /**
050 * Utility for building X509 certificate chains.
051 *
052 * @author Credit Union Central of British Columbia
053 * @author <a href="http://www.cucbc.com/">www.cucbc.com</a>
054 * @author <a href="mailto:juliusdavies@cucbc.com">juliusdavies@cucbc.com</a>
055 * @since 16-Nov-2005
056 */
057 public class X509CertificateChainBuilder {
058 /**
059 * Builds the ordered certificate chain upwards from the startingPoint.
060 * Uses the supplied X509Certificate[] array to search for the parent,
061 * grandparent, and higher ancestor certificates. Stops at self-signed
062 * certificates, or when no ancestor can be found.
063 * <p/>
064 * Thanks to Joe Whitney for helping me put together a Big-O( m * n )
065 * implementation where m = the length of the final certificate chain.
066 * For a while I was using a Big-O( n ^ 2 ) implementation!
067 *
068 * @param startingPoint the X509Certificate for which we want to find
069 * ancestors
070 * @param certificates A pool of certificates in which we expect to find
071 * the startingPoint's ancestors.
072 * @return Array of X509Certificates, starting with the "startingPoint" and
073 * ending with highest level ancestor we could find in the supplied
074 * collection.
075 * @throws java.security.NoSuchAlgorithmException
076 * on unsupported signature
077 * algorithms.
078 * @throws java.security.InvalidKeyException
079 * on incorrect key.
080 * @throws java.security.NoSuchProviderException
081 * if there's no default provider.
082 * @throws java.security.cert.CertificateException
083 * on encoding errors.
084 */
085 public static X509Certificate[] buildPath(X509Certificate startingPoint,
086 Certificate[] certificates)
087 throws NoSuchAlgorithmException, InvalidKeyException,
088 NoSuchProviderException, CertificateException {
089 // Use a LinkedList, because we do lots of random it.remove() operations.
090 return buildPath(startingPoint,
091 new LinkedList(Arrays.asList(certificates)));
092 }
093
094 /**
095 * Builds the ordered certificate chain upwards from the startingPoint.
096 * Uses the supplied collection to search for the parent, grandparent,
097 * and higher ancestor certificates. Stops at self-signed certificates,
098 * or when no ancestor can be found.
099 * <p/>
100 * Thanks to Joe Whitney for helping me put together a Big-O( m * n )
101 * implementation where m = the length of the final certificate chain.
102 * For a while I was using a Big-O( n ^ 2 ) implementation!
103 *
104 * @param startingPoint the X509Certificate for which we want to find
105 * ancestors
106 * @param certificates A pool of certificates in which we expect to find
107 * the startingPoint's ancestors.
108 * @return Array of X509Certificates, starting with the "startingPoint" and
109 * ending with highest level ancestor we could find in the supplied
110 * collection.
111 * @throws java.security.NoSuchAlgorithmException
112 * on unsupported signature
113 * algorithms.
114 * @throws java.security.InvalidKeyException
115 * on incorrect key.
116 * @throws java.security.NoSuchProviderException
117 * if there's no default provider.
118 * @throws java.security.cert.CertificateException
119 * on encoding errors.
120 */
121 public static X509Certificate[] buildPath(X509Certificate startingPoint,
122 Collection certificates)
123 throws NoSuchAlgorithmException, InvalidKeyException,
124 NoSuchProviderException, CertificateException {
125 LinkedList path = new LinkedList();
126 path.add(startingPoint);
127 boolean nodeAdded = true;
128 // Keep looping until an iteration happens where we don't add any nodes
129 // to our path.
130 while (nodeAdded) {
131 // We'll start out by assuming nothing gets added. If something
132 // gets added, then nodeAdded will be changed to "true".
133 nodeAdded = false;
134 X509Certificate top = (X509Certificate) path.getLast();
135 if (isSelfSigned(top)) {
136 // We're self-signed, so we're done!
137 break;
138 }
139
140 // Not self-signed. Let's see if we're signed by anyone in the
141 // collection.
142 Iterator it = certificates.iterator();
143 while (it.hasNext()) {
144 X509Certificate x509 = (X509Certificate) it.next();
145 if (verify(top, x509.getPublicKey())) {
146 // We're signed by this guy! Add him to the chain we're
147 // building up.
148 path.add(x509);
149 nodeAdded = true;
150 it.remove(); // Not interested in this guy anymore!
151 break;
152 }
153 // Not signed by this guy, let's try the next guy.
154 }
155 }
156 X509Certificate[] results = new X509Certificate[path.size()];
157 path.toArray(results);
158 return results;
159 }
160
161 public static boolean isSelfSigned(X509Certificate cert)
162 throws CertificateException, InvalidKeyException,
163 NoSuchAlgorithmException, NoSuchProviderException {
164
165 return verify(cert, cert.getPublicKey());
166 }
167
168 public static boolean verify(X509Certificate cert, PublicKey key)
169 throws CertificateException, InvalidKeyException,
170 NoSuchAlgorithmException, NoSuchProviderException {
171
172 String sigAlg = cert.getSigAlgName();
173 String keyAlg = key.getAlgorithm();
174 sigAlg = sigAlg != null ? sigAlg.trim().toUpperCase() : "";
175 keyAlg = keyAlg != null ? keyAlg.trim().toUpperCase() : "";
176 if (keyAlg.length() >= 2 && sigAlg.endsWith(keyAlg)) {
177 try {
178 cert.verify(key);
179 return true;
180 } catch (SignatureException se) {
181 return false;
182 }
183 } else {
184 return false;
185 }
186 }
187
188 public static void main(String[] args) throws Exception {
189 if (args.length < 2) {
190 System.out.println("Usage: [special-one] [file-with-certs]");
191 System.exit(1);
192 }
193 FileInputStream f1 = new FileInputStream(args[0]);
194 FileInputStream f2 = new FileInputStream(args[1]);
195 CertificateFactory cf = CertificateFactory.getInstance("X.509");
196 X509Certificate theOne = (X509Certificate) cf.generateCertificate(f1);
197 Collection c = cf.generateCertificates(f2);
198
199 X509Certificate[] path = buildPath(theOne, c);
200 for (int i = 0; i < path.length; i++) {
201 System.out.println(Certificates.getCN(path[i]));
202 }
203 }
204 }