文件列表:

figures (0, 2018-05-22)
figures\arc4-module.svg (10623, 2018-05-22)
figures\hex-digits.svg (30762, 2018-05-22)
figures\key-endianness.svg (7754, 2018-05-22)
figures\mem-editor.png (62360, 2018-05-22)
figures\rdy-en-arg.svg (35085, 2018-05-22)
figures\rdy-en-singleclock.svg (31897, 2018-05-22)
figures\rdy-en.svg (31897, 2018-05-22)
figures\slithy-toves.svg (4070, 2018-05-22)
settings (0, 2018-05-22)
settings\DE0_CV.qsf (27508, 2018-05-22)
settings\DE1_SoC.qsf (61015, 2018-05-22)
task1 (0, 2018-05-22)
task1\DE0_CV_golden_top.v (4628, 2018-05-22)
task1\c5_pin_model_dump.txt (2789, 2018-05-22)
task1\db (0, 2018-05-22)
task1\db\.cmp.kpt (564, 2018-05-22)
task1\db\altsyncram_4fg2.tdf (15793, 2018-05-22)
task1\db\altsyncram_pvp1.tdf (3257, 2018-05-22)
task1\db\ip (0, 2018-05-22)
task1\db\ip\sld590eee0f (0, 2018-05-22)
task1\db\ip\sld590eee0f\alt_sld_fab.qip (14594, 2018-05-22)
task1\db\ip\sld590eee0f\alt_sld_fab.sopcinfo (59567, 2018-05-22)
task1\db\ip\sld590eee0f\alt_sld_fab.v (2416, 2018-05-22)
task1\db\ip\sld590eee0f\alt_sld_fab__report.html (18236, 2018-05-22)
task1\db\ip\sld590eee0f\alt_sld_fab__report.xml (28822, 2018-05-22)
task1\db\ip\sld590eee0f\alt_sld_fab_wrapper_hw.tcl (3248, 2018-05-22)
task1\db\ip\sld590eee0f\submodules (0, 2018-05-22)
task1\db\ip\sld590eee0f\submodules\alt_sld_fab_alt_sld_fab.v (21200, 2018-05-22)
task1\db\ip\sld590eee0f\submodules\alt_sld_fab_alt_sld_fab_ident.sv (3229, 2018-05-22)
task1\db\ip\sld590eee0f\submodules\alt_sld_fab_alt_sld_fab_presplit.sv (576, 2018-05-22)
task1\db\ip\sld590eee0f\submodules\alt_sld_fab_alt_sld_fab_sldfabric.vhd (13672, 2018-05-22)
task1\db\ip\sld590eee0f\submodules\alt_sld_fab_alt_sld_fab_splitter.sv (2176, 2018-05-22)
task1\db\lab4_task1.(0).cnf.cdb (3270, 2018-05-22)
task1\db\lab4_task1.(0).cnf.hdb (1801, 2018-05-22)
task1\db\lab4_task1.(1).cnf.cdb (2112, 2018-05-22)
task1\db\lab4_task1.(1).cnf.hdb (1085, 2018-05-22)
... ...

