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.
The following concepts are assumed to be understood:
- Public key cryptography
- Symmetric cryptography
- Password Safe (originally counterpane, now a sourceforge project)
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
TYPE is one of:
* 0: Unused (ID slot placeholder)
* 1: GPG key, where
DATA is the keyid of the gpg key
* 2: Password, where
DATA is some hash of a password which can be used
to derive a key for decrypting an ACL entry.
The list of external ids forms a numbered sequence where the index (0-based)
into the sequence is the External ID number. (
An ACL Entry
ACL Entry ::= LENGTH EIDnr DATA HMAC
EIDnr is the number of the External ID as explained above. The
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
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
ENCRYPTIONKEY is used to initialise the stream cipher for the data
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,
DATALENGTH bytes of data, the
texture of which is defined by
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
PADLENGTH, TYPE, DATA, PAD tuple.
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
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
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,
PASSWORD and as for a node block, the NOTES are NULL terminated
EXPIRYDATE is a byte string of characters in RFC-822 date format.
It is expected that any implementation of Caius will adhere to the following guidelines in order to enhance the security of content over time.
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.
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.
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.
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.
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.
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.