Lab 13: Codebreaker

The purpose of this lab is to design a code breaker circuit that will decrypt a secret message by identifying the correct key. You will create a state machine to search for the correct key and display the decrypted message on the VGA display.

Learning Outcomes

• Implement a state machine using behavioral SystemVerilog
• Interact with previously designed modules

Preliminary

This lab involves encryption and decryption of messages using digital hardware. At the most basic level, an encryption process takes two inputs: a message (we call plaintext) and a secret key (we call the key). It produces an encrypted message, called the ciphertext. Decryption is the reverse process. It takes the ciphertext and the same original key, and produces the original plaintext.

In this lab we will be using the RC4 encryption algorithm. It’s an old encryption algorithm that is no longer considered secure, but it is useful for simple encryption tasks like this lab. For our system, we are going to use messages that are 16 bytes long (128 bits), and a 24 bit key.

How many different key values can our system have?

Assuming that valid messages are represented as ASCII characters A-Z, 0-9 and space, how many possible valid messages can be represented?

As an example, we may have a 16 byte message, “WE LOVE ECEN 320”, which we can assign to logic in SystemVerilog like this:

logic [127:0] plaintext;
assign plaintext = {8'h57, 8'h45, 8'h20, 8'h4C, 8'h4F, 8'h56, 8'h45, 8'h20, 8'h45, 8'h43, 8'h45, 8'h4E, 8'h20, 8'h33, 8'h32, 8'h30};
// The above is split up to show the individual bytes, we could also store it like this:
assign plaintext = 128'h5745204C4F5645204543454E20333230;
// Or like this:
assign plaintext = {"W", "E", " ", "L", "O", "V", "E", " ", "E", "C", "E", "N", " ", "3", "2", "0"};
// Or like this:
assign plaintext = {"WE LOVE ECEN 320"};
// All of the above assign the plaintext to an identical value

If we encrypt this message using the following key:

logic [23:0] key;
assign key = 24'h010203;

then the resulting ciphertext will be equal to 128'h5c057e9fd5458ec36d7ef9cc4d22ea3e. If you look up these values in the ASCII table, you will see that the ciphertext is not a readable message. For example, the first byte, 5c is for character \, and some of the bytes (such as ea) aren’t even valid ASCII character values. If we decrypt this ciphertext with the same key, we will get back the original message. If we use the wrong key, we will get another unreadable message.

If you’re interested, you can try this out on https://cryptii.com/pipes/rc4-encryption. Just keep in mind you need to reverse the bytes of the key. If you choose ‘key = 24’h010203’, then enter ‘03 02 01’ for the key on the website. The following image demonstrates how to use the website to encrypt and decrypt a message.

Answer the following questions using the website listed above.

Assuming the key is 24’h3fe21b, determine the encrypted value of the message ‘WE LOVE ECEN 320’. Paste the encrypted text directly from the web page (including spaces).

Using the same key shown above, decrypt the following message:0f 84 4e 5b 0b 4e 42 d3 5d 06 3c 6a 1a 5a 15 24. Make sure your response is 16 ASCII characters.

Assuming the key is 24’h3fe21X, where the last four bits of the key are unknown (represented by the ‘X’). Determine the key value that will decrypt the message ‘35 6b 6b a4 dd 97 71 20 f3 46 3c c9 09 4b 97 26’. Provide the key value as a 4-bit binary number. You will need to manually try mulitple values until you find a key that produces legible ASCII data.

Exercises

Exercise #1 - Decrypt Module

To help you with this lab, a RC4 decryption module has been provided for you (see decrypt_rc4.sv in the startercode). This module performs RC4 decryption/encryption on a 128-bit message and a 24-bit key. Because you will be instancing this module in your lab as part of the codebreaker assignment, it is important that you understand how the module operates.

Assuming one is using the provided module to perform RC4 decryption, the ciphertext is provided to the bytes_in input, and the key to the key input. The decryption process begins when the enable signal is raised, and when completed, the done output will be high for a single cycle (unlike the rx module you created, there is no handshake, so the parent module must always be watching the done signal). The resulting plaintext is available from the bytes_out output, which won’t change until you start a new encryption/decryption process (by lowering and raising the enable signal).

