One of the courses that I enjoyed most at Virginia Tech is a course I took as a second year student:
MATH 4175 (Cryptography)
Introduction to classical and modern symmetric-key cryptography; alphabetic ciphers, block ciphers and stream ciphers; background in modular arithmetic and probability; perfect secrecy; linear and differential cryptanalysis; Advanced Encryption Standard; hashing
In this class, one of the projects that we had to implement was the Advanced Encryption Standard (AES) (FIPS PUB 197). The requirements were fairly relaxed and the deliverables (in addition to the source code) were encryptions and decryptions in various modes of AES. Although we could choose the language of implementation, we were instructed not to use external libraries that did large amounts of the core work for us.
In the same semester that I was taking MATH 4175, I was also taking a computer organization
class that had some projects in the C programming language. I, personally, enjoy writing in
C and wanted to challenge myself to implement AES at the lowest level practical; so I decided
to use C. Although I had a great time writing that solution, I won't be making it public out of
an abundance of caution for reasons related to the Virginia Tech Honor Code.
In a course that I am currently enrolled in (CS 5560 - Fundamentals of Information Security),
we spent some time in class talking about AES. Furthermore, one of the homework assignments required us to
calculate the first couple of words of the expanded version of a given 128-bit key. This required the use
of some of the key expansion transformations like MixColumns and InvMixColumns.
You could do this work by hand, but it would take a good chunk of time. Thankfully, for this assignment we
were allowed to use code if that code was custom written. This meant I was allowed to use the code I wrote
in MATH 4175.
After submitting the homework, I wondered what languages other people used for the initial
MATH 4175 assignment. From what I heard in class, my best estimate is that Java
and Python made up at least 75% of the implementations. Then, I started to wonder what language
I could use to challenge myself even further. A functional language? Maybe a language like Nim
to teach myself something new? Then it hit me:
Scratch.
I have been teaching Scratch for quite a while, but would never consider it as a technology I would want to use to write serious “software”. It has quite a lot of hurdles in terms of what you can do, but you can work your way around most of them with the right tricks. To test out how feasible this would be, I decided to only implement AES Key Expansion for 128-bit keys in Scratch for now.
I approached the Scratch implementation the same way I did in C. First, be able to get the key as an input, then work on helper functions. After all of the helper functions are fully operational and tested, use them to implement the core logic for AES128 key expansion. So, this post is split up into those three chunks: Input, Helper Functions, and Key Expansion.
Before getting into the actual implementation, I think it's worth it to go over some of the quirks about Scratch that you might see appear throughout this project. Scratch, understandably, tries to make their platform as friendly as possible to inexperienced programmers. Because of this, it's missing some foundational components you'd normally see in text-based languages. Among the most notable of these missing features are functions (kind of). Scratch, instead, allows you to create “My Blocks”, which can take variables as parameters, but have no concept of a return value. Therefore, similar to what you would find in assembly, “My Blocks” can set a variable/register designated to store the return value which can be read from the calling code. This makes programming in Scratch for these types of projects feel like something out of a colorful children's book called “Drag and Drop Assembly”.
For my program, I decided to use a variable called "ax" to store the desired return values for "My Blocks".
For simple operations, this may just be a set variable block. For example, to emulate a function
hex2dec that converts a hexadecimal value to decimal, you could use
This uses the fact that if you attempt to add the string "0xA4" with a value of 0
in Scratch, it will return a value in decimal! Although useful, I don't actually use this in my program
since I store the key in either hexadecimal or binary throughout the lifetime of the program. If you were to
use this block, it would look something like this
The deeper I got into this project, the more I found myself following assembly practices. For example, I started to create my own general purpose registers for internal use in custom block. Furthermore, most of the helper custom blocks that I decided to create a almost entirely comprised of either variable manipulation blocks or calls to other custom blocks. Although on opposite ends of the technical spectrum, I found the translation between Scratch blocks and assembly instructions wasn't as far off as I initially expected.
Although, Scratch can't read from files, or be passed arguments via the command line, it can utilize the "ask" block to obtain input from the user. The response to this prompt is stored in the "answer" variable. After the user submits their key, I do some verification to ensure that there won't be any problems with key expansion.
The error_with block will display a given message and stop the program execution. Therefore, once this chunk of blocks has been run, we know that the answer variable is a valid 128-bit key given in hexadecimal format.
When I started programming AES in higher level languages, I started by implementing the helper functions.
For key expansion, those helper functions are RotWord and SubWord.
Additionally, Scratch doesn't provide the ability to perform an exclusive
or (XOR) operation on two numbers, so I decided to make a custom block to XOR two
words. Finally, it would be helpful to access the previous word of the current expanded key with
get_temp as well as the word four positions ago with get_four_words_ago for use in
the key expansion core.
RotWord
Takes a four-byte word and performs a cyclic permutation.
SubWord
Takes a four-byte input word and applies an S-box to each of the four bytes to produce an output word
SubByte
Takes a byte input and produces the substitution for that byte
0x00 => 0x63, 0x01 => 0x7C, 0x02 => 0x77, etc.)
XOR Words
Takes two four-byte words as inputs in hex and computes their exclusive or (XOR) as a hexadecimal string
XOR Nibble
Takes two 4-bit nibble values in hex as inputs (single hex characters) and computes the hex string created from XORing the two inputs
nibble_to_bin and bin_to_nibble blocks do exactly what you would expect
Get
Takes the current expanded key in hex as an input and returns the last word (4 bytes).temp
get_four_words_ago block looks exactly the same as the get_temp
block other than the fact that the 7 is replaced with a 31 (different offsets).
After putting together the helper blocks, I wrote some tests to make sure they were producing the behavior that I wanted. Once all the tests were being passing, the core of the key expansion algorithm could be created. Because of the helper blocks, the structure looks pretty similar to what you might see in a higher level language, with some minor changes.
I found that debugging was fairly easy, since Scratch allows you to separate blocks and run them individually by clicking on them. This, in a way, is similar to how you would use a traditional debugger in a text-based language. You can go line-by-line or block-by-block to see where bugs are originating. Furthermore, unit tests are easy to make in Scratch since you can create disconnected blocks that don't run as an effect of clicking the green flag. If you want to run the tests, you can just click on the top of a chunk of block and all blocks under it will be executed.
If I were to start this project from the beginning again, I think I would be more
intentional about the format of the data as it's being passed around by the many
helper blocks. When I first started this project, many of my helper functions were expecting and returning
values in different formats which required many intermediate conversions. Thankfully, I was able to reformat
the code so that all data is always in hexadecimal format when being transferred between helper functions.
This cleaned up the logic of the key_expansion helper function and increased the overall
comprehension of the project.
Refactoring is extremely easy because of the modular nature of Scratch blocks. You can easily cut out chunks of blocks and place them somewhere else. Scratch also allows you to duplicate block(s) very easily, which sped up the development time when sections of blocks are similar to each other. Furthermore, refactoring variable names or "My Block" names/parameters always works because of how Scratch manages these objects. Altogether, coding in Scratch's development environment isn't a terrible experience.
Although done in a block-base language, I don't think this code would be any easier to explain to a beginner than comparable source code in Python for example. In my opinion, this is mostly due to the added complexity for workarounds and seemingly cryptic variable names.
I found this to be an extremely gratifying experience. The constraints that Scratch creates forces you to be creative in how you solve complex problems. This project obviously has no practical uses, but did grow my understanding of Scratch and how you can bend it to your will, which will be useful for explaining some of these features to my students in the future. Furthermore, the patterns I used to implement key expansion gave me a refresher on assembly and the patters that I would use to solve the same problem in assembly.