Title: Related-Key Linear Cryptanalysis of DES
Speaker: Darakhshan J. Mir, Rutgers University
Date: Wednesday, September 20, 2006 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
A coding theory framework is used to treat linear cryptanalysis as communication over a very noisy channel, and related-key linear cryptanalysis, as a concatenated code. We prove and further experimentally demonstrate (using the DES cipher) that a related-key attack using n related keys generated from k independent ones (such that n is greater than k), can improve the amortized cost, (in plaintext-ciphertext pairs per independent key) over that of k single key attacks. Moreover, we also demonstrate that, while the improvement in the cost is asymptotic, this improvement of related-key attacks on the error of single-key attacks does not require a particularly large number of related keys. As a specific example if, n=31 and k=21, there is an improvement of 26.2% over single-key linear cryptanalysis. A paper describing the theoretical results appears in the IEEE-ISIT 2006 and may be downloaded from http://www.seas.gwu.edu/~poorvi/RKA06.pdf.
This is work done with Poorvi Vora, as part of a Master's thesis at The George Washington University under her supervision.