# Lab 4: Memories from Room 40 ## Contents * [Background](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#background) * [ARC4 Decryption](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#arc4-decryption) * [The ready\-enable microprotocol](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#the-ready-enable-microprotocol) * [Length\-prefixed strings](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#length-prefixed-strings) * [Designing the Decryption Circuit](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#designing-the-decryption-circuit) * [Task 1: Embedded memories and ARC4 state initialization](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#task-1-embedded-memories-and-arc4-state-initialization) * [Creating a RAM block using the Wizard](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#creating-a-ram-block-using-the-wizard) * [Implementing the S\-array initialization step](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#implementing-the-s-array-initialization-step) * [Examining memory contents inside the FPGA](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#examining-memory-contents-inside-the-fpga) * [Simulating Altera memories in ModelSim](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#simulating-altera-memories-in-modelsim) * [Initializing memories](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#initializing-memories) * [Task 2: The Key\-Scheduling Algorithm](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#task-2-the-key-scheduling-algorithm) * [Task 3: The Pseudo\-Random Generation Algorithm](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#task-3-the-pseudo-random-generation-algorithm) * [Task 4: Cracking ARC4](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#task-4-cracking-arc4) * [Task 5: Cracking in parallel](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#task-5-cracking-in-parallel) * [Deliverables](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#deliverables) * [Extra ciphertexts](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#extra-ciphertexts) ## Background In this lab, you will get experience creating a design that contains several on-chip memories, and uses a more efficient ready-enable interface to connect modules that have variable latencies. The circuit you will create is an ARC4 decryption circuit. [ARC4](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/https://en.wikipedia.org/wiki/RC4) is a popular symmetric stream cipher, and was widely used in encrypting web traffic, wireless data, and so on; it has since been broken. Still, the structure of ARC4 is similar to modern symmetric encryption methods, and provides a good vehicle for studying digital circuits that make extensive use of on-chip memory. In the rest of the lab, you will first design an ARC4 decryption circuit. The secret key will initially be obtained from a bank of switches on your DE1-SoC board, and the encrypted message will be given to you as a ROM initialization file. Next, you will extend this to build an ARC4 cracking circuit; the circuit will implement a “brute-force” attack by cycling through the entire key space and stopping when a successful decryption is performed. Finally, you will create a cracking circuit with multiple decryption units to speed things up. The description of this lab is fairly long, but this is mostly because it includes lots of explanations about ARC4, how to generate and examine memories, and so on. Do not be discouraged by this — the amount of actual code you have to write is not excessive. Finally, some debugging advice. More than prior labs, this one would benefit from having a “known good” high-level implementation that you can compare with step by step. You don't have to do this, of course, and you will not be marked on it, but it will make your life much easier. ### ARC4 Decryption This section describes the ARC4 cipher. A stream cipher like ARC4 uses the provided encryption key to generate a pseudo-random byte stream that is xor'd with the plaintext to obtain the ciphertext. Because xor is symmetric, encryption and decryption are exactly the same. The basic ARC4 algorithm uses the following parameters: | Parameter | Type | Semantics | | --- | --- | --- | | `key[]` | input | array of bytes that represent the secret key (24 bits in our implementation) | | `ciphertext[]` | input | array of bytes that represent the encrypted message | | `plaintext[]` | output | array of bytes that represent the decrypted result (same length as ciphertext) | and proceeds as shown in this pseudocode: -- key-scheduling algorithm: initialize the s array for i = 0 to 255: s[i] = i j = 0 for i = 0 to 255: j = (j + s[i] + key[i mod keylength]) mod 256 -- for us, keylength is 3 swap values of s[i] and s[j] -- pseudo-random generation algorithm: generate byte stream (“pad”) to be xor'd with the ciphertext i = 0, j = 0 for k = 0 to message_length-1: i = (i+1) mod 256 j = (j+s[i]) mod 256 swap values of s[i] and s[j] pad[k] = s[(s[i]+s[j]) mod 256] -- ciphertext xor pad --> plaintext for k = 0 to message_length-1: plaintext[k] = pad[k] xor ciphertext[k] -- xor each byte The length of the secret key can vary — in this lab, we will use a smaller key of 24 bits (3 bytes) to ensure that you can “crack” the encryption in a reasonable amount of time. Note that the key is stored [big-endian](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/https://en.wikipedia.org/wiki/Endianness). The following diagram shows the values of key[0], key[1], and key[2] for the 24-bit secret key of 'b000000110101111100111100 = 'h035F3C.

### The ready-enable microprotocol In some of the previous labs, you used a simple start/done microprotocol to let your circuit take a variable number of cycles. In this lab, we will be using a slightly more sophisticated ready/enable microprotocol to achieve the same goal. The handshake has two sides: the “caller” and the “callee.” Whenever the callee is ready to accept a request, it asserts its `rdy` signal. If `rdy` is asserted, the caller may assert `en` to make a “request” to the callee. The following timing diagram illustrates this:

