At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 237 MD5 hash operations, and a collision of MD4 with complexity less than 28 MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 229 MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.