|
Home Page The Sigaba Home Page
|
PresentationThe following sections each describe an article or a thesis concerning the cryptanlysis of the Sigaba. I have given them in historical order. In short, it has three groups:
Design of the Sigaba and its cryptanalysis - 1940The American cryptanalysts who created the Sigaba made it immune to all types of attacks known at the time of its design. Because their knowledge was very extensive, the Sigaba still resists the most modern attacks today with the help of computers ... if we respect the operating procedures that completed the design of the machine in terms of security. Nevertheless, these American cryptanalysts knew that future attacks could defeat their creation. Thanks to their experience, they knew that prior to any attack, the enemy had to have the rotor wiring. This is why the procedures (link) were very rigorous to avoid this possibility (machine monitoring, rotor destruction procedure, spare rotor sets, planned obsolescence of the rotors, ...). But it is also possible to reconstruct this wiring even without having physical access to the rotors by the simple cryptanalyst. But for this, it is necessary to have several "in-depth" messages. American cryptanalysts estimated that the enemy had to have at least 10 superimposed messages in order to deduce the rotor wiring. It can also be noted that this was the main fear among the designers of the German army's Enigma. Once again, the Sigaba's operating procedures do everything to avoid this possibility (link). John Savard and Richard Pekelney – 1999
PresentationAlthough some information has leaked since 1940, it was necessary to wait for the article by Savard and Pekelney to have a complete description of the functioning of the Sigaba. This precise knowledge of the Sigaba was made possible thanks to the US Army and Navy declassified many documents describing the Sigaba and the inspection of an authentic Sigaba. Knowledge of how Sigaba works was obviously a prerequisite before any attack development. The article by Savard and Pekeney is not limited to a simple description of the machine but has a chapter concerning the cryptanalyst of the machine. Two types of attack are proposed. On the other hand, no details are provided for a concrete implementation of these attacks. Exhaustive attack (we know the rotor wiring)First, a "brut force" type attack is considered but quickly dismissed. Explicitly, it consists of trying all the configuration possibilities: rotor order, orientation and starting positions. It requires prior knowledge of the rotor wiring. The number of possibilities is astronomical. The key space is of the order of 96 bits, well beyond our current possibilities in terms of calculations. On the other hand, if we base ourselves on the practices of use of the machine, an attack is compatible with the current computing power. For example, if we inspect the rules in force in the Navy, the starting position of the control rotors is given in the header of the cryptogram. On the other hand, we always use the same order of the index rotors. In this case, the length of the key goes down to 49 bits (in fact 48.6) which allows a brute force attack with the help of computers. Second attack: Superposition (we don't know the wiring)In the case where the rotor wiring is unknown, the authors suggest an attack based solely on the knowledge of several messages (10 to 15) encrypted with the same key (therefore in-depth). From these messages the plaintext of the messages is deduced. Then the wiring of the encryption rotors is deduced. Other methods to deduce the wiring of the control rotors are suggested. This type of attack is, as we see, inspired by Army/Navy documents. Lee - 2003IntroductionLee proposes simplified situations: the attack of a machine equipped with one, two or three cipher rotors. The action of the control rotors is seen as a whole: a flow of random movement of the cipher rotors like the ancestor of the Sigaba whose advancement of the rotors was controlled by a Telex tape.Attack of a rotor (wiring unknown)We need to find the wiring of an encryption rotor. We have a cryptogram and a crib that gives crypto/plain pairs. The goal is to find the wiring of the encryption rotor alone. Note: for testing, we can take a real Sigaba for which the other 4 rotors are wired to provide the identity permutation: A=>A, B=>B, …. The technique used is of the “Brut Force” type, in short we try all the possibilities. We need a Crib of at least 20 characters. We deduce not only the wiring of the rotor but also the sequence of advancement of the rotors. Attack of a machine with 2,3,.. rotors (wiring known)The second attack proposed by Lee assumes knowledge of the rotor wiring and a Crib. His method allows to find the configuration (order of the rotors, their orientation and their starting position) as well as the sequence of advancement of the rotors. The author describes in detail his attack in the case where only 2 or 3 encryption rotors are used. An attack on a machine equipped with 5 rotors is considered but is not described in detail. The author estimates that it can be carried out in less than a day of calculation. Wing On Chan & Stamp– 2007AssumptionsThe wiring of the 15 rotors is assumed to be known. The 10 rotors with 26 contacts are assumed to be set to normal or reversed mode. However, the 5 index rotors (with 10 contacts) can only be set to normal (non-reverse) mode. The key is not indicated in the message header. The key for the encryption and control rotors are different. Under these conditions, the key space is 95.8 bits (beyond 70 bits, the current limit of resolution by exhaustive attack).The attack (plain text known)Chan's attack is basically a brute force type attack with some tricks. The attack consists of two phases (described below).Phase 1We consider all possible configurations for the encryption rotors (order of the rotors, normal/reverse orientation of each rotor, initial position of each rotor). For each one, we keep the configurations compatible with the known clear/crypto pairs.Key space: 43.4 bits. The advancement of the rotors (apparently random) means that for many different initial positions of the rotors, we obtain after a few steps, the same configurations. We note that at each step, there are 30 possible combinations of advancement of the 5 rotors. Chan (unlike Lee) takes this phenomenon into account and stores the plausible configurations in a tree accordingly. This drastically reduces the tests to be performed. Chan estimates that with a Crib of 30 letters, 0.427% of the configurations survive. With a Crib of 100 letters, approximately 0.2% of the configurations remain. In short, with a crib of 100 letters, the remaining key space is 34.5 bits (about 24 billion). Phase 2We consider the remaining configurations of the cipher rotors and try to determine the configuration of the control rotors. The index rotors are considered in a special way: we take the equivalent of a permutation of 10 digits. For each configuration of the cipher rotors, there are 2**35.41 configurations of the control rotors and 2**16.8 of the index rotors. In short, we have a key space of 52.2 bits (for each remaining configuration of the cipher rotors).Note: Chan's thesis then indicates some tricks to reduce the number of computations. ConclusionAccording to Chan, the Sigaba keyspace used by the Navy has a keyspace of 48.4 bits. In the Roosevelt-Churchill (POTUS-PRIME) liaison, the indicator method does not reduce the keyspace which is therefore 95 bits. The attack proposed by Chan concludes that with a 100-letter crib, he obtains the correct key with 82% success with a keyspace of 84.5 bits (41.1 for phase 1, 43.4 for phase 2). In any case, the proposed attack is beyond the possibilities of the time (2007).Mark Stamp and Richard M. Low. 2007Broadly echoes Stamp & Chan's presentation.Heather Ellie Kwong – 2008OverviewKwong’s attack follows Chan & Stamp’s approach: This is a known plaintext attack. The rotor wiring is known. The key space is theoretically 102.3 bits. The index rotors are assumed not to be inverted, which reduces the key space to 95.6 bits. The attack is divided into two phases: the first searches for plausible configurations of the cipher rotors. Plausible in the sense compatible with the known crypto/plaintext letter pairs. The second phase studies all the possibilities of the control and index rotors.The key space for the first phase is 43.4 bits. At each step of advancement of the rotors, there are 30 possibilities of advancement. For the second phase, for each configuration of the cipher rotors retained, the key space is 52.2 bits. In total (43.4 + 52.2), this makes 95.6 bits. Kwong’s softwareKwong wrote a program in C++. In his thesis, he gives the pseudo-code. A graphical interface allows the cryptanalyst to choose the cryptogram, the plaintext, the part of the key to study (order and position of the initial and final rotors) and the crib length to use.For the first phase, an exhaustive attack takes about 70 hours. The second phase takes about 2 hours for each configuration tested. This makes about 40 years of calculation for a complete attack. Kwong studies the performance of his program for cribs of 5 to 150 letters. ConclusionThe attack presented in Kwong's thesis is unrealistic if we do not apply the restrictions in use at the time of WWII.On the other hand, Kwong wrote a program in C++ that he describes and that concretely allows an attack of the Sigaba by restricting the key space. Lasry – 2019OverviewThis new attack assumes that the rotors' wiring is known, but that their order, orientation, and starting positions are unknown. It is inspired by the attack described by Chan, and also consists of two phases.Chan's attack is generally an exhaustive attack. Lasry's is a divide-and-conquer type in MITM (Man-in-the-middle) mode. It requires only a small Crib (8 letters) and a payload of about 60.1 bits (much smaller than an exhaustive attack). The attack is feasible but requires a large configuration: a computer equipped with at least 80 GB of memory. Phase 1Phase 1 produces a list of plausible configurations. Each stored configuration (in a table in memory) includes the order of the rotors, their orientation and their initial position as well as the advancement of the rotors for each letter of the Crib (limited to 8 letters). This configuration is considered plausible in the sense that it allows via a Sigaba simulator to reproduce the cryptogram.The advancement of the rotors is represented by a sequence of bits which serves as an access key to a Hash table in memory. The value associated with the Hash key contains a list of rotor configurations compatible with the advancement identified by the Hash key. Phase 2In the second phase, each configuration of the control rotors and index rotors is tested. It is checked whether it produces an advancement sequence stored in the Hash table. If so, the program tries to decrypt the rest of the cryptogram and checks (via the coincidence index) whether the decryption corresponds to a plausible plaintext.Lasry – 2021PresentationThis is a known plaintext attack (100-letter Crib) with a high probability of success (90%). On the other hand, this attack can be performed on a regular computer in about a day (24 hours).Discovery of a statistical bias of SigabaThe great innovation of the Sigaba compared to the cipher machines of the time is the apparently random advancement of the cipher rotors. This advancement is controlled by the Stepping Maze. A priori, one might think that the stepping Maze, made up of the control rotors and the index rotors, generates random sequences. In fact, this is not the case. In addition, the gap between randomness and the operation of the stepping Maze is more marked for the CSP-2900. One could have imagined the opposite.Concretely, certain advancement configurations (for example 00111: the last three rotors advance, the first two remain static) are very frequent. On the other hand, the advancement of each rotor taken individually is more or less frequent. Lasry's article describes this phenomenon in detail. Reproduce this bias using my SimulatorMy Sigaba simulator makes it easy to see this statistical bias. Indeed, in the log produced by my software, we have (for each cipher letter) the advancement of the rotors. These lines contains the string "Advance cipher rotors:". It is enough to extract these lines to then produce statistics (via Excel, Unix tools, etc.). Below, we indicate the number of advances of each cipher rotor for 1000 ciphered letters (this number can easily be changed) on the CSP-889: thus, the second rotor advances in 50.3% of cases (which is normal). On the other hand, rotors 4 and 5 advance in about 73% of cases, which is excessive. In the case of a CSP-2900, the second rotor advances almost systematically (in more than 80% of cases). On the other hand, advancements 00011, 001111, 01011 and 10011 are very very frequent: each corresponding to about 10% of cases [these values are consistent with the data provided by Lasry].
$ python3 -c 'print("A"*1000)' | python3 sigaba_tui.py -c -D LOG |grep 'Advance cipher' |
sed 's/.*Advance.*: \[//' | sed 's/\]//' | awk -F, '{for (i=1;i<6;i++) {
if( $i == 1 ){ tb[i] ++}}}END{print tb[1],tb[2],tb[3],tb[4],tb[5]}'
540 503 508 738 729
$ python3 -c 'print("A"*1000)' | python3 sigaba_tui.py -c -D LOG -m CSP-2900 |
grep 'Advance cipher' | sed 's/.*Advance.*: \[//' | sed 's/\]//' | awk -F,
'{for (i=1;i<6;i++) { if( $i == 1 ){ tb[i] ++}}}END{print tb[1],tb[2],tb[3],tb[4],tb[5]}'
726 808 686 769 659
$ python3 -c 'print("A"*10000)' | python3 sigaba_tui.py -c -D LOG |grep 'Advance cipher' |
sed 's/.*Advance.*: \[//' | sed 's/\]//' | awk '{ dico[$0] ++}END{for (key in dico)
{print key, ":", dico[key]}}' |sort -k2 -t: -n |tail -4
...
0, 0, 0, 1, 1 : 605
0, 0, 1, 1, 1 : 988
0, 1, 0, 1, 1 : 1004
1, 0, 0, 1, 1 : 1029
A new attackThe attack is done in two phases (similar to those of the previous attacks):
Note: to speed up the calculations, Lasry uses several improvements and tricks that in short make his algorithm run in a reasonable time (1 day). References
Web Links
|