RC5-32/20/32 CBC Pad implementation in C for Linux using file mapping and generating key from user passphrase

rc5.c

/*

This is C implementation of RC5-32/20/32 CBC Pad. You can change
algorithm macroses W, R and B in order to create RC5 variations.
R and B parameters can be chosen freely (but with RFC 2040
limitations), but only W=32 is implemented in this code fully.
Those lines where W changing can occure errors is commented.

You can compile this file using the following directive:
gcc rc5.c md5.c rand.c io.c \
	-DOMIT_RAND_MAIN -DOMIT_MD5_MAIN -o bin/rc5

Following flags are available:
-DOMIT_RC5_MAIN   Do not include main of rc5.c into your code.

Setting the key
==================
This program generates RC5 key using the user passphrase. Let
P be passphrase and K be the key. Knowing the result of MD5 is
always 16 bit, key generation algorithm can be stated as
following:
md5(P) >> 4                    for 8 bit,
md5(P)                             16 bit,
concat(md5(P), md5(md5(P)))        32 bit.

Structure of the encrypted file
=================================
Encrypted file structure is following:
1st        block is encrypted IV
[2..n-1]th blocks is file content
[n]th      block contains padding if needed.
Padding will be added to the file if content of the file is not
a multiplier of word size. Padding have the following structure:
[f1 ... fn (8-n) ... (8-n)], where f1..fn is the [1..n]th block
of the file and (8-n) is leftover size. 

Suppose we have following file:
"abcdefghjklm"
Its size in bytes is 12. Then encrypted file will look as
following:
1: [ebc(iv ...)]           EBC-encrypted initialization vector
2: [ebc(a b c d e f g h)]  encrypted content of the file
3: [ebc(j k l m 4 4 4 4)]  content of the file + padding

Blocks are also CBC-chained.

*/

#include "rc5.h"

#ifndef RSHIFT_U8
#define RSHIFT_U8(p, n) ( (uint8_t*)(p)+(n) )
#endif

#ifndef OMIT_RC5_MAIN

#define ENCRYPT_MODE 1
#define DECRYPT_MODE 0
char         mode      = ENCRYPT_MODE;
mapstream_t* fin       = NULL;
mapstream_t* fout      = NULL;
char*        fout_addr = NULL;
rc5_key_t*   key       = NULL;

int main(int argc, char *argv[]){

	// Settings for linear congruence generator
	LINCON_RAND_M = 217728;
	LINCON_RAND_A = 84589;
	LINCON_RAND_C = 45989;
	RAND_SEED     = (uint64_t)clock();

	int argument = 0;

	while( (argument = getopt(argc, argv, "hp:i:o:ds")) != -1 ){
		switch(argument){

			case 'h':
				printf(
"Usage ./rc5 [-e|-d] -i input_file -p passphrase [...]\n"
"This is RC5-32/20/32 implementation. It takes your file and encrypts it with\n"
"the key you gave.\n"
"Following flags are available:\n"
"  -h      Prints this message;\n"
"  -i [..] Input file to work with;\n"
"  -o [..] Output file, which will be truncated and created if don't exist.\n"
"  -d      Use decrypt mode. Decrypts -i file and put result to -o. Encryption\n"
"          mode is used by default;\n"
"  -p      Passphrase to operate with.\n"
				);
				return 0;
				break;

			case 'p':
				key = rc5_generate_key(optarg);
				break;

			case 'i':
				fin = malloc(sizeof(mapstream_t));
        // `openfmap` is from io.h namespace.
				openfmap(fin, optarg, O_RDONLY, 0, PROT_READ, 0);
        // Warning here: this code finds nearest multiplier
        // of 8, because our word size is 32 bit (and 32
        // bit is 8 bytes). You should find nearest multipliers
        // of 4 or 16 if some day you will decide size of
        // the word should be changed.
        // Comments and suggestions are welcomed here.
				fin->sizeslot1 = (fin->fsize + 7) & (-8);
				break;

			case 'o':
				fout = malloc(sizeof(mapstream_t));
				fout_addr = optarg;
				break;

			case 'd':
				mode = DECRYPT_MODE;
				break;

		}
	}

	if(fin == NULL || fout == NULL){
		EMERGENCY("Use -i and -o flags to set input and output files");
		exit(EXIT_FAILURE);
	}

	if(key == NULL){
		EMERGENCY("Passphrase was not set");
		exit(EXIT_FAILURE);
	}

	openfmap(
		fout, fout_addr,
		O_RDWR | O_TRUNC | O_CREAT, 0, PROT_WRITE,
		(mode == ENCRYPT_MODE)
			? fin->sizeslot1 + BW
			: fin->fsize - BW
	);

	rc5_word S[T];
	rc5_setup(key->d, S);

	if(mode == ENCRYPT_MODE){
		rc5_enc_cbc_pad(S, fin, fout);
	}
	else{
    // rc5_dec_cbc_pad returns number of bytes should
    // be truncated at the end of the file.
		uint8_t pad_erase = rc5_dec_cbc_pad(S, fin, fout);
		truncate(fout_addr, fout->fsize - pad_erase);
	}

	closefmap(fin);
	closefmap(fout);
	memset(S, 0, T);
	free(fin);
	free(fout);
	free(key);

	return 0;

}
#endif

