Differences

This shows you the differences between two versions of the page.

--- labs:sp20_codebreaker [2020/04/28 17:23]
nelson [Final Passoff]
+++ — (current)
@@ Line 1: / Line 1: @@
-====== Codebreaker ======
-<color blue>Below is a link to Prof Nelson's lab introduction video.  If you missed it at the start of lab you can watch it here.  Or, even if you were present at the start of lab you can go back and review it as you work through the lab to help answer questions along the way.   BUT, it is not substitute for also carefully reading the lab assignment itself.\\ \\
-  * [[https://expl.ai/UWMRSDW | Intro Video]]
-</color>
-===== Overview =====
-In this lab you will be given a secret message that has been encrypted with a secret key.  You will create a circuit that tries every possible key until you find out which key successfully decrypts the message.
-Your design will start searching for the key after the center button is pressed.  The current key being tried is displayed on the LEDs, and your stopwatch from a previous lab is used to time how long it takes for you to find the correct key.  Once you have discovered the secret message, you will display this secret message on the VGA monitor.
-{{youtube>IgUdRXjBiwE?rel=0&noborder&560x315}}
-The progression of the exercises is:
-  * <del>Exercise 1: Set up your project, and draw a message of your choosing on the screen.</del>
-  * Exercise 2 and 3: You will be given an encrypted message, and the decryption key.  You will decrypt the message, and display the decrypted message <del>on the screen</del> via simulation.
-  * Exercise 4: You will be given an encrypted message, but not the decryption key.  You will search through all keys to find the key that properly decrypts a given message, and then display the decoded message <del>on the screen</del> via simulation.
-===== Learning Outcomes =====
-  * Implement a state machine using behavioral SystemVerilog
-  * Build a system in SystemVerilog that contains several interacting modules.
-===== Preliminary =====
-==== ASCII Character Values ====
-In computer systems, we typically use an 8-bit integer value to represent different characters, including uppercase (A, B, C, ...) and lowercase (a, b, c, ...) alphabet characters, digits (0, 1, 2, ...), symbols ($, %, ^, ...) and special characters (space, tab, new line).  Online you can easily find an [[http://www.asciitable.com/|ASCII Table]] that lists the integer values we use for each of these characters.  Almost all computers and electronics you will encounter use these same standardized ASCII values.  When you consult this table, be mindful that the values are typically listed in both decimal and hexadecimal, so be sure you are looking at the correct column!
-  *<color red>What is the hexadecimal ASCII value for character ''D''?</color>
-  *<color red>What is the hexadecimal ASCII value for character ''d''?</color>
-  *<color red>What character is represented by the ASCII value ''0x09''?</color> (Enter it in LearningSuite as it appears in the linked ASCII table.)
-==== Encryption ====
-This lab is all about **encryption** and **decryption**, but it may be the first time you've learned about these things.  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 **cyphertext**.  Decryption is the reverse process.  It takes the cyphertext and the same original key, and produces the original plaintext.
-In this lab we will be using the [[https://en.wikipedia.org/wiki/RC4|RC4]] encryption algorithm.  It's an old encryption algorithm, and don't worry, you don't need to understand how it works.  What's important to know for our system is that we are going to use __messages that are 16 bytes long (128 bits), and a 24 bit key__.
-  * <color #ed1c24>How many different key values can our system have?</color>
-As an example, we may have a 16 byte message, "WE LOVE ECEN 220", which we can assign to ''logic'' in SystemVerilog like this:
-<code SystemVerilog>
-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'h32, 8'h32, 8'h30};
-// The above is split up to show the individual bytes, we could also store it like this:
-assign plaintext = 128'h5745204C4F5645204543454E20323230;
-// Or like this:
-assign plaintext = {"W", "E", " ", "L", "O", "V", "E", " ", "E", "C", "E", "N", " ", "2", "2", "0"};
-// Or like this:
-assign plaintext = {"WE LOVE ECEN 220"};
-// All of the above assign the plaintext to an identical value
-</code>
-If we encrypt this message using the following key:
-<code SystemVerilog>
-logic [23:0] key;
-assign key = 24'h010203;
-</code>
-The resulting cyphertext will be equal to ''128'h5c057e9fd5458ec36d7ef9cc4d23ea3e''.  If you look up these values in the ascii table you will see that the cyphertext 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 cyphertext 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).
-**In this lab you will be given the cyphertext, and then you need to try all of the keys until you find one that produces a readable message.  Then you will have hacked the system and figured out the key!**
-You might be worried that you will find a key that produces a readable message, but 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 we give you).
-==== Modules ====
-Once you've figured out the key and decrypted the secret message you will want to display it.  Unfortunately there's no easy way to display messages like this on the board, so you are given some modules that can be used to display text on the monitor using the VGA connection.
-You can download the following modules and add them to your Vivado project:
-  * The [[resources:rc4|decrypt_rc4 module]].  This module performs the decryption.  You will provide a 128-bit message, a 24-bit key, and a start signal.  It will takes some time to perform the decryption, and then it will raise its ''done'' output, and provide the decrypted message.
-  * The [[resources:vga_drawer|BitmapToVga module]].  This module draws pixels to the VGA monitor.  You won't have to interact with this module directly in this lab.
-    * <color #ed1c24>The BitmapToVga module has an internal bitmap image that it outputs it to the VGA monitor.  How many pixels wide is the bitmap?  How many pixels tall?</color>
-    * <color #ed1c24>In what corner of the screen is the origin (0,0)? </color>
-  * The [[resources:char_drawer|CharDrawer]] module.  You provide this module with a 128-bit ASCII message, a starting (x, y) coordinate, and a ''start'' signal.  It will output (x,y) pixel values that when connected to the ''BitmapToVga'' module, will draw the message on the screen.  You will be given a top-level that connects these two modules together, so you only need to worry about sending the correct inputs to the ''CharDrawer'' module.
-You should use your 7 segment controller from a previous lab for this.
-/* For example, suppose we randomly choose some cyphertext in the hopes of decrypting it into a valid message. Since each byte has 37 valid characters, out of a possible 256, the odds that a specific key value will produce a valid 16-byte message is (37/256)<sup>16</sup> = 3.63e-14.  If we try all possible values for the 24-bit key, the odds become 2<sup>24</sup>⋅(37/256)<sup>16</sup>, which is about 1 in 1.6 million.  As you see, even for our small message and key size, it is very unlikely that we can find a valid message by luck.  In the last exercise of the lab you will be given some cyphertext that //will// decrypt into a valid message, you just need to find the correct key.
-*/
-=====Exercises=====
-==== Exercise #1 - Draw a message on the screen ====
-The full system for this lab is shown below.  Almost everything you design will be contained in the ''Codebreaker'' module that you will implement shortly.  The top-level module, shown in the diagram below, is provided to you and you shouldn't need to modify it (except perhaps for your personal exploration).
-{{:labs:codebreaker:codebreaker_diagram.png?1200|}}
-=== Top-Level Module ===
-The top-level module is ''codebreaker_top''. Download it here: {{ :labs:codebreaker:codebreaker_top.sv |}}
-Look over the top-level module, and make sure you understand how it works.  The module contains:
-  * A ''clk_generator'' instance, that generates a 25MHz clock needed by the VGA display.  **NOTE: this is a complex circuit which is able to synthesize multiple other clocks from a single input clock.  As such, it REQUIRES at least 400ns simulation time before it will output valid clock signals to the rest of your circuit.  See note below.**
-  * A ''BitmapToVga'' instance, that controls the VGA outputs, and has inputs that allow you to modify the pixel colors of the bitmap that is displayed over VGA.
-  * A ''CharDrawer'' instance, that is connected to the ''BitmapToVga'', that is used to draw messages to the bitmap, and thus the VGA display.
-  * ''SevenSegmentControl'' and ''stopwatch'' instances, that are configured like the Stopwatch lab.
-  * The ''Codebreaker'' instance.
-**Complete each of the following steps**:
-  - [[tutorials:vivado_project_setup|Create a Vivado project]] (remember to run the commands to configure the error messages)
-  - Add the top-level module to your project.
-  - Create an appropriate constraints file for all of the top-level ports.
-  - Add all other necessary modules to your project.  You will need to expand the modules in the Design Sources list to make sure you have included all necessary modules.  For this lab, you only need to create the ''Codebreaker'' module (ports listed below).  All other modules have been given to you, or were created in previous labs.
-  - <del>In this first exercise, your Codebreaker module will be very simple:</del>
-    - <del>Drive the ''key_display'' and ''stopwatch_run'' outputs to 0.</del>
-    - <del>Drive the ''plaintext_to_draw'' output to a message of your choice to draw on the screen (the ''CharDrawer'' can only draw upper case letters, digits and spaces. </del>
-    - <del>Connect the ''draw_plaintext'' output to the ''start'' input.</del>
-^ Module Name = Codebreaker^^^^
-^ Port Name ^ Direction ^ Width ^ Description ^
-| clk | Input | 1 | 100 MHz Input Clock |
-| reset | Input | 1 | Active-high reset|
-| start | Input | 1 | Begin searching for the secret key |
-| key_display | Output | 16 | Display portion of current key value being tested |
-| stopwatch_run | Output | 1 | Active-high enable of stopwatch |
-| draw_plaintext | Output | 1 | Raise this signal to tell the ''CharDrawer'' module to start drawing your message. |
-| done_drawing_plaintext | Input | 1 | This input is high once the ''CharDrawer'' module is done drawing your message.|
-| plaintext_to_draw | Output | 128 | The ASCII message to send to the ''CharDrawer''|
-<del>**Pass-off:** Generate the bitstream and program the board.  You can use the **+** button on the monitors in the lab to switch them to the VGA input.  Verify that your message is displayed after you press ''btnc''.  You don't need to show it to the TAs.</del>
-----
-==== Exercise #2 - Decrypt and Display a Message  (SM design) ====
-The next step of this lab is to actually decrypt and display a message.  To do this, you will have to instance the ''decrypt_rc4'' module in your ''Codebreaker'' module.  Before you start modifying your SystemVerilog, you will design the state machine that interacts with the decryption module.
-This exercise is entirely done on paper.  Design and draw a finite state machine that:
-  * Waits for the start button
-  * Decrypts the cyphertext and obtains the plaintext.
-  * Displays the plaintext message on the VGA display.
-  * Stays in a terminating state until reset.
-Inputs to your state machine:
-  * ''Codebreaker'' input ''start''
-  * ''Codebreaker'' input ''done_drawing_plaintext''
-  * A new signal you create connected to the ''done'' output of the ''decrypt_rc4'' module.
-Outputs of your state machine:
-  * A new signal you create that you should connect to the ''enable'' input of the ''decrypt_rc4'' module.
-  * ''draw_plaintext'' output of ''Codebreaker''.
-Remember, the ''decrypt_rc4'' module takes some time to perform the decryption, so you will need to wait for the ''done'' output to be high before displaying the message on the display.
-Tips:
-  * You can implement this in 4 states.
-  * It is good to choose meaningful state names (not S1, S2, etc.) This will help you reason about and debug your state machine.
-**Pass-off**: <del>Show</del> Use Zoom to share your state machine with the TA and get feedback.
-----
-==== Exercise #3 - Decrypt and Display a Message  ====
-Implement your state machine in your ''Codebreaker'' module. Test your design with the following 128-bit cyphertext and 24-bit key.  You should get a readable message <del>on the display</del> in your simulation. You should be simulating codebreaker_top and using your own tcl file.
-<code SystemVerilog>
-assign key = 24'h79726a;
-assign cyphertext = 128'h93a931affae622e10a029bd3d4bd6ced;
-</code>
-Use simulation to debug your design when necessary. A **reset time of at least 400 ns is required** to allow the clk_generator module to begin functioning properly and get a clk signal to your Codebreaker module. Remember to use the signals of codebreaker_top and not Codebreaker in your tcl script ('CPU_RESETN' and not 'reset').
-<del>For this exercise you can continue to connect 0 to the ''key_display'' and ''stopwatch_run'' outputs.  Since your state machine is now assigning a value to ''draw_plaintext'', make sure you don't still have it connected to the ''start'' input.</del>
-**Pass-off:** <del>Show the TA the decoded message being displayed on the monitor.</del>  <color red> Include a screenshot of the simulation showing the decoded message in the lab report.  In order to make the decoded message be in ASCII instead of hex, change the radix of the plaintext_to_draw to be ASCII (right click it in the simulation window to get to radix menu). How take a screenshot will depend on your local computer (the one you are sitting at, NOT the computer that is actually running Vivado.  For example, searching for "Windows 10 screenshot" will bring up many articles on how to  make screenshots in Windows.  Similar mechanisms will apply to any type of computer you might be working on. Further, if you decide you need to concatenate multiple PDF files into one to attach, there are many online sites that will do it for you.  Further, there are many tools you can use on your own system to do it.  </color>
-----
-==== Exercise #4 - Brute-Force Key Search ====
-{{ :labs:codebreaker:codebreaker_flow.png?nolink&600 |}}
-The final object of the lab is to modify your state machine to complete the above flow diagram.  This consists of a system that tries every possible key value until the input cyphertext is correctly decrypted.
-**You know you have located the correct key when the produced plaintext only contains the characters A-Z, 0-9 or space.**
-Changes from the last exercise:
-  * You will need to add a state that checks the decrypted message, and decides whether it is readable.  If it is readable you can display the message and stop, otherwise, you should continue on to the next key.
-  * The **upper** 16 bits of the key should be output on the LEDs.  This will help you see that your search is progressing.
-  * Your state machine should have a new output that is connected to the ''stopwatch_run'' output of ''Codebreaker''.  Run the stopwatch after the user presses the button and stop once a valid plaintext message is found.
-Checking that each of the 16 bytes in the plaintext is valid may require writing a very long logic expression.  To save yourself some typing, we will give it to you:
-<code Verilog>
-    // Check that each byte of the plaintext is A-Z,0-9 or space.
-    logic plaintext_is_ascii;
-    assign plaintext_is_ascii = ((plaintext_to_draw[127:120] >= "A" && plaintext_to_draw[127:120] <= "Z") || (plaintext_to_draw[127:120] >= "0" && plaintext_to_draw[127:120] <= "9") || (plaintext_to_draw[127:120] == " ")) &&
-                                ((plaintext_to_draw[119:112] >= "A" && plaintext_to_draw[119:112] <= "Z") || (plaintext_to_draw[119:112] >= "0" && plaintext_to_draw[119:112] <= "9") || (plaintext_to_draw[119:112] == " ")) &&
-                                ((plaintext_to_draw[111:104] >= "A" && plaintext_to_draw[111:104] <= "Z") || (plaintext_to_draw[111:104] >= "0" && plaintext_to_draw[111:104] <= "9") || (plaintext_to_draw[111:104] == " ")) &&
-                                ((plaintext_to_draw[103:96] >= "A" && plaintext_to_draw[103:96] <= "Z") || (plaintext_to_draw[103:96] >= "0" && plaintext_to_draw[103:96] <= "9") || (plaintext_to_draw[103:96] == " ")) &&
-                                ((plaintext_to_draw[95:88] >= "A" && plaintext_to_draw[95:88] <= "Z") || (plaintext_to_draw[95:88] >= "0" && plaintext_to_draw[95:88] <= "9") || (plaintext_to_draw[95:88] == " ")) &&
-                                ((plaintext_to_draw[87:80] >= "A" && plaintext_to_draw[87:80] <= "Z") || (plaintext_to_draw[87:80] >= "0" && plaintext_to_draw[87:80] <= "9") || (plaintext_to_draw[87:80] == " ")) &&
-                                ((plaintext_to_draw[79:72] >= "A" && plaintext_to_draw[79:72] <= "Z") || (plaintext_to_draw[79:72] >= "0" && plaintext_to_draw[79:72] <= "9") || (plaintext_to_draw[79:72] == " ")) &&
-                                ((plaintext_to_draw[71:64] >= "A" && plaintext_to_draw[71:64] <= "Z") || (plaintext_to_draw[71:64] >= "0" && plaintext_to_draw[71:64] <= "9") || (plaintext_to_draw[71:64] == " ")) &&
-                                ((plaintext_to_draw[63:56] >= "A" && plaintext_to_draw[63:56] <= "Z") || (plaintext_to_draw[63:56] >= "0" && plaintext_to_draw[63:56] <= "9") || (plaintext_to_draw[63:56] == " ")) &&
-                                ((plaintext_to_draw[55:48] >= "A" && plaintext_to_draw[55:48] <= "Z") || (plaintext_to_draw[55:48] >= "0" && plaintext_to_draw[55:48] <= "9") || (plaintext_to_draw[55:48] == " ")) &&
-                                ((plaintext_to_draw[47:40] >= "A" && plaintext_to_draw[47:40] <= "Z") || (plaintext_to_draw[47:40] >= "0" && plaintext_to_draw[47:40] <= "9") || (plaintext_to_draw[47:40] == " ")) &&
-                                ((plaintext_to_draw[39:32] >= "A" && plaintext_to_draw[39:32] <= "Z") || (plaintext_to_draw[39:32] >= "0" && plaintext_to_draw[39:32] <= "9") || (plaintext_to_draw[39:32] == " ")) &&
-                                ((plaintext_to_draw[31:24] >= "A" && plaintext_to_draw[31:24] <= "Z") || (plaintext_to_draw[31:24] >= "0" && plaintext_to_draw[31:24] <= "9") || (plaintext_to_draw[31:24] == " ")) &&
-                                ((plaintext_to_draw[23:16] >= "A" && plaintext_to_draw[23:16] <= "Z") || (plaintext_to_draw[23:16] >= "0" && plaintext_to_draw[23:16] <= "9") || (plaintext_to_draw[23:16] == " ")) &&
-                                ((plaintext_to_draw[15:8] >= "A" && plaintext_to_draw[15:8] <= "Z") || (plaintext_to_draw[15:8] >= "0" && plaintext_to_draw[15:8] <= "9") || (plaintext_to_draw[15:8] == " ")) &&
-                                ((plaintext_to_draw[7:0] >= "A" && plaintext_to_draw[7:0] <= "Z") || (plaintext_to_draw[7:0] >= "0" && plaintext_to_draw[7:0] <= "9") || (plaintext_to_draw[7:0] == " "));
-</code>
-<del>Test</del> Simulate your brute-force design on the cyphertext below.  HINT: the key is 000005 - be sure your circuit finds that one.
-<code SystemVerilog>
-assign cyphertext = 128'hca7d05cd7e096d91acaf6fd347ef4994;
-</code>
-<color red> Include a screenshot of your simulation waveforms demonstrating that your simulation works and finds the correct key (be sure both the key and resulting decoded text are visible in the simulation). </color>
-**<del>Final</del> Pass-Off:** Choose two of the cyphertexts below, decode the message, and <del>display it on the VGA display</del> demonstrate that it works via simulation.  NOTE: the cyphertexts were encoded using a key fairly close to 0 to minimize simulation time.  Thus, if your search has not found the key prior to it reaching the value of 30, then you have a problem in your design and you can kill the simulation and start debugging your design.
-<color red>Be sure the original cyphertext, decoded text, and the resulting key are visible in your simulation waveforms. </color>
-<code Verilog>
-assign cyphertext = 128'hca91b1577f34443894de1001885d6aa5;
-assign cyphertext = 128'h57e967f1e86498a1eedc596a84f1fa26;
-assign cyphertext = 128'h5b99cbef5dffe0f58c3e81df23ba858f;
-assign cyphertext = 128'h77c58ceb8e5b342a583db6be53f8097c;
-assign cyphertext = 128'hbd6a2012369d963f18802a8a70ca7ec7;
-</code>
-/* Small keys for simulation:
-   "BRUTE FORCE  RC4" key = 24'h000009;
-   "EZ KEY IS 000003" key = 24'h000003;
-   "THAT TOOK FORVER" key = 24'h000013;
-   " I PICKED NUM 4 " key = 24'h000004;
-   "YOU CRACK ME UP " key = 24'h000007;
-  */
-==== Exercise #5 - Synthesize and Implement ====
-Synthesize and implement your design.
-<color red>Submit your synthesis logs to LearningSuite to demonstrate that you had no errors or critical warnings and, therefore, that your design *should work in all likelihood in hardware.</color>
-//Go to the tab "Reports" at the bottom of the screen. The report will likely be called "synth_#_synth_synthesis_report_#".
-Print to PDF as you would other SV modules and submit to learning suite.//
-<color red>For the synthesis and implementation logs, explain the source of any CRITICAL WARNING messages and why they are OK. </color>
-<color red>Submit your ''Codebreaker'' SystemVerilog module using the code submission on Learning Suite.</color> (Make sure your SystemVerilog conforms to the lab SystemVerilog coding standards).
-=====Final Passoff=====
-<color green>
-Attach a video of your experiment where you choose one of the cyphertexts above and demonstrate how your circuit finds the proper key and stops with the key value showing on the LEDs.  Be sure to state in the video what the cyphertext you chose was and then show in the video what the key found was.
-</color>
-<color green>
-Attach a video of your experiment where you choose the following cyphertext: and demonstrate how your circuit finds the proper key and stops with the key value showing on the LEDs.  Be sure to state in the video what the cyphertext you chose was and then show in the video what the key found was.  Also, state how long it took as measured by your timer.
-</color>
-For the final passoff part you have 2 choices.  The first choice is the default method.  But, if you don't have access to a VGA monitor you may do the second one.
-<color green>
-Choice #1: Connect a VGA cable to computer monitor and demonstrate that when your board finds a key, it also displays the decoded message correctly.  In doing this, if you find that nothing displays when a key has been found you may want to go back up to the exercise that has been <del>struck out</del> and do that part to ensure that your board can talk to the VGA monitor and actually draw stuff on it.  Create a video that shows this running on both of the experiments you did above where youshow the key that was found as well as the decrypted message that is displayed on the monitor.  Obviously, you can only do this if you have access to a computer monitor that accepts VGA (the VAST majority of monitors made in the past 30 years will, only very recent monitors have quit supporting VGA and only support HDMI).
-</color>
-<color green>
-Choice #2: Speed up your brute-force algorithm by using 2 or 4 simultaneous RC4 decryption instances, and have each of them try a different part of the key space. Stop as soon as one of the modules find the correct key and display that key on the LED's.  The best way to do this will be to make a controller (maybe a state machine?) that tells them all to start and waits for one of them to signal that it found the key.  The state machine then needs to stop them all (one will already be stopped) and then select the right output to display on the LED's to show what the key was that was found.  It should show that key until another test is run again.
-</color>

User Tools

Differences

Page Tools

BYU ECEn 220

Site Tools