In deep submicron CMOS transistors, the static leakage current has become a significant contributor to power consumption with channel length and subthreshold voltage being continuously scaled down. Also, this increased leakage has recently led to the rise of side-channel attacks on CMOS based implementations. Nanoelectromechanical System (NEMS) relay technology is emerging as an alternative to CMOS with one of its most prominent advantages being the zero static leakage, providing an inherent defense against power side-channel attacks at the same time. On the other hand, this emerging technology introduces timing challenges in the design process; to minimize the timing delay of NEMS relays, binary decision diagram (BDD) based implementation is utilized to design combinational logic. What's important from a security perspective is that the timing delay of the BDD implementation of a NEMS relay based design is inherently input dependent. An adversary can therefore leverage the data dependency to identify secret information of the chip. We propose a timing delay based attack on NEMS relay based designs, use AES as a case study, and show that it can achieve a success rate of 1.0 for interconnect delay variations within a standard deviation of 0.0022. To the best of our knowledge, this paper is the first to expose an inherent security vulnerability of a NEMS relay based design.