I was once asked to explain how to send messages securely between remote systems. After giving my explanation I became curious about how the problem was solved before computers and the sophisticated algorithms and protocols we have today. The answer was quite supprising.
By chance, I needed to look up the entomology of robot. I’d always assumed that robot was a word invented by Asimov in the 1960s for one of his early Sci-Fi novels. As I discovered, this is far from the truth. Robots were eighteenth century, European farm labourers! A landowner would loan a plot of land from his estate to the robot and in return the robot would toil in the main estate as repayment. The practice was eventually abolished in 1848 since it was considered a form of bonded labour.
The European agricultural robots had no written contract with the landowner so there was a problem to overcome; how to resolve any disputes between landowner and robot. Landowners could evict robots at any time without consequences and robots could refuse to work on the main estate.
The English agricultural workforce had an equivalent to the robot called Indentured labourers and they had a written document detailing the agreement to solve the dispute problem. A copy of the document could be produced to confirm the agreement between both parties. The obvious second problem being: how to determine that the document was genuine and unaltered.
In modern IT systems, we have a similar problem to the robots and indentured labourers, especially in extended enterprises when systems are disconnected and isolated. If a system sent a document to another system, how would the receiving system verify the message was genuine and unaltered.
For example, Alice sends a message to Mallory saying “Alice shall pay Mallory £100.00”. Mallory mischievously moves the full-stop to the end of the message so it now reads “Alice shall pay Mallory £10000.”. Although this looks like a genuine message the meaning is far from the original intent. How do we stop unscrupulous people altering a message, Mallory is keeping all the right letters but not necessarily in the right order! Non-repudiation is the answer.
Creating a non-repudiation message has a couple of simple steps.
- First, decide on two algorithms, one for a hash and a second for encryption.
- Second, create a hash of the original message. A hash is a small, fixed length value created from a much larger piece of text. A hash algorithm is a one-way function, if you have just the hash value you cannot determine the original text that produced it. Although a hash has a finite set of values, even minor changes to the original text will produce vastly different hash values. The chances of modifying the original text with a specific meaning and producing the same hash value is almost impossible.
- Third, the hash value is then encrypted using the author’s private key. Anyone can verify the author’s message if they have: the author’s public key, the original message, the encrypted hash and the two algorithms used in the process.
- Fourth, the receiver applies the hash algorithm to the message.
- Fifth, the receiver decrypts the encrypted hash provide by the author.
- Finally, check the decrypted hash value is the same as the hash value calculated in step four.
That is how we solve the repudiation problem with computers but how did our forefathers ensure that these documents were unaltered given most of the population couldn’t read nor write and ‘X’ was often the only signature available. No computers, no certificate authorities, Diffie and Hellman weren’t even a twinkle in the their great, great, great, great, great grandfather’s eyes.
Contracts between indenturee and landowners were written twice on a single document. The document was cut in half using a random zig-zag or tooth like pattern, hence the derivation from denture. Each party retained their half of the contract. No two contract terminators would look the same given the random cutting pattern and the bisected words across the intersection. An unscrupulous landowner could attempt a ‘brute force’ attack of creating a new half of his contract to match the other’s terminator. However, the effort to create an exact match of the contract’s terminator would far out weight the value of the contract – a situation that hopefully exists today.
For important contracts, three copies of the contract were written on a document and cut into three sections. The middle section going to a trusted authority, usually a judge or lawyer. In this case, either the landowner or the indenturee could call upon the authority to confirm the details of the contract.
Conclusion
The early approach to deal with repudiation does not exactly match today’s approach. There have been improvements on the way the pattern is implemented, which is entirely expected. The introduction of agreed standards, proven algorithms, Certificate Authorities as well as dedicated hardware makes things a lot more robust. However, I truly admire the simplicity and elegance of a solution that is based on a pair of scissors.