From 197dc467dec28a04c3b2f30da7cef122dfbb13e9 Mon Sep 17 00:00:00 2001 From: lloyd Date: Wed, 1 Jan 2014 21:20:55 +0000 Subject: Shuffle things around. Add NIST X.509 test to build. --- lib/constructs/aont/info.txt | 8 + lib/constructs/aont/package.cpp | 120 +++++++++++ lib/constructs/aont/package.h | 44 +++++ lib/constructs/cryptobox/cryptobox.cpp | 163 +++++++++++++++ lib/constructs/cryptobox/cryptobox.h | 55 ++++++ lib/constructs/cryptobox/info.txt | 13 ++ lib/constructs/cryptobox_psk/cryptobox_psk.cpp | 134 +++++++++++++ lib/constructs/cryptobox_psk/cryptobox_psk.h | 47 +++++ lib/constructs/cryptobox_psk/info.txt | 10 + lib/constructs/fpe_fe1/fpe_fe1.cpp | 193 ++++++++++++++++++ lib/constructs/fpe_fe1/fpe_fe1.h | 44 +++++ lib/constructs/fpe_fe1/info.txt | 7 + lib/constructs/rfc3394/info.txt | 1 + lib/constructs/rfc3394/rfc3394.cpp | 122 ++++++++++++ lib/constructs/rfc3394/rfc3394.h | 45 +++++ lib/constructs/srp6/info.txt | 7 + lib/constructs/srp6/srp6.cpp | 163 +++++++++++++++ lib/constructs/srp6/srp6.h | 97 +++++++++ lib/constructs/srp6/srp6_files.cpp | 69 +++++++ lib/constructs/srp6/srp6_files.h | 53 +++++ lib/constructs/tss/info.txt | 8 + lib/constructs/tss/tss.cpp | 262 +++++++++++++++++++++++++ lib/constructs/tss/tss.h | 76 +++++++ 23 files changed, 1741 insertions(+) create mode 100644 lib/constructs/aont/info.txt create mode 100644 lib/constructs/aont/package.cpp create mode 100644 lib/constructs/aont/package.h create mode 100644 lib/constructs/cryptobox/cryptobox.cpp create mode 100644 lib/constructs/cryptobox/cryptobox.h create mode 100644 lib/constructs/cryptobox/info.txt create mode 100644 lib/constructs/cryptobox_psk/cryptobox_psk.cpp create mode 100644 lib/constructs/cryptobox_psk/cryptobox_psk.h create mode 100644 lib/constructs/cryptobox_psk/info.txt create mode 100644 lib/constructs/fpe_fe1/fpe_fe1.cpp create mode 100644 lib/constructs/fpe_fe1/fpe_fe1.h create mode 100644 lib/constructs/fpe_fe1/info.txt create mode 100644 lib/constructs/rfc3394/info.txt create mode 100644 lib/constructs/rfc3394/rfc3394.cpp create mode 100644 lib/constructs/rfc3394/rfc3394.h create mode 100644 lib/constructs/srp6/info.txt create mode 100644 lib/constructs/srp6/srp6.cpp create mode 100644 lib/constructs/srp6/srp6.h create mode 100644 lib/constructs/srp6/srp6_files.cpp create mode 100644 lib/constructs/srp6/srp6_files.h create mode 100644 lib/constructs/tss/info.txt create mode 100644 lib/constructs/tss/tss.cpp create mode 100644 lib/constructs/tss/tss.h (limited to 'lib/constructs') diff --git a/lib/constructs/aont/info.txt b/lib/constructs/aont/info.txt new file mode 100644 index 000000000..fb66d4129 --- /dev/null +++ b/lib/constructs/aont/info.txt @@ -0,0 +1,8 @@ +define PACKAGE_TRANSFORM 20131128 + + +block +ctr +rng +filters + diff --git a/lib/constructs/aont/package.cpp b/lib/constructs/aont/package.cpp new file mode 100644 index 000000000..1adee90e8 --- /dev/null +++ b/lib/constructs/aont/package.cpp @@ -0,0 +1,120 @@ +/* +* Rivest's Package Tranform +* +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include + +namespace Botan { + +void aont_package(RandomNumberGenerator& rng, + BlockCipher* cipher, + const byte input[], size_t input_len, + byte output[]) + { + const size_t BLOCK_SIZE = cipher->block_size(); + + if(!cipher->valid_keylength(BLOCK_SIZE)) + throw Invalid_Argument("AONT::package: Invalid cipher"); + + // The all-zero string which is used both as the CTR IV and as K0 + const std::string all_zeros(BLOCK_SIZE*2, '0'); + + SymmetricKey package_key(rng, BLOCK_SIZE); + + Pipe pipe(new StreamCipher_Filter(new CTR_BE(cipher), package_key)); + + pipe.process_msg(input, input_len); + pipe.read(output, pipe.remaining()); + + // Set K0 (the all zero key) + cipher->set_key(SymmetricKey(all_zeros)); + + secure_vector buf(BLOCK_SIZE); + + const size_t blocks = + (input_len + BLOCK_SIZE - 1) / BLOCK_SIZE; + + byte* final_block = output + input_len; + clear_mem(final_block, BLOCK_SIZE); + + // XOR the hash blocks into the final block + for(size_t i = 0; i != blocks; ++i) + { + const size_t left = std::min(BLOCK_SIZE, + input_len - BLOCK_SIZE * i); + + zeroise(buf); + copy_mem(&buf[0], output + (BLOCK_SIZE * i), left); + + for(size_t j = 0; j != sizeof(i); ++j) + buf[BLOCK_SIZE - 1 - j] ^= get_byte(sizeof(i)-1-j, i); + + cipher->encrypt(&buf[0]); + + xor_buf(&final_block[0], &buf[0], BLOCK_SIZE); + } + + // XOR the random package key into the final block + xor_buf(&final_block[0], package_key.begin(), BLOCK_SIZE); + } + +void aont_unpackage(BlockCipher* cipher, + const byte input[], size_t input_len, + byte output[]) + { + const size_t BLOCK_SIZE = cipher->block_size(); + + if(!cipher->valid_keylength(BLOCK_SIZE)) + throw Invalid_Argument("AONT::unpackage: Invalid cipher"); + + if(input_len < BLOCK_SIZE) + throw Invalid_Argument("AONT::unpackage: Input too short"); + + // The all-zero string which is used both as the CTR IV and as K0 + const std::string all_zeros(BLOCK_SIZE*2, '0'); + + cipher->set_key(SymmetricKey(all_zeros)); + + secure_vector package_key(BLOCK_SIZE); + secure_vector buf(BLOCK_SIZE); + + // Copy the package key (masked with the block hashes) + copy_mem(&package_key[0], + input + (input_len - BLOCK_SIZE), + BLOCK_SIZE); + + const size_t blocks = ((input_len - 1) / BLOCK_SIZE); + + // XOR the blocks into the package key bits + for(size_t i = 0; i != blocks; ++i) + { + const size_t left = std::min(BLOCK_SIZE, + input_len - BLOCK_SIZE * (i+1)); + + zeroise(buf); + copy_mem(&buf[0], input + (BLOCK_SIZE * i), left); + + for(size_t j = 0; j != sizeof(i); ++j) + buf[BLOCK_SIZE - 1 - j] ^= get_byte(sizeof(i)-1-j, i); + + cipher->encrypt(&buf[0]); + + xor_buf(&package_key[0], &buf[0], BLOCK_SIZE); + } + + Pipe pipe(new StreamCipher_Filter(new CTR_BE(cipher), package_key)); + + pipe.process_msg(input, input_len - BLOCK_SIZE); + + pipe.read(output, pipe.remaining()); + } + +} diff --git a/lib/constructs/aont/package.h b/lib/constructs/aont/package.h new file mode 100644 index 000000000..52d1c2190 --- /dev/null +++ b/lib/constructs/aont/package.h @@ -0,0 +1,44 @@ +/* +* Rivest's Package Tranform +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_AONT_PACKAGE_TRANSFORM_H__ +#define BOTAN_AONT_PACKAGE_TRANSFORM_H__ + +#include +#include + +namespace Botan { + +/** +* Rivest's Package Tranform +* @param rng the random number generator to use +* @param cipher the block cipher to use +* @param input the input data buffer +* @param input_len the length of the input data in bytes +* @param output the output data buffer (must be at least +* input_len + cipher->BLOCK_SIZE bytes long) +*/ +void BOTAN_DLL aont_package(RandomNumberGenerator& rng, + BlockCipher* cipher, + const byte input[], size_t input_len, + byte output[]); + +/** +* Rivest's Package Tranform (Inversion) +* @param cipher the block cipher to use +* @param input the input data buffer +* @param input_len the length of the input data in bytes +* @param output the output data buffer (must be at least +* input_len - cipher->BLOCK_SIZE bytes long) +*/ +void BOTAN_DLL aont_unpackage(BlockCipher* cipher, + const byte input[], size_t input_len, + byte output[]); + +} + +#endif diff --git a/lib/constructs/cryptobox/cryptobox.cpp b/lib/constructs/cryptobox/cryptobox.cpp new file mode 100644 index 000000000..aa2369c6c --- /dev/null +++ b/lib/constructs/cryptobox/cryptobox.cpp @@ -0,0 +1,163 @@ +/* +* Cryptobox Message Routines +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace Botan { + +namespace CryptoBox { + +namespace { + +/* +First 24 bits of SHA-256("Botan Cryptobox"), followed by 8 0 bits +for later use as flags, etc if needed +*/ +const u32bit CRYPTOBOX_VERSION_CODE = 0xEFC22400; + +const size_t VERSION_CODE_LEN = 4; +const size_t CIPHER_KEY_LEN = 32; +const size_t CIPHER_IV_LEN = 16; +const size_t MAC_KEY_LEN = 32; +const size_t MAC_OUTPUT_LEN = 20; +const size_t PBKDF_SALT_LEN = 10; +const size_t PBKDF_ITERATIONS = 8 * 1024; + +const size_t PBKDF_OUTPUT_LEN = CIPHER_KEY_LEN + CIPHER_IV_LEN + MAC_KEY_LEN; + +} + +std::string encrypt(const byte input[], size_t input_len, + const std::string& passphrase, + RandomNumberGenerator& rng) + { + secure_vector pbkdf_salt(PBKDF_SALT_LEN); + rng.randomize(&pbkdf_salt[0], pbkdf_salt.size()); + + PKCS5_PBKDF2 pbkdf(new HMAC(new SHA_512)); + + OctetString master_key = pbkdf.derive_key( + PBKDF_OUTPUT_LEN, + passphrase, + &pbkdf_salt[0], + pbkdf_salt.size(), + PBKDF_ITERATIONS); + + const byte* mk = master_key.begin(); + + SymmetricKey cipher_key(&mk[0], CIPHER_KEY_LEN); + SymmetricKey mac_key(&mk[CIPHER_KEY_LEN], MAC_KEY_LEN); + InitializationVector iv(&mk[CIPHER_KEY_LEN + MAC_KEY_LEN], CIPHER_IV_LEN); + + Pipe pipe(get_cipher("Serpent/CTR-BE", cipher_key, iv, ENCRYPTION), + new Fork( + nullptr, + new MAC_Filter(new HMAC(new SHA_512), + mac_key, MAC_OUTPUT_LEN))); + + pipe.process_msg(input, input_len); + + /* + Output format is: + version # (4 bytes) + salt (10 bytes) + mac (20 bytes) + ciphertext + */ + const size_t ciphertext_len = pipe.remaining(0); + + std::vector out_buf(VERSION_CODE_LEN + + PBKDF_SALT_LEN + + MAC_OUTPUT_LEN + + ciphertext_len); + + for(size_t i = 0; i != VERSION_CODE_LEN; ++i) + out_buf[i] = get_byte(i, CRYPTOBOX_VERSION_CODE); + + copy_mem(&out_buf[VERSION_CODE_LEN], &pbkdf_salt[0], PBKDF_SALT_LEN); + + pipe.read(&out_buf[VERSION_CODE_LEN + PBKDF_SALT_LEN], MAC_OUTPUT_LEN, 1); + pipe.read(&out_buf[VERSION_CODE_LEN + PBKDF_SALT_LEN + MAC_OUTPUT_LEN], + ciphertext_len, 0); + + return PEM_Code::encode(out_buf, "BOTAN CRYPTOBOX MESSAGE"); + } + +std::string decrypt(const byte input[], size_t input_len, + const std::string& passphrase) + { + DataSource_Memory input_src(input, input_len); + secure_vector ciphertext = + PEM_Code::decode_check_label(input_src, + "BOTAN CRYPTOBOX MESSAGE"); + + if(ciphertext.size() < (VERSION_CODE_LEN + PBKDF_SALT_LEN + MAC_OUTPUT_LEN)) + throw Decoding_Error("Invalid CryptoBox input"); + + for(size_t i = 0; i != VERSION_CODE_LEN; ++i) + if(ciphertext[i] != get_byte(i, CRYPTOBOX_VERSION_CODE)) + throw Decoding_Error("Bad CryptoBox version"); + + const byte* pbkdf_salt = &ciphertext[VERSION_CODE_LEN]; + + PKCS5_PBKDF2 pbkdf(new HMAC(new SHA_512)); + + OctetString master_key = pbkdf.derive_key( + PBKDF_OUTPUT_LEN, + passphrase, + pbkdf_salt, + PBKDF_SALT_LEN, + PBKDF_ITERATIONS); + + const byte* mk = master_key.begin(); + + SymmetricKey cipher_key(&mk[0], CIPHER_KEY_LEN); + SymmetricKey mac_key(&mk[CIPHER_KEY_LEN], MAC_KEY_LEN); + InitializationVector iv(&mk[CIPHER_KEY_LEN + MAC_KEY_LEN], CIPHER_IV_LEN); + + Pipe pipe(new Fork( + get_cipher("Serpent/CTR-BE", cipher_key, iv, DECRYPTION), + new MAC_Filter(new HMAC(new SHA_512), + mac_key, MAC_OUTPUT_LEN))); + + const size_t ciphertext_offset = + VERSION_CODE_LEN + PBKDF_SALT_LEN + MAC_OUTPUT_LEN; + + pipe.process_msg(&ciphertext[ciphertext_offset], + ciphertext.size() - ciphertext_offset); + + byte computed_mac[MAC_OUTPUT_LEN]; + pipe.read(computed_mac, MAC_OUTPUT_LEN, 1); + + if(!same_mem(computed_mac, + &ciphertext[VERSION_CODE_LEN + PBKDF_SALT_LEN], + MAC_OUTPUT_LEN)) + throw Decoding_Error("CryptoBox integrity failure"); + + return pipe.read_all_as_string(0); + } + +std::string decrypt(const std::string& input, + const std::string& passphrase) + { + return decrypt(reinterpret_cast(&input[0]), + input.size(), + passphrase); + } + +} + +} diff --git a/lib/constructs/cryptobox/cryptobox.h b/lib/constructs/cryptobox/cryptobox.h new file mode 100644 index 000000000..7a363f72d --- /dev/null +++ b/lib/constructs/cryptobox/cryptobox.h @@ -0,0 +1,55 @@ +/* +* Cryptobox Message Routines +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_CRYPTOBOX_H__ +#define BOTAN_CRYPTOBOX_H__ + +#include +#include +#include + +namespace Botan { + +/** +* This namespace holds various high-level crypto functions +*/ +namespace CryptoBox { + +/** +* Encrypt a message using a passphrase +* @param input the input data +* @param input_len the length of input in bytes +* @param passphrase the passphrase used to encrypt the message +* @param rng a ref to a random number generator, such as AutoSeeded_RNG +*/ +BOTAN_DLL std::string encrypt(const byte input[], size_t input_len, + const std::string& passphrase, + RandomNumberGenerator& rng); + + +/** +* Decrypt a message encrypted with CryptoBox::encrypt +* @param input the input data +* @param input_len the length of input in bytes +* @param passphrase the passphrase used to encrypt the message +*/ +BOTAN_DLL std::string decrypt(const byte input[], size_t input_len, + const std::string& passphrase); + +/** +* Decrypt a message encrypted with CryptoBox::encrypt +* @param input the input data +* @param passphrase the passphrase used to encrypt the message +*/ +BOTAN_DLL std::string decrypt(const std::string& input, + const std::string& passphrase); + +} + +} + +#endif diff --git a/lib/constructs/cryptobox/info.txt b/lib/constructs/cryptobox/info.txt new file mode 100644 index 000000000..b7bf6e4e8 --- /dev/null +++ b/lib/constructs/cryptobox/info.txt @@ -0,0 +1,13 @@ +define CRYPTO_BOX 20131128 + + +filters +ctr +hmac +rng +serpent +sha2_64 +base64 +pbkdf2 +pem + diff --git a/lib/constructs/cryptobox_psk/cryptobox_psk.cpp b/lib/constructs/cryptobox_psk/cryptobox_psk.cpp new file mode 100644 index 000000000..f22e43b43 --- /dev/null +++ b/lib/constructs/cryptobox_psk/cryptobox_psk.cpp @@ -0,0 +1,134 @@ +/* +* Cryptobox Message Routines +* (C) 2013 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include + +namespace Botan { + +namespace CryptoBox { + +namespace { + +const u32bit CRYPTOBOX_MAGIC = 0x571B0E4F; +const std::string CRYPTOBOX_CIPHER = "AES-256/CBC"; +const std::string CRYPTOBOX_MAC = "HMAC(SHA-256)"; +const std::string CRYPTOBOX_KDF = "KDF2(SHA-256)"; + +const size_t MAGIC_LENGTH = 4; +const size_t KEY_KDF_SALT_LENGTH = 10; +const size_t MAC_KEY_LENGTH = 32; +const size_t CIPHER_KEY_LENGTH = 32; +const size_t CIPHER_IV_LENGTH = 16; +const size_t MAC_OUTPUT_LENGTH = 32; + +} + +std::vector encrypt(const byte input[], size_t input_len, + const SymmetricKey& master_key, + RandomNumberGenerator& rng) + { + std::unique_ptr kdf(get_kdf(CRYPTOBOX_KDF)); + + const secure_vector cipher_key_salt = + rng.random_vec(KEY_KDF_SALT_LENGTH); + + const secure_vector mac_key_salt = + rng.random_vec(KEY_KDF_SALT_LENGTH); + + SymmetricKey cipher_key = + kdf->derive_key(CIPHER_KEY_LENGTH, + master_key.bits_of(), + cipher_key_salt); + + SymmetricKey mac_key = + kdf->derive_key(MAC_KEY_LENGTH, + master_key.bits_of(), + mac_key_salt); + + InitializationVector cipher_iv(rng, 16); + + std::unique_ptr mac(get_mac(CRYPTOBOX_MAC)); + mac->set_key(mac_key); + + Pipe pipe(get_cipher(CRYPTOBOX_CIPHER, cipher_key, cipher_iv, ENCRYPTION)); + pipe.process_msg(input, input_len); + secure_vector ctext = pipe.read_all(0); + + std::vector out(MAGIC_LENGTH); + store_be(CRYPTOBOX_MAGIC, &out[0]); + out += cipher_key_salt; + out += mac_key_salt; + out += cipher_iv.bits_of(); + out += ctext; + + mac->update(out); + + out += mac->final(); + return out; + } + +secure_vector decrypt(const byte input[], size_t input_len, + const SymmetricKey& master_key) + { + const size_t MIN_CTEXT_SIZE = 16; // due to using CBC with padding + + const size_t MIN_POSSIBLE_LENGTH = + MAGIC_LENGTH + + 2 * KEY_KDF_SALT_LENGTH + + CIPHER_IV_LENGTH + + MIN_CTEXT_SIZE + + MAC_OUTPUT_LENGTH; + + if(input_len < MIN_POSSIBLE_LENGTH) + throw Decoding_Error("Encrypted input too short to be valid"); + + if(load_be(input, 0) != CRYPTOBOX_MAGIC) + throw Decoding_Error("Unknown header value in cryptobox"); + + std::unique_ptr kdf(get_kdf(CRYPTOBOX_KDF)); + + const byte* cipher_key_salt = &input[MAGIC_LENGTH]; + + const byte* mac_key_salt = &input[MAGIC_LENGTH + KEY_KDF_SALT_LENGTH]; + + SymmetricKey mac_key = kdf->derive_key(MAC_KEY_LENGTH, + master_key.bits_of(), + mac_key_salt, + KEY_KDF_SALT_LENGTH); + + std::unique_ptr mac(get_mac(CRYPTOBOX_MAC)); + mac->set_key(mac_key); + + mac->update(&input[0], input_len - MAC_OUTPUT_LENGTH); + secure_vector computed_mac = mac->final(); + + if(!same_mem(&input[input_len - MAC_OUTPUT_LENGTH], &computed_mac[0], computed_mac.size())) + throw Decoding_Error("MAC verification failed"); + + SymmetricKey cipher_key = + kdf->derive_key(CIPHER_KEY_LENGTH, + master_key.bits_of(), + cipher_key_salt, KEY_KDF_SALT_LENGTH); + + InitializationVector cipher_iv(&input[MAGIC_LENGTH+2*KEY_KDF_SALT_LENGTH], + CIPHER_IV_LENGTH); + + const size_t CTEXT_OFFSET = MAGIC_LENGTH + 2 * KEY_KDF_SALT_LENGTH + CIPHER_IV_LENGTH; + + Pipe pipe(get_cipher(CRYPTOBOX_CIPHER, cipher_key, cipher_iv, DECRYPTION)); + pipe.process_msg(&input[CTEXT_OFFSET], + input_len - (MAC_OUTPUT_LENGTH + CTEXT_OFFSET)); + return pipe.read_all(); + } + +} + +} diff --git a/lib/constructs/cryptobox_psk/cryptobox_psk.h b/lib/constructs/cryptobox_psk/cryptobox_psk.h new file mode 100644 index 000000000..2f16ee461 --- /dev/null +++ b/lib/constructs/cryptobox_psk/cryptobox_psk.h @@ -0,0 +1,47 @@ +/* +* Cryptobox Message Routines +* (C) 2009,2013 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_CRYPTOBOX_PSK_H__ +#define BOTAN_CRYPTOBOX_PSK_H__ + +#include +#include +#include + +namespace Botan { + +/** +* This namespace holds various high-level crypto functions +*/ +namespace CryptoBox { + +/** +* Encrypt a message using a shared secret key +* @param input the input data +* @param input_len the length of input in bytes +* @param key the key used to encrypt the message +* @param rng a ref to a random number generator, such as AutoSeeded_RNG +*/ +BOTAN_DLL std::vector encrypt(const byte input[], size_t input_len, + const SymmetricKey& key, + RandomNumberGenerator& rng); + +/** +* Encrypt a message using a shared secret key +* @param input the input data +* @param input_len the length of input in bytes +* @param key the key used to encrypt the message +* @param rng a ref to a random number generator, such as AutoSeeded_RNG +*/ +BOTAN_DLL secure_vector decrypt(const byte input[], size_t input_len, + const SymmetricKey& key); + +} + +} + +#endif diff --git a/lib/constructs/cryptobox_psk/info.txt b/lib/constructs/cryptobox_psk/info.txt new file mode 100644 index 000000000..03f7525f5 --- /dev/null +++ b/lib/constructs/cryptobox_psk/info.txt @@ -0,0 +1,10 @@ +define CRYPTOBOX_PSK 20131128 + + +aes +cbc +hmac +kdf2 +rng +sha2_64 + diff --git a/lib/constructs/fpe_fe1/fpe_fe1.cpp b/lib/constructs/fpe_fe1/fpe_fe1.cpp new file mode 100644 index 000000000..b22d3a8df --- /dev/null +++ b/lib/constructs/fpe_fe1/fpe_fe1.cpp @@ -0,0 +1,193 @@ +/* +* Format Preserving Encryption using the scheme FE1 from the paper +* "Format-Preserving Encryption" by Bellare, Rogaway, et al +* (http://eprint.iacr.org/2009/251) +* +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include + +namespace Botan { + +namespace FPE { + +namespace { + +// Normally FPE is for SSNs, CC#s, etc, nothing too big +const size_t MAX_N_BYTES = 128/8; + +/* +* Factor n into a and b which are as close together as possible. +* Assumes n is composed mostly of small factors which is the case for +* typical uses of FPE (typically, n is a power of 10) +* +* Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b +* then this is always 3 +*/ +void factor(BigInt n, BigInt& a, BigInt& b) + { + a = 1; + b = 1; + + size_t n_low_zero = low_zero_bits(n); + + a <<= (n_low_zero / 2); + b <<= n_low_zero - (n_low_zero / 2); + n >>= n_low_zero; + + for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) + { + while(n % PRIMES[i] == 0) + { + a *= PRIMES[i]; + if(a > b) + std::swap(a, b); + n /= PRIMES[i]; + } + } + + if(a > b) + std::swap(a, b); + a *= n; + if(a < b) + std::swap(a, b); + + if(a <= 1 || b <= 1) + throw std::runtime_error("Could not factor n for use in FPE"); + } + +/* +* According to a paper by Rogaway, Bellare, etc, the min safe number +* of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1 +* so 3 rounds is safe. The FPE factorization routine should always +* return a >= b, so just confirm that and return 3. +*/ +size_t rounds(const BigInt& a, const BigInt& b) + { + if(a < b) + throw std::logic_error("FPE rounds: a < b"); + return 3; + } + +/* +* A simple round function based on HMAC(SHA-256) +*/ +class FPE_Encryptor + { + public: + FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const std::vector& tweak); + + ~FPE_Encryptor() { delete mac; } + + BigInt operator()(size_t i, const BigInt& R); + + private: + MessageAuthenticationCode* mac; + std::vector mac_n_t; + }; + +FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const std::vector& tweak) + { + mac = new HMAC(new SHA_256); + mac->set_key(key); + + std::vector n_bin = BigInt::encode(n); + + if(n_bin.size() > MAX_N_BYTES) + throw std::runtime_error("N is too large for FPE encryption"); + + mac->update_be(static_cast(n_bin.size())); + mac->update(&n_bin[0], n_bin.size()); + + mac->update_be(static_cast(tweak.size())); + mac->update(&tweak[0], tweak.size()); + + mac_n_t = unlock(mac->final()); + } + +BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R) + { + secure_vector r_bin = BigInt::encode_locked(R); + + mac->update(mac_n_t); + mac->update_be(static_cast(round_no)); + + mac->update_be(static_cast(r_bin.size())); + mac->update(&r_bin[0], r_bin.size()); + + secure_vector X = mac->final(); + return BigInt(&X[0], X.size()); + } + +} + +/* +* Generic Z_n FPE encryption, FE1 scheme +*/ +BigInt fe1_encrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const std::vector& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const size_t r = rounds(a, b); + + BigInt X = X0; + + for(size_t i = 0; i != r; ++i) + { + BigInt L = X / b; + BigInt R = X % b; + + BigInt W = (L + F(i, R)) % a; + X = a * R + W; + } + + return X; + } + +/* +* Generic Z_n FPE decryption, FD1 scheme +*/ +BigInt fe1_decrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const std::vector& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const size_t r = rounds(a, b); + + BigInt X = X0; + + for(size_t i = 0; i != r; ++i) + { + BigInt W = X % a; + BigInt R = X / a; + + BigInt L = (W - F(r-i-1, R)) % a; + X = b * L + R; + } + + return X; + } + +} + +} diff --git a/lib/constructs/fpe_fe1/fpe_fe1.h b/lib/constructs/fpe_fe1/fpe_fe1.h new file mode 100644 index 000000000..66e7f1cfa --- /dev/null +++ b/lib/constructs/fpe_fe1/fpe_fe1.h @@ -0,0 +1,44 @@ +/* +* Format Preserving Encryption (FE1 scheme) +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_FPE_FE1_H__ +#define BOTAN_FPE_FE1_H__ + +#include +#include + +namespace Botan { + +namespace FPE { + +/** +* Encrypt X from and onto the group Z_n using key and tweak +* @param n the modulus +* @param X the plaintext as a BigInt +* @param key a random key +* @param tweak will modify the ciphertext (think of as an IV) +*/ +BigInt BOTAN_DLL fe1_encrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const std::vector& tweak); + +/** +* Decrypt X from and onto the group Z_n using key and tweak +* @param n the modulus +* @param X the ciphertext as a BigInt +* @param key is the key used for encryption +* @param tweak the same tweak used for encryption +*/ +BigInt BOTAN_DLL fe1_decrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const std::vector& tweak); + +} + +} + +#endif diff --git a/lib/constructs/fpe_fe1/info.txt b/lib/constructs/fpe_fe1/info.txt new file mode 100644 index 000000000..42264e54e --- /dev/null +++ b/lib/constructs/fpe_fe1/info.txt @@ -0,0 +1,7 @@ +define FPE_FE1 20131128 + + +hmac +sha2_32 +bigint + diff --git a/lib/constructs/rfc3394/info.txt b/lib/constructs/rfc3394/info.txt new file mode 100644 index 000000000..4b62b16e3 --- /dev/null +++ b/lib/constructs/rfc3394/info.txt @@ -0,0 +1 @@ +define RFC3394_KEYWRAP 20131128 diff --git a/lib/constructs/rfc3394/rfc3394.cpp b/lib/constructs/rfc3394/rfc3394.cpp new file mode 100644 index 000000000..cfe95f40b --- /dev/null +++ b/lib/constructs/rfc3394/rfc3394.cpp @@ -0,0 +1,122 @@ +/* +* AES Key Wrap (RFC 3394) +* (C) 2011 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include +#include +#include + +namespace Botan { + +namespace { + +BlockCipher* make_aes(size_t keylength, + Algorithm_Factory& af) + { + if(keylength == 16) + return af.make_block_cipher("AES-128"); + else if(keylength == 24) + return af.make_block_cipher("AES-192"); + else if(keylength == 32) + return af.make_block_cipher("AES-256"); + else + throw std::invalid_argument("Bad KEK length for NIST keywrap"); + } + +} + +secure_vector rfc3394_keywrap(const secure_vector& key, + const SymmetricKey& kek, + Algorithm_Factory& af) + { + if(key.size() % 8 != 0) + throw std::invalid_argument("Bad input key size for NIST key wrap"); + + std::unique_ptr aes(make_aes(kek.length(), af)); + aes->set_key(kek); + + const size_t n = key.size() / 8; + + secure_vector R((n + 1) * 8); + secure_vector A(16); + + for(size_t i = 0; i != 8; ++i) + A[i] = 0xA6; + + copy_mem(&R[8], &key[0], key.size()); + + for(size_t j = 0; j <= 5; ++j) + { + for(size_t i = 1; i <= n; ++i) + { + const u32bit t = (n * j) + i; + + copy_mem(&A[8], &R[8*i], 8); + + aes->encrypt(&A[0]); + copy_mem(&R[8*i], &A[8], 8); + + byte t_buf[4] = { 0 }; + store_be(t, t_buf); + xor_buf(&A[4], &t_buf[0], 4); + } + } + + copy_mem(&R[0], &A[0], 8); + + return R; + } + +secure_vector rfc3394_keyunwrap(const secure_vector& key, + const SymmetricKey& kek, + Algorithm_Factory& af) + { + if(key.size() < 16 || key.size() % 8 != 0) + throw std::invalid_argument("Bad input key size for NIST key unwrap"); + + std::unique_ptr aes(make_aes(kek.length(), af)); + aes->set_key(kek); + + const size_t n = (key.size() - 8) / 8; + + secure_vector R(n * 8); + secure_vector A(16); + + for(size_t i = 0; i != 8; ++i) + A[i] = key[i]; + + copy_mem(&R[0], &key[8], key.size() - 8); + + for(size_t j = 0; j <= 5; ++j) + { + for(size_t i = n; i != 0; --i) + { + const u32bit t = (5 - j) * n + i; + + byte t_buf[4] = { 0 }; + store_be(t, t_buf); + + xor_buf(&A[4], &t_buf[0], 4); + + copy_mem(&A[8], &R[8*(i-1)], 8); + + aes->decrypt(&A[0]); + + copy_mem(&R[8*(i-1)], &A[8], 8); + } + } + + if(load_be(&A[0], 0) != 0xA6A6A6A6A6A6A6A6) + throw Integrity_Failure("NIST key unwrap failed"); + + return R; + } + +} diff --git a/lib/constructs/rfc3394/rfc3394.h b/lib/constructs/rfc3394/rfc3394.h new file mode 100644 index 000000000..febd5207e --- /dev/null +++ b/lib/constructs/rfc3394/rfc3394.h @@ -0,0 +1,45 @@ +/* +* AES Key Wrap (RFC 3394) +* (C) 2011 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_AES_KEY_WRAP_H__ +#define BOTAN_AES_KEY_WRAP_H__ + +#include + +namespace Botan { + +class Algorithm_Factory; + +/** +* Encrypt a key under a key encryption key using the algorithm +* described in RFC 3394 +* +* @param key the plaintext key to encrypt +* @param kek the key encryption key +* @param af an algorithm factory +* @return key encrypted under kek +*/ +secure_vector BOTAN_DLL rfc3394_keywrap(const secure_vector& key, + const SymmetricKey& kek, + Algorithm_Factory& af); + +/** +* Decrypt a key under a key encryption key using the algorithm +* described in RFC 3394 +* +* @param key the encrypted key to decrypt +* @param kek the key encryption key +* @param af an algorithm factory +* @return key decrypted under kek +*/ +secure_vector BOTAN_DLL rfc3394_keyunwrap(const secure_vector& key, + const SymmetricKey& kek, + Algorithm_Factory& af); + +} + +#endif diff --git a/lib/constructs/srp6/info.txt b/lib/constructs/srp6/info.txt new file mode 100644 index 000000000..1d1c4ba96 --- /dev/null +++ b/lib/constructs/srp6/info.txt @@ -0,0 +1,7 @@ +define SRP6 20131128 + + +bigint +hash +dl_group + diff --git a/lib/constructs/srp6/srp6.cpp b/lib/constructs/srp6/srp6.cpp new file mode 100644 index 000000000..7bc879350 --- /dev/null +++ b/lib/constructs/srp6/srp6.cpp @@ -0,0 +1,163 @@ +/* +* SRP-6a (RFC 5054 compatatible) +* (C) 2011,2012 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include + +namespace Botan { + +namespace { + +BigInt hash_seq(const std::string& hash_id, + size_t pad_to, + const BigInt& in1, + const BigInt& in2) + { + std::unique_ptr hash_fn( + global_state().algorithm_factory().make_hash_function(hash_id)); + + hash_fn->update(BigInt::encode_1363(in1, pad_to)); + hash_fn->update(BigInt::encode_1363(in2, pad_to)); + + return BigInt::decode(hash_fn->final()); + } + +BigInt compute_x(const std::string& hash_id, + const std::string& identifier, + const std::string& password, + const std::vector& salt) + { + std::unique_ptr hash_fn( + global_state().algorithm_factory().make_hash_function(hash_id)); + + hash_fn->update(identifier); + hash_fn->update(":"); + hash_fn->update(password); + + secure_vector inner_h = hash_fn->final(); + + hash_fn->update(salt); + hash_fn->update(inner_h); + + secure_vector outer_h = hash_fn->final(); + + return BigInt::decode(outer_h); + } + +} + +std::string srp6_group_identifier(const BigInt& N, const BigInt& g) + { + /* + This function assumes that only one 'standard' SRP parameter set has + been defined for a particular bitsize. As of this writing that is the case. + */ + try + { + const std::string group_name = "modp/srp/" + std::to_string(N.bits()); + + DL_Group group(group_name); + + if(group.get_p() == N && group.get_g() == g) + return group_name; + + throw std::runtime_error("Unknown SRP params"); + } + catch(...) + { + throw Invalid_Argument("Bad SRP group parameters"); + } + } + +std::pair +srp6_client_agree(const std::string& identifier, + const std::string& password, + const std::string& group_id, + const std::string& hash_id, + const std::vector& salt, + const BigInt& B, + RandomNumberGenerator& rng) + { + DL_Group group(group_id); + const BigInt& g = group.get_g(); + const BigInt& p = group.get_p(); + + const size_t p_bytes = group.get_p().bytes(); + + if(B <= 0 || B >= p) + throw std::runtime_error("Invalid SRP parameter from server"); + + BigInt k = hash_seq(hash_id, p_bytes, p, g); + + BigInt a(rng, 256); + + BigInt A = power_mod(g, a, p); + + BigInt u = hash_seq(hash_id, p_bytes, A, B); + + const BigInt x = compute_x(hash_id, identifier, password, salt); + + BigInt S = power_mod((B - (k * power_mod(g, x, p))) % p, (a + (u * x)), p); + + SymmetricKey Sk(BigInt::encode_1363(S, p_bytes)); + + return std::make_pair(A, Sk); + } + +BigInt generate_srp6_verifier(const std::string& identifier, + const std::string& password, + const std::vector& salt, + const std::string& group_id, + const std::string& hash_id) + { + const BigInt x = compute_x(hash_id, identifier, password, salt); + + DL_Group group(group_id); + return power_mod(group.get_g(), x, group.get_p()); + } + +BigInt SRP6_Server_Session::step1(const BigInt& v, + const std::string& group_id, + const std::string& hash_id, + RandomNumberGenerator& rng) + { + DL_Group group(group_id); + const BigInt& g = group.get_g(); + const BigInt& p = group.get_p(); + + p_bytes = p.bytes(); + + BigInt k = hash_seq(hash_id, p_bytes, p, g); + + BigInt b(rng, 256); + + B = (v*k + power_mod(g, b, p)) % p; + + this->v = v; + this->b = b; + this->p = p; + this->hash_id = hash_id; + + return B; + } + +SymmetricKey SRP6_Server_Session::step2(const BigInt& A) + { + if(A <= 0 || A >= p) + throw std::runtime_error("Invalid SRP parameter from client"); + + BigInt u = hash_seq(hash_id, p_bytes, A, B); + + BigInt S = power_mod(A * power_mod(v, u, p), b, p); + + return BigInt::encode_1363(S, p_bytes); + } + +} diff --git a/lib/constructs/srp6/srp6.h b/lib/constructs/srp6/srp6.h new file mode 100644 index 000000000..6f3960be1 --- /dev/null +++ b/lib/constructs/srp6/srp6.h @@ -0,0 +1,97 @@ +/* +* SRP-6a (RFC 5054 compatatible) +* (C) 2011,2012 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_RFC5054_SRP6_H__ +#define BOTAN_RFC5054_SRP6_H__ + +#include +#include +#include +#include +#include + +namespace Botan { + +/** +* SRP6a Client side +* @param username the username we are attempting login for +* @param password the password we are attempting to use +* @param group_id specifies the shared SRP group +* @param hash_id specifies a secure hash function +* @param salt is the salt value sent by the server +* @param B is the server's public value +* @param rng is a random number generator +* +* @return (A,K) the client public key and the shared secret key +*/ +std::pair +BOTAN_DLL srp6_client_agree(const std::string& username, + const std::string& password, + const std::string& group_id, + const std::string& hash_id, + const std::vector& salt, + const BigInt& B, + RandomNumberGenerator& rng); + +/** +* Generate a new SRP-6 verifier +* @param identifier a username or other client identifier +* @param password the secret used to authenticate user +* @param salt a randomly chosen value, at least 128 bits long +* @param group_id specifies the shared SRP group +* @param hash_id specifies a secure hash function +*/ +BigInt BOTAN_DLL generate_srp6_verifier(const std::string& identifier, + const std::string& password, + const std::vector& salt, + const std::string& group_id, + const std::string& hash_id); + +/** +* Return the group id for this SRP param set, or else thrown an +* exception +* @param N the group modulus +* @param g the group generator +* @return group identifier +*/ +std::string BOTAN_DLL srp6_group_identifier(const BigInt& N, const BigInt& g); + +/** +* Represents a SRP-6a server session +*/ +class BOTAN_DLL SRP6_Server_Session + { + public: + /** + * Server side step 1 + * @param v the verification value saved from client registration + * @param group_id the SRP group id + * @param hash_id the SRP hash in use + * @param rng a random number generator + * @return SRP-6 B value + */ + BigInt step1(const BigInt& v, + const std::string& group_id, + const std::string& hash_id, + RandomNumberGenerator& rng); + + /** + * Server side step 2 + * @param A the client's value + * @return shared symmetric key + */ + SymmetricKey step2(const BigInt& A); + + private: + std::string hash_id; + BigInt B, b, v, S, p; + size_t p_bytes; + }; + +} + +#endif diff --git a/lib/constructs/srp6/srp6_files.cpp b/lib/constructs/srp6/srp6_files.cpp new file mode 100644 index 000000000..4df2986f3 --- /dev/null +++ b/lib/constructs/srp6/srp6_files.cpp @@ -0,0 +1,69 @@ +/* +* SRP-6a File Handling +* (C) 2011 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include + +namespace Botan { + +SRP6_Authenticator_File::SRP6_Authenticator_File(const std::string& filename) + { + std::ifstream in(filename.c_str()); + + if(!in) + return; // no entries + + while(in.good()) + { + std::string line; + std::getline(in, line); + + std::vector parts = split_on(line, ':'); + + if(parts.size() != 4) + throw Decoding_Error("Invalid line in SRP authenticator file"); + + std::string username = parts[0]; + BigInt v = BigInt::decode(base64_decode(parts[1])); + std::vector salt = unlock(base64_decode(parts[2])); + BigInt group_id_idx = BigInt::decode(base64_decode(parts[3])); + + std::string group_id; + + if(group_id_idx == 1) + group_id = "modp/srp/1024"; + else if(group_id_idx == 2) + group_id = "modp/srp/1536"; + else if(group_id_idx == 3) + group_id = "modp/srp/2048"; + else + continue; // unknown group, ignored + + entries[username] = SRP6_Data(v, salt, group_id); + } + } + +bool SRP6_Authenticator_File::lookup_user(const std::string& username, + BigInt& v, + std::vector& salt, + std::string& group_id) const + { + std::map::const_iterator i = entries.find(username); + + if(i == entries.end()) + return false; + + v = i->second.v; + salt = i->second.salt; + group_id = i->second.group_id; + + return true; + } + +} diff --git a/lib/constructs/srp6/srp6_files.h b/lib/constructs/srp6/srp6_files.h new file mode 100644 index 000000000..4e0d3ff02 --- /dev/null +++ b/lib/constructs/srp6/srp6_files.h @@ -0,0 +1,53 @@ +/* +* SRP-6a File Handling +* (C) 2011 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_SRP6A_FILES_H__ +#define BOTAN_SRP6A_FILES_H__ + +#include +#include +#include + +namespace Botan { + +/** +* A GnuTLS compatible SRP6 authenticator file +*/ +class BOTAN_DLL SRP6_Authenticator_File + { + public: + /** + * @param filename will be opened and processed as a SRP + * authenticator file + */ + SRP6_Authenticator_File(const std::string& filename); + + bool lookup_user(const std::string& username, + BigInt& v, + std::vector& salt, + std::string& group_id) const; + private: + struct SRP6_Data + { + SRP6_Data() {} + + SRP6_Data(const BigInt& v, + const std::vector& salt, + const std::string& group_id) : + v(v), salt(salt), group_id(group_id) {} + + BigInt v; + std::vector salt; + std::string group_id; + }; + + std::map entries; + }; + +} + +#endif diff --git a/lib/constructs/tss/info.txt b/lib/constructs/tss/info.txt new file mode 100644 index 000000000..0c86bebbe --- /dev/null +++ b/lib/constructs/tss/info.txt @@ -0,0 +1,8 @@ +define THRESHOLD_SECRET_SHARING 20131128 + + +hash +rng +filters +hex + diff --git a/lib/constructs/tss/tss.cpp b/lib/constructs/tss/tss.cpp new file mode 100644 index 000000000..2024b39ec --- /dev/null +++ b/lib/constructs/tss/tss.cpp @@ -0,0 +1,262 @@ +/* +* RTSS (threshold secret sharing) +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include +#include +#include + +namespace Botan { + +namespace { + +/** +Table for GF(2^8) arithmetic (exponentials) +*/ +const byte RTSS_EXP[256] = { +0x01, 0x03, 0x05, 0x0F, 0x11, 0x33, 0x55, 0xFF, 0x1A, 0x2E, 0x72, +0x96, 0xA1, 0xF8, 0x13, 0x35, 0x5F, 0xE1, 0x38, 0x48, 0xD8, 0x73, +0x95, 0xA4, 0xF7, 0x02, 0x06, 0x0A, 0x1E, 0x22, 0x66, 0xAA, 0xE5, +0x34, 0x5C, 0xE4, 0x37, 0x59, 0xEB, 0x26, 0x6A, 0xBE, 0xD9, 0x70, +0x90, 0xAB, 0xE6, 0x31, 0x53, 0xF5, 0x04, 0x0C, 0x14, 0x3C, 0x44, +0xCC, 0x4F, 0xD1, 0x68, 0xB8, 0xD3, 0x6E, 0xB2, 0xCD, 0x4C, 0xD4, +0x67, 0xA9, 0xE0, 0x3B, 0x4D, 0xD7, 0x62, 0xA6, 0xF1, 0x08, 0x18, +0x28, 0x78, 0x88, 0x83, 0x9E, 0xB9, 0xD0, 0x6B, 0xBD, 0xDC, 0x7F, +0x81, 0x98, 0xB3, 0xCE, 0x49, 0xDB, 0x76, 0x9A, 0xB5, 0xC4, 0x57, +0xF9, 0x10, 0x30, 0x50, 0xF0, 0x0B, 0x1D, 0x27, 0x69, 0xBB, 0xD6, +0x61, 0xA3, 0xFE, 0x19, 0x2B, 0x7D, 0x87, 0x92, 0xAD, 0xEC, 0x2F, +0x71, 0x93, 0xAE, 0xE9, 0x20, 0x60, 0xA0, 0xFB, 0x16, 0x3A, 0x4E, +0xD2, 0x6D, 0xB7, 0xC2, 0x5D, 0xE7, 0x32, 0x56, 0xFA, 0x15, 0x3F, +0x41, 0xC3, 0x5E, 0xE2, 0x3D, 0x47, 0xC9, 0x40, 0xC0, 0x5B, 0xED, +0x2C, 0x74, 0x9C, 0xBF, 0xDA, 0x75, 0x9F, 0xBA, 0xD5, 0x64, 0xAC, +0xEF, 0x2A, 0x7E, 0x82, 0x9D, 0xBC, 0xDF, 0x7A, 0x8E, 0x89, 0x80, +0x9B, 0xB6, 0xC1, 0x58, 0xE8, 0x23, 0x65, 0xAF, 0xEA, 0x25, 0x6F, +0xB1, 0xC8, 0x43, 0xC5, 0x54, 0xFC, 0x1F, 0x21, 0x63, 0xA5, 0xF4, +0x07, 0x09, 0x1B, 0x2D, 0x77, 0x99, 0xB0, 0xCB, 0x46, 0xCA, 0x45, +0xCF, 0x4A, 0xDE, 0x79, 0x8B, 0x86, 0x91, 0xA8, 0xE3, 0x3E, 0x42, +0xC6, 0x51, 0xF3, 0x0E, 0x12, 0x36, 0x5A, 0xEE, 0x29, 0x7B, 0x8D, +0x8C, 0x8F, 0x8A, 0x85, 0x94, 0xA7, 0xF2, 0x0D, 0x17, 0x39, 0x4B, +0xDD, 0x7C, 0x84, 0x97, 0xA2, 0xFD, 0x1C, 0x24, 0x6C, 0xB4, 0xC7, +0x52, 0xF6, 0x01 }; + +/** +Table for GF(2^8) arithmetic (logarithms) +*/ +const byte RTSS_LOG[] = { +0x90, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1A, 0xC6, 0x4B, 0xC7, 0x1B, +0x68, 0x33, 0xEE, 0xDF, 0x03, 0x64, 0x04, 0xE0, 0x0E, 0x34, 0x8D, +0x81, 0xEF, 0x4C, 0x71, 0x08, 0xC8, 0xF8, 0x69, 0x1C, 0xC1, 0x7D, +0xC2, 0x1D, 0xB5, 0xF9, 0xB9, 0x27, 0x6A, 0x4D, 0xE4, 0xA6, 0x72, +0x9A, 0xC9, 0x09, 0x78, 0x65, 0x2F, 0x8A, 0x05, 0x21, 0x0F, 0xE1, +0x24, 0x12, 0xF0, 0x82, 0x45, 0x35, 0x93, 0xDA, 0x8E, 0x96, 0x8F, +0xDB, 0xBD, 0x36, 0xD0, 0xCE, 0x94, 0x13, 0x5C, 0xD2, 0xF1, 0x40, +0x46, 0x83, 0x38, 0x66, 0xDD, 0xFD, 0x30, 0xBF, 0x06, 0x8B, 0x62, +0xB3, 0x25, 0xE2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7E, 0x6E, 0x48, +0xC3, 0xA3, 0xB6, 0x1E, 0x42, 0x3A, 0x6B, 0x28, 0x54, 0xFA, 0x85, +0x3D, 0xBA, 0x2B, 0x79, 0x0A, 0x15, 0x9B, 0x9F, 0x5E, 0xCA, 0x4E, +0xD4, 0xAC, 0xE5, 0xF3, 0x73, 0xA7, 0x57, 0xAF, 0x58, 0xA8, 0x50, +0xF4, 0xEA, 0xD6, 0x74, 0x4F, 0xAE, 0xE9, 0xD5, 0xE7, 0xE6, 0xAD, +0xE8, 0x2C, 0xD7, 0x75, 0x7A, 0xEB, 0x16, 0x0B, 0xF5, 0x59, 0xCB, +0x5F, 0xB0, 0x9C, 0xA9, 0x51, 0xA0, 0x7F, 0x0C, 0xF6, 0x6F, 0x17, +0xC4, 0x49, 0xEC, 0xD8, 0x43, 0x1F, 0x2D, 0xA4, 0x76, 0x7B, 0xB7, +0xCC, 0xBB, 0x3E, 0x5A, 0xFB, 0x60, 0xB1, 0x86, 0x3B, 0x52, 0xA1, +0x6C, 0xAA, 0x55, 0x29, 0x9D, 0x97, 0xB2, 0x87, 0x90, 0x61, 0xBE, +0xDC, 0xFC, 0xBC, 0x95, 0xCF, 0xCD, 0x37, 0x3F, 0x5B, 0xD1, 0x53, +0x39, 0x84, 0x3C, 0x41, 0xA2, 0x6D, 0x47, 0x14, 0x2A, 0x9E, 0x5D, +0x56, 0xF2, 0xD3, 0xAB, 0x44, 0x11, 0x92, 0xD9, 0x23, 0x20, 0x2E, +0x89, 0xB4, 0x7C, 0xB8, 0x26, 0x77, 0x99, 0xE3, 0xA5, 0x67, 0x4A, +0xED, 0xDE, 0xC5, 0x31, 0xFE, 0x18, 0x0D, 0x63, 0x8C, 0x80, 0xC0, +0xF7, 0x70, 0x07 }; + +byte gfp_mul(byte x, byte y) + { + if(x == 0 || y == 0) + return 0; + return RTSS_EXP[(RTSS_LOG[x] + RTSS_LOG[y]) % 255]; + } + +byte rtss_hash_id(const std::string& hash_name) + { + if(hash_name == "SHA-160") + return 1; + else if(hash_name == "SHA-256") + return 2; + else + throw Invalid_Argument("RTSS only supports SHA-1 and SHA-256"); + } + +HashFunction* get_rtss_hash_by_id(byte id) + { + if(id == 1) + return new SHA_160; + else if(id == 2) + return new SHA_256; + else + throw Decoding_Error("Bad RTSS hash identifier"); + } + +} + +RTSS_Share::RTSS_Share(const std::string& hex_input) + { + contents = hex_decode_locked(hex_input); + } + +byte RTSS_Share::share_id() const + { + if(!initialized()) + throw Invalid_State("RTSS_Share::share_id not initialized"); + + return contents[20]; + } + +std::string RTSS_Share::to_string() const + { + return hex_encode(&contents[0], contents.size()); + } + +std::vector +RTSS_Share::split(byte M, byte N, + const byte S[], u16bit S_len, + const byte identifier[16], + RandomNumberGenerator& rng) + { + if(M == 0 || N == 0 || M > N) + throw Encoding_Error("RTSS_Share::split: M == 0 or N == 0 or M > N"); + + SHA_256 hash; // always use SHA-256 when generating shares + + std::vector shares(N); + + // Create RTSS header in each share + for(byte i = 0; i != N; ++i) + { + shares[i].contents += std::make_pair(identifier, 16); + shares[i].contents += rtss_hash_id(hash.name()); + shares[i].contents += M; + shares[i].contents += get_byte(0, S_len); + shares[i].contents += get_byte(1, S_len); + } + + // Choose sequential values for X starting from 1 + for(byte i = 0; i != N; ++i) + shares[i].contents.push_back(i+1); + + // secret = S || H(S) + secure_vector secret(S, S + S_len); + secret += hash.process(S, S_len); + + for(size_t i = 0; i != secret.size(); ++i) + { + std::vector coefficients(M-1); + rng.randomize(&coefficients[0], coefficients.size()); + + for(byte j = 0; j != N; ++j) + { + const byte X = j + 1; + + byte sum = secret[i]; + byte X_i = X; + + for(size_t k = 0; k != coefficients.size(); ++k) + { + sum ^= gfp_mul(X_i, coefficients[k]); + X_i = gfp_mul(X_i, X); + } + + shares[j].contents.push_back(sum); + } + } + + return shares; + } + +secure_vector +RTSS_Share::reconstruct(const std::vector& shares) + { + const size_t RTSS_HEADER_SIZE = 20; + + for(size_t i = 0; i != shares.size(); ++i) + { + if(shares[i].size() != shares[0].size()) + throw Decoding_Error("Different sized RTSS shares detected"); + if(shares[i].share_id() == 0) + throw Decoding_Error("Invalid (id = 0) RTSS share detected"); + if(shares[i].size() < RTSS_HEADER_SIZE) + throw Decoding_Error("Missing or malformed RTSS header"); + + if(!same_mem(&shares[0].contents[0], + &shares[i].contents[0], RTSS_HEADER_SIZE)) + throw Decoding_Error("Different RTSS headers detected"); + } + + if(shares.size() < shares[0].contents[17]) + throw Decoding_Error("Insufficient shares to do TSS reconstruction"); + + u16bit secret_len = make_u16bit(shares[0].contents[18], + shares[0].contents[19]); + + byte hash_id = shares[0].contents[16]; + + std::unique_ptr hash(get_rtss_hash_by_id(hash_id)); + + if(shares[0].size() != secret_len + hash->output_length() + RTSS_HEADER_SIZE + 1) + throw Decoding_Error("Bad RTSS length field in header"); + + std::vector V(shares.size()); + secure_vector secret; + + for(size_t i = RTSS_HEADER_SIZE + 1; i != shares[0].size(); ++i) + { + for(size_t j = 0; j != V.size(); ++j) + V[j] = shares[j].contents[i]; + + byte r = 0; + for(size_t k = 0; k != shares.size(); ++k) + { + // L_i function: + byte r2 = 1; + for(size_t l = 0; l != shares.size(); ++l) + { + if(k == l) + continue; + + byte share_k = shares[k].share_id(); + byte share_l = shares[l].share_id(); + + if(share_k == share_l) + throw Decoding_Error("Duplicate shares found in RTSS recovery"); + + byte div = RTSS_EXP[(255 + + RTSS_LOG[share_l] - + RTSS_LOG[share_k ^ share_l]) % 255]; + + r2 = gfp_mul(r2, div); + } + + r ^= gfp_mul(V[k], r2); + } + secret.push_back(r); + } + + if(secret.size() != secret_len + hash->output_length()) + throw Decoding_Error("Bad length in RTSS output"); + + hash->update(&secret[0], secret_len); + secure_vector hash_check = hash->final(); + + if(!same_mem(&hash_check[0], + &secret[secret_len], hash->output_length())) + throw Decoding_Error("RTSS hash check failed"); + + return secure_vector(&secret[0], &secret[secret_len]); + } + +} diff --git a/lib/constructs/tss/tss.h b/lib/constructs/tss/tss.h new file mode 100644 index 000000000..4664af317 --- /dev/null +++ b/lib/constructs/tss/tss.h @@ -0,0 +1,76 @@ +/* +* RTSS (threshold secret sharing) +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_RTSS_H__ +#define BOTAN_RTSS_H__ + +#include +#include +#include +#include + +namespace Botan { + +/** +* A split secret, using the format from draft-mcgrew-tss-03 +*/ +class BOTAN_DLL RTSS_Share + { + public: + /** + * @param M the number of shares needed to reconstruct + * @param N the number of shares generated + * @param secret the secret to split + * @param secret_len the length of the secret + * @param identifier the 16 byte share identifier + * @param rng the random number generator to use + */ + static std::vector + split(byte M, byte N, + const byte secret[], u16bit secret_len, + const byte identifier[16], + RandomNumberGenerator& rng); + + /** + * @param shares the list of shares + */ + static secure_vector + reconstruct(const std::vector& shares); + + RTSS_Share() {} + + /** + * @param hex_input the share encoded in hexadecimal + */ + RTSS_Share(const std::string& hex_input); + + /** + * @return hex representation + */ + std::string to_string() const; + + /** + * @return share identifier + */ + byte share_id() const; + + /** + * @return size of this share in bytes + */ + size_t size() const { return contents.size(); } + + /** + * @return if this TSS share was initialized or not + */ + bool initialized() const { return (contents.size() > 0); } + private: + secure_vector contents; + }; + +} + +#endif -- cgit v1.2.3