Rudimentary Cryptology: Keeping Secrets

TLDR: A walkthrough of basic cryptography principles.

Introduction

The interest in my previous article was great, but it invariably led to many giving responses similar to the ones mentioned in the article itself. It seems that despite talking to an IT security-minded subset of society of mostly IT professionals interested in cryptography, it is fair to say the overwhelming majority of them did not feel comfortable tackling the puzzle I set. This stems from the fact that they believe they lack the knowledge and skills to understand the article itself, I probably wouldn't go quite that far myself, but there is a hurdle there holding people back. The feedback was such that before I had even published that article I had already agreed to write a series on the basics of cryptography, so here we are. Hopefully, this will provide people with knowledge and skills to form a jumping-off point to allow people to dive into cryptography.

I have tried to build this in a way that relies on building intuitions about what is going on that we later define in maths. This is because it stays away from the maths initially which people find to be a barrier and instead focuses on allowing the learner to develop a concept of how it works that they can test. Once they have that, maths is introduced so they can make a mental link about how what they know is written down. The reason for not avoiding maths entirely is that it is useful, you see, I don't expect everything you learn about cryptography to be from me, so if I can provide you with the knowledge of what maths means by pairing it with intuitions you already understand when you see that maths in other texts on the subject, you will know what it means and be able to build on that.

Tools

So before we get started I wanted to look at some existing tools that can help us as we learn. First up are some deciphering tools GCHQ's CyberChef is really useful it's full of all sorts of data processing and encryption/decryption techniques, and you can even chain them together to quickly get the results you need. DCode is a super handy tool for the cryptanalysis side of things, it's got a super handy frequency analysis tool amongst other things. There are also a ton of hash cracker sites for cracking well-known and weak hashes, just google it when you need one.

There are also a number of tools for learning cryptography that I've found quite helpful. First up there's Khan Academy this might seem almost a bit too basic for the subject matter but trust me it isn't. The particular course I've linked is entirely free of charge and teaches a lot of fundamental computer science and cryptographic knowledge, heck it is even one of the pieces of source material I used to write this article. Next up we have CryptoHack as it says it's a learning platform for cryptography, I would very much recommend signing up to their discord if you can as it's full of crypto whiz-kids, way smarter than me. I would also recommend picking up some books if you want to learn more, I can definitely recommend A Cryptography Primer by Philip N. Klein and Cybercryptography: Applicable Cryptography for Cyberspace Security by Song Y. Yan as these books helped me to understand a lot of the topics. Another good resource for me was the Introduction to Cryptography Lecture Series by Christof Paar. Finally I have some additional research tools for you, a bunch of programs I've built for doing the heavy lifting in cryptosystems. Rather than give you them straight away, I'll show you how to build them, so you know what they're doing and when to use them.

What is Cryptography?

Try to answer the question directly and you may find yourself relying on specific rigorous concepts or circular explanations, but what exactly is cryptography at its most basic? Like most things with computers it doesn't make much sense without some form of information, so lets assume I'm a wizard and I can use the phrase "Hocus Pocus" to perform any sort of magic I like. I want a cheeseburger? No problem, one quick utterance and poof the cheeseburger is mine. The problem is this is immensely powerful, if I were so inclined I could give your dog extra spots, the horror! Worse still, I'm not the only wizard, and some of them might be evil, if they learn my magic words that would be very bad, they could cause all sorts of mischief. There's only one thing for it, I'll have to make sure I never tell anyone those magic words. This has done two things, 1, we have recognized "Hocus Pocus" as a piece of valuable information, and 2, we have decided to keep it secret to prevent mischief. This in a way is like a form of cryptography, my choice to never share the phrase with anyone prevents them discovering what the phrase is and therefore prevents them using it, of course how does one then perform magic in the presence of others?

This is the core of what cryptography is, you begin with a piece of information and an intent to keep it secret, this is what is referred to as controlled information asymmetry. That's a complex phrase so lets unpack it, "controlled" refers to our wish to keep it secret and control who gets access, "information" refers the piece of information itself our "Hocus Pocus" phrase, and "asymmetry" refers to the fact that I know it, but other potentially evil wizards do not, therefore it isn't symmetrical in how it is distributed. In fact those evil wizards are why cryptography exists, as without an adversary the problem simply evaporates, we need someone to keep the secret from. Cryptography then is about keeping secrets, over time it has evolved to do more than this and it crops up in all sorts of ways.

