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

[zooko]

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 2050, 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 6 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			15489		512		15489

Also from that site, DCSSI recommends:

date		symmetric	asymmetric	dl key	dl group
----			--------		----------		------	--------
2011-2020	100			2048		256		2048
 > 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
 > 2030		128			3072		256		3072		sha-256
 >> 2030		192			7680		384		7680		sha-384
 >>> 2030	256			15360		512		15360		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			15424		512		15424		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