/*Read file as blocks and perform padding, If freeafter = 1 after executing,
* then function result should be freed.*/
rc5_block_t* rc5_read_pad_map(char* freeafter, mapstream_t* source){

	*freeafter = 0;

	// Reached the end of the file
	if(source->cursor >= source->sizeslot1)
		return RC5_EOF;

	// Next block is fully in the file range
	if(source->cursor + (BW) <= source->fsize){
		rc5_block_t* block = (rc5_block_t*)(source->map + source->cursor);
		// Increase cursor at one block size in bytes
		source->cursor += BW;
		return block;
	}

	// Block will contain padding
	rc5_block_t* block = calloc(1, sizeof(rc5_block_t));
	*freeafter = 1;
	char unpaded_size = source->fsize - source->cursor;
	memcpy(block, source->map + source->cursor, unpaded_size);

	// Pad file with padding size
	char padding_size = 8 - unpaded_size;
	while(unpaded_size < 8)
		block->bytes[unpaded_size++] = padding_size;

	source->cursor += BW;
	return block;

}

/*Read file as simple RC5 blocks [a, b]. */
rc5_block_t* rc5_read_map(mapstream_t* source){

	if(source->cursor >= source->fsize)
		return RC5_EOF;

	rc5_block_t* block = (rc5_block_t*)(source->map + source->cursor);
	source->cursor += BW;
	return block;

}

/*Encode `fin` file with RC5-CBC-PAD mode using given S table. Initialization
* vector will be calculated using linear congruence calculator. */
void rc5_enc_cbc_pad(rc5_word S[T], mapstream_t* fin, mapstream_t* fout){

	char         freeafter;
	rc5_block_t* plain_block;
	rc5_block_t* plain_block_xor = malloc(sizeof(rc5_block_t));
	rc5_block_t* prev_cypher_block = (rc5_block_t*)&fout->map[-BW];
	rc5_block_t* curr_cypher_block = (rc5_block_t*) fout->map;

	rc5_block_t* iv = rc5_create_iv();
	memcpy(curr_cypher_block, iv, sizeof(rc5_block_t));

	while(
		// Read block of plain text and assign result to plain_block
		(plain_block = rc5_read_pad_map(&freeafter, fin)) != RC5_EOF &&
		// Shift prev_cypher_block. At first iteration this becomes just the
		// beginning of the file.
		(prev_cypher_block = (rc5_block_t*)RSHIFT_U8(prev_cypher_block, BW)) &&
		// Shift curr_cypher_block. At 1st iter this becomes 2nd block in the
		// file. That makes sense, because 1st block already filled with IV.
		(curr_cypher_block = (rc5_block_t*)RSHIFT_U8(curr_cypher_block, BW))
	){

		memcpy(plain_block_xor, plain_block, sizeof(rc5_block_t));
		for(char i = 0; i < BW; i++)
			plain_block_xor->bytes[i] ^= prev_cypher_block->bytes[i];
		rc5_block_encrypt(plain_block_xor, curr_cypher_block, S);

		if(freeafter) free(plain_block);

	}

	free(plain_block_xor);

	// Encrypt IV
	rc5_block_encrypt(iv, (rc5_block_t*)fout->map, S);
	rc5_destroy_iv(iv);

}

