Update, 2021
RPK is no longer just a theoretical concept, a variant built on this original RPK write up has now been successfully built and implemented in our cryptocurrency software, Coincast. The RPK protocol, along with this variant are by Minty Networks, LLC.
Executive Summary
One of the biggest issues facing cryptography, specifically cryptocurrency, is the loss of high-entropy private keys. There are countless documentations of crypto-investors losing untold millions to key-loss, whether it be hard-drive failure, house fire, or even just misplacement.
Until now, the only solution would be online key backups, but this is out of the quesiton as it would almost guarantee theft (and offline key backups puts one at risk of key-backup-loss, which is no better). Enter RPKs, Recoverable Private Keys. The RPK Protocol is a method for generating high-entropy private keys via a low-entropy password such that they are easy to recover by the owner of the key, but impossible to recover by a third party.
As a bonus, this solution is completely decentralized, nothing is stored anywhere, no third parties are used.
Protocol Overview
When it comes to security and entropy, only one variable really matters, key length. A hex key that is 15 characters long is brute-forceable, while one that is 30 characters long is not. That is, 16^30 is unimaginably larger than 16^15.
With the RPK protocol, the user generates a private key using a Memorizable Password, for example “Z3braStrip3s”, which in this case is 12 characters long. The protocol then generates a random key that is N characters long, for the sake of example we will use “AAC337” (N=6) but in practice N will be significantly longer than this. The protocol then concatenates the user’s Memorizable Password and the Randomly Generated Key, to make one combined key “Z3braStrip3sAAC337”, this is the Generation Key. The Generation Key is then run through a hashing algorithm that will deterministically output a private key of the desired length (for example 64 characters for Ethereum).
Because of this, for a large N, brute forcing the Generation Key can become an impossible task without the user’s memorizable password but an easy task with the user’s memorizable password. In our example, the user’s memorizable password, Z3braStrip3s, is 12 characters long. This memorizable password is never stored anywhere except in the user’s brain, it’s also, by nature, able to be memorized (unlike an Ethereum private key). Now, the protocol generated the second half of the Generation Key using an arbitrary length N (in our elementary example, N was 6), this means the generation key’s entropy is now 12+N. So, with the user’s knowledge of their Memorizable Password, recovering a private key becomes brute-forceable in N steps, but to a third party, the brute force requires N+12 steps.
Suppose N=10, if a user loses their private key, they can recover their Generation Key via brute force (in an alphanumeric environment a-z, A-Z, 0-9) in, at most, 62^10 iterations (839 quadrillion iterations). This is because they know the first 12 characters of the Generation Key (Z3braStrip3s). A third party attacker however, would have to brute force every possible combination of the memorizable password, and for every password guess, then brute force every possible Randomly Generated Key (assuming N is known) before it can move onto the next password guess… this would require 62^22 iterations (2 thousand billion billion billion billion), an impossible task.
With RPK, if the user loses their private key, they can recreate the Generation Key via brute force in a reasonable amount of time (by providing their Memorizable Password), but a third party can not possibly brute force the Generation Key. This works because, in our example, 62^22 is unimaginably larger than 62^10.
Therefore, when using the RPKs (Recoverable Private Keys) for cryptocurrency, one should pick a memorizable password of length X and a randomly generated component length to be used, N, such that brute forcing a key of length X+N has a desired level of entropy that would cost significantly more to crack (in terms of renting super computer space) than would ever be stored on said wallet, but brute forcing a key of length N would cost significantly less to crack than would ever be stored on said wallet. This way, if a RPK-generated private key is lost, it can be recovered in a matter of days by the owner (who knows the memorizable password) but a matter of eons by a third party.
RPK protocol is completely decentralized, nothing has to be stored anywhere, no third parties will host encrypted files or anything of that nature, one will simply brute force their generation key if they lose it, using their memorizable password component to drastically lower the entropy requirements of the brute force to a reasonable range.
Layman Example
Put more simply, suppose the random-key component of the generation-key has enough entropy that guessing it would take about $50 of rented super computer processing.
If one knows the user-password component they can obtain the generation-key (and therefore the private-key) with $50 worth of processing.
If a third party doesn't know the user-password component, then for every individual guess they make at the user-password component, they have to spend $50 in computer processing power (so that they can cross check it with every possible random-key component). $50 PER GUESS. This makes brute-forcing expensive, after even just a mere 100m guesses at the user-password component (which only covers 0.0000000000021% of the guesses they'll have to make by the way), they will have
Therefore, you lose your private key and regenerate it with $50 of brute forcing, mean while your attackers are still guessing away at your generation-key, $5B in the hole, and haven't even touched 1% of 1% of 1% of 1% of 1% of 1% of the total guesses they'll need to make.
Notes
Security Note: Memorizable passwords must be unique and not re-used. Quantum computers may one day pose a risk to this protocol.
Technical Note: ASICs pose a risk to one day brute forcing RPKs so an ASIC-resistant hash function, such as Argon2, must be used.
Nomenclature Note: Other protocols may arise for RPKs (Recoverable Private Keys), so this specific, original, protocol can be clarified as PC-RPK, that is, Password-Concatenated RPK.
-
Albert Renshaw, March 17 2020
Instagram: @Albert
Twitter: @Valuable