botan.constructs.tss source code

1 /**
2 * RTSS (threshold secret sharing)
3 * 
4 * Copyright:
5 * (C) 2009 Jack Lloyd
6 * (C) 2014-2015 Etienne Cimon
7 *
8 * License:
9 * Botan is released under the Simplified BSD License (see LICENSE.md)
10 */
11 module botan.constructs.tss;
12 
13 import botan.constants;
14 static if (BOTAN_HAS_THRESHOLD_SECRET_SHARING && BOTAN_HAS_SHA1 && BOTAN_HAS_SHA2_32):
15 
16 import memutils.vector;
17 import botan.hash.hash;
18 import botan.rng.rng;
19 import botan.utils.loadstor;
20 import botan.filters.pipe;
21 import botan.codec.hex;
22 import botan.hash.sha2_32;
23 import botan.hash.sha160;
24 import botan.utils.types;
25 import botan.utils.exceptn;
26 import botan.utils.get_byte;
27 
28 /**
29 * A split secret, using the format from draft-mcgrew-tss-03
30 */
31 struct RTSS
32 {
33 public:
34     /**
35     * Params:
36     *  M = the number of shares needed to reconstruct
37     *  N = the number of shares generated
38     *  S = the secret to split
39     *  S_len = the length of the secret
40     *  identifier = the 16 ubyte share identifier
41     *  rng = the random number generator to use
42     */
43     static auto split(ubyte M, ubyte N,
44                              const(ubyte)* S, size_t S_len,
45                              in ubyte[16] identifier,
46                              RandomNumberGenerator rng)
47     {
48         if (M == 0 || N == 0 || M > N)
49             throw new EncodingError("split: M == 0 or N == 0 or M > N");
50         
51         Unique!SHA256 hash = new SHA256(); // always use SHA-256 when generating shares
52         Vector!RTSS shares = Vector!RTSS(N);
53         // Create RTSS header in each share
54         foreach (ubyte i; 0 .. N)
55         {
56             shares[i].m_contents = SecureArray!ubyte();
57             shares[i].m_contents ~= identifier.ptr[0 .. 16];
58             shares[i].m_contents ~= rtssHashId(hash.name);
59             shares[i].m_contents ~= M;
60             shares[i].m_contents ~= get_byte(6, S_len);
61             shares[i].m_contents ~= get_byte(7, S_len);
62         }
63         
64         // Choose sequential values for X starting from 1
65         foreach (ubyte i; 0 .. N)
66             shares[i].m_contents.pushBack(i+1);
67         
68         logTrace("pushed back");
69         // secret = S || H(S)
70         SecureVector!ubyte secret = SecureVector!ubyte(S[0 .. S_len]);
71         logTrace("secret");
72         secret ~= hash.process(S, S_len);
73         
74         logTrace("secret ", secret[]);
75         foreach (ubyte s; secret[])
76         {
77             Vector!ubyte coefficients = Vector!ubyte(M-1);
78             rng.randomize(coefficients.ptr, coefficients.length);
79             
80             foreach (ubyte j; 0 .. N)
81             {
82                 const ubyte X = cast(const ubyte) (j + 1);
83                 
84                 ubyte sum = s;
85                 ubyte X_i = X;
86                 
87                 foreach (coefficient; coefficients[])
88                 {
89                     sum ^= gfp_mul(X_i, coefficient);
90                     X_i  = gfp_mul(X_i, X);
91                 }
92                 
93                 shares[j].m_contents.pushBack(sum);
94             }
95         }
96         
97         return shares.move();
98     }
99 
100 
101     /**
102     * Params:
103     *  shares = the list of shares
104     */
105 
106     static SecureVector!ubyte reconstruct()(auto const ref Vector!RTSS shares)
107     {
108         __gshared immutable size_t RTSS_HEADER_SIZE = 20;
109         
110         foreach (ref share; shares[])
111         {
112             if (share.length != shares[0].length)
113                 throw new DecodingError("Different sized RTSS shares detected");
114             if (share.shareId() == 0)
115                 throw new DecodingError("Invalid (id = 0) RTSS share detected");
116             if (share.length < RTSS_HEADER_SIZE)
117                 throw new DecodingError("Missing or malformed RTSS header");
118             
119             if (!sameMem(&shares[0].m_contents[0], &share.m_contents[0], RTSS_HEADER_SIZE))
120                 throw new DecodingError("Different RTSS headers detected");
121         }
122         
123         if (shares.length < shares[0].m_contents[17])
124             throw new DecodingError("Insufficient shares to do TSS reconstruction");
125         
126         ushort secret_len = make_ushort(shares[0].m_contents[18], shares[0].m_contents[19]);
127         
128         ubyte hash_id = shares[0].m_contents[16];
129 
130         Unique!HashFunction hash = getRtssHashById(hash_id);
131         
132         if (shares[0].length != secret_len + hash.outputLength + RTSS_HEADER_SIZE + 1) {
133             hash.release();
134             assert(hash.outputLength > 0);
135             throw new DecodingError("Bad RTSS length field in header " ~ shares[0].length.to!string ~ " != " ~ (secret_len + hash.outputLength + RTSS_HEADER_SIZE + 1).to!string);
136         }
137         Vector!ubyte V = Vector!ubyte(shares.length);
138         SecureVector!ubyte secret = SecureVector!ubyte();
139         
140         foreach (size_t i; (RTSS_HEADER_SIZE + 1) .. shares[0].length)
141         {
142             foreach (size_t j; 0 .. V.length)
143                 V[j] = shares[j].m_contents[i];
144             
145             ubyte r = 0;
146             foreach (size_t k; 0 .. shares.length)
147             {
148                 // L_i function:
149                 ubyte r2 = 1;
150                 foreach (size_t l; 0 .. shares.length)
151                 {
152                     if (k == l)
153                         continue;
154                     
155                     ubyte share_k = shares[k].shareId();
156                     ubyte share_l = shares[l].shareId();
157                     
158                     if (share_k == share_l)
159                         throw new DecodingError("Duplicate shares found in RTSS recovery");
160                     
161                     ubyte div = RTSS_EXP[(255 + RTSS_LOG[share_l] - RTSS_LOG[share_k ^ share_l]) % 255];
162                     
163                     r2 = gfp_mul(r2, div);
164                 }
165                 
166                 r ^= gfp_mul(V[k], r2);
167             }
168             secret.pushBack(r);
169         }
170         
171         if (secret.length != secret_len + hash.outputLength)
172             throw new DecodingError("Bad length in RTSS output");
173         
174         hash.update(secret.ptr, secret_len);
175         SecureVector!ubyte hash_check = hash.finished();
176         
177         if (!sameMem(hash_check.ptr, &secret[secret_len], hash.outputLength))
178             throw new DecodingError("RTSS hash check failed");
179         secret.length = secret_len;
180         return secret;
181     }
182 
183 
184 
185     /**
186     * Params:
187     *  hex_input = the share encoded in hexadecimal
188     */
189     this(in string hex_input)
190     {
191         m_contents = SecureArray!ubyte(hexDecodeLocked(hex_input)[]);
192     }
193 
194 
195     /**
196     * Returns: hex representation
197     */
198     string toString() const
199     {
200         return hexEncode(m_contents.ptr, m_contents.length);
201     }
202 
203     /**
204     * Returns: share identifier
205     */
206     ubyte shareId() const
207     {
208         if (!initialized())
209             throw new InvalidState("shareId not initialized");
210         
211         return m_contents[20];
212     }
213 
214     /**
215     * Returns: size of this share in bytes
216     */
217     size_t size() const { return m_contents.length; }
218 
219     /// ditto
220     @property size_t length() const { return size(); }
221 
222     /**
223     * Returns: if this TSS share was initialized or not
224     */
225     bool initialized() const { return (m_contents.length > 0); }
226 private:
227     SecureArray!ubyte m_contents;
228 }
229 
230 
231 private:
232 
233 /**
234 Table for GF(2^8) arithmetic (exponentials)
235 */
236 __gshared immutable ubyte[256] RTSS_EXP = [
237     0x01, 0x03, 0x05, 0x0F, 0x11, 0x33, 0x55, 0xFF, 0x1A, 0x2E, 0x72,
238     0x96, 0xA1, 0xF8, 0x13, 0x35, 0x5F, 0xE1, 0x38, 0x48, 0xD8, 0x73,
239     0x95, 0xA4, 0xF7, 0x02, 0x06, 0x0A, 0x1E, 0x22, 0x66, 0xAA, 0xE5,
240     0x34, 0x5C, 0xE4, 0x37, 0x59, 0xEB, 0x26, 0x6A, 0xBE, 0xD9, 0x70,
241     0x90, 0xAB, 0xE6, 0x31, 0x53, 0xF5, 0x04, 0x0C, 0x14, 0x3C, 0x44,
242     0xCC, 0x4F, 0xD1, 0x68, 0xB8, 0xD3, 0x6E, 0xB2, 0xCD, 0x4C, 0xD4,
243     0x67, 0xA9, 0xE0, 0x3B, 0x4D, 0xD7, 0x62, 0xA6, 0xF1, 0x08, 0x18,
244     0x28, 0x78, 0x88, 0x83, 0x9E, 0xB9, 0xD0, 0x6B, 0xBD, 0xDC, 0x7F,
245     0x81, 0x98, 0xB3, 0xCE, 0x49, 0xDB, 0x76, 0x9A, 0xB5, 0xC4, 0x57,
246     0xF9, 0x10, 0x30, 0x50, 0xF0, 0x0B, 0x1D, 0x27, 0x69, 0xBB, 0xD6,
247     0x61, 0xA3, 0xFE, 0x19, 0x2B, 0x7D, 0x87, 0x92, 0xAD, 0xEC, 0x2F,
248     0x71, 0x93, 0xAE, 0xE9, 0x20, 0x60, 0xA0, 0xFB, 0x16, 0x3A, 0x4E,
249     0xD2, 0x6D, 0xB7, 0xC2, 0x5D, 0xE7, 0x32, 0x56, 0xFA, 0x15, 0x3F,
250     0x41, 0xC3, 0x5E, 0xE2, 0x3D, 0x47, 0xC9, 0x40, 0xC0, 0x5B, 0xED,
251     0x2C, 0x74, 0x9C, 0xBF, 0xDA, 0x75, 0x9F, 0xBA, 0xD5, 0x64, 0xAC,
252     0xEF, 0x2A, 0x7E, 0x82, 0x9D, 0xBC, 0xDF, 0x7A, 0x8E, 0x89, 0x80,
253     0x9B, 0xB6, 0xC1, 0x58, 0xE8, 0x23, 0x65, 0xAF, 0xEA, 0x25, 0x6F,
254     0xB1, 0xC8, 0x43, 0xC5, 0x54, 0xFC, 0x1F, 0x21, 0x63, 0xA5, 0xF4,
255     0x07, 0x09, 0x1B, 0x2D, 0x77, 0x99, 0xB0, 0xCB, 0x46, 0xCA, 0x45,
256     0xCF, 0x4A, 0xDE, 0x79, 0x8B, 0x86, 0x91, 0xA8, 0xE3, 0x3E, 0x42,
257     0xC6, 0x51, 0xF3, 0x0E, 0x12, 0x36, 0x5A, 0xEE, 0x29, 0x7B, 0x8D,
258     0x8C, 0x8F, 0x8A, 0x85, 0x94, 0xA7, 0xF2, 0x0D, 0x17, 0x39, 0x4B,
259     0xDD, 0x7C, 0x84, 0x97, 0xA2, 0xFD, 0x1C, 0x24, 0x6C, 0xB4, 0xC7,
260     0x52, 0xF6, 0x01 ];
261 
262 /**
263 Table for GF(2^8) arithmetic (logarithms)
264 */
265 __gshared immutable ubyte[] RTSS_LOG = [
266     0x90, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1A, 0xC6, 0x4B, 0xC7, 0x1B,
267     0x68, 0x33, 0xEE, 0xDF, 0x03, 0x64, 0x04, 0xE0, 0x0E, 0x34, 0x8D,
268     0x81, 0xEF, 0x4C, 0x71, 0x08, 0xC8, 0xF8, 0x69, 0x1C, 0xC1, 0x7D,
269     0xC2, 0x1D, 0xB5, 0xF9, 0xB9, 0x27, 0x6A, 0x4D, 0xE4, 0xA6, 0x72,
270     0x9A, 0xC9, 0x09, 0x78, 0x65, 0x2F, 0x8A, 0x05, 0x21, 0x0F, 0xE1,
271     0x24, 0x12, 0xF0, 0x82, 0x45, 0x35, 0x93, 0xDA, 0x8E, 0x96, 0x8F,
272     0xDB, 0xBD, 0x36, 0xD0, 0xCE, 0x94, 0x13, 0x5C, 0xD2, 0xF1, 0x40,
273     0x46, 0x83, 0x38, 0x66, 0xDD, 0xFD, 0x30, 0xBF, 0x06, 0x8B, 0x62,
274     0xB3, 0x25, 0xE2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7E, 0x6E, 0x48,
275     0xC3, 0xA3, 0xB6, 0x1E, 0x42, 0x3A, 0x6B, 0x28, 0x54, 0xFA, 0x85,
276     0x3D, 0xBA, 0x2B, 0x79, 0x0A, 0x15, 0x9B, 0x9F, 0x5E, 0xCA, 0x4E,
277     0xD4, 0xAC, 0xE5, 0xF3, 0x73, 0xA7, 0x57, 0xAF, 0x58, 0xA8, 0x50,
278     0xF4, 0xEA, 0xD6, 0x74, 0x4F, 0xAE, 0xE9, 0xD5, 0xE7, 0xE6, 0xAD,
279     0xE8, 0x2C, 0xD7, 0x75, 0x7A, 0xEB, 0x16, 0x0B, 0xF5, 0x59, 0xCB,
280     0x5F, 0xB0, 0x9C, 0xA9, 0x51, 0xA0, 0x7F, 0x0C, 0xF6, 0x6F, 0x17,
281     0xC4, 0x49, 0xEC, 0xD8, 0x43, 0x1F, 0x2D, 0xA4, 0x76, 0x7B, 0xB7,
282     0xCC, 0xBB, 0x3E, 0x5A, 0xFB, 0x60, 0xB1, 0x86, 0x3B, 0x52, 0xA1,
283     0x6C, 0xAA, 0x55, 0x29, 0x9D, 0x97, 0xB2, 0x87, 0x90, 0x61, 0xBE,
284     0xDC, 0xFC, 0xBC, 0x95, 0xCF, 0xCD, 0x37, 0x3F, 0x5B, 0xD1, 0x53,
285     0x39, 0x84, 0x3C, 0x41, 0xA2, 0x6D, 0x47, 0x14, 0x2A, 0x9E, 0x5D,
286     0x56, 0xF2, 0xD3, 0xAB, 0x44, 0x11, 0x92, 0xD9, 0x23, 0x20, 0x2E,
287     0x89, 0xB4, 0x7C, 0xB8, 0x26, 0x77, 0x99, 0xE3, 0xA5, 0x67, 0x4A,
288     0xED, 0xDE, 0xC5, 0x31, 0xFE, 0x18, 0x0D, 0x63, 0x8C, 0x80, 0xC0,
289     0xF7, 0x70, 0x07 ];
290 
291 ubyte gfp_mul(ubyte x, ubyte y)
292 {
293     if (x == 0 || y == 0)
294         return 0;
295     return RTSS_EXP[(RTSS_LOG[x] + RTSS_LOG[y]) % 255];
296 }
297 
298 ubyte rtssHashId(in string hash_name)
299 {
300     if (hash_name == "SHA-160")
301         return 1;
302     else if (hash_name == "SHA-256")
303         return 2;
304     else
305         throw new InvalidArgument("RTSS only supports SHA-1 and SHA-256");
306 }
307 
308 HashFunction getRtssHashById(ubyte id)
309 {
310     if (id == 1)
311         return new SHA160;
312     else if (id == 2)
313         return new SHA256;
314     else
315         throw new DecodingError("Bad RTSS hash identifier");
316 }
317 
318 static if (BOTAN_TEST):
319 import botan.test;
320 import botan.rng.auto_rng;
321 import botan.codec.hex;
322 
323 static if (BOTAN_HAS_TESTS && !SKIP_TSS_TEST) unittest
324 {
325     logDebug("Testing tss.d ...");
326 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
327     
328     size_t fails = 0;
329     
330     ubyte[16] id;
331     for(int i = 0; i != 16; ++i)
332         id[i] = cast(ubyte)i;
333     
334     const SecureVector!ubyte S = hexDecodeLocked("7465737400");
335     logTrace("Split TSS: ", S[]);
336     Vector!RTSS shares = RTSS.split(cast(ubyte)2, cast(ubyte)4, cast(const(ubyte)*)&S[0], S.length, id, *rng);
337     logTrace("Reconstruct TSS");
338     auto back = RTSS.reconstruct(shares);
339     
340     if (S != back)
341     {
342         logTrace("TSS-0: " ~ hexEncode(S) ~ " != " ~ hexEncode(back));
343         ++fails;
344     }
345     Object ta;
346     shares.resize(shares.length-1);
347     
348     back = RTSS.reconstruct(shares);
349     
350     if (S != back)
351     {
352         logTrace("TSS-1: " ~ hexEncode(S) ~ " != " ~ hexEncode(back));
353         ++fails;
354     }
355     
356     testReport("tss", 2, fails);
357 }