Botan
1.11.15
|
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 }