It is illegal for the caller to assert `en` if `rdy` is deasserted; if this happens, the behaviour of the callee is undefined. Whenever `rdy` is asserted, it means that the callee is able to accept a request _in the same cycle_. This implies that a module that needs multiple cycles to process a request and cannot buffer more incoming requests **must** ensure `rdy` is deasserted in the cycle following the `en` call. Similarly, each cycle during which the `en` signal is asserted indicates a distinct request, so the caller must ensure `en` is deasserted in the following cycle if it only wishes to make a single request. The following timing diagram shows an example of this behaviour:

In this lab, you do not need to make requests in the same cycle `rdy` goes high, although it might be helpful for the bonus competition. You **do**, however, need to make sure you deassert `rdy` in the cycle following `en`. Finally, some requests come with arguments. For example, Task 3 requires you to write a decrypt module which follows the ready/enable protocol and takes the secret key as an argument. In this case, the argument port must be valid **at the same time** as the corresponding `en` signal, as in this diagram:

Unlike our old star/done scheme, this microprotocol allows the callee to accept multiple requests and buffer them. You do not need to implement that in this lab, although it might be helpful for the optional competition task. Note: Be careful about combinational loops. For example, since `en` can derive from `rdy` through combinational logic, `rdy` cannot also derive from `en` combinationally; otherwise, the two signals will form a wire loop. ### Length-prefixed strings In this lab, messages (both plaintext and encrypted) are length-prefixed strings of any length from 0 to 255 characters. Strings are encoded as an array of bytes, where the first byte indicates the length of the string (# of characters), and the remaining bytes are the ASCII values of the characters; thus, a string with _n_ characters is represented by _n_+1 bytes. For example, the phrase “slithy toves” is represented by the following byte array (numbers shown in hexadecimal):

Encrypted strings are encoded the same way: the length is _not_ encrypted, but all the characters in the string are. (This length-prefixed string encoding is often called a “Pascal string” from its use in the 1970s-vintage UCSD flavour of Pascal. Note that these are different from the null-terminated “C strings” you may have seen before.) ## Designing the Decryption Circuit ### Task 1: Embedded memories and ARC4 state initialization In this task, you will get started by creating a RAM using the Megafunction Wizard, creating circuitry to fill the memory, and observing the contents using the In-System Memory Content Editor. #### Creating a RAM block using the Wizard First, create a new Quartus project. Then, create a memory component as follows: In Quartus, select _Tools→IP Catalog_, and from the IP catalog pane that opens, choose _Basic Functions→On Chip Memory→RAM: 1-Port_. Choose Verilog, and create an output file called `s_mem.v` in your project directory. In the next few panels, customize your Megafunction as follows: - How wide should the _q_ output bus be? **8 bits** - How many 8-bit words of memory? **256 words** - What should the memory block type be? **M10K** (this is the SRAM block embedded in the Cyclone V) - What clocking method would you like to use? **Single clock** - Which ports should be registered: **make sure the _q_ output port is unselected** - Create one clock enable signal... : **do not select** - Create an _aclr_ asynchronous clear... : **do not select** - Create a _rden_ read enable... : **do not select** - What should the _q_ output be...: **new data** - Do you want to specify the initial contents? **no** - Allow In-System Memory Content Editor to capture and update...: **select this** - The _Instance ID_ of this RAM is: **S** (uppercase) - Generate netlist: **do not select** - Do you want to add the Quartus Prime file to the project? **yes** When you finish this, you will find the file `s_mem.qip` in your project file list. If you expand it, you will also see `s_mem.v`. Open the Verilog file and examine it: you will find the module declaration for `s_mem`, which will look something like this: ```Verilog module s_mem ( address, clock, data, wren, q); input [7:0] address; input clock; input [7:0] data; input wren; output [7:0] q; ``` Be sure your declaration matches the above. This is the module you will include as a component in your design. **Do not modify this file**, or it might not do what you want during synthesis. In the rest of the file you can see how `s_mem.v` configures and instantiates the actual embedded RAM component we discussed in lecture. The instance ID you specified (here, “S”) will be used to identify this memory when you examine the memory while your circuit is running inside your FPGA. #### Implementing the S-array initialization step In the `task1` folder you will find a `init.sv` and a toplevel file `task1.sv`. In `init.sv`, you will will implement the first step of ARC4, where the cipher state S is initialized to [0..255]: for i = 0 to 255: s[i] = i The `init` module follows the ready/enable microprotocol [described above](https://github.com/basilwong/FPGA-ARC4-cracker/blob/master/#the-ready-enable-microprotocol). You will see that this declares the component that you have just created using the Wizard. You will find that the toplevel `task1` module already instantiates the `s_mem` RAM you generated earlier using the MF Wizard. `KEY[3]` will serve as our reset signal. Add an instance of your `init` module and connect it to the RAM instance. For the final submission, make sure that `init` is activated **exactly once** every time reset is deasserted, and that _S_ is not written to after `init` finishes. Note: **do not** rename the memory instance — we need to be able to access it from a testbench to test your code. Hint: Remember to follow the ready-enable microprotocol we defined earlier. It is not outside the realm of possibility that we could replace either `init` or `task1` with another implementation when testing your code. Import your pin assignments (as usual), compile, and proceed to the next steps to learn how to examine the _S_ memory in the FPGA and in Modelsim. #### Examining memory contents inside the FPGA You can examine the contents of the memory while your circuit is running in the FPGA. To do this, program your FPGA with the circuit and select _Tools→In-System Memory Content Editor_ while your circuit is active. This will open a window that shows the memory contents. In the instance manager window (left) you should see a list of memories in your design (in this Task, only the _S_ memory you created). Right click _S_, and choose _Read Data from In-System Memory_:

