1 /*
2  * Copyright (c) 1997, 2003, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.  Oracle designates this
8  * particular file as subject to the "Classpath" exception as provided
9  * by Oracle in the LICENSE file that accompanied this code.
10  *
11  * This code is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14  * version 2 for more details (a copy is included in the LICENSE file that
15  * accompanied this code).
16  *
17  * You should have received a copy of the GNU General Public License version
18  * 2 along with this work; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20  *
21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22  * or visit www.oracle.com if you need additional information or have any
23  * questions.
24  */
25 
26 package sun.security.x509;
27 
28 import java.io.*;
29 import java.util.*;
30 
31 import sun.security.util.*;
32 
33 /**
34  * Represent the GeneralSubtrees ASN.1 object.
35  * <p>
36  * The ASN.1 for this is
37  * <pre>
38  * GeneralSubtrees ::= SEQUENCE SIZE (1..MAX) OF GeneralSubtree
39  * </pre>
40  * </p>
41  *
42  *
43  * @author Amit Kapoor
44  * @author Hemma Prafullchandra
45  * @author Andreas Sterbenz
46  */
47 public class GeneralSubtrees implements Cloneable {
48 
49     private final List<GeneralSubtree> trees;
50 
51     // Private variables
52     private static final int NAME_DIFF_TYPE = GeneralNameInterface.NAME_DIFF_TYPE;
53     private static final int NAME_MATCH = GeneralNameInterface.NAME_MATCH;
54     private static final int NAME_NARROWS = GeneralNameInterface.NAME_NARROWS;
55     private static final int NAME_WIDENS = GeneralNameInterface.NAME_WIDENS;
56     private static final int NAME_SAME_TYPE = GeneralNameInterface.NAME_SAME_TYPE;
57 
58     /**
59      * The default constructor for the class.
60      */
GeneralSubtrees()61     public GeneralSubtrees() {
62         trees = new ArrayList<GeneralSubtree>();
63     }
64 
GeneralSubtrees(GeneralSubtrees source)65     private GeneralSubtrees(GeneralSubtrees source) {
66         trees = new ArrayList<GeneralSubtree>(source.trees);
67     }
68 
69     /**
70      * Create the object from the passed DER encoded form.
71      *
72      * @param val the DER encoded form of the same.
73      */
GeneralSubtrees(DerValue val)74     public GeneralSubtrees(DerValue val) throws IOException {
75         this();
76         if (val.tag != DerValue.tag_Sequence) {
77             throw new IOException("Invalid encoding of GeneralSubtrees.");
78         }
79         while (val.data.available() != 0) {
80             DerValue opt = val.data.getDerValue();
81             GeneralSubtree tree = new GeneralSubtree(opt);
82             add(tree);
83         }
84     }
85 
get(int index)86     public GeneralSubtree get(int index) {
87         return trees.get(index);
88     }
89 
remove(int index)90     public void remove(int index) {
91         trees.remove(index);
92     }
93 
add(GeneralSubtree tree)94     public void add(GeneralSubtree tree) {
95         if (tree == null) {
96             throw new NullPointerException();
97         }
98         trees.add(tree);
99     }
100 
contains(GeneralSubtree tree)101     public boolean contains(GeneralSubtree tree) {
102         if (tree == null) {
103             throw new NullPointerException();
104         }
105         return trees.contains(tree);
106     }
107 
size()108     public int size() {
109         return trees.size();
110     }
111 
iterator()112     public Iterator<GeneralSubtree> iterator() {
113         return trees.iterator();
114     }
115 
trees()116     public List<GeneralSubtree> trees() {
117         return trees;
118     }
119 
clone()120     public Object clone() {
121         return new GeneralSubtrees(this);
122     }
123 
124     /**
125      * Return a printable string of the GeneralSubtree.
126      */
toString()127     public String toString() {
128         String s = "   GeneralSubtrees:\n" + trees.toString() + "\n";
129         return s;
130     }
131 
132     /**
133      * Encode the GeneralSubtrees.
134      *
135      * @params out the DerOutputStrean to encode this object to.
136      */
encode(DerOutputStream out)137     public void encode(DerOutputStream out) throws IOException {
138         DerOutputStream seq = new DerOutputStream();
139 
140         for (int i = 0, n = size(); i < n; i++) {
141             get(i).encode(seq);
142         }
143         out.write(DerValue.tag_Sequence, seq);
144     }
145 
146     /**
147      * Compare two general subtrees by comparing the subtrees
148      * of each.
149      *
150      * @param other GeneralSubtrees to compare to this
151      * @returns true if match
152      */
equals(Object obj)153     public boolean equals(Object obj) {
154         if (this == obj) {
155             return true;
156         }
157         if (obj instanceof GeneralSubtrees == false) {
158             return false;
159         }
160         GeneralSubtrees other = (GeneralSubtrees)obj;
161         return this.trees.equals(other.trees);
162     }
163 
hashCode()164     public int hashCode() {
165         return trees.hashCode();
166     }
167 
168     /**
169      * Return the GeneralNameInterface form of the GeneralName in one of
170      * the GeneralSubtrees.
171      *
172      * @param ndx index of the GeneralSubtree from which to obtain the name
173      */
getGeneralNameInterface(int ndx)174     private GeneralNameInterface getGeneralNameInterface(int ndx) {
175         return getGeneralNameInterface(get(ndx));
176     }
177 
getGeneralNameInterface(GeneralSubtree gs)178     private static GeneralNameInterface getGeneralNameInterface(GeneralSubtree gs) {
179         GeneralName gn = gs.getName();
180         GeneralNameInterface gni = gn.getName();
181         return gni;
182     }
183 
184     /**
185      * minimize this GeneralSubtrees by removing all redundant entries.
186      * Internal method used by intersect and reduce.
187      */
minimize()188     private void minimize() {
189 
190         // Algorithm: compare each entry n to all subsequent entries in
191         // the list: if any subsequent entry matches or widens entry n,
192         // remove entry n. If any subsequent entries narrow entry n, remove
193         // the subsequent entries.
194         for (int i = 0; i < size(); i++) {
195             GeneralNameInterface current = getGeneralNameInterface(i);
196             boolean remove1 = false;
197 
198             /* compare current to subsequent elements */
199             for (int j = i + 1; j < size(); j++) {
200                 GeneralNameInterface subsequent = getGeneralNameInterface(j);
201                 switch (current.constrains(subsequent)) {
202                     case GeneralNameInterface.NAME_DIFF_TYPE:
203                         /* not comparable; different name types; keep checking */
204                         continue;
205                     case GeneralNameInterface.NAME_MATCH:
206                         /* delete one of the duplicates */
207                         remove1 = true;
208                         break;
209                     case GeneralNameInterface.NAME_NARROWS:
210                         /* subsequent narrows current */
211                         /* remove narrower name (subsequent) */
212                         remove(j);
213                         j--; /* continue check with new subsequent */
214                         continue;
215                     case GeneralNameInterface.NAME_WIDENS:
216                         /* subsequent widens current */
217                         /* remove narrower name current */
218                         remove1 = true;
219                         break;
220                     case GeneralNameInterface.NAME_SAME_TYPE:
221                         /* keep both for now; keep checking */
222                         continue;
223                 }
224                 break;
225             } /* end of this pass of subsequent elements */
226 
227             if (remove1) {
228                 remove(i);
229                 i--; /* check the new i value */
230             }
231 
232         }
233     }
234 
235     /**
236      * create a subtree containing an instance of the input
237      * name type that widens all other names of that type.
238      *
239      * @params name GeneralNameInterface name
240      * @returns GeneralSubtree containing widest name of that type
241      * @throws RuntimeException on error (should not occur)
242      */
createWidestSubtree(GeneralNameInterface name)243     private GeneralSubtree createWidestSubtree(GeneralNameInterface name) {
244         try {
245             GeneralName newName;
246             switch (name.getType()) {
247             case GeneralNameInterface.NAME_ANY:
248                 // Create new OtherName with same OID as baseName, but
249                 // empty value
250                 ObjectIdentifier otherOID = ((OtherName)name).getOID();
251                 newName = new GeneralName(new OtherName(otherOID, null));
252                 break;
253             case GeneralNameInterface.NAME_RFC822:
254                 newName = new GeneralName(new RFC822Name(""));
255                 break;
256             case GeneralNameInterface.NAME_DNS:
257                 newName = new GeneralName(new DNSName(""));
258                 break;
259             case GeneralNameInterface.NAME_X400:
260                 newName = new GeneralName(new X400Address((byte[])null));
261                 break;
262             case GeneralNameInterface.NAME_DIRECTORY:
263                 newName = new GeneralName(new X500Name(""));
264                 break;
265             case GeneralNameInterface.NAME_EDI:
266                 newName = new GeneralName(new EDIPartyName(""));
267                 break;
268             case GeneralNameInterface.NAME_URI:
269                 newName = new GeneralName(new URIName(""));
270                 break;
271             case GeneralNameInterface.NAME_IP:
272                 newName = new GeneralName(new IPAddressName((byte[])null));
273                 break;
274             case GeneralNameInterface.NAME_OID:
275                 newName = new GeneralName
276                     (new OIDName(new ObjectIdentifier((int[])null)));
277                 break;
278             default:
279                 throw new IOException
280                     ("Unsupported GeneralNameInterface type: " + name.getType());
281             }
282             return new GeneralSubtree(newName, 0, -1);
283         } catch (IOException e) {
284             throw new RuntimeException("Unexpected error: " + e, e);
285         }
286     }
287 
288     /**
289      * intersect this GeneralSubtrees with other.  This function
290      * is used in merging permitted NameConstraints.  The operation
291      * is performed as follows:
292      * <ul>
293      * <li>If a name in other narrows all names of the same type in this,
294      *     the result will contain the narrower name and none of the
295      *     names it narrows.
296      * <li>If a name in other widens all names of the same type in this,
297      *     the result will not contain the wider name.
298      * <li>If a name in other does not share the same subtree with any name
299      *     of the same type in this, then the name is added to the list
300      *     of GeneralSubtrees returned.  These names should be added to
301      *     the list of names that are specifically excluded.  The reason
302      *     is that, if the intersection is empty, then no names of that
303      *     type are permitted, and the only way to express this in
304      *     NameConstraints is to include the name in excludedNames.
305      * <li>If a name in this has no name of the same type in other, then
306      *     the result contains the name in this.  No name of a given type
307      *     means the name type is completely permitted.
308      * <li>If a name in other has no name of the same type in this, then
309      *     the result contains the name in other.  This means that
310      *     the name is now constrained in some way, whereas before it was
311      *     completely permitted.
312      * <ul>
313      *
314      * @param other GeneralSubtrees to be intersected with this
315      * @returns GeneralSubtrees to be merged with excluded; these are
316      *          empty-valued name types corresponding to entries that were
317      *          of the same type but did not share the same subtree between
318      *          this and other. Returns null if no such.
319      */
intersect(GeneralSubtrees other)320     public GeneralSubtrees intersect(GeneralSubtrees other) {
321 
322         if (other == null) {
323             throw new NullPointerException("other GeneralSubtrees must not be null");
324         }
325 
326         GeneralSubtrees newThis = new GeneralSubtrees();
327         GeneralSubtrees newExcluded = null;
328 
329         // Step 1: If this is empty, just add everything in other to this and
330         // return no new excluded entries
331         if (size() == 0) {
332             union(other);
333             return null;
334         }
335 
336         // Step 2: For ease of checking the subtrees, minimize them by
337         // constructing versions that contain only the widest instance of
338         // each type
339         this.minimize();
340         other.minimize();
341 
342         // Step 3: Check each entry in this to see whether we keep it or
343         // remove it, and whether we add anything to newExcluded or newThis.
344         // We keep an entry in this unless it is narrowed by all entries in
345         // other.  We add an entry to newExcluded if there is at least one
346         // entry of the same nameType in other, but this entry does
347         // not share the same subtree with any of the entries in other.
348         // We add an entry from other to newThis if there is no name of the
349         // same type in this.
350         for (int i = 0; i < size(); i++) {
351             GeneralNameInterface thisEntry = getGeneralNameInterface(i);
352             boolean removeThisEntry = false;
353 
354             // Step 3a: If the widest name of this type in other narrows
355             // thisEntry, remove thisEntry and add widest other to newThis.
356             // Simultaneously, check for situation where there is a name of
357             // this type in other, but no name in other matches, narrows,
358             // or widens thisEntry.
359             boolean sameType = false;
360             for (int j = 0; j < other.size(); j++) {
361                 GeneralSubtree otherEntryGS = other.get(j);
362                 GeneralNameInterface otherEntry =
363                     getGeneralNameInterface(otherEntryGS);
364                 switch (thisEntry.constrains(otherEntry)) {
365                     case NAME_NARROWS:
366                         remove(i);
367                         i--;
368                         newThis.add(otherEntryGS);
369                         sameType = false;
370                         break;
371                     case NAME_SAME_TYPE:
372                         sameType = true;
373                         continue;
374                     case NAME_MATCH:
375                     case NAME_WIDENS:
376                         sameType = false;
377                         break;
378                     case NAME_DIFF_TYPE:
379                     default:
380                         continue;
381                 }
382                 break;
383             }
384 
385             // Step 3b: If sameType is still true, we have the situation
386             // where there was a name of the same type as thisEntry in
387             // other, but no name in other widened, matched, or narrowed
388             // thisEntry.
389             if (sameType) {
390 
391                 // Step 3b.1: See if there are any entries in this and other
392                 // with this type that match, widen, or narrow each other.
393                 // If not, then we need to add a "widest subtree" of this
394                 // type to excluded.
395                 boolean intersection = false;
396                 for (int j = 0; j < size(); j++) {
397                     GeneralNameInterface thisAltEntry = getGeneralNameInterface(j);
398 
399                     if (thisAltEntry.getType() == thisEntry.getType()) {
400                         for (int k = 0; k < other.size(); k++) {
401                             GeneralNameInterface othAltEntry =
402                                 other.getGeneralNameInterface(k);
403 
404                             int constraintType =
405                                 thisAltEntry.constrains(othAltEntry);
406                             if (constraintType == NAME_MATCH ||
407                                 constraintType == NAME_WIDENS ||
408                                 constraintType == NAME_NARROWS) {
409                                 intersection = true;
410                                 break;
411                             }
412                         }
413                     }
414                 }
415                 if (intersection == false) {
416                     if (newExcluded == null) {
417                         newExcluded = new GeneralSubtrees();
418                     }
419                     GeneralSubtree widestSubtree =
420                          createWidestSubtree(thisEntry);
421                     if (!newExcluded.contains(widestSubtree)) {
422                         newExcluded.add(widestSubtree);
423                     }
424                 }
425 
426                 // Step 3b.2: Remove thisEntry from this
427                 remove(i);
428                 i--;
429             }
430         }
431 
432         // Step 4: Add all entries in newThis to this
433         if (newThis.size() > 0) {
434             union(newThis);
435         }
436 
437         // Step 5: Add all entries in other that do not have any entry of the
438         // same type in this to this
439         for (int i = 0; i < other.size(); i++) {
440             GeneralSubtree otherEntryGS = other.get(i);
441             GeneralNameInterface otherEntry = getGeneralNameInterface(otherEntryGS);
442             boolean diffType = false;
443             for (int j = 0; j < size(); j++) {
444                 GeneralNameInterface thisEntry = getGeneralNameInterface(j);
445                 switch (thisEntry.constrains(otherEntry)) {
446                     case NAME_DIFF_TYPE:
447                         diffType = true;
448                         // continue to see if we find something later of the
449                         // same type
450                         continue;
451                     case NAME_NARROWS:
452                     case NAME_SAME_TYPE:
453                     case NAME_MATCH:
454                     case NAME_WIDENS:
455                         diffType = false; // we found an entry of the same type
456                         // break because we know we won't be adding it to
457                         // this now
458                         break;
459                     default:
460                         continue;
461                 }
462                 break;
463             }
464             if (diffType) {
465                 add(otherEntryGS);
466             }
467         }
468 
469         // Step 6: Return the newExcluded GeneralSubtrees
470         return newExcluded;
471     }
472 
473     /**
474      * construct union of this GeneralSubtrees with other.
475      *
476      * @param other GeneralSubtrees to be united with this
477      */
union(GeneralSubtrees other)478     public void union(GeneralSubtrees other) {
479         if (other != null) {
480             for (int i = 0, n = other.size(); i < n; i++) {
481                 add(other.get(i));
482             }
483             // Minimize this
484             minimize();
485         }
486     }
487 
488     /**
489      * reduce this GeneralSubtrees by contents of another.  This function
490      * is used in merging excluded NameConstraints with permitted NameConstraints
491      * to obtain a minimal form of permitted NameConstraints.  It is an
492      * optimization, and does not affect correctness of the results.
493      *
494      * @param excluded GeneralSubtrees
495      */
reduce(GeneralSubtrees excluded)496     public void reduce(GeneralSubtrees excluded) {
497         if (excluded == null) {
498             return;
499         }
500         for (int i = 0, n = excluded.size(); i < n; i++) {
501             GeneralNameInterface excludedName = excluded.getGeneralNameInterface(i);
502             for (int j = 0; j < size(); j++) {
503                 GeneralNameInterface permitted = getGeneralNameInterface(j);
504                 switch (excludedName.constrains(permitted)) {
505                 case GeneralNameInterface.NAME_DIFF_TYPE:
506                     break;
507                 case GeneralNameInterface.NAME_MATCH:
508                     remove(j);
509                     j--;
510                     break;
511                 case GeneralNameInterface.NAME_NARROWS:
512                     /* permitted narrows excluded */
513                     remove(j);
514                     j--;
515                     break;
516                 case GeneralNameInterface.NAME_WIDENS:
517                     /* permitted widens excluded */
518                     break;
519                 case GeneralNameInterface.NAME_SAME_TYPE:
520                     break;
521                 }
522             } /* end of this pass of permitted */
523         } /* end of pass of excluded */
524     }
525 }
526