Review the source of the decrypt_rc4.sv file and answer the following questions:

How many bits is the bytes_in port when using default parameters?

How many bits are in the dual_port_ram memory used by the module?

How many write ports are there in the memory used by the module?

How many states are used in the state machine?

Create a tcl file named sim_decrypt_rc4.tcl to simulate this module performing decryption on two ciphertext/key pairs. Organize your tcl file as follows:

1. Start with the restart command
2. Create an oscillating clock signal with a period of 10ns
3. Set the reset to 1
4. Set default values for the signals and run for a few clock cycles
5. Run the decrypt function by setting enable to 1 with the following inputs:
   • key = 24'h010203
   • ciphertext = 128'h5745204C4F5645204543454E20333230
6. Run for 11 us (the decryption should be done by this time)
7. Set enable to 0 and run for 1 us
8. Run the decrypt function by setting enable to 1 with the following inputs:
   • key = 24'h3fe21b
   • ciphertext = 128'h0f844e5b0b4e42d35d063c6a1a5a1524
9. Run for 11 us (the decryption should be done by this time)
10. Set enable to 0 and run for 1 us

Note than when writing your .tcl scripts you can specify constants using the -radix flag as follows:

add_force bytes_in -radix hex 5745204C4F5645204543454E20333230

Make sure the results from your decryption/encryption are correct (see your responses to the preliminary to check your results). After simulating the decryption process successfully, take a screenshot of the full simulation and name it sim_decrypt_rc4.png.

Exercise #2 - Codebreaker Module

For this exercise you will create a module called codebreaker.sv that performs the primary code breaking function of this lab. This module will perform a brute-force search by performing the decrypt function multiple times with all possible keys to determine the key used to encrypt the message. Once a valid plain text message is received (i.e., all ASCII characters), the module will stop and provide the key needed to decrypt the message and the resulting plain text. You might be worried that you will find a key that produces a readable message, but it is not the correct key. Don’t worry, the odds of this are extremely unlikely (and we’ve double-checked that this won’t happen with the encrypted messages you will be tested with).

Begin this exercise by creating a module with the following ports:

Follow the steps below to build your codebreaker module.

decrypt_rc4

Begin this module by instancing the decrypt_rc4 module in your codebreaker module and connecting the clk, reset, key, and bytes_out ports. Add internal signals for the other ports. The instructions below will describe how these other ports are to be used.

ASCII Message Check

An important function that your module must perform is to determine whether the decrypted message is a valid ASCII message (i.e., the message in the bytes_out output of the decrypt_rc4 module). Once you determine that the decrypted message is a valid ASCII message, you can stop the searching for a key.

To determine if the decrypted message is a valid ASCII message, you will need to check each byte of the message to make sure it is a valid ASCII character. The following function can be added to your module to determine if a byte is a valid ASCII character (in this case we are only accepting capital letters, numbers, and spaces).

// Determines whether the input byte is an ASCII character
function logic isAscii(input logic [7:0] byte_in);
    isAscii = ((byte_in >= "A" && byte_in <= "Z") || 
            (byte_in >= "0" && byte_in <= "9") ||
            (byte_in == " "));
endfunction

Create a logic expression using this function that checks all the 16 bytes of the message simultaneously to determine if all bytes are ascii.

Ciphertext and Key Register

You will need a 128-bit register to store the original ciphertext provided and a 24-bit register to hold the key you are checking. The ciphertext register should be loaded with the value of the bytes_in input when a new code breaking operation is started (i.e., when the start signal is asserted and you are in an IDLE state). The ciphertext register will remain the same during the full duration of the code breaking operation.

The key register should be initialized to zero when the code breaking operation starts. The key register should be incremented by one each time a new decryption operation is started as described below in the state machine description. Make sure to connect the key register to the key output port (or directly use the key register as the output port), so that the parent module can see the current key being tested.

State Machine

You will need a state machine to control the operation of the codebreaker. This state machine is designed to continuously perform the decryption operation with different keys until a valid ASCII message is found. A flow diagram of the state machine is shown below:

