Cemented granular materials (CGMs) consist of densely packed solid particles and a pore-filling solid matrix sticking to the particles. We use a sub-particle lattice discretization method to investigate the particle-scale origins of strength and failure properties of CGMs. We show that jamming of the particles leads to highly inhomogeneous stress fields. The stress probability density functions are increasingly wider for a decreasing matrix volume fraction, the stresses being more and more concentrated in the interparticle contact zones with an exponential distribution as in cohesionless granular media. Under uniaxial loading, pronounced asymmetry can occur between tension and compression both in strength and in the initial stiffness as a result of the presence of bare contacts (with no matrix interposed) between the particles. Damage growth is analyzed by considering the evolution of stiffness degradation and the number of broken bonds in the particle phase. A brutal degradation appears in tension as a consequence of brittle fracture in contrast to the more progressive nature of damage growth in compression. We also carry out a detailed parametric study in order to assess the combined influence of the matrix volume fraction and particlematrix adherence. Three regimes of crack propagation can be distinguished corresponding to no particle damage, particle abrasion and particle fragmentation, respectively. We find that particle damage scales well with the relative toughness of the particle-matrix interface with respect to the particle toughness. This relative toughness is a function of both matrix volume fraction and particle-matrix adherence and it appears therefore to be the unique control parameter governing transition from soft to hard behavior.