[Colloquium] Akshima/MS Presentation/Dec 6, 2019

[Margaret Jaffey]

This is an announcement of Akshima’s MS Presentation.  

------------------------------------------------------------------------------
Date:  Friday, December 6, 2019

Time:  2:00 PM

Place:  John Crerar Library 298

M.S. Candidate:  Akshima 

M.S. Paper Title: Time-Memory Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions

Abstract:
We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary S-bit auxiliary advice input about the random oracle and T queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage Ω(ST^2/2^n), where n is the output length, beating the birthday bound by a factor of S. These attacks were shown to be optimal.
   
 We observe that the collisions produced are very long, on the order T blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find short collisions. We first exhibit a simple attack for finding B-block-long collisions achieving advantage Ω(STB/2^n). We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the ST^2/2^n bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length 1, length 2, and unbounded-length collisions: Namely, the optimal attacks achieve (up to logarithmic factors) order of (S+T)/2^n, ST/2^n and ST^2/2^n advantage.  We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.

Akshima's advisor is Prof. David Cash

Login to the Computer Science Department website for details:
https://newtraell.cs.uchicago.edu/phd/ms_announcements#akshima <https://newtraell.cs.uchicago.edu/phd/ms_announcements#akshima>

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey
Student Affairs Administrator
    for the PhD program
Department of Computer Science
The University of Chicago
John Crerar Library, Room 350
5730 S. Ellis Ave.

773-702-6011
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191122/eba580f4/attachment.html>