Building hardware security primitives with on-device memory fingerprints is a compelling proposition given the ubiquity of memory in electronic devices, especially for low-end Internet of Things devices for which cryptographic modules are often unavailable. However, the use of fingerprints in security functions is challenged by the small, but unpredictable variations in fingerprint reproductions from the same device due to measurement noise. Our study formulates a novel and pragmatic approach to achieve highly reliable fingerprints from device memories. We investigate the transformation of raw fingerprints into a noise-tolerant space where the generation of fingerprints is intrinsically highly reliable. We derive formal performance bounds to support practitioners to easily adopt our methods for applications. Subsequently, we demonstrate the expressive power of our formalization by using it to investigate the practicability of extracting noise-tolerant fingerprints from commodity devices. Together with extensive simulations, we have employed 119 chips from five different manufacturers for extensive experimental validations. Our results, including an end-to-end implementation demonstration with a low-cost wearable Bluetooth inertial sensor capable of on-demand and runtime key generation, show that key generators with failure rates less than $10^-6$ can be efficiently obtained with noise-tolerant fingerprints with a single fingerprint snapshot to support ease-of-enrollment.