Skip to content

Instantly share code, notes, and snippets.

@louisswarren

louisswarren/Makefile

Last active Apr 30, 2021
Embed
What would you like to do?
Key expansion
#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;
}
#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;
}
.PHONY: default
default: keys
./keys
keys: CFLAGS += -lcrypto
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment