[Colloquium] [masters-presentation] /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

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=