Strong stationary times and its use in cryptography
This addresses security vulnerabilities for cryptographic systems by providing a novel approach to timing-attack immunity, though it appears incremental in leveraging existing SST techniques.
The paper tackles the problem of timing attacks in cryptography by proposing a new class of algorithms based on Strong Stationary Times (SST), which stop according to a stopping rule to ensure perfect samples from a uniform distribution and immunity to timing attacks, and demonstrates applicability in constructing symmetric encryption schemes immune to such attacks.
This paper presents applicability of Strong Stationary Times (SST) techniques in the area of cryptography. The applicability is in three areas: *) Propositions of a new class of cryptographic algorithms (pseudo-random permutation generators) which do not run for the predefined number of steps. Instead, these algorithms stop according to a stopping rule defined as SST, for which one can obtain provable properties: *** results are perfect samples from uniform distribution, *** immunity to timing attacks (no information about the resulting permutation leaks through the information about the number of steps SST algorithm *) We show how one can leverage properties of SST-based algorithms to construct an implementation (of a symmetric encryption scheme) which is immune to the timing-attack by reusing implementations which are not secure against timing-attacks. In symmetric key cryptography researchers mainly focus on constant time (re)implementations. Our approach goes in a different direction and explores ideas of input masking. *) Analysis of idealized (mathematical) models of existing cryptographic schemes -- i.e., we improve a result by Mironov ((Not So) Random Shuffles of RC4; Advances in Cryptology -- CRYPTO 2002)