1 /** 
2 * Key-pair recovery generator
3 */
4 module tagion.wallet.KeyRecover;
5 
6 import std.algorithm.iteration : filter, map;
7 import std.algorithm.mutation : copy;
8 import std.array : array;
9 import std.range : StoppingPolicy, indexed, iota, lockstep;
10 import std.string : representation;
11 import tagion.basic.Message;
12 import tagion.basic.Types : Buffer;
13 import tagion.basic.tagionexceptions : Check;
14 import tagion.crypto.SecureInterfaceNet : HashNet;
15 import tagion.crypto.random.random;
16 import tagion.hibon.Document : Document;
17 import tagion.hibon.HiBON : HiBON;
18 import tagion.hibon.HiBONRecord;
19 import tagion.utils.Miscellaneous : xor;
20 import tagion.wallet.Basic : saltHash;
21 import tagion.wallet.WalletException : KeyRecoverException;
22 import tagion.wallet.WalletRecords : RecoverGenerator;
23 
24 alias check = Check!KeyRecoverException;
25 
26 /**
27  * Key-pair recovery generator
28  */
29 @safe
30 struct KeyRecover {
31     enum MAX_QUESTION = 10;
32     enum MAX_SEEDS = 64;
33     const HashNet net;
34     RecoverGenerator generator;
35 
36     /**
37      * 
38      * Params:
39      *   net = hash used by the recovery
40      */
41     @nogc
42     this(const HashNet net) pure nothrow {
43         this.net = net;
44     }
45 
46     /**
47      * 
48      * Params:
49      *   net = hash used by the recovery 
50      *   doc = document of the recovery generator 
51 
52      */
53     this(const HashNet net, Document doc) {
54         this.net = net;
55         generator = RecoverGenerator(doc);
56     }
57 
58     /**
59      * 
60      * Params:
61      *   net = hash used by the recovery
62      *   generator = the recover generator  
63      */
64     this(const HashNet net, RecoverGenerator generator) {
65         this.net = net;
66         this.generator = generator;
67     }
68 
69     /**
70      * 
71      * Returns: the document of the generator
72      */
73     const(Document) toDoc() const {
74         return generator.toDoc;
75     }
76 
77     /**
78      * Generates the quiz hash of the from a list of questions and answers
79      * 
80      * Params:
81      *   questions = List of questions 
82      *   answers = List for answers
83      * Returns: List of common hashs of question and answers
84      */
85     immutable(ubyte)[][] quiz(scope const(string[]) questions, scope const(char[][]) answers) const @trusted
86     in {
87         assert(questions.length is answers.length);
88     }
89     do {
90         auto results = new Buffer[questions.length];
91         foreach (ref result, question, answer; lockstep(results, questions, answers,
92                 StoppingPolicy.requireSameLength)) {
93             scope strip_down = cast(ubyte[]) answer.strip_down;
94             scope answer_hash = net.rawCalcHash(strip_down);
95             scope question_hash = net.rawCalcHash(question.representation);
96             result = net.rawCalcHash(answer_hash ~ question_hash);
97         }
98         return results;
99     }
100 
101     /**
102      * Total number of combination of possible seed value
103      * Params:
104      *   M = number of question 
105      *   N = confidence
106      * Returns: totol number of combinations
107      */
108     @nogc
109     static uint numberOfSeeds(const uint M, const uint N) pure nothrow
110     in {
111         assert(M >= N);
112         assert(M <= 10);
113     }
114     do {
115         return (M - N) * N + 1;
116     }
117 
118     @nogc
119     static unittest {
120         assert(numberOfSeeds(10, 5) is 26);
121     }
122 
123     static void iterateSeeds(
124             const uint M,
125             const uint N,
126             scope void delegate(scope const(uint[]) indices) @safe dg) {
127         scope include = new uint[N];
128         iota(N).copy(include);
129         void local_search(const int index, const int size) @safe {
130             if (index >= 0) {
131                 dg(include);
132                 pragma(msg, "review(cbr): Side channel attack fixed");
133                 if (include[index] < size) {
134                     include[index]++;
135                     local_search(index, size);
136                 }
137                 else if (index > 0) {
138                     include[index - 1]++;
139                     local_search(index - 1, size - 1);
140                 }
141             }
142         }
143 
144         local_search(cast(int) include.length - 1, M - 1);
145     }
146 
147     /**
148      * Creates the key-pair
149      * Params:
150      *   questions = List of question 
151      *   answers = List of answers
152      *   confidence = Confidence of the answers
153      */
154     void createKey(
155             scope const(string[]) questions,
156             scope const(char[][]) answers,
157             const uint confidence) {
158         createKey(quiz(questions, answers), confidence);
159     }
160 
161     /**
162      * Ditto except is uses a list of hashes
163      * This can be used of something else than quiz is used
164      * Params:
165      *   A = List of hashes
166      *   confidence = confidence
167      */
168     void createKey(
169             scope const(ubyte[][]) A,
170             const uint confidence) {
171         scope R = new ubyte[net.hashSize];
172         getRandom(R);
173         scope (exit) {
174             R[] = 0;
175         }
176         quizSeed(R, A, confidence);
177     }
178 
179     /**
180      * Generates the quiz seed values from the privat key R and the quiz list
181      * 
182      * Params:
183      *   R = generated private-key
184      *   A = List of hashes
185      *   confidence = number of minimum correct answern
186      */
187     void quizSeed(scope ref const(ubyte[]) R,
188             scope const(ubyte[][]) A,
189             const uint confidence) {
190         scope (success) {
191             generator.confidence = confidence;
192             generator.S = net.saltHash(R);
193         }
194         scope (failure) {
195             generator.Y = null;
196             generator.S = null;
197             generator.confidence = 0;
198         }
199         check(A.length > 1, message("Number of questions must be more than one"));
200         check(confidence <= A.length, message(
201                 "Number qustions must be lower than or equal to the confidence level (M=%d and N=%d)",
202                 A.length, confidence));
203         check(A.length <= MAX_QUESTION, message("Mumber of question is %d but it should not exceed %d",
204                 A.length, MAX_QUESTION));
205         const number_of_questions = cast(uint) A.length;
206         const seeds = numberOfSeeds(number_of_questions, confidence);
207         check(seeds <= MAX_SEEDS, message("Number quiz-seeds is %d which exceed that max value of %d",
208                 seeds, MAX_SEEDS));
209         generator.Y = new Buffer[seeds];
210         uint count;
211         void calculate_this_seeds(scope const(uint[]) indices) @safe {
212             scope list_of_selected_answers_and_the_secret = indexed(A, indices);
213             pragma(msg, "review(cbr): Recovery now used Y_a = R x H(A_a) instead of Y_a = R x H(A_a)");
214 
215             generator.Y[count] = xor(R, net.rawCalcHash(
216                     xor(list_of_selected_answers_and_the_secret)));
217             count++;
218         }
219 
220         iterateSeeds(number_of_questions, confidence, &calculate_this_seeds);
221     }
222 
223     /**
224      * Generate the private-key from quiz (correct answers)
225      * Params:
226      *   R = generated private-key
227      *   questions = list of questions
228      *   answers = list of answers
229      * Returns: true if it was successfully
230      */
231     bool findSecret(
232             scope ref ubyte[] R,
233             scope const(string[]) questions,
234             scope const(char[][]) answers) const {
235         return findSecret(R, quiz(questions, answers));
236     }
237 
238     /** 
239      * Recover the private-key from the hash-list A
240      * The hash-list is usually the question+answers hash 
241      * Params:
242      *   R = Private-key
243      *   A = List of hashes 
244      * Returns: true if it was successfully
245      */
246     bool findSecret(scope ref ubyte[] R, Buffer[] A) const {
247         check(A.length > 1, message("Number of questions must be more than one"));
248         check(generator.confidence <= A.length,
249                 message("Number qustions must be lower than or equal to the confidence level (M=%d and N=%d)",
250                 A.length, generator.confidence));
251         const number_of_questions = cast(uint) A.length;
252         const seeds = numberOfSeeds(number_of_questions, generator.confidence);
253         import std.traits;
254         import std.range;
255 
256         bool result;
257         void search_for_the_secret(scope const(uint[]) indices) @safe {
258             scope list_of_selected_answers_and_the_secret = indexed(A, indices);
259             const guess = net.rawCalcHash(xor(list_of_selected_answers_and_the_secret));
260             scope _R = new ubyte[net.hashSize];
261             foreach (y; generator.Y) {
262                 xor(_R, y, guess);
263                 pragma(msg, "review(cbr): constant time on a equal - sidechannel attack");
264                 if (generator.S == net.saltHash(_R)) {
265                     _R.copy(R);
266                     result = true;
267                 }
268             }
269         }
270 
271         pragma(msg, "review(cbr): Constant time - sidechannel attack");
272         iterateSeeds(number_of_questions, generator.confidence, &search_for_the_secret);
273         return result;
274     }
275 }
276 
277 /**
278  * Strip down question and answer
279  * Converts the string to lower-case and takes only letters and numbers
280  * Params:
281  *   text = 
282  * Returns: stripped text
283  */
284 char[] strip_down(const(char[]) text) pure @safe
285 out (result) {
286     assert(result.length > 0);
287 }
288 do {
289     import std.ascii : isAlphaNum, toLower;
290 
291     return text
292         .map!(c => cast(char) toLower(c))
293         .filter!(c => isAlphaNum(c))
294         .array;
295 }
296 
297 static immutable standard_questions = [
298     "What is your favorite book?",
299     "What is the name of the road you grew up on?",
300     "What is your mother’s maiden name?",
301     "What was the name of your first/current/favorite pet?",
302     "What was the first company that you worked for?",
303     "Where did you meet your spouse?",
304     "Where did you go to high school/college?",
305     "What is your favorite food?",
306     "What city were you born in?",
307     "Where is your favorite place to vacation?"
308 ];
309 
310 ///
311 unittest {
312     import std.array : join;
313     import tagion.crypto.SecureNet : StdHashNet;
314 
315     auto selected_questions = indexed(standard_questions, [0, 2, 3, 7, 8]).array.idup;
316     string[] answers = [
317         "mobidick",
318         "Mother Teresa!",
319         "Pluto",
320         "Pizza",
321         "Maputo"
322     ];
323     const net = new StdHashNet;
324     auto recover = KeyRecover(net);
325     recover.createKey(selected_questions, answers, 3);
326 
327     auto R = new ubyte[net.hashSize];
328 
329     { // All the ansers are correct
330         const result = recover.findSecret(R, selected_questions, answers);
331         assert(R.length == net.hashSize);
332         assert(result); // Password found
333     }
334 
335     { // 3 out of 5 answers are correct. This is a valid answer to generate the secret key
336         string[] good_answers = [
337             "MobiDick",
338             "MOTHER TERESA",
339             "Fido",
340             "pizza",
341             "Maputo"
342         ];
343         auto goodR = new ubyte[net.hashSize];
344         const result = recover.findSecret(goodR, selected_questions, good_answers);
345         assert(R.length == net.hashSize);
346         assert(result); // Password found
347         assert(R == goodR);
348     }
349 
350     { // 2 out of 5 answers are correct. This is NOT a valid answer to generate the secret key
351         string[] bad_answers = [
352             "mobidick",
353             "Monalisa",
354             "Fido",
355             "Burger",
356             "Maputo"
357         ];
358         auto badR = new ubyte[net.hashSize];
359         const result = recover.findSecret(badR, selected_questions, bad_answers);
360         assert(!result); // Password not found
361         assert(R != badR);
362 
363     }
364 }