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
032package org.apache.commons.ssl;
033
034import java.io.FileInputStream;
035import java.security.InvalidKeyException;
036import java.security.NoSuchAlgorithmException;
037import java.security.NoSuchProviderException;
038import java.security.PublicKey;
039import java.security.SignatureException;
040import java.security.cert.Certificate;
041import java.security.cert.CertificateException;
042import java.security.cert.CertificateFactory;
043import java.security.cert.X509Certificate;
044import java.util.Arrays;
045import java.util.Collection;
046import java.util.Iterator;
047import 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 */
057public 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}