[tahoe-dev] nice new picture of DSA-based encryption, plus key length ideas

zooko zooko at zooko.com
Tue Jan 8 20:16:15 PST 2008


One more time, with better tabulation and also with 70-column line  


We have in mind a new encryption scheme which makes for much faster
directory creation (because creation of DSA key pairs is much faster
than the creation of RSA key pairs), and has many other features,
including 256-bit symmetric encryption keys instead of 128-bit.

Here is the description of it:


And Brian just posted a pretty picture:


Brian asked me to look at it and submit comments.  The first comment I
have is about key sizes.  We might want to use key sizes larger than
those currently used for data in motion.  This is because people might
start considering using Tahoe for long-term storage and long-term
security.  If they do, then they will be very conservative about
algorithm security, because the attackers have the advantage of using
tools and resources from 2030 or 2050 to attack the confidentiality or
integrity of data that was stored in 2008 or 2010.

According to the handy-dandy http://www.keylength.com / , Lenstra's
2004 equations suggest that for security until 2048, assuming
(pessimistically, from the point of view of a Tahoe user) that DES was
too weak in 1982 and that the attacker's ability to factor doubles
every 12 months, then we should use:

date    symmetric   asymmetric  dl key  dl group  hash
----    ---------   ----------  ------  -------   ----
2048    100         3172        200     2358      200

(Note that "asymmetric", meaning, I guess RSA, is included only for
comparison -- we don't plan to use RSA.)

Also on that handy-dandy site, it says that RFC 3766 suggests that the
following are equivalently strong:

symmetric  asymmetric  dl key  dl group
---------  ----------  ------  --------
128        3253        256     3253
256        15,489      512     15,489

Also from that site, DCSSI recommends:

date        symmetric   asymmetric   dl key  dl group
----        ---------   ----------   ------  --------
2011-2020   100         2048         256     2048
after 2020  100         4096         256     4096

Also, NIST recommends:

date        symmetric  asymmetric   dl key   dl group hash
----        ---------  ----------   ------   -------- ----
2008-2010   80         1024         160      1024     sha-224
2011-2030   112        2048         224      2048     sha-224
later       128        3072         256      3072     sha-256
even later  192        7680         384      7680     sha-384
even later  256        15,360       512      15,360   sha-512

Finally, ECRYPT recommends:

protection             symmetric   asymmetric   dl key   dl group     
----------             ---------   ----------   ------   --------     
2008-2026              112         2432         224      2432        224
2008-2036              128         3248         256      3248        256
forseeable future[*]   256         15,424       512      15,424      512

[*] including protection against quantum computers

The countervailing pressure for us is:

1.  dl keys are our write-caps, so if we empower users to manage their
write-caps directly (and I very much value doing so), then they are
exposed directly to the user.  Likewise, symmetric keys are our

256-bit caps look like one of these four:

128-bit caps look like one of these four:

Other sizes of capability are also legitimate key sizes to use.

2.  dl group size is the size of the dsa public key and the dsa
signature which each get stored in each share (currently) for each
directory and each mutable file.  I guess if we wanted to we could
erasure code those and store a share of it with each data share.  :-)

Because I want people to feel free to use caps directly, I want them
to be as small as possible in order to compete with "tiny URLs" (which
are centralized identifiers that people can manipulate and use as a
references to caps).  So I'm interested in smallest discrete log key
size that experts recommend as being secure.

We should probably choose either convenient key sizes or
long-term-high-assurance key sizes, and we should probably make the dl
group size , the symmetric encryption size, and the hash size be
"proportional" to one another in estimated longevity of security.
This probably means choosing one (or both) of:

protection   symmetric  dl key  dl group  hash
----------   ---------  ------  --------  ----
option A     100        200     2358      256
option B     256        512     15,424    512

Option A: maybe these caps will become distrusted within a decade or
two.  Maybe they will last for many decades.

Option B: these will remain highly trusted, even for high-value data,
for many decades, even in the face of quantum computation and small
cryptanalytic results against the crypto primitives unless there is a
very surprising cryptanalytic result against the crypto primitives

Those "higher safety" caps, with write-caps of 512 bits would look
like this: (The read-caps would look just like the 256-bit caps shown

512-bit write caps: 

200-bit write-caps would look like this:

100-bit read-caps would look like this: McwduQ4rn7U4Yg90vA
McwduQ4rn7U4Yg90vA g8gb5qeqfqx5kqdnb74m



More information about the tahoe-dev mailing list