Second Preimages on n-bit Hash Functions by John Kelsey and Bruce Schneier
Ok, i figured out. I thought "M" - original message, but it's random data necessary for generation "Expandable Messages". In this case, range [ 0, 2^(n/2) ] is right.