Sort children map before hash

The unordered map may generate different hash due to its order. The
children map needs to be sorted each time before hashing to avoid false
verification failure due to the map.

Store the sorted children map in verity dentry to avoid sorting it each
time verification happens.

Also serialize the whole VerityDescriptor struct to hash now that the
map is removed from it.

PiperOrigin-RevId: 382201560

2 files changed, 27 insertions, 4 deletions

diff --git a/pkg/sentry/fsimpl/verity/filesystem.go b/pkg/sentry/fsimpl/verity/filesystem.go
index e84452421..b5735a86d 100644
--- a/pkg/sentry/fsimpl/verity/filesystem.go
+++ b/pkg/sentry/fsimpl/verity/filesystem.go
@@ -283,7 +283,7 @@ func (fs *filesystem) verifyChildLocked(ctx context.Context, parent *dentry, chi
 		Mode:                  uint32(parentStat.Mode),
 		UID:                   parentStat.UID,
 		GID:                   parentStat.GID,
-		Children:              parent.childrenNames,
+		Children:              parent.childrenList,
 		HashAlgorithms:        fs.alg.toLinuxHashAlg(),
 		ReadOffset:            int64(offset),
 		ReadSize:              int64(merkletree.DigestSize(fs.alg.toLinuxHashAlg())),
@@ -404,6 +404,9 @@ func (fs *filesystem) verifyStatAndChildrenLocked(ctx context.Context, d *dentry
 
 	var buf bytes.Buffer
 	d.hashMu.RLock()
+
+	d.generateChildrenList()
+
 	params := &merkletree.VerifyParams{
 		Out:            &buf,
 		Tree:           &fdReader,
@@ -412,7 +415,7 @@ func (fs *filesystem) verifyStatAndChildrenLocked(ctx context.Context, d *dentry
 		Mode:           uint32(stat.Mode),
 		UID:            stat.UID,
 		GID:            stat.GID,
-		Children:       d.childrenNames,
+		Children:       d.childrenList,
 		HashAlgorithms: fs.alg.toLinuxHashAlg(),
 		ReadOffset:     0,
 		// Set read size to 0 so only the metadata is verified.
diff --git a/pkg/sentry/fsimpl/verity/verity.go b/pkg/sentry/fsimpl/verity/verity.go
index ffc8f019d..2227b542a 100644
--- a/pkg/sentry/fsimpl/verity/verity.go
+++ b/pkg/sentry/fsimpl/verity/verity.go
@@ -39,6 +39,7 @@ import (
 	"encoding/json"
 	"fmt"
 	"math"
+	"sort"
 	"strconv"
 	"strings"
 	"sync/atomic"
@@ -509,6 +510,7 @@ func (fstype FilesystemType) GetFilesystem(ctx context.Context, vfsObj *vfs.Virt
 		if err := fs.verifyStatAndChildrenLocked(ctx, d, stat); err != nil {
 			return nil, nil, err
 		}
+		d.generateChildrenList()
 	}
 
 	d.vfsd.Init(d)
@@ -565,6 +567,11 @@ type dentry struct {
 	// populated by enableVerity. childrenNames is also protected by dirMu.
 	childrenNames map[string]struct{}
 
+	// childrenList is a complete sorted list of childrenNames. This list
+	// is generated when verity is enabled, or the first time the file is
+	// verified in non runtime enable mode.
+	childrenList []string
+
 	// lowerVD is the VirtualDentry in the underlying file system. It is
 	// never modified after initialized.
 	lowerVD vfs.VirtualDentry
@@ -750,6 +757,17 @@ func (d *dentry) verityEnabled() bool {
 	return !d.fs.allowRuntimeEnable || len(d.hash) != 0
 }
 
+// generateChildrenList generates a sorted childrenList from childrenNames, and
+// cache it in d for hashing.
+func (d *dentry) generateChildrenList() {
+	if len(d.childrenList) == 0 && len(d.childrenNames) != 0 {
+		for child := range d.childrenNames {
+			d.childrenList = append(d.childrenList, child)
+		}
+		sort.Strings(d.childrenList)
+	}
+}
+
 // getLowerAt returns the dentry in the underlying file system, which is
 // represented by filename relative to d.
 func (d *dentry) getLowerAt(ctx context.Context, vfsObj *vfs.VirtualFilesystem, filename string) (vfs.VirtualDentry, error) {
@@ -963,10 +981,12 @@ func (fd *fileDescription) generateMerkleLocked(ctx context.Context) ([]byte, ui
 		return nil, 0, err
 	}
 
+	fd.d.generateChildrenList()
+
 	params := &merkletree.GenerateParams{
 		TreeReader:     &merkleReader,
 		TreeWriter:     &merkleWriter,
-		Children:       fd.d.childrenNames,
+		Children:       fd.d.childrenList,
 		HashAlgorithms: fd.d.fs.alg.toLinuxHashAlg(),
 		Name:           fd.d.name,
 		Mode:           uint32(stat.Mode),
@@ -1262,7 +1282,7 @@ func (fd *fileDescription) PRead(ctx context.Context, dst usermem.IOSequence, of
 		Mode:                  fd.d.mode,
 		UID:                   fd.d.uid,
 		GID:                   fd.d.gid,
-		Children:              fd.d.childrenNames,
+		Children:              fd.d.childrenList,
 		HashAlgorithms:        fd.d.fs.alg.toLinuxHashAlg(),
 		ReadOffset:            offset,
 		ReadSize:              dst.NumBytes(),