[tahoe-dev] two reasons not to use semi-private keys in our new cap design

[Zooko O'Whielacronx]

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