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

Tue Jan 8 20:16:15 PST 2008

Folks:

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

Folks:

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:

http://allmydata.org/trac/tahoe/ticket/217

And Brian just posted a pretty picture:

http://allmydata.org/trac/tahoe/attachment/ticket/217/mutable-DSA.png

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     
hash
----------             ---------   ----------   ------   --------     
----
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
read-caps.

256-bit caps look like one of these four:

http://127.0.0.1:8123/v9f4ezaZpLOiGVSmlpZ9NIGEOE6HYwAA5mLxbVPrROM
v9f4ezaZpLOiGVSmlpZ9NIGEOE6HYwAA5mLxbVPrROM
http://127.0.0.1:8123/ 
z9m9o63sug1m8eo3k1ujpfu7g1yaeqnqo7to9y8gcmas4w9meuto
z9m9o63sug1m8eo3k1ujpfu7g1yaeqnqo7to9y8gcmas4w9meuto

128-bit caps look like one of these four:

http://127.0.0.1:8123/ZDjtvnPPGe1gSDxiccLa8A
http://127.0.0.1:8123/cohq5xuu3hc64ane8tt8dos46y
ZDjtvnPPGe1gSDxiccLa8A
cohq5xuu3hc64ane8tt8dos46y

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
above.)

512-bit write caps:

http://127.0.0.1:8123/ 
LiuZU0CCvv3HbKmRU2wqqR9GSDOg_6DAT6YHm2MYgmzrtPmHN_kv77zHlKhkUP3Q7YE5FgOW 
meR0uNq6l_Lb2g
http://127.0.0.1:8123/ 
fai31w4yok9x5t5cigeig5bkirxwc1buwd94bonxwad3saaaojsqzp83oh591m9xzud3jkdr 
kd67b5cb8rmy8fw3ht4mtsi4193pzso
LiuZU0CCvv3HbKmRU2wqqR9GSDOg_6DAT6YHm2MYgmzrtPmHN_kv77zHlKhkUP3Q7YE5FgOW 
meR0uNq6l_Lb2g
fai31w4yok9x5t5cigeig5bkirxwc1buwd94bonxwad3saaaojsqzp83oh591m9xzud3jkdr 
kd67b5cb8rmy8fw3ht4mtsi4193pzso

200-bit write-caps would look like this:

http://127.0.0.1:8123/biGvBl4XzCGJBqmV7lZllrubc3w5muyPRg
biGvBl4XzCGJBqmV7lZllrubc3w5muyPRg
http://127.0.0.1:8123/pao46b16n9gndnegigk6hiuf1473sh5h8gpq3d4g
pao46b16n9gndnegigk6hiuf1473sh5h8gpq3d4g

100-bit read-caps would look like this:

http://127.0.0.1:8123/ McwduQ4rn7U4Yg90vA
McwduQ4rn7U4Yg90vA
http://127.0.0.1:8123/ g8gb5qeqfqx5kqdnb74m
g8gb5qeqfqx5kqdnb74m

Regards,

Zooko