Extensive efforts have been devoted in both the engineering and scientific domains to seek new designs and processing techniques capable of making stronger and tougher materials. One such method for enhancing such damage-tolerance in metallic alloys is a surface nano-crystallization technology that involves the use of hundreds of small hard balls which are vibrated using high-power ultrasound so that they impact onto the surface of a material at high speed (termed Surface Mechanical Attrition Treatment or SMAT). However, few studies have been devoted to the precise underlying mechanical mechanisms associated with this technology and the effect of processing parameters. As SMAT is dynamic plastic deformation process, here we use random impact deformation as a means to investigate the relationship between impact deformation and the parameters involved in the processing, specifically ball size, impact velocity, ball density and kinetic energy. Using analytical and numerical solutions, we examine the size of the indents and the depths of the associated plastic zones induced by random impacts, with results verified by experiment in austenitic stainless steels. In addition, global random impact and local impact frequency models are developed to analyze the statistical characteristics of random impact coverage, together with a description of the effect of random multiple impacts, which are more reflective of SMAT. We believe that these models will serve as a necessary foundation for further, and more energy-efficient, development of such surface nano-crystalline processing technologies for the strengthening of metallic materials.