From 1fd84c7dc70a0a6e6d8651fafa50c51dd697ae77 Mon Sep 17 00:00:00 2001 From: Benedict Date: Thu, 2 Feb 2017 00:32:26 +0100 Subject: added random stuff which hasn't beend added because yeah --- lib/.lib6.c.swp | Bin 0 -> 24576 bytes lib/a.out | Bin 0 -> 18736 bytes lib/circulardoublelinkedlist.h | 54 ----- lib/hashtable.h | 109 ---------- lib/lib.h | 1 + lib/lib2.c | 31 ++- lib/lib2.h | 3 +- lib/lib4.c | 196 +++++++++++++++++- lib/lib4.h | 16 +- lib/lib5.c | 6 - lib/lib5.h | 2 +- lib/lib6.c | 216 +++++++++++++++++++- lib/lib6.h | 30 +++ lib/md4.c | 251 +++++++++++++++++++++++ lib/mt_19937_tempering.txt | 34 ++++ lib/sha1.c | 391 ++++++++++++++++++++++++++++++++++++ lib/sha1.h | 56 ++++++ lib/test.c | 24 +++ lib/test_list.c | 51 +++++ lib/util/a.out | Bin 0 -> 19368 bytes lib/util/circulardoublelinkedlist.h | 54 +++++ lib/util/doublelinkedlist.h | 58 ++++++ lib/util/hashtable.h | 159 +++++++++++++++ lib/util/hashtable.h.gch | Bin 0 -> 2500240 bytes lib/util/set.h | 39 ++++ lib/util/set.h.gch | Bin 0 -> 2077904 bytes lib/util/test_hash.c | 48 +++++ lib/util/util.c | 25 +++ lib/util/util.h | 10 + 29 files changed, 1676 insertions(+), 188 deletions(-) create mode 100644 lib/.lib6.c.swp create mode 100755 lib/a.out delete mode 100644 lib/circulardoublelinkedlist.h delete mode 100644 lib/hashtable.h create mode 100644 lib/md4.c create mode 100644 lib/mt_19937_tempering.txt create mode 100644 lib/sha1.c create mode 100644 lib/sha1.h create mode 100644 lib/test.c create mode 100644 lib/test_list.c create mode 100755 lib/util/a.out create mode 100644 lib/util/circulardoublelinkedlist.h create mode 100644 lib/util/doublelinkedlist.h create mode 100644 lib/util/hashtable.h create mode 100644 lib/util/hashtable.h.gch create mode 100644 lib/util/set.h create mode 100644 lib/util/set.h.gch create mode 100644 lib/util/test_hash.c create mode 100644 lib/util/util.c create mode 100644 lib/util/util.h (limited to 'lib') diff --git a/lib/.lib6.c.swp b/lib/.lib6.c.swp new file mode 100644 index 0000000..50e56d4 Binary files /dev/null and b/lib/.lib6.c.swp differ diff --git a/lib/a.out b/lib/a.out new file mode 100755 index 0000000..8fecb11 Binary files /dev/null and b/lib/a.out differ diff --git a/lib/circulardoublelinkedlist.h b/lib/circulardoublelinkedlist.h deleted file mode 100644 index 5cda46d..0000000 --- a/lib/circulardoublelinkedlist.h +++ /dev/null @@ -1,54 +0,0 @@ -#ifndef __LIST__ -#define __LIST__ - -/** - * ciruclar double linked list implementation - * - **/ - -#include - -struct list { - struct list *next; - struct list *prev; -}; - -#define LIST_INIT(name) do { (name)->next = (name); (name)->prev = (name); } while(0); - -static int inline __list_insert(struct list *prev, struct list *new, struct list *next) -{ - prev->next = new; - new->prev = prev; - new->next = next; - next->prev = new; -} - -static int inline list_insert_after(struct list *list, struct list *new_elem) -{ - return __list_insert(list, new_elem, list->next); -} - -static int inline list_insert_before(struct list *list, struct list *new_elem) -{ - return __list_insert(list->prev, new_elem, list); -} - -static void inline __list_delete(struct list *prev, struct list *elem, struct list *next) -{ - prev->next = next; - next->prev = prev; - elem->next = elem; - elem->prev = elem; -} -static void inline list_delete(struct list *elem) -{ - __list_delete(elem->prev, elem, elem->next); -} - -#define list_get_prev(elem) (elem)->prev -#define list_get_next(elem) (elem)->next - -#define LIST_FOR_EACH(pos, head) for(pos = head->next; pos != head; pos = pos->next) -#define CONTAINER_OF(ptr, type, member) ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))) - -#endif diff --git a/lib/hashtable.h b/lib/hashtable.h deleted file mode 100644 index ff501cc..0000000 --- a/lib/hashtable.h +++ /dev/null @@ -1,109 +0,0 @@ -#ifndef __HASHMAP__ -#define __HASHMAP__ - -#include -#include -#include "circulardoublelinkedlist.h" -#include "util.h" - -struct ht_item { - char *hash; - void *data; - unsigned int data_length; - struct list list; -}; - -struct hashtable { - struct ht_item **begin; - unsigned int length; - unsigned int hash_length; - void (*hash_function)(void *data, unsigned int data_length, char *res); -}; - - -int __ht_init(struct hashtable *ht, unsigned int number_elem, - unsigned int hash_length, void (*func)(void *data, - unsigned int data_length, char *res)) -{ - ht->begin = xmalloc(sizeof(struct ht_item)*number_elem); - ht->length = number_elem; - ht->hash_length = hash_length; - ht->hash_function = func; -} - -void compute_hash_sha1(void *data, unsigned int data_length, char *res) -{ - SHA_CTX sha1; - - SHA1_Init(&sha1); - SHA1_Update(&sha1, data, data_length); - SHA1_Final(res, &sha1); - -} - -int ht_init_sha1(struct hashtable *ht) -{ - __ht_init(ht, 300, 20, compute_hash_sha1); -} - -void *ht_is_in_list(struct list *list, char *hash, int hash_length) -{ - struct list *head, *iter; - struct ht_item *res = NULL; - - head = list; - res = CONTAINER_OF(head, struct ht_item, list); - if(memcmp(res->hash, hash, hash_length) == 0) - return res->data; - - LIST_FOR_EACH(iter,head) { - res = CONTAINER_OF(iter, struct ht_item, list); - if(memcmp(res->hash, hash, hash_length) == 0) - return res->data; - } - - return NULL; -} - -void ht_add(struct hashtable *ht, void *data, unsigned int data_length, - void *key, unsigned int key_length) -{ - unsigned long index; - struct ht_item *new_elem = xmalloc(sizeof(struct ht_item)); - new_elem->hash = xmalloc(ht->hash_length); - new_elem->data = xmalloc(data_length); - - memcpy(new_elem->data, data, data_length); - new_elem->data_length = data_length; - LIST_INIT(&new_elem->list); - - ht->hash_function(key, key_length, new_elem->hash); - memcpy(&index, new_elem->hash, sizeof(unsigned long)); - index = index % ht->length; - - if(ht->begin[index] == NULL) { - ht->begin[index] = new_elem; - return; - } - - if(ht_is_in_list(&(ht->begin[index]->list), new_elem->hash, - ht->hash_length) == NULL) { - list_insert_after(&(ht->begin[index]->list), &new_elem->list); - printf("kollision\n"); - return; - } -} - -void *ht_get(struct hashtable *ht, void *key, unsigned int key_length) -{ - char *hash = xmalloc(ht->hash_length); - unsigned long index; - - ht->hash_function(key, key_length, hash); - memcpy(&index, hash, sizeof(unsigned long)); - index = index % ht->length; - - return ht_is_in_list(&(ht->begin[index]->list), hash, ht->hash_length); -} - -#endif diff --git a/lib/lib.h b/lib/lib.h index a561442..20db486 100644 --- a/lib/lib.h +++ b/lib/lib.h @@ -25,5 +25,6 @@ int isprintable(char *string, int length); int read_base64_file(const char *file, char **out); int string_is_ecb_encrypted(char *string, int length_string, int blocksize); char **transpose_blocks(char *ciphertext, int blocksize, int length); +int isprintable(char *string, int length); #endif /* __CYRPTO_LIB__ */ diff --git a/lib/lib2.c b/lib/lib2.c index f9904b6..2d62305 100644 --- a/lib/lib2.c +++ b/lib/lib2.c @@ -71,20 +71,22 @@ int aes_cbc(char *in, int length_in, char *out, unsigned char *string_key, char AES_KEY key; int number_blocks = length_in / 16; int i, j; + unsigned char debug[16]; unsigned char ciphertext[128+1]; unsigned char tmp_after_aes[128+1]; unsigned char cleartext[128+1]; // set the key and bits + memset(tmp_after_aes, 0, 129); if(encrypt) AES_set_encrypt_key(string_key, 128, &key); else AES_set_decrypt_key(string_key, 128, &key); - memcpy(init_vector, iv, 16); + memcpy(iv, init_vector, 16); // implement cbc mode for(i=0;i 9) + buf[i] = random_number_between(48,57); + else + buf[i] = random_number_between(97,102); + } +} int generate_random_bytes(char *buf, int length_key_bytes) { diff --git a/lib/lib2.h b/lib/lib2.h index 8e1ae98..f3c7e7b 100644 --- a/lib/lib2.h +++ b/lib/lib2.h @@ -21,6 +21,7 @@ int aes_cbc(char *in, int length_in, char *out, unsigned char *string_key, char int valid_pkcs7_padding(const char *in, int length_in, char *unpadded, int blocksize); int aes_ecb(char *in, int length_in, char *out, unsigned char *string_key, int blocksize, int encrypt); +int generate_random_hex(char *buf, int length_key_bytes); int generate_random_bytes(char *buf, int length_key_bytes); int random_number_between(int min, int max); char *encrypt_with_random_bytes(char *toencrypt, int length, int ecb); @@ -34,6 +35,6 @@ int challenge16_encrypt(char *input, char **encrypted, int cbc_mode); void challenge16_decrypt(char *encrypted, int length, int cbc_mode); int challenge12_and_14_oracle(char *attacker_data, int attacker_data_lengthn, char **ciphertext, int prepend_data); int aes_ecb_detect_prepended_data(); - +int aes_cbc_padded(char *in, int length_in, char **out, unsigned char *string_key, char *init_vector, int encrypt); #endif diff --git a/lib/lib4.c b/lib/lib4.c index 1b25ef9..224adf0 100644 --- a/lib/lib4.c +++ b/lib/lib4.c @@ -22,6 +22,126 @@ int aes_ctr_edit(char *ciphertext, int ciphertext_length, int offset, char *newt } +unsigned int left_rotate(int shift, int value) +{ + // TODO make use of the x86 instruction rol, ror + unsigned int ret = value; + unsigned int mask = 0xFFFFFFFF << shift; + ret = ret << shift; + ret |= ((value & mask) >> (32-shift)); + return ret; +} + +void sha1_helper_copy_chunk(char *chunk, int *dest) +{ + int i; + for(i=0;i<16;i++) { + memcpy(&dest[i], &chunk[i], 4); + } +} + +void sha1_hash(char *text, int text_length) +{ + unsigned char *padding; + char *hash; + int padding_len = sha1_padding(text_length, &padding); + + char *to_hash = malloc(text_length + padding_len); + + memcpy(to_hash, text, text_length); + memcpy(&to_hash[text_length], padding, padding_len); + hash_sha1_core(to_hash, (text_length + padding_len), &hash); + int i; + for(i=0;i<64;i++) + printf("%02x", hash[i]); + printf("\n"); +} + +void hash_sha1_core(char *text, int text_length, char **sha1_hash) +{ + *sha1_hash = malloc(20); + int i,j; + unsigned int h0 = 0x67452301; + unsigned int h1 = 0xEFCDAB89; + unsigned int h2 = 0x98BADCFE; + unsigned int h3 = 0x10325476; + unsigned int h4 = 0xC3D2E1F0; + + unsigned int temp; + int chunks = (text_length*8) / 512; + unsigned int w[80]; + unsigned int a,b,c,d,e,f,k; + char *chunk; + + for(i=0;i= 0 && i <= 19) { + f = (b & c) | ((~b) & d); + k = 0x5A827999; + } + else if (i >= 20 && i <= 39) { + f = b ^ c ^ d; + k = 0x6ED9EBA1; + } + else if (i>= 40 && i <= 59) { + f = (b & c) | (b & d) | (c & d); + k = 0x8F1BBCDC; + } + else if (i >= 60 && i <= 79) { + f = b ^ c ^ d; + k = 0xCA62C1D6; + } + + temp = left_rotate(5 ,a); + temp += f + e + k + w[j]; + e = d; + d = c; + c = left_rotate(30, b); + b = a; + a = temp; + + } + + h0 += a; + h1 += b; + h2 += c; + h3 += d; + h4 += e; + } + + // copy h_i into sha_hash + memcpy(*sha1_hash, &h0, 4); + memcpy(&((*sha1_hash)[4]), &h1, 4); + memcpy(&((*sha1_hash)[8]), &h2, 4); + memcpy(&((*sha1_hash)[12]), &h3, 4); + memcpy(&((*sha1_hash)[16]), &h4, 4); +} + +void sha1_set_magic_nr(SHA1Context *sh, unsigned int *magic) +{ + sh->Message_Digest[0] = magic[0]; + sh->Message_Digest[1] = magic[1]; + sh->Message_Digest[2] = magic[2]; + sh->Message_Digest[3] = magic[3]; + sh->Message_Digest[4] = magic[4]; +} + + void sha1_hmac(unsigned int *mac, unsigned char *message, unsigned int msg_len, unsigned char *key, unsigned int key_len) { @@ -47,11 +167,21 @@ int sha1_hmac_verify(unsigned int *mac, unsigned char *msg, unsigned int msg_len sha1_hmac(com_mac, msg, msg_len, key, key_len); + printf("mac of msg is:\n"); + int i; + for(i=0;i<5;i++) + printf("%02x", com_mac[i]); + printf("\n"); + printf("to compate with\n"); + for(i=0;i<5;i++) + printf("%02x", mac[i]); + printf("\n"); + return !memcmp(com_mac, mac, 20); } -int sha1_padding(unsigned long msg_len, char **result) +int sha1_padding(unsigned long msg_len, unsigned char **result) { int i; unsigned int padding_len = 64 - (msg_len % 64); @@ -62,8 +192,7 @@ int sha1_padding(unsigned long msg_len, char **result) memset((*result), 0x00, padding_len); // append 1 - memset(&(*result)[0], 0x80, 1); - //(*result)[0] = 0x80; + (*result)[0] = 0x80; // write the 8 byte msg_len at the end bytewise for(i=0;i<8;i++) { @@ -77,12 +206,67 @@ void sha1_hmac_forge(unsigned int *mac, unsigned char *text, unsigned int text_l unsigned int *sha1_registers) { SHA1Context sh; - SHA1Reset(&sh); + SHA1Reset_Mod(&sh, sha1_registers); - sha1_set_magic_nr(&sh, sha1_registers); SHA1Input(&sh, text, text_len); - SHA1Result(&sh); + SHA1Result_Forged(&sh); memcpy(mac, &(sh.Message_Digest), 20); } + +void md4_prefix_key_mac(uint32_t **mac, unsigned char *text, unsigned int text_len, + unsigned char *key, unsigned int key_len) +{ + char *res = malloc(text_len + key_len); + + memcpy(res, text, text_len); + memcpy(res+text_len, key, key_len); + + MD4(res, (text_len + key_len), mac, NULL); +} + +int md4_prefix_key_verify(uint32_t *mac, unsigned char *text, unsigned int text_len, + unsigned char *key, unsigned int key_len) +{ + uint32_t *hash; + + MD4(text, text_len, &hash, NULL); + printf("computed mac is:\n"); + int i; + for(i=0;i<4;i++) + printf("%02x", hash[i]); + printf("\n"); + return !memcmp(hash, mac, 4*sizeof(uint32_t)); +} + +void md4_prefix_key_forge(uint32_t **mac, unsigned char *text, unsigned int text_len, + unsigned int *md4_registers) +{ + MD4(text, text_len, mac, md4_registers); +} + +uint32_t stringToUint32(char *s){ + uint32_t l; + int i; + l=0; + for(i=0; i<4; i++){ + l = l|(((uint32_t)((unsigned char)s[i]))<<(8*(3-i))); + } + return l; +} + +uint32_t changeEndianness(uint32_t x){ + return ((x & 0xFF) << 24) | ((x & 0xFF00) << 8) | ((x & 0xFF0000) >> 8) | ((x & 0xFF000000) >> 24); +} + +int md4_padding(unsigned long msg_len, unsigned char **result) +{ + int len = sha1_padding(msg_len, result); + int i; + //change endianess + for(i=0;i - +unsigned int left_rotate(int shift, int value); int aes_ctr_edit(char *ciphertext, int ciphertext_length, int offset, char *newtext); +void hash_sha1_core(char *text, int text_length, char **sha1_hash); +void hash_sha1(char *text, int text_length, char **sha1_hash); +void sha1_hash(char *text, int text_length); void sha1_hmac(unsigned int *mac, unsigned char *message, unsigned int msg_len, unsigned char *key, unsigned int key_len); int sha1_hmac_verify(unsigned int *mac, unsigned char *msg, unsigned int msg_len, unsigned char *key, unsigned int key_len); -int sha1_padding(unsigned long msg_len, char **result); +int sha1_padding(unsigned long msg_len, unsigned char **result); void sha1_hmac_forge(unsigned int *mac, unsigned char *text, unsigned int text_len, unsigned int *sha1_registers); +void MD4(char *str, int len, uint32_t **hash, uint32_t *md4_registers); +void md4_prefix_key_mac(uint32_t **mac, unsigned char *text, unsigned int text_len, + unsigned char *key, unsigned int key_len); +int md4_prefix_key_verify(uint32_t *mac, unsigned char *text, unsigned int text_len, + unsigned char *key, unsigned int key_len); +void md4_prefix_key_forge(uint32_t **mac, unsigned char *text, unsigned int text_len, + unsigned int *md4_registers); +int md4_padding(unsigned long msg_len, unsigned char **result); #endif diff --git a/lib/lib5.c b/lib/lib5.c index 1eb25e3..3be330d 100644 --- a/lib/lib5.c +++ b/lib/lib5.c @@ -417,12 +417,6 @@ int rsa_decrpyt(int message, struct rsa_key *private) return modulo((message^private->exponent), private->modulo); } -void die(char *message) -{ - printf("%s\n", message); - exit(1); -} - int rsa_encrypt_bignum(BIGNUM *message, BIGNUM *res, struct rsa_key_bignum *public) { return BN_mod_exp(res, message, public->exponent, public->modulo, ctx); diff --git a/lib/lib5.h b/lib/lib5.h index 43d8165..d30a2c0 100644 --- a/lib/lib5.h +++ b/lib/lib5.h @@ -7,6 +7,7 @@ #include #include #include +#include "util/util.h" struct dh_param { mpz_t A; @@ -90,7 +91,6 @@ void sha1_key_from_dh(struct dh_param *dh, unsigned char *key); void dh_mitm(struct dh_param *dh); int rsa_decrypt_bignum(BIGNUM *message, BIGNUM *res, struct rsa_key_bignum *private); int rsa_encrypt_bignum(BIGNUM *message, BIGNUM *res, struct rsa_key_bignum *public); -void die(char *message); int rsa_decrpyt(int message, struct rsa_key *private); int rsa_encrypt(int message, struct rsa_key *public); int modulo(int a, int b); diff --git a/lib/lib6.c b/lib/lib6.c index 5999e91..85dbd9e 100644 --- a/lib/lib6.c +++ b/lib/lib6.c @@ -4,6 +4,7 @@ #include "lib3.h" #include "lib2.h" #include "lib.h" +#include "util/set.h" #include @@ -31,21 +32,20 @@ int rsa_verify_bignum(BIGNUM *signed_message, BIGNUM *org_message, struct rsa_ke **/ void pkcs1_5_padding(char *message, char *result, unsigned int target_length_byte) { - SHA1Context sha1; + SHA_CTX sha1; char sha1_hash[20]; int i; memset(result, 0xff, target_length_byte); result[0] = 0x00; - result[1] = 0x01; + result[1] = 0x02; result[target_length_byte-21] = 0x00; // TODO ASN.1 things - SHA1Reset(&sha1); - SHA1Input(&sha1, message, strlen(message)); - SHA1Result(&sha1); - memcpy(sha1_hash, &(sha1.Message_Digest), 20); + SHA1_Init(&sha1); + SHA1_Update(&sha1, message, strlen(message)); + SHA1_Final(sha1_hash, &sha1); for(i = 20;i>0;i--) result[target_length_byte-i] = sha1_hash[20-i]; @@ -95,6 +95,9 @@ int shitty_pkcs1_5_padding_verify(char *to_verify, int len, char *message) return 0; } + char buf[(1024/8)*2]; + hex_binary_to_string(to_verify, buf, len); + printf("got:\n%s\n", buf); return 1; } @@ -245,3 +248,204 @@ int rsa_parity_orcale(BIGNUM *message, struct rsa_key_bignum *private) rsa_decrypt_bignum(message, decrypted, private); return BN_is_odd(decrypted); } + +int rsa_bleichenbacher_orcale(BIGNUM *ciphertext, struct rsa_key_bignum *priv) +{ + int ret = 0; + BIGNUM *plaintext = BN_new(); + rsa_decrypt_bignum(ciphertext, plaintext, priv); + char *p = malloc(BN_num_bytes(plaintext)); + BN_bn2bin(plaintext, p); + + if(p[0] == 0x02) + ret = 1; + + free(p); + BN_free(plaintext); + return ret; +} + +int bleichenbacher_prepare(BIGNUM *c_0, struct rsa_key_bignum *public, + struct bb_attack *b) +{ + b->_2a = BN_new(); + b->one = BN_new(); + b->two = BN_new(); + b->three = BN_new(); + b->B = BN_new(); + b->_2B = BN_new(); + b->_3B = BN_new(); + b->c_0 = BN_new(); + BIGNUM *tmp2 = BN_new(); + + BN_set_word(b->one, 1); + BN_set_word(b->two, 2); + BN_set_word(b->three, 3); + BN_copy(b->c_0, c_0); + + unsigned long long k = (BN_num_bytes(public->modulo) - 2) * 8; + BN_set_word(tmp2, k); + BN_mod_exp(b->B, b->two, tmp2, public->modulo, ctx); + BN_mod_mul(b->_3B, b->B, b->three, public->modulo, ctx); + BN_mod_mul(b->_2B, b->B, b->two, public->modulo, ctx); + BN_div(b->_2a, NULL, public->modulo, b->_3B, ctx); + printf("\n2a\n"); + BN_print(out, b->_2a); + printf("\n"); +} + +int bleichenbacher_step_2a(BIGNUM *s_i, struct rsa_key_bignum *public, + struct rsa_key_bignum *private, struct bb_attack *b) +{ + printf("bleichenbacher attack: step 2a\n"); + BIGNUM *new_c = BN_new(); + + // start from 2a = c_0/3B + BN_copy(s_i, b->_2a); + printf("start with s_i:\n"); + BN_print(out, s_i); + + while(1) { + // c_0 * s^e = m_0 * s + BN_mod_exp(new_c, s_i, public->exponent, public->modulo, ctx); + BN_mod_mul(new_c, new_c, b->c_0, public->modulo, ctx); + // asking orcale if this ciphertext has valid pkcs + if(rsa_bleichenbacher_orcale(new_c, private)) { + break; + } + // try next number + BN_mod_add(s_i, s_i, b->one, public->modulo, ctx); + } + printf("\ns_i from step 2a:\n"); + BN_print(out, s_i); +} +/** + * when methods get called, s_i contains s_i-1 + **/ +int bleichenbacher_step_2c(struct interval *m, BIGNUM *s_i, struct rsa_key_bignum *public, + struct rsa_key_bignum *private, struct bb_attack *b) +{ + BIGNUM *r_i = BN_new(); + BIGNUM *r_i_start = BN_new(); + BIGNUM *s_i_1 = BN_new(); + BIGNUM *tmp= BN_new(); + BIGNUM *si_upper = BN_new(); + BIGNUM *si_lower = BN_new(); + BIGNUM *new_c = BN_new(); + + BN_copy(s_i_1, s_i); + // TODO set it here to look if it works for the first step + BN_copy(m->lower, b->_2B); + BN_copy(m->upper, b->_3B); + + BN_mul(tmp, s_i_1, m->upper, ctx); + BN_sub(tmp, tmp, b->_2B); + BN_mul(tmp, tmp, b->two, ctx); + BN_div(r_i_start, NULL, tmp, public->modulo, ctx); + printf("tmp:\n"); + BN_print(out, tmp); + + printf("\nr_i start is:\n"); + BN_print(out, r_i_start); + + printf("\nout out out\n"); + // compute s_i intervall, increment r_i in this loop + while(1) { + BN_mul(tmp, r_i, public->modulo, ctx); + BN_add(si_lower, b->_2B, tmp); + BN_div(si_lower, NULL, si_lower, m->upper, ctx); + BN_add(si_upper, b->_3B, tmp); + BN_div(si_upper, NULL, si_upper, m->lower, ctx); + printf("\nsi_lower\n"); + BN_print(out, si_lower); + printf("\nsi_upper\n"); + BN_print(out, si_upper); + // try all s_i in [si_lower, si_upper] + while(BN_cmp(s_i, si_upper) != 1) { + // for all s_i between [si_lower, si_upper] + BN_mod_exp(tmp, s_i, public->exponent, public->modulo, ctx); + BN_mod_mul(new_c, tmp, b->c_0, public->modulo, ctx); + // try if we get valid pkcs padding + if(rsa_bleichenbacher_orcale(new_c, private)) + goto found_si; + + BN_add(s_i, s_i, b->one); + } + } + + +found_si: + printf("found s_i in step 2c:\n"); + BN_print(out, s_i); +} + +/** + * Narrowing down the solution + **/ + +/** +int bleichenbacher_step_3(BIGNUM *s_i, set_t *m_i1) +{ + struct list *intervall, *head; + // compute m_i from m_i-1 + LIST_TO_END(intervall, head) { + + } + +} +**/ + +BIGNUM *BN_max(BIGNUM *e1, BIGNUM *e2) +{ + if(BN_cmp(e1, e2) == 1) + return e1; + else + return e2; +} + +/** + * returns 1 if the intervall have been merged (one intervall), + * 2 if intevalls not overlapping (two intervalls) + **/ +int iv_merge2(struct interval *left, struct interval *right) +{ + if(!(BN_cmp(left->upper, right->lower) == -1)) { + BN_copy(left->upper, BN_max(left->upper, right->upper)); + return 1; + } + + return 2; +} + +/** + * returns 1 if all three intervalls have merged to one, res in left + * returns 2 if the left + middle has been merged and the right not, res in left + * returns 3 if none have been merged + * retuern 4 if the middle and the right has been merged and left not, res in middle + * + **/ + +int iv_merge3(struct interval *left, struct interval *middle, struct interval *rigth) +{ + if(iv_merge2(left, middle) == 1) { + if (iv_merge2(left, rigth) == 1) + return 1; + else + return 2; + } else { + if(iv_merge2(middle, rigth) == 1) + return 4; + else + return 3; + } + +} + +void iv_printf(struct interval *e1) +{ + printf("lower:"); + BN_print(out, e1->lower); + printf("\nupper:"); + BN_print(out, e1->upper); + printf("\n"); +} diff --git a/lib/lib6.h b/lib/lib6.h index a1cfa15..3923bbf 100644 --- a/lib/lib6.h +++ b/lib/lib6.h @@ -6,6 +6,25 @@ #include "lib3.h" #include "lib2.h" #include "lib.h" +#include "util/doublelinkedlist.h" + + +struct bb_attack { + BIGNUM *_2a; + BIGNUM *B; + BIGNUM *_2B; + BIGNUM *_3B; + BIGNUM *one; + BIGNUM *two; + BIGNUM *three; + BIGNUM *c_0; +}; + +struct interval { + BIGNUM *lower; + BIGNUM *upper; + struct list list; +}; struct dsa_public_params { @@ -43,4 +62,15 @@ void dsa_recover_k_from_repeated_nonce(BIGNUM *mess1_hash, BIGNUM *mess2_hash, void dsa_generate_magic_signature(struct dsa_public_params *pub, struct dsa_per_user_param *priv, BIGNUM *mess_hash); int rsa_parity_orcale(BIGNUM *message, struct rsa_key_bignum *private); +void pkcs1_5_padding(char *message, char *result, unsigned int target_length_byte); +int bleichenbacher_prepare(BIGNUM *c_0, struct rsa_key_bignum *public, struct bb_attack *b); +int bleichenbacher_step_2a(BIGNUM *s_i, struct rsa_key_bignum *public, + struct rsa_key_bignum *private, struct bb_attack *b); +int bleichenbacher_step_2c(struct interval *m, BIGNUM *s_i, struct rsa_key_bignum *public, + struct rsa_key_bignum *privat, struct bb_attack *b); +//int bleichenbacher_step_3(BIGNUM *s_i, set_t *m_i1); +int iv_merge2(struct interval *left, struct interval *right); +int iv_merge3(struct interval *left, struct interval *middle, struct interval *rigth); +int iv_list_insert(struct interval *iv, struct list *list); +void iv_printf(struct interval *e1); #endif /* __LIB_6_H__ */ diff --git a/lib/md4.c b/lib/md4.c new file mode 100644 index 0000000..031e74b --- /dev/null +++ b/lib/md4.c @@ -0,0 +1,251 @@ +/* + * + * Author: George Mossessian + * + * The MD4 hash algorithm, as described in https://tools.ietf.org/html/rfc1320 + */ + +#include +#include +#include +#include + + +typedef struct string{ + char *c; + int len; + char sign; +}string; + +static uint32_t *MD4Digest(uint32_t *w, int len); +static void setMD4Registers(uint32_t AA, uint32_t BB, uint32_t CC, uint32_t DD); +static uint32_t changeEndianness(uint32_t x); +static void resetMD4Registers(void); +static string stringCat(string first, string second); +static string uint32ToString(uint32_t l); +static uint32_t stringToUint32(string s); + +static const char *BASE16 = "0123456789abcdef="; + +#define F(X,Y,Z) (((X)&(Y))|((~(X))&(Z))) +#define G(X,Y,Z) (((X)&(Y))|((X)&(Z))|((Y)&(Z))) +#define H(X,Y,Z) ((X)^(Y)^(Z)) + +#define LEFTROTATE(A,N) ((A)<<(N))|((A)>>(32-(N))) + +#define MD4ROUND1(a,b,c,d,x,s) a += F(b,c,d) + x; a = LEFTROTATE(a, s); +#define MD4ROUND2(a,b,c,d,x,s) a += G(b,c,d) + x + (uint32_t)0x5A827999; a = LEFTROTATE(a, s); +#define MD4ROUND3(a,b,c,d,x,s) a += H(b,c,d) + x + (uint32_t)0x6ED9EBA1; a = LEFTROTATE(a, s); + +static uint32_t A = 0x67452301; +static uint32_t B = 0xefcdab89; +static uint32_t C = 0x98badcfe; +static uint32_t D = 0x10325476; + +string newString(char * c, int t){ + string r; + int i; + if(c!=NULL){ + r.len = (t<=0)?strlen(c):t; + r.c=(char *)malloc(sizeof(char)*(r.len+1)); + for(i=0; i>4)]; + out.c[j++]=BASE16[(in.c[i] & 0x0F)]; + } + out.c[j]='\0'; + return out; +} + + +string uint32ToString(uint32_t l){ + string s = newString(NULL,4); + int i; + for(i=0; i<4; i++){ + s.c[i] = (l >> (8*(3-i))) & 0xFF; + } + return s; +} + +uint32_t stringToUint32(string s){ + uint32_t l; + int i; + l=0; + for(i=0; i<4; i++){ + l = l|(((uint32_t)((unsigned char)s.c[i]))<<(8*(3-i))); + } + return l; +} + +void MD4(char *str, int len, uint32_t **hash, uint32_t *start){ + string m=newString(str, len); + uint32_t *w; + uint64_t mlen=m.len; + unsigned char oneBit = 0x80; + int i, wlen = m.len+2; + + if(!start) { + m=stringCat(m, newString((char *)&oneBit,1)); + + //append 0 ≤ k < 512 bits '0', such that the resulting message length in bits + //is congruent to −64 ≡ 448 (mod 512)4 + i=((56-m.len)%64); + if(i<0) i+=64; + m=stringCat(m,newString(NULL, i)); + + w = malloc(sizeof(uint32_t)*(m.len/4+2)); + + //append length, in bits (hence <<3), least significant word first + for(i=0; i>29) & 0xFFFFFFFF; + + wlen=i; + } + else { + w = malloc(sizeof(uint32_t)*(m.len/4+2)); + for(i=0;i> 8) | ((x & 0xFF000000) >> 24); +} + +void setMD4Registers(uint32_t AA, uint32_t BB, uint32_t CC, uint32_t DD){ + A=AA; + B=BB; + C=CC; + D=DD; +} + +void resetMD4Registers(void){ + setMD4Registers(0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476); +} diff --git a/lib/mt_19937_tempering.txt b/lib/mt_19937_tempering.txt new file mode 100644 index 0000000..dfdda7a --- /dev/null +++ b/lib/mt_19937_tempering.txt @@ -0,0 +1,34 @@ +Why can we reverse the tempering function? + +There are to kinds of operations in the tempering function of the MT: + + 1) Right shift + 2) Left shift with an AND + +To undo the first operation, a simple shift is straight forward. Let's consider +the following example of a 24-bit number + + 0010 1010 1011 1101 1111 0111 y + 0000 0000 0000 0000 0000 1010 1010 1111 0111 1101 11 y >> 18 := N + ^ + orginal string + 0010 1010 1011 1101 1111 1101 y ^ (y>>18) := M + + +On can see, that the first 18 bits of M are the same than y. That's clear, +because we have shifted 18 new 0 into it. But now we also now N completly, since +the last 6 bits are the first 6 of M (N is a shifted version of M). +If you shift less than 24/2 = 12 bits, you have to do the above steps in a +loop, because you cannot determin N completly one step. + +To understand why one can undo the second operation was a bit harder for me. +For me it was the easiest to understand it with the feistel network. + + + y y << 15 + | | + | | + XOR<--------- F <----------- + | | + \_______________________ / + /\______________________ diff --git a/lib/sha1.c b/lib/sha1.c new file mode 100644 index 0000000..5a0b117 --- /dev/null +++ b/lib/sha1.c @@ -0,0 +1,391 @@ +/* + * sha1.c + * + * Copyright (C) 1998, 2009 + * Paul E. Jones + * All Rights Reserved + * + ***************************************************************************** + * $Id: sha1.c 12 2009-06-22 19:34:25Z paulej $ + ***************************************************************************** + * + * Description: + * This file implements the Secure Hashing Standard as defined + * in FIPS PUB 180-1 published April 17, 1995. + * + * The Secure Hashing Standard, which uses the Secure Hashing + * Algorithm (SHA), produces a 160-bit message digest for a + * given data stream. In theory, it is highly improbable that + * two messages will produce the same message digest. Therefore, + * this algorithm can serve as a means of providing a "fingerprint" + * for a message. + * + * Portability Issues: + * SHA-1 is defined in terms of 32-bit "words". This code was + * written with the expectation that the processor has at least + * a 32-bit machine word size. If the machine word size is larger, + * the code should still function properly. One caveat to that + * is that the input functions taking characters and character + * arrays assume that only 8 bits of information are stored in each + * character. + * + * Caveats: + * SHA-1 is designed to work with messages less than 2^64 bits + * long. Although SHA-1 allows a message digest to be generated for + * messages of any number of bits less than 2^64, this + * implementation only works with messages with a length that is a + * multiple of the size of an 8-bit character. + * + */ + +#include "sha1.h" + +/* + * Define the circular shift macro + */ +#define SHA1CircularShift(bits,word) \ + ((((word) << (bits)) & 0xFFFFFFFF) | \ + ((word) >> (32-(bits)))) + +/* Function prototypes */ +void SHA1ProcessMessageBlock(SHA1Context *); +void SHA1PadMessage(SHA1Context *); + +/* + * SHA1Reset + * + * Description: + * This function will initialize the SHA1Context in preparation + * for computing a new message digest. + * + * Parameters: + * context: [in/out] + * The context to reset. + * + * Returns: + * Nothing. + * + * Comments: + * + */ +void SHA1Reset(SHA1Context *context) +{ + context->Length_Low = 0; + context->Length_High = 0; + context->Message_Block_Index = 0; + + context->Message_Digest[0] = 0x67452301; + context->Message_Digest[1] = 0xEFCDAB89; + context->Message_Digest[2] = 0x98BADCFE; + context->Message_Digest[3] = 0x10325476; + context->Message_Digest[4] = 0xC3D2E1F0; + + context->Computed = 0; + context->Corrupted = 0; +} + +void SHA1Reset_Mod(SHA1Context *context, unsigned int *init) +{ + context->Length_Low = 0; + context->Length_High = 0; + context->Message_Block_Index = 0; + + context->Message_Digest[0] = init[0]; + context->Message_Digest[1] = init[1]; + context->Message_Digest[2] = init[2]; + context->Message_Digest[3] = init[3]; + context->Message_Digest[4] = init[4]; + + context->Computed = 0; + context->Corrupted = 0; +} +/* + * SHA1Result + * + * Description: + * This function will return the 160-bit message digest into the + * Message_Digest array within the SHA1Context provided + * + * Parameters: + * context: [in/out] + * The context to use to calculate the SHA-1 hash. + * + * Returns: + * 1 if successful, 0 if it failed. + * + * Comments: + * + */ +int SHA1Result(SHA1Context *context) +{ + + if (context->Corrupted) { + return 0; + } + + if (!context->Computed) { + SHA1PadMessage(context); + context->Computed = 1; + } + + return 1; +} + +int SHA1Result_Forged(SHA1Context *context) +{ + if (context->Corrupted) { + return 0; + } + + if (!context->Computed) { + // do not pad forged extension + // we added the padding ourselves + context->Computed = 1; + } + + return 1; +} + +/* + * SHA1Input + * + * Description: + * This function accepts an array of octets as the next portion of + * the message. + * + * Parameters: + * context: [in/out] + * The SHA-1 context to update + * message_array: [in] + * An array of characters representing the next portion of the + * message. + * length: [in] + * The length of the message in message_array + * + * Returns: + * Nothing. + * + * Comments: + * + */ +void SHA1Input(SHA1Context *context, const unsigned char *message_array, unsigned length) +{ + if (!length) { + return; + } + + if (context->Computed || context->Corrupted) { + context->Corrupted = 1; + return; + } + + while(length-- && !context->Corrupted) { + context->Message_Block[context->Message_Block_Index++] = (*message_array & 0xFF); + + context->Length_Low += 8; + /* Force it to 32 bits */ + context->Length_Low &= 0xFFFFFFFF; + if (context->Length_Low == 0) { + context->Length_High++; + /* Force it to 32 bits */ + context->Length_High &= 0xFFFFFFFF; + if (context->Length_High == 0) { + /* Message is too long */ + context->Corrupted = 1; + } + } + + if (context->Message_Block_Index == 64) { + SHA1ProcessMessageBlock(context); + } + + message_array++; + } +// printf("\n"); +} + +/* + * SHA1ProcessMessageBlock + * + * Description: + * This function will process the next 512 bits of the message + * stored in the Message_Block array. + * + * Parameters: + * None. + * + * Returns: + * Nothing. + * + * Comments: + * Many of the variable names in the SHAContext, especially the + * single character names, were used because those were the names + * used in the publication. + * + * + */ +void SHA1ProcessMessageBlock(SHA1Context *context) +{ + const unsigned K[] = /* Constants defined in SHA-1 */ + { + 0x5A827999, + 0x6ED9EBA1, + 0x8F1BBCDC, + 0xCA62C1D6 + }; + int t; /* Loop counter */ + unsigned temp; /* Temporary word value */ + unsigned W[80]; /* Word sequence */ + unsigned A, B, C, D, E; /* Word buffers */ + + /* + * Initialize the first 16 words in the array W + */ + for(t = 0; t < 16; t++) + { + W[t] = ((unsigned) context->Message_Block[t * 4]) << 24; + W[t] |= ((unsigned) context->Message_Block[t * 4 + 1]) << 16; + W[t] |= ((unsigned) context->Message_Block[t * 4 + 2]) << 8; + W[t] |= ((unsigned) context->Message_Block[t * 4 + 3]); + } + + for(t = 16; t < 80; t++) + { + W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]); + } + + A = context->Message_Digest[0]; + B = context->Message_Digest[1]; + C = context->Message_Digest[2]; + D = context->Message_Digest[3]; + E = context->Message_Digest[4]; + + for(t = 0; t < 20; t++) + { + temp = SHA1CircularShift(5,A) + + ((B & C) | ((~B) & D)) + E + W[t] + K[0]; + temp &= 0xFFFFFFFF; + E = D; + D = C; + C = SHA1CircularShift(30,B); + B = A; + A = temp; + } + + for(t = 20; t < 40; t++) + { + temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1]; + temp &= 0xFFFFFFFF; + E = D; + D = C; + C = SHA1CircularShift(30,B); + B = A; + A = temp; + } + + for(t = 40; t < 60; t++) + { + temp = SHA1CircularShift(5,A) + + ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2]; + temp &= 0xFFFFFFFF; + E = D; + D = C; + C = SHA1CircularShift(30,B); + B = A; + A = temp; + } + + for(t = 60; t < 80; t++) + { + temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3]; + temp &= 0xFFFFFFFF; + E = D; + D = C; + C = SHA1CircularShift(30,B); + B = A; + A = temp; + } + + context->Message_Digest[0] = + (context->Message_Digest[0] + A) & 0xFFFFFFFF; + context->Message_Digest[1] = + (context->Message_Digest[1] + B) & 0xFFFFFFFF; + context->Message_Digest[2] = + (context->Message_Digest[2] + C) & 0xFFFFFFFF; + context->Message_Digest[3] = + (context->Message_Digest[3] + D) & 0xFFFFFFFF; + context->Message_Digest[4] = + (context->Message_Digest[4] + E) & 0xFFFFFFFF; + + context->Message_Block_Index = 0; +} + +/* + * SHA1PadMessage + * + * Description: + * According to the standard, the message must be padded to an even + * 512 bits. The first padding bit must be a '1'. The last 64 + * bits represent the length of the original message. All bits in + * between should be 0. This function will pad the message + * according to those rules by filling the Message_Block array + * accordingly. It will also call SHA1ProcessMessageBlock() + * appropriately. When it returns, it can be assumed that the + * message digest has been computed. + * + * Parameters: + * context: [in/out] + * The context to pad + * + * Returns: + * Nothing. + * + * Comments: + * + */ +void SHA1PadMessage(SHA1Context *context) +{ + /* + * Check to see if the current message block is too small to hold + * the initial padding bits and length. If so, we will pad the + * block, process it, and then continue padding into a second + * block. + */ + if (context->Message_Block_Index > 55) + { + context->Message_Block[context->Message_Block_Index++] = 0x80; + while(context->Message_Block_Index < 64) + { + context->Message_Block[context->Message_Block_Index++] = 0; + } + + SHA1ProcessMessageBlock(context); + + while(context->Message_Block_Index < 56) + { + context->Message_Block[context->Message_Block_Index++] = 0; + } + } + else + { + context->Message_Block[context->Message_Block_Index++] = 0x80; + while(context->Message_Block_Index < 56) + { + context->Message_Block[context->Message_Block_Index++] = 0; + } + } + + /* + * Store the message length as the last 8 octets + */ + context->Message_Block[56] = (context->Length_High >> 24) & 0xFF; + context->Message_Block[57] = (context->Length_High >> 16) & 0xFF; + context->Message_Block[58] = (context->Length_High >> 8) & 0xFF; + context->Message_Block[59] = (context->Length_High) & 0xFF; + context->Message_Block[60] = (context->Length_Low >> 24) & 0xFF; + context->Message_Block[61] = (context->Length_Low >> 16) & 0xFF; + context->Message_Block[62] = (context->Length_Low >> 8) & 0xFF; + context->Message_Block[63] = (context->Length_Low) & 0xFF; + SHA1ProcessMessageBlock(context); +} + diff --git a/lib/sha1.h b/lib/sha1.h new file mode 100644 index 0000000..27f98d2 --- /dev/null +++ b/lib/sha1.h @@ -0,0 +1,56 @@ +/* + * sha1.h + * + * Copyright (C) 1998, 2009 + * Paul E. Jones + * All Rights Reserved + * + ***************************************************************************** + * $Id: sha1.h 12 2009-06-22 19:34:25Z paulej $ + ***************************************************************************** + * + * Description: + * This class implements the Secure Hashing Standard as defined + * in FIPS PUB 180-1 published April 17, 1995. + * + * Many of the variable names in the SHA1Context, especially the + * single character names, were used because those were the names + * used in the publication. + * + * Please read the file sha1.c for more information. + * + */ + +#ifndef _SHA1_H_ +#define _SHA1_H_ +#include +/* + * This structure will hold context information for the hashing + * operation + */ +typedef struct SHA1Context +{ + unsigned Message_Digest[5]; /* Message Digest (output) */ + + unsigned Length_Low; /* Message length in bits */ + unsigned Length_High; /* Message length in bits */ + + unsigned char Message_Block[64]; /* 512-bit message blocks */ + int Message_Block_Index; /* Index into message block array */ + + int Computed; /* Is the digest computed? */ + int Corrupted; /* Is the message digest corruped? */ +} SHA1Context; + +/* + * Function Prototypes + */ +void SHA1Reset(SHA1Context *); +void SHA1Reset_Mod(SHA1Context *context, unsigned int *init); +int SHA1Result(SHA1Context *); +int SHA1Result_Forged(SHA1Context *); +void SHA1Input( SHA1Context *, + const unsigned char *, + unsigned); + +#endif diff --git a/lib/test.c b/lib/test.c new file mode 100644 index 0000000..36f3b1c --- /dev/null +++ b/lib/test.c @@ -0,0 +1,24 @@ +#include + +int main() +{ + mpz_t a, b, m, r; + + mpz_init_set_str(a, "fafbababcabfebdefbed344523334456a6b4a5c486ac4e86f4684", 16); + mpz_init_set_str(b, "2351399303373464486466122544523690094744" + "975233415544072992656881240319", 0); + mpz_init(m); + mpz_ui_pow_ui(m, 10, 40); + + mpz_init(r); + mpz_powm(r, a, b, m); + + gmp_printf("%Zd\n", r); /* ...16808958343740453059 */ + + mpz_clear(a); + mpz_clear(b); + mpz_clear(m); + mpz_clear(r); + + return 0; +} diff --git a/lib/test_list.c b/lib/test_list.c new file mode 100644 index 0000000..7e72fb8 --- /dev/null +++ b/lib/test_list.c @@ -0,0 +1,51 @@ +#include "doublelinkedlist.h" +#include +#include + + +struct in { + int low; + int max; + struct list next; +}; + +int main() +{ + struct in tmp; + struct in tmp2; + struct in tmp3; + struct in tmp4; + struct list *iter, *head; + + tmp.low = 1; + tmp.max = 3; + tmp2.low = 5; + tmp2.max = 9; + tmp3.low = 14; + tmp3.max = 16; + tmp4.low = 23; + tmp4.max = 35; + + LIST_INIT(&tmp.next); + LIST_INIT(&tmp2.next); + LIST_INIT(&tmp3.next); + LIST_INIT(&tmp4.next); + + list_insert_after(&tmp.next, &tmp2.next); + list_insert_after(&tmp2.next, &tmp3.next); + list_insert_after(&tmp3.next, &tmp4.next); + + head = &tmp2.next; + + LIST_TO_END(iter, head) { + struct in *i = CONTAINER_OF(iter, struct in, next); + printf("low: %i, max: %i\n", i->low, i->max); + } + + list_delete(&tmp4.next); + LIST_TO_END(iter, head) { + struct in *i = CONTAINER_OF(iter, struct in, next); + printf("low: %i, max: %i\n", i->low, i->max); + } + +} diff --git a/lib/util/a.out b/lib/util/a.out new file mode 100755 index 0000000..2457844 Binary files /dev/null and b/lib/util/a.out differ diff --git a/lib/util/circulardoublelinkedlist.h b/lib/util/circulardoublelinkedlist.h new file mode 100644 index 0000000..3e5c524 --- /dev/null +++ b/lib/util/circulardoublelinkedlist.h @@ -0,0 +1,54 @@ +#ifndef __CIRCULARLIST__ +#define __CIRCULARLIST__ + +/** + * ciruclar double linked list implementation + * + **/ +#include "util.h" +#include + +struct circular_list { + struct circular_list *next; + struct circular_list *prev; +}; + +#define CIRCULARLIST_INIT(name) do { (name)->next = (name); (name)->prev = (name); } while(0); + +static int inline __circular_list_insert(struct circular_list *prev, struct circular_list *new, struct circular_list *next) +{ + prev->next = new; + new->prev = prev; + new->next = next; + next->prev = new; +} + +static int inline circular_list_insert_after(struct circular_list *list, struct circular_list *new_elem) +{ + return __circular_list_insert(list, new_elem, list->next); +} + +static int inline circular_list_insert_before(struct circular_list *list, struct circular_list *new_elem) +{ + return __circular_list_insert(list->prev, new_elem, list); +} + +static void inline __circular_list_delete(struct circular_list *prev, struct circular_list *elem, struct circular_list *next) +{ + prev->next = next; + next->prev = prev; + elem->next = elem; + elem->prev = elem; +} +static void inline circular_list_delete(struct circular_list *elem) +{ + __circular_list_delete(elem->prev, elem, elem->next); +} + +#define circular_list_get_prev(elem) (elem)->prev +#define circular_list_get_next(elem) (elem)->next + +#define CIRCULARLIST_FOR_EACH(pos, head) for(pos = head->next; pos != head; pos = pos->next) +#define CONTAINER_OF(ptr, type, member) ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))) + +#endif diff --git a/lib/util/doublelinkedlist.h b/lib/util/doublelinkedlist.h new file mode 100644 index 0000000..460d799 --- /dev/null +++ b/lib/util/doublelinkedlist.h @@ -0,0 +1,58 @@ +#ifndef __LIST__ +#define __LIST__ + +/** + * double linked list implementation + * + **/ + +#include + +struct list { + struct list *next; + struct list *prev; +}; + +#define LIST_INIT(name) do { (name)->next = NULL; (name)->prev = NULL; } while(0); + +static int inline __list_insert(struct list *prev, struct list *new, struct list *next) +{ + if(prev != NULL) + prev->next = new; + new->prev = prev; + new->next = next; + if(next != NULL) + next->prev = new; +} + +static int inline list_insert_after(struct list *list, struct list *new_elem) +{ + return __list_insert(list, new_elem, list->next); +} + +static int inline list_insert_before(struct list *list, struct list *new_elem) +{ + return __list_insert(list->prev, new_elem, list); +} + +static void inline __list_delete(struct list *prev, struct list *elem, struct list *next) +{ + if(prev != NULL) + prev->next = next; + if(next != NULL) + next->prev = prev; + elem->next = elem; + elem->prev = elem; +} +static void inline list_delete(struct list *elem) +{ + __list_delete(elem->prev, elem, elem->next); +} + +#define list_get_prev(elem) (elem)->prev +#define list_get_next(elem) (elem)->next + +#define LIST_TO_END(pos, head) for(pos = head; pos != NULL; pos = pos->next) +#define CONTAINER_OF(ptr, type, member) ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))) + +#endif diff --git a/lib/util/hashtable.h b/lib/util/hashtable.h new file mode 100644 index 0000000..57ac495 --- /dev/null +++ b/lib/util/hashtable.h @@ -0,0 +1,159 @@ +#ifndef __HASHMAP__ +#define __HASHMAP__ + +#include +#include +#include "circulardoublelinkedlist.h" +#include "util.h" + +struct ht_item { + char *hash; + void *data; + unsigned int data_length; + struct list list; +}; + +struct hashtable { + struct ht_item **begin; + unsigned int length; + unsigned int hash_length; + void (*hash_function)(void *data, unsigned int data_length, char *res); +}; + + +int __ht_init(struct hashtable *ht, unsigned int number_elem, + unsigned int hash_length, void (*func)(void *data, + unsigned int data_length, char *res)) +{ + ht->begin = xmalloc(sizeof(struct ht_item)*number_elem); + ht->length = number_elem; + ht->hash_length = hash_length; + ht->hash_function = func; +} + +int ht_destroy(struct hashtable *ht) +{ + free(ht->begin); +} + +void compute_hash_sha1(void *data, unsigned int data_length, char *res) +{ + SHA_CTX sha1; + + SHA1_Init(&sha1); + SHA1_Update(&sha1, data, data_length); + SHA1_Final(res, &sha1); + +} + +int ht_init_sha1(struct hashtable *ht) +{ + __ht_init(ht, 300, 20, compute_hash_sha1); +} + +void *ht_is_in_list(struct list *list, char *hash, int hash_length) +{ + struct list *head, *iter; + struct ht_item *res = NULL; + + head = list; + res = CONTAINER_OF(head, struct ht_item, list); + if(memcmp(res->hash, hash, hash_length) == 0) + return res->data; + + CIRCULARLIST_FOR_EACH(iter,head) { + res = CONTAINER_OF(iter, struct ht_item, list); + if(memcmp(res->hash, hash, hash_length) == 0) + return res->data; + } + + return NULL; +} + +void ht_add(struct hashtable *ht, void *data, unsigned int data_length, + void *key, unsigned int key_length) +{ + unsigned long index; + struct ht_item *new_elem = xmalloc(sizeof(struct ht_item)); + new_elem->hash = xmalloc(ht->hash_length); + new_elem->data = xmalloc(data_length); + + memcpy(new_elem->data, data, data_length); + new_elem->data_length = data_length; + CIRCULARLIST_INIT(&new_elem->list); + + ht->hash_function(key, key_length, new_elem->hash); + memcpy(&index, new_elem->hash, sizeof(unsigned long)); + index = index % ht->length; + + if(ht->begin[index] == NULL) { + ht->begin[index] = new_elem; + return; + } + + if(ht_is_in_list(&(ht->begin[index]->list), new_elem->hash, + ht->hash_length) == NULL) { + list_insert_after(&(ht->begin[index]->list), &new_elem->list); + return; + } +} + +void *ht_get(struct hashtable *ht, void *key, unsigned int key_length) +{ + char *hash = xmalloc(ht->hash_length); + unsigned long index; + + ht->hash_function(key, key_length, hash); + memcpy(&index, hash, sizeof(unsigned long)); + index = index % ht->length; + + struct ht_item *res = ht_is_in_list(&(ht->begin[index]->list), hash, ht->hash_length); + free(hash); + return res; +} + +void __ht_delete_item(struct ht_item *delete) +{ + free(delete->hash); + free(delete->data); + free(delete); +} + +void ht_list_delete(struct list *list, unsigned long index, char *hash, + unsigned int hash_length) +{ + struct list *head, *iter; + struct ht_item *res; + + head = list; + res = CONTAINER_OF(head, struct ht_item, list); + if (memcmp(res->hash, hash, hash_length) == 0) { + list_delete(head); + __ht_delete_item(res); + return; + } + + CIRCULARLIST_FOR_EACH(iter, head) { + res = CONTAINER_OF(iter, struct ht_item, list); + if (memcmp(res->hash, hash, hash_length) == 0) { + list_delete(iter); + __ht_delete_item(res); + return; + } + } +} + +void ht_delete(struct hashtable *ht, void *key, unsigned int key_length) +{ + char *hash = xmalloc(ht->hash_length); + unsigned long index; + + ht->hash_function(key, key_length, hash); + memcpy(&index, hash, sizeof(unsigned long)); + index = index % ht->length; + + ht_list_delete(&ht->begin[index]->list, index, hash, ht->hash_length); + free(hash); +} + +#endif diff --git a/lib/util/hashtable.h.gch b/lib/util/hashtable.h.gch new file mode 100644 index 0000000..cf2b3d2 Binary files /dev/null and b/lib/util/hashtable.h.gch differ diff --git a/lib/util/set.h b/lib/util/set.h new file mode 100644 index 0000000..bd05351 --- /dev/null +++ b/lib/util/set.h @@ -0,0 +1,39 @@ +#ifndef __SET_H__ +#define __SET_H__ +#include +#include "hashtable.h" + +/** + * implementation of a set based on a hashtable implementation + * + **/ + +typedef struct hashtable set_t; + +void set_init(set_t *set) +{ + ht_init_sha1(set); +} + + +void set_insert(set_t *set, void *data, unsigned int data_length) +{ + ht_add(set, data, data_length, data, data_length); +} + +unsigned int set_is_in_set(set_t *set, void *data, unsigned int data_length) +{ + if(ht_get(set, data, data_length) == NULL) + return 0; + else + return 1; +} + +void set_delete(set_t *set, void *data, unsigned int data_length) +{ + ht_delete(set, data, data_length); +} + +#define SET_FOR_EACH + +#endif diff --git a/lib/util/set.h.gch b/lib/util/set.h.gch new file mode 100644 index 0000000..2c1b1fe Binary files /dev/null and b/lib/util/set.h.gch differ diff --git a/lib/util/test_hash.c b/lib/util/test_hash.c new file mode 100644 index 0000000..19d2aae --- /dev/null +++ b/lib/util/test_hash.c @@ -0,0 +1,48 @@ +#include "hashtable.h" +#include "set.h" + + +int main() +{ + int i; + struct hashtable ht; + + char *msg = malloc(100); + memcpy(msg, "Hallo dies ist meine Message\n", 20); + char *key = malloc(20); + + ht_init_sha1(&ht); + key[1] = '\n'; + for(i=0;i<156;i++) { + key[0] = i; + msg[0] = i; + ht_add(&ht, msg, strlen(msg), key, strlen(key)); + } + + + ht_delete(&ht, key, strlen(key)); + char *ret = ht_get(&ht, key, strlen(key)); + if(ret != NULL) + printf("uuh das sollte eigtl nicht mehr da sein\n"); + + key[0] = 'a' + 3; + ret = ht_get(&ht, key, strlen(key)); + if(ret == NULL) + printf("did not found data\n"); + + printf("message is: %s\n", msg); + printf("got data from ht: %s\n", ret); + + + set_t t; + + set_init(&t); + set_insert(&t, msg, strlen(msg)); + if(set_is_in_set(&t, msg, strlen(msg)) == 1) + printf("im set, alles gut\n"); + + set_delete(&t, msg, strlen(msg)); + if(set_is_in_set(&t, msg, strlen(msg)) == 0) + printf("nicht merg im set, alles gut\n"); + +} diff --git a/lib/util/util.c b/lib/util/util.c new file mode 100644 index 0000000..dd06869 --- /dev/null +++ b/lib/util/util.c @@ -0,0 +1,25 @@ +#include "util.h" + +void *die(char *text) +{ + printf("dieing: %s\n", text); + exit(1); +} + +void *xmalloc(unsigned int size) +{ + void *mem = malloc(size); + if(mem == NULL) + die("out of memory"); + else + return mem; +} + +void *xrealloc(void *data, unsigned int size) +{ + void *mem = realloc(data, size); + if(mem == NULL) + die("out of memory"); + else + return mem; +} diff --git a/lib/util/util.h b/lib/util/util.h new file mode 100644 index 0000000..b998ef8 --- /dev/null +++ b/lib/util/util.h @@ -0,0 +1,10 @@ +#ifndef __UTIL_H__ +#define __UTIL_H__ + +#include +#include + +void *die(char *text); +void *xmalloc(unsigned int size); +void *xrealloc(void *data, unsigned int size); +#endif -- cgit v1.2.3-70-g09d2