Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
276 lines (255 sloc) 12.1 KB
/*
* This is a statistical test of the HSS signatures.
* Now, we're not questioning the statistical properties of SHA-256. However,
* SHA-256 has one statistical "failing", identical inputs will result in
* identical outputs (actually, the entire HBS process depends on this, so
* it's not really that serious of a failing). So, what we're doing is
* looking for duplicate hashes, which would imply duplicate inputs (or a
* hash collision, which is *real* unlikely), which would imply a weakness.
* Now, the LMS scheme mandates that the hash inputs are distinct, except in
* three cases:
* - The OTS private keys
* - The I values
* - The C randomizer (the part that is hashed along with the message)
* Repeating OTS private keys is *BAD*, as it would give enough information
* for an attacker to forge. Repeating I values or C randomizers isn't nearly
* as bad, it'd just reduce the security margin (in the case of I, allow
* multitarget attacks; actually, the security proof accounts for it, however
* it really shouldn't happen in the relatively small number of keys we use),
* in the case of C, well, actually, collisions aren't an issue;
* predictability is (and having a higher-than-expected collision probability
* would make things predictable). Neither of these latter two would actually
* be the end of the world, but they shouldn't happen; we might as well throw
* those as well (especially since it makes the test easier).
*
* So, what we do is collect a series of signatures, and see if they contain
* any duplicated hashes
*
* Also, when we're doing a multilevel HSS scheme, two different signatures
* from the same Merkle level will contain the same upper level hashes (from
* common aux path), we deliberately make sure we sample from different top
* level signatures (and keep the same bottom level indexes; if there's a
* problem there, this would show it up)
*/
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "hss.h"
#include "test_hss.h"
/*
* This is the parameter set we use (and the internal number of hashes)
*/
#define LM_PARAM LMS_SHA256_N32_H5 /* Use as cheap of an LM path as */
/* possible; this is not what we're testing */
#define OTS_PARAM LMOTS_SHA256_N32_W1 /* Problems with the hash is */
/* more likely to show up here */
/* If you change the above params, the below need to be fixed as well */
/* Note: hashes are actually 32 bytes; however I values are 16, and we'd */
/* like to validate those against reuse */
/* The way to handle that is to claim to the infrastructure that we */
/* actually have 16 byte hashes (and twice as many, except for the I value) */
#define HASH_PER_OTS_SIG (2*(1 + 265))
#define HASH_PER_LM_SIG (2*5)
#define HASH_PER_PK (1 + 2)
#define HASH_SIZE 16
#define LOG_HASH_PER_MERKLE_TREE 5 /* We use an H=5 parameter sets */
#define HASH_PER_MERKLE_TREE 32 /* We use an H=5 parameter sets */
static int rnd_count;
/*
* This is the "randomness generator" we use for this test. Obviously,
* you shouldn't think of using this in a real program
*/
static bool generate_random(void *output, size_t length) {
int n = rnd_count++;
int i;
unsigned char *p = output;
for (i = length-1; i>=0; i--) {
p[i] = n & 0xff;
n >>= 8;
}
return true;
}
struct bin {
unsigned char hash[HASH_SIZE];
/* These bitfields track where the hash is from. It doesn't help */
/* us deciding whether the test passed or failed; it might give */
/* insight as to the reason behind a failure */
unsigned index : 9; /* Index from start of region */
unsigned region : 6; /* Which region (sig/pk in signaure) */
unsigned sig_num : 5; /* Which signature from the same key it's from */
unsigned key_num : 2; /* Which key it's from */
unsigned d : 3; /* The d value we used */
};
static int compare_hash(const void *a, const void *b) {
const struct bin *p = a;
const struct bin *q = b;
return memcmp(p->hash, q->hash, HASH_SIZE);
}
#define MAX_BIN 519936
/* Yes, this is 10+Meg; if you don't have that much, get a real computer */
#define MAX_D 4
bool test_stat(bool fast_flag, bool quiet_flag) {
rnd_count = 0;
bool success = false;
struct bin *t = malloc( MAX_BIN * sizeof *t );
if (!t) {
printf( " Malloc failure\n" );
return false;
}
long bin_count = 0;
int d;
for (d=1; d<=MAX_D; d++) {
int k;
param_set_t lm_type[MAX_D], lm_ots_type[MAX_D];
int i;
for (i=0; i<d; i++) {
lm_type[i] = LMS_SHA256_N32_H5;
/* We use W=1, as that's more likely to allow hash */
/* failures to show up */
lm_ots_type[i] = LMOTS_SHA256_N32_W1;
}
size_t pub_key_len = hss_get_public_key_len(d, lm_type, lm_ots_type);
size_t sig_len = hss_get_signature_len(d, lm_type, lm_ots_type);
size_t priv_len = hss_get_private_key_len(d, lm_type, lm_ots_type);
if (!pub_key_len || !sig_len || !priv_len) {
printf( " Bad parm set\n" );
goto failed;
}
/* Try it for 3 distinct keys */
for (k=0; k<3; k++) {
unsigned char aux_data[200];
unsigned char pub_key[pub_key_len];
unsigned char private_key[priv_len];
if (!hss_generate_private_key( generate_random,
d, lm_type, lm_ots_type,
NULL, private_key,
pub_key, pub_key_len,
aux_data, sizeof aux_data, 0 )) {
printf( " Pubkey gen failure\n" );
goto failed;
}
struct hss_working_key *w = hss_load_private_key(
NULL, private_key, 0, aux_data, sizeof aux_data, 0);
if (!w) {
printf( " Privkey load failure\n" );
goto failed;
}
for (i=0; i<HASH_PER_MERKLE_TREE; i++) {
static char test_message[3] = "abc";
/* Generate a signature */
unsigned char sig[sig_len];
if (!hss_generate_signature(w, NULL, private_key,
test_message, sizeof test_message,
sig, sig_len, 0)) {
printf( " Signature failure\n" );
hss_free_working_key(w);
goto failed;
}
/* Now, this test isn't here to check whether the */
/* signature generation process generates correct */
/* signatures, however it just feels wrong to not check */
if (!hss_validate_signature(pub_key,
test_message, sizeof test_message,
sig, sig_len, 0 )) {
printf( " Signature validation failure\n" );
hss_free_working_key(w);
goto failed;
}
/* Now, scan through the signature, and collect all the hashes */
size_t sig_offset = 4; /* Skip the initial num spk */
int j;
int region = 0;
for (j = 1;; j++) {
sig_offset += 8; /* Skip the q and the OTS type */
#define deposit_hash( bin, bin_count, signature, sig_offset, num_hash, region, k, sig_id, d ) \
{ int n; for (n = 0; n<num_hash; n++) { \
if (bin_count == MAX_BIN) { printf( " Error: MAX_BIN not large enough\n" ); \
hss_free_working_key(w); goto failed; } \
memcpy( bin[bin_count].hash, &signature[sig_offset], HASH_SIZE ); \
sig_offset += HASH_SIZE; \
bin[bin_count].index = n; \
bin[bin_count].region = region; \
bin[bin_count].key_num = k; \
bin[bin_count].sig_num = sig_id; \
bin[bin_count].d = d; \
bin_count++; \
} }
deposit_hash(t, bin_count, sig, sig_offset,
HASH_PER_OTS_SIG, region, k, i, d);
region++;
sig_offset += 4; /* Skip the LMS type */
if (j != 1) {
/* Non-topmost signature; we generate a fresh */
/* Merkle tree each time, so there really */
/* shouldn't be any repeats */
deposit_hash(t, bin_count, sig, sig_offset,
HASH_PER_LM_SIG, region, k, i, d);
region++;
} else {
/* j==1 is the topmost signature; they'll be a */
/* lot of repeats in that (because that Merkle */
/* tree is fixed for a private key) */
sig_offset += HASH_SIZE * HASH_PER_LM_SIG;
}
if (j == d) break;
/* Include the public key that follows */
sig_offset += 8; /* Skip the LMS/OTS type */
deposit_hash(t, bin_count, sig, sig_offset,
HASH_PER_PK, region, k, i, d);
region++;
}
if (sig_offset != sig_len) { printf( "Oops: we got something wrong here: %d %d\n", (int)sig_offset, (int)sig_len ); return false; }
if (i == 31) break;
if (d > 1) {
/* Hack to advance the key 32**(d-1) - 1 times */
/* We do this to make sure that the non-top Merkle */
/* trees we use are fresh */
if (!hss_reserve_signature( w, NULL, private_key,
(1L << (LOG_HASH_PER_MERKLE_TREE*(d-1))) - 1,
0)) {
printf( " Reservation failure\n" );
hss_free_working_key(w);
goto failed;
}
if (!hss_generate_working_key( NULL, private_key,
aux_data, sizeof aux_data, w,
0 )) {
printf( " Regeneration failure\n" );
hss_free_working_key(w);
goto failed;
}
}
}
hss_free_working_key(w);
}
}
/*
* Ok, we've collected all the hashes; now qsort them, and look for duplicates
*/
qsort(t, bin_count, sizeof *t, compare_hash);
size_t n;
success = true; /* We're successful unless we find a collision */
unsigned collision_count = 0;
for (n = 0; n+1 < bin_count; n++) {
if (0 == memcmp( t[n].hash, t[n+1].hash, HASH_SIZE )) {
success = false; /* Darn! Found a collision */
collision_count++;
if (!quiet_flag) {
/* On a massive collision, don't flood the output */
if (collision_count == 100) {
printf( "AND OTHER COLLISIONS NOT LISTED\n" );
break;
}
printf( "*** FOUND A COLLISION " );
printf( " (%d, %d, %d, %d, %d) vs (%d, %d, %d, %d, %d)\n",
t[n].d, t[n].key_num, t[n].sig_num, t[n].region, t[n].index,
t[n+1].d, t[n+1].key_num, t[n+1].sig_num, t[n+1].region, t[n+1].index );
} else
break; /* In quiet mode, there's no point in looking for */
/* a second collision */
}
}
failed:
free(t);
return success;
}