daemon: libutil: make nar parser much stricter.

The prior implementation of 'parse' was, to put it mildly, very accepting of
invalid input.  This made it very difficult to review its security properties,
which ended up relying entirely on the fact that it still didn't allow "/" in
directory entry names and that O_CREAT|O_EXCL implicitly causes symlinks to
not be followed in the final component, and mkdir and symlink never follow
symlinks in the final component, and all of the above throw exceptions when
they fail.

Some examples of what was allowed prior:

1. Empty archives:
   "nix-archive-1" "(" ")"
2. Archives with only a type:
   "nix-archive-1" "(" "type" "regular" ")"
3. Archives of regular files with multiple contents, which would be
   concatenated (e.g. this has contents "foobar"):
   "nix-archive-1" "(" "type" "regular" "contents" "foo" "contents" "bar" ")"
4. Archives of directories with multiple entries with the same name, and that
   aren't sorted:
   "nix-archive-1" "(" "type" "directory"
                       "entry" "(" "name" "c" "node" "(" ")" ")"
                       "entry" "(" "name" "b" "node" "(" ")" ")"
                       "entry" "(" "name" "b" "node" "(" ")" ")"
                       "entry" "(" "name" "a" "node" "(" ")" ")" ")"
5. Archives of directories with empty entries:
   "nix-archive-1" "(" "type" "directory" "entry" "(" ")" ")"
6. Archives of directories with entries with no name:
   "nix-archive-1" "(" "type" "directory" "entry" "(" "node" "(" ")" ")" ")"
7. Archives of directories with entries with no node:
   "nix-archive-1" "(" "type" "directory" "entry" "(" "name" "a" ")" ")"
7. Archives of directories with entries with multiple names:
   "nix-archive-1" "(" "type" "directory" "entry" "(" "name" "a"
                                                      "node" "(" ")"
                                                      "name" "b" ")" ")"
8. Archives of directories with entries with multiple nodes:
   "nix-archive-1" "(" "type" "directory" "entry" "(" "node" "(" ")"
                                                      "node" "(" ")" ")" ")"
9. Archives of directories with entries with multiple names and multiple
   nodes:
   "nix-archive-1" "(" "type" "directory"
                       "entry" "(" "name" "a" "node" "(" ")"
                                   "name" "b" "node" "(" ")" ")" ")"

Such permissiveness rather defeats the "normalized" part of "Normalized
ARchive".

Additionally, 'parse' previously used recursion with no explicit depth limit.
In practice Linux would still limit the depth to around 2048, since filenames
longer than 4096 bytes yield ENAMETOOLONG, but no such restriction exists on
Hurd.

The permissiveness issue is resolved by rewriting 'parse', and the unbounded
recursion issue is resolved by adding a nestLimit parameter so that no more
than DIRECTORY_NESTING_LIMIT (currently 256) levels of recursion are used.  An
alternate implementation that doesn't use recursion, 'parse_unbounded', is
included in case it is determined that the nesting limit should be removed,
but currently only 'parse' is used.

* nix/libutil/archive.cc (parse): rewrite to add nestLimit parameter.
  (parseDump): pass DIRECTORY_NESTING_LIMIT as nestLimit argument to 'parse'.
  (parse_unbounded): new function.

Change-Id: Ia3c32cc645b609f6ae7f3bcafc491ec0073cbb51
Signed-off-by: Ludovic Courtès <ludo@gnu.org>

1 files changed, 136 insertions, 56 deletions

diff --git a/nix/libutil/archive.cc b/nix/libutil/archive.cc
index 938fe8d4492..81c03f44d37 100644
--- a/nix/libutil/archive.cc
+++ b/nix/libutil/archive.cc
@@ -155,94 +155,169 @@ struct CaseInsensitiveCompare
     }
 };
 
+/* Used to place a consistent upper bound on recursion depth */
+#define DIRECTORY_NESTING_LIMIT 256
 
-static void parse(ParseSink & sink, Source & source, const Path & path)
+static void parse(ParseSink & sink, Source & source, const Path & path,
+                  int nestLimit)
 {
+    if (nestLimit <= 0) throw Error("nar directory nesting limit reached");
     string s;
 
     s = readString(source);
     if (s != "(") throw badArchive("expected open tag");
 
-    enum { tpUnknown, tpRegular, tpDirectory, tpSymlink } type = tpUnknown;
-
-    std::map<Path, int, CaseInsensitiveCompare> names;
+    s = readString(source);
+    if (s != "type") throw badArchive("expected type tag");
 
-    while (1) {
-        checkInterrupt();
+    s = readString(source);
 
+    if (s == "regular") {
+        bool executable = false;
         s = readString(source);
-
-        if (s == ")") {
-            break;
+        if (s == "executable") {
+            executable = true;
+            readString(source);
+            s = readString(source);
         }
 
-        else if (s == "type") {
-            if (type != tpUnknown)
-                throw badArchive("multiple type fields");
-            string t = readString(source);
+        if (s != "contents") throw badArchive("expected contents tag");
 
-            if (t == "regular") {
-                type = tpRegular;
-                sink.createRegularFile(path);
-            }
+        sink.createRegularFile(path);
+        if (executable) sink.isExecutable();
+        parseContents(sink, source, path);
+        s = readString(source);
+        if (s != ")") throw badArchive("expected close tag");
+    }
+    else if (s == "symlink") {
+        s = readString(source);
+        if (s != "target") throw badArchive("expected target tag");
+        s = readString(source);
+        sink.createSymlink(path, s);
+        s = readString(source);
+        if (s != ")") throw badArchive("expected close tag");
+    }
+    else if (s == "directory") {
+        string prevName;
+        sink.createDirectory(path);
+        while (true) {
+            checkInterrupt();
+            s = readString(source);
+            if (s == ")") break;
+            if (s != "entry") throw badArchive("expected entry tag");
 
-            else if (t == "directory") {
-                sink.createDirectory(path);
-                type = tpDirectory;
-            }
+            s = readString(source);
+            if (s != "(") throw badArchive("expected entry open tag");
 
-            else if (t == "symlink") {
-                type = tpSymlink;
-            }
+            s = readString(source);
+            if (s != "name") throw badArchive("expected name tag");
 
-            else throw badArchive("unknown file type " + t);
+            s = readString(source);
+            string name = s;
+            if (name.empty() || name == "." || name == ".."
+                || name.find('/') != string::npos
+                || name.find((char) 0) != string::npos)
+                throw Error(std::format("NAR contains invalid file name `{}'", name));
+            if (!prevName.empty() && name <= prevName)
+                throw Error("NAR directory is not sorted");
 
-        }
+            s = readString(source);
+            if (s != "node") throw badArchive("expected node tag");
+
+            parse(sink, source, path + "/" + name, nestLimit - 1);
 
-        else if (s == "contents" && type == tpRegular) {
-            parseContents(sink, source, path);
+            s = readString(source);
+            if (s != ")") throw badArchive("expected entry close tag");
+            prevName = name;
         }
+    }
+    else throw badArchive("unknown type");
+}
 
-        else if (s == "executable" && type == tpRegular) {
+/* Unbounded variant that doesn't recurse, uses path as its stack */
+static void parse_unbounded(ParseSink & sink, Source & source, Path & path)
+{
+    string prevName;
+    string s;
+start:
+    s = readString(source);
+    if (s != "(") throw badArchive("expected open tag");
+
+    s = readString(source);
+    if (s != "type") throw badArchive("expected type tag");
+
+    s = readString(source);
+
+    if (s == "regular") {
+        bool executable = false;
+        s = readString(source);
+        if (s == "executable") {
+            executable = true;
             readString(source);
-            sink.isExecutable();
+            s = readString(source);
         }
 
-        else if (s == "entry" && type == tpDirectory) {
-            string name, prevName;
+        if (s != "contents") throw badArchive("expected contents tag");
+
+        sink.createRegularFile(path);
+        if (executable) sink.isExecutable();
+        parseContents(sink, source, path);
+        s = readString(source);
+        if (s != ")") throw badArchive("expected close tag");
+    }
+    else if (s == "symlink") {
+        s = readString(source);
+        if (s != "target") throw badArchive("expected target tag");
+        s = readString(source);
+        sink.createSymlink(path, s);
+        s = readString(source);
+        if (s != ")") throw badArchive("expected close tag");
+    }
+    else if (s == "directory") {
+        sink.createDirectory(path);
+        while (true) {
+            checkInterrupt();
+            s = readString(source);
+            if (s == ")") break;
+            if (s != "entry") throw badArchive("expected entry tag");
+
+            s = readString(source);
+            if (s != "(") throw badArchive("expected entry open tag");
 
             s = readString(source);
-            if (s != "(") throw badArchive("expected open tag");
+            if (s != "name") throw badArchive("expected name tag");
 
-            while (1) {
-                checkInterrupt();
+            s = readString(source);
+            {
+                string name = s;
+                if (name.empty() || name == "." || name == ".."
+                    || name.find('/') != string::npos
+                    || name.find((char) 0) != string::npos)
+                    throw Error(std::format("NAR contains invalid file name `{}'", name));
+                if (!prevName.empty() && name <= prevName)
+                    throw Error("NAR directory is not sorted");
 
                 s = readString(source);
+                if (s != "node") throw badArchive("expected node tag");
 
-                if (s == ")") {
-                    break;
-                } else if (s == "name") {
-                    name = readString(source);
-                    if (name.empty() || name == "." || name == ".." || name.find('/') != string::npos || name.find((char) 0) != string::npos)
-                        throw Error(std::format("NAR contains invalid file name `{}'", name));
-                    if (name <= prevName)
-                        throw Error("NAR directory is not sorted");
-                    prevName = name;
-                } else if (s == "node") {
-                    if (s.empty()) throw badArchive("entry name missing");
-                    parse(sink, source, path + "/" + name);
-                } else
-                    throw badArchive("unknown field " + s);
+                /* parse(sink, source, path + "/" + name); */
+                path.append("/" + name);
+                prevName = "";
+                goto start;
             }
-        }
 
-        else if (s == "target" && type == tpSymlink) {
-            string target = readString(source);
-            sink.createSymlink(path, target);
+        continue_directory:
+            s = readString(source);
+            if (s != ")") throw badArchive("expected entry close tag");
         }
+    }
+    else throw badArchive("unknown type");
 
-        else
-            throw badArchive("unknown field " + s);
+    string::size_type slash_pos = path.rfind("/");
+    if (slash_pos != string::npos) {
+        prevName = string(path, slash_pos+1);
+        path.erase(slash_pos);
+        goto continue_directory;
     }
 }
 
@@ -258,7 +333,12 @@ void parseDump(ParseSink & sink, Source & source)
     }
     if (version != archiveVersion1)
         throw badArchive("input doesn't look like a normalized archive");
-    parse(sink, source, "");
+
+    parse(sink, source, "", DIRECTORY_NESTING_LIMIT);
+    /*
+    string file = "";
+    parse_unbounded(sink, source, file);
+    */
 }