wiki:OneHundredYearCryptography

Version 8 (modified by zooko, at 2010-11-14T06:16:44Z) (diff)

link to simulator in source

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.

The basic 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, I believe, 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: maybe AES-128 because it wastes fewer CPU cycles and is plenty secure. Indeed, if you worry too much about the related key model (which I don't since we never use related keys in Tahoe-LAFS) then AES-128 is arguably safer than AES-256!
  • What KDF is used to generate the keys/IVs? I think Zooko suggested using XSalsa20, but I haven't seen a concrete proposal. 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.

Hashing

We'll combine two hash functions using the Comb4P hash function combiner, which preserves most (but not all) security properties of the hashes. It also has the advantage of being simple and relatively fast, 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 uses.

Signatures

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

Brian and David-Sarah wrote a simulator​ or two to explore performance trade-offs in hash-based signature parameters. The output of one run with the following parameters is this: 

# range of hash output lengths
range_L_hash = [128]

lg_M = 53                   # lg(required number of signatures before losing security)

limit_bytes = 480000        # 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

  w   A   h    T    lg_N   L_GMSS (bytes)   c_S_mean (Mcycles)  c_S_worst (Mcycles)   score
 13  18   1   62   258.5    97524 (12191)      97272 (  98.36)     193095 ( 195.26)    +5.4 %
 13  17   1   63   257.5    99072 (12384)      93344 (  94.39)     185280 ( 187.36)    +5.0 %
 13  16   1   64   256.0   100620 (12578)      89245 (  90.24)     177125 ( 179.11)    +4.5 %
 13  15   1   66   257.9   103716 (12965)      86195 (  87.16)     171118 ( 173.03)    +3.7 %
 12  18   1   62   258.5   105651 (13207)      83097 (  84.03)     164745 ( 166.59)    +4.3 %
 13  14   1   68   258.9   106812 (13352)      82869 (  83.80)     164496 ( 166.34)    +2.6 %
 12  17   1   63   257.5   107328 (13416)      79744 (  80.64)     158080 ( 159.85)    +3.9 %
 12  16   1   64   256.0   109005 (13626)      76245 (  77.10)     151125 ( 152.82)    +3.3 %
 11  19   1   61   259.1   111972 (13997)      72757 (  73.57)     144026 ( 145.64)    +6.2 %
 11  18   1   62   258.5   113778 (14223)      70056 (  70.84)     138663 ( 140.22)    +5.9 %
 11  17   1   63   257.5   115584 (14448)      67232 (  67.98)     133056 ( 134.55)    +5.5 %
 11  16   1   64   256.0   117390 (14674)      64285 (  65.00)     127205 ( 128.63)    +4.9 %
 11  15   1   66   257.9   121002 (15126)      62075 (  62.77)     122878 ( 124.25)    +4.2 %
 11  14   1   68   258.9   124614 (15577)      59685 (  60.35)     118128 ( 119.45)    +3.1 %
 11  13   1   70   259.0   128226 (16029)      57048 (  57.69)     112890 ( 114.15)    +1.7 %
 11  12   1   72   258.1   131838 (16480)      54166 (  54.77)     107164 ( 108.36)    +0.0 %
 10  16   1   64   256.0   134160 (16770)      53365 (  53.96)     105365 ( 106.55)    -4.5 %
 11  11   1   75   259.5   137256 (17157)      51642 (  52.22)     102220 ( 103.36)    -2.1 %
 10  14   1   68   258.9   142416 (17802)      49542 (  50.10)      97842 (  98.94)    -6.2 %
 11  10   1   78   259.1   142674 (17835)      48822 (  49.37)      96617 (  97.70)    -4.9 %
  9  18   1   62   258.5   146286 (18286)      47376 (  47.91)      93303 (  94.35)    -7.6 %
 11   9   1   81   256.8   148092 (18512)      45633 (  46.14)      90282 (  91.29)    -8.5 %
  9  17   1   63   257.5   148608 (18576)      45472 (  45.98)      89536 (  90.54)    -8.0 %
  9  16   1   64   256.0   150930 (18867)      43485 (  43.97)      85605 (  86.56)    -8.5 %
  9  15   1   66   257.9   155574 (19447)      41975 (  42.45)      82678 (  83.60)    -9.1 %
  8  19   1   61   259.1   159960 (19995)      39184 (  39.62)      76880 (  77.74)    -6.8 %