The Rivest-Sherman Ciphertext-Only Attacks on Enigma-Like Machines
Speaker: Dr. Alan T. Sherman , University of Maryland, Baltimore County (UMBC)
Date: May 12 2006
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva, Stata Ctr
Host: Ron Rivest, CIS, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: We present, mathematically analyze, and experimentally evaluate
ciphertext-only attacks on Enigma-like cryptographs that search for the
rotors one at a time. Devised by Rivest and Sherman in 1980, but
previously unpublished, the full attack is the first ciphertext-only
attack on Enigma proposed in the open literature. In its basic
one-stage version, the attack rank orders all possible choices for the
fastest-moving rotor and its initial position, given a basket of rotors
with known rotor wirings. The full attack repeatedly applies the
one-stage attack to guide a heuristic search for the key (all rotors in
the scrambler and their initial positions), examining fewer candidate
keys on average than does exhaustive search. In comparison with
exhaustive search, the full attack is more complicated but finds the
solution more quickly on average, for sufficiently large baskets (for a
three-rotor machine, a basket of six rotors suffices). Throughout we
work on a simplified model of Enigma similar to the Railway Enigma that
has no ring settings nor plugboard connections.
The one-stage Rivest-Sherman (RS) Attack evaluates each candidate
(rotor, initial position)-pair by computing a statistic equivalent to
the Index of Coincidence (IC) on the character string that is generated
by passing ciphertext through the candidate rotor starting in its
candidate initial position. The attack computes this statistic
separately for each block of 26 characters, during which only the
fastest-moving rotor spins. The correct pair generates a string whose
distribution is equivalent (up to permutation of the letter frequencies
within each block) to that created by passing plaintext through the
correct rotor. By contrast, incorrect rotors, and the correct rotor in
any wrong initial position, generate strings formed by passing
approximately uniform text through the candidate rotor. The full attack
heuristically searches for the (rotor, initial position)-pair for each
rotor in the scrambler, one rotor at a time, performing an
iteratively-broadening tree search. For each rotor to be determined,
the full attack orders all candidate pairs by their statistical scores.
This search tests complete candidate keys by decrypting the ciphertext
and checking for valid plaintext.
We evaluate the effectiveness of the RS-Attacks by determining
relationships between their following parameters: ciphertext length,
running time, and probability of success at finding the correct key.
Contrary to predictions by Rivest and Sherman, the correct (rotor,
initial-position)-pair tends to have a low statistical score rather than
a high score. The reason stems from fact that, within each block, the
statistic is a mixed-alphabet IC rather than a matching-alphabet IC. We
extend and revise Sherman's 1981 theoretical analysis to explain all of
our experimental findings.
Keywords. Ciphertext-only attacks, cryptanalysis, cryptography,
cryptology, Enigma cryptograph, iteratively-broadening tree search,
Railway Enigma, Rivest-Sherman Attacks, RS-Attacks, rotor machines,
statistical cryptanalysis, wired-wheel machines.
(Joint work with William Byrd, now at Indiana University)
Alan T. Sherman is associate professor of computer science at UMBC,
director of the UMBC Center for Information Security and Assurance
(CISA), editor of Cryptologia, and a cryptologic consultant.
See other events that are part of Cryptography and Information Security Seminar Seminars 2005/2006
See other events happening in May 2006
