The Crypto Bone - A Technical View

You may have spent some time to look at the concept of the Crypto Bone from a user's point of view. Now we'll get to the core of the Crypto Bone and explain how it actually works. There are a number of decisions that have to be justified by a more technical approach to the inner workings of the Crypto Bone.

I try to give you as much information as possible to help you understand how the Crypto Bone works, without a formal definition like writing a RFC. I hope that understanding the Crypto Bone might motivate you to have a closer look at the source code and to contribute peer-review and support. Please contact me if you like to express your opinion on any technical aspect of the Crypto Bone and its security.

How it all began

Some time ago, in early December 2014, Ray Dillinger (bear@sonic.net) presented the following idea for a secure message system to me:

"Metaphorically, Alice has a mailbox on her machine. The in slot of her mailbox has a fancy lock on it, and Alice can control which keys open the lock. So, if she gives a key to Bob, then Bob can send her mail. If Bob gets hacked and a spammer gets his key, Alice can just change the lock and send Bob a new key. Nobody else's key is affected.

Alice can always tell which key opened the mail slot to put the mail in, so when the spammer uses Bob's key, she knows where the spammer got it and which key needs replacing.

She can maintain a "public" mailbox -- that basically means a mailbox whose key she gives out to anybody and everybody who asks, so people who don't even know her can send her mail. But she can change the key on the public mailbox as often as she wants - every day, or even every hour. Or she can take it down entirely if she wants to.

Each message contains a key that someone can use to send a reply to that message. Whenever Alice sends Bob a message, she sends him a new key. Whenever she gets a message from Bob using his new key, it means, first, she is absolutely sure he got the message she sent it with (proof of delivery), AND she changes her lock so his old key no longer works."

We then tried to find out, what the requirements for such a new message system were, in practice.

The Message Exchange Protocol

Every participant has to maintain a secret key database on the Crypto Bone in which the current key used to encrypt a message and the next key, that will be used for encryption in future, is stored for every correspondent. In addition to these two keys, there is a flag, which indicates that a message has been sent, so that follow-up messages can re-use this key until a reply from the other party has arrived. In certain circumstances it will be necessary to cache a key before it is replaced, so that older messages, that arrive late, can be decrypted, while a new message key is already being used.

The following table shows a typical exchange of encrypted messages. C = E.key(M) denotes the AES-128 encryption of a message with a key and D.key(C) denotes the decryption with the same key, that retrieves the message M again.

