Through nonequilibrium molecular dynamics simulations, we provide an atomic-scale picture of the dynamics of particles near the surface of a medium under ultra-strong shocks. This shows that the measured surface velocity v_f under ultra-strong shocks is actually the velocity of the critical surface at which the incident probe light is reflected, and v_f has a single-peaked structure. The doubling rule commonly used in the case of relatively weak shocks to determine particle velocity behind the shock front is generally not valid under ultra-strong shocks. After a short period of acceleration, v_f exhibits a long slowly decaying tail, which is not sensitive to the atomic mass of the medium. A scaling law for v_f is also proposed, and this may be used to improve the measurement of particle velocity u in future experiments.