Paper 2019/192
An OmissionTolerant 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 omissiontolerant 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 omissiontolerant 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 omissiontolerant checksum for a set of keyvalue pairs. To do so, we encode each keyvalue pair as the type and label of a leaf node of an incomplete typed hash tree without internalnode labels, then serialize the tree to obtain a bitstring encoding of the set. To compute the checksum on the encoding we deserialize the bitstring, 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 keyvalue pairs, an efficient adversary has a negligible probability of producing a modified encoding that represents a set of keyvalue 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.)"
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 omissiontolerant checksumintegrity protectiontyped hash treekeyless hash functionprovable securityasymptotic securitysystem parameterization
 Contact author(s)

fcorella @ pomcor com
kplewison @ pomcor com  History
 20190325: last of 3 revisions
 20190226: received
 See all versions
 Short URL
 https://ia.cr/2019/192
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/192, author = {Francisco Corella and Karen Lewison}, title = {An OmissionTolerant Cryptographic Checksum}, howpublished = {Cryptology ePrint Archive, Paper 2019/192}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/192}}, url = {https://eprint.iacr.org/2019/192} }