DNChainMatching


1   /*******************************************************************************
2    * Copyright (c) 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    * 
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.osgi.internal.verifier;
12  
13  import java.util.ArrayList  ;
14  import javax.security.auth.x500.X500Principal  ;
15  
16  /**
17   * This class contains a method to match a distinguished name (DN) chain against
18   * and DN chain pattern.
19   * <p>
20   * The format of DNs are given in RFC 2253. We represent a signature chain for
21   * an X.509 certificate as a semicolon separated list of DNs. This is what we
22   * refer to as the DN chain. Each DN is made up of relative distinguished names
23   * (RDN) which in turn are made up of key value pairs. For example:
24   * 
25   * <pre>
26   * 
27   *  
28   *   cn=ben+ou=research,o=ACME,c=us;ou=Super CA,c=CA
29   *   
30   *  
31   * </pre>
32   * 
33   * is made up of two DNs: "<code>cn=ben+ou=research,o=ACME,c=us</code>" and "
34   * <code>ou=Super CA,c=CA</code>". The first DN is made of of three RDNs: "
35   * <code>cn=ben+ou=research</code>" and "<code>o=ACME</code>" and "
36   * <code>c=us</code>". The first RDN has two name value pairs: "
37   * <code>cn=ben</code>" and "<code>ou=research</code>".
38   * <p>
39   * A chain pattern makes use of wildcards ('*') to match against DNs, DN
40   * prefixes, and value. If a DN in a DN chain is made up of a wildcard ("*"),
41   * that wildcard will match zero or more DNs in the chain. If the first RDN of a
42   * DN is the wildcard, that DN will match any other DN with the same suffix (the
43   * DN with the wildcard RDN removed). If a value of a name/value pair is a
44   * wildcard, the value will match any value for that name.
45   */
46  public class DNChainMatching {
47      /**
48       * Check the name/value pairs of the rdn against the pattern.
49       * 
50       * @param rdn ArrayList of name value pairs for a given RDN.
51       * @param rdnPattern ArrayList of name value pattern pairs.
52       * @return true if the list of name value pairs match the pattern.
53       */
54      private static boolean rdnmatch(ArrayList   rdn, ArrayList   rdnPattern) {
55          if (rdn.size() != rdnPattern.size())
56              return false;
57          for (int i = 0; i < rdn.size(); i++) {
58              String   rdnNameValue = (String  ) rdn.get(i);
59              String   patNameValue = (String  ) rdnPattern.get(i);
60              int rdnNameEnd = rdnNameValue.indexOf('=');
61              int patNameEnd = patNameValue.indexOf('=');
62              if (rdnNameEnd != patNameEnd || !rdnNameValue.regionMatches(0, patNameValue, 0, rdnNameEnd)) {
63                  return false;
64              }
65              String   patValue = patNameValue.substring(patNameEnd);
66              String   rdnValue = rdnNameValue.substring(rdnNameEnd);
67              if (!rdnValue.equals(patValue) && !patValue.equals("=*") && !patValue.equals("=#16012a")) { //$NON-NLS-1$ //$NON-NLS-2$
68                  return false;
69              }
70          }
71          return true;
72      }
73  
74      private static boolean dnmatch(ArrayList   dn, ArrayList   dnPattern) {
75          int dnStart = 0;
76          int patStart = 0;
77          int patLen = dnPattern.size();
78          if (patLen == 0) {
79              return false;
80          }
81          if (dnPattern.get(0).equals("*")) { //$NON-NLS-1$
82              patStart = 1;
83              patLen--;
84          }
85          if (dn.size() < patLen) {
86              return false;
87          } else if (dn.size() > patLen) {
88              if (!dnPattern.get(0).equals("*")) { //$NON-NLS-1$
89                  // If the number of rdns do not match we must have a prefix map
90                  return false;
91              }
92              // The rdnPattern and rdn must have the same number of elements
93              dnStart = dn.size() - patLen;
94          }
95          for (int i = 0; i < patLen; i++) {
96              if (!rdnmatch((ArrayList  ) dn.get(i + dnStart), (ArrayList  ) dnPattern.get(i + patStart))) {
97                  return false;
98              }
99          }
100         return true;
101     }
102 
103     /**
104      * Parses a distinguished name chain and returns an ArrayList where each
105      * element represents a distinguished name (DN) in the chain of DNs. Each
106      * element will be either a String, if the element represents a wildcard
107      * ("*"), or an ArrayList representing an RDN. Each element in the RDN
108      * ArrayList will be a String, if the element represents a wildcard ("*"),
109      * or an ArrayList of Strings, each String representing a name/value pair in
110      * the RDN.
111      * 
112      * @param dnChain
113      * @return a list of DNs.
114      * @throws IllegalArgumentException
115      */
116     private static ArrayList   parseDNchain(String   dnChain) throws IllegalArgumentException   {
117         ArrayList   parsed = new ArrayList  ();
118         int startIndex = 0;
119         startIndex = skipSpaces(dnChain, startIndex);
120         while (startIndex < dnChain.length()) {
121             int endIndex = startIndex;
122             boolean inQuote = false;
123             out: while (endIndex < dnChain.length()) {
124                 char c = dnChain.charAt(endIndex);
125                 switch (c) {
126                     case '"' :
127                         inQuote = !inQuote;
128                         break;
129                     case '\\' :
130                         endIndex++; // skip the escaped char
131                         break;
132                     case ';' :
133                         if (!inQuote)
134                             break out;
135                 }
136                 endIndex++;
137             }
138             if (endIndex > dnChain.length()) {
139                 throw new IllegalArgumentException  ("unterminated escape"); //$NON-NLS-1$
140             }
141             parsed.add(dnChain.substring(startIndex, endIndex));
142             startIndex = endIndex + 1;
143             startIndex = skipSpaces(dnChain, startIndex);
144         }
145         // Now we parse is a list of strings, lets make ArrayList of rdn out of
146         // them
147         for (int i = 0; i < parsed.size(); i++) {
148             String   dn = (String  ) parsed.get(i);
149             if (dn.equals("*")) //$NON-NLS-1$
150                 continue;
151             ArrayList   rdns = new ArrayList  ();
152             if (dn.charAt(0) == '*') {
153                 if (dn.charAt(1) != ',')
154                     throw new IllegalArgumentException  ("invalid wildcard prefix"); //$NON-NLS-1$
155                 rdns.add("*"); //$NON-NLS-1$
156                 dn = new X500Principal  (dn.substring(2)).getName(X500Principal.CANONICAL);
157             } else {
158                 dn = new X500Principal  (dn).getName(X500Principal.CANONICAL);
159             }
160             // Now dn is a nice CANONICAL DN
161             parseDN(dn, rdns);
162             parsed.set(i, rdns);
163         }
164         if (parsed.size() == 0) {
165             throw new IllegalArgumentException  ("empty DN chain"); //$NON-NLS-1$
166         }
167         return parsed;
168     }
169 
170     /**
171      * Increment startIndex until the end of dnChain is hit or until it is the
172      * index of a non-space character.
173      */
174     private static int skipSpaces(String   dnChain, int startIndex) {
175         while (startIndex < dnChain.length() && dnChain.charAt(startIndex) == ' ')
176             startIndex++;
177         return startIndex;
178     }
179 
180     /**
181      * Takes a distinguished name in canonical form and fills in the rdnArray
182      * with the extracted RDNs.
183      * 
184      * @param dn the distinguished name in canonical form.
185      * @param rdnArray the array to fill in with RDNs extracted from the dn
186      * @throws IllegalArgumentException if a formatting error is found.
187      */
188     private static void parseDN(String   dn, ArrayList   rdnArray) throws IllegalArgumentException   {
189         int startIndex = 0;
190         char c = '\0';
191         ArrayList   nameValues = new ArrayList  ();
192         while (startIndex < dn.length()) {
193             int endIndex;
194             for (endIndex = startIndex; endIndex < dn.length(); endIndex++) {
195                 c = dn.charAt(endIndex);
196                 if (c == ',' || c == '+')
197                     break;
198                 if (c == '\\') {
199                     endIndex++; // skip the escaped char
200                 }
201             }
202             if (endIndex > dn.length())
203                 throw new IllegalArgumentException  ("unterminated escape " + dn); //$NON-NLS-1$
204             nameValues.add(dn.substring(startIndex, endIndex));
205             if (c != '+') {
206                 rdnArray.add(nameValues);
207                 if (endIndex != dn.length())
208                     nameValues = new ArrayList  ();
209                 else
210                     nameValues = null;
211             }
212             startIndex = endIndex + 1;
213         }
214         if (nameValues != null) {
215             throw new IllegalArgumentException  ("improperly terminated DN " + dn); //$NON-NLS-1$
216         }
217     }
218 
219     /**
220      * This method will return an 'index' which points to a non-wild-card DN or
221      * the end-of-arraylist.
222      */
223     private static int skipWildCards(ArrayList   dnChainPattern, int dnChainPatternIndex) throws IllegalArgumentException   {
224         int i;
225         for (i = dnChainPatternIndex; i < dnChainPattern.size(); i++) {
226             Object   dnPattern = dnChainPattern.get(i);
227             if (dnPattern instanceof String  ) {
228                 if (!dnPattern.equals("*")) { //$NON-NLS-1$
229                     throw new IllegalArgumentException  ("expected wild-card in DN pattern"); //$NON-NLS-1$
230                 }
231                 // otherwise continue skipping over wild cards
232             } else if (dnPattern instanceof ArrayList  ) {
233                 // if its an arraylist then we have our 'non-wild-card' DN
234                 break;
235             } else {
236                 // unknown member of the DNChainPattern
237                 throw new IllegalArgumentException  ("expected String or Arraylist in DN Pattern"); //$NON-NLS-1$
238             }
239         }
240         // i either points to end-of-arraylist, or to the first non-wild-card
241         // pattern
242         // after dnChainPatternIndex
243         return i;
244     }
245 
246     /**
247      * recursively attempt to match the DNChain, and the DNChainPattern where
248      * DNChain is of the format: "DN;DN;DN;" and DNChainPattern is of the
249      * format: "DNPattern;*;DNPattern" (or combinations of this)
250      */
251     private static boolean dnChainMatch(ArrayList   dnChain, int dnChainIndex, ArrayList   dnChainPattern, int dnChainPatternIndex) throws IllegalArgumentException   {
252         if (dnChainIndex >= dnChain.size()) {
253             return false;
254         }
255         if (dnChainPatternIndex >= dnChainPattern.size()) {
256             return false;
257         }
258         // check to see what the pattern starts with
259         Object   dnPattern = dnChainPattern.get(dnChainPatternIndex);
260         if (dnPattern instanceof String  ) {
261             if (!dnPattern.equals("*")) { //$NON-NLS-1$
262                 throw new IllegalArgumentException  ("expected wild-card in DN pattern"); //$NON-NLS-1$
263             }
264             // here we are processing a wild card as the first DN
265             // skip all wild-card DN's
266             dnChainPatternIndex = skipWildCards(dnChainPattern, dnChainPatternIndex);
267             if (dnChainPatternIndex >= dnChainPattern.size()) {
268                 // the entire DNChainPattern was wild-cards, so we have a match
269                 return true;
270             }
271             //
272             // we will now recursively call to see if the rest of the
273             // DNChainPattern
274             // matches increasingly smaller portions of the rest of the DNChain
275             //
276             for (int i = dnChainIndex; i < dnChain.size(); i++) {
277                 if (dnChainMatch(dnChain, i, dnChainPattern, dnChainPatternIndex)) {
278                     return true;
279                 }
280             }
281             // if we are here, then we didn't find a match.. fall through to
282             // failure
283         } else if (dnPattern instanceof ArrayList  ) {
284             // here we have to do a deeper check for each DN in the pattern
285             // until we hit a wild card
286             do {
287                 if (!dnmatch((ArrayList  ) dnChain.get(dnChainIndex), (ArrayList  ) dnPattern)) {
288                     return false;
289                 }
290                 // go to the next set of DN's in both chains
291                 dnChainIndex++;
292                 dnChainPatternIndex++;
293                 // if we finished the pattern then it all matched
294                 if ((dnChainIndex >= dnChain.size()) && (dnChainPatternIndex >= dnChainPattern.size())) {
295                     return true;
296                 }
297                 // if the DN Chain is finished, but the pattern isn't finished
298                 // then if the rest of the pattern is not wildcard then we are
299                 // done
300                 if (dnChainIndex >= dnChain.size()) {
301                     dnChainPatternIndex = skipWildCards(dnChainPattern, dnChainPatternIndex);
302                     // return TRUE iff the pattern index moved past the
303                     // array-size
304                     // (implying that the rest of the pattern is all wild-cards)
305                     return (dnChainPatternIndex >= dnChainPattern.size());
306                 }
307                 // if the pattern finished, but the chain continues then we have
308                 // a mis-match
309                 if (dnChainPatternIndex >= dnChainPattern.size()) {
310                     return false;
311                 }
312                 // get the next DN Pattern
313                 dnPattern = dnChainPattern.get(dnChainPatternIndex);
314                 if (dnPattern instanceof String  ) {
315                     if (!dnPattern.equals("*")) { //$NON-NLS-1$
316                         throw new IllegalArgumentException  ("expected wild-card in DN pattern"); //$NON-NLS-1$
317                     }
318                     // if the next DN is a 'wild-card', then we will recurse
319                     return dnChainMatch(dnChain, dnChainIndex, dnChainPattern, dnChainPatternIndex);
320                 } else if (!(dnPattern instanceof ArrayList  )) {
321                     throw new IllegalArgumentException  ("expected String or Arraylist in DN Pattern"); //$NON-NLS-1$
322                 }
323                 // if we are here, then we will just continue to the match the
324                 // next set of DN's from the DNChain, and the DNChainPattern
325                 // since both are array-lists
326             } while (true);
327             // should never reach here?
328         } else {
329             throw new IllegalArgumentException  ("expected String or Arraylist in DN Pattern"); //$NON-NLS-1$
330         }
331         // if we get here, the the default return is 'mis-match'
332         return false;
333     }
334 
335     /**
336      * Matches a distinguished name chain against a pattern of a distinguished
337      * name chain.
338      * 
339      * @param dnChain
340      * @param pattern the pattern of distinguished name (DN) chains to match
341      *        against the dnChain. Wildcards "*" can be used in three cases:
342      *        <ol>
343      *        <li>As a DN. In this case, the DN will consist of just the "*".
344      *        It will match zero or more DNs. For example, "cn=me,c=US;*;cn=you"
345      *        will match "cn=me,c=US";cn=you" and
346      *        "cn=me,c=US;cn=her,c=CA;cn=you".
347      *        <li>As a DN prefix. In this case, the DN must start with "*,".
348      *        The wild card will match zero or more RDNs at the start of a DN.
349      *        For example, "*,cn=me,c=US;cn=you" will match "cn=me,c=US";cn=you"
350      *        and "ou=my org unit,o=my org,cn=me,c=US;cn=you"</li>
351      *        <li>As a value. In this case the value of a name value pair in an
352      *        RDN will be a "*". The wildcard will match any value for the given
353      *        name. For example, "cn=*,c=US;cn=you" will match
354      *        "cn=me,c=US";cn=you" and "cn=her,c=US;cn=you", but it will not
355      *        match "ou=my org unit,c=US;cn=you". If the wildcard does not occur
356      *        by itself in the value, it will not be used as a wildcard. In
357      *        other words, "cn=m*,c=US;cn=you" represents the common name of
358      *        "m*" not any common name starting with "m".</li>
359      *        </ol>
360      * @return true if dnChain matches the pattern.
361      * @throws IllegalArgumentException
362      */
363     public static boolean match(String   dnChain, String   pattern) {
364         ArrayList   parsedDNChain;
365         ArrayList   parsedDNPattern;
366         try {
367             parsedDNChain = parseDNchain(dnChain);
368         } catch (IllegalArgumentException   e) {
369             System.err.println(e.getMessage() + ": " + dnChain); //$NON-NLS-1$
370             return false;
371         }
372         try {
373             parsedDNPattern = parseDNchain(pattern);
374         } catch (IllegalArgumentException   e) {
375             System.err.println(e.getMessage() + ": " + pattern); //$NON-NLS-1$
376             return false;
377         }
378         try {
379             return dnChainMatch(parsedDNChain, 0, parsedDNPattern, 0);
380         } catch (Exception   e) {
381             e.printStackTrace();
382         }
383         return false;
384     }
385 }
386
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags