See also NewCapDesign and Bibliography.
This describes a project to enhance Tahoe-LAFS's cryptographic system so that Tahoe shipped today/next year might remain safe from cryptographic attacks for a 100 years. The initial ideas were presented on a post by Zooko on his klog.
One idea is to combine two primitives, both thought to be safe, such that even if one of them fails catastrophically Tahoe-LAFS remains secure.
Bulk Encryption
Convert from AES/CTR to using AES/CTR combined (by XOR) with XSalsa20. This has the advantage of being fully parallel, since you can compute both the AES and XSalsa20 keystreams in parallel and before the plaintext or ciphertext is known.
It's worth noting that AES is being retained more for political/name brand reasons than actual security. If this wasn't a factor we might well be better of instead using a design that is safe against timing attacks, such as Serpent or Noekeon. On the other hand, CTR mode probably makes timing attacks rather more difficult because the attacker can't choose inputs. And in Tahoe-LAFS's case, the initial CTR IV will be secret and chosen via a cryptographic KDF.
Open questions:
- Should we use AES-128, AES-192, or AES-256? Zooko says: I guess it is worth the added CPU cycles to use AES-256. The added CPU cycles on ARM, according to bench.cr.yp.to, is about 40 cycles per byte for AES-256 compared to about 28 cycles per byte for AES-128. See recent attacks on AES-128: http://eprint.iacr.org/2011/449 Here are measurements of performance: pycryptopp ticket #46, comment 13
- What KDF is used to generate the keys/IVs? Zooko says: per this mailing list thread HKDF might be a good choice for KDF.
- Samuel Neves had an alternate proposal for encryption to use the same or similar mechanisms as we use for hashing: Samuel Neves proposal. Zooko says: Samuel Neves's hash-based encryption proposal could be used in addition to AES and XSalsa20, or in place of XSalsa20.
Hashing
We'll combine two hash functions using an appropriate combiner depending on the hash function properties that are required, see Zooko's notes about hash function combiners. The Comb4P hash function combiner preserves most (but not all) security properties of the hashes, though because the extra work comes in the form of a set of final Feistel rounds, this may negatively effect performance when combined with the tree hashing mode Tahoe-LAFS uses.
Signatures
Daira has proposed to use hash-based digital signatures.
Discussion on the tahoe-dev list with Zooko, Brian Warner, Jack Lloyd, and Daira (then David-Sarah): 1, 2, 3, 4, 5.
Zooko posted "back of the envelope" performance constraints. Bottom-line: you get 30 million ARM instructions to implement one complete digital signature verification.
Julian Wälde has posted an actual implementation of hash-based digital signatures. This scheme apparently isn't actually a stateless scheme like the ones discussed above, but it does meet Zooko's performance criteria.
Brian and David-Sarah wrote a simulator or two to explore performance trade-offs in (stateless) hash-based signature parameters. The output of one run with the following parameters is this (note that the signing times include regeneration of per-message signing keys from a small long-term private key):
# range of hash output lengths
range_L_hash = [128]
lg_M = 53 # lg(required number of signatures before losing security)
limit_bytes = 20000 # limit on signature length
limit_cost = 500 # limit on Mcycles_Sig + weight_ver*Mcycles_ver
weight_ver = 1 # how important verification cost is relative to signature cost
# (note: setting this too high will just exclude useful candidates)
L_block = 512 # bitlength of hash input blocks
L_pad = 64 # bitlength of hash padding overhead (for M-D hashes)
L_label = 80 # bitlength of hash position label
L_prf = 256 # bitlength of hash output when used as a PRF
cycles_per_byte = 15.8 # cost of hash
B K K1 K2 q T L_hash lg_N sig_bytes c_sign (Mcycles) c_ver ( Mcycles ) ---- ---- ---- ------ ---- ---- ------ ------ --------- ------------------ -------------------------------- 30 26 26 1800 12 19 128 104.8 12926 460840 ( 466.00) 30470 +/- 8190 (30.81 +/- 8.28) 24 30 30 2100 12 18 128 104.3 13006 433211 ( 438.06) 32477 +/- 6536 (32.84 +/- 6.61) 24 31 31 1700 12 18 128 104.9 13006 441777 ( 446.72) 27696 +/- 6536 (28.01 +/- 6.61) 27 27 27 1500 12 19 128 105.6 13054 435350 ( 440.23) 26170 +/- 7470 (26.46 +/- 7.55) 27 26 26 1800 12 19 128 104.8 13246 423660 ( 428.40) 29750 +/- 7470 (30.08 +/- 7.55) 21 30 30 2100 12 18 128 104.3 13310 406136 ( 410.68) 32021 +/- 6080 (32.38 +/- 6.15) 22 31 31 1700 12 18 128 104.9 13310 416165 ( 420.83) 27278 +/- 6118 (27.58 +/- 6.19) 24 27 27 1500 12 19 128 105.6 13374 404290 ( 408.82) 25600 +/- 6880 (25.89 +/- 6.96) 24 26 26 1800 12 19 128 104.8 13566 393760 ( 398.17) 29180 +/- 6880 (29.51 +/- 6.96) 19 30 30 2100 12 18 128 104.3 13614 381341 ( 385.61) 31603 +/- 5662 (31.96 +/- 5.73) 19 31 31 1700 12 18 128 104.9 13614 388178 ( 392.53) 26822 +/- 5662 (27.12 +/- 5.73) 20 30 30 2100 12 18 128 104.3 13614 385331 ( 389.65) 31669 +/- 5728 (32.02 +/- 5.79) 21 27 27 1500 12 19 128 105.6 13694 378650 ( 382.89) 25120 +/- 6400 (25.40 +/- 6.47) 21 26 26 1800 12 19 128 104.8 13886 369060 ( 373.19) 28700 +/- 6400 (29.02 +/- 6.47) 18 30 30 2100 12 18 128 104.3 13918 362816 ( 366.88) 31299 +/- 5339 (31.65 +/- 5.40) 19 27 27 1500 12 19 128 105.6 14014 355150 ( 359.13) 24680 +/- 5960 (24.96 +/- 6.03) 24 22 22 1900 12 20 128 104.5 14126 353597 ( 357.56) 30675 +/- 7224 (31.02 +/- 7.30) 19 26 26 1800 12 19 128 104.8 14206 346440 ( 350.32) 28260 +/- 5960 (28.58 +/- 6.03) 16 30 30 2100 12 18 128 104.3 14222 342581 ( 346.42) 30957 +/- 4997 (31.30 +/- 5.05) 18 27 27 1500 12 19 128 105.6 14334 337610 ( 341.39) 24360 +/- 5620 (24.63 +/- 5.68) 21 22 22 1900 12 20 128 104.5 14462 331652 ( 335.37) 30171 +/- 6720 (30.51 +/- 6.80) 18 26 26 1800 12 19 128 104.8 14526 329540 ( 333.23) 27940 +/- 5620 (28.25 +/- 5.68) 19 24 24 1400 12 20 128 106.7 14606 331471 ( 335.18) 23751 +/- 6258 (24.02 +/- 6.33) 16 27 27 1500 12 19 128 105.6 14654 318430 ( 322.00) 24000 +/- 5260 (24.27 +/- 5.32) 19 22 22 1900 12 20 128 104.5 14798 311555 ( 315.04) 29709 +/- 6258 (30.04 +/- 6.33) 16 26 26 1800 12 19 128 104.8 14846 311080 ( 314.56) 27580 +/- 5260 (27.89 +/- 5.32) 27 15 15 1900 12 23 128 104.7 15038 301478 ( 304.85) 32316 +/- 8964 (32.68 +/- 9.06) 18 22 22 1900 12 20 128 104.5 15134 296540 ( 299.86) 29373 +/- 5901 (29.70 +/- 5.97) 24 16 16 1500 12 23 128 106.6 15230 292902 ( 296.18) 26856 +/- 8256 (27.16 +/- 8.35) 27 14 14 1500 12 24 128 105.7 15374 288750 ( 291.98) 27887 +/- 9337 (28.20 +/- 9.44) 24 15 15 1900 12 23 128 104.7 15422 280766 ( 283.91) 31632 +/- 8256 (31.99 +/- 8.35) 16 22 22 1900 12 20 128 104.5 15470 280139 ( 283.28) 28995 +/- 5523 (29.32 +/- 5.58) 21 16 16 1500 12 23 128 106.6 15614 274662 ( 277.74) 26280 +/- 7680 (26.57 +/- 7.77) 18 19 19 2000 12 21 128 104.4 15742 271818 ( 274.86) 30820 +/- 6182 (31.17 +/- 6.25) 24 14 14 1500 12 24 128 105.7 15774 268625 ( 271.63) 27175 +/- 8600 (27.48 +/- 8.70) 19 16 16 1500 12 23 128 106.6 15998 257958 ( 260.85) 25752 +/- 7152 (26.04 +/- 7.23) 16 19 19 2000 12 21 128 104.4 16094 256968 ( 259.85) 30424 +/- 5786 (30.76 +/- 5.85) 21 14 14 1500 12 24 128 105.7 16174 252000 ( 254.82) 26575 +/- 8000 (26.87 +/- 8.09) 18 16 16 1500 12 23 128 106.6 16382 245478 ( 248.23) 25368 +/- 6744 (25.65 +/- 6.82) 16 18 18 1500 12 22 128 106.5 16526 248497 ( 251.28) 24693 +/- 6049 (24.97 +/- 6.12) 19 14 14 1500 12 24 128 105.7 16574 236775 ( 239.43) 26025 +/- 7450 (26.32 +/- 7.53) 16 16 16 1500 12 23 128 106.6 16766 231846 ( 234.44) 24936 +/- 6312 (25.22 +/- 6.38) 16 15 15 1900 12 23 128 104.7 16958 223526 ( 226.03) 29712 +/- 6312 (30.04 +/- 6.38) 18 14 14 1500 12 24 128 105.7 16974 225400 ( 227.92) 25625 +/- 7025 (25.91 +/- 7.10) 16 14 14 1500 12 24 128 105.7 17374 212975 ( 215.36) 25175 +/- 6575 (25.46 +/- 6.65) 14 16 16 1500 12 23 128 106.6 17918 208230 ( 210.56) 24192 +/- 5544 (24.46 +/- 5.61) 14 15 15 1900 12 23 128 104.7 18110 201398 ( 203.65) 28968 +/- 5544 (29.29 +/- 5.61) 15 14 14 1500 12 24 128 105.7 18174 198975 ( 201.20) 24662 +/- 6062 (24.94 +/- 6.13) 13 16 16 1500 12 23 128 106.6 18302 199206 ( 201.44) 23904 +/- 5256 (24.17 +/- 5.31) 14 14 14 1500 12 24 128 105.7 18574 191450 ( 193.59) 24400 +/- 5775 (24.67 +/- 5.84) 12 16 16 1500 12 23 128 106.6 18686 190182 ( 192.31) 23616 +/- 4968 (23.88 +/- 5.02) 12 15 15 1900 12 23 128 104.7 18878 184478 ( 186.54) 28392 +/- 4968 (28.71 +/- 5.02) 13 14 14 1500 12 24 128 105.7 18974 183225 ( 185.28) 24100 +/- 5475 (24.37 +/- 5.54) 12 14 14 1500 12 24 128 105.7 19374 175000 ( 176.96) 23800 +/- 5175 (24.07 +/- 5.23) 12 15 15 1300 12 24 128 108.0 19374 183675 ( 185.73) 21425 +/- 5175 (21.66 +/- 5.23) 11 14 14 1500 12 24 128 105.7 19774 168525 ( 170.41) 23575 +/- 4925 (23.84 +/- 4.98)