In particular, include the following in your state machine should be designed as follows:

• When start is asserted, initialize the key register to 0 and the ciphertext register to the input ciphertext.
• Start a decrypt operation with the current key.
• When the decrypt is over, check to see if the message is all ASCII. If so, exit and assert the done output. Wait until the start signal goes low before accepting a new start signal.
• If the message is not ASCII, increment the key and try decrypting again.
• Create an internal error register that holds the error state of the codebreaker. Reset this register to zero every time a new search is started. If you have tried all possible keys (i.e., the key is 0xffffff, and you haven’t found a match), then exit operation, assert the done output and load a 1 to the error register.

A testbench named tb_codebreaker.sv has been created for you to test your codebreaker module. Create a Makefile rule named sim_tb_codebreaker that will run the simulation of your seven-segment controller with the testbench. This rule should generate a log file named sim_tb_codebreaker.log. Make sure that your testbench simulates without any errors.

What is the value of the key that the testbench found?

What is the value of the data_out of the decrypt module after attempting to decrypt with key 000002?

What is the time in nano seconds in which the simulation ends?

Exercise #3 - Top-Level

For this exercise you will create a top-level module name codebreaker_top.sv that instantiates the codebreaker module to perform code breaking of RC4 ciphertexts on the Basys3 board. Begin the exercise by adding the following top-level ports and parameters:

There are several components needed to implement the top-level design. Follow the guidelines listed below to build your top-level design.

UART Receiver

The UART receiver will be used to receive the ciphertext from the computer. This way you can decrypt multiple different messages by accepting new messages over the UART. Instance the rx module from your previous lab into your top-level module. Attach the ports to your rx module as follows:

• Assign the parameters for rx based on the top-level parameter values
• Attach the top-level clock and reset
• Create a two flip-flop synchronizer for the rx_in signal and attach it to the Sin port
• Create a signal ack and assign it to the Receive output of the rx module. Use this signal as the ReceiveAck input
• Create an internal signal for the Dout signal. More instructions on what to do with this signal will be described later
• You can leave the parityErr signal unconnected

Ciphertext Register

Create a 128-bit register called ciphertext to store the ciphertext you are trying to decode. This signal should be initialized to the value 128'ha13a3ab3071897088f3233a58d6238bb in the signal declaration. Also, the signal should be initialized to this value when the reset signal is asserted.

Please note: Just like last lab, although initializing signals at declaration is generally prohibited (see coding standard rule S12), this lab explicitly allows initializing ciphertext at signal declaration as described above.

The ciphertext register needs to be updated every time a byte is received from the UART receiver module. Design your register such that bits 0-7 are loaded with the Dout signal from the rx module when your ack signal is high. At the same time, shift all bytes in the register by one to make room for the new byte (i.e., set the new ciphertext value to the lower 120 bits of the previous ciphertext value concatenated with the new byte). Designed this way, you can update the 128-bit ciphertext register by sending 16 bytes over the receiver module.

Codebreaker Module

Instance the codebreaker module from the previous exercise in your top-level module. Attach the ports to your codebreaker module as follows:

• Attach the top-level clock and reset
• Attach the ciphertext register described above to the bytes_in input
• Create internal signals for the key, bytes_out, and done outputs (they will be discussed later)
• Attach the error signal to the top-level error output port (LED15)

Seven Segment Display & LEDs

The seven-segment display will be used to display the current key, the ciphertext, and the plain text. Instance the seven-segment display module and attach the outputs to the top-level ports. The value displayed on the seven-segment display will depend on the buttons pressed and switches 0-2 on the Basys3 board.

• Display the top 16 bits of the key (key[23:8]) when no buttons are pressed
• When btnl is pressed, display 16 bits of the ciphertext depending on the value of switches 0-2
  • When sw[2:0] is 000, display bits 15:0 of the ciphertext
  • When sw[2:0] is 001, display bits 31:16 of the ciphertext
  • When sw[2:0] is 010, display bits 47:32 of the ciphertext
  • When sw[2:0] is 011, display bits 63:48 of the ciphertext
  • When sw[2:0] is 100, display bits 79:64 of the ciphertext
  • When sw[2:0] is 101, display bits 95:80 of the ciphertext
  • When sw[2:0] is 110, display bits 111:96 of the ciphertext
  • When sw[2:0] is 111, display bits 127:112 of the ciphertext