Lets say I write you a letter, and send it via owl (as all good wizards do) and the owl drops it off on your desk, you open it and read it. How do you know I sent it? I mean it could also have been sent by my twin, the evil wizard N4d!r, how would you tell the difference? Well pretty simply actually as N4d!r has annoyingly perfect handwriting with fancy loops and everything, but the one thing he can't do is replicate my scrawl, especially not my signature which looks like a spider dipped itself in ink and crawled across the page dragging its entrails behind it before exploding. So a simple check of the signature will confirm it must be from me, this is a something known in security as authenticity, and it all relies on the uniqueness and inability for other people to replicate that signature. Okay so the message came from me, but how do we know N4d!r didn't alter the wording of the letter or, cut off the signature and attach it to an entirely different one? I mean he would only need to capture my owl in flight to do that and it flies right past his tower. That's why like all good wizards I seal and rubber stamp every letter I send of course, if that seal is broken when it arrives on your desk you immediately know something is wrong and the message has been tampered with. This is something in security we call integrity, the simple act of ensuring the information cannot be altered in transit without breaking the seal.

I know what you're wondering, "why don't we let Larry the Cat run the country?" trust me he's a much worse tyrant, we don't want that, but more importantly have you ever considered what the rubber stamp is for? I mean a blank seal still tells you if anyone tampered with it. Well firstly it's aesthetically pleasing to get a pretty little image on the seal and that reason alone is enough, but it does have a use. Each rubber stamp is unique to its wizard, they alone can make it with their personal magic, it can't be replicated, like a signature. But what do we need that for when we already signed the letter? Well, the letter tells you I wrote it but it could just have been sat as a draft on my desk when someone sent it without my permission to cause chaos and insurrection within the wizard ranks. The rubber stamp confirms that not only did I write it, I sent it out too, and you can retain that seal as proof that I did, this is known as non-repudiation, where it becomes impossible to deny that I was the one who sent it. This is important if you are writing things like decrees, so people can trust you aren't simply going to claim it was faked. How all these pieces work is what the rest of the series aims to unpick, but now you understand the basic terminology and what they aim to do.

Laying Out the Principles

Before we dive any further, lets iron out some of the words. For a start I've named the article "Cryptology" what even is that? Well we've just defined what Cryptography is in an intuitive way so how does it differ? Cryptology is derived from Greek kryptos "hidden" and logos "word/science", so hidden information is a good description, to give it a more formal definition Cryptology is the science of hidden/hiding information. Sounds exactly like Cryptography, but its actually bigger, Cryptography is using this science to secure information by creation of a Cryptosystem, the good guys or blue team if you will. Cryptology includes Cryptography, and also Cryptanalysis the usage of the science to break a Cryptosystem, the bad guys or red team. For the record I don't like good/bad as it unnecessarily attaches morality, a ransomware developer for example encrypts your data but you wouldn't call him good. A Cryptosystem obviously then being a system used to Encrypt and Decrypt data to hide its information and recover it when required, a good way to think about a Cryptosystem is like a box with a lock on it. Encryption is the act of hiding the information, so you put your letter in the box and lock it, and conversely Decryption is the act of revealing hidden information, you unlock the box and remove the letter. We also use the terms Plaintext and Ciphertext, they are fairly self explanatory Plaintext is the raw unencrypted information, the letter, Ciphertext is encrypted information, the locked box, so we can reasonably conclude a Cryptosystem looks like this:

This system raises a further question as to what is a cipher, here it is the vague notion of how we alter the information to keep it secret, the exact method depends on the system, so in this general case we can think of the cipher as the lock, though it does have a more specific meaning a bit later on. As a final note here on terminology, we talk about lots of things like keys, hashes, salts, nonces, etc. These are implementation details and I'll explain them as they come up, but generally speaking they are just strings of data with particular uniqueness qualities to them, so a bit like the signature and the stamp. Hopefully these explanations help demystify it a bit. So now we have some idea what the fancy words mean, a vague understanding of what cryptography aims to do, and even a rough idea as to the structure of how these systems operate. The main point of a Cryptosystem then is to alter information to keep it secret from an adversary but in such a way as it can still be recovered by the intended recipient, this is the basis on which Cryptography is built.

