mochimodev
commented
3 years ago The function primitive of all PoW systems is to enforce delay in a distributed system (through various means). Other uses for PoW mechanisms are incidental (coin creation, as an example).
Any system that seems to depends on a PoW function as a form of security is subject to offline or closed network attacks, where the rules for evaluating the PoW mechanism are entirely malleable. This is true because it is only the network effect that creates the appearance of consensus-based security in PoW enforced-delay systems.
Imagine an attacker recreates a lower-difficulty network where the validation checks for instantiation of this proposed secret key pair are ignored... The low/no-difficulty network allows the system to run at a much higher speed and at effectively zero cost.
Or, presuming that attack surface can be closed... a forked and subsequently closed network attack could be attempted that cycles the blockchain forward in time on a single machine, driving the difficulty to near zero, and allowing the use of "pretend" coins for your attack attempts. Both the limiting factors of coin value and network difficulty disappear.
I can't think of how to mitigate these things.
-stackoverflo
On May 31, 2021, at 12:25 PM, zawy12 @.***> wrote:
This is an idea for doing something that appears impossible. It uses POW and 2 seed words to create and recover 12 to 24 words for recovering wallet keys. People immediately object that it can be done with only 2 seeds ("low entropy") to create a secure set of 12 to 24 words ("high entropy"), but it's a standard technique called key stretching that goes back at least as far as 1990. A 2000 specification is still the standard, with most people using PBKDF2. Those familiar with PBDKF2 will balk at doing this with only 2 words, but I'm talking about really using POW in PBDK2 by letting the user adjust the difficulty to cost him 0.01% of his wallet's value to create his wallet keys. He is literally buying a reduction in what he has to remember.
I won't discuss PBKDF2 or the free modules that implement it because I was not aware I was reinventing an old technique when I wrote this. Seeing how I rolled my own will hopefully give a deeper understanding of how & why PBDKF2 works, enabling us to use it correctly, unlike BIP39 which appears to use it badly.
Overview: The user spends an adjustable amount of value on hashing just 2 secret words to create ("key stretch" them) into a random 128 to 256-bit string that can be converted directly to 12 to 24 words using BIP39's word list (but not its technique). These 12 to 24 words are not seeds because seeds are supposed to be what are key-stretched into keys. An attacker has to spend the same amount of value as the user spent for each of his guesses of the 2 secret words, so it can be incredibly expensive. 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. This is not too difficult if an attacker has to do it only once for all users, so there has to be a random 256-bit salt as an input to the hashing to "poison the 2 words" with randomness. All attackers are "forced" to see the salt and difficulty setting such as putting them on the blockchain with a transaction associated with the wallet. This makes the salt and difficulty as close as possible to being "unforgettable" to the user.
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. You have additional security from the ASIC equipment value. 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.
Specifics: 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 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. [Update: the hashing part should be replaced by PBKDF2 standard, assuming it allows a salt and difficulty setting.] For more security, the 256-bit result could be the input to a 10-day VDF that would require attacker to also employ enough hardware to do 140 M VDFs operating in parallel for 6 months (2 words from 50k list).
Alternate method: [working on idea to interlace POW and VDF]
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.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/zawy12/difficulty-algorithms/issues/70, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AIDXEIYLCK42FYXSAXXNLOTTQOZ6NANCNFSM453FKOWA.
dscotese
zawy12
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:
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.
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.
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)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.
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.