• When btnr is pressed, display 16 bits of the plaintext depending on the value of switches 0-2. Use the same mapping of 16 bits to display based on the switches as was used for the ciphertext.

led[7:0] should display the lower 8 bits of the key.

VGA Display

The VGA display will be used to display the ciphertext, the plaintext, the current key and a banner message. You will be able to see your codebreaker circuit decrypting the message in real-time on the VGA display. To create the VGA display, instance the VGA timing module from lab 8 and the character generator module from the previous lab.

A module named write_vga.sv has been created for you to interface with the character generator module. This module will write the plaintext, ciphertext, and key data to the VGA character generator. Attach the ports of this module as follows:

• Attach the top-level clock and reset
• Attach the char_addr, char_data, and write_char outputs to the corresponding inputs on your character generator module
• Attach the bytes_out signal from the codebreaker module to the plaintext input
• Attach the ciphertext register signal to the ciphertext input
• Attach the key register to the key input
• The write_display input should be high when both the last_column and last_row from the timing module are high. This will cause the plaintext, ciphertext, and key to be written to the VGA display at the end of each frame.

Review the source code of the write_vga.sv module and answer the following questions:

What column,row coordinates is the first character of the cipher text displayed on? (see the parameters in the write_vga.sv file)

What column,row coordinates is the first character of the plain text displayed on? (see the parameters in the write_vga.sv file)

What is the purpose of the ‘nibble_to_char’ function in the write_vga.sv file?

Using your character generator module from the previous lab, you can set the initial background text of the VGA display using the FILENAME parameter. The file named background_template.txt has been provided for you as a template for your default background for this lab. Copy this file and modify it to include your NetID and name the file background.txt. Create a Makefile rule named background.mem that will generate a memory file named background.mem from your background file using the python script from the previous lab.

After adding the three modules and hooking them up properly, create the logic for the VGA color signals. When the pixel_out is high, set the color to the FOREGROUND_COLOR parameter and the BACKGROUND_COLOR otherwise. You will also need to pipeline the synchronization signals as you did in last lab.

After completing your top-level module, simulation your top-level module with a tcl file named sim_codebreaker_top.tcl to simulate the top-level module. Follow these guidelines when creating your tcl file and simulating the top-level:

• When running the xelab command, specify the following flags to specify the top-level parameters:
  • --generic_top "WAIT_TIME_US=50" This will reduce the wait time for the debouncer for easier simulation.
  • --generic_top "FILENAME=background.mem" This will specify the background file to use for the VGA display so you can see values being displayed in your simulation.
• Generate a free running clock
• Set default values for all top-level inputs (make sure rx_in is 1)
• Issue a reset by asserting btnd
• Set btnc high for at least 50 us to start the codebreaker
• Simulate the receiving of a character over the rx module (consider copying tcl code from your lab 11 tcl file)
• Simulate for at least one full frame (16.7 ms) so you can see the write_vga module write to the character generator

After creating your tcl file, simulate your top-level module and take the following screenshots:

• A screenshot of your ciphertext register being updated after the rx module receives a byte. This screenshot should include the rx_in signal and the ciphertext register so that you can clearly see the ciphertext register update. Name this screenshot cipher_update.png
• A screenshot of the write_vga module performing writes to the character generator at the end of the frame. This screenshot should include the char_addr, char_data, and write_char signals so you can see the data being written to the character memory. Name this screenshot write_vga.png

Exercise #4 - Synthesis and Implementation

Once you are satisfied with your top-level circuit’s behavior, create a .xdc file that contains pin location definitions for each of your I/O ports. Create a Makefile rule named synth that runs the synthesis script and generates a log named synthesis.log and a ‘.dcp’ file named codebreaker_top_synth.dcp. Make sure that your synthesis command in your script specifies the background memory file: -generic {FILENAME=background.mem}

