A Combinatorial Pattern Matching Problem with Applications to Cryptography
Jovan Golic
Information Security Research Centre,
Queensland University of Technology,
GPO Box 2434, Brisbane, Q 4001, Australia.
golic@fit.qut.edu.au
Luke O'Connor
Distributed Systems Technology Centre (DSTC),
Queensland University of Technology,
GPO Box 2434, Brisbane, Q 4001, Australia.
oconnor@dstc.edu.au
Abstract
A combinatorial problem of deriving the probability that a given binary string
of length $n$ can be embedded into a random uniformly distributed binary string
of length $n(d+1)$ by inserting at most $d$ bits between any two successive
bits and an arbitrary number of bits at the end is considered for an arbitrary
$d$. The problem is relevant for the initial state reconstruction of
a clock-controlled shift register that is clocked at
least once and at most $d+1$ times per output symbol, given a segment of
its output sequence. This is called the embedding attack and is of cryptologic
importance. An exponentially small upper bound on this probability is derived
for alternating strings by using finite automata theory and generating
functions. Results obtained by computer simulations indicate that this bound
also holds for arbitrary strings as well.
The minimum length of the observed output sequence
required for a successful embedding attack is then linear in the shift
register length and exponential in $d$.
Conference Home Page