Algorithmic complexity in Libksba's DN/BER processing
Closed, ResolvedPublic

Assigned To
Authored By
• werner
Feb 13 2026, 11:36 AM

Description

Reported-by: Francisco Tacliad


Severity: Low (informational)
CWE: CWE-407 (Inefficient Algorithmic Complexity)

The campaign produced 36 hang inputs. Analysis:

  • 2 true timeouts (>5 seconds, did not complete)
  • 33 slow completions (finished given more time, but exceeded AFL++'s timeout threshold)
  • 1 memory leak (Finding 2 above)

The timeout inputs contain crafted ASN.1 length fields and nested
structures that trigger quadratic or worse processing time. In a
network-facing context (OCSP responder, key server), these could
be used for CPU exhaustion.

METHODOLOGY

Tool: AFL++ 4.x with afl-clang-fast, AddressSanitizer enabled
Target: libksba master, commit 63df565
Harness: Custom fuzz_ksba_dn.c exercising both ksba_dn_str2der()

and _ksba_derdn_to_str() code paths

Seeds: libksba test suite + hand-crafted RFC 2253 DN strings
Duration: ~16 hours on standard workstation
Results: 62 crashes, 36 hangs, 4800+ unique code paths explored

Full crash corpus and fuzz harness available on request.

Revisions and Commits

Event Timeline

• werner created this task.
• werner created this object in space Restricted Space.
• werner created this object with edit policy "Contributor (Project)".

do_expand_tree (which traverses the tree) has quadratic processing time, because it calls resolve_identifier which always traverses the tree by _ksba_asn_find_node.

We could modify do_expand_tree, adding a control structure CTX which has a cache table of identifier -> node for resolve_identifier, and let it only traverse the tree when not cached and put the result node into the cache.

Here is an experiment to have a cache table of identifiers.
This can only work on GNU system (with tdestroy), but we can see if this can improve the situation.

diff --git a/src/asn1-func.c b/src/asn1-func.c
index 7a33dd4..e39e243 100755
--- a/src/asn1-func.c
+++ b/src/asn1-func.c
@@ -30,6 +30,8 @@
 
 #ifndef BUILD_GENTOOLS
 #include <config.h>
+#else
+#define _GNU_SOURCE
 #endif
 
 #include <stdio.h>
@@ -38,6 +40,8 @@
 #include <ctype.h>
 #include <assert.h>
 
+#include <search.h>
+
 #ifdef BUILD_GENTOOLS
 # include "gen-help.h"
 #else
@@ -51,8 +55,8 @@
 #define gpgrt_log_debug(...)  /**/
 #endif
 
-
-static AsnNode resolve_identifier (AsnNode root, AsnNode node, int nestlevel);
+static AsnNode resolve_identifier (void **cache_p,
+                                   AsnNode root, AsnNode node, int nestlevel);
 
 
 static AsnNode
@@ -297,7 +301,7 @@ _ksba_asn_remove_node (AsnNode  node)
    the last element of a SET_OF.  A "+" matches the CHOICE with values
    set. */
 static AsnNode
-find_node (AsnNode root, const char *name, int resolve)
+find_node (AsnNode root, const char *name, void **cache_p)
 {
   AsnNode p;
   const char *s;
@@ -362,18 +366,18 @@ find_node (AsnNode root, const char *name, int resolve)
               /*                  __func__, buf, p?p->name:""); */
               if (p->name && !strcmp (p->name, buf))
                 break;
-              if (resolve && p->name && p->type == TYPE_IDENTIFIER)
+              if (cache_p && p->name && p->type == TYPE_IDENTIFIER)
                 {
                   AsnNode p2;
 
-                  p2 = resolve_identifier (root, p, 0);
+                  p2 = resolve_identifier (cache_p, root, p, 0);
                   if (p2 && p2->name && !strcmp (p2->name, buf))
                     break;
                 }
             }
 
-          if (resolve && p && p->type == TYPE_IDENTIFIER)
-            p = resolve_identifier (root, p, 0);
+          if (cache_p && p && p->type == TYPE_IDENTIFIER)
+            p = resolve_identifier (cache_p, root, p, 0);
 	}
     }
 
@@ -383,7 +387,7 @@ find_node (AsnNode root, const char *name, int resolve)
 AsnNode
 _ksba_asn_find_node (AsnNode root, const char *name)
 {
-  return find_node (root, name, 0);
+  return find_node (root, name, NULL);
 }
 
 
@@ -1080,13 +1084,45 @@ copy_tree (AsnNode src_root, AsnNode s)
 
 
 
+struct identifier_cache_entry {
+  char *name;
+  AsnNode node;
+};
+
+static int
+compare_cache_entry (const void *pa, const void *pb)
+{
+  const struct identifier_cache_entry *ea, *eb;
+
+  ea = pa;
+  eb = pb;
+  return strcmp (ea->name, eb->name);
+}
+
+static void
+cache_free_entry (void *e)
+{
+  struct identifier_cache_entry *ea = e;
+
+  xfree (ea->name);
+  xfree (ea);
+}
+
+static void
+cache_destroy (void *cache)
+{
+  tdestroy (cache, cache_free_entry);
+}
+
+
 static AsnNode
