wiki:NewCaps/WhatCouldGoWrong

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

http://jacaranda.org/tahoe/immutable-elkpoint-2.png

#what bad thing could happenhowwho could do itwhat could they targetwhat crypto property prevents ithow expensive to brute force [footnote 9]
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, and on the suitability of hash_r as a KDF (key derivation function).approx sqrt(2.p).2(r+t)/2 [footnotes 7,8]
2unauthorized readattack the encryption of K1 with Ranyoneany one filethe security of the encryption scheme used for K1, the secrecy of the read-key R, and the suitability of hash_r as a KDF.(p/N).2min(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, and on the suitability of hash_r as a KDF.(p/N).2r+t [footnotes 5,8]
4roadblock or speedbump [footnote 2]generate (EncK1,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 T(p/N).2t
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, and on resistance to attack #2.(p/N).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 deletionfigure out a working destroy-key KD for a given Dhashanyoneany one filethe hash function's preimage resistance on Dhash and the secrecy of KD(p/N).2min(d,dh)
8accidental collisionstorage indices (S1,T1) and (S2,T2) collide accidentallynot applicableany two filesapproximately random distribution of hash function outputs[footnote 4]
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 cryptonot applicable
10cause invalid share to verifygenerate (EncK1,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)(p/N).2t+u [footnote 5]
11undeletion [footnote 3]restore a deleted file's shares by controlling the relevant serversanyoneany one filenot prevented by cryptonot applicable
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)higher cost than #3

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.)

p is the success probability of an attack (0 < p <= 1). N is the number of targets for preimage attacks; this assumes that the attacker has stored the relevant hashes for N files and is content with finding a preimage for any of them. Note that since the attacker must also expend work to obtain each target hash, the cost of brute force cannot be reduced below a "square root" attack. For example, the work to forge an immutable file (attack #3) by brute force cannot be reduced to less than sqrt(p).2(r+t)/2 (roughly the same work as a collision attack), no matter how many targets are available.

  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 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 https://en.wikipedia.org/wiki/Birthday_attack . The effective hash length is approximately min(s,r)+t bits.
  1. On Merkle-Damgård hashes with an internal state that is the same size as the hash output (like SHA-256), there are better second-preimage attacks than brute force. See https://www.schneier.com/paper-preimages.pdf . The doubled "SHA-256d" construction used by Tahoe does not help here. 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 second-preimage attacks.
  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. The formula given in the Wikipedia Birthday Attack page is sqrt(2.ln(1/(1-p))).2(r+t)/2, but the approximation given here is very accurate for small p, and can only underestimate the cost. For p = 1/2 it underestimates by only a factor of 1.18. For p near 1 it underestimates severely; it is very hard for an attacker to be certain to find a collision.
  1. In order for the combined hash with output (R,T) to have the strength against collision and preimage attacks given here, there must not be multicollision attacks against the hash truncated to r bits or to t bits, that would yield an easier attack on the combined hash. See tahoe-dev/2009-October/003006.html .
  1. The estimates given here are in terms of work factor, i.e. they are products of machine size and attack time. See this paper by Dan Bernstein for discussion of parallel brute-force attacks, including attacks against multiple keys at once. Note that the applicability of these multiple-key attacks depends on the encryption mode. CTR mode with a fixed IV would be particularly vulnerable, so I (Daira) think we should use a variable IV. (Bernstein prefers simply to make the key longer, which would be good advice for most protocols, but most protocols don't have the usability constraint of the key length contributing to URL length.)
Last modified at 2013-05-23T18:04:34Z Last modified on 2013-05-23T18:04:34Z