Botan  1.11.15
src/lib/misc/tss/tss.cpp
Go to the documentation of this file.
00001 /*
00002 * RTSS (threshold secret sharing)
00003 * (C) 2009 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/tss.h>
00009 #include <botan/loadstor.h>
00010 #include <botan/pipe.h>
00011 #include <botan/hex.h>
00012 #include <botan/sha2_32.h>
00013 #include <botan/sha160.h>
00014 
00015 namespace Botan {
00016 
00017 namespace {
00018 
00019 /**
00020 Table for GF(2^8) arithmetic (exponentials)
00021 */
00022 const byte RTSS_EXP[256] = {
00023 0x01, 0x03, 0x05, 0x0F, 0x11, 0x33, 0x55, 0xFF, 0x1A, 0x2E, 0x72,
00024 0x96, 0xA1, 0xF8, 0x13, 0x35, 0x5F, 0xE1, 0x38, 0x48, 0xD8, 0x73,
00025 0x95, 0xA4, 0xF7, 0x02, 0x06, 0x0A, 0x1E, 0x22, 0x66, 0xAA, 0xE5,
00026 0x34, 0x5C, 0xE4, 0x37, 0x59, 0xEB, 0x26, 0x6A, 0xBE, 0xD9, 0x70,
00027 0x90, 0xAB, 0xE6, 0x31, 0x53, 0xF5, 0x04, 0x0C, 0x14, 0x3C, 0x44,
00028 0xCC, 0x4F, 0xD1, 0x68, 0xB8, 0xD3, 0x6E, 0xB2, 0xCD, 0x4C, 0xD4,
00029 0x67, 0xA9, 0xE0, 0x3B, 0x4D, 0xD7, 0x62, 0xA6, 0xF1, 0x08, 0x18,
00030 0x28, 0x78, 0x88, 0x83, 0x9E, 0xB9, 0xD0, 0x6B, 0xBD, 0xDC, 0x7F,
00031 0x81, 0x98, 0xB3, 0xCE, 0x49, 0xDB, 0x76, 0x9A, 0xB5, 0xC4, 0x57,
00032 0xF9, 0x10, 0x30, 0x50, 0xF0, 0x0B, 0x1D, 0x27, 0x69, 0xBB, 0xD6,
00033 0x61, 0xA3, 0xFE, 0x19, 0x2B, 0x7D, 0x87, 0x92, 0xAD, 0xEC, 0x2F,
00034 0x71, 0x93, 0xAE, 0xE9, 0x20, 0x60, 0xA0, 0xFB, 0x16, 0x3A, 0x4E,
00035 0xD2, 0x6D, 0xB7, 0xC2, 0x5D, 0xE7, 0x32, 0x56, 0xFA, 0x15, 0x3F,
00036 0x41, 0xC3, 0x5E, 0xE2, 0x3D, 0x47, 0xC9, 0x40, 0xC0, 0x5B, 0xED,
00037 0x2C, 0x74, 0x9C, 0xBF, 0xDA, 0x75, 0x9F, 0xBA, 0xD5, 0x64, 0xAC,
00038 0xEF, 0x2A, 0x7E, 0x82, 0x9D, 0xBC, 0xDF, 0x7A, 0x8E, 0x89, 0x80,
00039 0x9B, 0xB6, 0xC1, 0x58, 0xE8, 0x23, 0x65, 0xAF, 0xEA, 0x25, 0x6F,
00040 0xB1, 0xC8, 0x43, 0xC5, 0x54, 0xFC, 0x1F, 0x21, 0x63, 0xA5, 0xF4,
00041 0x07, 0x09, 0x1B, 0x2D, 0x77, 0x99, 0xB0, 0xCB, 0x46, 0xCA, 0x45,
00042 0xCF, 0x4A, 0xDE, 0x79, 0x8B, 0x86, 0x91, 0xA8, 0xE3, 0x3E, 0x42,
00043 0xC6, 0x51, 0xF3, 0x0E, 0x12, 0x36, 0x5A, 0xEE, 0x29, 0x7B, 0x8D,
00044 0x8C, 0x8F, 0x8A, 0x85, 0x94, 0xA7, 0xF2, 0x0D, 0x17, 0x39, 0x4B,
00045 0xDD, 0x7C, 0x84, 0x97, 0xA2, 0xFD, 0x1C, 0x24, 0x6C, 0xB4, 0xC7,
00046 0x52, 0xF6, 0x01 };
00047 
00048 /**
00049 Table for GF(2^8) arithmetic (logarithms)
00050 */
00051 const byte RTSS_LOG[] = {
00052 0x90, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1A, 0xC6, 0x4B, 0xC7, 0x1B,
00053 0x68, 0x33, 0xEE, 0xDF, 0x03, 0x64, 0x04, 0xE0, 0x0E, 0x34, 0x8D,
00054 0x81, 0xEF, 0x4C, 0x71, 0x08, 0xC8, 0xF8, 0x69, 0x1C, 0xC1, 0x7D,
00055 0xC2, 0x1D, 0xB5, 0xF9, 0xB9, 0x27, 0x6A, 0x4D, 0xE4, 0xA6, 0x72,
00056 0x9A, 0xC9, 0x09, 0x78, 0x65, 0x2F, 0x8A, 0x05, 0x21, 0x0F, 0xE1,
00057 0x24, 0x12, 0xF0, 0x82, 0x45, 0x35, 0x93, 0xDA, 0x8E, 0x96, 0x8F,
00058 0xDB, 0xBD, 0x36, 0xD0, 0xCE, 0x94, 0x13, 0x5C, 0xD2, 0xF1, 0x40,
00059 0x46, 0x83, 0x38, 0x66, 0xDD, 0xFD, 0x30, 0xBF, 0x06, 0x8B, 0x62,
00060 0xB3, 0x25, 0xE2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7E, 0x6E, 0x48,
00061 0xC3, 0xA3, 0xB6, 0x1E, 0x42, 0x3A, 0x6B, 0x28, 0x54, 0xFA, 0x85,
00062 0x3D, 0xBA, 0x2B, 0x79, 0x0A, 0x15, 0x9B, 0x9F, 0x5E, 0xCA, 0x4E,
00063 0xD4, 0xAC, 0xE5, 0xF3, 0x73, 0xA7, 0x57, 0xAF, 0x58, 0xA8, 0x50,
00064 0xF4, 0xEA, 0xD6, 0x74, 0x4F, 0xAE, 0xE9, 0xD5, 0xE7, 0xE6, 0xAD,
00065 0xE8, 0x2C, 0xD7, 0x75, 0x7A, 0xEB, 0x16, 0x0B, 0xF5, 0x59, 0xCB,
00066 0x5F, 0xB0, 0x9C, 0xA9, 0x51, 0xA0, 0x7F, 0x0C, 0xF6, 0x6F, 0x17,
00067 0xC4, 0x49, 0xEC, 0xD8, 0x43, 0x1F, 0x2D, 0xA4, 0x76, 0x7B, 0xB7,
00068 0xCC, 0xBB, 0x3E, 0x5A, 0xFB, 0x60, 0xB1, 0x86, 0x3B, 0x52, 0xA1,
00069 0x6C, 0xAA, 0x55, 0x29, 0x9D, 0x97, 0xB2, 0x87, 0x90, 0x61, 0xBE,
00070 0xDC, 0xFC, 0xBC, 0x95, 0xCF, 0xCD, 0x37, 0x3F, 0x5B, 0xD1, 0x53,
00071 0x39, 0x84, 0x3C, 0x41, 0xA2, 0x6D, 0x47, 0x14, 0x2A, 0x9E, 0x5D,
00072 0x56, 0xF2, 0xD3, 0xAB, 0x44, 0x11, 0x92, 0xD9, 0x23, 0x20, 0x2E,
00073 0x89, 0xB4, 0x7C, 0xB8, 0x26, 0x77, 0x99, 0xE3, 0xA5, 0x67, 0x4A,
00074 0xED, 0xDE, 0xC5, 0x31, 0xFE, 0x18, 0x0D, 0x63, 0x8C, 0x80, 0xC0,
00075 0xF7, 0x70, 0x07 };
00076 
00077 byte gfp_mul(byte x, byte y)
00078    {
00079    if(x == 0 || y == 0)
00080       return 0;
00081    return RTSS_EXP[(RTSS_LOG[x] + RTSS_LOG[y]) % 255];
00082    }
00083 
00084 byte rtss_hash_id(const std::string& hash_name)
00085    {
00086    if(hash_name == "SHA-160")
00087       return 1;
00088    else if(hash_name == "SHA-256")
00089       return 2;
00090    else
00091       throw Invalid_Argument("RTSS only supports SHA-1 and SHA-256");
00092    }
00093 
00094 HashFunction* get_rtss_hash_by_id(byte id)
00095    {
00096    if(id == 1)
00097       return new SHA_160;
00098    else if(id == 2)
00099       return new SHA_256;
00100    else
00101       throw Decoding_Error("Bad RTSS hash identifier");
00102    }
00103 
00104 }
00105 
00106 RTSS_Share::RTSS_Share(const std::string& hex_input)
00107    {
00108    contents = hex_decode_locked(hex_input);
00109    }
00110 
00111 byte RTSS_Share::share_id() const
00112    {
00113    if(!initialized())
00114       throw Invalid_State("RTSS_Share::share_id not initialized");
00115 
00116    return contents[20];
00117    }
00118 
00119 std::string RTSS_Share::to_string() const
00120    {
00121    return hex_encode(&contents[0], contents.size());
00122    }
00123 
00124 std::vector<RTSS_Share>
00125 RTSS_Share::split(byte M, byte N,
00126                   const byte S[], u16bit S_len,
00127                   const byte identifier[16],
00128                   RandomNumberGenerator& rng)
00129    {
00130    if(M == 0 || N == 0 || M > N)
00131       throw Encoding_Error("RTSS_Share::split: M == 0 or N == 0 or M > N");
00132 
00133    SHA_256 hash; // always use SHA-256 when generating shares
00134 
00135    std::vector<RTSS_Share> shares(N);
00136 
00137    // Create RTSS header in each share
00138    for(byte i = 0; i != N; ++i)
00139       {
00140       shares[i].contents += std::make_pair(identifier, 16);
00141       shares[i].contents += rtss_hash_id(hash.name());
00142       shares[i].contents += M;
00143       shares[i].contents += get_byte(0, S_len);
00144       shares[i].contents += get_byte(1, S_len);
00145       }
00146 
00147    // Choose sequential values for X starting from 1
00148    for(byte i = 0; i != N; ++i)
00149       shares[i].contents.push_back(i+1);
00150 
00151    // secret = S || H(S)
00152    secure_vector<byte> secret(S, S + S_len);
00153    secret += hash.process(S, S_len);
00154 
00155    for(size_t i = 0; i != secret.size(); ++i)
00156       {
00157       std::vector<byte> coefficients(M-1);
00158       rng.randomize(&coefficients[0], coefficients.size());
00159 
00160       for(byte j = 0; j != N; ++j)
00161          {
00162          const byte X = j + 1;
00163 
00164          byte sum = secret[i];
00165          byte X_i = X;
00166 
00167          for(size_t k = 0; k != coefficients.size(); ++k)
00168             {
00169             sum ^= gfp_mul(X_i, coefficients[k]);
00170             X_i  = gfp_mul(X_i, X);
00171             }
00172 
00173          shares[j].contents.push_back(sum);
00174          }
00175       }
00176 
00177    return shares;
00178    }
00179 
00180 secure_vector<byte>
00181 RTSS_Share::reconstruct(const std::vector<RTSS_Share>& shares)
00182    {
00183    const size_t RTSS_HEADER_SIZE = 20;
00184 
00185    for(size_t i = 0; i != shares.size(); ++i)
00186       {
00187       if(shares[i].size() != shares[0].size())
00188          throw Decoding_Error("Different sized RTSS shares detected");
00189       if(shares[i].share_id() == 0)
00190          throw Decoding_Error("Invalid (id = 0) RTSS share detected");
00191       if(shares[i].size() < RTSS_HEADER_SIZE)
00192          throw Decoding_Error("Missing or malformed RTSS header");
00193 
00194       if(!same_mem(&shares[0].contents[0],
00195                    &shares[i].contents[0], RTSS_HEADER_SIZE))
00196          throw Decoding_Error("Different RTSS headers detected");
00197       }
00198 
00199    if(shares.size() < shares[0].contents[17])
00200       throw Decoding_Error("Insufficient shares to do TSS reconstruction");
00201 
00202    u16bit secret_len = make_u16bit(shares[0].contents[18],
00203                                    shares[0].contents[19]);
00204 
00205    byte hash_id = shares[0].contents[16];
00206 
00207    std::unique_ptr<HashFunction> hash(get_rtss_hash_by_id(hash_id));
00208 
00209    if(shares[0].size() != secret_len + hash->output_length() + RTSS_HEADER_SIZE + 1)
00210       throw Decoding_Error("Bad RTSS length field in header");
00211 
00212    std::vector<byte> V(shares.size());
00213    secure_vector<byte> secret;
00214 
00215    for(size_t i = RTSS_HEADER_SIZE + 1; i != shares[0].size(); ++i)
00216       {
00217       for(size_t j = 0; j != V.size(); ++j)
00218          V[j] = shares[j].contents[i];
00219 
00220       byte r = 0;
00221       for(size_t k = 0; k != shares.size(); ++k)
00222          {
00223          // L_i function:
00224          byte r2 = 1;
00225          for(size_t l = 0; l != shares.size(); ++l)
00226             {
00227             if(k == l)
00228                continue;
00229 
00230             byte share_k = shares[k].share_id();
00231             byte share_l = shares[l].share_id();
00232 
00233             if(share_k == share_l)
00234                throw Decoding_Error("Duplicate shares found in RTSS recovery");
00235 
00236             byte div = RTSS_EXP[(255 +
00237                                  RTSS_LOG[share_l] -
00238                                  RTSS_LOG[share_k ^ share_l]) % 255];
00239 
00240             r2 = gfp_mul(r2, div);
00241             }
00242 
00243          r ^= gfp_mul(V[k], r2);
00244          }
00245       secret.push_back(r);
00246       }
00247 
00248    if(secret.size() != secret_len + hash->output_length())
00249       throw Decoding_Error("Bad length in RTSS output");
00250 
00251    hash->update(&secret[0], secret_len);
00252    secure_vector<byte> hash_check = hash->final();
00253 
00254    if(!same_mem(&hash_check[0],
00255                 &secret[secret_len], hash->output_length()))
00256       throw Decoding_Error("RTSS hash check failed");
00257 
00258    return secure_vector<byte>(&secret[0], &secret[secret_len]);
00259    }
00260 
00261 }