Changes between Version 20 and Version 21 of NewMutableEncodingDesign


Ignore:
Timestamp:
2012-01-10T21:06:17Z (13 years ago)
Author:
davidsarah
Comment:

update for Ed25519, and fix a bug that would allow meet-in-the-middle attacks against the private exponent

Legend:

Unmodified
Added
Removed
Modified
  • NewMutableEncodingDesign

    v20 v21  
    3333The RSA fields are so large that we clearly cannot put them in the filecaps,
    3434so the encoding scheme requires them to be stored in the shares, encrypted
    35 and hashed as necessary. The ECDSA keys are short enough (in most cases) to put
     35and hashed as necessary. The Ed25519 keys are short enough (in most cases) to put
    3636directly in the filecap, although note that this still increases the cap length
    3737relative to using a hash truncated to K+T bits.
     
    8585   same way as immutable files. Shares include a merkle tree over the share
    8686   blocks, and a second one over the ciphertext segments.
    87  * we'd like to add a merkle tree over the plaintext, without reintroducing
     87 * we'd like to add a Merkle tree over the plaintext, without reintroducing
    8888   the partial-information-guessing attack that prompted us to remove it.
    8989   This means encrypting the nodes of this merkle tree with a key derived
     
    107107   collision-resistance criteria.
    108108
    109 == ECDSA, semi-private keys, no traversalcap ==
     109== ECDSA or Ed25519, semi-private keys, no traversalcap ==
    110110
    111111Zooko captured the current leading semi-private-key-using mutable file design
     
    148148is the pubkey, and that can't be used to protect the data because it's public
    149149(and used by the server to validate shares). One approach is to use the
    150 current (discrete-log DSA) mutable file structure, and merely move the
    151 private key out of the share and into the writecap:
    152 
    153  * (K + T) writecap = (K+T)-bit random string = privkey
    154  * (2K + T) readcap = H(writecap)[:K] + H(pubkey)[:K+T]
     150current mutable file structure (with any signature algorithm), and merely
     151move the private key out of the share and into the writecap:
     152
     153 * (K + T) writecap = (K+T)-bit random string
     154 * (2K) privkey = H(writecap)
     155 * (2K + T) readcap = H(privkey)[:K] + H(pubkey)[:K+T]
    155156 * (K + T) verifycap = H(pubkey)[:K+T]
    156157 * storage-index = verifycap
     
    164165for mutable files.) The verifycap is K+T bits.
    165166
    166 === include ECDSA pubkey in cap ===
     167=== include ECDSA or Ed25519 pubkey in cap ===
    167168
    168169Or, if the pubkey is short enough, include it in the cap rather than
    169170requiring the client to fetch a copy:
    170171
    171  * (K + T) writecap = (K+T)-bit random string = privkey
    172  * (minimum 3K) readcap = H(writecap)[:K] + pubkey
     172 * (K + T) writecap = (K+T)-bit random string
     173 * (2K) privkey = H(writecap)
     174 * (minimum 3K) readcap = H(privkey)[:K] + pubkey
    173175 * (minimum 2K) verifycap = pubkey
    174176 * storage-index = H(pubkey)
    175177
    176 ECDSA pubkeys are slightly more than 2*K long, so this would increase the
    177 length of the readcaps whenever K > T. The advantage would be simplifying/speeding up
    178 the download process. It is highly unlikely that there is any public key algorithm
     178The hash to obtain the privkey is necessary because directly using a (K+T)-bit
     179exponent would allow meet-in-the-middle attacks. ECDSA or Ed25519 pubkeys are
     180slightly more than 2*K long, so this would increase the length of the readcaps
     181because 2*K > T. The advantage would be simplifying/speeding up the download
     182process. It is highly unlikely that there is any public key algorithm
    179183with keys shorter than 2*K for a K-bit security level. Since we can use shorter
    180184hashes than public keys, the H(pubkey) design above gives us shorter read caps,
     
    183187=== Any signature algorithm, no semi-private keys, with traversalcap ===
    184188
    185 Since a secure pubkey identifier (either H(pubkey)[:K+T] or the original privkey)
     189Since a secure pubkey identifier (either H(pubkey)[:K+T] or the original writecap)
    186190is present in all caps, it's easy to insert arbitrary intermediate levels. It
    187191doesn't even change the way the existing caps are used:
    188192
    189  * (K + T) writecap = (K+T)-bit random string = privkey
    190  * (2K + T) readcap = H(writecap)[:K] + H(pubkey)[:K+T]
     193 * (K + T) writecap = (K+T)-bit random string
     194 * (2K) privkey = H(writecap)
     195 * (2K + T) readcap = H(privkey)[:K] + H(pubkey)[:K+T]
    191196 * (2K + T) traversalcap: H(readcap)[:K] + H(pubkey)[:K+T]
    192197 * (K + T) verifycap = H(pubkey)[:K+T]