In this paper, we present a new distinguishing attack which works for secret prefix MAC based on 65-step (12-76) SHA-1. By birthday paradox, we first guarantee the existence of an internal collision at the output of the first iteration, then identify it by choosing the second message block smartly, and finally distinguish the specific MAC from a random function by making use of a near-collision differential path. The complexity of our new distinguisher is 2
queries with success probability 0.51. In comparison, we also present a distinguisher on secret prefix MAC instantiated with 63-step (8-70) SHA-1 according to Wang’s method introduced at FSE 2009 , which needs about 2
queries with success probability 0.70.