wiki:OneHundredYearCryptography

Version 17 (modified by davidsarah, at 2011-12-21T22:25:13Z) (diff)

clarifications about hash-based digital sigs

See also NewCapDesign.

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
  • 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

David-Sarah has proposed to use hash-based digital signatures.

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 (stateful) hash-based digital signatures! Exciting fact: his implementation meets Zooko's performance criterion!

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)