The Queen of the North:

A computational thinking tale

by Paul Curzon, Queen Mary University of London

Once upon a time there were two Queens. They were cousins and each ruled part of a large island. One cousin ruled the South, the other the North. Both believed they were wise and righteous rulers, and that it was their divine right to rule their kingdom. There had been many skirmishes between the two kingdoms over many decades, but more recently a fragile peace had broken out.

The Southern Queen

The Southern Queen had been made Queen as a young woman, and she had a canny understanding of power. There were constant plots against her life from both foreign powers and those within her own kingdom who wanted their own person on the throne. As a result she encouraged her chief minister to set up a spy network across the land, spreading its tentacles to neighbouring countries too. It was incredibly successful and ensured she knew who her real friends were and who were enemies plotting against her. As each new plot was thwarted her grip on the throne grew tighter. She also refused to marry, using hints of marriage to many suitors as a way to keep them all under her thumb, for a marriage to her would have made the man concerned the most powerful man in the land. That was so tempting, they did nothing to risk the prize. The longer she reigned, the stronger her position became.

The Northern Queen

The Northern Queen, by contrast had come to the throne as a baby and so was surrounded by powerful, controlling men who had ruled for her from before she could even walk or talk. She was also unlucky in marriage. She married young to a powerful foreign prince, but soon after the wedding he died. She then married one of her cousins from the South, but their marriage, borne of thoughts of power rather than love, was an unhappy one. The Queen had believed the marriage would strengthen her claim to the southern crown, which she secretly coveted. Her new husband, on the other hand, thought that, as a man, he should not just be a mere husband, supporting his wife the Queen, but be the King in his own right and rule the land himself. The Queen refused to allow this, and so things grew worse and worse between them. It soon became clear her husband was also a bully and a tyrant. This came to a head at a royal banquet. Her husband led a group of his followers to murder one of the banquet guests, a very close friend of the Queen, in front of everyone. This shocked the whole kingdom, and it was clear to the Queen that the marriage could not continue for the good of her country.

Then, one night, there was a great explosion and fire at the palace. The Queen escaped safely, but in the morning her husband's body was found on the lawn outside. He had been murdered in the confusion of the fire. The Queen was, of course, relieved as his plotting was stirring rebellion, though whisperings started amongst her subjects that she must have murdered him herself. Her position as Queen was weakened as a result. It soon became clear that the assassin must have been one of her nobles, and a particular Lord, one of her biggest supporters, was implicated. He had powerful friends in court though, and there wasn't enough evidence to conclusively prove his guilt. He was put on trial but was acquitted.

A rumour soon spread that the murderous Lord intended to marry the Queen himself, and so make himself King. Soon after, as the Queen travelled between palace and castle with her retinue, she was met by the Lord with his own small army. He told her that a rebellion was taking place and great danger awaited her at her castle if she continued. He had come, he said, to escort her to his own castle, where she would be safe. Once there, however, he imprisoned her and then forced her to marry him. He intended to then make himself King, just as her previous husband had. When the news broke however, many in the Queen's court took against them both. It looked to all that the two must have conspired together to kill her previous husband, so that she could marry anew, and so that he could become King.

Because of this, discontent grew and a real rebellion was mounted against both the Queen and her new husband. They raised an army, but lost the ensuing battle. They fled the battlefield, he overseas and she South leaving her own country for the safety of her cousin's land. Once she was gone, the rebels crowned her year-old son the new King of the North - with the plotting nobles, of course, in charge while he grew up, just as had happened with the Queen herself as a girl.

Escaping South

The Queen, who was now no longer a Queen, escaped south by fishing boat and sought sanctuary from her cousin, the Queen of the South. She expected to be given help to regain her rightful throne. However, the Queen of the South's spy network included informers in the north and they had heard her tell of her desire to take over the South. They had passed this on, and so the Queen of the South knew of her cousin's designs on her own kingdom. The southern Queen's spies also told her that many in the South secretly supported her deposed cousin's claim to rule over the whole island.

She therefore 'welcomed' her cousin by placing her immediately under house arrest in a castle a long way from court. Her advisors told her that her cousin was so great a threat that she should be executed, but the Queen could not do that to a regal cousin, not, at least, without her being involved in a clear and credible plot. She held her cousin captive, though in conditions suited to a noblewoman, ... for 18 long years. In the meantime the Queen's spies spread their network, and watched and waited.

Captivity