/*Inverse to rc5_enc_cbc_pad.
* Returns number if bytes should be truncated from the end of the file. */
uint8_t rc5_dec_cbc_pad(rc5_word S[T], mapstream_t* fin, mapstream_t* fout){

	rc5_block_t* output_block = (rc5_block_t*)&fout->map[-BW];


	char         freeafter = 1;
	rc5_block_t* prev_cypher_block = malloc(sizeof(rc5_block_t));
	rc5_block_t* curr_cypher_block = rc5_read_map(fin);
	rc5_block_decrypt(curr_cypher_block, prev_cypher_block, S);

	while(
		(curr_cypher_block = rc5_read_map(fin)) != RC5_EOF &&
		(output_block = (rc5_block_t*)RSHIFT_U8(output_block, BW))
	){

		rc5_block_decrypt(curr_cypher_block, output_block, S);

		for(char i = 0; i < BW; i++)
			output_block->bytes[i] ^= prev_cypher_block->bytes[i];

		if(freeafter){
			free(prev_cypher_block);
			freeafter = 0;
		}

		prev_cypher_block = curr_cypher_block;

	}

	// Byte cannot be paded for more than 7 bite, that's probably a part of file
	if(output_block->bytes[7] > 7) return 0;

	// Check if there's sequence of padding bytes at the end.
	char counter = 1, i = 6;
	for(;i >= 0; i--)
		if(output_block->bytes[i] == output_block->bytes[i + 1])
			counter++;
		// Sequence breaks here.
		else break;

	// If sequence were found correctly, all its numbers should be equal to
	// counter.
	if(output_block->bytes[i + 1] == counter)
		return counter;
	// Otherwise treat sequence as incorrect and ignore it.
	else
		return 0;

}

rc5_key_t* rc5_generate_key(const char* passphrase){

	rc5_md5sum_key_t* key = malloc(sizeof(rc5_md5sum_key_t));

	md_buffer_t* md1 = md5_hash_raw(passphrase, strlen(passphrase));

#if B == 32
	md_buffer_t* md2 = md5_hash_raw(md1->digits, 16);
	memcpy(&key->md[0], md1, sizeof(md_buffer_t));
	memcpy(&key->md[1], md2, sizeof(md_buffer_t));
	memset(md2, (uint8_t)0, sizeof(md_buffer_t));
	free(md2);
#elif B == 16
	memcpy(&key->md[0], md1, sizeof(md_buffer_t));
#elif B == 8
	memcpy(&key->md[0], &(md1->digits[8]), sizeof(md_buffer_t) / 2);
#endif

	memset(md1, (uint8_t)0, sizeof(md_buffer_t));
	free(md1);

	return (rc5_key_t*)key;

}

void rc5_block_encrypt(rc5_block_t* plain, rc5_block_t* cipher, rc5_word S[T]){

	rc5_word i;
	rc5_word word_a = plain->words.a + S[0];
	rc5_word word_b = plain->words.b + S[1];

	for(i = 1; i <= R; i++){
		word_a = ROTL(word_a ^ word_b, word_b) + S[2 * i    ];
		word_b = ROTL(word_b ^ word_a, word_a) + S[2 * i + 1];
	}

	cipher->words.a = word_a;
	cipher->words.b = word_b;

}

void rc5_block_decrypt(rc5_block_t* cipher, rc5_block_t* plain, rc5_word S[T]){

	rc5_word i;
	rc5_word word_b = cipher->words.b;
	rc5_word word_a = cipher->words.a;

	for(i = R; i > 0; i--){
		word_b = ROTR(word_b - S[2 * i + 1], word_a) ^ word_a;
		word_a = ROTR(word_a - S[2 * i    ], word_b) ^ word_b;
	}

	plain->words.b = word_b - S[1];
	plain->words.a = word_a - S[0];

} 

