Probabilistic fasteners are known to provide strong attachment onto their respective surfaces. Examples are Velcro® and the "3M dual lock"system. However, these systems typically only function using specific counter surfaces and are often destructive to other surfaces such as fabrics. Moreover, the design parameters to optimize their functionality are not obvious. Here, we present a surface patterned with soft micrometric features inspired by the mushroom shape showing a nondestructive mechanical interlocking and thus attachment to fabrics. We provide a scalable experimental approach to prepare these surfaces and quantify the attachment strength with rheometric and video-based analysis. In these "probabilistic fasteners,"we find that higher feature densities result in higher attachment force; however, the individual feature strength is higher on a low feature density surface. We interpret our results via a load-sharing principle common in fiber bundle models. Our work provides new handles for tuning the mechanical attachment properties of soft patterned surfaces that can be used in various applications including soft robotics.