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    }