Wallet and key import and export #220

pull sipa wants to merge 2 commits into bitcoin:master from sipa:showwallet changing 7 files +582 −11
  1. sipa commented at 10:04 pm on May 12, 2011: member

    Introduces four new RPC calls:

    • dumpprivkey: retrieve the private key corresponding to an address
    • importprivkey: add a private key to your wallet
    • removeprivkey: remove a private key from your wallet
    • dumpwallet: export the contents of your wallet in various ways
    • importwallet: import/merge a dumped wallet into your own.

    The private key format is analoguous to the address format. It is a 51-character base58-encoded string, that includes a version number and a checksum.

    The wallet format is JSON-based, and includes:

    • addresses (informational, optional)
    • private keys
    • amounts per balance (informational, optional)
    • blocks where addresses were first used (optional)
    • ids of transactions in which addresses were credited (optional)
    • labels (optional)

    It specifically does not contain:

    • sender address book
    • settings
    • account information
    • unconfirmed wallet transactions

    Note that playing around with import/export and moving addresses around between wallets may result in double-spends, which may result in corrupted wallets. See #195 for a solution

  2. gavinandresen commented at 0:09 am on May 13, 2011: contributor
    Nice! I’ll have to find some time to try to break it… rpc.cpp is getting way too big; maybe this would be a good time to start breaking it up into separate .cpp files with related functions (most of this code could be rpcimport.cpp, maybe….)
  3. rnavarro commented at 4:55 am on May 14, 2011: none
    Another feature that would be really really handy would be the ability to specify an account for the importprivkey command
  4. sipa commented at 4:49 pm on May 22, 2011: member
  5. jgarzik commented at 5:51 am on June 20, 2011: contributor
    I think this is useful for wallet security (print out a private key, stick in safety deposit box), so prioritizing a rebase for this would be appreciated.
  6. sipa commented at 5:06 pm on June 25, 2011: member

    Rebased against master, a few bugs fixed, and split off into separate source file.

    TODO: known wrong balance cached when importing keys

  7. EricJ2190 commented at 11:21 pm on July 5, 2011: contributor
    Since this uses the ifstream class, it needs to include fstream in headers.h to build in MSVC.
  8. sipa commented at 1:37 pm on July 11, 2011: member
    I’ve rebased the code against Matt’s newenc, plus some other refactorings. I’ll close the pull request until those are merged.
  9. sipa closed this on Jul 11, 2011

  10. sipa reopened this on Jul 13, 2011

  11. sipa commented at 10:37 am on July 13, 2011: member
    Ok, reopened because github doesn’t seem to track updates to the branch while the pullreq is closed, but this still depends on #403. Also, i’m not convinced how stable the wallet dump format is yet, so I’ve split the last commit in two, allowing merging of only key import/export.
  12. lachesis commented at 10:56 pm on July 16, 2011: contributor
    Didn’t build for me: wallet.cpp:273:65: error: ‘PubKeyToAddress’ was not declared in this scope
  13. sipa commented at 4:15 pm on July 17, 2011: member
    @lachesis: should be fixed
  14. gmaxwell commented at 11:09 pm on July 18, 2011: contributor

    I noticed some weird behavior with transactions heard over the network on imported keys:

    0{
    1    "account" : "",
    2    "address" : "1Wh4bh",
    3    "category" : "send",
    4    "amount" : -0.49500000,
    5    "fee" : -0.00500000,
    6    "confirmations" : 0,
    7    "txid" : "275d51ed81ae359cffe3728f6c7de8246b2b3c147b9dce316a5e952db5d76991",
    8    "time" : 1310993846
    9}
    

    Kind of a short address there… :) (from a checkout this morning)

  15. gmaxwell commented at 11:16 pm on July 18, 2011: contributor
    It’s really slow to import addresses one at a time— giving a rescan for each. If someone feels adventurous, deferred lazy rescan in a thread, and/or an import that call that takes many would be nice.
  16. sipa commented at 7:51 pm on August 3, 2011: member
    Rebased against master, and now includes a feature-complete ‘removeprivkey’ call (should remove the private key, the address book entry, redundant transactions, and account information). I don’t have time to test this the coming weeks, but if people want to try it, be my guest.
  17. sipa commented at 5:26 pm on September 3, 2011: member
    rebased against 0.4.0rc1, not tested after rebase
  18. gmaxwell commented at 6:37 am on September 18, 2011: contributor

    I think the existence of http://www.bitaddress.org/ is a strong argument against this functionality— the feature isn’t done yet and people are already creating websites which compromise bitcoin user’s security.

    Official import/export functionality will increase the apparent legitimacy of attacks exploiting the functionality and bitcoin will suffer the bad PR when users hurt themselves using it. :-/

  19. casascius commented at 9:46 pm on September 20, 2011: none
    @gmaxwell: What part of this functionality constitutes an exploit? The idea that one should be able to have their own private keys on paper, or on bitbills, or on physical bitcoins, etc. should be something that enhances security, not detracts from it. Please explain how security is compromised.
  20. in src/base58.h: in c72361c55b outdated
    309+public:
    310+    void SetSecret(const CSecret& vchSecret)
    311+    {
    312+        SetData(fTestNet ? 239 : 128, &vchSecret[0], vchSecret.size());
    313+    }
    314+
    


    casascius commented at 10:01 pm on September 20, 2011:

    I would like to request an addition here to support the Mini Private Key format as described in the Wiki. Basically, importing using this format would be exactly the same as the existing (51-character) string, but a 22-character mini private key could be provided instead. This would probably fit right here as a different SetSecret that took the string, and ought to take no more than a dozen lines of code. These codes are being used today in Casascius physical bitcoins. The 22-character code need not be persisted in any way - it ought to simply be converted to a normal instance of CBitcoinSecret immediately upon entry, so, these would be displayed in the normal 51-character format if they were exported or dumped.

    The mini private key is simple. The Bitcoin private key is computed as the SHA256 hash of the given string. No more, no less. A shorter private key is universally desirable both in QR codes and in situations where the private key must be manually typed.

    The mini private key format offers a simple well-formedness check and also a hash-based check for typo detection, which is designed to be briefly computationally intensive (requires multiple rounds of SHA256) so as to not detract from the limited entropy that can fit in 22 characters in a brute-force attack scenario. It is described in the Wiki article. Only 22-character strings that meet the well-formedness and typo check criteria should need to be considered for evaluation as importable private keys.

  21. enmaku commented at 7:40 pm on September 21, 2011: contributor
    @sipa: Nice mod! @gavinandresen re: testing: Works beautifully on Debian squeeze i686. All added functionality tested and working properly. @casascius: +1 for adding Mini Private Key format. It should be pretty easy to implement. Also, I believe the problem @gmaxwell was addressing is that scammers can generate “secure” keypairs for their victims and then never relinquish control of the private key, thus allowing them to steal funds from those accounts later
  22. casascius commented at 7:56 pm on September 21, 2011: none
    @enmaku,@gmaxwell: I wasn’t sure if keeping the private key was the concern here, because bitaddress.org appears to have been created with that concern in mind. The generator at bitaddress.org is actually quite novel from a security perspective: the generation is entirely client-side and implemented in javascript in easy-to-read code in a single self-contained html file that contains no references to any network resources. The QR codes are generated from scratch, client-side, as well. This is exactly how a personal address generator should be. One can save the single .html file to disk and use it to safely generate bitcoin addresses straight to their printer while disconnected from the internet. To me, it’s a shining example of a good idea rather than an exploit.
  23. enmaku commented at 8:00 pm on September 21, 2011: contributor
    @casascius: I think the concern is that while you and I might check the source, 99% of folks won’t and eventually one will crop up that phones home and makes a big database of privkeys ripe for exploitation. Realistically though this isn’t our problem any more than any other product or service whose userbase is regularly phished. We can put the info out there, but people want this feature and if it’s not in the main client it’ll be in external tools like pywallet. We can’t stop those who want to from importing addresses, merging wallets, etc. The best we can do is put up big scary popups in the GUI implementation informing folks that messing with the wallet is dangerous and if they do stupid things they’ll get bad results.
  24. casascius commented at 8:10 pm on September 21, 2011: none

    @enmaku: I share the concern, and am appreciative of the fact that the author of this website makes no attempt to explain what his website does to newbies. You have to know why you’re there and what the number means, otherwise it is just a gibberish generator. And the part I appreciate the most is simply that he has released functional code that can be clipped and put into other environments where the source is ostensibly trusted. (e.g. on MtGox, or on the LinuxCoin ISO). Free bonus is it’s platform independent.

    I think the best thing that can be done to the GUI implementation would be to include this functionality where the user can get at it, and seek to be less user unfriendly, then websites like this wouldn’t have a reason to exist.

  25. in src/rpcdump.cpp: in c72361c55b outdated
    157+        throw runtime_error(
    158+            "importprivkey <bitcoinprivkey> [label]\n"
    159+            "Adds a private key (as returned by dumpprivkey) to your wallet.");
    160+
    161+    string strSecret = params[0].get_str();
    162+    string strLabel = "";
    


    casascius commented at 5:50 am on September 22, 2011:

    Here is some code I wrote - AND TESTED =) - that enables full support for mini private key imports, including proper rejection of codes failing the typo check. Regular 51-character private keys still work like normal. Simply replace, removing 5 lines starting from “string strLabel = “”;” thru “bool fGood = vchSecret…” and inserting the following. Sorry I am new to developing with git, learning fast, but am unfamiliar with whether there is a way I can submit a “pull on a pull”, and sorry if there is a much better way to submit this.

    Edit: updated it to make sure removeprivkey benefited from the change as well, as the initial post had the new code right inside importprivkey and only benefited that command.

    Add the following function to rpcdump.cpp:

     0// Sets the private key of a CBitcoinSecret, detecting whether it's a mini or full private key
     1bool SetSecretDetect(string &strSecret, CBitcoinSecret &secret) {
     2    int nSecretLength = strSecret.size();
     3    if (nSecretLength == 22 || nSecretLength == 26)
     4    {
     5        if (strSecret[0] == 'S')
     6        {
     7            int i;
     8            bool fMini = false;
     9            for (i = 0; i < nSecretLength; i++)
    10            {
    11                char c = strSecret[i];
    12                if (c < '1' || c > 'z') break;
    13                if (c > '9' && c < 'A') break;
    14                if (c > 'Z' && c < 'a') break;
    15                if (c == 'I' || c == 'l' || c == 'O') break;
    16            }
    17            if (i==nSecretLength)
    18            {
    19                string strKeycheck(strSecret);
    20                strKeycheck += "?";
    21                uint256 hash;
    22                SHA256((unsigned char*)strKeycheck.c_str(), strKeycheck.size(), (unsigned char*)&hash);
    23                if (*(hash.begin()) == 0)
    24                    fMini=true;
    25                else
    26                {
    27                    uint256 hash2;
    28                    for (i=0; i<358; i++) // 358*2=716 +1=717
    29                    {
    30                        SHA256((unsigned char*)BEGIN(hash), sizeof(hash), (unsigned char*)&hash2);
    31                        SHA256((unsigned char*)BEGIN(hash2), sizeof(hash2), (unsigned char*)&hash);
    32                    }
    33                    if (*(hash.begin()) == 0) fMini = true;
    34                }
    35                if (fMini)
    36                {
    37                    uint256 hash;
    38                    SHA256((unsigned char*)strSecret.c_str(), nSecretLength, (unsigned char*)&hash);
    39                    secret.SetHash256(hash);
    40                    return true;
    41                }
    42            }
    43        }
    44    }
    45    return secret.SetString(strSecret);
    46}
    

    ….. then in importprivkey() and removeprivkey() find the following line: …..

    0bool fGood = vchSecret.SetString(strSecret);
    

    ….. and replace it with …..

    0bool fGood = SetSecretDetect(strSecret, vchSecret);
    

    ….. and then in base58.h in class CBitcoinSecret (public), I added, just after SetSecret(): ……

    0void SetHash256(const uint256& hash256)
    1{
    2    SetData(fTestNet ? 239 : 128, &hash256, 32);
    3}
    

    sipa commented at 10:19 am on September 22, 2011:

    I’m not opposed to adding other private key formats if they are useful, but I don’t think just any format should be added to the main client (as opposed to eg. shipping a small script to do the conversion). That said, the mini private key format sounds useful. What do other people think about supporting this format?

    Second, importprivkey is the wrong place to implement it, as CBitcoinSecrets are used in other places as well that could benefit from supporting it. I think either inside the constructor of CBitcoinSecret, or as a separate utility function that does the conversion.


    casascius commented at 12:46 pm on September 22, 2011:
    I had originally penciled it in to base58.h but it threw a fit seemingly because I had created a dependency on “string” within the header file that wasn’t resolved at compile time with the order it was included, and since this was my first venture into the code (and I haven’t used the STL much recently, I’ll bet vector<char> might have gotten me further), I was not quite sure how to make it work without messing with other files. If you have a recommendation on how you think it should be implemented, I’d be happy to make it that way and test it.

    sipa commented at 5:46 pm on September 22, 2011:
    The std namespace is not included in header files, to prevent namespace pollution. Use std::string and std::vector there instead of string and vector.

    casascius commented at 6:04 pm on September 22, 2011:

    Excellent suggestion, I will do that. (Sorry, C++ semantics rusty for me, otherwise that’s something that should otherwise be clear).

    My intent is to just make sure that the CBitcoinSecret has a SetString override that can handle either kind of key. (I believe the base class already has a SetString). I can do it in the constructor, but as far as I can tell, that will require a new member (a flag) or an exception thrown back to report back to the caller whether the string was any good. Suggest to me which you’d prefer, and I will do it that way and test it.

  26. casascius commented at 6:56 am on September 22, 2011: none
    One more thing… the bigger the block chain gets, the longer importprivkey takes to run, mainly because of the calls to rescan the wallet. I want this in the main client badly because I use it all the time and believe that keys on paper will help solve the black eye Bitcoin has received over security incidents, but it occurs to me that there is no way that this would be taken seriously as acceptable in the main client if it needs to pause for 90+ seconds (and growing) to perform an import. The client itself needs badly to maintain an index for the purpose of doing that rescanning (if it doesn’t do so already), among other useful purposes I can think of.
  27. sipa commented at 10:21 am on September 22, 2011: member

    Keeping a database of all addresses and all outputs to them would be a massive cost that isn’t justified for just somewhat faster importing of addresses. Take into account that when more complex scripts are supported, this becomes even harder, as there could be outputs with several possible addresses or even combinations thereof.

    The solution is using importwallet instead of importprivkey. It supports annotating keys with information about which transactions or starting in which block they are used, and only doing selective rescanning.

  28. casascius commented at 1:04 pm on September 22, 2011: none

    With respect to the massive database of addresses… I could see myself trying to implement that down the road as my familiarity with the code gets better, but possibly in the form of a patch or an option that is turned off by most people because it’s only useful to a specific audience: server operators.

    The specific real-world everyday application it would support would be so that websites (e.g. MtGox, or marketplaces that accept bitcoin deposits) could accept a “deposit by typed private key”, and the private key wouldn’t necessarily be imported, but rather, bitcoind would do one of two things:

    either, one - immediately create and broadcast a one-off transaction (without adding the key to the wallet like importprivkey does) that sent the entire balance at that address to a specific one given as a parameter, at which point it would be treated like a deposit that came in externally (with the option of sending only a specific amount, the rest, if any, going back to the original address or to an optionally provided but specific “change” address)…

    • or - two, offer an RPC query feature that simply coughed up all of the unspent transactions associated with a given address, so that some sort of RPC client could implement the creation of that transaction (a feature I believe is useful in itself for other purposes that also wouldn’t apply to everybody)

    Such a feature would depend on the ability to quickly find all transactions (standard ones, at least) given an address, and would promote the usability of paper bitcoin wallets and physical bearer items, which in turn is a viable way for joe schmoe and/or Grandpa to securely manage his bitcoins without needing to learn about wallet encryption and keyloggers. If bitcoind is tied up for a minute and a half to import an address, this will be impossible in a MtGox-like server scenario.

  29. casascius commented at 10:56 pm on September 23, 2011: none

    OK, here are the goods. Revised mini private key support that consists of adding two SetSecret functions to CBitcoinSecret to override the ones in its base class and no modifications anywhere else. I suppose this is a lot cleaner, and it requires only modifying base58.h and not rpcdump.cpp.

     0bool SetString(const std::string& strAddress) 
     1{
     2    return SetString(strAddress.c_str());
     3}
     4
     5
     6bool SetString(const char *psz) 
     7{
     8    int nSecretLength = strlen(psz);
     9    if (nSecretLength == 22 || nSecretLength == 26)
    10    {
    11        if (psz[0] == 'S')
    12        {
    13            int i;
    14            bool fMini = false;
    15            for (i = 0; i < nSecretLength; i++)
    16            {
    17                char c = psz[i];
    18                if (c < '1' || c > 'z') break;
    19                if (c > '9' && c < 'A') break;
    20                if (c > 'Z' && c < 'a') break;
    21                if (c == 'I' || c == 'l' || c == 'O') break;
    22            }
    23            if (i==nSecretLength)
    24            {
    25                std::string strKeycheck(psz);
    26                strKeycheck += "?";
    27                uint256 hash;
    28                SHA256((unsigned char*)strKeycheck.c_str(), strKeycheck.size(), (unsigned char*)&hash);
    29                if (*(hash.begin()) == 0)
    30                    fMini=true;
    31                else
    32                {
    33                    uint256 hash2;
    34                    for (i=0; i<358; i++) // 358*2=716 +1=717
    35                    {
    36                        SHA256((unsigned char*)BEGIN(hash), sizeof(hash), (unsigned char*)&hash2);
    37                        SHA256((unsigned char*)BEGIN(hash2), sizeof(hash2), (unsigned char*)&hash);
    38                    }
    39                    if (*(hash.begin()) == 0) fMini = true;
    40                }
    41                if (fMini)
    42                {
    43                    uint256 hash;
    44                    SHA256((unsigned char*)psz, nSecretLength, (unsigned char*)&hash);
    45                    SetData(fTestNet ? 239 : 128, &hash, 32);
    46
    47                    return true;
    48                }
    49            }
    50        }
    51    }
    52    return CBase58Data::SetString(psz);
    53
    54}
    
  30. sipa commented at 11:27 pm on September 23, 2011: member
    What do other people think about support for @casascius’ mini private keys?
  31. enmaku commented at 11:39 pm on September 23, 2011: contributor
    I think it could be a useful standard for short keys, though as a contributor on casascius’ deterministic wallet generator I may be a bit biased ;)
  32. gmaxwell commented at 0:04 am on September 24, 2011: contributor

    I’m not super-keen on the reduction in collision resistance compared to 160-bit addresses (keep in mind, general any-any “birthday paradox” collision is sqrt(brute force), so only 61.5 bits— but it’s actually lower than that, the “CRC” check reduces the keyspace by another 16 bits— so only 53.5 bits of collision resistance.

    If these are widely used the chances of two people accidental ending up with the same key is not so astronomically low that we could wave away critics who complain that this is a flaw in bitcoin.

    717 cycles of the hash is worthless as strengthening, I’m guessing this was some number picked by someone with a horribly slow interpreted implementation of SHA256?? Figure a random desktop CPU can do on the order of 1M/sha256/s/core, conservatively. If the count isn’t going to be increased to a reasonable number (e.g. >100k), then it really should just be set to 1: simpler and doesn’t give a false impression of security. Even 100k cycles would still result in technically usable key generation times (e.g. 12.7s worst case assuming 1Mh/s), but if that is too slow the validity check could be reduced to the 10,000 cycle point (max ~1 sec generation) then another million cycles (1 second import) could be applied before you can get the public key (and thus address) from a valid candidate key.

    I’m doubly concerned with the computational complexity here due to the fact that our own project has helped lower the cost per sha256 operation so much. :) The same cautions I made about using a hash function we’ve made so fast for the wallet crypto apply here but double so because we can’t change this.

    Also, the way the stretch is designed every intermediate step is has no feedback of the initial material. This means that internal collisions in the hash will reduce the space further. A proper PBKDF algorithm should be used.

  33. gmaxwell commented at 0:25 am on September 24, 2011: contributor
    (ah, I’d missed on my initial read that the iterated hash is only used for the ‘CRC’ check— this makes the colissions in the hash less serious, but it also means that collision attacks on the 22 character version are probably practical (or at least would be under wide usage) owing to the size of the space and the fairly low cost of checking them)
  34. enmaku commented at 0:33 am on September 24, 2011: contributor

    It’s a reduction to be sure, but a namespace of 22^58 possible keys is still pretty massive. That’s what, about an 8.7e-63 chance of finding a specific collision at 200 MH/s running for a year? Even if a million addressed existed to potentially collide with that’s still ~8.7e-57 for a single 5830, and I’m pretty sure mining is still more profitable.

    Besides, these addresses aren’t intended for the same kind of use as full Bitcoin addresses are, they’re specifically for space-limited situations and for such scenarios the slight increase in risk may be worth it.

  35. sipa commented at 1:04 am on September 24, 2011: member

    The total keyspace is 58^21/2^16 keys: 21 characters with 58 possibilities each, and of this total one key in 65536 will pass the validity check.

    It requires (65536_1 + 256_716 + 1)*58^21/2^16 = 2^124.94 SHA256 steps to generate all minikeys.

  36. sipa commented at 1:25 am on September 24, 2011: member
    On the other hand, I’m not sure why we are giving up any level of security at all. A 29x29 pixel QR code can encode 56 base36 characters, which is equivalent to a full 289 bits (256 + 33 bits crc) of information. Printing 22 base58 requires a similar number of pixels, i believe.
  37. casascius commented at 1:33 am on September 24, 2011: none

    First, let me comment on the “birthday paradox” argument. I believe this is a good argument that has been misapplied. If this were a hashing algorithm that had 21^58 possible outputs for 21^58 possible inputs, then it would definitely apply. But we are using SHA256. We are mapping 21^58 possible inputs into a keyspace of 2^256 outputs. To suggest that SHA256 will only give 2^61.5 unique outputs given 21^58 possible inputs is to suggest that SHA256 is a pretty poor hashing algorithm.

    Let me put it another way. If I decided that mini private keys had only 1 character (so, 58 possible keys going into SHA256), the same birthday paradox argument applied in the same way would suggest that SHA256 would only give sqrt(58), or about seven, possible unique outputs given these 58 inputs, and that the other 51 of them would be SHA256 collisions with one another. It goes without saying that’s not the case.

    Next, let’s review the process of one iteration of trying to brute force one of these keys. This isn’t hash cracking, because we don’t even have the target hash value. That’s because the hash value IS the asset - not the plaintext used to arrive at it, as would be the case in password cracking.

    To try one iteration (set the CRC aside), one would have to do the SHA256, and then convert that to a Bitcoin address, and then check that against the set of all Bitcoin addresses known to have funds. The most expensive part of this process by far is the “convert to Bitcoin address” step, which involves an elliptic curve multiplication. In fact, that step is so expensive as to render the SHA256 part nearly moot, whether it’s once or 717 times.

    The reason why I chose the number 717, with an option for 1 round, is specifically to keep it feasible to GENERATE these keys within slow interpreted languages like Javascript. To actually generate these keys requires a brute force SHA256 effort to find one with eight zero bits. If something like 100,000 rounds were required, the minimum expense to generate these keys would be high.

    I looked at it this way. To generate a mini key that passes the check after 1 round, that requires on average 256 SHA256 operations. To generate a mini key that passes the check after 717 rounds, that requires on average over 180,000 rounds (717*256). At some point, it almost becomes less expensive to do the EC multiply to see if the key has funds versus eliminating it through the CRC, and doing more rounds of SHA256 isn’t going to serve any useful purpose.

    I’m not sure 58^21/2^16 is the right math… as the CRC check is “either or”. The check passes with zeroes on the first round, OR zeroes on the 717th round, so about 1 in 128 random strings will pass the check. The math is probably better expressed as 58^21 / 2^7 in the worst case.

    Finally, these are being used for physical bitcoins worth 1 BTC. That’s the payoff for going to the effort of cracking one. The application this would be likely adopted for by others would be to help small payments move around from hand-to-hand, face to face, since these are the applications where space is at a premium. By no means am I recommending that someone use a 22-character code for their life savings. The low entropy is no secret, I mentioned it myself in the wiki article. I penciled in a 26-character version for applications where 22 characters (what I felt was the bare minimum) wasn’t going to cut it. If we turned on a 30 character version, we’d probably have a keyspace that exceeded the 160 bits present in a Bitcoin address to begin with, though I didn’t do it because I didn’t consider it necessary. It’s a trivial change if consensus says otherwise.

  38. casascius commented at 2:02 am on September 24, 2011: none

    @sipa: Do you suggest that a 56-character private key format that uses only uppercase be implemented instead of, versus in addition to, the 22 character format I propose? You make a very good point, in that with such a scheme, a smaller QR code becomes possible without any question as to whether a reduction is lessening security.

    My physical bitcoins aside, I believe a short-to-type private key format is highly valuable and important to Bitcoin’s future. I foresee Joe Sixpack buying bitcoins for cash at a pawn shop or check cashing place, and him receiving them in the form of a pre-made scratch-off card that gets activated (read: loaded) at the register. Which he will then take to the Bitcoin-accepting online marketplace of his choice, and type it in for instant credit. He may or may not be able to scan a QR code, and this Joe won’t be downloading clients or block chains. Typing 50+ mixed-case characters really sucks (done it numerous times), but especially for Joe. Even 22 sucks, but that’s already flirting with the minimum enough and there is not much that can be done about that.

  39. sipa commented at 2:04 am on September 24, 2011: member
    • I misunderstood one thing: the 0-byte tests are OR’ed; that means indeed 7 bits of error correction instead of 16. This does mean that if I were to attack, I’d just try those strings that hash to a 0 byte after 1 step first. Otherwise said, I can calculate half of all minikeys by only doing 256*58^21 SHA256 steps. That’s not really a problem, but it makes the 717 rounds more or less pointless.
    • We were talking about a different kind of collision resistance: there are 58^21/128 = 2^116 valid minikeys. If there are a lot of these in use (say 2^30), the chance of hitting one by generating a lot of them (which indeed requires an EC multiply + some SHA256 steps) becomes more likely. I think this is only a problem in theory.

    The real question is how useful it is to have it implemented by default in the client, which encourages people to use a (slightly) less secure system than full keys, which probably suffice for most purposes (imho).

  40. gmaxwell commented at 2:14 am on September 24, 2011: contributor

    The ec multiply is just slow on our existing cpu implementations. Gate count wise it’s much faster than sha256. (of course, you’ll still also need 1x sha256+ripemd160 to get an address)

    I think you’ve missed the point on the birthday paradox issue: I’m not proposing that this somehow makes it easier to find the private key from the address or anything like that. There are N=58^21 possible keys (minus the ones lost to checking), there are M being used. These are the only figures you need to know to figure out the probability of two identical keys coming into existence by chance. When M=sqrt(N) it’s 50%. The interior operations are as irrelevant as the 86400 seconds in a day are to the traditional birthday paradox example. :)

    For your use this level of security may be adequate. But if this is put in the software it will be used for other things, and I don’t believe it is adequate for very many things. (If you’d reached 2^160 I’d have nothing to complain about).

    I don’t follow why you did the either/or check (I’d correctly used the 7 bit number initially, but sipa corrected me on IRC doh, not that I’m also not guilty of misreading the code). Why isn’t this sha256^n(key)[0]&127==0 ? The early check reduces the security of the strengthening (and makes analysis harder) without providing a substantial speedup.

    Generating these keys in javascript is a bad idea. The current browsers JS does not provide an appropriate environment for security-important operations. The security of the official bitcoin software and its standard feature set should not be compromised by performance considerations related to poor performance in things that are a bad idea to begin with.

  41. casascius commented at 2:19 am on September 24, 2011: none

    @sipa: If you calculated half of all the minikeys and ignored all the ones that needed 717 rounds to generate, you’d only victimize those who elected to use the ones that passed on the first round. Those who follow the best practice of only using only the ones that pass on round 717, and not on round 1, where able, are not going to be affected. On the other hand, if you’re a javascript and you need to quickly generate an address to collect a payment that’s going to get swept to another wallet right away anyway, the option for a 1 round key comes in handy.

    Supporting the import of these private keys in the client doesn’t in and of itself encourage their unnecessary use. The average joe user isn’t going to be making the decision as to which kind of key to use, these decisions are presumably going to be made by developers who would have the intellectual means to weigh whether generating minikeys versus full keys in their app is a good design decision. I think it would be irresponsible to put a “generate minikey” button in the client. But I don’t think it serves any useful purpose to not accept them as imports and instead demand the user use some other utility to get the job he already needs done, done. (Having him find and download the other utility exposes him to a new class of risks by itself, far more frightening than a brute force attack on the key space).

  42. casascius commented at 3:00 am on September 24, 2011: none

    @gmaxwell: I used the “either or” check so that there would be a means to generate a crappy key if you only need it for a short time for a crappy purpose. In other words, if you have the means to select a key that passes the 717 check and not the 1st check, then by all means do that. That means, to generate a “better” key, explicitly discard all the candidates that pass on the 1st check.

    I agree with you that javascript is a poor environment to be generating keys, and I mention it only for ease of illustration. Minikeys could be needed in the context of an interpreted language on a server, or on a microcontroller. Imagine a check cashing shop that sells BTC and uses a VeriFone point-of-sale credit card machine to generate and issue a minicode on a piece of receipt tape - a very plausible application. That little box with its 400 MHz underclocked ARM and 2MB memory might not be able to do 180000 SHA256’s in any short order, and 95% says the dude buying it is probably going to redeem it that same day, so the window of opportunity for a thief is vanishingly short.

    On the other hand, let’s kick around as granted the conclusion that this is a bad idea. What do we want Joe Sixpack to do instead when he acquires a private key given to him on paper? We could make him type 51 characters instead of 22, sure. We could make him type 26 or 30 as well. We could make him scan a QR code, but it’s likely he either has nothing to scan it with, or is almost certainly going to have to hand-key it off his cell phone and into his computer, making the QR code of no benefit and nothing more than an extra burdensome step. I suppose it’s fair to say that a minimum length keycode is universally desirable, and it’s really just where to draw the line of being reckless with security.

    Let me also propose an alternate solution. The key space for my proposal is all of those who pass the SHA256 check with the magic byte “00”. What if, in addition to this, we define another key space, and that’s all of those 22-character base58 codes who fail my check but pass with magic byte “01”. And then we utilize a far more computationally intensive key derivation function to compute the 32-bytes in place of SHA256, that dwarfs both SHA256 and EC in resource complexity, and define that as the best practice for generating such short keycodes. And then still leave 717 and even 1-round SHA256 as a weak option so that microcontrollers can still stay in the game where needed.

  43. casascius commented at 4:22 am on September 24, 2011: none
    Example: use PBKDF2 whenever SHA256(code + ‘?’)[0]==0x01, and further, use the next byte (sha256()[1]) to encode the number of iterations needed to derive the key, exponentially (2^n), so that its difficulty is easily scaled (or 2^(n/4) to increase the useful range of choices). So a code whose sha256(code+’?’) starts with 0x01 0x28 would derive the key with 1024 (2^(40/4)) rounds, and one whose check hash starts with 0x01 0x60 would use 16777216 rounds (2^(96/4)). An upper bound would have to be hardcoded to prevent CPU DoS attacks on servers that accept redemptions, which would be increased by consensus as computing power advanced.
  44. casascius referenced this in commit fbb868660b on Sep 24, 2011
  45. casascius commented at 6:00 am on September 24, 2011: none

    OK, there it is. Proof of concept with PBKDF2, at least, at casascius/bitcoin. For testing purposes, I have commented out the wallet scanning, so all the delay experienced can be attributed to PBKDF2 and not the wallet scanning.

    I also got rid of the 717-round stuff. I haven’t used any such codes on physical bitcoins so it can be scrapped right now.

    So my submission either accepts a 1-round SHA256 if the test hash starts with 0x00 (as used on physical coins), and uses PBKDF2 if the test hash starts with 0x0100 thru 0x0150 (rejecting all else).

    Using 0x0150 does PBKDF2 with 1048576 iterations, and it takes my machine about six seconds to derive the key at that rate. Using 0x0128 uses 1024 iterations, and the delay is imperceptible (to me as the user). If accepted, the hardcoded limit should probably be somewhat lower to avoid DoS’s.

    Here are some test keys. Sksec8N4Pb9x3EmKChBq9c - ?=0x0128 - calls for 1024 iterations SmbM4uRBu2mQymCsuMKkiW - ?=0x0130 - calls for 4096 iterations Sou6jrw7YW8oeQjXeS8J5u - ?=0x0138 - calls for 16384 iterations SU6ppdqUTS3KWcnZuFxebf - ?=0x0140 - calls for 65536 iterations STk4hKyfJdXdZ2cZG3VByy - ?=0x0148 - calls for 262144 iterations SmEVr24rSdaUgnmX8LwpeM - ?=0x0150 - calls for 1048576 iterations S172quV4MT1ESiS5REfFQx - ?=0x0151 - will get rejected due to being past current hardcoded limit.

    EDIT: I previously had a brainfart and put 16777216 instead of 1048576 iterations. 1048576 is the correct number.

  46. casascius referenced this in commit 0702009c0d on Sep 24, 2011
  47. ghost assigned alexwaters on Oct 20, 2011
  48. T-X commented at 2:01 am on November 10, 2011: none

    @sipa: “What do other people think about support for @casascius’ mini private keys?”

    Sounds like an extra feature which will need extra attention. Maybe it should be added as an additional commit on top later and should be further discussed under a separate pull request after the “straightforward” 51-character base58-encoded import/export version got added?

  49. runeksvendsen commented at 2:39 pm on November 13, 2011: contributor

    EDIT: I got rid of the below error by adding an include in bitcoinrpc.cpp for boost/filesystem.hpp

    I get the following error when I try to build the showwallet branch with gcc 4.6:

     0g++ -c -pthread -Wno-invalid-offsetof -Wformat -g -DNOPCH  -DUSE_SSL -fno-stack-protector -fstack-protector-all -Wstack-protector -Wl,-z,relro -Wl,-z,now -D_FORTIFY_SOURCE=2 -O2 -MMD -o obj/nogui/bitcoinrpc.o bitcoinrpc.cpp
     1bitcoinrpc.cpp: In function 'void ThreadRPCServer2(void*)':
     2bitcoinrpc.cpp:2213:9: error: 'filesystem' has not been declared
     3bitcoinrpc.cpp:2213:26: error: expected ';' before 'certfile'
     4bitcoinrpc.cpp:2214:14: error: 'certfile' was not declared in this scope
     5bitcoinrpc.cpp:2214:49: error: 'filesystem' has not been declared
     6bitcoinrpc.cpp:2215:13: error: 'filesystem' has not been declared
     7bitcoinrpc.cpp:2215:32: error: 'certfile' was not declared in this scope
     8bitcoinrpc.cpp:2217:9: error: 'filesystem' has not been declared
     9bitcoinrpc.cpp:2217:26: error: expected ';' before 'pkfile'
    10bitcoinrpc.cpp:2218:14: error: 'pkfile' was not declared in this scope
    11bitcoinrpc.cpp:2218:45: error: 'filesystem' has not been declared
    12bitcoinrpc.cpp:2219:13: error: 'filesystem' has not been declared
    13bitcoinrpc.cpp:2219:32: error: 'pkfile' was not declared in this scope
    14make: *** [obj/nogui/bitcoinrpc.o] Error 1
    

    I’m using gcc 4.6.1, libc6 2.13 and libboost 1.46 from Debian sid (the Linuxcoin distribution). I have tried with gcc 4.5 as well, same error. The regular bitcoin branch builds without issues.

  50. sipa commented at 2:59 pm on November 13, 2011: member
    Thanks for reporting - an include was missing. It should be fixed now.
  51. runeksvendsen commented at 3:53 pm on November 13, 2011: contributor
    Thank you for adding this feature. I just tried importing a private key using this version of bitcoind on an offline computer, running Linuxcoin from a USB stick. I am now back in my everyday OS, Ubuntu, and everything seems to have worked fine - and I received no errors when importing the key, although it took a while. So consider it a thumbs up for the importprivkey command from here!
  52. gavinandresen commented at 3:28 pm on December 19, 2011: contributor
    I just pulled the other dumpprivkey; is this one now obsolete?
  53. Key removal
    Introduces a new RPC call, defined in rpcdump.cpp:
    * removeprivkey: delete a private key from your wallet
    68e308e1a1
  54. Wallet import and export
    Introduces two new RPC calls, defined in rpcdump.cpp:
    * dumpwallet: export the contents of your wallet in various ways
    * importwallet: import/merge a dumped wallet into your own.
    5e920af78f
  55. sipa commented at 3:43 pm on December 19, 2011: member
    No, this one still contains removeprivkey and dumpwallet/importwallet. I’ve rebased them against current master now, but I’ll close the request until it’s more clear what dumpwallet/importwallet should do (there’s talk of including addresses, for example).
  56. sipa commented at 3:44 pm on December 19, 2011: member
    closing
  57. sipa closed this on Dec 19, 2011

  58. dexX7 referenced this in commit 8f4e0d6c87 on Sep 4, 2015
  59. btcdrak referenced this in commit 7526479ac5 on Nov 28, 2015
  60. deadalnix referenced this in commit 83a7e002a7 on Jan 19, 2017
  61. lateminer referenced this in commit 225eb40ac6 on Dec 9, 2017
  62. classesjack referenced this in commit 3f44ebf51a on Jan 2, 2018
  63. attilaaf referenced this in commit d455a36b45 on Jan 13, 2020
  64. laanwj referenced this in commit 7723479300 on Mar 16, 2021
  65. cryptapus referenced this in commit 998f076148 on May 3, 2021
  66. cryptapus referenced this in commit f0f67f16be on May 3, 2021
  67. hebasto referenced this in commit b789914f17 on May 27, 2021
  68. rajarshimaitra referenced this in commit d3d464c4b7 on Aug 5, 2021
  69. DrahtBot locked this on Sep 8, 2021

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-23 15:12 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me