A7: Bitmap
500 - 750 points
Last updated
500 - 750 points
Last updated
On April 3, 1990, Dilbert was sent to the tiny country of Elbonia on a secret mission: to infiltrate the formerly communist, newly capitalist country and find targets who could become Western engineers. Secretly, Dilbert was also charged with becoming a liaison to the resistance movement from within Elbonia’s totalitarian neighbor, North Elbonia. It has been over three decades, and the mission is still on... with a twist. The governments of Elbonia and North Elbonia have joined forces and together tightened their grip on information. Instagram, X, and TikTok have all been banned. Searches on duckduckgo.com are often filtered out or redirected to NorthElbonia-SearchAndTortureDept.com.
You are the new tech assistant of Dilbert. Your mission is to build a tool for transmitting hidden and encrypted messages. All communications, including images, are controlled. However, images of national art are allowed to be sent.
Elbonian art is based on white noise rectangles, that is rectangles filled with a seemingly random collection of white and black pixels. Unsurprisingly, even the white noise is controlled in Elbonia, the Elbonian Ministry of Mud approves a single pattern every year as that year’s white noise. This year, the pattern seems to be:
where W stands for a white pixel, B stands for a black pixel, and R stand for a red pixel (used as a delimiter at the end. The white noise images are then made up by repeating this pattern for a total of 32 times vertically. An example of the final image can be seen below.
Using Assembly, build a tool to encrypt messages into (as well as decrypt messages from) this year's Elbonian white noise pattern in the form of Bitmap image files.
To ensure the absolute highest level of security, message processing and encryption encompasses multiple steps:
Compress the message using Run-Length Encoding (RLE).
Encrypt the compressed message using XOR encryption.
Create a BMP file with an image of this year's white noise pattern and hide the message in it.
Each of the steps is further described below.
Implement (in the a7-bmp-encode.S and a7-bmp-decode.S files respectively) subroutines with the following signatures:
The return values are simple status codes (where 0 indicates a successful execution). For encoding, the msg argument gives the message that should be encoded (with a maximum length of 450 characters). For decoding, buf points to a buffer with at least 451 bytes of space, to fit the decoded message. key is the key to use for XOR encryption and decryption, and file is a file pointer to a file stream opened for writing (bmp_encode) or reading (bmp_decode).
For encoding, the main program should take the path for the output file as its first command line argument and the message to be encoded as the second. So to encode "Hello World" into a file named image.bmp, the invocation would look as follows:
The main program for decoding is similar, however, without the message argument, so:
Internally, these programs should open the given file (for writing or reading respectively) and then call your bmp_encode or bmp_decode subroutine for further processing.
Make sure that your program appropriately closes the file after the encoding/decoding has finished to avoid any issues.
If you have functions that you want to use for both encoding and decoding, you can place them in the a7-bmp-shared.S file, which will be compiled with both programs. Make sure to add the required .global declarations as indicated by the example in the file.
If you haven't done so before, this assignment is really the point at which is advisable to structure your code into multiple functions offering abstractions for the different parts needed. For example, you could should create subroutines for RLE-encoding and decoding respectively.
Run-Length Encoding (RLE) is one of the simplest data encoding techniques. RLE is based on the notion of runs, which are sequences of specified lengths of the same item. For this assignment, you will use RLE-8, which encodes, in turn, the size of the sequence and each item on 8 bits each. For example, the RLE-8-encoded sequence of two bytes "5X" means that the sequence length is 5 and the item is 'X', for the fully decrypted text "XXXXX".
Runs longer than 9 characters (e.g., "AAAAAAAAAA") are split into multiple parts ("9A1A") in the encoding.
It may help to develop the RLE-encoding and decoding subroutines in close coordination. You may test whether they can successfully compress and decompress a message before continuing with the next step.
From the above equations, it is trivial to observe that:
Storing data as images requires complex data formats. One of the simplest is the bitmap (BMP) format, which you will use for this assignment. BMP files encode raster images, that is, images whose unit of information is a pixel; raster images can be directly displayed on computer screens, as their pixel information can be mapped one-to-one to the pixels displayed on the screen.
The BMP file format consists of a header, followed by a meta-description of the encoding used for pixel data, followed sometimes by more details about the colors used in the image (look-up table). The BMP file format is versatile, that is, it can accommodate a large variety of color encodings, image sizes, etc. It is beyond the purpose of this Manual to provide a full description of the BMP format, which is provided elsewhere. (Note: Although Wikipedia is not a universally trustworthy source of information, many of its articles on technical aspects, such as the “BMP file format” have been checked by tens to hundreds of domain experts.)
Luckily for you, of the many flavors of encodings, Elbonian authorities only accept one type. Thus, you must use the following BMP format for this assignment:
File Header, encoded as signature (two bytes, BM in ASCII); file size (integer, four bytes); reserved field (four bytes, 00 00 00 00 in hexadecimal encoding); offset of pixel data inside the image (integer, four bytes).
The file header size is 14 (two bytes for signature and four bytes each for file size, reserved field, and offset of pixel data). The file size is the sum of 14 (the file header size), 40 (the size of the bitmap header), and the size of the pixel data.
Bitmap Header, encoded as: header size (integer, four bytes, must have a value of 40); width of image in pixels (integer, four bytes, set to 32–see paragraph on white noise); height of image in pixels (integer, four bytes, set to 32–see paragraph on white noise); reserved field (two bytes, integer, must be 1); the number of bits per pixel (two bytes, integer, set here to 24); the compression method (four bytes, integer, set here to 0–no compression); size of pixel data (four bytes, integer); horizontal resolution of the image, in pixels per meter (four bytes, integer, set to 2,835); vertical resolution of the image, in pixels per meter (four bytes, integer, set to 2,835); colour palette information (four bytes, integer, set to 0); number of important colours (four bytes, integer, set to 0).
If all the requirements of the assignment are fulfilled, 500 points are awarded. One of the requirements is hiding messages in the white noise image. If the resulting image clearly shows modifications, no points are awarded. It is okay for some modifications to be slightly visible.
Note that the appearance of the image will be judged by the TA handling your submission and is not automatically tested on CodeGrade.
Outstanding solutions that do not show any visible modifications to the image are rewarded with an additional 250 points.
There are (as always, but especially for this assignment) many different approaches. Below are some example steps that might help but can also safely be ignored.
Start by implementing the individual parts of message processing. Test the individual parts of compression/decompression or encryption/decryption.
Try to create an empty/black BMP file and see if you can open the file with a regular image viewer. If viewing the file fails, there is likely something wrong in the header or body of your image file. It may help to use a hex viewer to look at the file contents to find the issue.
Combine all the parts! (... and see if you maybe should continue your studies at the Secret Service of your choice.)
Note that the initial release of the framework had two small errors related to this assignment. The errors have since been fixed, however, if you are on an earlier version of the framework you will need to fix them manually:
In the a7-bmp-decode.S file, change line 20 from:
to:
In the .vscode/launch.json file, change line 51 from:
to:
One of the common logical operations is the eXclusive OR (XOR, ). Two properties of XOR are of interest:
This means that we can use XOR to first encrypt () and then decrypt () a one-bit message with the key . It turns out that these two one-bit operations can be extended to -bit operations, that is, for an -bit message and an -bit key K:
If the size of the message is bits and the size of the key is bits, the key can be repeated until the whole message is encrypted.
Pixel Data, encoded as B G R triplets for each pixel, where B, G, and R are intensities of the blue, green, and red channels, respectively, with values stored as one-byte unsigned integers (0–255). It is important that the number of bytes per row must be a multiple of 4; use 0 to 3 bytes of padding, that is, having a value of zero (0) to achieve this for each row of pixels. The total size of the pixel data is , where is the number of rows in the image (32, see paragraph on white noise); is the size of the row, equal to the smallest multiple of 4 that is larger than the number of pixels per row (here, 32–see paragraph on white noise); and the constant is the number of bytes per pixel (24 bits per pixel, as specified in the field “number of bits per pixel”, see the Bitmap header description).
