Incremental Multiset Hash Functions and their Application to Memory Integrity Checking

We introduce a new cryptographic tool: multiset hash functions. Unlike standard hash functions which take strings as input, multiset hash functions operate on multisets (or sets). They map multisets of arbitrary finite size to strings (hashes) of fixed length. They are incremental in that, when new...

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính: Clarke, Dwaine, Devadas, Srinivas, van Dijk, Marten, Gassend, Blaise, Suh, G. Edward
Được phát hành: 2023
Truy cập trực tuyến:https://hdl.handle.net/1721.1/149987
_version_ 1826202598021005312
author Clarke, Dwaine
Devadas, Srinivas
van Dijk, Marten
Gassend, Blaise
Suh, G. Edward
author_facet Clarke, Dwaine
Devadas, Srinivas
van Dijk, Marten
Gassend, Blaise
Suh, G. Edward
author_sort Clarke, Dwaine
collection MIT
description We introduce a new cryptographic tool: multiset hash functions. Unlike standard hash functions which take strings as input, multiset hash functions operate on multisets (or sets). They map multisets of arbitrary finite size to strings (hashes) of fixed length. They are incremental in that, when new members are added to the multiset, the hash can be updated in time proportional to the change. The functions may be multiset-collision resistant in that it is diÔøΩcult to find two multisets which produce the same hash, or just set-collision resistant in that it is diÔøΩcult to find a set and a multiset which produce the same hash. In particular, we introduce four multiset hash functions, each with its own advantages. MSet-XOR-Hash uses the XOR operation and is very eÔøΩcient; however, it uses a secret key and is only set-collision resistant. MSet-Add-Hash uses addition modulo a large integer and, thus, is slightly less eÔøΩcient than MSet-XOR-Hash; MSet-Add-Hash also uses a secret key but it is multiset-collision resistant. MSet-Mu-Hash uses finite field arithmetic and is not as eÔøΩcient as the other two hash functions; however, MSet-Mu-Hash is multiset-collision resistant, and unlike the other two hash functions, does not require a secret key. MSet-VAdd-Hash is more eÔøΩcient than MSet-Mu-Hash; it is also multiset-collision resistant, and does not use a secret key, but the hashes it produces are significantly longer than the hashes of the other functions. The proven security of MSet-XOR-Hash and MSet-Add-Hash is quantitative. We reduce the hardness of finding collisions to the hardness of breaking the underlying pseudorandom functions. The proven security of MSet-Mu-Hash is in the random oracle model and is based on the hardness of the discrete logarithm problem. The proven security of MSet-VAdd-Hash is also in the random oracle model and is based on the hardness of the worst-case shortest vector problem. We demonstrate how set-collision resistant multiset hash functions make an existing oÔøΩine memory integrity checker secure against active adversaries. We improve on this checker such that it can use smaller time stamps without increasing the frequency of checks. The improved checker uses multiset-collision resistant hash functions
first_indexed 2024-09-23T12:10:11Z
id mit-1721.1/149987
institution Massachusetts Institute of Technology
last_indexed 2024-09-23T12:10:11Z
publishDate 2023
record_format dspace
spelling mit-1721.1/1499872023-03-30T03:46:11Z Incremental Multiset Hash Functions and their Application to Memory Integrity Checking Clarke, Dwaine Devadas, Srinivas van Dijk, Marten Gassend, Blaise Suh, G. Edward We introduce a new cryptographic tool: multiset hash functions. Unlike standard hash functions which take strings as input, multiset hash functions operate on multisets (or sets). They map multisets of arbitrary finite size to strings (hashes) of fixed length. They are incremental in that, when new members are added to the multiset, the hash can be updated in time proportional to the change. The functions may be multiset-collision resistant in that it is diÔøΩcult to find two multisets which produce the same hash, or just set-collision resistant in that it is diÔøΩcult to find a set and a multiset which produce the same hash. In particular, we introduce four multiset hash functions, each with its own advantages. MSet-XOR-Hash uses the XOR operation and is very eÔøΩcient; however, it uses a secret key and is only set-collision resistant. MSet-Add-Hash uses addition modulo a large integer and, thus, is slightly less eÔøΩcient than MSet-XOR-Hash; MSet-Add-Hash also uses a secret key but it is multiset-collision resistant. MSet-Mu-Hash uses finite field arithmetic and is not as eÔøΩcient as the other two hash functions; however, MSet-Mu-Hash is multiset-collision resistant, and unlike the other two hash functions, does not require a secret key. MSet-VAdd-Hash is more eÔøΩcient than MSet-Mu-Hash; it is also multiset-collision resistant, and does not use a secret key, but the hashes it produces are significantly longer than the hashes of the other functions. The proven security of MSet-XOR-Hash and MSet-Add-Hash is quantitative. We reduce the hardness of finding collisions to the hardness of breaking the underlying pseudorandom functions. The proven security of MSet-Mu-Hash is in the random oracle model and is based on the hardness of the discrete logarithm problem. The proven security of MSet-VAdd-Hash is also in the random oracle model and is based on the hardness of the worst-case shortest vector problem. We demonstrate how set-collision resistant multiset hash functions make an existing oÔøΩine memory integrity checker secure against active adversaries. We improve on this checker such that it can use smaller time stamps without increasing the frequency of checks. The improved checker uses multiset-collision resistant hash functions 2023-03-29T15:37:19Z 2023-03-29T15:37:19Z 2003-05 https://hdl.handle.net/1721.1/149987 MIT-LCS-TR-899 application/pdf
spellingShingle Clarke, Dwaine
Devadas, Srinivas
van Dijk, Marten
Gassend, Blaise
Suh, G. Edward
Incremental Multiset Hash Functions and their Application to Memory Integrity Checking
title Incremental Multiset Hash Functions and their Application to Memory Integrity Checking
title_full Incremental Multiset Hash Functions and their Application to Memory Integrity Checking
title_fullStr Incremental Multiset Hash Functions and their Application to Memory Integrity Checking
title_full_unstemmed Incremental Multiset Hash Functions and their Application to Memory Integrity Checking
title_short Incremental Multiset Hash Functions and their Application to Memory Integrity Checking
title_sort incremental multiset hash functions and their application to memory integrity checking
url https://hdl.handle.net/1721.1/149987
work_keys_str_mv AT clarkedwaine incrementalmultisethashfunctionsandtheirapplicationtomemoryintegritychecking
AT devadassrinivas incrementalmultisethashfunctionsandtheirapplicationtomemoryintegritychecking
AT vandijkmarten incrementalmultisethashfunctionsandtheirapplicationtomemoryintegritychecking
AT gassendblaise incrementalmultisethashfunctionsandtheirapplicationtomemoryintegritychecking
AT suhgedward incrementalmultisethashfunctionsandtheirapplicationtomemoryintegritychecking