Security Details

2021-12-01: periodic review, format for new site, minor edits
2020-06-04: periodic review, minor edits for clarity
2017-04-14: periodic review, minor changes for clarity
2016-03-10: updated text to match previously listed changes
2016-01-05: whole file hash changed to SHA1
2014-09-30: encrypted dest.db is copied directly to remotes
2013-10-24: Since Jan 2013, dest.conf can be stored in hb.db
2012-12-13: use /dev/random + /dev/urandom for keys because of
long hangs on Linux VMs
2012-11-08: removed public CRC from arc files
2012-09-05: edits before release
2012-05-24: misc typos

HB reads a file system, or selected files, and saves file data, file metadata, and backup metadata to a local backup directory. Data is stored primarily in two places: an encrypted database named hb.db stores metadata, and archive files store encrypted file data.

During backups, HB breaks files into blocks, suppresses redundant blocks, compresses and encrypts blocks, and stores blocks in arc files. Archive files are named arc.v.n, where v is the backup number (version) and n is a sequence number within the backup. Archive files are 100MB by default, but this is configurable. So a backup of 500MB will create arc.0.0 - arc.0.4, each ~100MB. The next backup creates arc.1.0, etc. If remote destinations are configured in dest.conf (a text file), arc files are sent offsite to all remotes during the backup. Local arc files may be deleted during the backup if cache-size-limit is set, the cache becomes full, and the arc files have been sent to all destinations.

File and backup metadata is stored in the hb.db database. File metadata includes Unix permission bits, ACLs, file dates and so on. Backup metadata includes cryptographic hashes for files & blocks, file & block relationships, and block & archive file relationships.

hb.db accumulates historical information for all backups: it knows which blocks are needed to reconstruct version 0 of a file, and which blocks are needed to reconstruct the most recent version. After a backup, the local backup directory has an updated hb.db database and incremental update files are sent to all remote destinations with changes to hb.db.

There are other utilities to remove files from the backup, list files, perform retention, mount a backup as a Unix filesystem, etc.

The security goal of HashBackup is secure remote storage of backup data to untrusted storage providers. Securing local backup data is not a primary goal: if someone has access to a computer, there are many avenues to monitor and attack it, from logging keystrokes to intercepting shared library calls, installing MITM device drivers, and so on.

Some data in HB’s local backup directory stays local, for example, the dedup table and the key in key.conf. Other data may be sent offsite, with the goal of being able to reconstruct the backup in a disaster situation: the computer is stolen, fire, flood, or the hard disk containing the local backup crashes.

The security goals then are to:

Different sites will have different security needs. For example, "remote" storage may be a company-owned FTP server connected over a LAN. Insecure protocols like FTP are supported because the convenience they provide may be more important to a particular customer than the protocol’s security issues. HashBackup supports secure transport methods, but also supports insecure but convenient transport methods.

There are several types of data sent to remote storage:

Two files are never sent offsite, but contain important information that is needed to recover the backup directory from a remote site:

key.conf contains the main key. hb init creates this key, by default using the system random number generators (/dev/random & /dev/urandom) to get a 256-bit key. This is then used to derive the rest of the keys. The key.conf file is never sent offsite. The key may be protected with a passphrase. The permissions are set to read-only for the user running init when the key file is created.

dest.conf is a text file containing remote configuration information. For example, connecting to a remote FTP server requires a host name, port number, user id, and password. Each remote destination will have a section in dest.conf with parameters needed to connect to the remote. dest.conf is not encrypted, so remote account passwords and access tokens are in the clear. It is not possible to use hash codes for passwords in dest.conf, because passwords must be supplied to remote services for validation. Users are encouraged to put very restrictive system access permissions on dest.conf.

For more security, the "hb dest load" command can be used to store the dest.conf file into the encrypted hb.db file, and then the dest.conf file is deleted. For best security, hb.db should also be protected with an admin passphrase and/or main key passphrase to prevent a local user from recovering remote credentials.

Copies of the key.conf and dest.conf text files must be stored separately and/or printed, to be used for disaster recovery (loss of the local backup directory).

HB uses random numbers to generate:

To generate keys, HB first tries to read as much of the key as possible from /dev/random, with a non-blocking read. If this read is unable to return a complete key because the entropy pool is depleted, the rest of the key is read from /dev/urandom. While /dev/random is preferred for key generation, it often blocks for very long times on Linux VMs, especially right after startup, to the point of being unusable. On BSD machines, /dev/random and /dev/urandom are usually equivalent and never block.

The other use of random data is for AES IVs and CBC padding. Up to 32 bytes may be required for each backup data block. This can require a significant amount of random data during backup operations, and might deplete the system’s entropy pools. /dev/urandom is a non-blocking version of /dev/random, but using it also might deplete the system’s entropy pools during backups, especially on Linux VMs.

To prevent system entropy pool depletion, HB uses AES-128 in OFB mode to generate cryptographically secure random numbers. The RNG is seeded with 48 bytes of data from /dev/urandom:

References:

Analysis of Linux RNG: http://www.pinkas.net/PAPERS/gpr06.pdf

Using AES as a CSRNG: Empirical Evidence Concerning AES Peter Hellekalek, Stefan Wegenkittl See section 4, Findings, first 3 paragraphs (RNG mode) https://dl.acm.org/doi/pdf/10.1145/945511.945515

The main sequence of events to use HB is:

For init command hb init -c backupdir:

hb init creates key.conf using the -k and -p options. There are 8 possible combinations, some being more secure than others. The less secure options tend to be more convenient to the user. All options are described here from most secure to least secure. Plus signs are used for "pros" while dash signs are used for "cons".

After the key.conf file is created with one of these combinations of -k and -p, the actual encryption keys are generated. The procedure is:

The backup function reads through the filesystem, breaks files into chunks, stores metadata in hb.db, stores file data in HB archive files, and optionally sends files offsite. Block creation is described here; sending files offsite is described later.

Archive files are sent offsite as is, without modification. The transport method (ftp, rsync, etc) is used to transfer the files and an entry is logged in dest.db on success. Details about the archive file format are discussed later. The integrity protection for archive data is the SHA1 hash stored in hb.db for each block, and the SHA1 hash for each file backed up, also stored in hb.db

Compared to archive files, it’s much harder to send hb.db offsite because it is one large file that grows as backups are added. To avoid using more bandwidth on every backup, hb.db is sent incrementally to remotes (only modified data is sent). These increments are numbered hb.db.0, hb.db.1, etc. the original hb.db is recoered by combining these increments,

Each increment is compressed and encrypted with AES-128, and contains several hashes / HMACs:

The first public SHA1 digest allows anyone to verify the integrity of the hb.db.n file.

Since the public SHA1 digest is over the entire hb.db.n file, it is possible to change the file data and update this digest. The private HMAC-SHA1 digest makes this impossible without knowing the authentication key.

It would still be possible for someone on the remote side to copy hb.db.1 over hb.db.0. This would verify with both the SHA1 and HMAC-SHA1, so another HMAC-SHA1 is added - this one over the original hb.db file. In addition to catching the copy problem, it also may catch software bugs, for example, if an increment is applied improperly, in the wrong order, twice or perhaps not at all.

After the hb.db.n increment file is created, it is uploaded to remotes like archive files.

The dest.db file is a manifest of all files on each remote.

The information in dest.db is not particularly sensitive. It tells which archive files and hb.db.n increments are on which remotes, the size of these files, and the dates they were transferred. It is encrypted like the hb.db file, with AES-128, using the same key as hb.db.

Like archive files, the dest.db file is copied directly to remote destinations. After the copy, more I/O may occur to the local dest.db, so the local and remote dest.db may not always match exactly.

Restoring a file uses local backup data if available, or downloads arc files from remote destinations if necessary.

During restore, hb.db is used to get a file’s original metadata (permissions, etc) and a list of blocks that make up the file data.

For each block in the file:

As a precaution against a padding oracle attack (which doesn’t exactly apply to HB because the key is present, but better to be cautious), no error is raised if an error occurs during depadding or decompression. Instead, the only error reported is "block hash mismatch".

After all blocks have been written to the restored file, the restored file’s SHA1 hash is compared with the original SHA1 hash created during backup. Because this is a file hash, it can detect errors such as restore bugs, dedup problems, and so on. For example, in the very unlikely event there is a SHA1 block hash collision during dedup, this file hash will detect it, although at that point nothing can be done to fix it.

If the local backup directory is lost because the hard drive crashes, the computer is stolen, a fire occurs, etc., the only copy of the backup is on remote destinations. To recover it requires:

If a -p 'ask' or 'env' passphrase was used, then the user needs to know the passphrase too.

Recover connects to a destination chosen by the user and downloads dest.db. This contains a list of all files backed up at the destination. The hb.db.n increments are downloaded, verified, and applied to re-create the original hb.db database. The archive files may or may not be downloaded, depending on options used. When the local backup directory has been re-created, backups and restores can occur again.

Details for recovering each file follow.

The dest.db file is encrypted like hb.db, but is a relatively small file so is sent and retrieved "as is", like arc files.

It would be possible to attack this on the remote by saving a dest.db and re-installing it every day on the remote, ignoring uploads of newer versions. Or, someone administering the remote storage could just delete all of the backup data. These types of attacks are possible whenever remote storage is used, and it is hard to impossible to protect from this kind of remote manipulation. One solution is to send backup data to multiple remote sites, so that if one misbehaves, others are still available.

Another option might be to display, log, or email some kind of HMAC fingerprint for the dest.db and hb.db files after every backup. Recover could display its calculated fingerprint and the user could decide whether they match. This could be implemented at any time, but for now, it seems like overkill and doubtful that users would follow this kind of procedure, so it would add little extra security.

This is basically the reverse process of generating an increment. Before processing an hb.db.n increment file, the SHA1 hash and HMAC of the file is verified. The recovery aborts if there is an error in either of these.

Data from the increment is decrypted, decompressed, and stored in hb.db.

After all increments have been restored, an HMAC is taken over the entire hb.db file. This must match the 2nd HMAC recorded in the last increment. If it doesn’t, an error is displayed and the recover aborts.

HB has a rekey operation to generate a new key.conf key. In its default operation, hb rekey -c backupdir will generate a new 256-bit random key, follow the procedure described above under 'init' for generating keys, then re-encrypt the hb.db and dest.db files. This re-encrypt occurs within a database transaction, so it’s an all-or-nothing operation. A commit makes the changes permanent, the old key file is renamed key.conf.orig, and the new key.conf file is installed. Rekey has special handling for interrupts occurring any time during the rekey operation to rollback the opration.

No archive data is modified on a rekey operation. Archive blocks are encrypted with backup keys, which are stored in hb.db, not key.conf. These are not changed on a rekey operation. The goal of rekey is that anyone with an old copy of key.conf can no longer access the backup after the rekey.

Archive files are a collection of encrypted blocks.

Before any data block is used from an archive file, a SHA1 hash is computed from the decrypted, decompressed data, and then compared to the SHA1 hash originally stored in hb.db for that block. This acts like an HMAC: an attacker changing archive data would also have to update the SHA1 in hb.db, and to do that, would need the key.

An attacker with write access to an archive on a remote could also just delete it, causing data loss. This can be mitigated by copying backups to multiple destinations. They cannot cause incorrect data to be restored because of the block and file hashes stored in hb.db.