Folks: I really like the idea of "Semi-Private Keys". I invented this idea! This makes me very proud. I described the idea in lafs.pdf [1] and drew two pretty pictures (Figures 2 and 3) which show how much simpler a system of diminishing crypto-capabilities can be if it is built with semi-private keys. Apropos our recent discussion about capability taxonomy, the use of semi-private keys (or actually of semi-semi-private keys) would greatly simplify the implementation of hierarchies of diminished caps with more levels (such as if Shallow Verify caps were included in addition to Deep Write, Deep Read, and Deep Verify). In addition to being simpler, this construction would allow for an efficient off-line diminish computation.
However, I really don't think we should rely on semi-private keys in our next cap design. There is no formal proof of their security, they've never been officially peer reviewed by cryptographers in a journal or conference, they are a new idea and almost all cryptographers on the planet have never heard of them. Therefore, there could be some subtle mathematical flaw in the idea which has gone unnoticed by Brian, Shawn, David-Sarah, myself, and the various other cryptographers who have looked at the idea. Also, even if the construction *is* actually safe, demanding and paranoid users such as governments and cypherpunks may refuse to rely on it out of an abundance of caution. There is another, more technical, reason not to use semi-private keys, which is that elliptic curve keys takes up twice as many bits as their security level. If our read caps contain an elliptic curve with K-bit security, then that curve has to have 2K-bits in it. Concretely, if we had a 96-bit security level (by the way I'm not yet sure that 96-bit security level is strong enough), then a read-key made up a 192-bit ecdsa semi-private key would look something like this: lafs://MR_1IvY9jxDREZmkfVyjM1eFmEqMpP8tGM9B A 128-bit security level (widely accepted) would require a 256-bit elliptic curve key, like this: lafs://MR_NHhjcZrScTqrxT73K7d4zgC4d5BzsjXYOf0JNgt2bFx And a 256-bit security level (super overkill to persuade even the most paranoid person that the crypto is not the weak point): lafs://MR_VVdUttNsfUw8eQYABYV0jGgY6hQGuoMji1LwtezvuZ4m74yhiMqjTC9v7fUOn50XzHXpggKRBpFxH3bL1jcAY3 In contrast, if we could use our current approach which doesn't rely on semi-private keys and somehow compress together the "read key" part of the cap and the "verify hash" part of the cap, then we could have 96-bit security with just one 96-bit value. However, as we recently discussed [2], short bitstrings such as hashes can be targetted by an attacker "at once". In contrast, this paper [3] seems to say that elliptic curve public keys can't be targetted en masse like that. That is, if you are given one 192-bit elliptic curve public key, it will probably cost about 2^96 to crack it. If you are given a trillion 192-bit elliptic curve public keys and you want to crack *any one* of them, it will probably *still* cost about 2^96! his conclusion is counter-intuitive to me, and I didn't really understand the math in that paper, so if anyone else wants to look at [3] and try to help us understand it that would be nice. (Note that this is the cost to crack an elliptic curve public key using the Pollard's rho method. The attack against secure hashes that we were talking about was a "brute force" attack in which you generate random ones yourself and then check if your random one collides with any of the many targets. One could do the same attack on elliptic curve public keys -- generating a random public key and then checking whether it is the same as someone else's public key. However, they are so long -- at least 192 bits -- that the 30 or 40 bits that you can shave off by generating a bilion or a trillion of them doesn't get you into range of having a chance of success.) Anyway, if the content of a cap is a secure hash output then the cap could be short, and so in order to avoid this "attack everyone at once" problem we have to make sure they aren't *too* short. Let's take our desired security level -- 96 bits -- and then add 64 bits to ensure that even if there are trillions upon trillions of targets out there (capabilities in use), the chance of success for the attacker is still negligible: 128 bit (possibly too short?): lafs://MR_4sViRyFdd9gt1WOWhBgEs6 160 bit (nice and safe): lafs://MR_S7msOFJ80xQ1WrDDiEP0M8ULxMT 256 bit (super overkill): lafs://MR_5yuGWCrBICTZEO06e0fhzYDuEqIbfKEpEBOlP239d5b Note: these caps have been formatted for human-usability by prepending them with a URL scheme (spelled here "lafs://", although other people who might be drivers of the standardization process such as Brian and Peter might prefer to spell it "tahoe://") and with "MR_" to mean "mutable file, read cap", and also the crypto bits have been base-62 encoded. Encoded in an 8-bit encoding such as ASCII or UTF-8, they now take up 32 bytes for a 128-bit cap, 37 bytes for a 160-bit cap, or 53 bytes for a 256-bit cap. When caps are not being presented to humans but instead are for computer use, such as when they are embedded inside directories, then they shouldn't be formatted like this, but should instead be basically just the pure 16, 20, 32, or 64 bytes of crypto material. So the trade-off between using semi-private keys embedded directly into the caps versus using secure hashes of traditional public keys in the caps is that the caps can be shorter for the same security level, as shown here, as long as that security level is at least 128 (or perhaps 160) bits. And, the crypto techniques we rely on can be standard. On the other hand, diminishing a capability cannot be performed as an off-line operation. E.g. if you have a read-write cap and you want to generate a read-cap, you have to find a storage server that has the "Extended Write Cap" and fetch it from there before you can generate the read-cap. (I suppose you could also cache the Extended Cap material or even include the necessary parts of it as an optional extension carried around with the cap itself!) Also, using traditional techniques instead of semi-private keys requires the format to be more complex. See lafs.pdf for details about that, but note that since I wrote that I've thought of another way to achieve "only one crypto value" using only standard crypto techniques. Note: I haven't yet published my idea for how to achieve "only one crypto value" by compressing together the read key and the verify hash. Regards, Zooko [1] http://allmydata.org/~zooko/lafs.pdf [2] http://allmydata.org/trac/tahoe/ticket/753#comment:1 [3] http://testgrid.allmydata.org:3567/file/URI:CHK:qxugzb4esi6b6clupozci7x6hu:jscs6fjjtm5jmqh3rchurubi5qmz7pxc2bf54ixt7vn64zmy5abq:3:10:305839/@@named=/multipledlog.pdf _______________________________________________ tahoe-dev mailing list [email protected] http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
