wrenchcrypt -- Deniable Encryption for humans Inspired by MaruTukku The main idea behind this program is that encrypted data and random noise can't be distinguished without additional knowledge. Thus, if encrypted data is randomly interlayed with random data, it can't be determined whether a considered block contains meaningful data or not. This program operates on files called "Extent", which have the following layout: +------------------------------+ --------------\ | HEADERS | | | * block size in bytes | | | * total size in blocks (m) | | | * number of aspects (n) | | | * used cipher | | +------------------------------+ | +------------------------------+ --\ | | ASPECT_0 | | | | * KEY_0 (password protected) | | | | * GEN_0 (encrypted by KEY_0) | | | | * MAP_0 (encrypted by KEY_0) | | | | * Address of A_0/B_0 | | | | * Address of A_0/B_1 | | | | * ... | | | | * Address of A_0/B_m | | | +------------------------------+ | | | ASPECT_1 | | | | * KEY_1 (password protected) | | | | * GEN_1 (encrypted by KEY_1) | | | | * MAP_1 (encrypted by KEY_1) | | | | * Address of A_1/B_0 | | | | * Address of A_1/B_1 | +-> Aspects | | * ... | | +-> Extent | * Address of A_1/B_m | | | +------------------------------+ | | | ... | | | +------------------------------+ | | | ASPECT_n | | | | * KEY_n (password protected) | | | | * GEN_n (encrypted by KEY_n) | | | | * MAP_n (encrypted by KEY_n) | | | | * Address of A_n/B_0 | | | | * Address of A_n/B_1 | | | | * ... | | | | * Address of A_n/B_m | | | +------------------------------+ --/ | +------------------------------+ --\ | | BLOCK_0 | | | +------------------------------+ | | | BLOCK_1 | | | +------------------------------+ +-> Blocks | | ... | | | +------------------------------+ | | | BLOCK_m | | | +------------------------------+ --/ ----------/ From the outside, without any additional information, this file looks like a simple header information, followed by random noise, regardless of whether there is any useful data in it or not. From the header, it is possible to determine the location of each structure, but without any passwords, the content of these structures is useless. Each aspect contains a map of blocks it uses. For example, consider this mapping: m=10, n=4 +-------------------+ +-------------------+ +-------------------+ +-------------------+ | MAP_0 | | MAP_1 | | MAP_2 | | MAP_3 | +-------------------+ +-------------------+ +-------------------+ +-------------------+ | A_0/B_0 = BLOCK_4 | | A_1/B_0 = BLOCK_5 | | A_2/B_0 = BLOCK_6 | | A_3/B_0 = UNUSED | | A_0/B_1 = BLOCK_7 | | A_1/B_1 = BLOCK_3 | | A_2/B_1 = UNUSED | | A_3/B_1 = UNUSED | | A_0/B_2 = UNUSED | | A_1/B_2 = BLOCK_9 | | A_2/B_2 = UNUSED | | A_3/B_2 = UNUSED | | A_0/B_3 = UNUSED | | A_1/B_3 = BLOCK_0 | | A_2/B_3 = UNUSED | | A_3/B_3 = UNUSED | | A_0/B_4 = UNUSED | | A_1/B_4 = UNUSED | | A_2/B_4 = UNUSED | | A_3/B_4 = UNUSED | | A_0/B_5 = UNUSED | | A_1/B_5 = UNUSED | | A_2/B_5 = UNUSED | | A_3/B_5 = UNUSED | | A_0/B_6 = UNUSED | | A_1/B_6 = UNUSED | | A_2/B_6 = UNUSED | | A_3/B_6 = UNUSED | | A_0/B_7 = UNUSED | | A_1/B_7 = UNUSED | | A_2/B_7 = UNUSED | | A_3/B_7 = UNUSED | | A_0/B_8 = UNUSED | | A_1/B_8 = UNUSED | | A_2/B_8 = UNUSED | | A_3/B_8 = UNUSED | | A_0/B_9 = UNUSED | | A_1/B_9 = UNUSED | | A_2/B_9 = UNUSED | | A_3/B_9 = UNUSED | +-------------------+ +-------------------+ +-------------------+ +-------------------+ The actual blocks would then contain fragmented data of aspects with the following order: +-------------------+ | BLOCK_0 = A_1/B_3 | | BLOCK_1 = UNUSED | | BLOCK_2 = UNUSED | | BLOCK_3 = A_1/B_1 | | BLOCK_4 = A_0/B_0 | | BLOCK_5 = A_1/B_0 | | BLOCK_6 = A_2/B_0 | | BLOCK_7 = A_0/B_1 | | BLOCK_8 = UNUSED | | BLOCK_9 = A_1/B_2 | +-------------------+ Now, let's consider that the user wants to read data from aspect 1. To do this, they need to provide password for KEY_1, which decrypts GEN_1 and MAP_1. The map can be read sequentially, and blocks can be fetched as they are referenced by the map. Each block can then be decrypted using a key generated by the lattice generator GEN_1 for each block, seeded by the block number (e.g. A_1/B_0=BLOCK_5 will be decrypted using key generated by GEN_1(0), A_1/B_1=BLOCK_3 by GEN_1(1), A_1/B_2=BLOCK_9 by GEN_1(2), and A_1/B_3=BLOCK_0 by GEN_1(3)). This yields the desired plaintext. However, the situation is more interesting when the user wants to write data. Do note that MAP_1 contains no information about which blocks are free for use by additional data. Since the unused blocks BLOCK_1, BLOCK_2, and BLOCK_8 contain random data, it is impossible to determine that no aspect is using them without decrypting maps of all aspects. Therefore, if the user only provided KEY_1, they would know only that BLOCK_5, BLOCK_3, BLOCK_9, and BLOCK_0 are used, and the rest is free, leading to potential overwrites of blocks belonging to other aspects. To prevent overwriting, the user would need to provide passwords of all aspects they want to preserve, so that their maps can also be decrypted and considered when determining which blocks are free. Let's consider that the user wants to write 4 blocks worth of data into ASPECT_3, while only possessing passwords to KEY_1, KEY_2, and KEY_3. To do this, they provide these 3 keys to decrypt MAP_1, MAP_2, and MAP_3. By examining the maps, they see that blocks BLOCK_1, BLOCK_2, BLOCK_4, BLOCK_7, and BLOCK_8 are unused (blocks BLOCK_4 and BLOCK_7 are in fact used by ASPECT_0, but the user doesn't have password for KEY_0 required to decrypt MAP_0 which would inform them of this). The user then supplies the 4 blocks worth of data, which are allocated to 4 of the 5 available blocks on random. For example, A_3/B_0 gets allocated to BLOCK_7, A_3/B_1 to BLOCK_2, A_3/B_2 to BLOCK_1, and A_3/B_3 to BLOCK_8. This would result in the following layout: +-------------------------------+ +-------------------+ +-------------------+ +-------------------+ | MAP_0 | | MAP_1 | | MAP_2 | | MAP_3 | +-------------------------------+ +-------------------+ +-------------------+ +-------------------+ | A_0/B_0 = BLOCK_4 | | A_1/B_0 = BLOCK_5 | | A_2/B_0 = BLOCK_6 | | A_3/B_0 = BLOCK_7 | | A_0/B_1 = BLOCK_7 (corrupted) | | A_1/B_1 = BLOCK_3 | | A_2/B_1 = UNUSED | | A_3/B_1 = BLOCK_2 | | A_0/B_2 = UNUSED | | A_1/B_2 = BLOCK_9 | | A_2/B_2 = UNUSED | | A_3/B_2 = BLOCK_1 | | A_0/B_3 = UNUSED | | A_1/B_3 = BLOCK_0 | | A_2/B_3 = UNUSED | | A_3/B_3 = BLOCK_8 | | A_0/B_4 = UNUSED | | A_1/B_4 = UNUSED | | A_2/B_4 = UNUSED | | A_3/B_4 = UNUSED | | A_0/B_5 = UNUSED | | A_1/B_5 = UNUSED | | A_2/B_5 = UNUSED | | A_3/B_5 = UNUSED | | A_0/B_6 = UNUSED | | A_1/B_6 = UNUSED | | A_2/B_6 = UNUSED | | A_3/B_6 = UNUSED | | A_0/B_7 = UNUSED | | A_1/B_7 = UNUSED | | A_2/B_7 = UNUSED | | A_3/B_7 = UNUSED | | A_0/B_8 = UNUSED | | A_1/B_8 = UNUSED | | A_2/B_8 = UNUSED | | A_3/B_8 = UNUSED | | A_0/B_9 = UNUSED | | A_1/B_9 = UNUSED | | A_2/B_9 = UNUSED | | A_3/B_9 = UNUSED | +-------------------------------+ +-------------------+ +-------------------+ +-------------------+ +-------------------+ | BLOCK_0 = A_1/B_3 | | BLOCK_1 = A_3/B_2 | | BLOCK_2 = A_3/B_1 | | BLOCK_3 = A_1/B_1 | | BLOCK_4 = A_0/B_0 | | BLOCK_5 = A_1/B_0 | | BLOCK_6 = A_2/B_0 | | BLOCK_7 = A_3/B_0 | <- Overwritten block! | BLOCK_8 = A_3/B_3 | | BLOCK_9 = A_1/B_2 | +-------------------+ The blocks will then be encrypted by GEN_3 in the same way as when decrypting (e.g. A_3/B_0=BLOCK_7 will be encrypted using key generated by GEN_3(0), A_3/B_1=BLOCK_2 by GEN_3(1), A_3/B_2=BLOCK_1 by GEN_3(2), and A_3/B_3=BLOCK_8 by GEN_3(3)). At this point, when the user provides password for KEY_0 in order to read ASPECT_0, the MAP_0 is used to look up which Extent blocks correspond to which aspect blocks; in this case, the aspect block A_0/B_0 is located at extent block BLOCK_4, and the aspect block A_0/B_1 is located at extent block BLOCK_7. However, BLOCK_7 was overwritten previously, so an attempt at decrypting the contents of it will not yield the original plaintext, nor the plaintext of the new content (since the encryption keys do not match). When an extent is created, the following sequence of events needs to occur: 1. The header fields are populated with user's preferences. 1.1 The number of aspects (n) defaults to 8, so that the actual number of used extents cannot be infered from the number of present extents. The user is advised to set n to a higher value than is actually needed. 2. Keys for each aspects are generated using random number generator. 3. The user is asked to enter unique password for individual keys, in random order. 3.1 The user can enter fewer than n passwords, in which case the rest is generated randomly (the user won't have access to these aspects). 3.2 The passwords are iterated through hashing function for several seconds before being used, to prevent brute-forcing. 4. The lattice generator is produced for each aspect, using random number generator. This is encrypted by the respective keys. 5. Block maps of each aspect are initialised as UNUSED (e.g. -1). This is encrypted by the respective keys. 6. All blocks are initialised using random number generator. These steps are triggered by the following command: $ wrench new [-m BLOCKS=1024] [-s BLOCK_SIZE=1024k] [-n ASPECTS=8] [-c CIPHER] <extent.file> >Please enter up to 8 passwords, separated by new line. >If you wish to enter fewer than 8 passwords, terminate your entry by an empty line. > >Transforming passwords... Done! >Populating header... Done! >Generating keys... Done! >Generating keygens... Done! >Generating empty maps... Done! >Populating blocks with noise... Done! >The extent is now created. After these steps, the Extent is ready to be written to. This process is comprised of the following steps: 1. The user provides password for the aspect to be written to. 1.1 This unlocks the corresponding key, which then decrypts the map and the lattice key generator of that aspect. 1.2 This alone is all that is necessary to read/write from/to an aspect. 2. The user provides password for all aspects that are to avoid being overwritten. 2.1 This unlocks the keys of these aspects, which unlock the maps. 2.2 From the maps, it is possible to determine which blocks are used and are to be avoided when writing. 2.3 Without these passwords, it should not be possible to tell which blocks are used by which aspects. 3. The map of the aspect to be written to is read, and all referenced blocks are overwritten with random noise. 4. The entire map is initialised with UNUSED 5. The user provides data to be written. 6. A block is selected at random from the pool of free blocks. The choice is registered in the aspect's map. 7. The data it encrypted by a key generated by the lattice generator seeded with the block sequence number, and written into the block (add whitening?). 7.1 If more data is to be written than can fit in one block, step 4 and 5 is repeated. These steps are triggered by the following command: $ wrench write <extent.file> [ <data.in> ] >Please enter password for the aspect you wish to write into: > >Please enter passwords for all aspects you wish to protect from overwriting, followed by empty line: > >Transforming passwords... Done! >Warning: This aspect already contains data, which will be overwritten. Proceed? [y/N]: y >Writing... Done! To keep the implementation simple, this command overwrites the previous content of the block with the new file. If the aspect already contains populated blocks, a warning is emitted. Finally, the data can be read back from the aspect by the following steps: 1. The user provides password for the aspect to be read from. 1.1 This unlocks the corresponding key, which then decrypts the map and the lattice key generator of that aspect. 2. The map is read sequentially, and blocks are fetched as they are referenced. 3. Each fetched block is decrypted by a key generated by the lattice generator seeded with the block sequence number. This is achieved by the following command: $ wrench read <extent.file> [ <data.out> ] >Please enter password for the aspect you wish to read from: > >Transforming password... Done! >Reading... Done! As a last function of the program, a single aspect can be wiped. The following steps achieve this: 1. The user provides password for the aspect to be wiped. 1.1 This unlocks the corresponding key, which then decrypts the map and the lattice key generator of that aspect. 2. The map of the aspect to be written to is read, and all referenced blocks are overwritten with random noise. 3. The entire map is initialised with UNUSED These steps are triggered by the following command: $ wrench truncate <extent.file> >Please enter password for the aspect you wish to wipe > >Transforming passwords... Done! >Wiping... Done! Notes: - Passwords are protected from being swapped onto a disk by mlock() -