Randomness: The Heart of Cryptography
Now let’s talk about randomness. Randomness is at the core of cryptography.
There’s no such thing as true randomness created by a computer. Computers use algorithms and generate what we call “pseudo-randomness,” that is they generate something that is as close to random as they can get.
In Minecraft, the game will randomly generate a new terrain everytime you start a new world. But, if you really like a terrain and you want to recreate it, then you can get the seed for that terrain and use the seed to recreate the exact same terrain. So it seems random at first, but if you are able to recreate a terrain exactly, then it must not be totally random. This is what we call pseudo-random.
The same concept applies to random number generators on computers. Computer algorithms also use seeds when they generate pseudo-random numbers. Play around with the Random Numer Generator below. It will use your seed to generate 5 random numbers.
- Middle Squares is a method used to generate pseudo-random numbers. Do you notice a pattern of how the random numbers are generated by looking at the numbers and their squares?
- What happens if you use the same seed?
- Do you think this is a good pseudo-random generator? Why or why not?
- Try using 0 as the seed. Now try 100. Now try 50. What do you see happening?
A good pseudo-random generator should not depend much on the seed. It should also have a long cycle, meaning it should visit every number in its range before it starts repeating itself.
At first, the Middle Square Generator seems very random, but the more you mess around with it the more you will find that it is easy to break. Hence, it is not a very good pseudo-random number generator.
So What Does True Random Look Like?
Take this image of a Gnu. This is the image in it’s normal form, but we would like to encrypt it so that it looks completely random.
This is our first attempt at encrypting our Gnu, but we did not do a very good job. You can still see the outline of the Gnu, and the encryption used 1 pattern for the white parts of the image and another pattern for the black parts of the image. This simple encryption made it easy to tell what the true image is.
This is an image of white noise, and this is ideally what our encrypted Gnu should look like. You can’t make out any hidden pictures from this image, and it looks totally random. This is the standard that cryptographers strive for when encrypting data (letters, numbers, AND pixels).
The Lava Lamp Wall
We now know that computers are great at generating pseudo-random numbers, but they are not so great at generating true random numbers.
That doesn’t mean that we gave up, instead someone found another way to generate true-randomness: lava lamps!
There is a company called Cloudflare that is based in San Francisco, CA. They use lava lamps to generate randomness and they are responsible for keeping 10% of the internet secure.
Watch this YouTube video to learn about Cloudflare and their lava lamp wall.
Can True Random Ever Work?
Let’s look back at the Wacky Encryption from the beginning of our lesson.
Is this encryption true-randomness or pseudo-randomness?
What are the pros and cons of this encryption from a cryptography perspective? Think about the level of encryption (how random it is) and the practicality of it (how easy it is to use).
Can true random ever work?
Building a wall is a lot easier than building a lockable door. If you were to make a truly random encryption, how would you decrypt it? The sweetspot lies in making an encryption that is pretty random, but most importantly has a secure key for decryption.
In cryptography, there’s something called Kerckhoffs’s Principle. Basically, this principle states that the security of an encryption scheme should be the security of the key if the lock is built right. That’s a little confusing, so lets think about this principle in terms we understand.
This bookcase is the entrance to the CRABS headquarters. In this entrance, the lock is the book and the key is pulling on the book. As cool as it looks, this bookcase is not secure. The CRABS try to keep this bookcase hidden, because they know that a STARS agent could browse the bookcase (not knowing that it’s a secret door) and stumble upon the right book by accident. Then, the STARS can break into the CRABS headquarters!
It would be more secure if everyone already knows where the lock is, but the key is very secure.
This door is the entrance to the STARS headquarters. Any CRABS can see the locks on the door in plain sight, and they know it is the entrance. However, none of the CRABS can get through the door because they don’t have the key (or keys) to get in. Even though the lock is more obvious, it doesn’t matter because the key is more secure. So the STARS headquarters is safe from any CRABS who want to break in.
What is True Secrecy?
True secrecy (aka the best lock and key) is this:
When given an encrypted output, every conceivable input is equally likely.
If you are given any cipher from yesterday where the coded message is just “Y”, what was the input?
CSPRNG stands for Cryptographically Secure PseudoRandom Number Generator. A CSPRNG generates numbers that are guaranteed to be absolutely random. They typically utilize mixing of two pieces of data. One of those pieces is usually some kind of environmental data that is hard for an outside observer to predict, such as the time between keystrokes. We heard about this kind of environmental data in the Cloudflare video.
Here we have a CSPRNG that uses AES (Advanced Encryption Standard). There’s a lot of big words here that we don’t necessarilly need to understand in order to get the concept. Basically what’s happening is that this random generator mixes your secret key (known to you and your partner) with a random number (that changes with every new encryption) and performs a cipher or ciphers on the output. These steps are repeated a certain number of times which is determined by the bytes that you choose.
Click on the link above to play around with the CSPRNG.
Kerckhoff’s Principle Quiz
Think back to all of the enncoding and encrypting we’ve done so far.
Which ones were examples of Kerckhoff’s Principle (public code with a secure key)?
Which ones were examples of security by obscurity (hidden code that is easy to crack)?
- Caesar Cipher
- The Wacky Encryption
- Number Coding (Binary, Base64, etc.)
- Middle Squares
- CSPRNG from AES
Upping the Security of the Wacky Encryption
Imagine if we took a plaintext message and performed a Caesar Cipher on it. Then, we perform a Substitution Cipher on that output. Then, we put that output into Base64. You can imagine that as we keep piling on these ciphers, the message gets more secure. We can see this in action by performing a Caesar Cipher on the output of the Wacky Encryption. Take an encrypted message and increase every number by the same amount. Now when you decrypt the message in the Wacky Encryption, it will produce a Caesar Cipher. Lets try it.
We could also try a similar layering of ciphers with the Middle Squares Random Number Generator.
You will need a partner and then you will follow these steps:
- Decide on a shared number.
- Each partner choose a 5 letter message.
- Put message into A1Z26 encoding with CyberChef.
- Add each encoded number to the number generated by Middle Squares.
- Send your message in the chat to your partner.
- Decode your partner’s message.
End of this Lesson!
Congratulations, you made it to the end of your second day of STARS training!
To mark your achievements, the STARS have presented you with these badges:
Today we learned:
- any data (message, numbers, picture) can be made digital
- digital content can be MIXED with other digital content (our hidden picture)
- if secret messages are MIXED with random content then we have good encryption
- but only if I can create the EXACT random content again
Thanks for learning with us! You can head back to our home page for crypto week, you can check out tomorrow’s lesson, or you can learn more about the different number systems we explored at the beginning of the lesson.
See you tomorrow!