A Generalized Birthday Problem, David Wagner.
Short version
(an extended abstract, as appeared in the proceedings of CRYPTO 2002)
Long version
(the full version of the paper, with further details and more attacks; currently in draft form)

Note: After this work was published at CRYPTO 2002, I discovered very significant prior work by Camion and Patarin. Please read the long version for a better discussion of related work and credit.