Alice	Bob
Alice and Bob exchange a secret in a secure way, i.e. at a personal meeting or in another suitable way. They both enter this secret as the initial key into their Crypto Bone via the graphical user interface.
email key nextkey flag bob secret none false Alice is waiting for the first message from Bob.	email key nextkey flag alice secret none false Bob encrypts a message M1-bob with the secret he has stored for Alice. Bob generates a new next key (key1-bob) and encrypts his message with the secret stored in the database for Alice: E.secret(M1-bob + key1-bob) = C1 Bob sends this cryptogram C1 to Alice.
email key nextkey flag bob secret key1-bob false Alice decrypts the email from Bob and learns the new next key and Bob's message M1-bob. D.secret(C1) = M1-bob + key1-bob Now Alice replies and generates a new next key of her own (key1-alice). Alice encrypts her message M1-alice with the current next key (key1-bob). E.key1-bob(M1-alice + key1-alice) = C2 Now the nextkey (key1-bob) becomes the key and Alice's next key will be stored.	email key nextkey flag alice secret key1-bob true Bob has stored his next key and the flag is set to true, because he has sent his first message encrypted with the secret.
email key nextkey flag bob key1-bob key1-alice true Alice's flag is set to true, because she has used the current key for the first time.	email key nextkey flag alice key1-bob key1-alice false Bob receives C2 from Alice and decrypts it with the current key (key1-bob). He learns Alice's message and stores the next key from Alice. Before storing Alice's new next key, Bob copies the current next key (key1-bob) to key. This key will now be used to encrypt further messages. To indicate that a key change has been performed the flag goes back to false.
email key nextkey flag bob key1-bob key1-alice true Alice is idle.	email key nextkey flag alice key1-alice key2-bob true Bob sends a new message M2-bob and uses the current key (key1-alice) to encrypt. He also generates a new next key of his own (key2-bob) and sends it within the encrypted message to Alice. E.key1-alice(M2-bob + key2-bob) = C3 The current next key (key1-alice) becomes the key before Bob stores his own new next key and the flag goes up.
email key nextkey flag bob key1-alice key2-bob false Alice receives C3 and updates the key database accordingly. She learns Bob's new next key and performs a key change. The key change resets the flag. But she does not reply and remains idle.	email key nextkey flag alice key1-alice key2-bob true Bob does not hear anything from Alice.
email key nextkey flag bob key1-alice key2-bob false Alice is still idle.	email key nextkey flag alice key1-alice key2-bob true Now Bob decides to send Alice a reminder message, or two. E.key1-alice(M3-bob + key2-bob) = C4 E.key1-alice(M4-bob + key2-bob) = C5 He does not generate a new next key, because the flag is up, so he re-uses the next key he has already sent to Alice. Bob does not know if Alice has got his messages. There's no response.
email key nextkey flag bob key2-bob key2-alice true Now Alice is back and replies to Bob's message(s). She generates a new next key of her own (key2-alice) and performs a key change. The flag goes on. E.key2-bob(M2-alice + key2-alice) = C6 She uses the current key (key2-bob) to encrypt and sends her own next key to Bob.	email key nextkey flag alice key1-alice key2-bob true Bob waits.
email key nextkey flag bob key2-bob key2-alice true Alice waits for Bob's reply.	email key nextkey flag alice key2-bob key2-alice false Bob receives the long-awaited reply from Alice, decrypts it with the current next key (key2-bob) and learns Alice's new next key. He performs a key change and resets the flag, because a new encryption key will be used next time. But Bob remains silent for a while.
email key nextkey flag bob key2-bob key2-alice true Alice gets nervous, she sends another message and re-uses the keys, because the flag is on. E.key2-bob(M3-alice + key2-alice) = C7 No change on the database.	email key nextkey flag alice key2-bob key2-alice false Bob is idle.
email key nextkey flag bob key2-bob key2-alice true Alice waits.	email key nextkey flag alice key2-alice key3-bob true When Bob sends a new message he performs a key change.

Under normal circumstances, when messages get through, this is the default behaviour of the two Crypto Bones. Even without the assumption of an evil adversary, it is possible that messages arrive late, because one of the Crypto Bones has lost internet connection to send the message out or is powered down for some reason. So, imagine that Bob's last message C5 is going out at the same time when Alice produces her message C6. In this case, Alice has performed a key change and key1-alice is no longer available for decryption of the late arriving C5.

This problem is solved by storing the key into a last key entry in the key database before the key is replaced by the new key. In case the previous message key is needed for decryption of late arrivals, every key change has to cache the current key before it expires. This is done automatically and does not show up in the table above.

The Foundation

To turn this model into a practical, working system a number of decisions have been made:

• Instead of developing a single binary program that can run on the user's endpoint device (laptop, smart-phone, tablet, ...) I decided to use a separate hardware device (the external Crypto Bone) to store the secret key database and to perform all encryption and decryption inside the external Crypto Bone.

• The Crypto Bone must be as isolated as possible. The only way to communicate with the Crypto Bone -- except sending and receiving emails -- is an encrypted tunnel between the external Crypto Bone and the user's endpoint device. Plain text will only reach the user via this encrypted link.

• To ensure interoperability, the encrypted messages are being produced by a program that uses Cryptlib as its foundation, so that encrypted messages are in OpenPGP format and are encrypted with AES-128 under all circumstances. The encryption key used must have at least 128 bit of "unpredictability" (entropy).

