diff options
author | Jussi Kivilinna <jussi.kivilinna@iki.fi> | 2013-11-04 13:32:49 +0200 |
---|---|---|
committer | Jussi Kivilinna <jussi.kivilinna@iki.fi> | 2013-11-06 19:22:59 +0200 |
commit | 8e1c0f9b894c39b6554c544208dc000682f520c7 (patch) | |
tree | d6c1246b129ff851e88a2b0ab5269054426ddec7 /cipher/blowfish.c | |
parent | 2590a5df6f5fc884614c8c379324027d2d61b9b5 (diff) | |
download | libgcrypt-8e1c0f9b894c39b6554c544208dc000682f520c7.tar.gz |
Optimize Blowfish weak key check
* cipher/blowfish.c (hashset_elem, val_to_hidx, add_val): New.
(do_bf_setkey): Use faster algorithm for detecting weak keys.
(bf_setkey): Move stack burning to do_bf_setkey.
--
Patch optimizes the weak key check for Blowfish. Instead of iterating through
sbox-tables for duplicates, insert values to hash-set and detect collisions.
Old check code was taking slightly longer time than the actual key setup of
Blowfish, which by itself is already quite slow.
After:
$ tests/benchmark --cipher-with-keysetup --cipher-repetitions 10 cipher blowfish
Running each test 10 times.
ECB/Stream CBC CFB OFB CTR CCM
--------------- --------------- --------------- --------------- --------------- ---------------
BLOWFISH 410ms 440ms 430ms 370ms 440ms 370ms 430ms 440ms 370ms 370ms - -
Before:
$ tests/benchmark --cipher-with-keysetup --cipher-repetitions 10 cipher blowfish
Running each test 10 times.
ECB/Stream CBC CFB OFB CTR CCM
--------------- --------------- --------------- --------------- --------------- ---------------
BLOWFISH 780ms 770ms 780ms 730ms 780ms 730ms 780ms 790ms 720ms 730ms - -
Without key-setup:
$ tests/benchmark --cipher-repetitions 10 cipher blowfish
Running each test 10 times.
ECB/Stream CBC CFB OFB CTR CCM
--------------- --------------- --------------- --------------- --------------- ---------------
BLOWFISH 70ms 70ms 80ms 30ms 80ms 30ms 80ms 90ms 20ms 30ms - -
Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
Diffstat (limited to 'cipher/blowfish.c')
-rw-r--r-- | cipher/blowfish.c | 101 |
1 files changed, 90 insertions, 11 deletions
diff --git a/cipher/blowfish.c b/cipher/blowfish.c index 84fa9d3d..4665a1dd 100644 --- a/cipher/blowfish.c +++ b/cipher/blowfish.c @@ -860,11 +860,67 @@ selftest(void) } +struct hashset_elem { + u32 val; + short nidx; + char used; +}; + +static inline byte +val_to_hidx(u32 val) +{ + /* bf sboxes are quite random already. */ + return (val >> 24) ^ (val >> 16) ^ (val >> 8) ^ val; +} + +static inline int +add_val(struct hashset_elem hset[256], u32 val, int *midx, + struct hashset_elem *mpool) +{ + struct hashset_elem *elem; + byte hidx; + + hidx = val_to_hidx(val); + elem = &hset[hidx]; + + /* Check if first is in use. */ + if (elem->used == 0) + { + elem->val = val; + elem->nidx = -1; + elem->used = 1; + return 0; + } + + /* Check if first matches. */ + if (elem->val == val) + return 1; + + for (; elem->nidx >= 0; elem = &mpool[elem->nidx]) + { + /* Check if elem matches. */ + if (elem->val == val) + return 1; + } + + elem->nidx = (*midx)++; + elem = &mpool[elem->nidx]; + + elem->val = val; + elem->nidx = -1; + elem->used = 1; + + return 0; +} static gcry_err_code_t do_bf_setkey (BLOWFISH_context *c, const byte *key, unsigned keylen) { - int i, j; + struct hashset_elem mempool[4 * 255]; /* Enough entries for the worst case. */ + struct hashset_elem hset[4][256]; + int memidx = 0; + int weak = 0; + int i, j, ret; u32 data, datal, datar; static int initialized; static const char *selftest_failed; @@ -879,6 +935,8 @@ do_bf_setkey (BLOWFISH_context *c, const byte *key, unsigned keylen) if( selftest_failed ) return GPG_ERR_SELFTEST_FAILED; + memset(hset, 0, sizeof(hset)); + for(i=0; i < BLOWFISH_ROUNDS+2; i++ ) c->p[i] = ps[i]; for(i=0; i < 256; i++ ) @@ -911,38 +969,60 @@ do_bf_setkey (BLOWFISH_context *c, const byte *key, unsigned keylen) do_encrypt( c, &datal, &datar ); c->s0[i] = datal; c->s0[i+1] = datar; + + /* Add values to hashset, detect duplicates (weak keys). */ + ret = add_val (hset[0], datal, &memidx, mempool); + weak = ret ? 1 : weak; + ret = add_val (hset[0], datar, &memidx, mempool); + weak = ret ? 1 : weak; } for(i=0; i < 256; i += 2 ) { do_encrypt( c, &datal, &datar ); c->s1[i] = datal; c->s1[i+1] = datar; + + /* Add values to hashset, detect duplicates (weak keys). */ + ret = add_val (hset[1], datal, &memidx, mempool); + weak = ret ? 1 : weak; + ret = add_val (hset[1], datar, &memidx, mempool); + weak = ret ? 1 : weak; } for(i=0; i < 256; i += 2 ) { do_encrypt( c, &datal, &datar ); c->s2[i] = datal; c->s2[i+1] = datar; + + /* Add values to hashset, detect duplicates (weak keys). */ + ret = add_val (hset[2], datal, &memidx, mempool); + weak = ret ? 1 : weak; + ret = add_val (hset[2], datar, &memidx, mempool); + weak = ret ? 1 : weak; } for(i=0; i < 256; i += 2 ) { do_encrypt( c, &datal, &datar ); c->s3[i] = datal; c->s3[i+1] = datar; + + /* Add values to hashset, detect duplicates (weak keys). */ + ret = add_val (hset[3], datal, &memidx, mempool); + weak = ret ? 1 : weak; + ret = add_val (hset[3], datar, &memidx, mempool); + weak = ret ? 1 : weak; } + /* Clear stack. */ + wipememory(hset, sizeof(hset)); + wipememory(mempool, sizeof(mempool[0]) * memidx); + + _gcry_burn_stack (64); /* Check for weak key. A weak key is a key in which a value in the P-array (here c) occurs more than once per table. */ - for(i=0; i < 255; i++ ) - { - for( j=i+1; j < 256; j++) - { - if( (c->s0[i] == c->s0[j]) || (c->s1[i] == c->s1[j]) || - (c->s2[i] == c->s2[j]) || (c->s3[i] == c->s3[j]) ) - return GPG_ERR_WEAK_KEY; - } - } + if (weak) + return GPG_ERR_WEAK_KEY; return GPG_ERR_NO_ERROR; } @@ -953,7 +1033,6 @@ bf_setkey (void *context, const byte *key, unsigned keylen) { BLOWFISH_context *c = (BLOWFISH_context *) context; gcry_err_code_t rc = do_bf_setkey (c, key, keylen); - _gcry_burn_stack (64); return rc; } |