diff options
Diffstat (limited to 'pkg/merkletree')
| -rw-r--r-- | pkg/merkletree/BUILD | 23 | ||||
| -rw-r--r-- | pkg/merkletree/merkletree.go | 496 | ||||
| -rw-r--r-- | pkg/merkletree/merkletree_test.go | 615 |
3 files changed, 1134 insertions, 0 deletions
diff --git a/pkg/merkletree/BUILD b/pkg/merkletree/BUILD new file mode 100644 index 000000000..501a9ef21 --- /dev/null +++ b/pkg/merkletree/BUILD @@ -0,0 +1,23 @@ +load("//tools:defs.bzl", "go_library", "go_test") + +package(licenses = ["notice"]) + +go_library( + name = "merkletree", + srcs = ["merkletree.go"], + visibility = ["//pkg/sentry:internal"], + deps = [ + "//pkg/abi/linux", + "//pkg/usermem", + ], +) + +go_test( + name = "merkletree_test", + srcs = ["merkletree_test.go"], + library = ":merkletree", + deps = [ + "//pkg/abi/linux", + "//pkg/usermem", + ], +) diff --git a/pkg/merkletree/merkletree.go b/pkg/merkletree/merkletree.go new file mode 100644 index 000000000..18457d287 --- /dev/null +++ b/pkg/merkletree/merkletree.go @@ -0,0 +1,496 @@ +// Copyright 2020 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Package merkletree implements Merkle tree generating and verification. +package merkletree + +import ( + "bytes" + "crypto/sha256" + "crypto/sha512" + "fmt" + "io" + + "gvisor.dev/gvisor/pkg/abi/linux" + "gvisor.dev/gvisor/pkg/usermem" +) + +const ( + // sha256DigestSize specifies the digest size of a SHA256 hash. + sha256DigestSize = 32 + // sha512DigestSize specifies the digest size of a SHA512 hash. + sha512DigestSize = 64 +) + +// DigestSize returns the size (in bytes) of a digest. +// TODO(b/156980949): Allow config SHA384. +func DigestSize(hashAlgorithm int) int { + switch hashAlgorithm { + case linux.FS_VERITY_HASH_ALG_SHA256: + return sha256DigestSize + case linux.FS_VERITY_HASH_ALG_SHA512: + return sha512DigestSize + default: + return -1 + } +} + +// Layout defines the scale of a Merkle tree. +type Layout struct { + // blockSize is the size of a data block to be hashed. + blockSize int64 + // digestSize is the size of a generated hash. + digestSize int64 + // levelOffset contains the offset of the beginning of each level in + // bytes. The number of levels in the tree is the length of the slice. + // The leaf nodes (level 0) contain hashes of blocks of the input data. + // Each level N contains hashes of the blocks in level N-1. The highest + // level is the root hash. + levelOffset []int64 +} + +// InitLayout initializes and returns a new Layout object describing the structure +// of a tree. dataSize specifies the size of input data in bytes. +func InitLayout(dataSize int64, hashAlgorithms int, dataAndTreeInSameFile bool) (Layout, error) { + layout := Layout{ + blockSize: usermem.PageSize, + } + + // TODO(b/156980949): Allow config SHA384. + switch hashAlgorithms { + case linux.FS_VERITY_HASH_ALG_SHA256: + layout.digestSize = sha256DigestSize + case linux.FS_VERITY_HASH_ALG_SHA512: + layout.digestSize = sha512DigestSize + default: + return Layout{}, fmt.Errorf("unexpected hash algorithms") + } + + // treeStart is the offset (in bytes) of the first level of the tree in + // the file. If data and tree are in different files, treeStart should + // be zero. If data is in the same file as the tree, treeStart points + // to the block after the last data block (which may be zero-padded). + var treeStart int64 + if dataAndTreeInSameFile { + treeStart = dataSize + if dataSize%layout.blockSize != 0 { + treeStart += layout.blockSize - dataSize%layout.blockSize + } + } + + numBlocks := (dataSize + layout.blockSize - 1) / layout.blockSize + level := 0 + offset := int64(0) + + // Calculate the number of levels in the Merkle tree and the beginning + // offset of each level. Level 0 consists of the leaf nodes that + // contain the hashes of the data blocks, while level numLevels - 1 is + // the root. + for numBlocks > 1 { + layout.levelOffset = append(layout.levelOffset, treeStart+offset*layout.blockSize) + // Round numBlocks up to fill up a block. + numBlocks += (layout.hashesPerBlock() - numBlocks%layout.hashesPerBlock()) % layout.hashesPerBlock() + offset += numBlocks / layout.hashesPerBlock() + numBlocks = numBlocks / layout.hashesPerBlock() + level++ + } + layout.levelOffset = append(layout.levelOffset, treeStart+offset*layout.blockSize) + + return layout, nil +} + +// hashesPerBlock() returns the number of digests in each block. For example, +// if blockSize is 4096 bytes, and digestSize is 32 bytes, there will be 128 +// hashesPerBlock. Therefore 128 hashes in one level will be combined in one +// hash in the level above. +func (layout Layout) hashesPerBlock() int64 { + return layout.blockSize / layout.digestSize +} + +// numLevels returns the total number of levels in the Merkle tree. +func (layout Layout) numLevels() int { + return len(layout.levelOffset) +} + +// rootLevel returns the level of the root hash. +func (layout Layout) rootLevel() int { + return layout.numLevels() - 1 +} + +// digestOffset finds the offset of a digest from the beginning of the tree. +// The target digest is at level of the tree, with index from the beginning of +// the current level. +func (layout Layout) digestOffset(level int, index int64) int64 { + return layout.levelOffset[level] + index*layout.digestSize +} + +// blockOffset finds the offset of a block from the beginning of the tree. The +// target block is at level of the tree, with index from the beginning of the +// current level. +func (layout Layout) blockOffset(level int, index int64) int64 { + return layout.levelOffset[level] + index*layout.blockSize +} + +// VerityDescriptor is a struct that is serialized and hashed to get a file's +// root hash, which contains the root hash of the raw content and the file's +// meatadata. +type VerityDescriptor struct { + Name string + Mode uint32 + UID uint32 + GID uint32 + RootHash []byte +} + +func (d *VerityDescriptor) String() string { + return fmt.Sprintf("Name: %s, Mode: %d, UID: %d, GID: %d, RootHash: %v", d.Name, d.Mode, d.UID, d.GID, d.RootHash) +} + +// verify generates a hash from d, and compares it with expected. +func (d *VerityDescriptor) verify(expected []byte, hashAlgorithms int) error { + h, err := hashData([]byte(d.String()), hashAlgorithms) + if err != nil { + return err + } + if !bytes.Equal(h[:], expected) { + return fmt.Errorf("unexpected root hash") + } + return nil + +} + +// hashData hashes data and returns the result hash based on the hash +// algorithms. +func hashData(data []byte, hashAlgorithms int) ([]byte, error) { + var digest []byte + switch hashAlgorithms { + case linux.FS_VERITY_HASH_ALG_SHA256: + digestArray := sha256.Sum256(data) + digest = digestArray[:] + case linux.FS_VERITY_HASH_ALG_SHA512: + digestArray := sha512.Sum512(data) + digest = digestArray[:] + default: + return nil, fmt.Errorf("unexpected hash algorithms") + } + return digest, nil +} + +// GenerateParams contains the parameters used to generate a Merkle tree. +type GenerateParams struct { + // File is a reader of the file to be hashed. + File io.ReaderAt + // Size is the size of the file. + Size int64 + // Name is the name of the target file. + Name string + // Mode is the mode of the target file. + Mode uint32 + // UID is the user ID of the target file. + UID uint32 + // GID is the group ID of the target file. + GID uint32 + // HashAlgorithms is the algorithms used to hash data. + HashAlgorithms int + // TreeReader is a reader for the Merkle tree. + TreeReader io.ReaderAt + // TreeWriter is a writer for the Merkle tree. + TreeWriter io.Writer + // DataAndTreeInSameFile is true if data and Merkle tree are in the same + // file, or false if Merkle tree is a separate file from data. + DataAndTreeInSameFile bool +} + +// Generate constructs a Merkle tree for the contents of params.File. The +// output is written to params.TreeWriter. +// +// Generate returns a hash of a VerityDescriptor, which contains the file +// metadata and the hash from file content. +func Generate(params *GenerateParams) ([]byte, error) { + layout, err := InitLayout(params.Size, params.HashAlgorithms, params.DataAndTreeInSameFile) + if err != nil { + return nil, err + } + + numBlocks := (params.Size + layout.blockSize - 1) / layout.blockSize + + // If the data is in the same file as the tree, zero pad the last data + // block. + bytesInLastBlock := params.Size % layout.blockSize + if params.DataAndTreeInSameFile && bytesInLastBlock != 0 { + zeroBuf := make([]byte, layout.blockSize-bytesInLastBlock) + if _, err := params.TreeWriter.Write(zeroBuf); err != nil { + return nil, err + } + } + + var root []byte + for level := 0; level < layout.numLevels(); level++ { + for i := int64(0); i < numBlocks; i++ { + buf := make([]byte, layout.blockSize) + var ( + n int + err error + ) + if level == 0 { + // Read data block from the target file since level 0 includes hashes + // of blocks in the input data. + n, err = params.File.ReadAt(buf, i*layout.blockSize) + } else { + // Read data block from the tree file since levels higher than 0 are + // hashing the lower level hashes. + n, err = params.TreeReader.ReadAt(buf, layout.blockOffset(level-1, i)) + } + + // err is populated as long as the bytes read is smaller than the buffer + // size. This could be the case if we are reading the last block, and + // break in that case. If this is the last block, the end of the block + // will be zero-padded. + if n == 0 && err == io.EOF { + break + } else if err != nil && err != io.EOF { + return nil, err + } + // Hash the bytes in buf. + digest, err := hashData(buf, params.HashAlgorithms) + if err != nil { + return nil, err + } + + if level == layout.rootLevel() { + root = digest + } + + // Write the generated hash to the end of the tree file. + if _, err = params.TreeWriter.Write(digest[:]); err != nil { + return nil, err + } + } + // If the generated digests do not round up to a block, zero-padding the + // remaining of the last block. But no need to do so for root. + if level != layout.rootLevel() && numBlocks%layout.hashesPerBlock() != 0 { + zeroBuf := make([]byte, layout.blockSize-(numBlocks%layout.hashesPerBlock())*layout.digestSize) + if _, err := params.TreeWriter.Write(zeroBuf[:]); err != nil { + return nil, err + } + } + numBlocks = (numBlocks + layout.hashesPerBlock() - 1) / layout.hashesPerBlock() + } + descriptor := VerityDescriptor{ + Name: params.Name, + Mode: params.Mode, + UID: params.UID, + GID: params.GID, + RootHash: root, + } + return hashData([]byte(descriptor.String()), params.HashAlgorithms) +} + +// VerifyParams contains the params used to verify a portion of a file against +// a Merkle tree. +type VerifyParams struct { + // Out will be filled with verified data. + Out io.Writer + // File is a handler on the file to be verified. + File io.ReaderAt + // tree is a handler on the Merkle tree used to verify file. + Tree io.ReaderAt + // Size is the size of the file. + Size int64 + // Name is the name of the target file. + Name string + // Mode is the mode of the target file. + Mode uint32 + // UID is the user ID of the target file. + UID uint32 + // GID is the group ID of the target file. + GID uint32 + // HashAlgorithms is the algorithms used to hash data. + HashAlgorithms int + // ReadOffset is the offset of the data range to be verified. + ReadOffset int64 + // ReadSize is the size of the data range to be verified. + ReadSize int64 + // Expected is a trusted hash for the file. It is compared with the + // calculated root hash to verify the content. + Expected []byte + // DataAndTreeInSameFile is true if data and Merkle tree are in the same + // file, or false if Merkle tree is a separate file from data. + DataAndTreeInSameFile bool +} + +// verifyMetadata verifies the metadata by hashing a descriptor that contains +// the metadata and compare the generated hash with expected. +// +// For verifyMetadata, params.data is not needed. It only accesses params.tree +// for the raw root hash. +func verifyMetadata(params *VerifyParams, layout *Layout) error { + root := make([]byte, layout.digestSize) + if _, err := params.Tree.ReadAt(root, layout.blockOffset(layout.rootLevel(), 0 /* index */)); err != nil { + return fmt.Errorf("failed to read root hash: %w", err) + } + descriptor := VerityDescriptor{ + Name: params.Name, + Mode: params.Mode, + UID: params.UID, + GID: params.GID, + RootHash: root, + } + return descriptor.verify(params.Expected, params.HashAlgorithms) +} + +// Verify verifies the content read from data with offset. The content is +// verified against tree. If content spans across multiple blocks, each block is +// verified. Verification fails if the hash of the data does not match the tree +// at any level, or if the final root hash does not match expected. +// Once the data is verified, it will be written using params.Out. +// +// Verify checks for both target file content and metadata. If readSize is 0, +// only metadata is checked. +func Verify(params *VerifyParams) (int64, error) { + if params.ReadSize < 0 { + return 0, fmt.Errorf("unexpected read size: %d", params.ReadSize) + } + layout, err := InitLayout(int64(params.Size), params.HashAlgorithms, params.DataAndTreeInSameFile) + if err != nil { + return 0, err + } + if params.ReadSize == 0 { + return 0, verifyMetadata(params, &layout) + } + + // Calculate the index of blocks that includes the target range in input + // data. + firstDataBlock := params.ReadOffset / layout.blockSize + lastDataBlock := (params.ReadOffset + params.ReadSize - 1) / layout.blockSize + + buf := make([]byte, layout.blockSize) + var readErr error + total := int64(0) + for i := firstDataBlock; i <= lastDataBlock; i++ { + // Read a block that includes all or part of target range in + // input data. + bytesRead, err := params.File.ReadAt(buf, i*layout.blockSize) + readErr = err + // If at the end of input data and all previous blocks are + // verified, return the verified input data and EOF. + if readErr == io.EOF && bytesRead == 0 { + break + } + if readErr != nil && readErr != io.EOF { + return 0, fmt.Errorf("read from data failed: %w", err) + } + // If this is the end of file, zero the remaining bytes in buf, + // otherwise they are still from the previous block. + // TODO(b/162908070): Investigate possible issues with zero + // padding the data. + if bytesRead < len(buf) { + for j := bytesRead; j < len(buf); j++ { + buf[j] = 0 + } + } + descriptor := VerityDescriptor{ + Name: params.Name, + Mode: params.Mode, + UID: params.UID, + GID: params.GID, + } + if err := verifyBlock(params.Tree, &descriptor, &layout, buf, i, params.HashAlgorithms, params.Expected); err != nil { + return 0, err + } + + // startOff is the beginning of the read range within the + // current data block. Note that for all blocks other than the + // first, startOff should be 0. + startOff := int64(0) + if i == firstDataBlock { + startOff = params.ReadOffset % layout.blockSize + } + // endOff is the end of the read range within the current data + // block. Note that for all blocks other than the last, endOff + // should be the block size. + endOff := layout.blockSize + if i == lastDataBlock { + endOff = (params.ReadOffset+params.ReadSize-1)%layout.blockSize + 1 + } + // If the provided size exceeds the end of input data, we should + // only copy the parts in buf that's part of input data. + if startOff > int64(bytesRead) { + startOff = int64(bytesRead) + } + if endOff > int64(bytesRead) { + endOff = int64(bytesRead) + } + n, err := params.Out.Write(buf[startOff:endOff]) + if err != nil { + return total, err + } + total += int64(n) + + } + return total, readErr +} + +// verifyBlock verifies a block against tree. index is the number of block in +// original data. The block is verified through each level of the tree. It +// fails if the calculated hash from block is different from any level of +// hashes stored in tree. And the final root hash is compared with +// expected. +func verifyBlock(tree io.ReaderAt, descriptor *VerityDescriptor, layout *Layout, dataBlock []byte, blockIndex int64, hashAlgorithms int, expected []byte) error { + if len(dataBlock) != int(layout.blockSize) { + return fmt.Errorf("incorrect block size") + } + + expectedDigest := make([]byte, layout.digestSize) + treeBlock := make([]byte, layout.blockSize) + var digest []byte + for level := 0; level < layout.numLevels(); level++ { + // Calculate hash. + if level == 0 { + h, err := hashData(dataBlock, hashAlgorithms) + if err != nil { + return err + } + digest = h + } else { + // Read a block in previous level that contains the + // hash we just generated, and generate a next level + // hash from it. + if _, err := tree.ReadAt(treeBlock, layout.blockOffset(level-1, blockIndex)); err != nil { + return err + } + h, err := hashData(treeBlock, hashAlgorithms) + if err != nil { + return err + } + digest = h + } + + // Read the digest for the current block and store in + // expectedDigest. + if _, err := tree.ReadAt(expectedDigest, layout.digestOffset(level, blockIndex)); err != nil { + return err + } + + if !bytes.Equal(digest, expectedDigest) { + return fmt.Errorf("verification failed") + } + blockIndex = blockIndex / layout.hashesPerBlock() + } + + // Verification for the tree succeeded. Now hash the descriptor with + // the root hash and compare it with expected. + descriptor.RootHash = digest + return descriptor.verify(expected, hashAlgorithms) +} diff --git a/pkg/merkletree/merkletree_test.go b/pkg/merkletree/merkletree_test.go new file mode 100644 index 000000000..0782ca3e7 --- /dev/null +++ b/pkg/merkletree/merkletree_test.go @@ -0,0 +1,615 @@ +// Copyright 2020 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package merkletree + +import ( + "bytes" + "fmt" + "io" + "math/rand" + "testing" + "time" + + "gvisor.dev/gvisor/pkg/abi/linux" + "gvisor.dev/gvisor/pkg/usermem" +) + +func TestLayout(t *testing.T) { + testCases := []struct { + dataSize int64 + hashAlgorithms int + dataAndTreeInSameFile bool + expectedDigestSize int64 + expectedLevelOffset []int64 + }{ + { + dataSize: 100, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + dataAndTreeInSameFile: false, + expectedDigestSize: 32, + expectedLevelOffset: []int64{0}, + }, + { + dataSize: 100, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + dataAndTreeInSameFile: false, + expectedDigestSize: 64, + expectedLevelOffset: []int64{0}, + }, + { + dataSize: 100, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + dataAndTreeInSameFile: true, + expectedDigestSize: 32, + expectedLevelOffset: []int64{usermem.PageSize}, + }, + { + dataSize: 100, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + dataAndTreeInSameFile: true, + expectedDigestSize: 64, + expectedLevelOffset: []int64{usermem.PageSize}, + }, + { + dataSize: 1000000, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + dataAndTreeInSameFile: false, + expectedDigestSize: 32, + expectedLevelOffset: []int64{0, 2 * usermem.PageSize, 3 * usermem.PageSize}, + }, + { + dataSize: 1000000, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + dataAndTreeInSameFile: false, + expectedDigestSize: 64, + expectedLevelOffset: []int64{0, 4 * usermem.PageSize, 5 * usermem.PageSize}, + }, + { + dataSize: 1000000, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + dataAndTreeInSameFile: true, + expectedDigestSize: 32, + expectedLevelOffset: []int64{245 * usermem.PageSize, 247 * usermem.PageSize, 248 * usermem.PageSize}, + }, + { + dataSize: 1000000, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + dataAndTreeInSameFile: true, + expectedDigestSize: 64, + expectedLevelOffset: []int64{245 * usermem.PageSize, 249 * usermem.PageSize, 250 * usermem.PageSize}, + }, + { + dataSize: 4096 * int64(usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + dataAndTreeInSameFile: false, + expectedDigestSize: 32, + expectedLevelOffset: []int64{0, 32 * usermem.PageSize, 33 * usermem.PageSize}, + }, + { + dataSize: 4096 * int64(usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + dataAndTreeInSameFile: false, + expectedDigestSize: 64, + expectedLevelOffset: []int64{0, 64 * usermem.PageSize, 65 * usermem.PageSize}, + }, + { + dataSize: 4096 * int64(usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + dataAndTreeInSameFile: true, + expectedDigestSize: 32, + expectedLevelOffset: []int64{4096 * usermem.PageSize, 4128 * usermem.PageSize, 4129 * usermem.PageSize}, + }, + { + dataSize: 4096 * int64(usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + dataAndTreeInSameFile: true, + expectedDigestSize: 64, + expectedLevelOffset: []int64{4096 * usermem.PageSize, 4160 * usermem.PageSize, 4161 * usermem.PageSize}, + }, + } + + for _, tc := range testCases { + t.Run(fmt.Sprintf("%d", tc.dataSize), func(t *testing.T) { + l, err := InitLayout(tc.dataSize, tc.hashAlgorithms, tc.dataAndTreeInSameFile) + if err != nil { + t.Fatalf("Failed to InitLayout: %v", err) + } + if l.blockSize != int64(usermem.PageSize) { + t.Errorf("Got blockSize %d, want %d", l.blockSize, usermem.PageSize) + } + if l.digestSize != tc.expectedDigestSize { + t.Errorf("Got digestSize %d, want %d", l.digestSize, sha256DigestSize) + } + if l.numLevels() != len(tc.expectedLevelOffset) { + t.Errorf("Got levels %d, want %d", l.numLevels(), len(tc.expectedLevelOffset)) + } + for i := 0; i < l.numLevels() && i < len(tc.expectedLevelOffset); i++ { + if l.levelOffset[i] != tc.expectedLevelOffset[i] { + t.Errorf("Got levelStart[%d] %d, want %d", i, l.levelOffset[i], tc.expectedLevelOffset[i]) + } + } + }) + } +} + +const ( + defaultName = "merkle_test" + defaultMode = 0644 + defaultUID = 0 + defaultGID = 0 +) + +// bytesReadWriter is used to read from/write to/seek in a byte array. Unlike +// bytes.Buffer, it keeps the whole buffer during read so that it can be reused. +type bytesReadWriter struct { + // bytes contains the underlying byte array. + bytes []byte + // readPos is the currently location for Read. Write always appends to + // the end of the array. + readPos int +} + +func (brw *bytesReadWriter) Write(p []byte) (int, error) { + brw.bytes = append(brw.bytes, p...) + return len(p), nil +} + +func (brw *bytesReadWriter) ReadAt(p []byte, off int64) (int, error) { + bytesRead := copy(p, brw.bytes[off:]) + if bytesRead == 0 { + return bytesRead, io.EOF + } + return bytesRead, nil +} + +func TestGenerate(t *testing.T) { + // The input data has size dataSize. It starts with the data in startWith, + // and all other bytes are zeroes. + testCases := []struct { + data []byte + hashAlgorithms int + expectedHash []byte + }{ + { + data: bytes.Repeat([]byte{0}, usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + expectedHash: []byte{64, 253, 58, 72, 192, 131, 82, 184, 193, 33, 108, 142, 43, 46, 179, 134, 244, 21, 29, 190, 14, 39, 66, 129, 6, 46, 200, 211, 30, 247, 191, 252}, + }, + { + data: bytes.Repeat([]byte{0}, usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + expectedHash: []byte{14, 27, 126, 158, 9, 94, 163, 51, 243, 162, 82, 167, 183, 127, 93, 121, 221, 23, 184, 59, 104, 166, 111, 49, 161, 195, 229, 111, 121, 201, 233, 68, 10, 154, 78, 142, 154, 236, 170, 156, 110, 167, 15, 144, 155, 97, 241, 235, 202, 233, 246, 217, 138, 88, 152, 179, 238, 46, 247, 185, 125, 20, 101, 201}, + }, + { + data: bytes.Repeat([]byte{0}, 128*usermem.PageSize+1), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + expectedHash: []byte{182, 223, 218, 62, 65, 185, 160, 219, 93, 119, 186, 88, 205, 32, 122, 231, 173, 72, 78, 76, 65, 57, 177, 146, 159, 39, 44, 123, 230, 156, 97, 26}, + }, + { + data: bytes.Repeat([]byte{0}, 128*usermem.PageSize+1), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + expectedHash: []byte{55, 204, 240, 1, 224, 252, 58, 131, 251, 174, 45, 140, 107, 57, 118, 11, 18, 236, 203, 204, 19, 59, 27, 196, 3, 78, 21, 7, 22, 98, 197, 128, 17, 128, 90, 122, 54, 83, 253, 108, 156, 67, 59, 229, 236, 241, 69, 88, 99, 44, 127, 109, 204, 183, 150, 232, 187, 57, 228, 137, 209, 235, 241, 172}, + }, + { + data: []byte{'a'}, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + expectedHash: []byte{28, 201, 8, 36, 150, 178, 111, 5, 193, 212, 129, 205, 206, 124, 211, 90, 224, 142, 81, 183, 72, 165, 243, 240, 242, 241, 76, 127, 101, 61, 63, 11}, + }, + { + data: []byte{'a'}, + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + expectedHash: []byte{207, 233, 114, 94, 113, 212, 243, 160, 59, 232, 226, 77, 28, 81, 176, 61, 211, 213, 222, 190, 148, 196, 90, 166, 237, 56, 113, 148, 230, 154, 23, 105, 14, 97, 144, 211, 12, 122, 226, 207, 167, 203, 136, 193, 38, 249, 227, 187, 92, 238, 101, 97, 170, 255, 246, 209, 246, 98, 241, 150, 175, 253, 173, 206}, + }, + { + data: bytes.Repeat([]byte{'a'}, usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256, + expectedHash: []byte{106, 58, 160, 152, 41, 68, 38, 108, 245, 74, 177, 84, 64, 193, 19, 176, 249, 86, 27, 193, 85, 164, 99, 240, 79, 104, 148, 222, 76, 46, 191, 79}, + }, + { + data: bytes.Repeat([]byte{'a'}, usermem.PageSize), + hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512, + expectedHash: []byte{110, 103, 29, 250, 27, 211, 235, 119, 112, 65, 49, 156, 6, 92, 66, 105, 133, 1, 187, 172, 169, 13, 186, 34, 105, 72, 252, 131, 12, 159, 91, 188, 79, 184, 240, 227, 40, 164, 72, 193, 65, 31, 227, 153, 191, 6, 117, 42, 82, 122, 33, 255, 92, 215, 215, 249, 2, 131, 170, 134, 39, 192, 222, 33}, + }, + } + + for _, tc := range testCases { + t.Run(fmt.Sprintf("%d:%v", len(tc.data), tc.data[0]), func(t *testing.T) { + for _, dataAndTreeInSameFile := range []bool{false, true} { + var tree bytesReadWriter + params := GenerateParams{ + Size: int64(len(tc.data)), + Name: defaultName, + Mode: defaultMode, + UID: defaultUID, + GID: defaultGID, + HashAlgorithms: tc.hashAlgorithms, + TreeReader: &tree, + TreeWriter: &tree, + DataAndTreeInSameFile: dataAndTreeInSameFile, + } + if dataAndTreeInSameFile { + tree.Write(tc.data) + params.File = &tree + } else { + params.File = &bytesReadWriter{ + bytes: tc.data, + } + } + hash, err := Generate(¶ms) + if err != nil { + t.Fatalf("Got err: %v, want nil", err) + } + + if !bytes.Equal(hash, tc.expectedHash) { + t.Errorf("Got hash: %v, want %v", hash, tc.expectedHash) + } + } + }) + } +} + +func TestVerify(t *testing.T) { + // The input data has size dataSize. The portion to be verified ranges from + // verifyStart with verifySize. A bit is flipped in outOfRangeByteIndex to + // confirm that modifications outside the verification range does not cause + // issue. And a bit is flipped in modifyByte to confirm that + // modifications in the verification range is caught during verification. + testCases := []struct { + dataSize int64 + verifyStart int64 + verifySize int64 + // A byte in input data is modified during the test. If the + // modified byte falls in verification range, Verify should + // fail, otherwise Verify should still succeed. + modifyByte int64 + modifyName bool + modifyMode bool + modifyUID bool + modifyGID bool + shouldSucceed bool + }{ + // Verify range start outside the data range should fail. + { + dataSize: usermem.PageSize, + verifyStart: usermem.PageSize, + verifySize: 1, + modifyByte: 0, + shouldSucceed: false, + }, + // Verifying range is valid if it starts inside data and ends + // outside data range, in that case start to the end of data is + // verified. + { + dataSize: usermem.PageSize, + verifyStart: 0, + verifySize: 2 * usermem.PageSize, + modifyByte: 0, + shouldSucceed: false, + }, + // Invalid verify range (negative size) should fail. + { + dataSize: usermem.PageSize, + verifyStart: 1, + verifySize: -1, + modifyByte: 0, + shouldSucceed: false, + }, + // 0 verify size should only verify metadata. + { + dataSize: usermem.PageSize, + verifyStart: 0, + verifySize: 0, + modifyByte: 0, + shouldSucceed: true, + }, + // Modified name should fail verification. + { + dataSize: usermem.PageSize, + verifyStart: 0, + verifySize: 0, + modifyByte: 0, + modifyName: true, + shouldSucceed: false, + }, + // Modified mode should fail verification. + { + dataSize: usermem.PageSize, + verifyStart: 0, + verifySize: 0, + modifyByte: 0, + modifyMode: true, + shouldSucceed: false, + }, + // Modified UID should fail verification. + { + dataSize: usermem.PageSize, + verifyStart: 0, + verifySize: 0, + modifyByte: 0, + modifyUID: true, + shouldSucceed: false, + }, + // Modified GID should fail verification. + { + dataSize: usermem.PageSize, + verifyStart: 0, + verifySize: 0, + modifyByte: 0, + modifyGID: true, + shouldSucceed: false, + }, + // The test cases below use a block-aligned verify range. + // Modifying a byte in the verified range should cause verify + // to fail. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4 * usermem.PageSize, + verifySize: usermem.PageSize, + modifyByte: 4 * usermem.PageSize, + shouldSucceed: false, + }, + // Modifying a byte before the verified range should not cause + // verify to fail. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4 * usermem.PageSize, + verifySize: usermem.PageSize, + modifyByte: 4*usermem.PageSize - 1, + shouldSucceed: true, + }, + // Modifying a byte after the verified range should not cause + // verify to fail. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4 * usermem.PageSize, + verifySize: usermem.PageSize, + modifyByte: 5 * usermem.PageSize, + shouldSucceed: true, + }, + // The tests below use a non-block-aligned verify range. + // Modifying a byte at strat of verify range should cause + // verify to fail. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4*usermem.PageSize + 123, + verifySize: 2 * usermem.PageSize, + modifyByte: 4*usermem.PageSize + 123, + shouldSucceed: false, + }, + // Modifying a byte at the end of verify range should cause + // verify to fail. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4*usermem.PageSize + 123, + verifySize: 2 * usermem.PageSize, + modifyByte: 6*usermem.PageSize + 123, + shouldSucceed: false, + }, + // Modifying a byte in the middle verified block should cause + // verify to fail. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4*usermem.PageSize + 123, + verifySize: 2 * usermem.PageSize, + modifyByte: 5*usermem.PageSize + 123, + shouldSucceed: false, + }, + // Modifying a byte in the first block in the verified range + // should cause verify to fail, even the modified bit itself is + // out of verify range. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4*usermem.PageSize + 123, + verifySize: 2 * usermem.PageSize, + modifyByte: 4*usermem.PageSize + 122, + shouldSucceed: false, + }, + // Modifying a byte in the last block in the verified range + // should cause verify to fail, even the modified bit itself is + // out of verify range. + { + dataSize: 8 * usermem.PageSize, + verifyStart: 4*usermem.PageSize + 123, + verifySize: 2 * usermem.PageSize, + modifyByte: 6*usermem.PageSize + 124, + shouldSucceed: false, + }, + } + + for _, tc := range testCases { + t.Run(fmt.Sprintf("%d", tc.modifyByte), func(t *testing.T) { + data := make([]byte, tc.dataSize) + // Generate random bytes in data. + rand.Read(data) + + for _, hashAlgorithms := range []int{linux.FS_VERITY_HASH_ALG_SHA256, linux.FS_VERITY_HASH_ALG_SHA512} { + for _, dataAndTreeInSameFile := range []bool{false, true} { + var tree bytesReadWriter + genParams := GenerateParams{ + Size: int64(len(data)), + Name: defaultName, + Mode: defaultMode, + UID: defaultUID, + GID: defaultGID, + HashAlgorithms: hashAlgorithms, + TreeReader: &tree, + TreeWriter: &tree, + DataAndTreeInSameFile: dataAndTreeInSameFile, + } + if dataAndTreeInSameFile { + tree.Write(data) + genParams.File = &tree + } else { + genParams.File = &bytesReadWriter{ + bytes: data, + } + } + hash, err := Generate(&genParams) + if err != nil { + t.Fatalf("Generate failed: %v", err) + } + + // Flip a bit in data and checks Verify results. + var buf bytes.Buffer + data[tc.modifyByte] ^= 1 + verifyParams := VerifyParams{ + Out: &buf, + File: bytes.NewReader(data), + Tree: &tree, + Size: tc.dataSize, + Name: defaultName, + Mode: defaultMode, + UID: defaultUID, + GID: defaultGID, + HashAlgorithms: hashAlgorithms, + ReadOffset: tc.verifyStart, + ReadSize: tc.verifySize, + Expected: hash, + DataAndTreeInSameFile: dataAndTreeInSameFile, + } + if tc.modifyName { + verifyParams.Name = defaultName + "abc" + } + if tc.modifyMode { + verifyParams.Mode = defaultMode + 1 + } + if tc.modifyUID { + verifyParams.UID = defaultUID + 1 + } + if tc.modifyGID { + verifyParams.GID = defaultGID + 1 + } + if tc.shouldSucceed { + n, err := Verify(&verifyParams) + if err != nil && err != io.EOF { + t.Errorf("Verification failed when expected to succeed: %v", err) + } + if n != tc.verifySize { + t.Errorf("Got Verify output size %d, want %d", n, tc.verifySize) + } + if int64(buf.Len()) != tc.verifySize { + t.Errorf("Got Verify output buf size %d, want %d,", buf.Len(), tc.verifySize) + } + if !bytes.Equal(data[tc.verifyStart:tc.verifyStart+tc.verifySize], buf.Bytes()) { + t.Errorf("Incorrect output buf from Verify") + } + } else { + if _, err := Verify(&verifyParams); err == nil { + t.Errorf("Verification succeeded when expected to fail") + } + } + } + } + }) + } +} + +func TestVerifyRandom(t *testing.T) { + rand.Seed(time.Now().UnixNano()) + // Use a random dataSize. Minimum size 2 so that we can pick a random + // portion from it. + dataSize := rand.Int63n(200*usermem.PageSize) + 2 + data := make([]byte, dataSize) + // Generate random bytes in data. + rand.Read(data) + + for _, hashAlgorithms := range []int{linux.FS_VERITY_HASH_ALG_SHA256, linux.FS_VERITY_HASH_ALG_SHA512} { + for _, dataAndTreeInSameFile := range []bool{false, true} { + var tree bytesReadWriter + genParams := GenerateParams{ + Size: int64(len(data)), + Name: defaultName, + Mode: defaultMode, + UID: defaultUID, + GID: defaultGID, + HashAlgorithms: hashAlgorithms, + TreeReader: &tree, + TreeWriter: &tree, + DataAndTreeInSameFile: dataAndTreeInSameFile, + } + + if dataAndTreeInSameFile { + tree.Write(data) + genParams.File = &tree + } else { + genParams.File = &bytesReadWriter{ + bytes: data, + } + } + hash, err := Generate(&genParams) + if err != nil { + t.Fatalf("Generate failed: %v", err) + } + + // Pick a random portion of data. + start := rand.Int63n(dataSize - 1) + size := rand.Int63n(dataSize) + 1 + + var buf bytes.Buffer + verifyParams := VerifyParams{ + Out: &buf, + File: bytes.NewReader(data), + Tree: &tree, + Size: dataSize, + Name: defaultName, + Mode: defaultMode, + UID: defaultUID, + GID: defaultGID, + HashAlgorithms: hashAlgorithms, + ReadOffset: start, + ReadSize: size, + Expected: hash, + DataAndTreeInSameFile: dataAndTreeInSameFile, + } + + // Checks that the random portion of data from the original data is + // verified successfully. + n, err := Verify(&verifyParams) + if err != nil && err != io.EOF { + t.Errorf("Verification failed for correct data: %v", err) + } + if size > dataSize-start { + size = dataSize - start + } + if n != size { + t.Errorf("Got Verify output size %d, want %d", n, size) + } + if int64(buf.Len()) != size { + t.Errorf("Got Verify output buf size %d, want %d", buf.Len(), size) + } + if !bytes.Equal(data[start:start+size], buf.Bytes()) { + t.Errorf("Incorrect output buf from Verify") + } + + // Verify that modified metadata should fail verification. + buf.Reset() + verifyParams.Name = defaultName + "abc" + if _, err := Verify(&verifyParams); err == nil { + t.Error("Verify succeeded for modified metadata, expect failure") + } + + // Flip a random bit in randPortion, and check that verification fails. + buf.Reset() + randBytePos := rand.Int63n(size) + data[start+randBytePos] ^= 1 + verifyParams.File = bytes.NewReader(data) + verifyParams.Name = defaultName + + if _, err := Verify(&verifyParams); err == nil { + t.Error("Verification succeeded for modified data, expect failure") + } + } + } +} |