Entropy - what is it, what does it mean and why is it useful?

Entropy is fascinating. It is a measure of the disorderliness of a system - and so, not unsurprisingly, it has a tendency to increase. You can't un-bake a cake, as they say. Organising, sorting and tidying are all counter-measures, but like recycling, it turns out that the real universe is more complex and tricky to work with than you might hope, and so trying to do 'the right thing' often has the opposite effect.

Measuring entropy is one of the activities that cryptographers use when designing random number generators. I always like the irony of a universe where there is an increasing amount of disorder, but when you want to make a source of random-ness, then it always seems to be infected with hidden layers of predictability. Random noise seems to be one of those nice ideas that is very difficult to obtain in practice, because there are a huge number of repetitive, predictable sources of information that drown out the random-ness. So random noise generation becomes a search for how to remove bias, or interference from non-random sources, followed by the refinement of statistical techniques to show how successful the removal has been.

As I have noted before, the better the encoding and encryption technique used, the more the resulting output looks like random noise. My 'think about things from a different viewpoint' brain takes that and inverts it, arriving at the conclusion that truly random noise must contain hidden information - but we just don't know the key (or the coding scheme!) and so can't decode it. I'm sure there is lots of money to be made from this type of thing, and, of course, there is!

Hackers also use entropy, but often for different reasons. If cryptographers have put lots of effort into making encryption produce noise-like data, then one way to look for encrypted data is to look for randomness. Firmware is a good place to look, because it is usually an intrinsic part of the underlying platform that services are built on, and so is an appealing target. So hackers look at firmware in a number of ways, which I always think of as different 'filters'...

The first filter that most people use is my old favourite: ASCII characters and strings. Open the extracted firmware (or data file containing it!) in a hex editor, and look for readable characters - for some reason, hex editors always seem to have a strict ordering of columns: index on the left, then the data in hex, and then the same data in ASCII printable characters. In the old 8-bit days, then you could expect to see lots of strings containing everything that appeared on the screen as text, plus lots of things that the programmer probably didn't want you to ever see: debug messages, passwords or cheat codes for reviewers/managers, initialisation settings, and more. As time has gone on, there is less and less useful information to be found, but sometimes... Wherever valuables are hidden, then there are people who will make tools to help the search. So truffleHog is just one example of a utility that searches for interesting strings on GitHub, and there are lots of other 'Information Gathering' and 'Reconnaissance' tools that will attempt to locate strings. The example screenshot above shows HexFiend,  a hex editor for MacOS, looking at itself...

What I look for in a hex editor, of course, is the ability to add offsets, to rotate, to invert and to do other 'ASCII-obscuring'-related processes in order to try and locate obfuscated strings...

Another filter that is used relates to randomness. Utilities like binwalk provide a graph that shows Entropy on the vertical axis, and index (position within the file) on the horizontal axis (binwalk does lots of other things too!). The binwalk example file shows exactly the sort of graph that the hacker probably isn't looking for: on the left, a short block with low entropy, followed by a big block with an entropy of about 0.6, followed by another short block with low entropy, then a block of about 0.5... and finally, a long block with low entropy. Nowhere in this graph is a flat block up at the 1.0 level, which would usually be inferred to mean either encrypted data, or better, keys!

(As often happens, one thing leads to another, so this thinking about binwalk took me in a very different direction, which will feature in a future blog post...)

The problem with just typing >binwalk -E filename.bin and then looking at the graph is that people get told that a flat line at 1.0 means encrypted or key data (with a short flat spike probably indicating keys!), a rough line peaking at 1.0 but with little spikes down to 0.9 or so means compressed, flat areas with zero entropy are just fixed data, and anything else is code. There's a problem here, and it relates to knowing what entropy is.

Remember that entropy is a measure of disorder. So when it is up at 1.0, it means that each successive value is very different to the previous one, and so on. - random values! Conversely, down at 0, it means that each successive value is no different to the previous one, etc. Note that 'no different' does not mean: '00 00 00 00 00...', it means lots of repeated values. So the graph doesn't show the values, it shows the variability instead.

