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 }