Changes between Version 14 and Version 15 of NewMutableEncodingDesign

Timestamp:

2010-01-08T03:35:39Z (15 years ago)

Author:

davidsarah

Comment:

update for multi-target attacks

NewMutableEncodingDesign

@@ -12 +12 @@
  * [http://allmydata.org/pipermail/tahoe-dev/2009-September/002848.html The Elk Point design] is very interesting, and has not yet been transcribed into this wiki page.
 
+= Parameters K and T =
+
+Below, K is the security level needed for an attack against confidentiality:
+such attacks will require p * 2^K^ work factor (product of machine size and time)
+for a probability of success p. T is the additional number of bits needed to take
+into account
+[http://allmydata.org/trac/tahoe/ticket/882#comment:6 multi-target attacks] against
+hash functions, so that attacks against integrity also require p * 2^K^ work factor
+for 2^T^ target files.
+
 = Yay ECDSA =
 
@@ -23 +33 @@
 The RSA fields are so large that we clearly cannot put them in the filecaps,
 so the encoding scheme requires them to be stored in the shares, encrypted
-and hashed as necessary. The DSA keys are short enough (in most cases) to put
-directly in the filecap, simplifying the design considerably.
+and hashed as necessary. The ECDSA keys are short enough (in most cases) to put
+directly in the filecap, although note that this still increases the cap length
+relative to using a hash truncated to K+T bits.
 
 = Desired Features =
@@ -47 +58 @@
 == Filecap Length ==
 
-A likely security parameter K (=kappa) would be 96, 128, or 160 bits, and most of
-the filecaps will be some multiple of K. [96 bits is too short IMHO --David-Sarah]
+A likely security parameter K (=kappa) would be 96, 128, or 160 bits.
+[96 bits is too short IMHO --David-Sarah]
 
 Assuming a {{{tahoe:}}} prefix and no additional metadata, here's what
@@ -83 +94 @@
 [http://allmydata.org/trac/tahoe/ticket/882#comment:6 #882:c6] for a
 counterargument saying that 50 extra bits or so are needed to be secure
-against multi-target attacks.
+against multi-target attacks (i.e. T = 50). This page has now been updated
+assuming the counterargument is correct.
 
 = Design Proposals =
@@ -123 +135 @@
    material) (remember, K=kappa, probably 128bits)
  * (minimum 2K) readcap = minimum 2*K-bit semiprivate key
- * verifycap = 2*K-bit public key
+ * (minimum 2K) verifycap = public key
  * storage-index = truncated verifycap
 
@@ -142 +154 @@
  * (minimum 2K) readcap = minimum 2*K-bit first semiprivate key
  * (minimum 2K) traversalcap = minimum 2*K-bit second semiprivate key
- * verifycap = 2*K-bit public key
+ * (minimum 2K) verifycap = public key
  * storage-index = truncated verifycap
 
@@ -158 +170 @@
 private key out of the share and into the writecap:
 
- * (1K) writecap = K-bit random string = privkey
- * (3K) readcap = H(writecap)[:K] + H(pubkey)
- * verifycap = H(pubkey)
+ * (K) writecap = K-bit random string = privkey
+ * (2K + T) readcap = H(writecap)[:K] + H(pubkey)[:K+T]
+ * (K + T) verifycap = H(pubkey)[:K+T]
  * storage-index = truncated verifycap
 
@@ -166 +178 @@
 from one of the shares, since they cannot derive it themselves. This
 preserves offline attenuation and server-side validation. The readcap grows
-to (1+2)*K : we can truncate the AES key since we only need K bits for K-bit
-confidentiality, but require 2*K bits on H(pubkey) to attain K-bit collision
-resistance. The verifycap is 2*K.
+to 2K + T : we only need K bits for K-bit confidentiality, but require K+T bits
+on H(pubkey) to attain K-bit second-preimage resistance for 2^T^ targets. (To
+obtain collision-resistance, set T = K, although that shouldn't be necessary
+for mutable files.) The verifycap is K+T bits.
 
 === include ECDSA pubkey in cap ===
@@ -175 +188 @@
 requiring the client to fetch a copy:
 
- * (1K) writecap = K-bit random string = privkey
+ * (K) writecap = K-bit random string = privkey
  * (minimum 3K) readcap = H(writecap)[:K] + pubkey
- * verifycap = pubkey
+ * (minimum 2K) verifycap = pubkey
  * storage-index = H(pubkey)
 
-I think ECDSA pubkeys are 2*K long, so this would not change the length of
-the readcaps. It would just simplify/speed-up the download process. If we
-could use shorter pubkeys, this design might give us slightly shorter keys.
-Alternately, if we could use shorter hashes, then the H(pubkey) design might
-give us slightly shorter keys.
+ECDSA pubkeys are slightly more than 2*K long, so this would increase the
+length of the readcaps whenever K > T. The advantage would be simplifying/speeding up
+the download process. It is highly unlikely that there is any public key algorithm
+with keys shorter than 2*K for a K-bit security level. Since we can use shorter
+hashes than public keys, the H(pubkey) design above gives us shorter read caps,
+although they are not shorter than using semi-private keys.
 
 === Any public key algorithm, no semi-private keys, with traversalcap ===
 
-Since a secure pubkey identifier (either H(pubkey) or the original privkey)
+Since a secure pubkey identifier (either H(pubkey)[:K+T] or the original privkey)
 is present in all caps, it's easy to insert arbitrary intermediate levels. It
 doesn't even change the way the existing caps are used:
 
  * (1K) writecap = K-bit random string = privkey
- * (3K) readcap = H(writecap)[:K] + H(pubkey)
- * (3K) traversalcap: H(readcap)[:K] + H(pubkey)
- * verifycap = H(pubkey)
+ * (2K + T) readcap = H(writecap)[:K] + H(pubkey)[:K+T]
+ * (2K + T) traversalcap: H(readcap)[:K] + H(pubkey)[:K+T]
+ * (K + T) verifycap = H(pubkey)[:K+T]
  * storage-index = truncated verifycap