Specifications are in the pdf file. The skeleton code is provided as well as driver and helper functions, although you don't need to use them. The majority of the code to be done is in crypto.c and sponge.c and is marked with //TODO or //Implement.
Problem 1: Cryptography Introduction In this assignment, you will implement some of the basic building blocks of cryptography. Cryptography is an area of computer science which deals with various aspects of information security. Speci�cally, you will build cryptographic primitives which provide assurances for integrity, authenticity and con�dentiality for some data that you might wish to send or store. These primitives are the cryptographic hash function, message authentication code (MAC) system, and authenticated encryption and decryption schemes. This assignment is purely an academic exercise. You must not use your implementations of these primitives to seriously attempt to secure data. Programming production-ready cryptographic libraries is extremely di�cult and may have fatal consequences if done incorrectly. Stick to using peer- reviewed, battled-tested libraries if you ever need to use cryptography outside of a learning environment. The Sponge Construction The primitives you implement here will be used in the three sets of programs you create. All three cryptographic primitives that you will implement are based on a data structure known as the cryptographic sponge. A sponge's state is simply an array of bytes, with a set of operations that need to be supported. For this assignment, you will use a sponge with a 48 byte (384 bit) state. A cryptographic sponge has some internal state. This internal state is split into two segments: The rate, which is the part of the sponge which absorbs some amount of the input each round by XOR-ing it with the current contents of that part of the sponge and The capacity, which is the remainder of the state and is not modi�ed directly by the input each round. Between each absorption, the state is run through a bijective function which typically acts on the entire state in some way. Following this absorbing phase, after all input data has been absorbed by the sponge, a squeezing phase typically begins, where data is extracted from the sponge's state, again running this function on the sponge. A diagram is shown below modi�ed from Wikipedia [1] which shows this process, is the rate as de�ned above, is the capacity as de�ned above, is our bijective function, is our input, split into segments of size rate, and is our output, split into segments of size rate. rate capacity f P n Z 0 0 P0 P1 Z0 Z1 absorbing squeezing rate capacity Pn−1 f f … f f f … Note that the demarcation phase occurs immediately following the full absorption of and is not shown in the diagram above, it is used to help with padding messages where their length isn't an exact multiple of the rate r and to help distinguish between messages of di�erent length. P For this assignment, the �rst program you will have to write is the hash program. The sca�old provides the interface already as well as a function to permute the values, permute_384 . The operations to be supported are: void sponge_init(sponge_t *sponge) which initialises a sponge by zeroing its state, void sponge_read(uint8_t *dest, sponge_t const *sponge, uint64_t num) which copies the �rst num bytes from the sponge's state into the dest bu�er, void sponge_write(sponge_t *sponge, uint8_t const *src, uint64_t num, bool bw_xor) which writes the �rst num bytes from the src bu�er into the �rst num bytes of the sponge's state either by bit-wise XOR with the state's existing �rst num bytes if bw_xor is true , or else by overriding the state's �rst num bytes. The remaining bytes of the state should be unaltered. void sponge_demarcate(sponge_t *sponge, uint64_t i, uint8_t delimiter) which bit- wise XORs the delimiter into the state's i th byte, and �nally void sponge_permute(sponge_t *sponge) , which applies a bijective function. (also known as a 384-bit permutation) to the state. f : {0, 1} →384 {0, 1}384 You should provide implementations of these operations in the src/sponge.c �le. You must use the permute_384 function found in include/permutation.h to implement the sponge_permute operation. For the purposes of this assignment, the provided permute_384 implements a permutation chosen uniformly randomly from the set of all possible 384-bit permutations. It is fast to compute the result of applying permute_384 to an input bit-string of length 384 bits. It is also fast to compute its inverse (remembering such an inverse permutation exists because permutation functions are bijective). You should keep this fact in mind when analysing the security of the sponge-based cryptographic primitives, but we do not explicitly make use of the inverse permutation in our implementation. Cryptographic Hash Function A cryptographic hash function is used to provide a check for data integrity against non-deliberate corruption. The hash function H H : {0, 1} → {0, 1}∗ n H(m) = h takes an input message of arbitrary length and outputs a �xed-length hash value (sometimes also called a digest) of bits. There is a technical de�nition for how a cryptographic hash function should behave, but the key properties that you should know are: m h n uniformity: for a randomly chosen message , is distributed uniformly among ,m H(m) {0, 1}n avalanching: a small change in the input should result in an uncorrelated and completely di�erent-looking digest. One example of how a hash function might be used is to check for stray radiation causing a bit-�ip in your computer’s hard drive. If you store the message and its hash on the hard drive, then later you can retrieve and and calculate . If , then there is a high probability that non-deliberate corruption has not occurred. Conversely if , then some corruption has happened. m h = H(m) m′ h′ H(m′) H(m′) = h′ H(m ) =′ h′ Sponge-based hash function This section is about the �rst program you'll create, the hash program. You should implement the function hash in src/crypto.c using the sponge construction. This function should accept an input message of speci�ed length and output a digest of speci�ed length. We begin by de�ning RATE = 16 in src/crypto.c . The sponge’s rate is the maximum number of bytes that can be read from or written to the sponge’s state using sponge_read or sponge_write before the sponge must be permuted via sponge_permute . After zeroing the sponge’s state with sponge_init , the hash function proceeds in three stages: Absorbing phase The input message is ‘absorbed’ into the sponge by alternating between writing subsequent blocks of size RATE bytes from the message (setting bw_xor to true ) into the sponge, and permuting the sponge’s state. In the last block, there will be between zero and RATE - 1 (inclusive) bytes left to write; you should just write these remaining bytes into the sponge without permuting immediately after. r Demarcation phase The two constant bytes DELIMITER_A and DELIMITER_B are de�ned in src/crypto.c . You should use sponge_demarcate to absorb DELIMITER_A into the state’s ’th byte (zero-based indexing, where was de�ned in the absorbing phase). You should then demarcate with DELIMITER_B into the state’s (RATE - 1) ’th byte. Finally, permute the sponge’s state. r r Squeezing phase We can now ‘squeeze’ a hash value from the state. You should alternate between reading RATE bytes from the sponge’s state using sponge_read and permuting the sponge’s state. In the last block, you may have fewer than RATE bytes to read; just read that number of bytes from the sponge. Implementation and testing You should view the comments in include/crypto.h for descriptions of the inputs and outputs to hash , and the comments in src/crypto.c for some examples demonstrating the correct number of writes and reads to the sponge’s state that you need to be doing. Note that output-based testing will be less useful for all tasks in this programming assignment, so you may �nd gdb more useful in ensuring functions are called in the correct order with the arguments you expect. You may test whether your program is working by clicking the Mark button on Ed, similar to the �rst assignment. You should be able to observe how changes to single characters in the input �le lead to completely di�erent looking hash values, demonstrating the avalanching property. You can make the hash program by running make hash . Input for hash is in the form: ./hash
Where: is the length the output hash will be in bytes.
is the �le to hash the contents of. The output is a string representing the hash of the �le in hexademical encoding, e.g. ./hash 32 tests/panda_1.txt a2f2e14b1b1e4f85fc38f04c99a10cfd9e1647b0f637e9dc83e3d5e5d52d4bde Message Authentication Code (MAC) System This section is about the second program you'll create, mac . We saw in the previous section how a cryptographic hash function can be used to provide a check for data integrity by detecting non-deliberate corruption with high probability. In the face of a sophisticated attacker however, this is not enough. In our hard drive example, an attacker with unnoticed access to our machine could just alter our stored �le, recalculate its hash and overwrite our stored digest. Then, we would not be able to detect this kind of tampering since the stored hash would match the hash that we calculate for the tampered �le. The key to solving this problem is to use a key! The key and message are inputs to the message authentication code (MAC) algorithm K m MAC : {0, 1} × {0, 1} → {0, 1}k ∗ n MAC(K, m) = t. where is the length of the key in bits, the message is of arbitrary length and the output authentication tag is of length bits. In the hard drive example, we would generate a random key and use it in the MAC algorithm, storing the message and resulting tag on the hard drive, but keeping the key stored separately in some secure environment. Our MAC algorithm should be designed such that any tampering from an attacker who does not possess the key can be detected with high probability. If an attacker alters the stored message or tag in any way, recalculating the MAC on the message with our secure secret key should result in a tag mismatch, which alerts us to a tampering attempt. k K m n For your implementation of the mac function in src/crypto