With all of this in mind, we can now think about hiding data. If I was trying to hide keys or encrypted code inside firmware, knowing that people would use binwalk to find those keys, then all I need to do is to change the variability of the keys or encrypted code. One simple way to do this is to just add zero bytes (or any other value) every n bytes. If we add 00 every other byte then we have an entropy of zero for the 00 bytes, and 1 for the keys or code, giving an overall entropy of 0.5. We have doubled the size of the data, but for keys this does not matter, and extracting the keys is trivial! However, if you look at the obscured key data in a hex editor, then all of those 00 bytes will be obvious...

Alternatively, you could split the keys or code into nibbles: half bytes. So 7E would become 70 and 0E. If I do this to lots of data, then there are only 32 different values: 0-F followed by 0, or 0 followed by 0-F. The entropy is now not anywhere near 1.0 any longer, because all those zeroes reduce the variability - you can predict that there will be a zero either at the start or the end of the two character hex digit. But the data isn't fixed either (it isn't just 7E 7E 7E 7E 7E...), and so the entropy is about 0.5. Not only that, but looking at the data in a hex editor, it is going to be much harder to spot the zeroes. The cost of this better obfuscation is that the extraction of the keys is slightly harder... So now the key data isn't going to be obvious in either binwalk or a hex editor. In other words, you can 'design' the entropy of your data if you know what is being measured.

When I wrote this, it didn't seem that special. But now, when I go back to it, the idea that you can edit your data so that you control the entropy is very interesting indeed! It kind of takes back some of the power that randomness takes away from you...

---

Many articles these days use clickbait techniques to get your click, and then break that trust by never actually answering any of the questions they pose. So, let's prevent this right here and now:

Entropy - what is it?