After synthesizing your design, carefully review the synthesis log for Warnings. Note that you will likely see warnings about the decrypt_rc4 module not being fully covered in a case statement “Synth 8-155”. This is ok for always_ff blocks and can be safely ignored.

How many FDCE/FDRE/FDSE cells are used by the design?

How many total LUT resources are used by the design? (add up all the LUT* resources)

How many total Block RAMs are used by the design? (RAMB18E1 or RAMB36E1)?

How many total IBUF and OBUF resources do you have in the design?

After successfully synthesizing your design, begin the implementation process by creating a Makefile rule named implement that runs an implementation tcl script. This rule should generate a log named implement.log, a ‘.dcp’ file named codebreaker_top.dcp, a ‘.bit’ file named codebreaker_top.bit, a utilization report named utilization.rpt, and a timing report named timing.rpt.

Review the ‘utilization.rpt’ file to answer the following questions.

How many ‘Slice LUTs’ are used by your design?

How many ‘Slice Registers’ are used by your design?

Review the ‘timing.rpt’ file to answer the following questions.

What is the Worst Negative Slack or ‘WNS’ of your design?

How many TNS total Endpoints are there in your design?

Open your implemented design in Vivado (codebreaker_top.dcp) and view the design in the hardware implementation view. Zoom in to the bottom left corner of the device (region X0Y0). Turn off the ‘Routing Resources’ icon and take a screenshot of this region showing the resources allocated for your design. Name this screenshot codebreaker_top.png and include it in your repository.

Exercise #5 - Download and Test

Download your bitfile and test your codebreaker on the Basys3 board by pressing ‘btnc’. Make sure that the LED/seven segment display is displaying the key being tested and that the VGA is showing the correct output.

A python script send_cipher.py has been created to send a variety of ciphertext messages to your Basys3 board. The python script includes five encrypted messages and one incomplete message that you can use to test your codebreaker. Run this script and select a ciphertext message (1-6) to send to your Basys3 board. Note that ciphertext message 1 is the same as the default ciphertext loaded into the ciphertext register.

python3 send_cipher.py --port /dev/ttyUSB1

For each message, determine the 16-byte plaintext message and the corresponding key.

What is the plain text and key for message #1?

What is the plain text and key for message #2?

What is the plain text and key for message #3?

What is the plain text and key for message #4?

What is the plain text and key for message #5

Message 6 is an invalid message that does not have an ASCII plaintext. Load this message and make sure you get the error LED when the search completes.

The TAs will use the following procedure to test your design:

• Verify that the default cipher text is loaded into the ciphertext register by pressing btnl and changing sw[2:0] to look at all the bytes
• Press btnc to start the codebreaker process
  • Make sure that the LED/seven segment display is displaying the key being tested
  • Wait until the codebreaking process is complete. Verify that the key is correct.
  • Verify that the plaintext is correct by pressing btnr and changing sw[2:0] to look at all the bytes
• View VGA display
  • Make sure display shows ciphertext, plaintext, and key during operation
  • Make sure display has student netid
• rx receiver
  • Send a message to the Basys3 board using the python script
  • Verify that the message is received correctly and the ciphertext register is updated

Final Pass-Off

• Required Files
  • codebreaker.sv
  • codebreaker_top.sv
  • sim_decrypt_rc4.tcl
  • sim_decrypt_rc4.png
  • background.txt
  • sim_codebreaker_top.tcl
  • cipher_update.png
  • write_vga.png
• Required Makefile ‘rules’
  • sim_tb_codebreaker: generates sim_tb_codebreaker.log
  • background.mem: requires background.txt; generates background.mem
  • synth: requires codebreaker.sv, codebreaker_top.sv; generates synthesis.log, codebreaker_top_synth.dcp
  • implement: requires codebreaker_top_synth.dcp; generates implement.log, codebreaker_top.dcp, codebreaker_top.bit, utilization.rpt, and timing.rpt

Answer the final two questions in your laboratory report:

How many hours did you work on the lab?

Provide any suggestions for improving this lab in the future