License ~~~~~~~ GPL v3 or (at your option) any later version Terminology ~~~~~~~~~~~ base device: this file/device/database holds all macroblocks, our worst case threat-model assumes an adversary can make snapshots of it at will, each block has a number scubed3 partition: a block device whose contents are managed by a scubed3 daemon, writing to a scubed3 partition causes changes to the macroblocks in the base device macroblocks: the smallest bit of information to someone who doesn't have the cryptographic key corresponding to it, a macroblock will either change randomly (each bit changes with a probability of .5) or not at all mesoblock: in a macroblock a series of mesoblocks are stored, along with information on where the mesoblock belongs on the scubed3 partition. indexblock: the first mesoblock in each macroblock contains information about the other mesoblocks in said macroblock ESSIV is a function that turns an uint64_t and two uint32_t's in a 128 bit block for use as IV (see Encryption). indexblocks are encrypted with IV = ESSIV(0, 0, macroblock_number) mesoblocks are encrypted with IV = ESSIV(seqno^nonce, mesoblock_number, macroblock_number), mesoblock_number is 1..255 (with the default sizes), the nonce is random and new for every write of a macroblock (it is in the indexblock) the indexblock IV will repeat when the same disk block is written the mesoblock IV does not repeat, also not when a seqno repeats: when the base device is restored from a backup and used again, or when a torn write is redone (the torn block is ignored, its write is redone in the same block with the same seqno); with the seqno alone, someone who has both versions of such a block (the backup and the device, or the old pages that an SSD keeps) would see the repeated IVs: with CBC the leading 16 byte blocks that are the same in both versions, and that the device was rolled back; the IV only repeats if the nonces of two writes of the same block happen to collide (with their seqnos), with probability about n^2/2^65 for n writes of a block Encryption ~~~~~~~~~~ Every mesoblock (also the indexblock) is encrypted on its own with CBC_ESSIV(AES256): AES-256 in CBC mode, the IV is ESSIV(iv0, iv1, iv2) = AES-256 encryption, with SHA256(key) as key, of the 16 byte block made of iv0 (uint64_t), iv1 and iv2 (uint32_t), big endian. An earlier design used a wide block mode (ABL) for the data, so that a macroblock changes completely or not at all. That is not needed: every write of a macroblock has a new seqno, so every data mesoblock has a new IV and changes completely; the indexblock has a fixed IV, but its first 32 bytes are a hash of the rest of it, which contains the seqno and the nonce, so with CBC the whole indexblock changes as well. To someone without the key, a macroblock changes completely or not at all. The cipher is given as MODE(BLOCKCIPHER) when a partition is opened or created; scubed3ctl always uses CBC_ESSIV(AES256). The other modes, NULL (no encryption) and CBC_PLAIN (CBC with the plain IV), are for testing only. Threat model ~~~~~~~~~~~~ The adversary has full knowledge about the macroblocks (including history) and may even have write access to them. This adversary may have keys to some scubed3 partitions. The goal is to be able to plausibly deny the existence of partitions to which the adversary has no keys. Only paranoia level 3 protects completely against this. We assume the adversary cannot detect read access. The keys of the open partitions are in the memory of scubed3, passphrases pass through scubed3ctl: both lock themselves into memory (mlockall, as root), so they do not go to swap. Hibernation (suspend to disk) writes all memory to swap anyway, locked or not: do not hibernate with partitions open, or use an encrypted swap with a key that is asked at resume. Paranoia levels ~~~~~~~~~~~~~~~ When a new macroblock needs to be selected: Level 0: not paranoid it is selected from all allocated blocks based on its emptiness, the most empty block gets selected (the block with the least live data, at random if there are more of them; not the block that is written now). The garbage collector then copies the least data, so writing is faster, but the order of the writes shows which blocks hold old data. A block with a lot of live data is not rewritten as long as there are emptier blocks, so old versions of discarded data in it stay on disk (they stay dead: their tombstones are kept as long as they are on disk). Switch it on with "paranoia 0" in scubed3ctl. After switching from level 0 to level 1, 2 or 3, the first two writes of every partition go to blocks that were chosen in level 0 (they are chosen in advance, see "Write order"). Level 1: moderately paranoid it is randomly selected from all allocated blocks (see "Write order" below). This hurts write performance. Level 2: just paranoid every write goes to a uniformly random block of the whole base device, whichever partition is written to. (this level of paranoia is required for flash media, this kind of media keeps an internal record about the order in which blocks are written to it, and for an adversary that makes many snapshots) It is only safe if all scubed3 partitions are open in the scubed3 process: blocks that do not belong to an open partition are overwritten with random data, so A PARTITION THAT IS NOT OPEN IS DESTROYED. When a partition needs to write a block, the scheduler draws who writes, until that partition is drawn: an open partition, with a probability proportional to its number of blocks (it writes the block its juggler chose as its next block, uniform over its blocks, see "Write order"; also if it has no new data), or the free space (a uniformly random free block is overwritten with random data, which looks the same as an encrypted block). So the written blocks are independent and uniform over the base device, also while partitions are resized (see "Write order"). The cost: a write of a partition that has a fraction f of the blocks costs 1/f block writes on average, and fsync waits for the turn of the partition. Switch it on with "paranoia 2" in scubed3ctl, after opening ALL partitions (it asks for confirmation, but not when switching between level 2 and 3: then all partitions are still open); closing a partition switches back to level 1 (its blocks would look free, a partition without blocks does not matter). The level is not stored, after starting scubed3 it is level 1. Creating, enlarging, shrinking and removing (shrinking to 0 blocks, see "Shrinking") partitions is safe in level 2 and 3: a new partition is open, and the blocks it gets were free. Level 2 hides where the writes go, not how many there are: if you write only to a hidden partition and reveal the key of another partition, the revealed partition is seen to be rewritten without new data; level 3 hides that. The same goes for the timing of the writes (level 3 hides that too): a partition writes its current block when it is full, and the current block first takes the live data of the next block, so the less live data the next block has, the more new data fits before the next write. Someone who knows when you write data, can see that the writes right after a pause more often go to blocks with little live data (old blocks). Level 3: extremely paranoid as level 2, but the writes are done at random moments that do not depend on what is written: on average RATE bytes per second (default 800 KiB/s, a 4 MiB block every 5.12 seconds), also if nothing is written; the time between two writes is exponentially distributed (a Poisson process). At every write, the scheduler of level 2 draws who writes: an open partition writes its current block (with or without new data), or a free block is overwritten with random data. So the number, the timing and the locations of the writes do not depend on what is written (while scubed3 runs: when it is started and stopped, and when the level changes, can be seen). The cost: - throughput: a partition with a fraction f of the blocks of the base device writes at most f*RATE (the garbage collector takes a part of it), so with the default rate a partition with 10% of the blocks writes at most 80 KiB/s: DO NOT MAKE SMALL PARTITIONS if you want to use level 3 (scubed3ctl shows the maximum of every partition when level 3 is switched on) - waiting: a writer whose current block is full waits for the turn of its partition (on average macroblock size/(f*RATE)), so does fsync; while it waits, writes to the other partitions and control commands wait too (except the paranoia command: you can always switch back), reads go on, also of that partition: its lock is released while it waits (nothing changes it in the meantime, everything that changes a partition waits for the io lock that the writer holds) - wear: RATE all the time; SSDs are rated for a number of terabytes written (TBW), typically a few hundred TB per TB of capacity: rate block (4 MiB) every per day per year 4096 KiB/s 1 s 362 GB 132 TB 800 KiB/s 5.12 s 71 GB 26 TB 400 KiB/s 10.24 s 35 GB 13 TB 128 KiB/s 32 s 11 GB 4.1 TB Switch it on with "paranoia 3 [KIBPS]" in scubed3ctl (in KiB/s, the default rate is set with the option -r of scubed3), after opening ALL partitions; closing a partition switches back to level 1. If the device cannot keep up with the rate, it writes as fast as it can (writes that are more than 4 average intervals plus 1 second late are skipped). Quick start ~~~~~~~~~~~ As root, with a base file (or a block device) filled with random data, the daemon, and scubed3ctl (it asks for the passphrase, twice when creating): # head -c 4G /dev/urandom > /var/lib/scubed3.base # scubed3 -b /var/lib/scubed3.base /mnt/scubed3 # scubed3ctl s3> create secret s3> resize secret 400 s3> luksformat secret s3> mke2fs secret s3> mount secret /mnt/secret ... s3> umount secret (without luksformat the filesystem is directly on the partition, see "LUKS on top of a partition" for why it is recommended; in paranoia level 1, mount, mke2fs and luksformat warn and ask you to type yes, see below) "resize secret 400" gives the partition 400 macroblocks of 4 MiB (a quarter of them is reserved for the garbage collector, so it holds 1.2 GiB); help lists the commands of scubed3ctl. mount opens the partition if needed, and then umount closes it. The files of the open partitions are in /mnt/scubed3, any program can use them, losetup(8) makes block devices of them. Keep the -m and -M options of scubed3 the same forever: the sizes are not stored, with other sizes the partitions are not found. With the default sizes the base device can be at most 408 GiB, larger devices need larger mesoblocks (see "Example calculation of indexblock size"). In paranoia level 2 and 3, do it in this order: open ALL partitions (open NAME), switch the level (paranoia 2), then mount them. The level is not stored, after a start of scubed3 it is level 1, and what is written before the level is switched (mounting a filesystem writes to it) is written in level 1, that shows which blocks belong to which partition. Do not close or umount a partition while you want to stay in level 2 or 3: closing switches back to level 1. scubed3ctl checks the level before mount, mke2fs and luksformat write to a partition: below the recommended level (paranoia= in the configuration file, default 2) it warns, and you have to type yes (the whole word) to go on. LUKS on top of a partition ~~~~~~~~~~~~~~~~~~~~~~~~~~ In paranoia level 2 and 3 all partitions are open, also the ones you do not use now, and an open partition is a file in the directory of scubed3 that anyone with access to the running computer can read. If someone takes the computer while it runs, the existence of the partitions cannot be denied anymore, and without more protection their data is lost too. A LUKS volume on top of a partition protects its data in that case, as long as the LUKS volume is not open (it is opened only to make a filesystem on it, and while it is mounted): s3> luksformat NAME cryptsetup luksFormat on the partition (asks for the LUKS passphrase; use another one than the passphrase of the partition) s3> mke2fs NAME opens the LUKS volume, makes the filesystem, closes it s3> mount NAME DIR opens the LUKS volume (as /dev/mapper/scubed3-NAME, see luks_prefix in Key derivation) and mounts it s3> umount NAME|DIR unmounts it and closes the LUKS volume mke2fs and mount see from the partition whether it has LUKS on it (it needs cryptsetup and the device mapper). The LUKS header is inside the encrypted partition, it is not visible on the base device. The LUKS keys are in memory while the volume is open: this protects the partitions that are not mounted when the computer is taken, not the mounted ones. How to start ~~~~~~~~~~~~ Building needs libfuse 3, libgcrypt and readline (and their development files), and autoconf, automake and pkg-config: ./autogen.sh && ./configure && make The programs are src/scubed3, src/scubed3ctl and src/keystorectl (see Key store), make install installs them in /usr/local/sbin (another place with ./configure --prefix=...). ./configure --without-readline builds scubed3ctl and keystorectl without line editing (the debian-installer has no readline), ./configure --enable-static-programs links the programs statically (it needs the static libraries of libfuse3, libgcrypt and libgpg-error; the debian-installer udeb is built so, it does not depend on library udebs). scubed3ctl and keystorectl read passphrases from the terminal without echo; when their input is not a terminal (a pipe), they read them as lines from their input. Debian packages of scubed3, and a component of the debian-installer that installs Debian with the root file system on a scubed3 partition: see contrib/debian-installer/README. Key store ~~~~~~~~~ Typing a passphrase for every partition (and every LUKS volume) is a lot of work. The keys can be kept in a key store, /etc/scubed3.keys (another file with -K): one passphrase of the key store gives the keys of a set of partitions (a view). Nothing in the file shows how many passphrases or keys there are, or whether it is used at all: it is 64 slots of random data, a slot with a view is encrypted with AES-256-GCM (the key from the passphrase, PBKDF2-SHA256 with the salt and iterations of the configuration file), a view has 64 entries (the name of a partition, its key and the key of its LUKS volume; unused entries cannot be told from used ones). Someone who learns one passphrase sees its view, the other slots look like unused ones. Two programs use it: keystorectl changes the key store: it reads it, unlocks views, changes them in memory; save writes it (nothing is written without save); it does not need the daemon (only import uses it) scubed3ctl uses the keys: it only reads the key store, ONE view at a time (unlock locks the view that was unlocked), so a name is always one partition keystorectl (the prompt is keys>): keys> setup guided: creates the key store, unlocks all its passphrases, adds passphrases and partitions, saves once keys> create a new key store (random data, no views); it never replaces an existing key store keys> unlock one passphrase of the key store keys> unlock-all passphrases until an empty one keys> keys the unlocked views (names, [LUKS]) keys> passphrase-add, passphrase-change [VIEW], passphrase-remove [VIEW] keys> add NAME [VIEW] new random keys, or the keys of NAME in another unlocked view (the same partition in more views) keys> add-passphrase NAME [VIEW] as add, but the partition gets the key of a passphrase (asked twice), so that it also opens without the key store; empty: a random key keys> import NAME [VIEW] a partition with its own passphrase; if it is open and has LUKS on it, the passphrase of the LUKS volume is asked, with it its volume key goes into the key store (cryptsetup luksDump --dump-volume-key, the volume is not changed) keys> copy NAME1 NAME2 [VIEW] NAME2 gets the keys of NAME1: the same partition under another name, for example root for the initramfs (remove NAME1 removes the old name) keys> remove NAME [VIEW] keys> lock VIEW forgets an unlocked view (in memory; a save then loses it) keys> derive the key of a passphrase (for -k, see below) keys> save writes the key store Quitting with changes that are not saved asks first; with -c the changes are lost and the exit status is an error, so a script ends with -c save: keystorectl -c unlock-all -c "add home 1" -c save scubed3ctl, with the key store: s3> unlock one passphrase of the key store (the view that is unlocked is locked first) s3> lock s3> keys the partitions of the unlocked view s3> open-all opens all partitions of the unlocked view s3> luksopen-all [NAME] opens the LUKS volumes of the open partitions of the unlocked view (NAME must be in it), with their keys from the key store s3> unlock-until NAME (for a boot) passphrases until one has a view with NAME, one line of output for each; the partitions of the views without NAME are opened (then the view is locked); at the end of the input the commands after it are not done s3> luksstatus [NAME] of every open partition (or NAME): its LUKS header (LUKS1, LUKS2), its LUKS key in the unlocked view, the loop device on its file, the /dev/mapper device on that (LUKS open), where it is mounted With a view unlocked, open, create, luksformat, mke2fs and mount use its keys instead of asking passphrases, luksopen opens a LUKS volume (as /dev/mapper/PREFIXNAME). The key store keeps the VOLUME KEY of a LUKS volume (random, 512 bits; cryptsetup open --volume-key-file, on a pipe, never in a file: no KDF runs, opening is fast, also at boot). The volume has ONE keyslot: luksformat asks its passphrase (twice, any length: with it the volume also opens without the key store), empty: a random key that is not kept (then only the key store opens it). A partition is first added with keystorectl (add, save), then created and formatted with scubed3ctl: keystorectl -c unlock -c "add home" -c save scubed3ctl -c unlock -c "create home" -c "resize home 100" \ -c "luksformat home" The passphrases of the key store are always typed by you (twice when they are new), they are never generated; the keys in it are random (getrandom(2)): the key of a partition 256 bits, the key of a LUKS volume 512 bits. A new view gets a slot chosen at random (getrandom(2)) among the slots that no unlocked view uses, not the first free one: the order in which the passphrases were added is not in the file. A view has a name while it is unlocked (it is not in the key store): by default iNN, NN its slot (00 to 63, inherent to the view); at the keys> prompt unlock asks a name (empty: the default), "name VIEW NAME" renames it, keys shows the slot of a view with a name of its own ([slot iNN]). A VIEW argument is the name, or (for scripts) the number of the view in the order of unlocking (1, 2, ...); the name of a view is not only digits. With -c (scripts) no name is asked. Without VIEW the only unlocked view is meant. The KDF of a passphrase takes seconds (with the default 16777216 iterations; minutes in a slow virtual machine). A script that runs the programs often computes it once: keystorectl derive prints the key of a passphrase of the key store (key: 64 hexadecimal digits), with -k keystorectl and scubed3ctl take these keys where they ask the passphrases of the key store (unlock, unlock-all, unlock-until, passphrase-add, ...). The key unlocks the view as the passphrase does: keep it as secret (the debian-installer keeps the keys in its memory, not in a file). Every save writes the whole key store again: the unlocked views with new IVs, all other slots new random data, so the file changes completely (an adversary with snapshots does not see which views changed). That is why ALL passphrases must be unlocked before a save: keystorectl cannot tell a view of a passphrase that is not unlocked from an unused slot, it is LOST (save asks you to type yes). The new file replaces the old one (a crash leaves the old or the new key store); on an SSD the old data may stay on the flash. Keep a backup of the key store (it is random data without its passphrases) and of the configuration file. Two keystorectl at the same time: a save takes a lock (flock) on the key store and checks that the file is still the one that was read; if another keystorectl saved it meanwhile, the save is refused (it would lose that change: a view that is not unlocked here is overwritten with random data), quit, unlock again and redo the change. The daemon serves one scubed3ctl at a time (a second one waits until the first quits, also while an s3> prompt is open; after 2 seconds it says so on stderr). Killing keystorectl or scubed3ctl (Ctrl-C, kill, also kill -9) does no harm: what scubed3ctl has asked the daemon is done or not (the daemon finishes a command also when scubed3ctl is gone), the key store is written to a new file that replaces the old one at once (killed before: the old key store stays; the new file is removed, after kill -9 by the next save), no key is ever in a file (cryptsetup gets keys on a pipe), and a terminal gets its echo back if it is killed at a passphrase prompt (not with kill -9: then type reset). keystorectl changes nothing before save; a partition that was added and saved but not yet created can be created later; luksformat killed while cryptsetup formats leaves the partition without a valid LUKS header (its key is in the key store: luksformat it again). One passphrase that opens everything is convenient, but if you have to give it away, everything is revealed: as with the partitions, keep a passphrase with a view you can admit, and others for the hidden partitions. Two views can have different partitions with the same name (import does not stop that), for example a root partition you can admit and a hidden one, both "root". The same name with the same keys in more views is the same partition, that is fine. scubed3ctl has one view unlocked at a time, so "root" is the partition of that view. In keystorectl both views can be unlocked at the same time (a save needs all views unlocked, see above): unlock warns, keys marks the name, add does not copy it (it is not clear which one); lock VIEW forgets one of them. Root on scubed3 ~~~~~~~~~~~~~~~ contrib/initramfs-tools has a hook and a script for initramfs-tools (Debian and derivatives): the root file system is on the partition root of the key store (see Key store). The initramfs starts scubed3 and asks one passphrase, exactly as cryptroot asks it for an encrypted disk ("Please unlock disk sda5_crypt:", with the same messages, nothing else on the console): a passphrase of the key store. A passphrase of a view without root (hidden partitions) is unlocked too, and gets the message of a wrong passphrase: type it first. The partitions of the unlocked views are opened (in level 2 and 3 all must be open), and the LUKS volumes of the view of root; the paranoia level is switched and root (with LUKS on it) is the root device. The daemon keeps running until the computer is switched off: it never opens a file by its path after its start (the base device is opened once and shared by all partitions, random data comes from getrandom(2)), systemd does not kill it at shutdown (it runs as @scubed3). The copy of the key store in the initramfs is destroyed after use. See contrib/initramfs-tools/README. You need to provide a set of macroblocks to scubed3, to which it has read/write access. Normally this is either a file or a block device, but it may be anything. (you would, however, need to write a custom blockio_init_* function and provide read, write and close methods to it if it is not a file or a block device) scubed3 -b BASE [-a CONTROL_SOCKET] [-m MESOBLOCK_LOG] [-M MACROBLOCK_LOG] [-r KIBPS] [FUSE options] MOUNTPOINT The mesoblock size is 2^MESOBLOCK_LOG bytes (12..20, default 14: 16KiB), the macroblock size 2^MACROBLOCK_LOG bytes (at most 2^30, default 22: 4MiB), a macroblock has 2 to 2^16 mesoblocks, and the index must fit in one mesoblock. The sizes are not stored in the macroblocks: a set of macroblocks must always be used with the same sizes. KIBPS is the rate of paranoia level 3 in KiB/s (default 800), it does not switch level 3 on. The FUSE options are those of libfuse 3 (see mount.fuse3(8)), for example -f (stay in the foreground), -d (debug output) and -o allow_other. scubed3 also accepts -o direct_io, which libfuse 2 had and libfuse 3 has not: reads and writes of the partition files then bypass the page cache of the kernel. A partition is unmounted with fusermount3 -u MOUNTPOINT (or umount, as root). Key derivation ~~~~~~~~~~~~~~ scubed3ctl derives the key of a partition from its passphrase with PBKDF2-SHA256. The salt and the number of iterations are the same for all partitions of a set of macroblocks (scubed3 cannot know which salt belongs to which partition). They are read from the configuration file /etc/scubed3.conf (another file can be given with -C): # scubed3 KDF parameters kdf=PBKDF2-SHA256 salt=some random text iterations=16777216 # the paranoia level that mount, mke2fs and luksformat require paranoia=2 # the start of the names of the LUKS volumes, /dev/mapper/myhost-NAME # (default scubed3-; the debian-installer makes it HOSTNAME-, as LVM # names the volume group HOSTNAME-vg) luks_prefix=myhost- Empty lines and lines starting with # are ignored, whitespace around keys and values is ignored, all keys are optional. If the file does not exist, the defaults are used: salt "scubed3_prod", 16777216 iterations and paranoia level 2. The options -s and -i override the values in the file. Below the recommended paranoia level, scubed3ctl warns before mount, mke2fs and luksformat (they write to the partition) and asks you to type yes. The salt is not secret, but without it the partitions cannot be opened: keep a backup of the configuration file (on paper is fine). A random salt can be made with printf 'salt=%s\n' $(head -c 24 /dev/urandom | base64) The configuration file reveals nothing more than the presence of scubed3: it does not say how many partitions there are. Control protocol ~~~~~~~~~~~~~~~~ scubed3 listens on a unix socket, /run/scubed3/control (another path can be given with -a, to scubed3 and to scubed3ctl). The directory of the socket is created with mode 0700 if it does not exist; it must belong to the user that runs scubed3 and nobody else may have access to it, otherwise scubed3 refuses to start. So no other user can connect to the socket, not even for a moment, and nobody can replace it. In addition, scubed3 only accepts connections from root and from its own user. scubed3 refuses to take over the socket of another running scubed3 process; a socket left behind by a crashed process is replaced. Commands can be written to the socket, and scubed3's response can be read. A command is a line of text terminated with a linefeed '\n'. A response starts with "OK\n", or "ERR\n". One or more lines follow. The last line must be ".\n". This terminates the message. The command scubed3ctl uses this interface to communicate with scubed3. Commands (scubed3ctl has commands of its own, like create, open, resize and mount, that use these; other commands are passed on as they are): - open-internal NAME CIPHER KEY - create-internal NAME CIPHER KEY opens a partition, or creates a new one (of 0 blocks) * NAME is the name of the file under the mountpoint, like root or swap, the name has no real meaning, you can open any partition under any name * CIPHER is the cipher, CBC_ESSIV(AES256) (see Encryption) * KEY is the cipher key, base16 encoded (hex) - close NAME closes a partition (it must not be in use; a removed partition in level 2 or 3 only when it is wiped, see Shrinking) - resize-internal NAME BLOCKS RESERVED resizes a partition to BLOCKS macroblocks, of which RESERVED are kept free (the usable size is (BLOCKS - RESERVED)*(mesoblocks per macroblock - 1) mesoblocks); see Shrinking; a partition has at least 2 blocks (with 1 block, every write would overwrite the only copy of its state), 0 blocks removes it; at least 1 block is reserved (the GC always empties one block, a partition that would be completely full could not make progress); a partition that is in use (its file is open, for example mounted) can be resized as long as its usable size does not become smaller: it can grow, and it can get extra reserved blocks and give them back (the debian-installer lends the unclaimed blocks to the partition it installs on this way, see contrib/debian-installer) - info NAME shows the state of a partition: no_macroblocks, pending_removals, trims, reserved_macroblocks, writes, no_indices, updated, wipe_left (a removed partition: blocks that are not wiped yet), tombstone_slots, tombstones_pending, mapped_mesoblocks - p shows all open partitions, the paranoia level, the number of free blocks that were overwritten with random data, and the rate of level 3; after a partition its flags: [U] in use, [C] closed when released, [MNT dir] mounted, and for a partition of size 0 that is removed (see Removing a partition): [removing] the removal is not on disk yet [removed, wiping: N with data, M empty] blocks with an index of it are not wiped yet: N with an older index (they would bring it back, with data), M with an index that says it is empty (last and prelast) [removed, wiping: M empty] only last and prelast are left [removed, wiped] no block has an index of it anymore, its passphrase can be used again - paranoia LEVEL [KIBPS] sets the paranoia level (0, 1, 2 or 3, see Paranoia levels), and the rate of level 3 in KiB/s; scubed3ctl has a command paranoia that asks for confirmation (not between level 2 and 3), because level 2 and 3 destroy partitions that are not open; this command does not wait for a partition that waits for its turn - check-data-integrity NAME checks the hashes of all live mesoblocks of a partition, it reports the number of mesoblocks checked, the number of corrupt mesoblocks, and the corrupt parts (see Integrity) as "corrupt=OFFSET+SIZE" (in bytes, for at most 100 mesoblocks) - check-available NAME, set-aux NAME KEY VALUE, get-aux NAME KEY, set-close-on-release NAME BOOL, static-info used by scubed3ctl (is a name free, remember the mountpoint, close the partition when it is unmounted, mountpoint/size/version of scubed3) - cycle NAME COUNT, verbose-juggler NAME for testing: write COUNT blocks, show the state of the juggler - help-internal, exit lists the commands, closes the connection Example calculation of indexblock size ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For this example we assume the following. Macroblock size 4MB (m). Mesoblock size 16kB (s). So, there are 256 mesoblocks per macroblock. Mesoblock 0 is the indexblock, the other ones are data blocks. Whatever values are used, the indexblock MUST fit in one mesoblock! Required size of the indexblock depends on the maximum amount of macroblocks scubed3 can support (the size of a backing device can change, so scubed3 should be able to deal with it, up to a maximum size). The useful size of the device is (1<<(macroblock_log - mesoblock_log) - 1)(no_macroblocks - reserved_blocks) Note that the usable size is limited by 2^32*(1<= trims[i].size is dead (discarded by shrinking) ...... rest of the 128 byte reserved space, MUST be 0 0x000100 uint32_t no_indices 0x000104 uint32_t idx0x01 (the logical mesoblock in data mesoblock 1, or 0xFFFFFFFE: mesoblock 1 holds tombstones, see Discard) 0x000108 uint32_t idx0x02 ...... 0x0004FC uint32_t idx0xff 0x000500 uint64_t hash0x01 (hash of the ciphertext of mesoblock 1, see Integrity) 0x000508 uint64_t hash0x02 ...... 0x000CF0 uint64_t hash0xff 0x000CF8 8 bytes, MUST be 0 0x000D00 bitmap: each bit represents a macroblock of the base device 0 FREE this block may be ours: if so, it has our signature on disk (otherwise we wouldn't be able to know that it is ours) and we don't care about the contents of this block 1 USED this block is ours: it may not have our signature yet because it has never been written and we care about the data (notice that it only makes sense not to care about the contents of a block if there are no older revisions of that data available that we DO care about...) 0x003FFC last 32 bits of bitmap (the bitmap is stored in units of 32 bits) 0x004000 mesoblock1 0x008000 mesoblock2 0x00C000 mesoblock3 ........ 0x3FC000 mesoblock255 0x400000 end There is space to index 0x4000 - 0x0D00 = 0x3300 = 13056 bytes, which corresponds to a base device size of 13056*8 = 104448 macroblocks, which correspond to 4MiB * 104448 = 408GiB Maximum usable size of the device is 2^32*(1< partition" in a shell destroys nothing. Discard ~~~~~~~ When files are deleted, the filesystem knows which blocks are free, scubed3 does not: it would keep their data, and the GC would keep copying it. A filesystem can tell, with discard (TRIM): run fstrim(8) on the mounted filesystem now and then (or mount it with -o discard). The loop device turns discard requests into fallocate(PUNCH_HOLE) on the partition, and write zeroes requests into fallocate(ZERO_RANGE); both are supported, the range reads as zeroes afterwards. Whole mesoblocks in the range are discarded, the parts of mesoblocks at the edges are written with zeroes. This works for ext3, ext4, XFS, btrfs, F2FS, vfat and every other filesystem that supports discard; ext2 can be mounted with the ext4 driver (mount -t ext4) to get discard, or the free blocks can be discarded offline with e2fsck -E discard. A discarded mesoblock must stay discarded when the partition is opened again, also if older versions of it are still on disk (in blocks that were not written since). So a discard writes a tombstone: a list of discarded logical mesoblocks in a data mesoblock of the current block (index value 0xFFFFFFFE; a big endian uint32_t count, followed by that many uint32_t's, at most 4095 per mesoblock). When a block is replayed, its tombstones are applied first: they discard the versions of those mesoblocks in older blocks (the data in the block itself is newer). A tombstone is needed as long as a version of its mesoblock is in the index of a block on disk; scubed3 counts these versions for every logical mesoblock. The GC carries tombstones that are still needed (from the tail, and from the victims when shrinking) to the current block, as live data; the others die out by themselves when the blocks with old versions are written again. A mesoblock that is discarded while it is in the current block (not yet on disk) is removed from it. A block that is added to a partition (grow) may still have an old index of ours, that would be replayed if the partition is opened again before the block is written: its versions are counted, and they get tombstones if they were discarded. The info command shows tombstone_slots (on disk), tombstones_pending (in the current block) and mapped_mesoblocks (mesoblocks that hold data). Shrinking ~~~~~~~~~ Shrinking sets pending_removals = no_macroblocks - target, the usable size is computed from the target. Mesoblocks past the new end are obsoleted at once, and a trim (seqno of the next write, new size) is recorded, so that these references are never replayed, not even after a later enlarge. At most 8 trims are kept; a trim is dropped when no block in the pool is older than it, trim_floor is then raised to its seqno. A shrink that would need a 9th trim is refused. While removals are pending, every write also drains a victim: the block in the pool (not the current block, not the tail) with the least live data. Its live mesoblocks are absorbed by the current block (up to the brim); when the victim holds no live data anymore, it is removed from the pool. A removed block is FREE in the bitmap of the next written block; it is given back to the unallocated blocks only after that block is on disk, and only when the next block is drawn without it (see "Write order"), that is after the write after it. A block that is its own next block removes nothing: if the next write of the same block is interrupted, the state falls back to the block before it, in which the removed block would still belong to the partition. For the same reason, a resize first writes out a current block that is its own next block. Closing a partition writes until its removed blocks are given back. On startup, the blocks that the most recent block removed are given back after the first write. A grow takes back the removed blocks of the partition that are not given back yet, before it takes unallocated blocks. Removing a partition (shrinking it to 0 blocks): its last blocks (the current and the next block, and the two most recently written blocks) are removed together, when none of them has live data: by a final write of the current block, with them FREE in its bitmap. The block written before it also says that the size is 0 (if it is the current block, there is one more write first). Then the partition is wiped: blocks that still have an index of it would bring it back, with its data, when it is opened again and its more recent indices are overwritten (by random data in level 2 and 3, or by another partition). All its blocks are overwritten with random data: the blocks it removed, and the free blocks that still have an old index of it (from an earlier shrink, they are found by reading the index of every free block). The two blocks with its two most recent indices (last and prelast, they say that the partition is empty) are kept until the others are wiped, then they are wiped too. In level 0 and 1 this is done at once. In level 2 and 3 the blocks are wiped when the scheduler draws them as free blocks, so the writes stay uniform: a block that is not last or prelast gets random data, if last is drawn its index is written again, if prelast is drawn the index is written there and it becomes last (so there are always two indices that say that it is empty: if a write is interrupted, the other one is left), when only those two are left they get random data when they are drawn. That takes long: about N*ln(k) block writes for k blocks on a base device of N blocks. Until it is done, the partition stays open and cannot be closed or resized ("p" and "info" show how many blocks are left), and its key cannot be used for another partition. Switching to level 0 or 1 wipes it at once; stopping scubed3 too. DO NOT USE THE PASSPHRASE OF A REMOVED PARTITION AGAIN UNTIL IT IS COMPLETELY WIPED: a new partition with it would get lower sequence numbers than the indices of the old one that are left. The removal needs writes of the partition (the victims and the final write): in level 2 and 3 the scheduler gives it its turns, in level 0 and 1 the resize to 0 does the writes itself. After a crash (or a power failure) the removal or the wipe is resumed when the partition is opened again (with its passphrase, scubed3 cannot know about it otherwise): - if the most recent index says that the partition has no blocks (the final write is on disk), the wipe is resumed: last is the most recent block, prelast the block before it (if its index also says that the partition is empty, otherwise the first block of the wipe that is drawn gets such an index and becomes last), the free blocks with an older index are found by the same scan; in level 0 and 1 they are wiped at once, and the open says so (there is nothing to open), in level 2 and 3 the partition is open until they are wiped, as above - if the crash came before the final write, the partition is opened with size 0 and pending removals, the removal continues (in level 0 and 1 at once) - if the crash came before anything of the removal was written, the partition is opened as it was, with its data: remove it again A wipe is interrupted safely: the random data is written before the index (see Durability), so if any of the old data of a block is left, its old index is left too, and the block is found again when the wipe is resumed (without the index, the old data would stay on disk: with CBC, a wrong IV only garbles the first 16 bytes of every mesoblock, someone with the key could read the rest). scubed3ctl warns about this when a partition is removed (resize NAME 0), you have to type yes (the whole word) to go on. Until the partition is opened again, last and prelast are ordinary free blocks for the other partitions: if both are overwritten while blocks with an older index of it are left, the most recent of those comes back (opening it is refused if it uses blocks of another partition, otherwise some of its data may come back). So after a crash during a removal, OPEN THE REMOVED PARTITION FIRST, before you open and write to the other partitions. A block of a partition that is being opened, that belongs to another open partition (an old index of it is the most recent one that is left), means that the state of the partition is damaged: it is not opened (the other partitions are not affected). Apart from the wiping of a removed partition, a removed block is not written to by its partition: removing blocks causes no extra writes and the write order stays uniform. On startup, a block with our signature is stale (not replayed) if it is FREE in the bitmap of the most recent block, or if its seqno < trim_floor. Opening a partition looks at every macroblock of the base device: only the first 128 bytes of its index are decrypted (with CBC they do not depend on the rest), the magic (at 0x70) must be right, then the whole index is read and checked (most blocks are not ours, a random block has the magic with probability 2^-64). scubed3 keeps the ciphertext of those 128 bytes of every block in memory (128 bytes per macroblock), it is updated by every write: the first open reads them from the base device (all reads are started at once, posix_fadvise), later opens only decrypt them. dev/opentime.py measures it: with 29000 macroblocks, the first open took 0.15s instead of 1.7s, later opens 0.008s instead of 0.15s. Durability ~~~~~~~~~~ Every macroblock is written in two steps: its data mesoblocks, then its index, each followed by fdatasync() of the base device. So the index is only on disk when its data is, and macroblocks reach the disk in the order in which they are written: the block that absorbed the live data of its tail is on disk before the tail is overwritten. Therefore only the most recently written block can be incomplete after a power failure; on startup the hashes of all its mesoblocks are checked, if one of them doesn't match, the block is ignored (corruption of the most recent block by other causes looks the same, its data is then lost). The index of the block before it names the same block as next_block, so it will be written again and the incomplete contents are overwritten. All writes have these two steps, also the random data of level 2 and 3 and of a wipe (see Removing a partition), so they look the same. fsync() on a partition writes out the current block (if it contains new data), so after fsync() returns, everything written before is on disk. Tests ~~~~~ The directory dev/ contains the tests and the development tools: torture tests (grow, shrink, crashes, torn writes), tests with filesystems on top, statistical tests of the paranoia levels and an independent offline reader of the format; dev/README explains them. Website ~~~~~~~ The directory doc/ contains the website of scubed3 (doc/index.html, it loads nothing from other sites: the fonts are in doc/fonts, under the GUST Font License): the idea, how it works, the paranoia levels (with a small simulation), measurements and the history.