Introducing Eve

Cryptologists use abstract diagrams to help them reason about how cryptosystems work. In its simplest form we are talking about a transfer of information from one person to another, communication, Cryptologists describe this by inventing two arbitrary people, traditionally they tend to call them Alice and Bob as their initials are A and B. Alice and Bob want to talk to each other, but they want to talk about something in private, maybe they need to discuss an upcoming Illuminati meeting but they don't have a private space available. As long as its just them it doesn't matter as there's nobody to overhear, but then in strolls Eve, Eve is not a member of the Illuminati and now conversation must stop otherwise it wouldn't be a secret society. Eve is an interesting choice of name but its the most common convention, you would expect something beginning with C, but E was chosen instead, presumably to imply Evil, in which case who better than Eve which I personally think is a little unfair but I'm not going to lecture you about how Lucifer was only trying to help. Eve is just what they use as standard and you can pick any name you like in your diagrams but Alice, Bob and Eve will be what you see time and again, so it's probably best to get used to it. Your basic diagram with them communicating over an insecure channel will look something like this:

Great, except Eve is just going to get all the secret information, which is not so great. What Alice and Bob need, is a secure channel, a means to communicate that Eve can't access. A simple way to do this is if Alice starts talking in French, Eve can't understand French and so is suddenly unable to understand anything Alice says. This does create a secure channel, but is perhaps not the best choice, it is possible to pick up a surprising amount from tone, gestures and context, Eve will likely immediately suspect Alice is trying to hide something, and languages have similarities, so there is a very real risk Eve may still discover the secrets. In any case Bob doesn't speak French either so this doesn't really work very well. What they really need is something that turns what Alice says into gibberish but Bob can still understand her perfectly, which is where ciphers come in, we'll get to them in a moment.

Why is a secure channel useful though? Surely this is a pretty rare use case? It's more common than you'd think but picture this instead, I am a general with an army preparing to attack a village of enemy soldiers in the river valley. I know that my colleague General Marcus has arrived on the other side of the valley with his army and we are preparing for a pincer attack. The enemy doesn't know we are here and the success of our attack relies on the element of surprise, it also relies on us attacking at the same time to ensure we have the numbers to win by splitting their defence. I have decided we shall attack at 4am tomorrow when they least suspect it. The problem is I need to let General Marcus know meaning I need to send a messenger, but there is only 1 river crossing, right at the heart of their village, otherwise the messenger would have to travel around which takes about 3 days. Our supplies are running low and we cannot afford to wait that long, but it is a guarantee that using the river crossing will have the messenger searched.

The locked box would be great right now, except the enemy will smash it open, so I need something less obvious. If I use a cipher to encrypt my message, it will make no sense to the enemy and they will allow the messenger to pass without learning anything. Marcus will then be able to use his knowledge of the cipher to decrypt the message. This is the value of a secure channel over physical security, while secure channels can be brute forced it is not as simple as smashing the lock, you have to prize apart the mechanism piece by piece, see above an example of how this subtly alters the communication diagram.

Obscurity

Why don't we talk about obscurity? I mean surely to keep information hidden it just needs to be baffling right? Or at least unpleasant sounding enough nobody wants to look into it. Think about it, if I want to send a secret letter, how about I just write the letter as normal, then write "Tax returns" on the envelope? Nobody is going to want to read that. This is known as security by obscurity, and you may have heard security experts refer to it as a bad idea, but why? Well, lets take another example that might make it more obvious, many of us are very familiar with the difficulties of getting good coffee at work. So what if Enrico your super awesome coffee merchant provides you with some amazing new beans, they're the best thing ever, but you only really drink coffee at work and your colleagues as pleasant as they are, are known for stealing from one another. You decide to give it a go anyway and hide the beans in your desk drawer, for the first few weeks it works perfectly and you have access to amazing coffee with an aroma so pleasant everyone is jealous. Then one day, you open your drawer and dun-dun-DUN! They're gone! Who could dare be so bold as to take the greatest beans ever grown and think they could live to tell the tale?

