A7: Bitmap
600 - 800 points
Last updated
600 - 800 points
Last updated
On April 3, 1990, Dilbert was sent to the tiny country of Elbonia on a : to infiltrate the 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:
For encoding, the msg argument gives the null-terminated UTF-8 message that should be encoded. For decoding, buf points to a buffer with enough space allocated to fit the original, 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).
You may safely assume that Dilbert will never send a message longer than 768 characters.
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.
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.
It is also very important to work closely with the debugger and ASan. This assignment is extremely prone to memory errors, leading to tests failing in the CodeGrade environment.
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., "AAAAAAAAAAAA") are split into multiple parts (0x09 A 0x03 A) in the encoding.
Extra hint: Will you ever need to use the byte 0x01 in RLE?
One of the common logical operations is the eXclusive OR (XOR, ). Two properties of XOR are of interest:
From the above equations, it is trivial to observe that:
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.
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.
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, 0x0 0x0 0x0 0x0); 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); color palette information (four bytes, integer, set to 0); number of important colors (four bytes, integer, set to 0).
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).
To pass the basic assignment, your programs should follow the following requirements:
The image must not show significant modifications.
This will be automatically tested by the CodeGrade environment. The threshold for the basic assignment is an absolute difference from the original image of at most 0x14 in any of the red, green, or blue bytes of any pixel
The decode program must exit gracefully, without any address sanitization errors when entering a wrong password (you should simply display the message resulting in xor-decrypting with the wrong key, hopefully different from the original message).
Note that the appearance of the image will also be judged by the TA handling your submission. We may reject submissions that show severe artifacts or differences from the original image, despite passing the tests.
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 conceptually developing an algorithm to hide the message inside the B G R bytes of the available pixels. Try pushing your algorithm to the limits (on paper) and calculate the maximum absolute difference from the original image in any of the B G R bytes of any pixel.
Implement 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.)
In short, there should be no visible artifacts in the image for any message length. On top of that, messages shorter than 382 characters should have an absolute difference from the original image of at most 0x01 in any of the red, green, or blue bytes of any pixel. This threshold is increased to 0x03 for messages longer than 382 characters.
The quality of your image will be automatically assessed by the CodeGrade environment. Even if your image looks the same as the original, we expect you to develop an algorithm that satisfies the dynamic pixel threshold requirement.
We also expect the images to look the same as the original to the human eye. This will also be judged by the TA handling your submission, reserving their right to reject a bonus submission if the images display any form of artifacts.
You can safely assume that the message transmitted is a regular UTF-8 message, containing only . Therefore, you may reserve bytes 0x01 to 0x09 specifically for Run-Length Encoding.
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 . (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.)
Implement all three .
The UTF-8 message must be hidden inside the image. You cannot store the message at the end of the image and call it a day. The totalitarian government is aware of these empty tricks and will catch you! Therefore, your file size must be exactly 3126 bytes, only including the data mentioned in the section.
Dilbert is and wants to make sure his message will never be detected. Your task is to ensure that the image does not differ from the original at all, with a dynamic pixel threshold based on the message length. Dilbert wants short messages to be even harder to detect than longer messages.
