Segmented hashing for secure data modification
AssigneeAmazon Technologies, Inc.
InventorsDavid Carl Salyers, James Christopher Sorenson, III, Ankur Khetrapal
Life of this patent
Estimating the term…
Abstract
Methods and apparatus for secure data modification using segmented hashing are disclosed. An intermediate device on a data path between a storage service and a client receives a modification request for a data segment of a data chunk of a storage object. The device generates a new chunk hash value for the chunk based on an original chunk hash value of the chunk, an original segment hash value of the segment to be modified, and a new segment hash value computed based on the modification. The device generates a modified version of the chunk based on the modification request, and uploads the modified version and the new chunk hash value to the storage service.
Claims20
A method, comprising:
- identifying, by a computing device, a number of segments of a data chunk;
- generating, by the computing device, hash values for respective segments of the data chunk;
- generating, by the computing device, intermediate hash values for the respective segments at least by multiplying the hash values by respective values;
- in response to determining that one or more of the intermediate hash values exceeds a size limit, generating, by the computing device, other intermediate hash values for the respective segments based on the intermediate hash values for the respective segments, wherein the other intermediate hash values do not exceed the size limit;
- generating, by the computing device, additional intermediate hash values for the respective segments by rotating individual ones of the other intermediate hash values by a respective number of bits;
- and
- generating, by the computing device, a hash value for the data chunk based on the additional intermediate hash values for the respective segments.
A system comprising one or more computing devices, wherein the one or more computing devices are configured to:
- identify a number of segments of a data chunk;
- generate hash values for respective segments of the data chunk;
- generate intermediate hash values for the respective segments at least by multiplication of the hash values by respective values;
- in response to a determination that one or more of the intermediate hash values exceeds a size limit, generate other intermediate hash values for the respective segments based on the intermediate hash values for the respective segments, wherein the other intermediate hash values do not exceed the size limit;
- generate additional intermediate hash values for the respective segments by rotation of individual ones of the other intermediate hash values by a respective number of bits;
- and
- generate a hash value for the data chunk based on the additional intermediate hash values for the respective segments.
A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:
- identify a number of segments of a data chunk;
- generate hash values for respective segments of the data chunk;
- generate intermediate hash values for the respective segments at least by multiplication of the hash values by respective values;
- in response to a determination that one or more of the intermediate hash values exceeds a size limit, generate other intermediate hash values for the respective segments based on the intermediate hash values for the respective segments, wherein the other intermediate hash values do not exceed the size limit;
- generate additional intermediate hash values for the respective segments by rotation of individual ones of the other intermediate hash values by a respective number of bits;
- and
- generate a hash value for the data chunk based on the additional intermediate hash values for the respective segments.
Dependencies are inferred from the claim text.