Looking for needles in haystacks

Paul Crowley wrote “Here's a proper programming challenge, simple to state, and in the end quite challenging to solve. A function produces a 64-bit output given a 64-bit input. It mostly behaves like a random function, so given a random input, most outputs occur with probability between 0 and 2-63; in other words, for a randomly-chosen 64-bit y, there are usually between 0 and 2 solutions to the equation f(x) = y. However, a few occur with much greater frequency - more like 2-32 or so. The function is pretty quick and easy to calculate, but its internal structure defies direct analysis. How would you identify these more frequent occurrences by experiment? How big a computer would you need to do it in something like a few hours to a few days? Think about it for a while before you read on.”

Truncated differential cryptanalysis of five rounds of Salsa20

Paul Crowley wrote “eSTREAM have just put my paper online: Truncated differential cryptanalysis of five rounds of Salsa20 (PDF) (discussion, Wikipedia on Salsa20). This doesn’t break the whole cipher, just a seriously reduced version. Experimentation played a key role in finding this result. I found the first differential by writing a short Python program that implemented a pretty…”

Understanding “Understanding Brute Force”

Paul Crowley wrote “D J Bernstein's draft paper Understanding Brute Force argues that the way we currently measure the cost of cryptanalytic attacks is highly misleading. The paper is a good example of Bernstein's unconventional style, and mixes quite informal writing with very formal and precise descriptions of cryptanalytic methods and costs. Though his conclusions are correct, I think he hasn't quite put his finger on how people have come to be misled in the past, so I shall have a go here at arguing what I think is the same point in different words. ”


Paul Crowley wrote “Of the many new ciphers proposed as part of the ECRYPT Stream Cipher Project, one of the most interesting is Christophe De Cannière and Bart Preneel’s TRIVIUM. TRIVIUM is designed to be very simple, admit a very low gate count implementation in hardware, and be reasonably efficient in both hardware and software, parallelizing in a…”