Caius -- A heirarchical delegable password safe

A long while ago I, Rob Kendrick, Clive Jones (and possibly others) sat down and tried to come up with a way to store passwords a-la Password Safe. However, being us, we wanted to ensure a number of properties which password safes commonly don't have. We wanted to allow the delegation of access to some subset of the passwords. We also wanted for it to be reasonable to deny that there is content which has not been decrypted.

I was reminded of this work when I was discussing the concept of deniable storage of secrets with a colleague (An idea I'll expand upon in another blog post at another time). I am therefore presenting, with little change other than formatting the design from years ago. I would be very interested if anyone knows of software which meets the properties of the Caius system since I would like to have one but simply don't trust myself (see another future posting) to write it right now.

Caius

The following concepts are assumed to be understood:

The 'Caius' system is a password-safe type system sporting hierarchical delegable access to the data it stores. The 'Caius Fob' is the data-store for the system.

The 'Caius Fob' is a file which consists of a header and then three sections. The header identifies it as such a file, the first section lists a number of 'External IDs' which can be used to access portions of the file. The second section lists ACL entries as defined below. The third section of the file is the encrypted data looked after by this file. It is not intended that the holder of a CaiusFob be able to deny it is a CaiusFob, but it is expected that it be possible to deny an ability to decrypt (perhaps by lacking a password) any ACL entries. Given that the structure of the file is known, it is necessary that there be external IDs for which the password or GPG key is not valid or cannot decrypt an ACL entry, and ACL entries which even if decrypted may not be valid, and ACL entries which even if decrypted and valid may not be used to encode any data blocks.

An External ID

External ID ::=
   LENGTH
   TYPE
   DATA

Where TYPE is one of:

The list of external ids forms a numbered sequence where the index (0-based) into the sequence is the External ID number. (EIDnr)

An ACL Entry

ACL Entry ::=
   LENGTH
   EIDnr
   DATA
   HMAC

The EIDnr is the number of the External ID as explained above. The LENGTH is the length of the DATA section which is a key-pair as explained below, encrypted to the external id. The HMAC uses the authentication key in the key-pair in the DATA section, and authenticates the EIDnr, LENGTH, DATA tuple.

One possibility for increasing deniability is to remove the EIDnr from this part of the file, and assume that for every external ID you try to decrypt all ACLs you've not succeeded in decrypting thus-far. This has the benefit of being able to deny that an ACL entry ought to be decryptable with the credentials you hold, but also an increased inability to know if you have successfully unlocked everything appropriate to being able to fully manipulate a CaiusFob. This tradeoff is currently set in favour of better understanding of the content, but a future design feature might suggest EIDnr should always be -1 to indicate "unknown, try every EID".

A key pair

Key Pair ::=
   ENCRYPTIONKEY
   AUTHENTICATIONKEY

The ENCRYPTIONKEY is used to initialise the stream cipher for the data section. The AUTHENTICATIONKEY is used to compute HMACs for the appropriate ACL entries or data blocks (as defined below)

The data section

First consider a set of stream ciphers. There exists always one cipher which we will call the NULL cipher. It is defined such that Cipher(Byte, Offset) == Byte and is always available. Then there is a cipher initialised for each key pair we can successfully extract from the ACL entry section of the file.

Each of these ciphers is initialised and made ready such that the data section can be xored with the bytes as they come out of the stream ciphers in an attempt to decrypt the blocks. Essentially this is equivalent to decrypting the entire data section with each cipher in turn to produce N proposed cleartexts which can then be examined to find decrypted blocks.

Whenever a cipher, combined with the data stream in the file, manages to produce a sequence of eight bytes of value zero, we have reached a synchronisation point and what follows is a data block enciphered with which ever cipher managed to reveal the synchronisation sequence.

Since it is vanishingly unlikely that you will find eight zeros in a row when playing about with arbitrary cipher initialisation, we consider this to be an acceptable synchronisation sequence.

Once we have found a sync sequence, we can know the length of this block and thus we do not look for sync markers again until after the block we have just found.

A data block

Data block ::=
   DATALENGTH
   PADLENGTH
   TYPE
   DATA
   PAD
   HMAC

Such that each field is the obvious, DATA is DATALENGTH bytes of data, the texture of which is defined by TYPE and PAD is PADLENGTH arbitrary bytes which pad this block. HMAC is keyed using the authentication key associated with the stream cipher managing to decrypt this and is over the DATALENGTH, PADLENGTH, TYPE, DATA, PAD tuple.

If TYPE is zero then this is a ''free-space'' block and will typically contain zero bytes of DATA and some number of padding. This is however arbitrary and not enforced, the free space can be DATA if the implementer prefers and implementations are encouraged if possible to randomise the distribution of the consumed space between the DATA and PAD sections.

A node block

TYPE == 1 (Node)
DATA ::=
   MY_ID
   PARENT_ID
   NAME
   NOTES

MY_ID is a unique ID for this node. (generally a random number, probably 64 bits long, perhaps a UUID). PARENT_ID if not all NULLs is the ID for the parent node. If all NULLs then this is the root of a heirarchy. NAME is a NULL terminated byte string of one or more characters which is the name of this node. It may consist only of any characters other than NULL and the forward-slash character. NOTES is a byte string of zero or more characters, NULL terminated. Note that the DATALENGTH of the data block clearly delimits this field but the NULL is present to aid parsing.

A system block

TYPE == 2 (System)
DATA ::=
   PARENT_ID
   USERNAME
   PASSWORD
   EXPIRYDATE
   NOTES

PARENT_ID is the node to which this block belongs. It is required that any system blocks you succeed in decrypting can be placed within a node you succeed in decrypting. If the library encounters a system block which belongs to a node it cannot find then this is considered to be a corrupt system block and will be treated as though it could not be decrypted.

USERNAME is a byte string of one or more characters terminated by a NULL, ditto for PASSWORD and as for a node block, the NOTES are NULL terminated also.

EXPIRYDATE is a byte string of characters in RFC-822 date format.

Implementation notes

It is expected that any implementation of Caius will adhere to the following guidelines in order to enhance the security of content over time.

  1. Any time a block is invalidated (such as by the changing of a password, the obsoleting of an entry, the changing of notes, names, or reparenting a node) anywhere from one to all of the bits in the block can be changed. Trivially, this includes the synchronisation sequence preceeding the block as if the synchronisation sequence isn't present then the block does not exist.

  2. Every time a CaiusFob is altered in any way, some amount of known intra-block padding must be altered in a random way. Ideally this will be done so that it looks like number 1 has happened somewhere else in the file as well. Anywhere from zero to all of the padding can be thusly altered in any given change.

  3. No attempt will be made to write to any part of the file which cannot be positively identified as padding unless the user has explicitly stated that they will accept damage to data they cannot currently decrypt.

  4. No indication will be given to the user if any part of the file was unable to be decrypted or failed an HMAC check. Such data is simply incorrectly decrypted and thus ignored.

  5. Intrablock padding can be positively identified if you have two consecutive blocks in a CaiusFob such that the number of bytes between them could not possibly hold the simplest of free space blocks.

  6. When appending a block to a CaiusFob it is encouraged to place up to 50% of the size of the intrablock spacing before it as random padding, and up to 50% afterwards also. Naturally anywhere between zero and the full amount is acceptable, ideally the implementation would choose at random each time.