If you receive some information, how do you know if it’s intact or has been changed?
I’m going to continue explaining how you can detect errors in this episode. Make sure to listen to the previous episode also. And the best option is to subscribe to the podcast through your podcast application so you’ll be sure to get episodes automatically as soon as they’re published.
This is a simple episode but don’t be fooled. I actually learned something myself while preparing this. Something very basic about math. I’ve said many times that you don’t need to know a lot about math in order to program and I’ll always try to simplify and reduce the amount of math that’s needed.
This episode will contain a lesson in logic and another brief math lesson. The actual subject of checksums will then use these techniques. What I’m going to explain about logic is easy but you might want to make sure to listen to the Q&A Friday episode from 2015-Dec-18 first about logic operators. And you should be able to follow along the math lesson with a basic ability to do long division.
Before we get into that, why are checksums used and what are they? A checksum is another way to detect errors. This could help you detect errors when reading, writing, or receiving and sending information. The previous episode explains parity and you can use parity along with checksums if you want. Neither of these will help you detect errors made on purpose where an attacker has tried to hide the evidence. They’re easy to get around and really only good for detecting errors caused by random events or noise.
Using a checksum is not as complicated as using cryptography. I’ll explain cryptography in future episodes. Checksums have an advantage similar to parity; they’re easy and fast to calculate.
The word checksum usually refers to the result of the calculation. It’s an extra piece of information that gets added onto your data that does as the name suggests. It allows you to check the sum.
I’ll describe two different ways to create a checksum in this episode, longitudinal parity check and Fletcher checksum. Listen to the full episode or read the full transcript below.
Transcript
I’m going to continue explaining how you can detect errors in this episode. Make sure to listen to the previous episode also. And the best option is to subscribe to the podcast through your podcast application so you’ll be sure to get episodes automatically as soon as they’re published.
This is a simple episode but don’t be fooled. I actually learned something myself while preparing this. Something very basic about math. Now, I come across things that I don’t know all the time. But this one, wow, was like learning some new aspect about one plus one equals two.
I’ve said many times that you don’t need to know a lot about math in order to program and I’ll always try to simplify and reduce the amount of math that’s needed.
This episode will contain a lesson in logic and another brief math lesson. The actual subject of checksums will then use these techniques. What I’m going to explain about logic is easy but you might want to make sure to listen to the Q&A Friday episode from 2015-Dec-18 first about logic operators. And you should be able to follow along the math lesson with a basic ability to do long division.
Before we get into that, why are checksums used and what are they? A checksum is another way to detect errors. This could help you detect errors when reading, writing, or receiving and sending information. The previous episode explains parity and you can use parity along with checksums if you want. Neither of these will help you detect errors made on purpose where an attacker has tried to hide the evidence. They’re easy to get around and really only good for detecting errors caused by random events or noise.
Imagine you have a device to check for liquid on the floor. It’ll work great for accidental spills and will help keep you from slipping. But it won’t help you at all detect when an adult spills something. That’s because the other person just needs to wipe up the mess and you’ll never detect anything. These simple error detection techniques are like this. It’s real easy for somebody to change the information and update the parity or checksum. And they’re not foolproof for random changes either. Using a checksum will help you detect more errors than just parity though.
Using a checksum is not as complicated as using cryptography. I’ll explain cryptography in future episodes. Checksums have an advantage similar to parity; they’re easy and fast to calculate.
The word checksum usually refers to the result of the calculation. It’s an extra piece of information that gets added onto your data that does as the name suggests. It allows you to check the sum.
I’ll describe two different ways to create a checksum in this episode.
The first method is called a longitudinal parity check. Instead of counting the number of ones and adding another bit throughout the data to bring the total number of ones to either an even or an odd number, this method relies on an operation called exclusive OR. Sometimes, this is just called XOR. It’s really just binary addition that ignores the carry. But explaining it like that will probably confuse you.
◦ This is the logic lesson I mentioned. Let’s first review the logic OR operation. I’m going to explain this using the terms true and false. When working with binary data, true is the same thing as a one and false is the same thing as a zero.
◦ If you have two or more inputs where each input can be either true or false, then a logical OR operation on these inputs will result in a true output as long as any of the inputs is true. They might all be true inputs and you’ll get a true output. Or maybe just one of the inputs is true and you’ll get a true output. Or several of the inputs is true and you’ll still get a true output. If you have five inputs and two of them are true, then the output will be true. With a logical OR operation, the only time the output will be false is when all of the inputs is false.
◦ Now, an exclusive OR operation adds a slight twist to this. In order for the output of an XOR operation to be true, then there must be only a single input that’s true. In other words, there must be one and only one input exclusively that is true in order for the output to be true. If all of the inputs are false, then the output will also be false. If all the inputs are true, then the output will be false. If you have five inputs and two of them are true, then an XOR operation will be false. But if you have five inputs and let’s say that the fourth input is the only one that’s true, then this satisfies the exclusive requirement and the output will be true.
Going back to the longitudinal parity check, it’s not really parity like how I described parity in the previous episode. Remember there, I described the need to group a certain number of bits, usually eight, and add an extra parity bit. This means that the parity bits get sent along with every byte of data. A checksum is different. With a checksum, you keep track of an ongoing value that keeps changing as you process more and more data. Once you’re done processing all your data, the final value becomes the checksum and gets added to the data as an extra value either at the end or at the beginning.
This method exclusive ORs each word or maybe each double word with the next. A word is usually two bytes or 16 bits and that makes a double word four bytes or 32 bits. When you exclusive or one word with another word, what you’re doing is exclusive ORing each bit in one word with the same bit from the other word. If you write one word as a series of binary ones and zeros, then just write the other word right under the first so the ones and zeros align.
The second method is called the Fletcher checksum and this computes the modular sum of each word. What’s a modular sum? That’s the math lesson I promised.
◦ Let me start with an example. Let’s say that the current time is 1pm and I ask you what time it’ll be 24 hours from now. The day will change but the time will still be 1pm. You know that the same time comes around again every 24 hours. And if we ignore the am or pm, then the same time comes around again every 12 hours. It repeats itself. There’s a type of math operation known ad modulo arithmetic that’s based on repetition like this.
◦ All modulo arithmetic is concerned with is the remainder. In other words, going from 1pm to 3pm is important. It doesn’t matter how many days pass. It could be a 2 hour difference. Or a 26 hour difference. Or even a 50 hour difference. All of these will go from 1pm to 3pm.
◦ Working with modulo arithmetic is really just like throwing away the whole numbers of a division answer and only keeping the remainder. If I asked you what is 5 divided by 1, the answer is 5. But let’s not ignore the remainder. 5 divided by 1 is 5 with a remainder of 0. I could also ask you what is 5 modulo 1, or usually pronounced as just 5 mod 1. Remember that modulo arithmetic is only interested in the remainder. So 5 mod 1 is 0. Simple, right? Okay, what’s 5 mod 3? Well, 5 divided by 3 is 1 with a remainder of 2. So that means that 5 mod 3 is 2.
Back to the Fletcher checksum, it works by picking a value to use as your modulus. That’s the number that determines how often the cycle repeats. In the example 5 mod 3 equals 2, the number 3 is the modulus. Once you have this number, just perform the modular division on each word in your data and add those results together. Then modular divide this sum one last time. The result becomes your checksum.
Regardless of which method you use to create a checksum, you can verify the checksum to check for errors by performing the same procedure and comparing checksums. If they match, then you can be more confident that there are no errors. But if they’re different, then you know either the data or the checksum is wrong.
Now I started out telling you about something new that I learned. I’ve been programming for 25 years so my experience and knowledge has been based on what I’ve learned while programming. I’m not a math major. What I learned has nothing to do with checksums but about how modulo arithmetic works with negative numbers. Not the modulus, but the number that’s being divided. In other words, what’s -5 mod 3? My answer was -2. My thinking was that you treat this just like everything was positive and then make the answer negative. I even created a program in C++ that agreed with me. This is how I’ve always understood modulo arithmetic to work.
The only problem is that it’s not the way mathematicians define it. A person who studies math would say that -5 mod 3 is 1. That’s also what Google says the correct answer should be. What I learned from all this is that the remainder should never be a negative number.
I don’t think I’ve ever had a need to modulo divide negative numbers before and at least for C++, it looks like the language designers probably didn’t either.
It’s something to think about. The next time I need to perform modulo arithmetic in my applications, you can be sure that I’ll be thinking about how to handle negative numbers. And I won’t forget that if it took me 25 years to learn something this simple, how much more is yet to be learned.