Secure communications in wireless ad hoc networks require setting up end-to-end secret keys for communicating node pairs. Due to physical limitations and scalability requirements, full key-connectivity can not be achieved by key pre-distribution. In this paper, we develop an analytical framework for the on-demand key establishment approach. We propose a novel security metric, called REM resilience vector to quantify the resilience of any key establishment schemes against Revealing, Erasure, and Modification (REM) attacks. Our analysis shows that previous key establishment schemes are vulnerable under REM attacks. Relying on the new security metric, we prove a universal bound on achievable REM resilience vectors for any on-demand key establishment scheme. This bound that characterizes the optimal security performance analytically is shown to be tight, as we propose a REM-resilient key establishment scheme which achieves any vector within this bound. In addition, we develop a class of low complexity key establishment schemes which achieve nearly-optimal REM-attack resilience.