Assignment 2
Introduction
This assignment contains three problems:
Problem 1 involves the implementation of four cryptographic programs, used for hashing, message authentication and authenticated encryption (AE) and decryption.
Copyright By PowCoder代写 加微信 powcoder
Problem 2 involves the conception and implementation of a new function on a 2-3-4 tree (introduced in workshop 9).
Problem 3 involves answering a number of theory questions in di�erent situations.
As with the �rst assignment, you may �nd di�erent problems and parts more or less di�cult and may choose to only answer some parts of each problem. Marks may not be distributed in order of di�culty.
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
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 from Wikipedia [1] which shows this process, r is the rate, c is the capacity, f is our bijective function, P is our input, split into n segments of size r, and Z is our output, split into segments of size r.
The primitives you implement here will be used in the three sets of programs you create.
absorbing squeezing
P0 P1 Pn−1 Z0 Z1
ff…fff…
Note that the demarcation phase occurs immediately following the full absorption of P 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.
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. f : {0, 1}384 → {0, 1}384
(also known as a 384-bit permutation) to the state.
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 H is used to provide a check for data integrity against non-deliberate corruption. The hash function
H : {0,1}∗ → {0,1}n H(m) = h
takes an input message m of arbitrary length and outputs a �xed-length hash value h (sometimes also called a digest) of n bits. There is a technical de�nition for how a cryptographic hash function should behave, but the key properties that you should know are:
uniformity: for a randomly chosen message m, H(m) is distributed uniformly among {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 m and its hash h = H(m) on the hard drive, then later you can retrieve m′ and h′ and calculate H(m′). If H(m′) = h′, then there is a high probability that non-deliberate corruption has not occurred. Conversely if H(m′) = h′, then some corruption has happened.
Sponge-based hash function
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
This section is about the �rst program you’ll create, the hash program.
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 r bytes into the sponge without permuting immediately after.
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 r’th byte (zero-based indexing, where r 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. 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
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 BASE64 encoding, e.g.
./hash 32 tests/panda_1.txt a2f2e14b1b1e4f85fc38f04c99a10cfd9e1647b0f637e9dc83e3d5e5d52d4bde
Message Authentication Code (MAC) System
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 K and message m are inputs to the message authentication code (MAC) algorithm
MAC:{0,1}k ×{0,1}∗ →{0,1}n MAC(K, m) = t.
where k is the length of the key K in bits, the message m is of arbitrary length and the output authentication tag is of length n 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.
For your implementation of the mac function in src/crypto.c , you will see CRYPTO_KEY_SIZE = 32 de�ned in include/crypto.h indicating the use of 32-byte (256-bit) keys. You should begin by absorbing the input key into a zeroed sponge. Since RATE divides CRYPTO_KEY_SIZE exactly, this should be a simple matter of calling sponge_write (with bw_xor set to true ) for the �rst key block, then permuting the sponge, then writing the 2nd key block into the sponge, then performing one more permutation. Let this phase be known as the keying phase.
The rest of the MAC algorithm then proceeds with an absorbing, demarcation and squeezing phase as described for the hash function. In essence, you will be calculating MAC(K, m) = H(K∣∣m), where ∣∣ in this notation represents concatenation (rather than a logical OR in C).
Implementation and testing
You should view the comments in include/crypto.h for descriptions of the inputs and outputs to mac , and the comments in src/crypto.c for some hints on how to implement this approach. You
may �nd the sponge diagram useful in approaching this task.
This section is about the second program you’ll create, mac .
You can make the mac program by running make mac . Input for mac is in the form:
./mac
is the length the output MAC authentication tag will be in bytes. is the binary �le containing the key, two are provided for you in
tests/key_1.key, tests/key_2.key.
is the �le to generate the MAC of.
The output is a string representing the MAC authentication tag of the �le in BASE64 encoding, e.g.
./mac 32 tests/key_1.key tests/panda_1.txt b31bd00e9663482c0466d63923330d587dd82bde3549ad47952d688f73025959
Authenticated Encryption (AE) Scheme
Say that you and your equally security-conscious friend have managed to generate and store a key K that only both of you hold. Using the MAC algorithm, you can now send and receive messages between yourselves over the internet, and be almost completely assured that they were not tampered with in transit by someone without the key. However, there is one major issue: anyone over the network can still read your messages! Clearly this is not ideal if you don’t want anyone but your friend to know about your amazing study routine for COMP20007. Therefore, you will implement a scheme for authenticated encryption (AE) which provides a check for data integrity and authenticity, and also provides con�dentiality. This prevents outsiders from reading your precious messages.
Encryption
The encryption routine
AuthEncr : {0, 1}k × {0, 1}l → {0, 1}n × {0, 1}l AuthEncr(K, m) = (t, c)
takes a key K of length k bits and a plaintext message m of length l bits as input, and outputs an authentication tag t of length n bits and the encrypted ciphertext c also of length l bits.
You should implement the auth_encr function in src/crypto.c . The scheme is almost identical to the MAC algorithm. However, we make a slight alteration to the absorbing phase. Immediately after
This section is about the �nal pair of programs you’ll create, encr and decr
every call to sponge_write during the absorbing phase (but not the keying phase!), you should sponge_read an identical number of bytes into the ciphertext bu�er.
Decryption
The decryption routine
AuthDecr:{0,1}k ×{0,1}n ×{0,1}l →{0,1}l ×{0,1} AuthDecr(K, t, c) = {(m, 0) if authentication tag is valid
(m, 1) otherwise
takes a key K of length k bits, a tag t of length n bits and a ciphertext message m of length l bits as input. It should output the decrypted plaintext, and an integer 0 if the tag is valid for this message, or 1 otherwise. Given the description of the encryption routine, you should be able to implement decryption in auth_decr in src/crypto.c . You will have to use sponge_write with bw_xor set to
false during the absorbing phase. Implementation and testing
You should view the comments in include/crypto.h for descriptions of the inputs and outputs to encr and decr and the comments in src/crypto.c for some hints on how to implement this
approach. You may �nd the sponge diagram particularly useful in approaching the decr task.
You can make the encr and decr programs by running make encr and make decr (respectively) or
simply make all to make both. Input for encr is in the form:
./encr