|
Home Page The Red Home Page
|
IntroductionThe RED machine is very weak cryptologically. Once the Cryptanalyst knows its structure, it offers very little resistance. The page SIS's Cryptanalysis explains how the US military was able to reconstruct the machine using only cryptograms. Known-plaintext attackIf we have a plain text of a few dozen characters, it's easy to find the cryptogram key. First, we deduce the Sixes and Twenties. The principle is simple: a letter from the Sixes is encrypted by another letter belonging to the set of Sixes. The same is true for the Twenties: a letter from the Twenties is encrypted by a letter belonging to the set of Twenties. The Sixes are more easily deduced because the set is smaller. Next, it is easy to deduce the Plugs from the Sixes. We assume that the progression is regular (we ignore the possibility of removed PINS). This assumption is logical, because the progression is mostly regular. Thus, we can deduce the sequence of Sixes (which constitutes the plugboard of Sixes). As we deduce the letters of the Sixes, we find anomalies: we have to move forward one step further to maintain the consistency of the Sixes already found. We proceed by trial and error: We try to remove a PIN. If this doesn't yield good results, we remove another or move the position of the removed PIN. Ultimately, we obtain all the removed PINS. If we have found them all, we deduce the period and can present the plaintext/ciphertext pair in slices of length equal to the period. We can now decipher the rest of the cryptogram based on the letters we already know. Note: We haven't found the entire key. Therefore, we don't necessarily know the number of the removed PINS, nor the absolute position of the wheels' starting points, but we were able to decipher the message and find the Plugboard configuration. Then, if we have other messages using the same plugboard, we will have very little difficulty in deciphering it. The key associated with the indicator is knownIntroductionNot only the RED machine is insecure, but so are the procedures used by the Japanese. If we know all the keys associated with the 240 indicators used, all that's left is to find the Plugboard configuration. MethodIf we know the removed PINS, the mode (direct/reverse), and the starting position of the wheels, it is possible to divide the cryptogram into segments equal to the length of the breakwheel period (between 40 and 47). We can also divide the cryptogram into segments of 6 letters and 20 letters (specifying the gaps generated by the removed PINS). Each column is encrypted at a specific position on one of the two half-rotors. Then, positioning a Crib is not a problem (see below). If we don't have a Crib, we can always use the most common bigrams and trigrams (a very useful method in the case of the Japanese). Normally, with the methods just invoked, the Plugboard configuration is found quickly. Attack using cryptograms alone
Distribute the letters into Sixes and TwentiesAs we saw on our page dedicated to cryptanalysis performed by the SIS (link) , it is easy, using a simple frequency analysis, to distribute the letters between Sixes and Twenties for all the cryptograms belonging to the same 10-day period. Find the length of the period (number of PINs removed)The period of the RED machine is greater than 2000 characters. If we limit ourselves to the Sixes, the period is less than or equal to 47 x 6 = 282. More likely, it is between 240 and 280. The period imposed by the Breakwheel is between 36 and 47. We divide the cryptogram into all periods compatible with the possible values of the breakwheel. For each period, we calculate the number of coincidences between a Sixes letter and another Sixes letter distant by the length of the period. The coincidence index thus calculated is greater when the period value is correct. Here is an example with the first genuine cryptogram (see Genuine messages). There are six pins removed, so the breakwheel period is equal to 47-6=41. This is the value for which the IC is maximal (0.041). $ python3 red_period.py KAWONC < MSGS/4JAN1937a.cry Length of the cryptogram: 665 Breakwheel: 37, Period: 222, Coincidences: 7, IC: 0.011 Breakwheel: 38, Period: 228, Coincidences: 13, IC: 0.020 Breakwheel: 39, Period: 234, Coincidences: 13, IC: 0.020 Breakwheel: 40, Period: 240, Coincidences: 8, IC: 0.012 Breakwheel: 41, Period: 246, Coincidences: 27, IC: 0.041 Breakwheel: 42, Period: 252, Coincidences: 17, IC: 0.026 Breakwheel: 43, Period: 258, Coincidences: 14, IC: 0.021 Breakwheel: 44, Period: 264, Coincidences: 10, IC: 0.015 Breakwheel: 45, Period: 270, Coincidences: 9, IC: 0.014 Breakwheel: 46, Period: 276, Coincidences: 15, IC: 0.023 Breakwheel: 47, Period: 282, Coincidences: 23, IC: 0.035 Note: This method is described in the draft "Solution of the RED machine" (see References). Using Cribs to Reconstruct PlugboardsIf we know the Sixes/Twenties separation, we can place a Crib. For example, if the Sixes is composed of the letters OZAJNB, the BELLEROPHON Crib can be written as a list of letters belonging alternately to the Sixes (S) and Twenties (T) letters: STTTTTSTTSS. If pins have been removed, it doesn't matter! Example:
$ more MSGS/konheim.txt
The issue of performance evaluation and prediction has concerned users
throughout the history of computer evolution In fact as in any other
technological development the issue is most acute when the technology is
young the persistent pursuit of products with improved cost performance
characteristics then constantly leads to untried uncertain features from
the initial conception of a system architectural design to its daily
operation after installation in the early planning phase of a new computer
system product the manufacturer
$ python3 red_tui.py -I konheim -P 00110111011 -W 10,3,10 -c -V \
> -G KAQWDEBOUHVMJYXFTGPLISZNRC < MSGS/konheim.txt | python groupe.py \
> MSGS/konheim_main_options.cry
TJWTB CFDNX REJVG HGKJB QARKM XQOHS LWGDL UWKLC XXBRC EIFIP
JWUYK WIUQS CVBGN MMIPB ILFDY PUYUI XCTGI SSBID OQOMX GMYCN
VSYQY ZEXZY KVPHJ UEPUQ TZLLN GBIBW FDEZW VRCNW PZSGD SMVIE
TBHCZ ODFHN EWGQY GYDXQ IBNNO SVOCF NXZMS XVEVW PZVIC WGSLR
OMSPX HIVLC WJTNT WNLFI XXNUZ EQPNI CNDMH TUTEV RKZUD PQGBD
YBTSN HVFMD OSBRZ OWLNN CSQQD VFVPO MLMQE VLYWV IASJR QQYGP
ASXXI SZPES JLFGE YSBRP DCCOL TTOQM IHXQV ALLCV BKJSC UKPAQ
UTGCH RVBLA WCZRF GQCKY FOCAT OWXOP TSDIL EXTUB YRURA EEMZR
PLEMV GUPVO WSESJ WGKDH XFFIX DSCJS BQZZM GAROT FMQVA CXTWT
CHJWH
$ python3 scan_crib_vc.py
SYNTAXE: scan_crib_vc.py crypto crib [SIXES]
SIXES are equal to vowels by default
$ python3 scan_crib_vc.py MSGS/konheim_main_options.cry ARCHITECTURAL KAQWDE
> ARCHITECTURAL < V.....V....V. >>SIXES: KAQWDE
335: ALLCVBKJSCUKP
425: DSCJSBQZZMGAR
Note: The plaintext does indeed contain the word ARCHITECTURAL at position 335. Position 425 is a false positive. The methods described by KonheimIn 2007, Konheim (see References) described some RED attack methods.
Modern Attack Using the Hill Climbing MethodNowadays, we can attack a Red message without needing Cribs. Simply use the Hill Climbing method. First case: We only ignore the Plugboard configurationThere are only 240 indicators that give us all the accepted keys except the Plugboard configuration. The Hill Climbing method is easy to implement and converges very quickly regardless of the fitness method used (IC, bigram, trigram, etc.). Second Case: We Ignore EverythingIn fact, the number of PINS configurations is small: 2048 (2^11). Of course, the starting position of the Breakwheel must be taken into account. In total, this requires fewer than 100,000 tests. It must also be taken into account that the encryption method (encryption/decryption) and the direction of wheel rotation (forward/reverse) are unknown. In total, 400,000 tests must be performed. For each test, the Plugboard configuration can be found using the Hill Climbing method mentioned above. If we assume that each test using Hill Climbing takes 1 second, the solution can be found in less than 5 days. Notes:
NoteI have just presented an approach here that is not at all subtle. I advise those who wish to tackle my 6th problem in my RED challenge to be more imaginative! For example, we can consider that the Sixes/Twenties separation is easy to find. A Hill Climbing approach can then be based solely on decrypting the Sixes. Furthermore, to reduce the number of PINs positions to explore by calculating the period, we can reduce the number of tests to perform from 2,000 to only 400 (or even fewer). Finally, we can also use the Friedman interval method as long as we know the Sixes/Twenties distribution... ReferencesBooks and Articles
Internet
|