// k is secret input key
void rc5_setup(uint8_t* key, rc5_word S[T]){ 

	rc5_word i, j, k;
	rc5_word word_a, word_b;
	rc5_word L[C];

	// Convert secret key from bytes to words
	for(
		i = B - 1, L[C - 1] = 0;
		i != -1;
		i--
	)
		L[i / WW] = (L[i / WW] << 8) + key[i];

	// Set S (expanded key) table
	for(
		S[0] = Pw, i = 1;
		i < T;
		i++
	)
		S[i] = S[i - 1] + Qw;

	// Mix in the secret key
	for(
		word_a = word_b = 0, i = j = k = 0;
		k < 3 * T;
		k++, i = (i + 1) % T, j = (j + 1) % C
	){
		word_a = S[j] = ROTL(S[i] + (word_a + word_b), 3);
		word_b = L[j] = ROTL(L[j] + (word_a + word_b), (word_a + word_b));
	}

}

rc5_block_t* rc5_create_iv(){

	rc5_block_t* iv = malloc(sizeof(rc5_block_t));

	iv->words.a = (rc5_word)rand_lincon();
	iv->words.b = (rc5_word)rand_lincon();

	return iv;

}

void rc5_destroy_iv(rc5_block_t* iv){

	memset(iv, 0, sizeof(rc5_block_t));
	free(iv);

}

rc5.h

#ifndef H_RC5
#define H_RC5

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>

// These headers can be found in gist.github.com/lynnporu
// https://gist.github.com/lynnporu/0cb091a71a8e1574dcae3e39a3952b9a
#include "io.h"
// https://gist.github.com/lynnporu/3906db1a772eee52fba56c20169d9022
#include "rand.h"
// https://gist.github.com/lynnporu/11cb33333ab6dcf607bc0f8dc524cc80
#include "md5.h"

#define W  32             // Size of the word in bits
#define WW (W / 8)        // Bytes in word
#define BW (W / 4)        // Size of block on bytes
#define R  20             // Word size
#define B  32             // Size of the key in bytes
#define C  ((B * 8) / W)  // Number of words in key
#define T  2 * (R + 1)    // Size of the table S = 2*(R+1)

// Magic constants
#define P16  0xb7e1
#define Q16  0x9e37
#define P32  0xb7e15163
#define Q32  0x9e3779b9
#define P64  0xb7e151628aed2a6b
#define Q64  0x9e3779b97f4a7c15
#if   W == 16
	typedef uint16_t rc5_word;
	#define Pw   P16
	#define Qw   Q16
#elif W == 32
	typedef uint32_t rc5_word;
	#define Pw   P32
	#define Qw   Q32
#elif W == 64
	typedef uint64_t rc5_word;
	#define Pw   P64
	#define Qw   Q64
#endif

// Rotation operators; x should by unsigned
#define ROTL(x,y) (((x) << (y & (W - 1))) | ((x) >> (W - (y & (W - 1)))))
#define ROTR(x,y) (((x) >> (y & (W - 1))) | ((x) << (W - (y & (W - 1)))))

#define RC5_EOF ((rc5_block_t*)(-1))

typedef struct {
	uint8_t d[B];
} rc5_key_t;

// This can be used to compute RC5 key from MD5 hash of the passphrase
typedef union {
	rc5_key_t     bytes;
	md_buffer_t md[B / 16];
} rc5_md5sum_key_t;

typedef union {
	struct {
		rc5_word a;
		rc5_word b;
	} words;
	uint8_t bytes[BW];
} rc5_block_t;

__attribute__((malloc))
rc5_key_t* rc5_generate_key(const char* passphrase);

__attribute__((warn_unused_result, hot))
rc5_block_t* rc5_read_pad_map(char* freeafter, mapstream_t* source);

void rc5_block_encrypt(rc5_block_t* plain, rc5_block_t* cipher, rc5_word S[T]);
void rc5_block_decrypt(rc5_block_t* cipher, rc5_block_t* plain, rc5_word S[T]);

void rc5_setup(uint8_t* k, rc5_word S[T]);

void rc5_enc_cbc_pad(rc5_word S[T], mapstream_t* fin, mapstream_t* fout);
uint8_t rc5_dec_cbc_pad(rc5_word S[T], mapstream_t* fin, mapstream_t* fout);

__attribute__((malloc, warn_unused_result))
rc5_block_t* rc5_create_iv();

void rc5_destroy_iv(rc5_block_t* iv);

#endif