Implantable medical devices, sensors and wearables are widely deployed today. However, establishing a secure wireless communication channel to these devices is a major challenge, amongst others due to the constraints on energy consumption and the need to obtain immediate access in emergencies. To address this issue, researchers have proposed various key agreement protocols based on the measurement of physiological signals such as a person’s heart signal. At the core of such protocols are fuzzy cryptographic primitives that allow to agree on a shared secret based on several simultaneous, noisy measurements of the same signal. So far, although many fuzzy primitives have been proposed, there is no comprehensive evaluation and comparison yet of the overhead that such methods incur on resource-constrained embedded devices. In this paper, we study the feasibility of six types of fuzzy cryptographic primitives on embedded devices for 128-bit key agreement. We configure several variants for each fuzzy primitive under different parameter selections and mismatch rates of the physiological signal measurements on an MSP430 microcontroller, and then measure and compare their energy consumption and communication overhead. The most efficient constructions consume between 0.021 mJ and 0.198 mJ for the transmitter and between 0.029 mJ and 0.380 mJ for the receiver under different mismatch rates. Subsequently, we modify the best performing methods so that they run in constant time to protect against timing side-channel attacks, and observe that these changes only minimally affect resource consumption. Finally, we provide open-source implementations and energy consumption data of each fuzzy primitive as a reference for real-world designs.