Surface shedding of an asteroid is a failure mode where surface materials fly off due to strong centrifugal forces beyond the critical spin period, while the internal structure does not deform significantly. This paper proposes a possible structure of an asteroid interior that leads to such surface shedding due to rapid rotation rates. A rubble pile asteroid is modeled as a spheroid composed of a surface shell and a concentric internal core, the entire assembly called the test body. The test body is assumed to be uniformly rotating around a constant rotation axis. We also assume that while the bulk density and the friction angle are constant, the cohesion of the surface shell is different from that of the internal core. First, developing an analytical model based on limit analysis, we provide the upper and lower bounds for the actual surface shedding condition. Second, we use a Soft-Sphere Discrete Element Method (SSDEM) to study dynamical deformation of the test body due to a quasi-static spin-up. In this paper we show the consistency of both approaches. Additionally, the SSDEM simulations show that the initial failure always occurs locally and not globally. In addition, as the core becomes larger, the size of lofted components becomes smaller. These results imply that if there is a strong enough core in a progenitor body, surface shedding is the most likely failure mode.