• Because the message exchange uses ordinary email as the transport mechanism, all attempts to ensure privacy, in the sense that it is not visible who communicates with whom, are not (yet) part of the project. Confidentiality remains the main objective.

• The hardware and software components should be as open as possible to ensure that the system can be audited comprehensively for security.

• If the messaging system is used without a separate, external device, the message key database must be isolated and protected as much as possible (a separate daemon on the user's machine will be used for this purpose). This deamon must simulate the external device using the same communication protocol. In this case, the encrypted link is replaced by a data exchange through a socket on the endpoint device.

In 2015 I started with a Beagle Bone and a minimalist version of OpenBSD 5.7 to implement the external Crypto Bone and on the Raspberry Pi a minimal Debian OS was used with similar functionality. In the meantime the Crypto Bone has made its way into the Fedora Linux distribution as a separate package. It is only natural that this package (from version 1.1) also comprises the external Crypto Bone software.

In its current version the external Crypto Bone's software is based on Fedora 24 and a single, universal software release is used on all different hardware platforms.

But a number of measures have been taken to ensure that the Crypto Bone software works isolated and uses only very few basic components of the operating system.

In fact the core software uses only one single crypto library, cryptlib-3.4.3, developed and maintained by Peter Gutmann, which has an excellent reputation and track record. This additional crypto library is the foundation both for the encrypted message key database inside the Crypto Bone and for all OpenPGP message encryption and decryption.

I hope that code review of the system will lead to further improvements.

The Minimalist Operating System Base

The following list summarizes the basic software components that the OS has to provide for the external Crypto Bone Core Software to run safely.

• bash
• a reliable entropy source (/dev/random)
• cryptlib-3.4.3
• ssh
• sudo, iptables
• fetchmail, opensmtpd or exim
• coreutils

The Core Software

The Core Software comprises of a handful of scripts that are written in bash and a daemon process written in C, that uses a reduced Cryptlib library. During the normal boot process, systemd starts the daemon cryptoboneexternd that waits for the arrival of the master key which will eventually be used to decrypt the message key data base. The master key is sent from the user's main machine through the ssh link to the external device. The daemon will store the master key in its main memory so that it does not end up in the filesystem and will be destroyed when the external device is powered down.

The software also establishes a ramdisk (/dev/shm/EXRAM) where certain configuration files as well as incoming and outgoing messages will be stored. It makes sure that permissions on crucial files are set restrictively to root read access. Decrypted messages will be stored in this ramdisk, to ensure that they are lost when the system goes down.

On the activation of a fresh external Crypto Bone installation, when the external daemon starts for the first time, three secrets are generated, the "masterkey" for the encrypted database, a ssh private key "cbb" and the "local.key". While the "masterkey" is used to encrypt the key database, the ssh private key "cbb" secures the encrypted connection to the user's endpoint device. This key is encrypted with the local secret in the file "local.key". These three secrets must be transferred to the user's main machine in a safe way.

A new user "cryptobone" is created on the external device, whose password is taken from the file "local.key". This user has minimal access permission and can use the message key database only if it uses the "local.key" to elevate access permissions via sudo to communicate with the daemon running with UID 0.

So any command, that is sent to the external device via the ssh tunnel, will only work, if the "local.key" is included in the command. Without it, the database cannot be accessed. The program "cbcontrol" is the central intermediary between the commands send to the user "cryptobone" via the ssh link and the use of secret information by the external daemon running as root.

To unlock the external Crypto Bone the masterkey must be transferred from the user's main machine through a secure ssh link, that can be established with the ssh private key. The masterkey is then stored in the external Crypto Bone's memory used by the daemon and does not remain on the system when it is powered off.

It is very important that both the masterkey and the private ssh key are stored safely on the main Linux computer. It's the job of the local daemon process to make sure, these keys are present in memory only, while the Linux computer is active. To achive a maximum of protection, the daemon reads both secrets from an encrypted file system, that is mounted exclusively for a very short time when the main Linux computer boots. This file system will never be mounted while the user's main Linux computer is running in normal operation.

So the master key will be transferred to the external device only while the Linux computer is booting. Shortly after booting the main computer the masterkey becomes inaccessible unless someone gains full root permissions on the main Linux computer.

This mechanism makes sure, that both secrets cannot be compromised by malware running on behalf of the ordinary user who runs the graphical user program. It would take full root access to manually retrive these secrets on the main Linux computer. And in this case, security is already lost completely.

All other operations on the external Crypto Bone can be controlled by using the "cryptobone" GUI program on the user's main machine.

On the external Crypto Bone the message key data base is encrypted and can only be used by the external Crypto Bone daemon that makes use of the Cryptlib library, if the master key has been received from the main machine. This daemon maintains an encrypted file in which all message keys and other secrets are being stored. Both the masterkey, which will be stored inside the daemon's main memory, and the local secret stored on the user's main machine are required to access this encrypted key data base.

Changes on the key database happen when either a new message is created (to be sent out) or if a legitimate (decryptable) message arrives. The first part is handled in the script that executes commands sent to the Crypto Bone through the ssh link (function write_message) and the second part in the shell script processmessage.

The following pseudo code describes the logic behind these two crucial components:

on SENDING a message:  (function write_message)
      
      if nextkey == "none":
              # nothing received and never sent anything before
	      create a new nextkey and store
              use key to encrypt
              set FLAG = True (on)
	      # FLAG indicates that a first message has been sent
	      # and that follow up messages shall not create new
	      # nextkeys as long as the FLAG is ON

      else:
              # there is a valid nextkey (either set on receipt or
	      # because we've sent a message already)

	      if FLAG == ON:
	             # we will use the current key and nextkey again
		     encrypt with current key
		     send current nextkey with message
		     # no changes to the key database, FLAG remains ON

	      else:
	             # FLAG has been reset (OFF) because we've received a
		     # message from our correspondent
		     # use this nextkey now to encrypt and create a new nextkey
		     copy the current key to lastkey  #  needed for late arrivals
		     copy nextkey (set by correspondent) to key and 
		     encrypt with this key
		     create a new nextkey (our nextkey) and store
		     set FLAG to ON, indicating that we've sent a reply

on RECEIVING a message:   (processmessage)

      find the FROM name
      read "key" and "nextkey" from the key database (using FROM)

      try to decrypt message with "key"
      if successful:
             read NEXTKEY from plaintext file (correspondent's nextkey)

      else:
            # message cannot be decrypted with "key"
	    use "nextkey" (currently stored) to decrypt message
	    if successful: 
	           read NEXTKEY from plain text file (correspondent's nextkey)
            
	    else:
                   # message cannot be decrypted with "nextkey"
	           use "lastkey" to decrypt message, maybe a late arrival
	           if successful: 
		          make sure that the key database does not change
                   else:
                          # message is not decryptable.
		          move message to FORENSIC directory, or forget it


      if decryption was successful and a new NEXTKEY exists:
            # update the key database with NEXTKEY
	    if stored nextkey == "none":
	           # we've nothing sent yet
	           do not change key
		   store NEXTKEY as nextkey
                   set FLAG OFF , to indicate that a new nextkey has arrived

            else:
	           # we have a nextkey, either our's or the correspondent's
		   if stored nextkey == NEXTKEY:
		         # we receive a follow up message from correspondent
			 # do nothing on the key database
                   else:
		         # correspondent sends us a new NEXTKEY
			 copy stored nextkey to key 
			 # next message we sent will be encrypted with this key
			 store NEXTKEY as nextkey
                         set FLAG = OFF, to indicate that a new nextkey has arrived

Attacks on the Crypto Bone

A comprehensive analysis of possible attacks and the underlying threat model will be presented in a separate page.

8 November 2016