View Javadoc
1   /*
2    * Copyright (c) 1996, 2006, 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.util;
27  
28  import java.io.*;
29  import java.math.BigInteger;
30  import java.util.Arrays;
31  
32  /**
33   * Represent an ISO Object Identifier.
34   *
35   * <P>Object Identifiers are arbitrary length hierarchical identifiers.
36   * The individual components are numbers, and they define paths from the
37   * root of an ISO-managed identifier space.  You will sometimes see a
38   * string name used instead of (or in addition to) the numerical id.
39   * These are synonyms for the numerical IDs, but are not widely used
40   * since most sites do not know all the requisite strings, while all
41   * sites can parse the numeric forms.
42   *
43   * <P>So for example, JavaSoft has the sole authority to assign the
44   * meaning to identifiers below the 1.3.6.1.4.1.42.2.17 node in the
45   * hierarchy, and other organizations can easily acquire the ability
46   * to assign such unique identifiers.
47   *
48   * @author David Brownell
49   * @author Amit Kapoor
50   * @author Hemma Prafullchandra
51   */
52  
53  final public
54  class ObjectIdentifier implements Serializable
55  {
56      /**
57       * We use the DER value (no tag, no length) as the internal format
58       * @serial
59       */
60      private byte[] encoding = null;
61  
62      private transient volatile String stringForm;
63  
64      /*
65       * IMPORTANT NOTES FOR CODE CHANGES (bug 4811968) IN JDK 1.7.0
66       * ===========================================================
67       *
68       * (Almost) serialization compatibility with old versions:
69       *
70       * serialVersionUID is unchanged. Old field "component" is changed to
71       * type Object so that "poison" (unknown object type for old versions)
72       * can be put inside if there are huge components that cannot be saved
73       * as integers.
74       *
75       * New version use the new filed "encoding" only.
76       *
77       * Below are all 4 cases in a serialization/deserialization process:
78       *
79       * 1. old -> old: Not covered here
80       * 2. old -> new: There's no "encoding" field, new readObject() reads
81       *    "components" and "componentLen" instead and inits correctly.
82       * 3. new -> new: "encoding" field exists, new readObject() uses it
83       *    (ignoring the other 2 fields) and inits correctly.
84       * 4. new -> old: old readObject() only recognizes "components" and
85       *    "componentLen" fields. If no huge components are involved, they
86       *    are serialized as legal values and old object can init correctly.
87       *    Otherwise, old object cannot recognize the form (component not int[])
88       *    and throw a ClassNotFoundException at deserialization time.
89       *
90       * Therfore, for the first 3 cases, exact compatibility is preserved. In
91       * the 4th case, non-huge OID is still supportable in old versions, while
92       * huge OID is not.
93       */
94      private static final long serialVersionUID = 8697030238860181294L;
95  
96      /**
97       * Changed to Object
98       * @serial
99       */
100     private Object      components   = null;          // path from root
101     /**
102      * @serial
103      */
104     private int         componentLen = -1;            // how much is used.
105 
106     // Is the components field calculated?
107     transient private boolean   componentsCalculated = false;
108 
109     private void readObject(ObjectInputStream is)
110             throws IOException, ClassNotFoundException {
111         is.defaultReadObject();
112 
113         if (encoding == null) {  // from an old version
114             init((int[])components, componentLen);
115         }
116     }
117 
118     private void writeObject(ObjectOutputStream os)
119             throws IOException {
120         if (!componentsCalculated) {
121             int[] comps = toIntArray();
122             if (comps != null) {    // every one understands this
123                 components = comps;
124                 componentLen = comps.length;
125             } else {
126                 components = HugeOidNotSupportedByOldJDK.theOne;
127             }
128             componentsCalculated = true;
129         }
130         os.defaultWriteObject();
131     }
132 
133     static class HugeOidNotSupportedByOldJDK implements Serializable {
134         private static final long serialVersionUID = 1L;
135         static HugeOidNotSupportedByOldJDK theOne = new HugeOidNotSupportedByOldJDK();
136     }
137 
138     /**
139      * Constructs, from a string.  This string should be of the form 1.23.56.
140      * Validity check included.
141      */
142     public ObjectIdentifier (String oid) throws IOException
143     {
144         int ch = '.';
145         int start = 0;
146         int end = 0;
147 
148         int pos = 0;
149         byte[] tmp = new byte[oid.length()];
150         int first = 0, second;
151         int count = 0;
152 
153         try {
154             String comp = null;
155             do {
156                 int length = 0; // length of one section
157                 end = oid.indexOf(ch,start);
158                 if (end == -1) {
159                     comp = oid.substring(start);
160                     length = oid.length() - start;
161                 } else {
162                     comp = oid.substring(start,end);
163                     length = end - start;
164                 }
165 
166                 if (length > 9) {
167                     BigInteger bignum = new BigInteger(comp);
168                     if (count == 0) {
169                         checkFirstComponent(bignum);
170                         first = bignum.intValue();
171                     } else {
172                         if (count == 1) {
173                             checkSecondComponent(first, bignum);
174                             bignum = bignum.add(BigInteger.valueOf(40*first));
175                         } else {
176                             checkOtherComponent(count, bignum);
177                         }
178                         pos += pack7Oid(bignum, tmp, pos);
179                     }
180                 } else {
181                     int num = Integer.parseInt(comp);
182                     if (count == 0) {
183                         checkFirstComponent(num);
184                         first = num;
185                     } else {
186                         if (count == 1) {
187                             checkSecondComponent(first, num);
188                             num += 40 * first;
189                         } else {
190                             checkOtherComponent(count, num);
191                         }
192                         pos += pack7Oid(num, tmp, pos);
193                     }
194                 }
195                 start = end + 1;
196                 count++;
197             } while (end != -1);
198 
199             checkCount(count);
200             encoding = new byte[pos];
201             System.arraycopy(tmp, 0, encoding, 0, pos);
202             this.stringForm = oid;
203         } catch (IOException ioe) { // already detected by checkXXX
204             throw ioe;
205         } catch (Exception e) {
206             throw new IOException("ObjectIdentifier() -- Invalid format: "
207                     + e.toString(), e);
208         }
209     }
210 
211     /**
212      * Constructor, from an array of integers.
213      * Validity check included.
214      */
215     public ObjectIdentifier (int values []) throws IOException
216     {
217         checkCount(values.length);
218         checkFirstComponent(values[0]);
219         checkSecondComponent(values[0], values[1]);
220         for (int i=2; i<values.length; i++)
221             checkOtherComponent(i, values[i]);
222         init(values, values.length);
223     }
224 
225     /**
226      * Constructor, from an ASN.1 encoded input stream.
227      * Validity check NOT included.
228      * The encoding of the ID in the stream uses "DER", a BER/1 subset.
229      * In this case, that means a triple { typeId, length, data }.
230      *
231      * <P><STRONG>NOTE:</STRONG>  When an exception is thrown, the
232      * input stream has not been returned to its "initial" state.
233      *
234      * @param in DER-encoded data holding an object ID
235      * @exception IOException indicates a decoding error
236      */
237     public ObjectIdentifier (DerInputStream in) throws IOException
238     {
239         byte    type_id;
240         int     bufferEnd;
241 
242         /*
243          * Object IDs are a "universal" type, and their tag needs only
244          * one byte of encoding.  Verify that the tag of this datum
245          * is that of an object ID.
246          *
247          * Then get and check the length of the ID's encoding.  We set
248          * up so that we can use in.available() to check for the end of
249          * this value in the data stream.
250          */
251         type_id = (byte) in.getByte ();
252         if (type_id != DerValue.tag_ObjectId)
253             throw new IOException (
254                 "ObjectIdentifier() -- data isn't an object ID"
255                 + " (tag = " +  type_id + ")"
256                 );
257 
258         encoding = new byte[in.getLength()];
259         in.getBytes(encoding);
260         check(encoding);
261     }
262 
263     /*
264      * Constructor, from the rest of a DER input buffer;
265      * the tag and length have been removed/verified
266      * Validity check NOT included.
267      */
268     ObjectIdentifier (DerInputBuffer buf) throws IOException
269     {
270         DerInputStream in = new DerInputStream(buf);
271         encoding = new byte[in.available()];
272         in.getBytes(encoding);
273         check(encoding);
274     }
275 
276     private void init(int[] components, int length) {
277         int pos = 0;
278         byte[] tmp = new byte[length*5+1];  // +1 for empty input
279 
280         if (components[1] < Integer.MAX_VALUE - components[0]*40)
281             pos += pack7Oid(components[0]*40+components[1], tmp, pos);
282         else {
283             BigInteger big = BigInteger.valueOf(components[1]);
284             big = big.add(BigInteger.valueOf(components[0]*40));
285             pos += pack7Oid(big, tmp, pos);
286         }
287 
288         for (int i=2; i<length; i++) {
289             pos += pack7Oid(components[i], tmp, pos);
290         }
291         encoding = new byte[pos];
292         System.arraycopy(tmp, 0, encoding, 0, pos);
293     }
294 
295     /**
296      * This method is kept for compatibility reasons. The new implementation
297      * does the check and conversion. All around the JDK, the method is called
298      * in static blocks to initialize pre-defined ObjectIdentifieies. No
299      * obvious performance hurt will be made after this change.
300      *
301      * Old doc: Create a new ObjectIdentifier for internal use. The values are
302      * neither checked nor cloned.
303      */
304     public static ObjectIdentifier newInternal(int[] values) {
305         try {
306             return new ObjectIdentifier(values);
307         } catch (IOException ex) {
308             throw new RuntimeException(ex);
309             // Should not happen, internal calls always uses legal values.
310         }
311     }
312 
313     /*
314      * n.b. the only public interface is DerOutputStream.putOID()
315      */
316     void encode (DerOutputStream out) throws IOException
317     {
318         out.write (DerValue.tag_ObjectId, encoding);
319     }
320 
321     /**
322      * @deprecated Use equals((Object)oid)
323      */
324     @Deprecated
325     public boolean equals(ObjectIdentifier other) {
326         return equals((Object)other);
327     }
328 
329     /**
330      * Compares this identifier with another, for equality.
331      *
332      * @return true iff the names are identical.
333      */
334     @Override
335     public boolean equals(Object obj) {
336         if (this == obj) {
337             return true;
338         }
339         if (obj instanceof ObjectIdentifier == false) {
340             return false;
341         }
342         ObjectIdentifier other = (ObjectIdentifier)obj;
343         return Arrays.equals(encoding, other.encoding);
344     }
345 
346     @Override
347     public int hashCode() {
348         return Arrays.hashCode(encoding);
349     }
350 
351     /**
352      * Private helper method for serialization. To be compatible with old
353      * versions of JDK.
354      * @return components in an int array, if all the components are less than
355      *         Integer.MAX_VALUE. Otherwise, null.
356      */
357     private int[] toIntArray() {
358         int length = encoding.length;
359         int[] result = new int[20];
360         int which = 0;
361         int fromPos = 0;
362         for (int i = 0; i < length; i++) {
363             if ((encoding[i] & 0x80) == 0) {
364                 // one section [fromPos..i]
365                 if (i - fromPos + 1 > 4) {
366                     BigInteger big = new BigInteger(pack(encoding, fromPos, i-fromPos+1, 7, 8));
367                     if (fromPos == 0) {
368                         result[which++] = 2;
369                         BigInteger second = big.subtract(BigInteger.valueOf(80));
370                         if (second.compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) == 1) {
371                             return null;
372                         } else {
373                             result[which++] = second.intValue();
374                         }
375                     } else {
376                         if (big.compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) == 1) {
377                             return null;
378                         } else {
379                             result[which++] = big.intValue();
380                         }
381                     }
382                 } else {
383                     int retval = 0;
384                     for (int j = fromPos; j <= i; j++) {
385                         retval <<= 7;
386                         byte tmp = encoding[j];
387                         retval |= (tmp & 0x07f);
388                     }
389                     if (fromPos == 0) {
390                         if (retval < 80) {
391                             result[which++] = retval / 40;
392                             result[which++] = retval % 40;
393                         } else {
394                             result[which++] = 2;
395                             result[which++] = retval - 80;
396                         }
397                     } else {
398                         result[which++] = retval;
399                     }
400                 }
401                 fromPos = i+1;
402             }
403             if (which >= result.length) {
404                 result = Arrays.copyOf(result, which + 10);
405             }
406         }
407         return Arrays.copyOf(result, which);
408     }
409 
410     /**
411      * Returns a string form of the object ID.  The format is the
412      * conventional "dot" notation for such IDs, without any
413      * user-friendly descriptive strings, since those strings
414      * will not be understood everywhere.
415      */
416     @Override
417     public String toString() {
418         String s = stringForm;
419         if (s == null) {
420             int length = encoding.length;
421             StringBuffer sb = new StringBuffer(length * 4);
422 
423             int fromPos = 0;
424             for (int i = 0; i < length; i++) {
425                 if ((encoding[i] & 0x80) == 0) {
426                     // one section [fromPos..i]
427                     if (fromPos != 0) {  // not the first segment
428                         sb.append('.');
429                     }
430                     if (i - fromPos + 1 > 4) { // maybe big integer
431                         BigInteger big = new BigInteger(pack(encoding, fromPos, i-fromPos+1, 7, 8));
432                         if (fromPos == 0) {
433                             // first section encoded with more than 4 bytes,
434                             // must be 2.something
435                             sb.append("2.");
436                             sb.append(big.subtract(BigInteger.valueOf(80)));
437                         } else {
438                             sb.append(big);
439                         }
440                     } else { // small integer
441                         int retval = 0;
442                         for (int j = fromPos; j <= i; j++) {
443                             retval <<= 7;
444                             byte tmp = encoding[j];
445                             retval |= (tmp & 0x07f);
446                         }
447                         if (fromPos == 0) {
448                             if (retval < 80) {
449                                 sb.append(retval/40);
450                                 sb.append('.');
451                                 sb.append(retval%40);
452                             } else {
453                                 sb.append("2.");
454                                 sb.append(retval - 80);
455                             }
456                         } else {
457                             sb.append(retval);
458                         }
459                     }
460                     fromPos = i+1;
461                 }
462             }
463             s = sb.toString();
464             stringForm = s;
465         }
466         return s;
467     }
468 
469     /**
470      * Repack all bits from input to output. On the both sides, only a portion
471      * (from the least significant bit) of the 8 bits in a byte is used. This
472      * number is defined as the number of useful bits (NUB) for the array. All the
473      * used bits from the input byte array and repacked into the output in the
474      * exactly same order. The output bits are aligned so that the final bit of
475      * the input (the least significant bit in the last byte), when repacked as
476      * the final bit of the output, is still at the least significant position.
477      * Zeroes will be padded on the left side of the first output byte if
478      * necessary. All unused bits in the output are also zeroed.
479      *
480      * For example: if the input is 01001100 with NUB 8, the output which
481      * has a NUB 6 will look like:
482      *      00000001 00001100
483      * The first 2 bits of the output bytes are unused bits. The other bits
484      * turn out to be 000001 001100. While the 8 bits on the right are from
485      * the input, the left 4 zeroes are padded to fill the 6 bits space.
486      *
487      * @param in        the input byte array
488      * @param ioffset   start point inside <code>in</code>
489      * @param ilength   number of bytes to repack
490      * @param iw        NUB for input
491      * @param ow        NUB for output
492      * @return          the repacked bytes
493      */
494     private static byte[] pack(byte[] in, int ioffset, int ilength, int iw, int ow) {
495         assert (iw > 0 && iw <= 8): "input NUB must be between 1 and 8";
496         assert (ow > 0 && ow <= 8): "output NUB must be between 1 and 8";
497 
498         if (iw == ow) {
499             return in.clone();
500         }
501 
502         int bits = ilength * iw;    // number of all used bits
503         byte[] out = new byte[(bits+ow-1)/ow];
504 
505         // starting from the 0th bit in the input
506         int ipos = 0;
507 
508         // the number of padding 0's needed in the output, skip them
509         int opos = (bits+ow-1)/ow*ow-bits;
510 
511         while(ipos < bits) {
512             int count = iw - ipos%iw;   // unpacked bits in current input byte
513             if (count > ow - opos%ow) { // free space available in output byte
514                 count = ow - opos%ow;   // choose the smaller number
515             }
516             // and move them!
517             out[opos/ow] |=                         // paste!
518                 (((in[ioffset+ipos/iw]+256)         // locate the byte (+256 so that it's never negative)
519                     >> (iw-ipos%iw-count))          // move to the end of a byte
520                         & ((1 << (count))-1))       // zero out all other bits
521                             << (ow-opos%ow-count);  // move to the output position
522             ipos += count;  // advance
523             opos += count;  // advance
524         }
525         return out;
526     }
527 
528     /**
529      * Repack from NUB 8 to a NUB 7 OID sub-identifier, remove all
530      * unnecessary 0 headings, set the first bit of all non-tail
531      * output bytes to 1 (as ITU-T Rec. X.690 8.19.2 says), and
532      * paste it into an existing byte array.
533      * @param out the existing array to be pasted into
534      * @param ooffset the starting position to paste
535      * @return the number of bytes pasted
536      */
537     private static int pack7Oid(byte[] in, int ioffset, int ilength, byte[] out, int ooffset) {
538         byte[] pack = pack(in, ioffset, ilength, 8, 7);
539         int firstNonZero = pack.length-1;   // paste at least one byte
540         for (int i=pack.length-2; i>=0; i--) {
541             if (pack[i] != 0) {
542                 firstNonZero = i;
543             }
544             pack[i] |= 0x80;
545         }
546         System.arraycopy(pack, firstNonZero, out, ooffset, pack.length-firstNonZero);
547         return pack.length-firstNonZero;
548     }
549 
550     /**
551      * Repack from NUB 7 to NUB 8, remove all unnecessary 0
552      * headings, and paste it into an existing byte array.
553      * @param out the existing array to be pasted into
554      * @param ooffset the starting position to paste
555      * @return the number of bytes pasted
556      */
557     private static int pack8(byte[] in, int ioffset, int ilength, byte[] out, int ooffset) {
558         byte[] pack = pack(in, ioffset, ilength, 7, 8);
559         int firstNonZero = pack.length-1;   // paste at least one byte
560         for (int i=pack.length-2; i>=0; i--) {
561             if (pack[i] != 0) {
562                 firstNonZero = i;
563             }
564         }
565         System.arraycopy(pack, firstNonZero, out, ooffset, pack.length-firstNonZero);
566         return pack.length-firstNonZero;
567     }
568 
569     /**
570      * Pack the int into a OID sub-identifier DER encoding
571      */
572     private static int pack7Oid(int input, byte[] out, int ooffset) {
573         byte[] b = new byte[4];
574         b[0] = (byte)(input >> 24);
575         b[1] = (byte)(input >> 16);
576         b[2] = (byte)(input >> 8);
577         b[3] = (byte)(input);
578         return pack7Oid(b, 0, 4, out, ooffset);
579     }
580 
581     /**
582      * Pack the BigInteger into a OID subidentifier DER encoding
583      */
584     private static int pack7Oid(BigInteger input, byte[] out, int ooffset) {
585         byte[] b = input.toByteArray();
586         return pack7Oid(b, 0, b.length, out, ooffset);
587     }
588 
589     /**
590      * Private methods to check validity of OID. They must be --
591      * 1. at least 2 components
592      * 2. all components must be non-negative
593      * 3. the first must be 0, 1 or 2
594      * 4. if the first is 0 or 1, the second must be <40
595      */
596 
597     /**
598      * Check the DER encoding. Since DER encoding defines that the integer bits
599      * are unsigned, so there's no need to check the MSB.
600      */
601     private static void check(byte[] encoding) throws IOException {
602         int length = encoding.length;
603         if (length < 1 ||      // too short
604                 (encoding[length - 1] & 0x80) != 0) {  // not ended
605             throw new IOException("ObjectIdentifier() -- " +
606                     "Invalid DER encoding, not ended");
607         }
608         for (int i=0; i<length; i++) {
609             // 0x80 at the beginning of a subidentifier
610             if (encoding[i] == (byte)0x80 &&
611                     (i==0 || (encoding[i-1] & 0x80) == 0)) {
612                 throw new IOException("ObjectIdentifier() -- " +
613                         "Invalid DER encoding, useless extra octet detected");
614             }
615         }
616     }
617     private static void checkCount(int count) throws IOException {
618         if (count < 2) {
619             throw new IOException("ObjectIdentifier() -- " +
620                     "Must be at least two oid components ");
621         }
622     }
623     private static void checkFirstComponent(int first) throws IOException {
624         if (first < 0 || first > 2) {
625             throw new IOException("ObjectIdentifier() -- " +
626                     "First oid component is invalid ");
627         }
628     }
629     private static void checkFirstComponent(BigInteger first) throws IOException {
630         if (first.signum() == -1 ||
631                 first.compareTo(BigInteger.valueOf(2)) == 1) {
632             throw new IOException("ObjectIdentifier() -- " +
633                     "First oid component is invalid ");
634         }
635     }
636     private static void checkSecondComponent(int first, int second) throws IOException {
637         if (second < 0 || first != 2 && second > 39) {
638             throw new IOException("ObjectIdentifier() -- " +
639                     "Second oid component is invalid ");
640         }
641     }
642     private static void checkSecondComponent(int first, BigInteger second) throws IOException {
643         if (second.signum() == -1 ||
644                 first != 2 &&
645                 second.compareTo(BigInteger.valueOf(39)) == 1) {
646             throw new IOException("ObjectIdentifier() -- " +
647                     "Second oid component is invalid ");
648         }
649     }
650     private static void checkOtherComponent(int i, int num) throws IOException {
651         if (num < 0) {
652             throw new IOException("ObjectIdentifier() -- " +
653                     "oid component #" + (i+1) + " must be non-negative ");
654         }
655     }
656     private static void checkOtherComponent(int i, BigInteger num) throws IOException {
657         if (num.signum() == -1) {
658             throw new IOException("ObjectIdentifier() -- " +
659                     "oid component #" + (i+1) + " must be non-negative ");
660         }
661     }
662 }