1
0
mirror of https://github.com/trezor/trezor-firmware.git synced 2024-12-04 21:48:17 +00:00
trezor-firmware/crypto/bip39.c

287 lines
7.9 KiB
C
Raw Permalink Normal View History

2014-05-22 18:54:58 +00:00
/**
* Copyright (c) 2013-2014 Tomas Dzetkulic
* Copyright (c) 2013-2014 Pavol Rusnak
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES
* OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
2016-01-19 14:11:57 +00:00
#include <stdbool.h>
#include <string.h>
2013-11-08 00:24:47 +00:00
#include "bip39.h"
2013-11-25 21:46:54 +00:00
#include "hmac.h"
#include "memzero.h"
#include "options.h"
#include "pbkdf2.h"
2013-11-25 21:46:54 +00:00
#include "rand.h"
2013-11-08 00:24:47 +00:00
#include "sha2.h"
2016-01-19 14:11:57 +00:00
#if USE_BIP39_CACHE
static int bip39_cache_index = 0;
static CONFIDENTIAL struct {
bool set;
char mnemonic[256];
char passphrase[64];
uint8_t seed[512 / 8];
2016-01-19 14:11:57 +00:00
} bip39_cache[BIP39_CACHE_SIZE];
void bip39_cache_clear(void) {
memzero(bip39_cache, sizeof(bip39_cache));
bip39_cache_index = 0;
}
2016-01-19 14:11:57 +00:00
#endif
2013-11-08 00:24:47 +00:00
const char *mnemonic_generate(int strength) {
if (strength % 32 || strength < 128 || strength > 256) {
return 0;
}
uint8_t data[32] = {0};
random_buffer(data, 32);
const char *r = mnemonic_from_data(data, strength / 8);
memzero(data, sizeof(data));
return r;
2013-11-08 00:24:47 +00:00
}
static CONFIDENTIAL char mnemo[24 * 10];
const char *mnemonic_from_data(const uint8_t *data, int len) {
if (len % 4 || len < 16 || len > 32) {
return 0;
}
uint8_t bits[32 + 1] = {0};
sha256_Raw(data, len, bits);
// checksum
bits[len] = bits[0];
// data
memcpy(bits, data, len);
int mlen = len * 3 / 4;
int i = 0, j = 0, idx = 0;
char *p = mnemo;
for (i = 0; i < mlen; i++) {
idx = 0;
for (j = 0; j < 11; j++) {
idx <<= 1;
idx += (bits[(i * 11 + j) / 8] & (1 << (7 - ((i * 11 + j) % 8)))) > 0;
}
2022-05-30 09:13:24 +00:00
strcpy(p, BIP39_WORDLIST_ENGLISH[idx]);
p += strlen(BIP39_WORDLIST_ENGLISH[idx]);
*p = (i < mlen - 1) ? ' ' : 0;
p++;
}
memzero(bits, sizeof(bits));
return mnemo;
2013-11-08 00:24:47 +00:00
}
void mnemonic_clear(void) { memzero(mnemo, sizeof(mnemo)); }
int mnemonic_to_bits(const char *mnemonic, uint8_t *bits) {
if (!mnemonic) {
return 0;
}
uint32_t i = 0, n = 0;
while (mnemonic[i]) {
if (mnemonic[i] == ' ') {
n++;
}
i++;
}
n++;
// check that number of words is valid for BIP-39:
// (a) between 128 and 256 bits of initial entropy (12 - 24 words)
// (b) number of bits divisible by 33 (1 checksum bit per 32 input bits)
// - that is, (n * 11) % 33 == 0, so n % 3 == 0
if (n < 12 || n > 24 || (n % 3)) {
return 0;
}
char current_word[10] = {0};
uint32_t j = 0, ki = 0, bi = 0;
uint8_t result[32 + 1] = {0};
memzero(result, sizeof(result));
i = 0;
while (mnemonic[i]) {
j = 0;
while (mnemonic[i] != ' ' && mnemonic[i] != 0) {
if (j >= sizeof(current_word) - 1) {
return 0;
}
current_word[j] = mnemonic[i];
i++;
j++;
}
current_word[j] = 0;
if (mnemonic[i] != 0) {
i++;
}
int k = mnemonic_find_word(current_word);
if (k < 0) { // word not found
return 0;
}
for (ki = 0; ki < 11; ki++) {
if (k & (1 << (10 - ki))) {
result[bi / 8] |= 1 << (7 - (bi % 8));
}
bi++;
}
}
if (bi != n * 11) {
return 0;
}
memcpy(bits, result, sizeof(result));
memzero(result, sizeof(result));
// returns amount of entropy + checksum BITS
return n * 11;
}
int mnemonic_check(const char *mnemonic) {
uint8_t bits[32 + 1] = {0};
int mnemonic_bits_len = mnemonic_to_bits(mnemonic, bits);
if (mnemonic_bits_len != (12 * 11) && mnemonic_bits_len != (18 * 11) &&
mnemonic_bits_len != (24 * 11)) {
return 0;
}
int words = mnemonic_bits_len / 11;
uint8_t checksum = bits[words * 4 / 3];
sha256_Raw(bits, words * 4 / 3, bits);
if (words == 12) {
return (bits[0] & 0xF0) == (checksum & 0xF0); // compare first 4 bits
} else if (words == 18) {
return (bits[0] & 0xFC) == (checksum & 0xFC); // compare first 6 bits
} else if (words == 24) {
return bits[0] == checksum; // compare 8 bits
}
return 0;
}
// passphrase must be at most 256 characters otherwise it would be truncated
void mnemonic_to_seed(const char *mnemonic, const char *passphrase,
uint8_t seed[512 / 8],
void (*progress_callback)(uint32_t current,
uint32_t total)) {
int mnemoniclen = strlen(mnemonic);
int passphraselen = strnlen(passphrase, 256);
#if USE_BIP39_CACHE
// check cache
if (mnemoniclen < 256 && passphraselen < 64) {
for (int i = 0; i < BIP39_CACHE_SIZE; i++) {
if (!bip39_cache[i].set) continue;
if (strcmp(bip39_cache[i].mnemonic, mnemonic) != 0) continue;
if (strcmp(bip39_cache[i].passphrase, passphrase) != 0) continue;
// found the correct entry
memcpy(seed, bip39_cache[i].seed, 512 / 8);
return;
}
}
2016-01-19 14:11:57 +00:00
#endif
uint8_t salt[8 + 256] = {0};
memcpy(salt, "mnemonic", 8);
memcpy(salt + 8, passphrase, passphraselen);
static CONFIDENTIAL PBKDF2_HMAC_SHA512_CTX pctx;
pbkdf2_hmac_sha512_Init(&pctx, (const uint8_t *)mnemonic, mnemoniclen, salt,
passphraselen + 8, 1);
if (progress_callback) {
progress_callback(0, BIP39_PBKDF2_ROUNDS);
}
for (int i = 0; i < 16; i++) {
pbkdf2_hmac_sha512_Update(&pctx, BIP39_PBKDF2_ROUNDS / 16);
if (progress_callback) {
progress_callback((i + 1) * BIP39_PBKDF2_ROUNDS / 16,
BIP39_PBKDF2_ROUNDS);
}
}
pbkdf2_hmac_sha512_Final(&pctx, seed);
memzero(salt, sizeof(salt));
2016-01-19 14:11:57 +00:00
#if USE_BIP39_CACHE
// store to cache
if (mnemoniclen < 256 && passphraselen < 64) {
bip39_cache[bip39_cache_index].set = true;
strcpy(bip39_cache[bip39_cache_index].mnemonic, mnemonic);
strcpy(bip39_cache[bip39_cache_index].passphrase, passphrase);
memcpy(bip39_cache[bip39_cache_index].seed, seed, 512 / 8);
bip39_cache_index = (bip39_cache_index + 1) % BIP39_CACHE_SIZE;
}
2016-01-19 14:11:57 +00:00
#endif
2013-11-08 00:24:47 +00:00
}
2019-09-20 22:26:14 +00:00
// binary search for finding the word in the wordlist
int mnemonic_find_word(const char *word) {
int lo = 0, hi = BIP39_WORD_COUNT - 1;
2019-09-20 22:26:14 +00:00
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
2022-05-30 09:13:24 +00:00
int cmp = strcmp(word, BIP39_WORDLIST_ENGLISH[mid]);
2019-09-20 22:26:14 +00:00
if (cmp == 0) {
return mid;
}
if (cmp > 0) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
const char *mnemonic_complete_word(const char *prefix, int len) {
// we need to perform linear search,
// because we want to return the first match
for (int i = 0; i < BIP39_WORD_COUNT; i++) {
2022-05-30 09:13:24 +00:00
if (strncmp(BIP39_WORDLIST_ENGLISH[i], prefix, len) == 0) {
return BIP39_WORDLIST_ENGLISH[i];
2019-09-20 22:26:14 +00:00
}
}
return NULL;
}
const char *mnemonic_get_word(int index) {
if (index >= 0 && index < BIP39_WORD_COUNT) {
2022-05-30 09:13:24 +00:00
return BIP39_WORDLIST_ENGLISH[index];
2019-09-20 22:26:14 +00:00
} else {
return NULL;
}
}
uint32_t mnemonic_word_completion_mask(const char *prefix, int len) {
if (len <= 0) {
return 0x3ffffff; // all letters (bits 1-26 set)
}
uint32_t res = 0;
for (int i = 0; i < BIP39_WORD_COUNT; i++) {
2022-05-30 09:13:24 +00:00
const char *word = BIP39_WORDLIST_ENGLISH[i];
2019-09-20 22:26:14 +00:00
if (strncmp(word, prefix, len) == 0 && word[len] >= 'a' &&
word[len] <= 'z') {
res |= 1 << (word[len] - 'a');
}
}
return res;
}