DSA Signing Key Recovery with Noisy Side Channels and Variable Error Rates

The Digital Signature Algorithm (DSA) computes a modular exponentiation with a per-message ephemeral secret. This involves a sequence of modulo square and multiply operations which, if known, enables an adversary to obtain the DSA private key. Cache-based side channel attacks are able to recover only discontiguous blocks of the ephemeral key thanks to the sliding window optimization implemented in many crypto libraries. Further, noisy side channels, rarely addressed in the literature, greatly complicate key retrieval. Through extensive experiments, we obtain estimates of the error rate as a function of block position and size. We demonstrate key retrieval in the presence of noise and model the time complexity of key recovery as a function of error rate. Our model exposes the tradeoff between number of signature operations that need to be monitored and the computational requirements for the attack. By selectively using interior blocks in the ephemeral key, we are able to retrieve the DSA private key with less than half the number of signatures required by previous work that use only the rightmost block.