Wednesday, September 26, 2007

Mary Queen of Scot's Guide to Information Security

Mary's Story

In January 1586, the English throne was in dispute between the Catholic Mary Queen of Scots and the Protestant Queen Elizabeth (whom most of us know today as Kate Blanchett). Fears for Elizabeth's safety escalated, and culminated with Mary being imprisoned in order to stop her from plotting to kill Elizabeth. While imprisoned, Mary conspired with a Catholic nobleman named Anthony Babington to overthrow and possibly execute Elizabeth. Elizabeth's fears were well founded, it seems. They communicated using encoded messages which they believed were of strong enough encoding to stop the royal spies from deciphering.

The messages between Mary and Babington contained two levels of encoding. The 23 unique letters in the English alphabet were substituted with 23 unique symbols. 36 common words and phrases in the language were also substituted with unique symbols. A complete decoding key dated from 1586 and containing Babington's signature follows:

The messages were smuggled in and out of prison through beer barrel stoppers where a nearby brewer delivered and picked up the barrels. Queen Mary's servants would retrieve the messages from the beer barrels and place messages back into the hollow of the beer barrel stopper.

The royal Spy Master intercepted all of the messages between Mary and Babbington. Each message was copied by the Spy Master and then sent on to its destination intact. Each message was decoded by trial and error by starting with letter substitutions and using the frequency of common characters (frequency analysis) until a readable text was found. The rest of the message was guessed at by the message context until the entire cipher was understood. Each message was returned in good enough condition that it was not evident that it had been read and copied.

Once Mary acknowledged the existing plot in an encoded message, the royals used a cipher and language expert to forge a postscript to the same message asking Babbington for the identity of the six conspirators. Babington received the forged postscript and message, but he never replied with the names of the conspirators. Nevertheless, he and the six conspirators were discovered and imprisoned. The forged postscript can still be found today in the National Archives:

Queen Mary denied her part in the plot, but her correspondence was the evidence; therefore, Mary was sentenced to death. Elizabeth signed her cousin's death warrant, and on February 8 1587, in front of 300 witnesses, Mary, Queen of Scots, was executed.


Q. Confidentiality is the concept of protecting sensitive data from being viewable by an unauthorized entity. Were the secret communications confidential? How would the answers from Mary and Elizabeth differ?

A. Mary would say the messages were confidential, because she believed that her encoding scheme was strong enough to secure the data even though it was publicly transmitted. Elizabeth knew otherwise, as she had cracked Mary's code. The message passing protocol, involving the brewer and beer barrel stoppers had little to do with confidentiality, because both parties assumed that the messages could be intercepted. The encoding, rather than their messaging system, was their primary method to obtain confidentiality. In this case, a stronger encoding or encryption algorithm would be needed to maintain confidentiality in the messages.

Q. Integrity is the concept of ensuring that data has not been altered by an unknown entity during its transit or storage. Did the messages have integrity? What would the answers from Elizabeth and Babington differ?

A. For the most part, Elizabeth and her Spy Master maintained the integrity of the messages by not altering them in transit. However, the last message contained a forged post script in an attempt to extract more information from the plotters. Elizabeth certainly knew this last message had no integrity, but did Babington? He never replied to the message, so he might have realized the message was a fake. From his perspective, all of the messages except the last one had integrity.

Q. Authentication is the concept of ensuring that a user's identity is truly what the user claims to be. Did the messages ensure that the author was truly the person they said they were? How could the system be changed to ensure authentication?

A. There are three broad bases to proving you are who you say you are: what you know, what you have, and what you are. The authentication scheme here is based on what you know... Mary and Babington believed only they knew the encoding scheme. So the author's identity was proven on the simple basis that the encoded message made sense when decoded. Passwords and personal questions are today's equivalent of a "what you know" authentication scheme. "What you have" was a common authentication scheme in the 1500s. Nobles would seal a document with wax and press their signet ring into wax, leaving a somewhat unforgeable impression of their identity in the envelope. Smartcards, ID Chips, and Secure ID cards are today's examples of "what you have" authentication. "What you are" was probably infrequently used in the middle ages, as a fingerprint was not noticed to be unique in the West until 1823. 14th century Persia knew and used this authentication technique, but like many things from Arabia, the technology never migrated West and was not "discovered" until much later. Today all sorts of biometric devices can be used for authentication, from hand size to retina scans.

One easy way to ensure authentication would have been to encrypt a signature line into each message, possibly based on some astronomical chart or calendar. However, Babington did not seem fooled by the one forged message, so perhaps their messages contained an authentication scheme we don't know about.

Q. Authorization is the concept of determining what actions a user is allowed to perform after being allowed access to the system. Was any authorization system in this system? How would one have helped?

A. Short answer: no. The only functions available in the system were to read or write a message. Any authenticated user could do both.

Q. Non-repudiation is the concept that when a user performs an action on data, such as sending a message, that action must be bound with the user in such a way that the user cannot deny performing the action. Did this message system contain non-repudiation? How is non-repudiation achieved today?

A. To this day, there is no definitive proof that Mary wrote the messages. The system contained no non-repudiation. Non-repudiative messaging system today rely on public/private key exchanges (PKI) and asymmetric encryption algorithms. Any message that can be decoded with a person's public key is mathematically guaranteed to have been generated with their private key. Often today, plain text (unsecured) emails are exchanged, and the email's signature line contains a small encrypted message. The recipient can decrypt the message with the author's public key and thus prove the identity of the author. Nonetheless, Mary was executed. The court of law has lower standards than information exchange, it seems.

Epilogue: Elizabeth was reluctant to execute Mary, for she realized that once a sovereign became answerable for the common man's crimes, the belief that a king's or queen's actions were accountable only to God would be undercut and ultimately challenge the structure upon which her authority was founded.


Scott said...

Does anyone know how the encoding scheme was communicated to Mary if she was under lock and key at the time of the plot's formation?

Hamlet D'Arcy said...

I've tried to search for details about how they performed their key exchange but haven't found anything. Perhaps a book on the subject might contain details... or perhaps the answer is lost to history.

If you find out please post!

Jimmy said...

The amount of info you have here is more than I can find online. Do you have some sources?

Hamlet D'Arcy said...

Simon Signh's book "The Code Book" (which has a bibliography), wikipedia, and I think an article from the Guardian (IIRC).