This is about What Could Go Wrong with the "Rainhill 3" immutable file caps: http://jacaranda.org/tahoe/immutable-rainhill-3.svg

Wayback Machine link: https://web.archive.org/web/*/http://jacaranda.org/tahoe/*

Explanation by ccx:

> What I assume this to be is an encoding scheme for immutable directories that allows deriving deep-verify capability so that whole directory tree below can be verified recursively.
>
> This is done by encoding separately the readcaps of items contained in the directory (Plain_R) and verifycaps of the same items (Plain_V).
>
> By applying this scheme to the plaintexts together with convergence secret (CS) and encoding parameters you will get two encryption keys EncK_R and EncK_V for each part respectively.

(http://jacaranda.org/tahoe/immutable-rainhill-3.png or [attachment:immutable-rainhill-3.svg download the attached SVG] if your browser does not correctly handle SVG.)

[[Image(immutable-rainhill-3.svg)]]

The following table is based on a previous version of the protocol (Elk Point 2). It has been updated, but doesn't yet take into account attacks against the new features (incremental verification and deep-verify caps).

||#||''what bad thing could happen''||''how''||''who could do it''||''what could they target''||''what crypto property prevents it''||''how expensive to brute force'' [footnote 6]||
||1||shape-shifter immutable file [footnote 1]||collide read-cap (''R'',''T'')||creator of a file||their own file||the hash function's and cap format's collision resistance on the read-cap (''R'',''T''). This also depends on the hashes and PRP being correctly implemented, and on the suitability of hash_''k'' as a KDF (key derivation function).||approx sqrt(2.''p'').2^(''r''+''t'')/2^ [footnotes 4,5]||
||2||unauthorized read||attack the encryption of ''K_R'' with ''R''||anyone||any one file||the security of the PRP, the secrecy of the read-key ''R'', and the suitability of hash_''r'' as a KDF.||''p''.2^min(''r'',''k'')^ / ''m''||
||3||forgery of immutable file||generate a matching read-cap (''R'',''T'') for someone else's file||anyone||any one file||the hash function's and cap format's second-preimage resistance on (''R'',''T''). This also depends on the hashes and PRP being correctly implemented, and on the suitability of hash_''k'' and hash_''r'' as a KDF.||''p''.2^''r''+''t''^ / ''m'' [footnotes 3,5]||
||4||unauthorized read||attack the encryption of the plaintext with ''K_R''||anyone||any one file||the security of the encryption scheme used for the plaintext, and the secrecy of the encryption key ''K_R''. The latter also depends on the security and seeding of the RNG that generated it, and on resistance to attack !#2.||''p''.2^''k''^ / ''m''||
||5||unauthorized read||figure out the input to the hash function that generates ''S'' and/or ''V''||anyone||any one file||the hash function's onewayness for ''R'' -> ''V'' or ''V'' -> ''S''||brute force on ''R'' is !#2||
||6||accidental collision||storage indices (''S1'',''T1'') and (''S2'',''T2'') collide accidentally||not applicable||any two files||approximately random distribution of hash function outputs||[footnote 2]||
||7||denial of service||prevent access to servers holding sufficient shares (by controlling some of them, or by attacking them or the network)||anyone||any file||not prevented by crypto||not applicable||
||8||cause invalid share to verify||generate (''EncK_R'',''EncK_V'',''Q'') that hashes to someone else's ''T'', and copy their ''S''||anyone||any one file||the hash function's second-preimage resistance on ''T''||''p''.2^''t''^ / ''m'' [footnote 3]||

where ''k'' = bitlength(''K_*''), ''r'' = bitlength(''R''), ''s'' = bitlength(''S'') = bitlength(''V''), ''t'' = bitlength(''T'').

''p'' is the success probability of an attack (0 < ''p'' <= 1). ''m'' is the number of targets for preimage attacks; this assumes that the attacker has stored the relevant hashes for ''m'' 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

2. See the probability table at https://en.wikipedia.org/wiki/Birthday_attack . The effective hash length is approximately ''r''+''t'' bits.

3. 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 http://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.

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

5. 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 [//pipermail/tahoe-dev/2009-October/003006.html tahoe-dev/2009-October/003006.html].

6. The estimates given here are in terms of work factor, i.e. they are products of machine size and attack time. See [http://cr.yp.to/snuffle/bruteforce-20050425.pdf this paper by Dan Bernstein] for discussion of parallel brute-force attacks, including attacks against multiple keys at once.