    001/*
    002 * $HeadURL: http://juliusdavies.ca/svn/not-yet-commons-ssl/tags/commons-ssl-0.3.15/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}