Effiicient sampling of the structure of cryptographic generators' state transition graphs
Cryptographic generators like the A5/1 are finite state machines with deterministic transition functions. Their state transition graphs cannot be analyzed analytically, nor can they be explored completely because of their size which typically is at least n = 2^64. Yet, their structure, i.e. number and sizes of weakly connected components, is of interest because a structure deviating significantly from expected values for random graphs may indicate a weakness or backdoor. By sampling, one randomly chooses k nodes, derives their distribution onto connected components by graph exploration, and extrapolates these results to the complete graph. In known algorithms, the computational cost to determine the component for one randomly chosen node is up to O(pn), which severely restricts the sample size k. We present an algorithm where the computational cost to find the connected component for one randomly chosen node is O(n^1/2), so that a much larger sample size k can be analyzed in a given time. We report on the performance of a prototype implementation, and about preliminary analysis for several generators.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten