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