Main | Project presentation | Architecture | Data Structures | Security | References | Project Page

Data Structures in SecCubes

SecCube records

From a high level view, a SecCube can be seen as a collection of records. There are three different type of records:

• an INIT record: this record is unique in a given SecCube. It stores configuration data for the SecCube. It is written at initialization.
• MAP records: those records help retrieve end-user's data. They'll be detailed below. It is possible to have several MAP records per SecCube. In particular, this occurs as the SecCube grows in size.
• DATA records: those records contain end-user's payload. Of course, there are several DATA records in a given SecCube. Each time the end-user adds data to the SecCube, this adds a DATA record. So, DATA records are end-users data unit.

An important fact about record's is that their size is variable. For INIT and MAP records, their size is fixed at initialization time, and cannot be changed (well, it's possible, but that requires offline conversion tools). For DATA records, obviously, their size depends on end-user's payload's size.

SecCube blocks

Physical media usually do not operate on variable size data units such as records. They rather use fixed size data units such as sectors on hard disks, or cells in Flash memories. In this project, we generally name fixed size data units as blocks. All SecCube records (INIT, MAP and DATA records) are encapsulated in SecCube blocks. A simplified explanation is that they are cut into blocks, so that all blocks concatenated build a record. This is slightly oversimplified, because actually, all blocks begin with a block header. So, this means that actually a given record is mapped on several blocks such that block 1 has a block header + the beginning of the record, block 2 has a block header + some more data of the record etc.

Blocks are identified by block identifiers. The implementation of block identifiers depends on the underlying support. It can be a physical address on the media, or an offset for instance.

The structure of a block is detailed in blockcube.h. Basically, it contains:

• a block header (blockheader_t). That block header contains a record type - to specify what kind of record the block is encapsulating (INIT, MAP or DATA), and also a next block identifier. The next block identifier field chains blocks of a given record. The last block of a given record is chained back to a 'null' block identifier.
• part of a record. If the record is small enough to fit in a single block, then the entire record is written.

INIT record

• an INIT record header (initheader_t)
• an armoured OpenPGP public key
• an encryption storage key, encrypted by the previous public key. This field does not exist if the SecCube is not set for encryption.
• an MAC key, encrypted by the public key
• the MAC of the entire INIT record

The size of an INIT record depends on selected algorithms and public key length specified in the INIT record header. The location of each variable size field (public key, encryption key, MAC key and MAC) is specified by parameters of the INIT record header.

MAP record

• the MAC of an entire MAP record.
• a table of MAP entries which associate a record identifier to a block identifier. The structure of MAP entries is detailed in blockcube.h

A MAP record always fits in a single block, so it is also called a MAP block. The reason a MAP record does not span over several blocks, is that then, it'd be necessary to keep a list of all MAP records. The reason we don't have a single MAP record is that, when new data is added to the SecCube and that requires a new MAP entry, we do not want to recompute the entire MAC record, because that would mean re-writting the MAP record too often (and might damage the corresponding underlying cell).

DATA record

• a data record header (see blockcube.h). In particular, that also stores end-user's record's label.
• payload's hash. This field does not exist if the hash option isn't set
• payload's MAC. Same, this is only present if MACing is enabled
• payload's timestamp. Same.
• and finally, the payload - possibly encrypted if encryption is enabled

Chaining blocks

• a single INIT record. This record is always locating at the beginning of the SecCube. Its first block has identifier 0.
• several MAP records. At first, a SecCube is created with a single pre-allocated MAP record. This MAP record is pre-filled with appropriate mappings to 'foreseen' DATA blocks. The idea is to write the MAP block only once for wear leveling issues (or a small amount of times). Then, if other MAP records are required (to address unreferenced or new records), the new MAP record is chained to the last MAP block using the next block field of the generic header (indeed, a MAP record fits in a single block, so next MAP block = next MAP record). The last MAP block is chained to block identifier 0.
• several DATA records. Each entry of MAP record points to the first block of a record. If records span over multiple blocks, they are chained using the next block field of the generic header. The last DATA block of a given record is chained to block identifier 0. A 'DATA' block may be:
  • used: such DATA blocks are filled with data.
  • linked, but free: this DATA block is referenced by a MAP block but does not contain any relevant data.
  • unlinked: this DATA block is not used yet, and not linked to any MAP block yet either. It may be used by new MAP blocks.

Note that all blocks begin with a generic header, but only the first 'DATA' block of a given record begins with record identifier and payload size (etc). This means that the record structure is actually encapsulated in DATA blocks, and concatenating each content of 'DATA' blocks (except headers) builds a record structure.