oid.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package x509
     6  
     7  import (
     8  	"bytes"
     9  	"encoding/asn1"
    10  	"errors"
    11  	"math"
    12  	"math/big"
    13  	"math/bits"
    14  	"strconv"
    15  	"strings"
    16  )
    17  
    18  var (
    19  	errInvalidOID = errors.New("invalid oid")
    20  )
    21  
    22  // An OID represents an ASN.1 OBJECT IDENTIFIER.
    23  type OID struct {
    24  	der []byte
    25  }
    26  
    27  // ParseOID parses a Object Identifier string, represented by ASCII numbers separated by dots.
    28  func ParseOID(oid string) (OID, error) {
    29  	var o OID
    30  	return o, o.unmarshalOIDText(oid)
    31  }
    32  
    33  func newOIDFromDER(der []byte) (OID, bool) {
    34  	if len(der) == 0 || der[len(der)-1]&0x80 != 0 {
    35  		return OID{}, false
    36  	}
    37  
    38  	start := 0
    39  	for i, v := range der {
    40  		// ITU-T X.690, section 8.19.2:
    41  		// The subidentifier shall be encoded in the fewest possible octets,
    42  		// that is, the leading octet of the subidentifier shall not have the value 0x80.
    43  		if i == start && v == 0x80 {
    44  			return OID{}, false
    45  		}
    46  		if v&0x80 == 0 {
    47  			start = i + 1
    48  		}
    49  	}
    50  
    51  	return OID{der}, true
    52  }
    53  
    54  // OIDFromInts creates a new OID using ints, each integer is a separate component.
    55  func OIDFromInts(oid []uint64) (OID, error) {
    56  	if len(oid) < 2 || oid[0] > 2 || (oid[0] < 2 && oid[1] >= 40) {
    57  		return OID{}, errInvalidOID
    58  	}
    59  
    60  	length := base128IntLength(oid[0]*40 + oid[1])
    61  	for _, v := range oid[2:] {
    62  		length += base128IntLength(v)
    63  	}
    64  
    65  	der := make([]byte, 0, length)
    66  	der = appendBase128Int(der, oid[0]*40+oid[1])
    67  	for _, v := range oid[2:] {
    68  		der = appendBase128Int(der, v)
    69  	}
    70  	return OID{der}, nil
    71  }
    72  
    73  func base128IntLength(n uint64) int {
    74  	if n == 0 {
    75  		return 1
    76  	}
    77  	return (bits.Len64(n) + 6) / 7
    78  }
    79  
    80  func appendBase128Int(dst []byte, n uint64) []byte {
    81  	for i := base128IntLength(n) - 1; i >= 0; i-- {
    82  		o := byte(n >> uint(i*7))
    83  		o &= 0x7f
    84  		if i != 0 {
    85  			o |= 0x80
    86  		}
    87  		dst = append(dst, o)
    88  	}
    89  	return dst
    90  }
    91  
    92  func base128BigIntLength(n *big.Int) int {
    93  	if n.Cmp(big.NewInt(0)) == 0 {
    94  		return 1
    95  	}
    96  	return (n.BitLen() + 6) / 7
    97  }
    98  
    99  func appendBase128BigInt(dst []byte, n *big.Int) []byte {
   100  	if n.Cmp(big.NewInt(0)) == 0 {
   101  		return append(dst, 0)
   102  	}
   103  
   104  	for i := base128BigIntLength(n) - 1; i >= 0; i-- {
   105  		o := byte(big.NewInt(0).Rsh(n, uint(i)*7).Bits()[0])
   106  		o &= 0x7f
   107  		if i != 0 {
   108  			o |= 0x80
   109  		}
   110  		dst = append(dst, o)
   111  	}
   112  	return dst
   113  }
   114  
   115  // AppendText implements [encoding.TextAppender]
   116  func (o OID) AppendText(b []byte) ([]byte, error) {
   117  	return append(b, o.String()...), nil
   118  }
   119  
   120  // MarshalText implements [encoding.TextMarshaler]
   121  func (o OID) MarshalText() ([]byte, error) {
   122  	return o.AppendText(nil)
   123  }
   124  
   125  // UnmarshalText implements [encoding.TextUnmarshaler]
   126  func (o *OID) UnmarshalText(text []byte) error {
   127  	return o.unmarshalOIDText(string(text))
   128  }
   129  
   130  func (o *OID) unmarshalOIDText(oid string) error {
   131  	// (*big.Int).SetString allows +/- signs, but we don't want
   132  	// to allow them in the string representation of Object Identifier, so
   133  	// reject such encodings.
   134  	for _, c := range oid {
   135  		isDigit := c >= '0' && c <= '9'
   136  		if !isDigit && c != '.' {
   137  			return errInvalidOID
   138  		}
   139  	}
   140  
   141  	var (
   142  		firstNum  string
   143  		secondNum string
   144  	)
   145  
   146  	var nextComponentExists bool
   147  	firstNum, oid, nextComponentExists = strings.Cut(oid, ".")
   148  	if !nextComponentExists {
   149  		return errInvalidOID
   150  	}
   151  	secondNum, oid, nextComponentExists = strings.Cut(oid, ".")
   152  
   153  	var (
   154  		first  = big.NewInt(0)
   155  		second = big.NewInt(0)
   156  	)
   157  
   158  	if _, ok := first.SetString(firstNum, 10); !ok {
   159  		return errInvalidOID
   160  	}
   161  	if _, ok := second.SetString(secondNum, 10); !ok {
   162  		return errInvalidOID
   163  	}
   164  
   165  	if first.Cmp(big.NewInt(2)) > 0 || (first.Cmp(big.NewInt(2)) < 0 && second.Cmp(big.NewInt(40)) >= 0) {
   166  		return errInvalidOID
   167  	}
   168  
   169  	firstComponent := first.Mul(first, big.NewInt(40))
   170  	firstComponent.Add(firstComponent, second)
   171  
   172  	der := appendBase128BigInt(make([]byte, 0, 32), firstComponent)
   173  
   174  	for nextComponentExists {
   175  		var strNum string
   176  		strNum, oid, nextComponentExists = strings.Cut(oid, ".")
   177  		b, ok := big.NewInt(0).SetString(strNum, 10)
   178  		if !ok {
   179  			return errInvalidOID
   180  		}
   181  		der = appendBase128BigInt(der, b)
   182  	}
   183  
   184  	o.der = der
   185  	return nil
   186  }
   187  
   188  // AppendBinary implements [encoding.BinaryAppender]
   189  func (o OID) AppendBinary(b []byte) ([]byte, error) {
   190  	return append(b, o.der...), nil
   191  }
   192  
   193  // MarshalBinary implements [encoding.BinaryMarshaler]
   194  func (o OID) MarshalBinary() ([]byte, error) {
   195  	return o.AppendBinary(nil)
   196  }
   197  
   198  // UnmarshalBinary implements [encoding.BinaryUnmarshaler]
   199  func (o *OID) UnmarshalBinary(b []byte) error {
   200  	oid, ok := newOIDFromDER(bytes.Clone(b))
   201  	if !ok {
   202  		return errInvalidOID
   203  	}
   204  	*o = oid
   205  	return nil
   206  }
   207  
   208  // Equal returns true when oid and other represents the same Object Identifier.
   209  func (oid OID) Equal(other OID) bool {
   210  	// There is only one possible DER encoding of
   211  	// each unique Object Identifier.
   212  	return bytes.Equal(oid.der, other.der)
   213  }
   214  
   215  func parseBase128Int(bytes []byte, initOffset int) (ret, offset int, failed bool) {
   216  	offset = initOffset
   217  	var ret64 int64
   218  	for shifted := 0; offset < len(bytes); shifted++ {
   219  		// 5 * 7 bits per byte == 35 bits of data
   220  		// Thus the representation is either non-minimal or too large for an int32
   221  		if shifted == 5 {
   222  			failed = true
   223  			return
   224  		}
   225  		ret64 <<= 7
   226  		b := bytes[offset]
   227  		// integers should be minimally encoded, so the leading octet should
   228  		// never be 0x80
   229  		if shifted == 0 && b == 0x80 {
   230  			failed = true
   231  			return
   232  		}
   233  		ret64 |= int64(b & 0x7f)
   234  		offset++
   235  		if b&0x80 == 0 {
   236  			ret = int(ret64)
   237  			// Ensure that the returned value fits in an int on all platforms
   238  			if ret64 > math.MaxInt32 {
   239  				failed = true
   240  			}
   241  			return
   242  		}
   243  	}
   244  	failed = true
   245  	return
   246  }
   247  
   248  // EqualASN1OID returns whether an OID equals an asn1.ObjectIdentifier. If
   249  // asn1.ObjectIdentifier cannot represent the OID specified by oid, because
   250  // a component of OID requires more than 31 bits, it returns false.
   251  func (oid OID) EqualASN1OID(other asn1.ObjectIdentifier) bool {
   252  	if len(other) < 2 {
   253  		return false
   254  	}
   255  	v, offset, failed := parseBase128Int(oid.der, 0)
   256  	if failed {
   257  		// This should never happen, since we've already parsed the OID,
   258  		// but just in case.
   259  		return false
   260  	}
   261  	if v < 80 {
   262  		a, b := v/40, v%40
   263  		if other[0] != a || other[1] != b {
   264  			return false
   265  		}
   266  	} else {
   267  		a, b := 2, v-80
   268  		if other[0] != a || other[1] != b {
   269  			return false
   270  		}
   271  	}
   272  
   273  	i := 2
   274  	for ; offset < len(oid.der); i++ {
   275  		v, offset, failed = parseBase128Int(oid.der, offset)
   276  		if failed {
   277  			// Again, shouldn't happen, since we've already parsed
   278  			// the OID, but better safe than sorry.
   279  			return false
   280  		}
   281  		if i >= len(other) || v != other[i] {
   282  			return false
   283  		}
   284  	}
   285  
   286  	return i == len(other)
   287  }
   288  
   289  // Strings returns the string representation of the Object Identifier.
   290  func (oid OID) String() string {
   291  	var b strings.Builder
   292  	b.Grow(32)
   293  	const (
   294  		valSize         = 64 // size in bits of val.
   295  		bitsPerByte     = 7
   296  		maxValSafeShift = (1 << (valSize - bitsPerByte)) - 1
   297  	)
   298  	var (
   299  		start    = 0
   300  		val      = uint64(0)
   301  		numBuf   = make([]byte, 0, 21)
   302  		bigVal   *big.Int
   303  		overflow bool
   304  	)
   305  	for i, v := range oid.der {
   306  		curVal := v & 0x7F
   307  		valEnd := v&0x80 == 0
   308  		if valEnd {
   309  			if start != 0 {
   310  				b.WriteByte('.')
   311  			}
   312  		}
   313  		if !overflow && val > maxValSafeShift {
   314  			if bigVal == nil {
   315  				bigVal = new(big.Int)
   316  			}
   317  			bigVal = bigVal.SetUint64(val)
   318  			overflow = true
   319  		}
   320  		if overflow {
   321  			bigVal = bigVal.Lsh(bigVal, bitsPerByte).Or(bigVal, big.NewInt(int64(curVal)))
   322  			if valEnd {
   323  				if start == 0 {
   324  					b.WriteString("2.")
   325  					bigVal = bigVal.Sub(bigVal, big.NewInt(80))
   326  				}
   327  				numBuf = bigVal.Append(numBuf, 10)
   328  				b.Write(numBuf)
   329  				numBuf = numBuf[:0]
   330  				val = 0
   331  				start = i + 1
   332  				overflow = false
   333  			}
   334  			continue
   335  		}
   336  		val <<= bitsPerByte
   337  		val |= uint64(curVal)
   338  		if valEnd {
   339  			if start == 0 {
   340  				if val < 80 {
   341  					b.Write(strconv.AppendUint(numBuf, val/40, 10))
   342  					b.WriteByte('.')
   343  					b.Write(strconv.AppendUint(numBuf, val%40, 10))
   344  				} else {
   345  					b.WriteString("2.")
   346  					b.Write(strconv.AppendUint(numBuf, val-80, 10))
   347  				}
   348  			} else {
   349  				b.Write(strconv.AppendUint(numBuf, val, 10))
   350  			}
   351  			val = 0
   352  			start = i + 1
   353  		}
   354  	}
   355  	return b.String()
   356  }
   357  
   358  func (oid OID) toASN1OID() (asn1.ObjectIdentifier, bool) {
   359  	out := make([]int, 0, len(oid.der)+1)
   360  
   361  	const (
   362  		valSize         = 31 // amount of usable bits of val for OIDs.
   363  		bitsPerByte     = 7
   364  		maxValSafeShift = (1 << (valSize - bitsPerByte)) - 1
   365  	)
   366  
   367  	val := 0
   368  
   369  	for _, v := range oid.der {
   370  		if val > maxValSafeShift {
   371  			return nil, false
   372  		}
   373  
   374  		val <<= bitsPerByte
   375  		val |= int(v & 0x7F)
   376  
   377  		if v&0x80 == 0 {
   378  			if len(out) == 0 {
   379  				if val < 80 {
   380  					out = append(out, val/40)
   381  					out = append(out, val%40)
   382  				} else {
   383  					out = append(out, 2)
   384  					out = append(out, val-80)
   385  				}
   386  				val = 0
   387  				continue
   388  			}
   389  			out = append(out, val)
   390  			val = 0
   391  		}
   392  	}
   393  
   394  	return out, true
   395  }
   396
View as plain text