Paper 2019/192

An Omission-Tolerant Cryptographic Checksum

Francisco Corella and Karen Lewison

Abstract

A cryptographic checksum is a small data item that is computed from a data structure and can be used to prevent undetected intentional modification by making it difficult for an adversary to construct a different data structure that has the same checksum. We broaden the concept of a checksum to include the concept of a data item intended to prevent certain modifications while tolerating others. An omission-tolerant checksum is computed from an encoding of a set and does not change when the encoding is modified to omit elements from the set, while making it difficult for an adversary to modify an original, i.e. unmodified, encoding in any other way without invalidating the checksum. We use the root label of a typed hash tree to implement an omission-tolerant checksum. A typed hash tree is a variation on a Merkle tree, where each node has a type and a label. The root label of a typed hash tree does not change when a subtree is pruned from the tree. The same is true for a Merkle tree, but in a Merkle tree this a "bug" to be mitigated, while in a typed hash tree it is a "feature" that makes it possible to use the label of the root node as an omission-tolerant checksum for a set of key-value pairs. To do so, we encode each key-value pair as the type and label of a leaf node of an incomplete typed hash tree without internal-node labels, then serialize the tree to obtain a bit-string encoding of the set. To compute the checksum on the encoding we deserialize the bit-string, compute the missing internal nodes, and output the label of the root node as the checksum. We use Boneh and Shoup's system parameterization and attack game methodology to prove that, given an original encoding of a set of key-value pairs, an efficient adversary has a negligible probability of producing a modified encoding that represents a set of key-value pairs other than a subset of the given one and that has the same checksum.

Note: In this revision we have made one change. In step 5 of the game protocol of Game 4 we have replaced the parenthetical remark "(The adversary can compute Z and z from y as needed.)" with "(The adversary can compute z from y as needed.)"