<div dir="ltr"><div class="gmail_default" style="font-family:garamond,serif"><br></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-16 2:04 GMT+02:00 Ryan Carboni <span dir="ltr"><<a href="mailto:ryacko@gmail.com" target="_blank">ryacko@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Aren't collisions checked manually to ensure that they actually are the same file? I don't really understand the intent of the question.</div>
</blockquote><div><br></div><div><div class="gmail_default" style="font-family:garamond,serif">​<span style="font-size:12.8px">No,  there are large sets of hashes that are distributed by organisations spending time on categorizing files and distributing the hashes with categorization to parties wanting to use these sets of hashes in a forensic investigations. In the forensic investigation, these hash sets are then used with the hashes calculated over files found on media in a set-theory way in order to focus both the automated and manual part of the digital forensic investigation.  Some of the hash sets are used as a "we can safely ignore these files" type of set. These include files from OS distributions, large collections of software packages, clipart collections, etc,etc. Basically the stuff that you don't want to waste man-hours , CPU-cycles or IO activity on.  Some sets are "A person needs to look at these" type of set. These sets are things like collections of the hashes of child pornographic images.</span></div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif"><br></div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">So there are three scenario's where a preimage attack could be a problem:</div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif"><br></div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">1) As an anti forensic technique, making an evidence containing file have a hash from one of the  "we can safely ignore these files" set.</div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">2) As denial of service attack on the human component of the investigation by making a relatively large set of non-legally-problematic files match with a hash from a "A person needs to look at these" set.</div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">3) As part of a targeted anti-forensic attack. Making a file that can exploit a flaw in a viewer for its file type match with a hash from a  "A person needs to look at these" set.</div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif"><br></div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">So basically if an attacker is able to successfully do a first preimage attack where the hash of the modified file matches "ANY ONE OF" of the hashes from the large set of hashes (for what we mostly don't have the original files).</div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif"><br></div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">Now my question is the following:</div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif"><br></div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">If the complexity of a first preimage attack for the used hasing algoritm is defined as 2^{N}, and the size of the hash-set that our "ANY ONE OF" implies is 2^{M}, what would be the worst case complexity of an  "ANY ONE OF" geared first preimage attack?</div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif"><br></div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif">I gather it would be smaller than 2^{N} yet probably not as small as the naive assumption of 2^{N-M}.  </div><div class="gmail_default" style="font-size:12.8px;font-family:garamond,serif"><br></div><div class="gmail_default" style="font-family:garamond,serif"><span style="font-size:12.8px">I hope my question is making more sense now.</span>​</div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">_______________________________________________<br>
The cryptography mailing list<br>
<a href="mailto:cryptography@metzdowd.com">cryptography@metzdowd.com</a><br>
<a href="http://www.metzdowd.com/mailman/listinfo/cryptography" rel="noreferrer" target="_blank">http://www.metzdowd.com/mailman/listinfo/cryptography</a><br></blockquote></div><br></div></div>