The In-System Memory Content Editor in only available for the single-ported RAM and ROM configurations. The reason is simple: when you generate a RAM or ROM with the in-system editing option enabled, Quartus generates circuitry to read and write your memory; that circuitry takes up one of the ports of the underlying embedded memory, leaving you with only one port. You will need to use the Memory Content Editor later in the lab. #### Simulating Altera memories in ModelSim To simulate with ModelSim, you will need to include the `altera_mf_ver` library (under the Libraries tab) when you start simulation. If you are using the tcl shell instead of clicking around, use the `-L` option to `vsim`, like in this example: vsim -L altera_mf_ver work.tb_task1 To make ModelSim happy about how many picoseconds each #-tick is, you will have to add `timescale 1ps / 1ps at the beginning of your testbench. You might find ModelSim's memory viewer (accessible from _View→Memory List_) helpful here; it will list all the memories in the design and allow you to examine any of them. I usually change the radix to hex (right-click on the memory contents view and select _Properties_). Alternately, you can access the memory from your testbench using the dot notation: dut.s_mem.altsyncram_component.m_default.altsyncram_inst.mem_data (assuming you named your `task1` instance `dut` inside your testbench). Note that **the dot notation may be used only in your testbench**, not in anything you wish to synthesize. If you (later) decide to initialize the memory in one of your testbenches in an initial block, be sure to do this after a delay (e.g., `#10`); otherwise your initialization will end up in a race condition with the Altera memory model and its own initial block. You might want to become friends with `$readmemh()` and `$writememh()` as well. #### Initializing memories In Quartus, can initialize memories at compilation time using either a Memory Interface File (.mif) or an Intel Hex Format file (.hex). We recommend you use the first format because it's _a lot_ easier to read, but it's up to you. Either way, Quartus includes a table-like editor for these formats; you can create a new file via _File→New→Memory Files_. ### Task 2: The Key-Scheduling Algorithm Many symmetric ciphers, including ARC4, have a phase called the _Key-Scheduling Algorithm_ (KSA). The objective of the KSA is to spread the key entropy evenly across _S_ to prevent statistical correlations in the generated ciphertext that could be used to break the cipher. ARC4 does this by swapping values of _S_ at various indices: j = 0 for i = 0 to 255: j = (j + s[i] + key[i mod keylength]) mod 256 -- for us, keylength is 3 swap values of s[i] and s[j] (and, in fact, does not completely succeed at this, which can be exploited to break the cipher). In folder `task2` you will find `ksa.sv`, which you will fill out to implement the KSA phase. Like `init`, the `ksa` module will implement the ready/enable microprotocol. Note that `ksa` must **not** include the functionality of `init`. Next, finish the toplevel implementation in `task2.sv`. This module should instantiate the _S_ memory as well as `init` (from Task 1) and `ksa`. To set the key, we will use the switches on your DE1-SoC. There are only ten switches, so **for tasks 2 and 3 only** the toplevel module (here, `task2` but not `init`) should hardwire bits [23:10] of the `ksa` _key_ parameter to zero; we will use _SW_[9:0] as _key_[9:0]. (Don't confuse the encryption _key_ parameter to `ksa` with the _KEY_ parameter to `task2`, which refers to the DE1-SoC buttons.) On reset (`KEY[3]`), it will first run `init` and then `ksa`, just like in the ARC4 pseudocode. Again, make sure that your code obeys the module interfaces and does not rely on exact timing properties of other modules; we might replace some of these modules for testing. To check your work, here are the final contents of _S_ for the key `'h00033C` after both `init` and `ksa` have finished: 0000: b4 04 2b e5 49 0a 90 9a e4 17 f4 10 3a 36 13 77 0010: 11 c4 bc 38 4f 6d *** 06 6e 3d 2c ae cd 26 40 a2 0020: c2 da 67 68 5d 3e 02 73 03 aa 94 69 6a 97 6f 33 0030: 63 5b 8a 58 d9 61 f5 46 96 55 7d 53 5f ab 07 9c 0040: a7 72 31 a9 c6 3f f9 91 f2 f6 7c c7 b3 1d 20 88 0050: a0 ba 0c 85 e1 cf cb 51 c0 2e ef 80 76 b2 d6 71 0060: 24 ad 6b db ff fe ed 84 4e 8c bb d3 a5 2f be c8 0070: 0e 8f d1 a6 86 e3 62 b0 87 ec b9 78 81 e0 4d 5a 0080: 7a 79 14 29 56 e8 4a 8e 18 c5 ca b7 25 de 99 c3 0090: 2a 65 30 1a ea fb a1 89 35 a4 09 a3 c1 d8 2d b8 00a0: 60 47 39 bd 1f 05 5e 43 b1 dd e9 1c af 9b fa 01 00b0: f7 08 75 b6 82 ce 42 e2 cc 9e eb 27 22 df bf fc 00c0: 0d d0 95 23 d2 a8 7e 74 4c d7 12 7f fd 83 1e 28 00d0: *** 54 3c 21 dc f3 93 59 8b 7b 00 48 e7 6c d5 c9 00e0: 70 9f ac 41 0b f0 19 b5 8d 16 d4 f1 92 9d 66 44 00f0: 4b 15 45 f8 0f 57 34 32 50 52 ee 3b 5c 37 e6 1b Before proceeding further, verify that this is the case in simulation using Modelsim's Memory List, and then in FPGA using the In-System Memory Content Editor. (A common mistake is getting the key endianness backwards.) ### Task 3: The Pseudo-Random Generation Algorithm The final phase of ARC4 generates the bytestream that is then xor'd with the input plaintext to encrypt the message, or, as in our case, with the input ciphertext to decrypt it. We don't need the bytestream by itself, so in this task we will combine both. i = 0, j = 0 for k = 0 to message_length-1: i = (i+1) mod 256 j = (j+s[i]) mod 256 swap values of s[i] and s[j] pad[k] = s[(s[i]+s[j]) mod 256] for k = 0 to message_length-1: plaintext[k] = pad[k] xor ciphertext[k] -- xor each byte First, generate two additional memories: a ROM to hold the ciphertext (instance name _CT_), and a RAM where you will write the plaintext (instance name _PT_). Both will be 8-bit wide and 256 8-bit words deep, and will connect to your ARC4 decryption module:

Both the plaintext and ciphertext are stored starting at address 0 as length-prefixed strings (described earlier). Then, implement the bytestream/xor functionality in the `prga.sv` file in the `task3` folder. This has interfaces for all three memories. As before, the module obeys the rdy/en protocol, except that now it has a _key_ argument which must be valid at the same time as the relevant _en_ signal is asserted. Note that the `prga` module should **not** include the functionality of `init` ... ...

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：