Changes between Version 40 and Version 41 of NewCaps/WhatCouldGoWrong

Timestamp:

2009-10-11T16:57:11Z (15 years ago)

Author:

davidsarah

Comment:

correct formula for cost of collision attack #1

NewCaps/WhatCouldGoWrong

@@ -3 +3 @@
 
 ||#||''what bad thing could happen''||''how''||''who could do it''||''what could they target''||''what crypto property prevents it''||''how expensive to brute force''||
-||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 encryption of ''K1'' being deterministic and correct.||''p''.2^(''r''+''t'')/2^||
+||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 encryption of ''K1'' being deterministic and correct.||approx sqrt(2.''p'').2^(''r''+''t'')/2^ [footnote 7]||
 ||2||unauthorized read||attack the encryption of ''K1'' with ''R''||anyone||any one file||the security of the encryption scheme used for ''K1'', and the secrecy of the read-key ''R''||''p''.2^min(''r'',''k'')^||
 ||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 encryption of ''K1'' being deterministic and correct.||''p''/''N''.2^''r''+''t''^ [footnote 5]||
@@ -20 +20 @@
 (The notes to the diagram assume ''k'' == ''r''.)
 
-''p'' <= 1 is the success probability of an attack. ''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.
+''p'' is the success probability of an attack (0 < ''p'' <= 1), and ''c''(''p'') = sqrt(2.ln(1/(1-''p''))). (For example, ''c''(1/2) = 1.18 and ''c''(2^-40) = . For small ''p'', ln(1/(1-''p'')) approx= ''p''.)
+
+''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.
 
 
@@ -29 +31 @@
 3. ''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
 
-4. See the probability table at http://en.wikipedia.org/wiki/Birthday_Paradox . The effective hash length is approximately min(''s'',''r'')+''t'' bits.
+4. See the probability table at http://en.wikipedia.org/wiki/Birthday_Attack . The effective hash length is approximately min(''s'',''r'')+''t'' bits.
 
 5. 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.
 
 6. ''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).
+
+7. 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.