Electroneum
electrum-words.cpp
Go to the documentation of this file.
1 // Copyrights(c) 2017-2021, The Electroneum Project
2 // Copyrights(c) 2014-2019, The Monero Project
3 //
4 // All rights reserved.
5 //
6 // Redistribution and use in source and binary forms, with or without modification, are
7 // permitted provided that the following conditions are met:
8 //
9 // 1. Redistributions of source code must retain the above copyright notice, this list of
10 // conditions and the following disclaimer.
11 //
12 // 2. Redistributions in binary form must reproduce the above copyright notice, this list
13 // of conditions and the following disclaimer in the documentation and/or other
14 // materials provided with the distribution.
15 //
16 // 3. Neither the name of the copyright holder nor the names of its contributors may be
17 // used to endorse or promote products derived from this software without specific
18 // prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
21 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
22 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
40 #include <string>
41 #include <cstdint>
42 #include <vector>
43 #include <unordered_map>
44 #include "wipeable_string.h"
45 #include "misc_language.h"
46 #include "int-util.h"
48 #include <boost/crc.hpp>
49 
50 #include "chinese_simplified.h"
51 #include "english.h"
52 #include "dutch.h"
53 #include "french.h"
54 #include "italian.h"
55 #include "german.h"
56 #include "spanish.h"
57 #include "portuguese.h"
58 #include "japanese.h"
59 #include "russian.h"
60 #include "esperanto.h"
61 #include "lojban.h"
62 #include "english_old.h"
63 #include "language_base.h"
64 #include "singleton.h"
65 
66 #undef ELECTRONEUM_DEFAULT_LOG_CATEGORY
67 #define ELECTRONEUM_DEFAULT_LOG_CATEGORY "mnemonic"
68 
69 namespace crypto
70 {
71  namespace ElectrumWords
72  {
73  std::vector<const Language::Base*> get_language_list();
74  }
75 }
76 
77 namespace
78 {
79  uint32_t create_checksum_index(const std::vector<epee::wipeable_string> &word_list,
80  const Language::Base *language);
81  bool checksum_test(std::vector<epee::wipeable_string> seed, const Language::Base *language);
82 
92  bool find_seed_language(const std::vector<epee::wipeable_string> &seed,
93  bool has_checksum, std::vector<uint32_t> &matched_indices, Language::Base **language)
94  {
95  // If there's a new language added, add an instance of it here.
96  std::vector<Language::Base*> language_instances({
110  });
111  Language::Base *fallback = NULL;
112 
113  std::vector<epee::wipeable_string>::const_iterator it2;
114  matched_indices.reserve(seed.size());
115 
116  // Iterate through all the languages and find a match
117  for (std::vector<Language::Base*>::iterator it1 = language_instances.begin();
118  it1 != language_instances.end(); it1++)
119  {
120  const std::unordered_map<epee::wipeable_string, uint32_t, Language::WordHash, Language::WordEqual> &word_map = (*it1)->get_word_map();
121  const std::unordered_map<epee::wipeable_string, uint32_t, Language::WordHash, Language::WordEqual> &trimmed_word_map = (*it1)->get_trimmed_word_map();
122  // To iterate through seed words
123  bool full_match = true;
124 
125  epee::wipeable_string trimmed_word;
126  // Iterate through all the words and see if they're all present
127  for (it2 = seed.begin(); it2 != seed.end(); it2++)
128  {
129  if (has_checksum)
130  {
131  trimmed_word = Language::utf8prefix(*it2, (*it1)->get_unique_prefix_length());
132  // Use the trimmed words and map
133  if (trimmed_word_map.count(trimmed_word) == 0)
134  {
135  full_match = false;
136  break;
137  }
138  matched_indices.push_back(trimmed_word_map.at(trimmed_word));
139  }
140  else
141  {
142  if (word_map.count(*it2) == 0)
143  {
144  full_match = false;
145  break;
146  }
147  matched_indices.push_back(word_map.at(*it2));
148  }
149  }
150  if (full_match)
151  {
152  // if we were using prefix only, and we have a checksum, check it now
153  // to avoid false positives due to prefix set being too common
154  if (has_checksum)
155  if (!checksum_test(seed, *it1))
156  {
157  fallback = *it1;
158  full_match = false;
159  }
160  }
161  if (full_match)
162  {
163  *language = *it1;
164  MINFO("Full match for language " << (*language)->get_english_language_name());
165  return true;
166  }
167  // Some didn't match. Clear the index array.
168  memwipe(matched_indices.data(), matched_indices.size() * sizeof(matched_indices[0]));
169  matched_indices.clear();
170  }
171 
172  // if we get there, we've not found a good match, but we might have a fallback,
173  // if we detected a match which did not fit the checksum, which might be a badly
174  // typed/transcribed seed in the right language
175  if (fallback)
176  {
177  *language = fallback;
178  MINFO("Fallback match for language " << (*language)->get_english_language_name());
179  return true;
180  }
181 
182  MINFO("No match found");
183  memwipe(matched_indices.data(), matched_indices.size() * sizeof(matched_indices[0]));
184  return false;
185  }
186 
193  uint32_t create_checksum_index(const std::vector<epee::wipeable_string> &word_list,
194  const Language::Base *language)
195  {
196  epee::wipeable_string trimmed_words = "", word;
197 
198  const auto &word_map = language->get_word_map();
199  const auto &trimmed_word_map = language->get_trimmed_word_map();
200  const uint32_t unique_prefix_length = language->get_unique_prefix_length();
201  for (std::vector<epee::wipeable_string>::const_iterator it = word_list.begin(); it != word_list.end(); it++)
202  {
203  word = Language::utf8prefix(*it, unique_prefix_length);
204  auto it2 = trimmed_word_map.find(word);
205  if (it2 == trimmed_word_map.end())
206  throw std::runtime_error("Word \"" + std::string(word.data(), word.size()) + "\" not found in trimmed word map in " + language->get_english_language_name());
207  trimmed_words += it2->first;
208  }
209  boost::crc_32_type result;
210  result.process_bytes(trimmed_words.data(), trimmed_words.length());
211  return result.checksum() % word_list.size();
212  }
213 
220  bool checksum_test(std::vector<epee::wipeable_string> seed, const Language::Base *language)
221  {
222  if (seed.empty())
223  return false;
224  // The last word is the checksum.
225  epee::wipeable_string last_word = seed.back();
226  seed.pop_back();
227 
228  const uint32_t unique_prefix_length = language->get_unique_prefix_length();
229 
230  auto idx = create_checksum_index(seed, language);
231  epee::wipeable_string checksum = seed[idx];
232 
233  epee::wipeable_string trimmed_checksum = checksum.length() > unique_prefix_length ? Language::utf8prefix(checksum, unique_prefix_length) :
234  checksum;
235  epee::wipeable_string trimmed_last_word = last_word.length() > unique_prefix_length ? Language::utf8prefix(last_word, unique_prefix_length) :
236  last_word;
237  bool ret = Language::WordEqual()(trimmed_checksum, trimmed_last_word);
238  MINFO("Checksum is " << (ret ? "valid" : "invalid"));
239  return ret;
240  }
241 }
242 
248 namespace crypto
249 {
255  namespace ElectrumWords
256  {
266  bool words_to_bytes(const epee::wipeable_string &words, epee::wipeable_string& dst, size_t len, bool duplicate,
267  std::string &language_name)
268  {
269  std::vector<epee::wipeable_string> seed;
270 
271  words.split(seed);
272 
273  if (len % 4)
274  {
275  MERROR("Invalid seed: not a multiple of 4");
276  return false;
277  }
278 
279  bool has_checksum = true;
280  if (len)
281  {
282  // error on non-compliant word list
283  const size_t expected = len * 8 * 3 / 32;
284  if (seed.size() != expected/2 && seed.size() != expected &&
285  seed.size() != expected + 1)
286  {
287  MERROR("Invalid seed: unexpected number of words");
288  return false;
289  }
290 
291  // If it is seed with a checksum.
292  has_checksum = seed.size() == (expected + 1);
293  }
294 
295  std::vector<uint32_t> matched_indices;
296  auto wiper = epee::misc_utils::create_scope_leave_handler([&](){memwipe(matched_indices.data(), matched_indices.size() * sizeof(matched_indices[0]));});
297  Language::Base *language;
298  if (!find_seed_language(seed, has_checksum, matched_indices, &language))
299  {
300  MERROR("Invalid seed: language not found");
301  return false;
302  }
303  language_name = language->get_language_name();
304  uint32_t word_list_length = language->get_word_list().size();
305 
306  if (has_checksum)
307  {
308  if (!checksum_test(seed, language))
309  {
310  // Checksum fail
311  MERROR("Invalid seed: invalid checksum");
312  return false;
313  }
314  seed.pop_back();
315  }
316 
317  for (unsigned int i=0; i < seed.size() / 3; i++)
318  {
319  uint32_t w[4];
320  w[1] = matched_indices[i*3];
321  w[2] = matched_indices[i*3 + 1];
322  w[3] = matched_indices[i*3 + 2];
323 
324  w[0]= w[1] + word_list_length * (((word_list_length - w[1]) + w[2]) % word_list_length) +
325  word_list_length * word_list_length * (((word_list_length - w[2]) + w[3]) % word_list_length);
326 
327  if (!(w[0]% word_list_length == w[1]))
328  {
329  memwipe(w, sizeof(w));
330  MERROR("Invalid seed: mumble mumble");
331  return false;
332  }
333 
334  w[0] = SWAP32LE(w[0]);
335  dst.append((const char*)&w[0], 4); // copy 4 bytes to position
336  memwipe(w, sizeof(w));
337  }
338 
339  if (len > 0 && duplicate)
340  {
341  const size_t expected = len * 3 / 32;
342  if (seed.size() == expected/2)
343  {
344  dst.append(dst.data(), dst.size()); // if electrum 12-word seed, duplicate
345  }
346  }
347 
348  return true;
349  }
350 
359  std::string &language_name)
360  {
362  if (!words_to_bytes(words, s, sizeof(dst), true, language_name))
363  {
364  MERROR("Invalid seed: failed to convert words to bytes");
365  return false;
366  }
367  if (s.size() != sizeof(dst))
368  {
369  MERROR("Invalid seed: wrong output size");
370  return false;
371  }
372  dst = *(const crypto::secret_key*)s.data();
373  return true;
374  }
375 
383  bool bytes_to_words(const char *src, size_t len, epee::wipeable_string& words,
384  const std::string &language_name)
385  {
386 
387  if (len % 4 != 0 || len == 0) return false;
388 
389  const Language::Base *language = NULL;
390  const std::vector<const Language::Base*> language_list = crypto::ElectrumWords::get_language_list();
391  for (const Language::Base *l: language_list)
392  {
393  if (language_name == l->get_language_name() || language_name == l->get_english_language_name())
394  language = l;
395  }
396  if (!language)
397  {
398  return false;
399  }
400  const std::vector<std::string> &word_list = language->get_word_list();
401  // To store the words for random access to add the checksum word later.
402  std::vector<epee::wipeable_string> words_store;
403 
404  uint32_t word_list_length = word_list.size();
405  // 4 bytes -> 3 words. 8 digits base 16 -> 3 digits base 1626
406  for (unsigned int i=0; i < len/4; i++, words.push_back(' '))
407  {
408  uint32_t w[4];
409 
410  w[0] = SWAP32LE(*(const uint32_t*)(src + (i * 4)));
411 
412  w[1] = w[0] % word_list_length;
413  w[2] = ((w[0] / word_list_length) + w[1]) % word_list_length;
414  w[3] = (((w[0] / word_list_length) / word_list_length) + w[2]) % word_list_length;
415 
416  words += word_list[w[1]];
417  words += ' ';
418  words += word_list[w[2]];
419  words += ' ';
420  words += word_list[w[3]];
421 
422  words_store.push_back(word_list[w[1]]);
423  words_store.push_back(word_list[w[2]]);
424  words_store.push_back(word_list[w[3]]);
425 
426  memwipe(w, sizeof(w));
427  }
428 
429  words += words_store[create_checksum_index(words_store, language)];
430  return true;
431  }
432 
434  const std::string &language_name)
435  {
436  return bytes_to_words(src.data, sizeof(src), words, language_name);
437  }
438 
439  std::vector<const Language::Base*> get_language_list()
440  {
441  static const std::vector<const Language::Base*> language_instances({
454  });
455  return language_instances;
456  }
457 
462  void get_language_list(std::vector<std::string> &languages, bool english)
463  {
464  const std::vector<const Language::Base*> language_instances = get_language_list();
465  for (std::vector<const Language::Base*>::const_iterator it = language_instances.begin();
466  it != language_instances.end(); it++)
467  {
468  languages.push_back(english ? (*it)->get_english_language_name() : (*it)->get_language_name());
469  }
470  }
471 
478  {
479  std::vector<epee::wipeable_string> word_list;
480  seed.split(word_list);
481  return word_list.size() != (seed_length + 1);
482  }
483 
485  {
486  const std::vector<const Language::Base*> language_instances = get_language_list();
487  for (std::vector<const Language::Base*>::const_iterator it = language_instances.begin();
488  it != language_instances.end(); it++)
489  {
490  if ((*it)->get_language_name() == name)
491  return (*it)->get_english_language_name();
492  }
493  return "<language not found>";
494  }
495 
496  }
497 
498 }
#define MERROR(x)
Definition: misc_log_ex.h:73
Portuguese word list and map.
const std::vector< std::string > & get_word_list() const
Returns a pointer to the word list.
A singleton helper class based on template.
French word list and map.
size_t size() const noexcept
std::vector< const Language::Base * > get_language_list()
#define MINFO(x)
Definition: misc_log_ex.h:75
New Dutch word list and map.
::std::string string
Definition: gtest-port.h:1097
auto_scope_leave_caller create_scope_leave_handler(t_scope_leave_handler f)
crypto namespace.
Definition: crypto.cpp:58
static T * instance()
Definition: singleton.h:57
bool words_to_bytes(const epee::wipeable_string &words, epee::wipeable_string &dst, size_t len, bool duplicate, std::string &language_name)
Converts seed words to bytes (secret key).
A base language class which all languages have to inherit from for Polymorphism.
const char * name
void append(const char *ptr, size_t len)
const std::unordered_map< epee::wipeable_string, uint32_t, WordHash, WordEqual > & get_trimmed_word_map() const
Returns a pointer to the trimmed word map.
Language Base class for Polymorphism.
Russian word list and map.
New Esperanto word list and map.
size_t length() const noexcept
void split(std::vector< wipeable_string > &fields) const
const std::unordered_map< epee::wipeable_string, uint32_t, WordHash, WordEqual > & get_word_map() const
Returns a pointer to the word map.
bool bytes_to_words(const char *src, size_t len, epee::wipeable_string &words, const std::string &language_name)
Converts bytes (secret key) to seed words.
Italian word list and map.
unsigned int uint32_t
Definition: stdint.h:126
German word list and map.
Japanese word list and map.
Older version of English word list and map.
Spanish word list and map.
std::string get_english_name_for(const std::string &name)
Returns the name of a language in English.
New English word list and map.
New Lojban word list and map.
Mnemonic seed generation and wallet restoration from them.
const std::string & get_english_language_name() const
Returns the name of the language in English.
bool get_is_old_style_seed(const epee::wipeable_string &seed)
Tells if the seed passed is an old style seed or not.
void * memwipe(void *src, size_t n)
const char * data() const noexcept
uint32_t get_unique_prefix_length() const
Returns the number of unique starting characters to be used for matching.
Simplified Chinese word list and map.
#define SWAP32LE
Definition: int-util.h:244
T utf8prefix(const T &s, size_t count)
Returns a string made of (at most) the first count characters in s. Assumes well formedness. No check is made for this.
Definition: language_base.h:60