O(N²) CPU amplification in `ObjectIdentifier.String()` — triggered inside `ParseCertificate` and ZGrab2 JSON output

[tynus3]

Summary

ObjectIdentifier.String() in encoding/asn1/asn1.go uses raw += string concatenation in a loop, giving O(N²) total character copies for an OID with N arcs. This is directly triggered inside ParseCertificate at multiple call sites and in ZGrab2's JSON serialization path — meaning no caller code is needed to trigger the attack. A crafted 64 KB OID causes ~23 seconds of CPU stall per certificate (14 String() calls × ~1.6 s each).

Root Cause

// encoding/asn1/asn1.go:243-252  — current code (O(N²))
func (oi ObjectIdentifier) String() string {
    var s string
    for i, v := range oi {
        if i > 0 {
            s += "."             // allocates len(s)+1 bytes, copies all of s
        }
        s += strconv.Itoa(v)   // allocates len(s)+digits bytes, copies all of s
    }
    return s
}

Each s += allocates a new backing array and copies the full accumulated string. For N arcs: Σᵢ₌₁ᴺ i ≈ N²/2 total byte copies. The Go GC
collects the intermediate strings, so peak RSS stays bounded at O(N) ~ 640 KB — but it forces 129 GB of allocation churn for a 256 KB OID, causing sustained GC pressure across the entire process, not just the affected goroutine.

RDNSequence.String() in x509/pkix/pkix.go:194-250 has the same pattern (s += typeName + "=" + ... inside nested loops).

Note

1. This Is Worse Than A Standalone Slow Function as oid.String() is called at three independent sites inside ParseCertificate, all on attacker-controlled OIDs:
   | Call site | Location | Calls per OID |
   |-----------|----------|:---:|
   | extKeyUsageFromOID — EKU OID lookup | x509/x509.go:703 | 1 per EKU OID |
   | EV/OV/DV certificate policy lookup | x509/x509.go:1303–1307 | 3 per policy OID |
   | ExtensionsMap construction | x509/x509.go:1690 | 1 per extension OID |

A certificate with 1 EKU, 1 policy OID, and 10 extensions triggers 14 String() calls on those OIDs before ParseCertificate returns.
Measured cost:

OID arcs	1 call	14 calls (realistic cert)
8 000	26 ms	362 ms
16 000	94 ms	1 322 ms
32 000	311 ms	4 354 ms
64 000	2 320 ms	32 479 ms (~32 s)

A single 64 KB crafted certificate stalls ParseCertificate for ~32
seconds on one goroutine.

2. ZGrab2 always hits the JSON serialization path
3. GC pressure affects the whole process.
   Huge allocation churn for a 256 KB OID triggers continuous GC background work.

Reproduce

package main

import (
    "fmt"
    "time"
    zasn1 "github.com/zmap/zcrypto/encoding/asn1"
)

func main() {
    // Build OID with 64000 arcs (~64KB)
    content := make([]byte, 63999)
    for i := range content { content[i] = 0x01 }
    payload := append([]byte{0x06, 0x83, 0x00, 0xF9, 0xFF}, content...)

    var oi zasn1.ObjectIdentifier
    zasn1.Unmarshal(payload, &oi)

    t := time.Now()
    _ = oi.String()
    fmt.Printf("String() on 64k-arc OID: %v\n", time.Since(t))
    // Expected: ~1.6 seconds. Linear would be ~0.01 ms.
}

---

Thanks for maintaining Zcrypto. Please let me know if I need to provide more information.
And please let me know if I made any mistakes.