Easier-to-remember Seed Words
zawy12 opened this issue · 3 comments
Update:
I did an HTML+javascript web page to convert BIP39 words to sentences and to recover up to 3 seed words if you've saved the hash of the seeds. I also uploaded my 2048 word lists for nouns, adjectives, and verbs.
End update.
People have often used 12 seed words (from BIP39's dictionary of 2k words) for key recovery. They read like this:
obey rifle member way enforce miracle ranch improve execute slam draft ramp
If you use different dictionaries for different parts of speech like adjectives, nouns, verbs, and names and make them each consist of 5k to 10k words, you can make "sentences" that read a lot better than the above and need only 10 words. Here's a pattern of random adjective-noun-verb-adjective-noun.
Breakable donut asserts bossy luxury.
Practical linen revises reliable lounge.
Verbs are not as plentiful unless spanish is used, and the best set of adjectives is copyrighted. I'll show various ideas, but it seems to just use adjective-noun pairs with 8k words in each list, allowing 10 words to replace 12 from BIP39 (132 bits) and guessing the last 2 bits. If 4 languages are used & the nouns and adjectives are 8k in each, 9 words are needed. Using different languages can force the user to learn a word in a different language which may help recall.
The useful ideas in this article may end here, except if the user does the work to finds images to re-enforce word pairs as described below, It greatly assists in remembering. For 8k word lists (10 words), 5 images would be needed. Of course mnemonics such as a memory palace and first letter of each word can also work.
In summary, after investigating everything, I'm partial to 8,500 word lists of adjectives and nouns and then doing a google image search for each adjective-noun pair to find an image that can trigger memory and mnemonics.
Some people might remember better if it uses names. The names are odd because I needed to pull them from a list of 10k names. I randomly generated these examples without selecting.
Aira's astounded chipmunk refills Brendan.
Jovie's thundering collection ridicules Iann.
I've played with other ideas like combining the words with a sprinkling of letter and numbers, and locations in squares like this. I later added the images which helped tremendously in remembering the adjective-noun words pairs. Verbs might be a little harder to remember.
It's been a month since I did the above and easily remembered the images that allowed me to remember the word pairs. I also remembered the "D47 Q53" but not as well. The locations in squares were harder to remember.
The good thing about the location method is that if you remember the approximate location, you know can guess the details which you can't do with words (if they don't have images) except to know it's an adjective or noun. If you know the sequence of placing the following dots, it's the equivalent of 12 words from BIP39, Twice as many dots would be 256 bits. People like to say 2^256 is more than the atoms in the universe, but you can encode that by dropping 22 marbles into a box that can sit on the top of your desk (you have to remember the sequence of the placements, otherwise some information is lost).
Another version:
Key Stretching
All the above was interesting but I thought about other methods and "rediscovered" key stretching and tried to carry it to the limit. The rest of this article is the result.
This is an idea for using only 2 or 3 words and POW to generate a 256-bit random string. A random salt is needed so that an attacker is not able to generate all the solutions which could then be used to attack many people who are using this technique. The salt is visible to the attacker and the user so that only 2 or 3 secret words are needed (to prevent me from cheating when I say only 2 words are needed). With 2 keys selected from a 50k dictionary, there are 2.5B possibilities, so the attacker has to hash 1.25B times more than the user to have a 50% chance of success.
Example: If you want to protect $10 M with 2 secret words for 3 years, you would use a newish ASIC that will not be more than 100x more costly to run than professional ASICs in 3 years in low-cost electricity regions. If you want a protection factor of 15 even if BTC jumps 20x in value, you would have to spend $10 M * 100 * 15 * 20 / 1.25B = $240 on electricity. To protect $100k you need to spend just $2.4. If you use 3 secret words, you could use a GPU and spend $1 on electricity to protect $10 M.
POW method (preferred): You select how much you're going to spend on hashing by selecting the difficulty. You hash the 256-bit random salt + 2 secret words from a list of 50k with a nonce that must start at zero & increment by 1 until the 1st winning hash is found. The hash just before (or after) the winning one is your 128 to 256-bit key that determines your 12 to 24 seed words. The winning hash isn't used because the leading zeros make it non-random.
PBKDF method and problem: Instead of hashing until a winning hash is found as in the POW method, the number of required hashes is specified. The process does not seem effectively different and it has the advantage of having a known amount of hashing required. But it does not allow the user to use the multithreading capability of his GPUs like the POW method. But the attacker can use multithreads when trying to crack it. This is why POW is preferred. Here is this method and then I'll show a solution for trying to make it like the POW method. In Wikipedia's PBKDF2 notation, this implements (if I'm not mistaken)
DK = PBKDF2(sha256(), password, 256_bit_salt, hashes, 256)
# Perlish code for single-thread PBKDF2
# You can't convert this to multithreaded hashing
# Generate "random" wallet key from 2 seed words.
@word_list = 64k words (2^16 )
word1 = random ( word_list )
word2 = random ( word_list )
password = word1 . word2 # concatenation
# User hash cost should be 0.001% (1/1E5) of value in wallet
hashes = wallet_USD / 1E5 / USD_per_hash
hash = sha256(256_bit_salt . password)
for i = 1 to hashes {
hash = sha256(hash . password)
}
wallet_key = hash
# map each 16 bits in the 256 bits to a word in word_list to get 16 English key words
# This is equivalent to using 24 words from BIP39 because word_list is 32x bigger.
Solution to PBKDF2 single-thread problem: This solution is not needed (you can just use a CPU) if you use 3 seed words or use the VDF additional protection. A solution to PBDKF's single thread problem is to apply the PBKDF to each word in the word list that is not the seed word, so the user can run up to 50k (or 64k as in the above pseudocode) threads in parallel, like the attacker. First create a unique salt for each word in the word list from the seed word. The hashing is done on each word (potentially in parallel) that is not the seed word. The pseudocode below tries to work out the details of doing it correctly. If a user can run only 1 thread, it does not add any penalty that he did not have before. Attackers still have to explore the same number of word pairs. Instead of checking every combination of word pairs, they have to check every list of words that does not contain the word pair. This is applying De Morgan's law, the Boolean logic AND(A, B) = NOT(OR(notA, notB) where A = 1st word and notA = the list that does not contain A. At the end of the two rounds, the outputs are XOR'd together one-by-one down the list until there's 1 final 256 bit answer which is the final key.
# Perlish code for MULTI-THREAD PBKDF2
# THIS DOES NOT ACTUALLY SUPPORT MULTITHREAD
# This just shows the method that can be converted to multithreading
# This is "roll your on" and has no evidence of security. RFC2898 may have an alternative
# Generate "random" wallet key from 2 seed words.
@word_list = 64k words
word1 = random ( word_list )
word2 = random ( word_list )
password = word1 . word2 # global
# User hash cost should be 0.001% (1/1E5) of value in wallet
hashes = wallet_USD / 1E5 / USD_per_hash / 2 / 64E3 # <== notice reduction from prior example
salt = 256_bit_salt
for i = 0 to 64e3 { # this is the loop that would broken up into threads.
next if word1 = word_list[i] # do every word except word1
for j = 1 to hashes { # each thread has this number of hashes on its word
hash1[i] = sha256(salt . word_list[i] )
}
}
for i = 0 to 64E3 { salt2 = XOR(salt, hash1[i] }
# Now repeat the above loop for word2 using salt2.
# Your output with be a hash2 array (like hash1 above).
# finish up
wallet_key = 0;
for i = 0 to 64E3 {
wallet_key = XOR (hash2[i], wallet_key)
}
exit;
VDF as an alternative or additional security: VDFs could be used in place of POW or PBKDF or in addition to them. For more security, the 256-bit result could be the input to a 1-day VDF that would require the attacker to employ enough hardware to do 14 M VDFs operating in parallel for 6 months. I was not able to think of a way to interlace POW and VDF to get some kind of multiplicative increase. The main point of VDFs is to prevent parallel computation, but as an attacker gets through the POW or PBKDF part of seed guesses, he can run a separate VDF for each guess. A 3rd seed would have a lot of added security as does the others. As with PBKDF, the user is at a disadvantage because he can't deploy multiple threads, so it requires the same fix of hashing (time-delaying) "everything that is not-my-password". The only difference I can see between VDF and PBKDF is that the VDF has proof of the time delay in the output. If you plan ahead you can start a VDF for a lot of different seed pairs for use in the future, greatly increasing security. Adding VDF to the end of POW instead of front does not make it a lot more difficult. It's really only forcing the attacker to employ a lot of VDF hardware (possibly as efficient as POW in OPEX/CAPEX) in addition to POW hardware, so it seems there's not a fundamental difference between VDF & POW from the attacker's point of view. Not knowing exactly how many hashes the POW will take for a given guess averages out to the same as the VDF & PBKDF having a fixed number. POW & VDF effectively have an input nonce and an output proof. I can't find a use for the output proof for the benefit of the user (except it lets POW be the simpler method because it does not need my fix), so I can't find a fundamental difference for this use between POW, VDF, and PBKDF (if my fix is employed).
VDF, POW, and PBKDF are theoretically the same for this application? The OPEX/CAPEX ratio that ASICs end up being capable of may be independent (for this use case) from it being a POW, VDF, or PBKDF. Considering how every anti-ASIC method seems to eventually fail (maybe Chia's proof of space-time will work), the ultimate OPEX/CAPEX ratio seems to be a function of Moore's law, economics, and speculation about future price instead of the type of computation. My point is that this may prevent a clever way to interlace POW, VDF, and PBKDF to get a fundamentally better key stretch. I have a persistent desire to use "something else" to do the impossible of costing the attacker more than the possible guesses times the user's cost to key stretch. Or at least use VDFs in key stretching as VDFs are intended (make parallel VDFs useless). But it seems like the best I can hope for is trying to discover the elusive "for the people" CPU-based POW that's as costly when using GPUs, ASICs, or FPGAs.
Scrypt, Lyra2, and Argon2. This are KDF (keyword derived functions) used in POW and password hashing (pretty much the same as key stretching, but storing the hashed output openly on the server to verify the entered password was correct) that can work in place of sha256.
Using many ASIC-resistant (new) POWs sequentially. Each hash changes to a different POW in a fixed sequence. Not many attackers will be in possession of ASICs for a variety of POWs, so this can make a user's GPU more competitive, reducing the length of the necessary password. Several coins use this technique properly as opposed to Verge that historically has used it & "fixed" it badly with consequences.
You want to remember the 12 to 24 words so you don't have to repeat the expensive hash to recover them, so this is an insurance policy with a deductible equal to the one-time payment. There is an assumption that it's implemented & deployed more securely than your ability to keep and/or remember your 12 to 24 words.
User error: If the wallet software does not select and broadcast to the chain the salt and difficulty, users may select a weak difficulty, a trivial salt, reuse the same salt, or not correctly broadcasting the salt and difficulty so that they are forgotten.
Renting ASICs over the internet to make up for not having at least a GPU would require pre- and post- hashing a fair amount that is random so that the owner can't easily connect your hashing with your salt and difficulty, but it greatly reduces security. Renting could greatly level the playing field, but it's a real challenge to figure out a way to do it securely.
"The next hash is your 128 to 256-bit key that determines your 12 to 24 seed words. The winning hash isn't used because the leading zeros make it non-random."
The next hash after one that meets the difficulty requirement (leading zeroes) is no more random than the "winning" hash - because it's always "The hash of a hash with ____ leading zeroes," which is much more easily computed. A safer plan is to use the hash right before the winning hash, as there's no easy way to find that one (unless you know the seed words).
@mochimodev I don't understand your objection. @zawy12 specified that you choose "how much you're going to spend on hashing by selecting the difficulty," not by using the difficulty from a blockchain.
I must not be understanding you correctly. You refer to "the rules for evaluating the PoW mechanism" as something under the control of a potential attacker. In the case where said rules are relaxed, the winning hash will be different from the one the keyholder found, so the attacker gets the wrong answer. I think you may have identified the problem at the end of your post, where you wrote "network difficulty."