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

Tue Jan 8 20:13:39 PST 2008

Folks:

Here is another attempt with better formatting, and I fixed one error  
in the text.

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