**PRE-DRAFT**
4/27/2018
davidwr
Using paper to make a "secure vault" for key-escrow systems
Definitions:
Key-escrow system: A system in which a 3rd party holds backdoor "keys" to many locked "things" - e.g. phones, computer accounts, etc.
Secure vault: A system in which the backdoor keys are effectively protected against unauthorized access.
Summary:
Public/private key pairs are generated.
Private keys are encrypted using a master key.
The encrypted private keys are split into two parts.
Each part is printed out and stored in a separate locked box.
Variations:
Encrypted keys are split into more than two parts.
The master key changes periodically, e.g. every 1000 keys or every week.
Multiple copies of printouts can be made to provide redundancy. If this is done, any verification system needs to make sure the multiple copies are in fact the same.
Example:
System with one master key and with the encrypted private key split into two parts, with an automated verification system.
Each part has the last 50% of the generated public key, a serial number, and a time-stamp, and the serial number of the generating machine, which together serve as a label.
The system consists of two systems: A generator system an an automation system.
The generation system:
Input is the master key, typically the public key of a public/private key pair.
Output consists of three printouts, 1 of which is public and 2 of which are private.
The public printout consists of the label described above plus the generated public key.
Private printout #1 consists of the label described above plus an "part number" indicating "part 1 of 2" and the first 50% of the encrypted private key.
Private printout #2 consists of the label described above plus an "part number" indicating "part 2 of 2" and the second 50% of the encrypted private key.
The input and output of the generation system will be made available to the automated verification system.
The verification system:
The automated verificaiton system will match the two private printouts, decrypt them using the master key which is an input to both systems, then verify that the decryupted private key and the public key provided by the generation system are indeed a match.
Upon successful verification:
The public key is made available to the end user.
Private printout #1 is stored in a secure box labeled "secure box #1."
Private printout #2 is stored in a secure box labeled "secure box #2."
In a typical system, these private keys would be printed on small pieces of paper, similar to the small pieces of paper used by some "pull lever" voting booths used in the United States in the second half of the 20th century.
There would typically be thousands or tens of thousands of such pieces of paper in each secure box before the boxes had to be changed.
As boxes are filled, information is recorded to make it easy to identify which box contains which private keys, based on their labels.
The records concerning the contents of each secure box are not considered secure in the scope of this system, but it may be beneficial to keep control access to these records and store them securely.
The idea is that it would be very rare that any of the secure boxes would ever be opened. If they did need to be opened, it would be a manual, labor-intensive task to find the desired information. No computers or other non-manual devices would be involved in finding the "needle in a haystack" if a search were required. Only highly trusted people would be allowed to conduct these searches.
Search procedure:
If an authorized party presented the key-escrow service with the public key, then:
The key escrow service would verify that the request is legitimate and take other steps required by law, such as notifying all parties that have a right to know that the key has been requested in case they have a right to protest.
They key escrow service would look up the label associated with the public key. The label is described under "The generation system" and "The verification system" above.
Using the label, the key escrow service would identify the secure boxes that hold each part of the key.
Seperately, the boxes would be reviewed by trusted employees under secure conditions. No cameras or other recording devices other than "pen and paper" would be allowed in the controlled environment.
The employees would look for the slip of paper in each box that had the correct label.
The employees would write down a copy of the partial encrypted private key and store it in a sealed envelope or other secure container.
They would restore the contents of the box, re-seal it, and return it to secure storage.
The sealed envelopes from each secure box would be taken to a secure area along with the key used to encrypt them. A non-networked computer in a secure area would take the contents of the envelopes and the key used to encrypt them and produce a candidate private key. It would then match it with the public key. If they matched, it would print out the private key. In practice, this computer would be the same as the verification system described above, except that it would print out the decrypted private key.
The private key would be sent to the authorized entity that requested it using a secure method.
Error conditions:
If an error happens during key generation, printing, verification, depositing the partial encrypted keys into the secure boxes, or making the public key available to the user, that public key is never used. If printouts of the partial encrypted keys wind up in the secure boxes, this is not an error. If necessary, a trusted human is called in to replace the secure boxes, clear any mechanical faults, and reset the system.
If an error happens during the printing of the labels for the secure boxes and this error cannot be recovered either automatically or with manual intervention without compromising the contents of the secure boxes, all public keys associated with those secure boxes will be considered invalid and not used.
If the private key used to encrypt the secure boxes is compromised, all public keys produced after the point of compromise will be considered invalid and not used. Optionally, all public keys whose private keys were enrypted with that key will be considered invalid and not used.
If the contents of a secure box are ever compromised, the public keys associated with that secure box should be considered compromised. If possible, they should not be used. Recalls or destruction of devices or accounts depending on these keys may be warranted.
Discussion of variations:
Encrypted keys are split into more than two parts:
By splitting the keys into more than two parts, it makes an actual compromise more difficult. It also makes key retrieval more difficult. However, it makes it easier to have a malicious party compromise one box for the purpose of invalidating all keys associated with that box, since he will have more targets (boxes) to choose from.
The master key changes periodically, e.g. every 1000 keys or every week.
By controlling how often the master key changes, it reduces the impact of a compromised master key. On the other hand, it means there are more master keys to protect.
Multiple copies of printouts can be made to provide redundancy. If this is done, any verification system needs to make sure the multiple copies are in fact the same.
More copies means more redundancy, but it also means more possibilities for either a true compromise or a "forced discard attack" where the goal of the attacker is not to compromise a key but to force the key-escrow service to discard many keys, thereby increasing their cost of doing business.
Vulnerabilities:
This system is inherently vulnerable to false requests which are clever enough to be indistinguishable from a legitimate request.
Human vulnerabilities, such as a compromised or corrupt employee, are always possible. Mitigating these is beyond the scope of this document.
Physical vulnerabilities, such as the secure boxes not being secure from theft or destruction, can be mitigated by creating and maintaining multiple copies of the information held in the secure boxes.
Summary:
By using paper printouts of an encrypted private key, never storing the private key in any electronic system for more than a few seconds, and never storing it in any encrypted system, we can provide a key-escrow system in which the escrowed keys are immune from automated attacks.
This system also considers slow, labor-intensive, high-cost information retreival a desirable feature. By imposing a high high delay and a high monetary cost - which will presumably be paid for by the requesting party - it strongly discourages requests for key retreival.
Patentability:
This was written as an off-the-cuff description of how to secure the private keys after reading 'A few thoughts on Ray Ozzie's "Clear" Proposal' by Nathan Green dated April 26, 2018 ( at http://blog.cryptographyengineering.com/2018/04/26/a-few-thoughts-on-ray-ozzies-clear-proposal/ and http://web.archive.org/web/20180427000040/http://blog.cryptographyengineering.com/2018/04/26/a-few-thoughts-on-ray-ozzies-clear-proposal/ ).
I have some knowledge in technical issues but I am not a security expert.
If I can think of this in a matter of hours, that's proof that there is nothing above that isn't, pardon the pun, "patently obvious."
It is likely that anything closely related to this is also patently obvious.
Errors:
I have not proofread the above. It probably contains ommissions, inconsistencies, and other technical errors. I'm posting it to demonstrate that any ideas along these lines are obvious.