Problem is you don't have the first clue who did it, you never told anyone and you were always so careful, so what went wrong? Well, lets start with the obvious, your plan seemed smart, but that's just the problem, it wasn't, obscurity gives you a false sense of security, and that is it's most deadly weapon. As much as we like to pretend we're unique or random, we humans are pattern crunchers, every second of every day we are following and recognising patterns, its what we do best, and it doesn't take a genius to lock onto your patterns, suddenly that "unique" idea to put it in your cabinet is starting to feel like something everyone would do. The cabinet has a lock on it, the smart plan would have been to lock it, because obscurity isn't a lock, its a picture of one, about as useful as a paper security guard. It just gets worse from here, because once they've learned how to think like you, it doesn't matter where you hide your beans, they'll think of it, because you are the single point of failure.

You can't really test the security of this sort of approach either, because once you've told someone where the beans are, the will know exactly where to look as there is nothing preventing them. Given the right person and enough time, they will try checking in your drawer as well as everywhere else just as a potential place you could have hidden them, I mean the entire office could smell that aroma so it was inevitable they would find them. Worst of all, how could you not have noticed Angela and Steve from accounting watching you like a hawk every time you mentioned coffee. You've played yourself for a fool, because that's what obscurity does. So I don't think my supposed tax returns are going to be very safe somehow.

the Kerckhoffs Doctrine

Who was Auguste Kerckhoffs? Doesn't really matter being honest, beyond he was an old guy who knew what he was talking about, look him up if you like, he's not all that relevant to the subject. As is so often the case, it's what he did that mattered, he redefined the entire way of thinking about cryptography, overturning 2,000 years of bad ideas that seemed to work but wouldn't stand up to scrutiny. So what exactly did he do? He effectively recognized and showed how security by obscurity was the single greatest problem with all cryptography up to that point.

We've just seen the significant pitfalls of relying on obscurity and all of the same applies when you use it to build a cryptosystem. No matter how complex the system, obscurity relies on your ability to outthink the enemy, and while a lot of the time in practice that holds true, it is not something you can rely on, as even Einstein would have pointed out, there is always someone smarter than you. To truly "win" Kerckhoffs realized, you need a system that is verifiably insoluble and intractable (both words that loosely mean unsolvable, insoluble refers to the inability to dissolve it into smaller parts, intractable means effectively uncalculatable) such that even a greater mind would encounter the same problem. Which presented a problem, because you simply cannot verify something that must be kept secret without invalidating its secrecy. So Kerckhoffs came up with his principles that is now often referred to as the Kerckhoffs Doctrine:

The security of a cryptosystem should depend only on the secrecy of the key used, not on the secrecy of the system itself.

• Auguste Kerckhoffs rephrased by Philip N. Klein (2014) A cryptography primer : secrets and promises. Cambridge University Press.

This is actually just one of 6 principles he defined for military communication, but it is largely regarded as the important and relevant bit. Why this is so important is because firstly it stops a lot of the shenanigans that led to such woefully bad cryptosystems, but secondly, by removing secrecy from the system it then opens it up for scrutiny and verification, meaning cryptography can be battle-tested. As explained earlier, the biggest issue with obscurity is how it blinds the creator, leading them to believe their system is secure when it is not, and if the creator cannot be trusted to verify the system, then nobody can ever be sure a system is actually secure, the best they can do is work in uncertainty. The more a system is used and tested without failure or flaws the more certain you can be that it is secure, and confidence in that system grows, whereas those that do fail are obviously not secure.

As it happens it can also be equally difficult to tell if your supposedly super secure cryptosystem is accidentally just an intricate obscurity, which only goes to further the importance of openness in our algorithms. This philosophy is the same one that the entire open source community is founded on, and while there are other factors at play, the general concensus seems to be that open source software is often much better than its closed source counterparts. This is a core foundation that all modern cryptography is founded upon, which is why I have tackled it so early to give it time to sink in. Now we will look at a series of cryptosystems that predate it and how their failures prove the importance of the doctrine in building good cryptosystems.

Alright, this post has become long enough. Next time we tackle historical ciphers and how to attack them.

Manifest | Signature