The second sentence (I've never recovered fully from the Amazon review of my book where someone counted the number of pages before I actually said what something did...) tries to describe entropy without being a definition: 'a measure of the disorderliness...' . But two sentences later, my favourite is the 'un-bake a cake' metaphor. Maybe I should have said: You can't un-write a blog post...'!

Entropy - what does it mean?

This is the real fascinating thing about entropy: the more efficient you encode or encrypt something, the higher the entropy, and the more it stands out and waves a flag saying: 'Here I am!'. And the mitigation that I suggest is to reduce that efficiency by making it bigger! I suppose that having it secure and hard to find is a good compromise, but I'm now wondering if there is a way of reducing the entropy algorithmically that is hard to detect - and ultimately, the optimum way of doing that would probably also look something like noise - but special noise that has the effect of reducing the entropy of the actual data than looks like noise because it is efficiently encrypted or encoded. Unfortunately, I'm not a good enough cryptographer to to able to figure out if this can be done, but I'm always open to feedback!

Entropy - why is it useful?

The third paragraph is my 'reverse way of looking at the way the world works' moment: You can use entropy as a measure of how good your encoding or encryption is. I've always loved the way that this is the opposite of sayings like 'the perfect shape is a circle...'. Playing double jeopardy then, it follows that the more ordered a system is, the worse the encoding or encryption. In this case, the universe contains a lot of very badly encoded and encrypted information, and I am very, so very glad that we don't have the keys or the algorithms!

---

If you find my writing helpful, informative or entertaining, then please consider visiting the following  link for my Synthesizerwriter alias (I write several blogs, but it makes sense to only have one 'Coffee' donation link!):

Buy me a coffee

Puzzles and security - a synergistic relationship?

Apparently, human beings are hard-wired to detect patterns. Sometimes this is good, but sometimes it can be too effective, or misleading, or subject-to-multiple-interpretations... A cynic might rewrite it as:

Humans are hard-wired to detect patterns, even when the patterns aren't there...

Patterns are very important in security, or, to put it another way: the hiding of patterns is often very important in security. Encryption is a good example of a way of hiding the patterns of ASCII-encoded text data and making them look slightly more noise-like. 'Obfuscation' is that wonderful word for hiding something in plain sight. I always remember something that was drilled into me when I worked on audio encoding:

The better the coding scheme, the more the output looks like noise.

And this hooks very nicely into the way that people use entropy as a way to find encoded data - plain program code has low entropy, but encrypted passwords (or other important/valuable data) have high entropy. So scanning code for high entropy sections would seem to be a good way of finding interesting encrypted data...

Unfortunately, one of the obvious things to do when you start to protect data with encryption is to hide it in similar data. Encryption is not the only way to increase the entropy of program code, of course, just applying a simple compression scheme would also work. This 'one action leads to a corresponding follow-up action, which then leads to another action...' is the 'climbing a ladder' escalation analogy that can be used to model all sorts of interchanges. 

Puzzles are interesting because they can train you to look at problems in many different ways, and breaking assumptions - one of the other things that humans are very good at is making assumptions, of course. 

So, let's look at one of the puzzles on the Nullcon 2020 badge (and the answers), and see how it encourages potential puzzle solvers (like security analysts and cryptographers) to think laterally.

Here's what part of the top of the badge looks like:

 (There's something about the look of 'fluorescent green plastic' that makes it appear super-cool!)

Puzzle setters like myself know that there are clues that give away typical encodings that are used for text, so any numbers between 46 and 122 (decimal) would tend to suggest an ASCII encoding (A-z, plus 0-9 plus '.' and '/'), which would be confirmed by having lots of '32's indicating spaces. In this case, the initial number is '00', which is deliberate misdirection, and is based on people initially looking at the beginning and ending of sequences - putting the 32 mid-sequence kind of hides it amongst the other numbers.

So the '00' is hopefully going to cause some people to immediately reject this as being ASCII-encoded text, but then if they look closer, they will see the '32' and note that all the other numbers are between 48 and 122... Which means that it probably is ASCII-encoded text, but that the first character is different or special in some way. One thought at this point might be that this is an index: the first piece of encoded text might be preceded by a zero, and so other encoded text would then be examined to see if the initial numbers were 01, 02 03, etc. But the other number puzzles on the badge do not follow this sequence (so one obfuscation method that a puzzle setter could potentially use would be to deliberately offset ASCII-encoded text so that the first number is an ascending index or offset...) and so there must be something else about the number '00'. Looking it up on an ASCII table quickly reveals the secret: 00 is the decimal number that represents the archaic non-printing 'NULL' character, and given the name of the conference for this badge (Nullcon!), it is obvious that the Null character is being used to replace four ASCII numbers with a single shortcut number!

One can imagine a puzzle setter who exploits this to encode other words with appropriately similar  extensions using the ASCII characters outside of the ./A-z, 0-9 (46-122) range. If the fictional conference called 'DevCan' wanted a badge, then this could be encoded with 127 (character for 'DEL' (delete)), then 08 ('backspace'), then 11 ('VT', the 08 ('backspace'), then 24 (character for 'CAN' (cancel)). Thus giving 127 08 11 08 24 for encoding DevCan. That 127 is a dead giveaway, so I suspect that the hex versions would be used instead: 7F 08 0B 08 18.

For Hex-encoded ASCII, then the numbers that people look for are 2E to 7B (./0-9A-z), so those two 08s and the 18 are good misdirection!

If the puzzle solver approaches things from the opposite end of the sequence (often a good technique to try), then the last four numbers are all inside the 0-9 range of 48-57 (decimal), and so are obviously numbers. Decoding them to '2020' is another strong clue that this is ASCII-encoded text.

Finally, there's the 32, which is like a waving red flag to anyone who is looking for ASCII-encoded text! One approach that a puzzler might take would be to replace this with another character: 00 (Null) being one candidate. But in this case, 00 is already used, so another character would be used. Using 00 (Null) as a replacement character for 'Space' might be something that a specific puzzle setter has used previously, of course, and so knowing who set the puzzle might be useful. Conversely, puzzle setters might strive to avoid using the same obfuscation methods more than once.

One difference between a puzzle and real world decoding is that puzzle setters like to give clues. The 32 in the middle of this sequence is one example, but for a conference called Nullcon, with a badge that has the word 'Nullconium' as well as 'Nullcon' written in a weird 'falling-over' books font, then there are lots of pointers to 'Nullcon' being a likely candidate for some encoded text on the badge - especially given the 'Periodic Table tile' / 'Top Trumps card' metaphor of the badge design.

If you have read this far, then you should now have had a glimpse of how puzzles like the Nullcon badge can encourage you to take an oblique look at problems, and thus may help you to solve your next challenge in an inventive and unusual way. And the world definitely needs novel solutions!

---

If you find my writing helpful, informative or entertaining, then please consider visiting the following  link for my Synthesizerwriter alias (I write several blogs, but it makes sense to only have one 'Coffee' donation link!):

Buy me a coffee