an idea

This commit was sponsored by Ole-Morten Duesund on Patreon.

1 files changed, 129 insertions, 0 deletions

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.