Highly stretchable strain sensors are key elements of new applications in wearable electronics and soft robotics. Most of the available technologies only measure positive strain (stretching), and cannot measure negative strains (compression). We propose here a stretchable technology that enables the measurement of both negative and positive strains with high sensitivity. A carbon nanotube paper is pre-cracked to introduce a well-controlled network of open cracks as the sensing element; then, the pre-cracked paper is sandwiched by thermoplastic elastomer. The resulting sensor is also pre-stretched and subjected to thermal annealing, which removes any residual stress so the pre-streched configuration remains stable. This process results in a stretchable structure with a network of open cracks that is sensitive to both negative and positive strains. We demonstrate that such sensors can measure negative strains up to -13% with high sensitivity and robust stretchability.