-resolve_identifier (AsnNode root, AsnNode node, int nestlevel)
+resolve_identifier (void **cache_p, AsnNode root, AsnNode node, int nestlevel)
 {
   char buf_space[50];
   char *buf;
   AsnNode n;
   size_t bufsize;
+  struct identifier_cache_entry *e, **ep;
 
   if (nestlevel > 20)
     return NULL;
@@ -1103,11 +1139,26 @@ resolve_identifier (AsnNode root, AsnNode node, int nestlevel)
       return_null_if_fail (buf);
     }
   strcpy (stpcpy (stpcpy (buf, root->name), "."), node->value.v_cstr);
-  n = _ksba_asn_find_node (root, buf);
+
+  e = xmalloc (sizeof (*e));
+  e->name = xstrdup (buf);
+  e->node = NULL;
+
+  ep = tsearch (e, cache_p, compare_cache_entry);
+  if (*ep != e)
+    {
+      /* found in the cache */
+      xfree (e);
+      return (*ep)->node;
+    }
+
+  n = find_node (root, buf, NULL);
 
   /* We do just a simple indirection. */
   if (n && n->type == TYPE_IDENTIFIER)
-    n = resolve_identifier (root, n, nestlevel+1);
+    n = resolve_identifier (cache_p, root, n, nestlevel+1);
+
+  e->node = n;
 
   if (buf != buf_space)
     xfree (buf);
@@ -1117,7 +1168,7 @@ resolve_identifier (AsnNode root, AsnNode node, int nestlevel)
 
 
 static AsnNode
-do_expand_tree (AsnNode src_root, AsnNode s, int depth)
+do_expand_tree (void **cache_p, AsnNode src_root, AsnNode s, int depth)
 {
   AsnNode first=NULL, dprev=NULL, d, down, tmp;
   AsnNode *link_nextp = NULL;
@@ -1135,7 +1186,7 @@ do_expand_tree (AsnNode src_root, AsnNode s, int depth)
         {
           AsnNode s2, *dp;
 
-          d = resolve_identifier (src_root, s, 0);
+          d = resolve_identifier (cache_p, src_root, s, 0);
           if (!d)
             {
               fprintf (stderr, "RESOLVING IDENTIFIER FAILED\n");
@@ -1205,7 +1256,7 @@ do_expand_tree (AsnNode src_root, AsnNode s, int depth)
             }
           else
             {
-	      tmp = do_expand_tree (src_root, down, depth+1);
+	      tmp = do_expand_tree (cache_p, src_root, down, depth+1);
 	      if (tmp)
 		{
 		  if (link_nextp)
@@ -1246,10 +1297,13 @@ do_expand_tree (AsnNode src_root, AsnNode s, int depth)
 AsnNode
 _ksba_asn_expand_tree (AsnNode parse_tree, const char *name)
 {
-  AsnNode root;
+  AsnNode root, n;
+  void *cache = NULL;
 
-  root = name? find_node (parse_tree, name, 1) : parse_tree;
-  return do_expand_tree (parse_tree, root, 0);
+  root = name? find_node (parse_tree, name, &cache) : parse_tree;
+  n = do_expand_tree (&cache, parse_tree, root, 0);
+  cache_destroy (cache);
+  return n;
 }
• gniibe mentioned this in Unknown Object (Maniphest Task).Feb 23 2026, 4:04 AM
• gniibe mentioned this in Unknown Object (Maniphest Task).Mar 2 2026, 3:00 AM

Here is updated patch (implementing t_search and t_destroy by ourselves):

• gniibe mentioned this in Unknown Object (Maniphest Task).Mar 9 2026, 2:40 AM

Updated the patch to use an implementation in C library when available.

Push the change: rK9ccbafd9b26b: Fix _ksba_asn_expand_tree with cache table.

• gniibe changed the task status from Open to Testing.Oct 9 2026, 3:47 AM
• gniibe mentioned this in Unknown Object (Maniphest Task).Oct 12 2026, 3:48 AM

The cache table works well when there are many uses for an identifier.

For the case of deep indirect references (VAR1->VAR2->...->final value), the recursive calls of resolve_identifier and its call of find_node would matter (might result quadratic processing time).

We can improve this by:

  • in _ksba_asm_expand_tree, we take two passes approach
  • first pass: walking the tree of nodes, register all identifiers into a cache table
  • second pass: run do_expand_tree with modified resolve_identifier
    • resolve_identifier firstly checks the cache table if there is an entry, use it if there
      • when an entry doesn't exist, only when this case, call find_node to find an node and put it into the cache
• gniibe mentioned this in Unknown Object (Maniphest Task).Mon, Oct 19, 4:07 AM
• werner shifted this object from the Restricted Space space to the S1 Public space.Tue, Nov 17, 6:14 PM