From 5f5db1e390512cf68a5667863d5205f7d3e99a60 Mon Sep 17 00:00:00 2001 From: Joey Hess Date: Mon, 26 Jun 2017 11:43:42 -0400 Subject: an idea This commit was sponsored by Ole-Morten Duesund on Patreon. --- doc/serverless.mdwn | 129 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 129 insertions(+) create mode 100644 doc/serverless.mdwn diff --git a/doc/serverless.mdwn b/doc/serverless.mdwn new file mode 100644 index 0000000..555bbfb --- /dev/null +++ b/doc/serverless.mdwn @@ -0,0 +1,129 @@ +idea, unfinished and unreviewed + +Storage: + +* Input password and name from user. The name is a combination of their + own name and a more obscure name (such as the name of their high-school + sweetheart). +* Generate N by argon2(name), tuned to take 10 minutes. +* Generate list I by sha256 of N+1,2,3.. , hashes truncated to 10 bytes. +* Generate P, a byte chosen at random. +* Generate K by argon2(password+name, salt=P), tuned to take 0.195 (50/256) + minutes. +* Generate padding to obscure the length of the data. For example, + pad all keys to be as long as a rsa4096 gpg secret key as exported by + paperkey (2724 bytes), to prevent targeting types of keys by size. +* AES encrypt (length + checksum + data + padding) with K as the key, + generating D. +* Split D into 70 byte chunks, call this list C. +* Generate 36 item list T of 80 byte values + (size of bitcoin's `OP_RETURN`), by concating I[x] with D[x]. +* Generate 36 bitcoin transactions storing list T in `OP_RETURN` +* Store the transactions in bitcoin blockchain. + +Retrieval: + +* Input password and name from user. +* Generate N by argon2(name) (takes 10 minutes) +* Generate list I by sha256 of N+1,2,3.. , hashes truncated to 10 bytes. +* Begin retrieving transactions from bitcoin blockchain, looking for ones + with `OP_RETURN` starting with values from I. Extract the 70 byte + chunks from the `OP_RETURN`, generating ordered list C. +* At the same time, generate K by argon2(password+name, salt=p), guessing + values for P until the right one is found (takes 25 minutes on average) +* Once K and C are available, decrypt (concat C) with K and verify + checksum. + +Password guessing: + +Password guessing cost is unchanged from original keysafe. Eg, 25 CPU-years +for a super-weak 19 entropy password. + +Before password guessing can begin, the keysafe transactions for a key +need to be found in the blockchain. + +The attacker can assume that transactions from around the same time are +grouped together. But, the attacker needs to order the transactions +correctly to recover D. If they get the order wrong, their password +cracking will never succeed. With 36 transactions, and 36 factorial possible +combinations, guessing the right order is infeasible. So, grouping +transactions does not benefit an attacker. The attacker needs to guess the +name and generate I to find the right ordering. + +Each guess of a name takes 10 minutes CPU work. This is the same attack +cost as guessing names to download shares from keysafe servers, and a +name that attackers are unlikely to guess prevents this attack, and so +prevents password cracking from starting. + +(keysafe servers also impose a proof of work when lots of requests for +shares are being made, which adds to the cost. That PoW is capped at 8 +minutes per request. This new design doesn't have that so is somewhat weaker. +To get equal strength as original keysafe, could increase the +work needed to guess a name to 18 minutes?) + +Storage servers: + +A storage server can be sent the bitcoin transactions, +and broadcast them to the bitcoin network. This way keysafe does not +need to run a full bitcoin node. It may be possible to use eg, electrum +servers as keysafe storage servers. + +Keysafe would need to verify that the transactions reached the +network (by querying retrieval servers). + +Retrieval servers: + +Retrieval could download the entire bitcoin blockchain and scan it, but +that would be gigabytes of download and take probably days. So instead, +there can be retrieval servers, which the user connects to via tor and +requests keysafe transactions tagged with I. + +Retrieval servers learn which transactions contain keys with still active +users who have needed to restore their key. These might be more interesting +transations to try to guess the passwords of. For example, if people are +using keysafe to safely transit borders with their gpg keys, a government +might focus on transactions retrieved soon after a person of interest +crossed a border. + +Retrieval servers could provide innaccurate or slow results, or too many +transactions, to try to prevent key restore. But keysafe can know about a +lot of retrieval servers, and query several at once. Get a list of +transaction ids from each, and then go through all the lists in parallel +and request transactions from each server until it has retrieved enough. + +Storage cost: + +Current cost per bitcoin transaction is $1, so storing a key in keysafe +would cost $36. + +Of course, keysafe could also use a blockchain other than bitcoin, eg +lightcoin or dodgecoin have much smaller transaction fees. Using those +would allow storing the whole gpg public+private key, not only the paperkey +minimised private key. + +The risk is that all copies of a less widely used blockchain could be lost, +preventing restore of a gpg key. Litecoin is probably big enough and +dodgecoin amusing enough to avoid such a fate for long enough for keysafe +backups to be useful. + +Name collisions: + +If an attacker can guess the name that a user used with keysafe, and their +password, then as well as decrypting their gpg key, they can add new +transactions using the same name and encrypred with the same password. +Keysafe won't be able to tell which to use, and so the user might restore +a gpg key controlled by the attacker. + +Keysafe could prevent this by preferring earlier bitcoin transactions to +later ones. + +On the other hand, a user might reuse a name and password when storing an +updated/new gpg key. Then they might expect keysafe to restore the newest +version of the key they stored. + +Keysafe might want to try to retrieve old transactions when storing a key, +to detect if the user is doing that. It could tell the user they need to +pick a different name if it finds any transactions using the name they +chose. This would also guard against several of users picking the same name, +which could otherwise make keysafe restore need to download a lot of +transactions. -- cgit v1.2.3