At the start the cousin had just wanted her kingdom back. But during the long years in captivity she grew more and more desperate and started to believe her only option was to depose the Queen of the South. She was encouraged by her supporters across the land, who also plotted on her behalf. They set up a secret way to communicate with her, a form of steganography - the hiding of messages so others do not even know a message is being communicated. They hid their messages in barrels of Ale that were regularly taken to and from the castle in which she was held. For extra security they also wrote the hidden messages using a cipher, swapping the letters of the alphabet for other symbols. That way, they were sure, even if the messages were discovered, they could not be read. In this way, a plan was agreed to break her out of captivity to lead an army that would rise up against the Queen of the South.

The former Queen was unlucky yet again in her choice of friends. The person who set up their covert means of communication was in fact working for the southern kingdom's spymaster, a double agent who had infiltrated the cousin's circle. He was working for the Queen of the South from the very start. The spymaster had set up a classic man-in-the-middle attack, where a spy secretly receives all messages being sent, reading them before passing them on to their intended destination. Every one of the secret messages had in fact been intercepted and taken to the spymaster, before being delivered onwards. His experts carefully removed the wax seals on the letters. They were then confronted with the cipher. The spymaster, however, knew of an ancient algorithm, called frequency analysis, that had been devised in the East to crack such ciphers. By counting how common each symbol was in the encoded letter and comparing that to the frequencies of letters occurring in their language, it was possible to make good guesses as to which of the symbols were which letters. The most common symbol was likely the most common letter. By substituting the most common letters in to the message, more clues could then be obtained of other letters by seeing which words would be made with the known letters. Gradually the original message could be teased out, letter by letter, until the whole message could be read.

In this way the spymaster read all the messages. As he didn't want the plotters to realise their messages were being read, he then carefully resealed the letters and sent them on their way, back and forth. He was the man-in-the-middle of the attack, reading everything, with the plotters no wiser that all their discussion was being read by their enemy.

The spymaster was even more cunning still. Realising he would need cast-iron proof to convince the Queen of her cousin's ongoing treachery, having deciphered one of the messages to the Queen, he forged an extra message on the end, written it in their own cipher. It asked her to confirm she definitely did support the plot. The Queen, believing the whole message to be from her supporters, as only they knew the cipher, wrote back confirming she definitely supported them. The spymaster decrypted the message and he had, at last the hard, damning evidence he needed. But he did not stop there. He added to a new letter a request, apparently from the Queen, that the plotters tell her the names of all who were involved, so she could be sure she trusted every last one. The plotters duly did so. The spymaster had caught them all!

He had the evidence to convince the Queen that her cousin was a real threat and must die to quash the rebellion that was brewing in her name. She was tried and beheaded. Her co-conspirators died a more gruesome death still. They were rounded up, tortured and then hung, drawn and quartered in public, a very slow and painful way to die.

The Queen of the South, on the other hand, lived a long and prosperous life, eventually dying at a very old age. When she died, however, as she had never married, so had no children, she had no immediate heir. By a twist of fate, the Queen of the North's son who had been King of the North for the past 18 years and was now a young man, was the next in line to the southern throne. He became King of the whole island, so the two kingdoms were, in the end, united. Sadly, it would be untrue to say that everyone, as a result, lived happily ever after.

The End

SPOILER ALERT

The story has a lot of relevance for today. Man-in-the-middle attacks are still used. If you use the free wifi in a cyber-cafe or hotel, everything you communicate could be passing through a hacker’s sniffer program. It could be looking for passwords either in plaintext or encrypted. If encrypted then they can be saved and cracked online. All the communication are passed on as normal so you have no idea what is happening. See for example ‘Piracy on the open wifi‘. Relay attacks on contactless cards or contactless car keys are also a variation on a man-in-the middle attack.

Despite it reading as a Grimm’s fairy tale or perhaps a plot line for the Game of Thrones, the story is all basically true. The story is actually the true story of cousins, Mary Queen of Scots and Elizabeth I of England. It’s not clear whether Mary agreed to marry or was forced to after her abduction. I’ve also collapsed the spies involved in to a single spymaster and his double agent, when in reality several people were involved, but they did set up exactly that man-in-the-middle attack on Mary and even added extra messages on to the end of the messages using the cipher, though it appears they arrested those involved before they had chance to respond to the forged messages.

Oh and if you are interested in what happened to Mary’s last husband…he fled to Denmark where he spent the last 10 years of his life chained to a post in prison.