Week 4: Try a Byte of AES!
Hello everybody! I hope you all had a lovely week. I focused most of my time on researching some of the known attacks against the “discrete logarithm problem.” In my week one blog post, I used a mixed paint example to describe the idea that RSA utilizes an easy process (multiplication) to encrypt data, but must undergo a hard process (factorization) to decrypt the data without a secret key. The mixing paint example, while effective in showing the premise of a trapdoor algorithm, is actually better used to describe a process called the “Diffie-Hellman Key Exchange.” I will explain the key differences between RSA and Diffie-Hellman in a future post.
The Diffie-Hellman Key Exchange is a process through which two parties can create a shared secret key that can then be used to encrypt future messages. This algorithm utilizes exponents and modular arithmetic, in which public numbers are raised to private numbers to create a new, secret number. Because this process uses exponentiation, an attacker who hopes to get their hands on either Alice’s or Bob’s private numbers would have to use a logarithm. The difficulty of solving this problem, or, in other words, trying to identify how many times a number was multiplied by itself to get a different number, is very, very hard in modulo p. Thus, this process is known as the discrete logarithm problem, and its difficulty to break is one of the reasons that the Diffie-Hellman Key Exchange is considered secure. You may also notice that the Diffie-Hellman process looks very similar to elliptic curve encryption, and this is because they are essentially the same. The only difference is that traditional Diffie-Hellman deals with exponentiating numbers rather than adding points on a curve. Essentially, elliptic curve encryption is a generalized form of the Diffie-Hellman key exchange.
So, it makes sense that Diffie-Hellman is fairly secure, but I want to briefly look at its security a little more closely. If the only way to solve the discrete logarithm problem was by brute force, meaning that one would have to repeatedly multiply the number “X” by itself, it would take about 2^80 steps and thousands upon thousands of years for a classical computer to break a string of 80 bits. This would mean that Diffie-Hellman is VERY secure. Unfortunately, there are processes such as the “baby-step-giant-step” algorithm and “Pollard’s rho method” that speed up the discrete logarithm process and require strings to have a bit length of at least 160. Even more unfortunately, the index-calculus attack can pose a serious threat to traditional Diffie-Hellman, requiring a bit length of at least 1024 to be considered secure. Ultimately, although Diffie-Hellman is considered secure for now, it isn’t very efficient as it requires very long bit strings. If better algorithms are found that speed up the discrete logarithm process further, or in the face of stable quantum computers, Diffie-Hellman would no longer be a secure process of encryption.
This week, I also learned about the Advanced Encryption Standard (AES). As I mentioned earlier, Diffie-Hellman is used between two parties to generate a shared secret key. This shared secret key can then be used to encrypt data through symmetric encryption algorithms, simply meaning that the encryption and decryption processes rely on this single key. AES is a symmetric crypto-system that is used in Wi-Fi, VPNs, password managers, and in securing a lot of government data transmissions. The process of AES encrypts 128 bit strings (or a length of 16 “bytes,” each “byte” defined as a group of 8 bits) through four steps: SubBytes, ShiftRows, MixColumns, and Key Addition. The first step, SubBytes, provides “confusion,” meaning that within the initial string of bytes, each one is systematically substituted with a new byte. For example, the byte “00101001” may be substituted for “01101011.” Note, however, that in this example, only two bits were actually flipped.
Next, ShiftRows provides diffusion by mixing up the order of the bytes and therefore increasing the chance that there are more flipped bits from the original sequence. For example, the entire byte “01100101” may take the place of the byte “11011101,” which may have taken the place of another byte “00010010.”
Then, MixColumn provides further diffusion by multiplying the bits by a matrix of numbers, which essentially causes more bits to flip through an amplification that allows one altered byte to affect an entire column of bytes.
Finally, Key Addition means that the secret key obtained from Diffie-Hellman is added to the string of bits mod 2. These steps are repeated several times; the exact number of which is determined by the bit length of the secret key.
AES was actually developed in a public competition as a response to the weakening security of its predecessor, the Data Encryption Standard (DES). I haven’t researched DES very thoroughly, but I hope to offer more insight into the differences between these two algorithms and the history behind AES in a future post.
As I promised in my last post, I also began researching historical methods of encryption this week. A recommendation from Mr. Smith was to look into the Enigma machine, and it was very fascinating to research! The Enigma machine was used in World War II by the Germans for encryption of their messages. It is based on substitution encryption, meaning that each letter is substituted for another one. A basic example of substitution encryption is the Caesar cipher, which shifts each letter of the alphabet a certain number of places. Rather than using a simple Caesar cipher, however, the Enigma machine has multiple rotors that allow for three different encoding sequences. This means that one letter can be encrypted into multiple other letters each time its key is pressed. Additionally, a plugboard is used to swap the places of ten letters with one another, independent of the rotors, to add an extra layer of security. If you’re interested in seeing pictures of an Enigma machine and what the rotors look like, check out these images from the CIA’s digital artifact museum. Although there are only three rotors in an Enigma machine, the Germans could choose rotors from a set of five, each with 26 starting positions for the letters of the alphabet. This means that there are 60 ways to order the five rotors and 17,576 choices for initially lining up the letters!
At first, the Enigma machine gave the Germans a huge advantage. However, this only lasted until codebreakers realized that a letter could never be encoded as itself. Codebreakers then began guessing words that would likely appear in the message, such as “Hitler,” and used a process of elimination to try and match up the word with an encoded part of the message, capitalizing on the fact that no single letter could ever be encoded to itself. Two men, Alan Turing and Gordon Welchman, later developed a machine called the British Bombe, which simulated the Enigma machine and could much more rapidly attempt to guess at different combinations of plugboard options and rotor combinations.
To close off this week’s post, I want to quickly touch on the Wikipedia questions I received last week. After talking with Dr. Ismert, I think the reliability of Wikipedia in the math field is heavily based on the culture of mathematicians. Because many textbooks and papers aren’t easily accessible without paid subscriptions, Wikipedia is a way for mathematicians to share their knowledge publicly. The culture around sharing knowledge makes it very common for incredibly smart mathematicians to actively contribute to Wikipedia and other free sites, while also checking for any false information. Of course, there also aren’t too many people who are actively trying to put false information into Wikipedia’s articles on obscure math theorems :).
Thank you for tuning in to another blog! Until next week.
Comments:
All viewpoints are welcome but profane, threatening, disrespectful, or harassing comments will not be tolerated and are subject to moderation up to, and including, full deletion.