wiki:NewCaps/WhatCouldGoWrong

Version 31 (modified by davidsarah, at 2009-10-11T15:17:43Z) (diff)

note attacks better than brute-force on Merkle-Damgård hashes

This is about What Could Go Wrong with the "Elk Point 2" immutable file caps: http://zooko.com/immutable-elkpoint-2.svg (http://zooko.com/immutable-elkpoint-2.png if your browser does not correctly handle SVG.)

#what bad thing could happenhowwho could do itwhat could they targetwhat crypto property prevents ithow expensive to brute force [footnote 5]
1shape-shifter immutable file [footnote 1]collide read-cap (R,T)creator of a filetheir own filethe hash function's and cap format's collision resistance on the read-cap (R,T). This also depends on the encryption of K1 being deterministic and correct.2(r+t)/2
2unauthorized readattack the encryption of K1 with Ranyoneany one filethe security of the encryption scheme used for K1, and the secrecy of the read-key R2min(r,k)
3forgery of immutable filegenerate a matching read-cap (R,T) for someone else's fileanyoneany one filethe hash function's and cap format's second-preimage resistance on (R,T). This also depends on the encryption of K1 being deterministic and correct.2r+t [footnote 7]
4roadblock or speedbump [footnote 2]generate (K1enc,Dhash,V) that hash to someone else's T, and copy their Sanyone [footnote 6]any one filethe hash function's and cap format's second-preimage resistance on T2t
5unauthorized readattack the encryption of the plaintext with K1anyoneany one filethe security of the encryption scheme used for the plaintext, and the secrecy of the encryption key K1. The latter also depends on the security and seeding of the RNG that generated it.2k
6unauthorized readfigure out the input to the hash function that generates Sanyoneany one filethe hash function's onewayness for (R,T) -> Sbrute force on R is #2
7unauthorized deletionbrute force KDanyoneany one filesecrecy of KD2d
8unauthorized deletionfigure out a working destroy key KD from Dhashanyoneany one filethe hash function's preimage resistance on Dhash2min(d,dh)
9denial of serviceprevent access to servers holding sufficient shares (by controlling some of them, or by attacking them or the network)anyoneany filenot prevented by crypton/a
10cause invalid share to verifygenerate (K1enc,Dhash,V) that hash to someone else's (T,U), and copy their Sanyoneany one filethe hash function's second-preimage resistance on (T,U)2t+u [footnote 7]
11undeletion [footnote 3]restore a deleted file's shares by controlling the relevant serversanyoneany one filenot prevented by crypton/a
12undeletion [footnote 3]generate matching (R,T,U) for a deleted fileanyoneany one filethe hash function's and cap format's second-preimage resistance on (R,T,U)2r+t+u [footnote 7]
13accidental collisionstorage indices (S1,T1) and (S2,T2) collide accidentallyn/aany two filesapproximately random distribution of hash function outputs[footnote 4]

where k = bitlength(K1), r = bitlength(R), s = bitlength(S), t = bitlength(T), u = bitlength(U), d = bitlength(KD), dh = bitlength(Dhash).

(The notes to the diagram assume k == r.)

  1. shape-shifter immutable file: creator creates more than one file matching the immutable file readcap
  1. roadblock: attacker prevents uploader (including repairer) from being able to write a real share into the right storage index; speedbump: attacker adds his bogus share into the list of shares stored under the storage index by the same method; downloader has to download, examine, and discard the bogus (K1enc,Dhash,V)'s until it finds the real one. Also see http://allmydata.org/pipermail/tahoe-dev/2009-October/002959.html
  1. undeletion: attacker makes a deleted file (for which it need not have had a read cap) accessible at its previous storage index, and readable by previous read caps
  1. See the probability table at http://en.wikipedia.org/wiki/Birthday_Paradox . The effective hash length is approximately min(s,r)+t bits.
  1. Brute force costs assume a single-target attack that is expected to succeed with high probability. Costs will be lower for attacking multiple targets or for a lower success probability. (Should we give explicit formulae for this?)
  1. roadblock/speedbump attacks could be restricted to holders of a read cap by use of an extra signature, as in the Elk Point 3 design (diagram at http://jacaranda.org/tahoe/mutable-addonly-elkpoint-3.svg for mutable files).
  1. On Merkle-Damgård hashes with an internal state that is the same size as the hash output, there are better second-preimage attacks than brute force. See http://www.schneier.com/paper-preimages.pdf . This is not significant for roadblock/speedbump attacks because the internal state will be much larger than t bits, but it is significant for the other attacks.