Key expansion

importance.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/sha.h>

#define BUF_SZ (1 << 16)
#define PAD_SZ 256

#define hash_init   SHA256_Init
#define hash_update SHA256_Update
#define hash_final  SHA256_Final
#define hash_ctx    SHA256_CTX
#define HASH_SZ     SHA256_DIGEST_LENGTH

uint8_t
incr_pad(char pad[PAD_SZ], size_t padlen)
{
	size_t i = 0;
	for (i = 0; ((uint8_t) pad[i] == 0xFF); ++i)
		pad[i] = 0;
	pad[i]++;
	if (i > padlen) {
		fprintf(stderr, "Trying %ld padding\n", i);
		return i;
	} else {
		return padlen;
	}
//	return i > padlen ? i : padlen;
}

int
main(int argc, char *argv[])
{
	char buf[BUF_SZ];
	char pad[PAD_SZ];
	char md[HASH_SZ];
	hash_ctx buf_ctx, trial_ctx;
	uint8_t padlen = 0;
	size_t buflen = 0;

	size_t i;
	uint8_t importance = 1;

	if (argc > 1 && !(importance = atoi(argv[1]))) {
		fprintf(stderr, "Usage: %s <importance>\n", argv[0]);
		return 1;
	}

	padlen = importance;
	hash_init(&buf_ctx);

	while (buflen = fread(buf, 1, BUF_SZ, stdin)) {
		hash_update(&buf_ctx, buf, buflen);
		fwrite(buf, 1, buflen, stdout);
	}

	do {
		memcpy(&trial_ctx, &buf_ctx, sizeof(hash_ctx));
		hash_update(&trial_ctx, pad, padlen);
		hash_update(&trial_ctx, &padlen, 1);
		hash_final(md, &trial_ctx);
		for (i = 0; i < importance; ++i) {
			if (md[i]) {
				padlen = incr_pad(pad, padlen);
				break;
			}
		}
	} while (i != importance);

	fwrite(pad, padlen, 1, stdout);
	fwrite(&padlen, 1, 1, stdout);

	return 0;
}

keys.c

#include <stdlib.h>
#include <stdio.h>
#include <openssl/sha.h>

/* Key expansion scheme:
 * 1. Create a buffer of 2^23 blocks of 256-bit words (256 MB).
 * 2. Set block 0 to the SHA256 of the input
 * 3. Fill the remaining blocks as follows:
 *      i) Set block n + 1 to the SHA256 of block n
 *     ii) XOR the first byte of block (n + 1) with ((n + 1) % 256)
 *    iii) XOR the first byte of block (n + 1) with the last byte of block n
 * 4. Let y(0) be the final (the (2^23 - 1)th) block
 * 5. Compute the sequence yn as follows:
 *      i) Consider y(n) as 10 3-byte segments (with two bytes left over)
 *     ii) For i = 1..10, let s[i] be the ith segment, big endian modulo 2^23
 *         (i.e. without the highest bit)
 *    iii) Compute y(n+1) = s[1] ^ s[2] ^ ... ^ s[10]
 * 6. The output is y(2^16)
 *
 * The above process means that 10 * 2^16 of the blocks are used for the final
 * output, which ends up being more than 1 in 16 unique blocks.
 */
#define ADDRBITS 23
#define NUMSTRANDS 10

#define BLOCKSIZE SHA256_DIGEST_LENGTH
#define NUMBLOCKS (1 << ADDRBITS)

#if ADDRBITS * NUMSTRANDS > BLOCKSIZE * 8
#error Impossible configuration
#endif

void
debug(void)
{
	fprintf(stderr, "Allocating 2^%d = %d blocks", ADDRBITS, NUMBLOCKS);
	fprintf(stderr, " of %d bytes (%d bits)\n", BLOCKSIZE, 8 * BLOCKSIZE);
	fprintf(stderr, "This will use %dMB\n", NUMBLOCKS * BLOCKSIZE / 1024 / 1024);
	fprintf(stderr, "Running %d strands", NUMSTRANDS);
	fprintf(stderr, ", using %d bits of blocks\n", NUMSTRANDS * ADDRBITS);
}

void
print_block(unsigned char *block)
{
	size_t i;
	for (i = 0; i < BLOCKSIZE; ++i)
		printf("%02x", (uint8_t) block[i]);
	printf("\n");
}

int
main(void)
{
	debug();

	size_t i, j, k;
	char msg[] = "This is a test";
	unsigned char *buf = calloc(NUMBLOCKS, BLOCKSIZE);
	unsigned char y[BLOCKSIZE], z[BLOCKSIZE];
	uint32_t strand_addr;

	SHA256(msg, sizeof(msg)-1, buf);
	for (i = 1; i < NUMBLOCKS; ++i) {
		SHA256(&buf[BLOCKSIZE * (i - 1)], BLOCKSIZE, &buf[BLOCKSIZE * i]);
		buf[BLOCKSIZE * i] ^= ((unsigned char) i) ^ buf[BLOCKSIZE * i - 1];
	}

	for (j = 0; j < BLOCKSIZE; ++j)
		y[j] = buf[BLOCKSIZE * (NUMBLOCKS - 1) + j];
	for (j = 0; j < BLOCKSIZE; ++j)
		z[j] = 0;
	for (k = 0; k < (1 << 16); ++k) {
		for (i = 0; i < NUMSTRANDS; ++i) {
			strand_addr = (y[3*i] << 16) | (y[3*i + 1] << 8) | y[3*i +2];
			strand_addr &= NUMBLOCKS - 1;
			fprintf(stderr, "hit block %06x\n", strand_addr);
			for (j = 0; j < BLOCKSIZE; ++j)
				z[j] ^= buf[strand_addr + j];
		}
		for (j = 0; j < BLOCKSIZE; ++j)
			y[j] = z[j];
	}

	print_block(z);

	return 0;
}

Makefile

.PHONY: default
default: keys
	./keys

keys: CFLAGS += -lcrypto