CYBE 331 – Lab 6 Keyed Hashing and Carter-Wegman MACs

In this lab, you'll develop your own Carter-Wegman (CW) MAC creation and verification programs that go along with a stream cipher provided.  

A CW MAC is a very computationally efficient authentication code that has gained much acceptance.  It has the following formula:

Given:

A block cipher with an t-bit key and s-bit block

Km : A mac key which is s-bits

Kb  : A block cipher key suitable for the block cipher (t-bits)

N    : A nonce (>0) which is the size of a plaintext block to the block cipher (s-bits)

C0…Cn-1 :  A Sequence of blocks of ciphertext (each s-bits long)

p    : a prime number chosen that's just larger than 2^s

You compute the authentication tag as follows:

AuthTag(Km, Kb, N, C0…Cn-1) is

Equation 1: .

Note: This looks intimidating, but is quite simple in practice.

Note: the mod 2^s is just there to make the left part of the x-or the same size as the blockcipher output

Equation 2:

Note that it's just a polynomial evaluated where the coefficients are the ciphertext blocks (u32int_t's in our case) and the  is our MAC Key.

Question 1: Let's do some playing with equation 2 by hand.  Assume C0 = 1, C1 =2, C2 =3, …

Choose Km = 15 and p= 17 and n = 3.

1.a:  compute Equation 2 (showing work). Note that the sum gets big quickly.

1.b: Now, recompute 1.a but take the remainder (mod p) for each term before continuing with the sum. You should get the same result. Note, you can do the (mod p) as often as necessary.

1.c Finally, there is a nicer way to do this: Create a variable maybe call it sum and evaluate it like the following:

Note that as you get a block of ciphertext, you only need to multiply the prior sum by the mac key and add the new block of ciphertext and then take the remainder.

Do this by hand to compute 1.a. Note how the numbers are always smaller than p and you never have to compute the power of Km.

Part 2: Download the speckcntr.zip from canvas.  It includes two C files:

speck.c: implements a simple 32-bit version of the speck blockcipher and a function that implements counter mode for speck.  (You can google Speck if you are interested.)

Our version of speck has a key size of 32 bits and block size of 32bits.

spectcntr.c: implements a functional stream cipher program that encrypts a file given an IV and a key

Your project is to create two very similar programs:

cwenc.c

and

cwverify.c

A. Play with speccntr.c

a. Create a simple 12 character text file containing "1000 DOLLARS".  Name it plain.txt

b. Choose a key and IV and encrypt plain.txt to cipher.txt using spectcntr.c.  

c. Verify you can decrypt cipher.txt using the program with the same IV and key.

d. Now, pretend to be Mallory.  Go get your bittwiddle program from prior labs and flip a bit in the first byte of cipher.txt. (call this bad.txt) Your goal is to change the cipher.txt so that when Bob decrypts it, some larger sum of money is decrypted.

i. Note 1's ascii code is 0x31 = 00110001b, 3's code is 0x33 =00110011 for instance.

e. How did you achieve this?

B. cwenc.c. Begin with spectcntr.c.  

a. You will need to input the Nonce, the Km, and Kb from the command line (in addition to the arguments already there). You should do so as hexadecimal (see the existing code for how to do it).

b. As your program encrypts the input file, it should compute the CW MAC authentication tag from Equation 1 while using the trick from 1.c to compute the polynomial.  (Note: You should use uint64_t's for your mathematics and be sure to take the remainder mod p after each multiply and add.) Note: The prime p is defined in the source code already.

c. Your program should output the tag to standard output in the following format with your netid:

i. daniels: A377221F

C. cwverify.c will begin with speccntr.c again but this time will not encrypt the file, but simply output the authentication tag for the file (Assume the file is ciphertext.) (You should remove all command line arguments but the input file, Nonce, Km, and Kb.)

a. Output the authentication tag in the same format as the prior program.

D. Do part A from above again, but this time use cwenc.c to encrypt plain.txt and then verify the tag for cipher.txt using cwverify.  What happens when you try to verify bad.txt?

Turnins:

1. Create a folder netid-lab5

2. Put answers to questions from above in answers.pdf in that folder

3. Include cwenc.c and cwverify.c and speck.c in the folder as well

4. Turn in a zip of the folder netid-lab5.zip on canvas.