Reference no: EM133105263

Assignment: Using assembly to hide data in a bitmap

On April 2, 1990, Dilbert was sent to the tiny country of Elbonia on a secret mission6: to infiltrate the formerly communist, newly capitalist country and find targets who can become Western engineers. Secretly, Dilbert was also charged with becoming a liaison to the resistance movement from within Elbonia's totalitarian neighbour, 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. Facebook, Twit- ter, YouTube have been banned. Searches on google are often filtered out or redirected to NorthElbonia-SearchAndTortureDept.

You are the new tech assistant of Dilbert. Your mission: using assembly, encrypt messages into the photos of Elbonian white noise that Dilbert provides for you. In detail:

1. Make sure you understand the message.

2. Compress the message using the Run-Length Encoding (RLE) technique.

3. Prepare the white noise image.

4. Use XOR to encrypt the message into the white noise image.

5. Save the results as image bitmaps, in BMP format.

6. Test that you can decrypt the message, using again the XOR encryption technique.
More details follow. This message will not self-destruct in 5 seconds.

Data: The Message
Complexity: Easy

To demonstrate that your assembly code works, encrypt and decrypt the message Reading Dilbert strips or encoding Elbonian messages are not good excuses for failing the TI1406 final exam., including the final dot (‘.'). Save the message as an assembly data chunk before you continue.

Each message, before encryption, must be preceded and followed by the pattern 8 x T, 4x I, 2 x 1, 2 x 4, 4 x 0.8 x 5, where <number> <character> means that character is repeated number times, e.g., 8 x T means T T T T T T T T. The added parts are called the "lead" and the "trail" of the message.

Table 2.1: XOR truth table.

Data Compression: Run-Length Encoding (RLE)
Complexity: Moderate

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 length 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 8T means that the sequence length is 8 and the item is T, for the fully decrypted text T T T T T T T T.

You have to devise your own algorithms for RLE-8-encoding and RLE-8-decoding the message described in the previous paragraph.

Data: Repeating White Noise Patterns

Complexity: Easy

Since Dilbert's photo camera has been confiscated, we cannot provide you with pictures of anything Elbonian. However, Elbonians are very proud of their national art, which is based on white noise rectangles, that is, rectangles filled with a seemingly random collection of white and black pixels. You are to implement a generator of Elbonian white noise.

Be warned, to show that in Elbonia even white noise is controlled, the Elbonian Ministry of Mud approves every year a single pattern as that year's white noise. The pattern can be seen in the numerous works of poorly printed art on the streets. Dilbert believes this year's pattern is:

W W W W W W W W B B B B B B B B W W W W B B B B W W B B B W W

(31 pixels long), where W means white and B means black.

Create a sequence by repeating the Elbonian white noise pattern, followed by a red pixel, 32 times. This will form a 32 × 32 image, where each pixel is either white, black, or red.

Data Encryption: XOR

Complexity: Moderate

One of the common logical operations is the exclusive OR (XOR, ⊕), equivalent to the Boolean logic concept of "TRUE if only one of the two operands, but not both, is TRUE". Table 2.1 summarises the truth table of XOR.

Two properties of XOR are of interest:
x ⊕ 0 = x (2.1a)
x ⊕ x = 0 (2.1b)

From Equations 2.1a and 2.1b (non-idempotency), it is trivial to observe that:

(x ⊕ y) ⊕ y = x ⊕ (y ⊕ y)

= x ⊕ 0
= x

Equation 2.2 means that we can use XOR to first encrypt (x ⊕ y) and then decrypt ((x ⊕ y) ⊕ y) a one-bit message x with the encryption/decryption key y. It turns out that these two one-bit operations can be extended to n-bit operations, that is, for an n-bit message M and an n-bit key

K:

(M ⊕ K) ⊕ K = M (2.3)

For example, if the message is TEST in ASCII (M = 01010100 01000101 01010011 01010100 in binary) and the key is TRY! in ASCII (K = 01010100 01010010 01011001 00100001), the encrypted text is:

M ⊕ K = 01010100 01000101 01010011 01010100
⊕ 01010100 01010010 01011001 00100001
= 00000000 00010111 00001010 01110101

The decrypted text is:

(M ⊕ K) ⊕ K = 00000000 00010111 00001010 01110101
⊕ 01010100 01010010 01011001 00100001
= 01010100 01000101 01010011 01010100
= M

If the size of the message is m bits and the size of the key is k << n bits, the key can be repeated.

Effectively, using the full k bits of the key K, first the first k bits of the message M are encrypted, then the next k bits, etc.

Last, a good example of implementing the XOR encryption technique in C is the "C Tutorial - XOR Encryption" by Shaden Smith, June 20097.

Data Representation: the BMP Format (Simplified)

Complexity: Difficult

Storing data as images requires complex data formats. One of the simplest is the bitmap (BMP) format, which you must use. 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 colours used in the image (look-up table, see also the paragraph on white noise). The BMP file format is versatile, that is, it can accommodate a large variety of colour encodings, image sizes, etc. It is beyond the purpose of this manual to provide a full description of the BMP format, which is provided elsewhere8.

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:

Question 1. 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 size is the sum between the file header size, the size of the bitmap info header, and the size of the pixel data. 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.

Question 2. Bitmap Header, encoded as 9: header size (integer, four bytes, must have a value of 40); width of image in pixels (integer, four bytes, set to 32-see 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 2835); vertical resolution of the image, in pixels per meter (four bytes, integer, set to 2835); colour palette information (four bytes, integer, set to 0); number of important colours (four bytes, integer, set to 0).

Question 3. 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 Nrows × Srow × 3, where Nrows is the number of rows in the image (32-see paragraph on white noise); Srow 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 3 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).

Last, but not least

You should go and have your code checked by a lab course assistant. You have now officially proved mastery in the basics of assembly programming. Not bad!