Optimized hierarchical integrity protection for stored data

1. A method for protecting an integrity of data stored in a storage medium comprising a controller, the storage medium configured to be accessed in access units, wherein an access unit is a page of memory of the storage medium that may be written to or read from in a single write or read operation, the method comprising:

receiving, with the controller, data items from a host device for storage in the storage medium;

grouping, with the controller, based on a size of an access unit of the storage medium, the data items into a plurality of groups of the same size, wherein:

at least some of the groups of the plurality of groups comprise a pluralities of the data items;

the plurality of groups are aligned with access units of the storage medium; and

each group of the plurality of groups occupies an identical number of pages of memory in the storage medium;

computing, with the controller, a group signature over each group of the plurality of groups, thereby generating multiple group signatures;

computing, with the controller, an upper-level signature over the multiple group signatures; and

storing, with the controller, the plurality of groups of data items, the group signatures, and the upper-level signature in locations in the storage medium, wherein the number of signature levels is statically defined.

2. The method according to claim 1 , wherein grouping the data items into the plurality of groups comprises:

selecting the data items to be included in each group based on a size of the page of memory.

3. The method according to claim 2 , wherein storing the group signatures comprises;

grouping the multiple signatures into two or more signature groups based on the size of the page of memory; and

aligning each of the signature groups with the access units in a location in the storage medium.

4. The method according to claim 1 , wherein computing the upper-level signature comprises:

grouping the group signatures into signature groups for storage in the storage medium;

computing super-signatures over the signature groups; and

calculating the upper-level signature over the super-signatures.

5. The method according to claim 4 , wherein calculating the upper-level signature comprises grouping the super-signatures into two or more super-groups and computing upper-level signatures over the super-signatures in the two or more super-groups, and

wherein the method further comprises arranging the groups of the data items and the super-groups into first and second levels, respectively, of a hierarchy, which comprises at least three levels and culminates in a top level containing a top-level signature computed over the hierarchy according to the number of statically-defined signature levels.

6. The method according to claim 1 , wherein the data items are cryptographic secrets.

7. The method of claim 1 , wherein the storage medium comprises flash memory.

8. The method of claim 1 , wherein at least two of the data items received from the store device for storage in the storage medium are not the same size.

9. The method of claim 1 , wherein the data items received from the host device for storage in the storage medium comprise a media file and a key associated with the media file; and

wherein the media file and the key are grouped in different groups.

10. A storage system configured to be accessed in access units, wherein an access unit is a page of non-volatile memory of the storage system that may be written to or read from in a single write or read operation, the storage system comprising:

a non-volatile memory; and

a processor in communication with the non-volatile memory, the controller configured to:

receive data items from a host device for storage in the non-volatile memory;

group, based on a size of an access unit of the storage system, the data items into a plurality of groups of the same size, wherein the controller groups the data items into the plurality of groups so that:

at least one group of the plurality of groups comprises a plurality of the data items;

the plurality of groups are aligned with access units of the storage system; and

each group of the plurality of groups occupies an identical number of pages of non-volatile memory in the storage system;

compute a group signature over each group of the plurality of similarly-sized groups, thereby generating multiple group signatures;

compute an upper-level signature over the multiple group signatures; and

store in the non-volatile memory the plurality of groups of data items, the group signatures, and the upper-level signature, wherein the number of signature levels is statically defined.

11. The storage system of claim 10 , wherein to group the data items into the plurality of groups, the processor is configured to select the data items to be included in each group based on a size of the page of memory.

12. The storage system of claim 11 , wherein to store the group signatures, the processor is further configured to:

group the multiple signatures into one or more signatures groups based on the size of the page of memory; and

align each of the signature groups with the access units in a location in the non-volatile memory.

13. The storage system of claim 11 , wherein to compute the upper-level signature, the processor is configured to:

group the group signatures into signature groups for storage in the non-volatile memory;

compute super-signatures over the signature groups; and

calculate the upper-level signature over the super-signatures.

14. The storage system of claim 13 , wherein to calculate the upper-level signature, the processor is configured to:

group the super-signatures into two or more super groups; and

compute upper-level signatures over the super-signatures in the two or more super groups.

15. The storage system of claim 14 , wherein the processor is further configured to arrange the groups of the data items and the super-groups into first and second levels, respectively, of a hierarchy, which comprises at least three level and culminates in a top level containing a top-level signatures computed over the hierarchy based on the number of statically-defined signature levels.

16. The storage system of claim 10 , wherein the data items are cryptographic secrets.

17. The storage system of claim 10 , wherein the non-volatile memory comprises flash memory.

18. The storage system of claim 10 , wherein at least two of the data items received from the storage device for storage in the non-volatile memory at not the same size.

19. The storage system of claim 10 , wherein the data items received from the host device for storage in the non-volatile memory comprise a media file and a key associated with the media file; and

wherein the media file and the key are grouped in different groups.