Changes between Version 53 and Version 54 of NewCaps/WhatCouldGoWrong


Ignore:
Timestamp:
2009-11-21T20:35:07Z (15 years ago)
Author:
davidsarah
Comment:

cost of brute-force multi-target preimage attacks can't be reduced to less than a collision attack

Legend:

Unmodified
Added
Removed
Modified
  • NewCaps/WhatCouldGoWrong

    v53 v54  
    2222(The notes to the diagram assume ''k'' == ''r''.)
    2323
    24 ''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.
     24''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.
    2525
    2626