TDD-Deciphered.com

Part 12: Spare Parts

13/02/2010

In the last installment, we managed to decode a genuine wartime message, but to do so we had to draw in new wheels and a reflector which we didn't then take the time to test. We'll do that housekeeping now, and include the code for the remaining wheels and reflectors.

However, let's first look at the reason those wheels existed. Time for some maths, some history, and a little light cryptography.

One of the key principles of secure cryptography is that its security should not rely on the details of the system being unknown; this is known as "security through obscurity" and is generally known for working until it suddenly doesn't. Instead, the security of the system relied on the immense number of possible "keys" (rotor and plugboard settings) that could be applied.

The original 3-rotor steckerless commercial machine (the Enigma C was the first "portable" device working with a lamp output) built up its key combinations from:

- The order of the three available rotors (6 options)
- The offsets of each of the three rotors (26x26x26 = 17576 options)
- The position of a single, twin-position reflector (2 options)

Note that the original positions of the rotors do not add to the number of options, as these are sent (in some form) as part of the preamble of the message.

This gives a total of 210912 "keys". In the modern age of brute-force computer attacks, this would be considered pitifully insecure - but, for a commercial cipher at a time when all attacks would have to be conducted by hand, was presumably considered very strong. (It's also possible that in 1924 such mechanical devices held something of a mystique, as prior to this time almost all coding and encipherment would have been by hand or using the very simplest of devices).

However, it presumably wasn't considered adequate for military security. The various forms of the Service Enigmas were considered to be "medium grade" cyphering systems, between hand codes (still widely used in the war, by all sides) and more secure systems including fully mechanised "high-speed" multi-rotor systems like the Lorenz Schlüsselzusatz and the Siemens Geheimschreiber. They were generally used to send tactical messages rather than either immediate 'line of fire' or strategic signals. As such, efforts were made to make the keys truly unbreakable.

By the time that German and Russian forces invaded Poland, all arms of the German military were using a three wheel steckered Enigma, either as the Enigma I "Service Enigma" used by the German Army and Air Force (with numeric indicators on the rotors) or the M3 used by the German Navy (with alphabetic indicators). These were supplied with five rotors, I to V, which we've already seen and tested.

The number of possible keys for this system are made up from:

- The choice of three rotors from five (10 options)
- The order of the three chosen rotors (6 options, as above)
- The offsets of each of the three rotors (26x26x26 = 17576 options)
- One fixed-position reflector (1 option; while there were 3 types of rotors used at various times, they do not seem to have been used at the same times)
- The choice of 10 pairs of steckers from 26 sockets (150,738,274,937,250 options according to the NSA's maths)

This produces something in the order of 158 million, million, million possible keys, a number it is simply impossible to brute-force by hand. For this reason, the Germans did not believe at any time duing the war, or for decades afterwards, that the Enigma had been broken. So why increase the complexity? Probably on a purely precautionary basis. Note also that most of the complexity comes from the steckers, but because these don't rotate (or change) during the message, they are not as resilient to cryptographic attack as having more rotor combinations.

You may be wondering how, with that number of combinations to take, the Enigmas were ever broken. That's a very long story though, best answered by visiting Bletchley Park yourself, or doing some further reading

And yet there was an even more complex turnover rotor Enigma, used uniquely by the U-boat service. This had four rotors; three of them chosen from an increased pool of 8 standard rotors, and one chosen from two special thin rotors (known as Beta and Gamma) that fit in the fourth slot, alongside a thin reflector.

This increases the maths to (I think):

- The choice of three rotors from eight (56 options)
- The choice of one rotor from two (2 options)
- The order of the three chosen standard rotors (6 options)
- The offsets of each of the three rotors (26x26x26x26 = 456976 options)
- One fixed-position thin reflector (1 option assuming the two weren't used at the same time)
- The choice of 10 pairs of steckers from 26 sockets (150,738,274,937,250 options according to the NSA's maths)

which comes out to 46 thousand, million, million, million keys - before even considering the re-wirable Reflector D used briefly towards the end of the war.

So, here are the remaining wheels and reflectors ("dunn" indicates a thin reflector) used in the M3, M4 and I machines that added to that complexity:
  1. final class Enigma_Rotor_VI extends Enigma_Rotor_Abstract
  2. {
  3. protected $_coreMapping=array(
  4. 'A'=>'J','B'=>'P','C'=>'G','D'=>'V','E'=>'O','F'=>'U','G'=>'M','H'=>'F','I'=>'Y',
  5. 'J'=>'Q','K'=>'B','L'=>'E','M'=>'N','N'=>'H','O'=>'Z','P'=>'R','Q'=>'D','R'=>'K',
  6. 'S'=>'A','T'=>'S','U'=>'X','V'=>'L','W'=>'I','X'=>'C','Y'=>'T','Z'=>'W'
  7. );
  8.  
  9. protected $_pegPositions = array('A','N');
  10. }
  11.  
  12. final class Enigma_Rotor_VII extends Enigma_Rotor_Abstract
  13. {
  14. protected $_coreMapping=array(
  15. 'A'=>'N','B'=>'Z','C'=>'J','D'=>'H','E'=>'G','F'=>'R','G'=>'C','H'=>'X','I'=>'M',
  16. 'J'=>'Y','K'=>'S','L'=>'W','M'=>'B','N'=>'O','O'=>'U','P'=>'F','Q'=>'A','R'=>'I',
  17. 'S'=>'V','T'=>'L','U'=>'P','V'=>'E','W'=>'K','X'=>'Q','Y'=>'D','Z'=>'T'
  18. );
  19.  
  20. protected $_pegPositions = array('A','N');
  21. }
  22.  
  23. final class Enigma_Rotor_VIII extends Enigma_Rotor_Abstract
  24. {
  25. protected $_coreMapping=array(
  26. 'A'=>'F','B'=>'K','C'=>'Q','D'=>'H','E'=>'T','F'=>'L','G'=>'X','H'=>'O','I'=>'C',
  27. 'J'=>'B','K'=>'J','L'=>'S','M'=>'P','N'=>'D','O'=>'Z','P'=>'R','Q'=>'A','R'=>'M',
  28. 'S'=>'E','T'=>'W','U'=>'N','V'=>'I','W'=>'U','X'=>'Y','Y'=>'G','Z'=>'V'
  29. );
  30.  
  31. protected $_pegPositions = array('A','N');
  32. }
  33.  
  34. final class Enigma_Rotor_Beta extends Enigma_Rotor_Abstract
  35. {
  36. protected $_coreMapping=array(
  37. 'A'=>'L','B'=>'E','C'=>'Y','D'=>'J','E'=>'V','F'=>'C','G'=>'N','H'=>'I','I'=>'X',
  38. 'J'=>'W','K'=>'P','L'=>'B','M'=>'Q','N'=>'M','O'=>'D','P'=>'R','Q'=>'T','R'=>'A',
  39. 'S'=>'K','T'=>'Z','U'=>'G','V'=>'F','W'=>'U','X'=>'H','Y'=>'O','Z'=>'S'
  40. );
  41.  
  42. protected $_pegPositions = array();
  43. }
  44.  
  45. final class Enigma_Rotor_Gamma extends Enigma_Rotor_Abstract
  46. {
  47. protected $_coreMapping=array(
  48. 'A'=>'F','B'=>'S','C'=>'O','D'=>'K','E'=>'A','F'=>'N','G'=>'U','H'=>'E','I'=>'R',
  49. 'J'=>'H','K'=>'M','L'=>'B','M'=>'T','N'=>'I','O'=>'Y','P'=>'C','Q'=>'W','R'=>'L',
  50. 'S'=>'Q','T'=>'P','U'=>'Z','V'=>'X','W'=>'V','X'=>'G','Y'=>'J','Z'=>'D'
  51. );
  52.  
  53. protected $_pegPositions = array();
  54. }
  55.  
  56. class Enigma_Reflector_Bdunn extends Enigma_Reflector_Abstract
  57. {
  58. protected $_halfMapping=array('A'=>'E','B'=>'N','C'=>'K','D'=>'Q','F'=>'U','G'=>'Y',
  59. 'H'=>'W','I'=>'J','L'=>'O','M'=>'P','R'=>'X','S'=>'Z','T'=>'V');
  60. }
  61.  
  62. class Enigma_Reflector_Cdunn extends Enigma_Reflector_Abstract
  63. {
  64. protected $_halfMapping=array('A'=>'R','B'=>'D','C'=>'O','E'=>'J','F'=>'N','G'=>'T',
  65. 'H'=>'K','I'=>'V','L'=>'M','P'=>'W','Q'=>'Z','S'=>'X','U'=>'Y');
  66. }
As this is inherently fragile data, we can add it to our rotor and reflector integrity tests:

In Enigma/RotorTest.php, we rename and revise the dataprovider for testCoherentRotorIdentities
  1. /**
  2.   * Make sure each rotor's mapping is coherent
  3.   * @return null
  4.   * @dataProvider allRotorsDataProvider
  5.   */
  6. function testCoherentRotorIdentities(Enigma_Rotor_Abstract $rotor)
  7. {
  8. $mapping=$rotor->getCoreMapping();
  9. $this->assertTrue(is_array($mapping));
  10. $this->assertSame(26,count($mapping));
  11.  
  12. $inputsSeen=array();
  13. $outputsSeen=array();
  14.  
  15. foreach($mapping as $i=>$o) {
  16. $this->assertFalse(isset($inputsSeen[$i]),'Input seen before');
  17. $this->assertFalse(isset($outputsSeen[$o]),'Ouput seen before');
  18. $this->assertSame(1,preg_match('/^[A-Z]$/',$i),'Input "'.$i.'" must be upper-case letter');
  19. $this->assertSame(1,preg_match('/^[A-Z]$/',$o),'Output must be upper-case letter');
  20. $inputsSeen[$i]=true;
  21. $outputsSeen[$o]=true;
  22. }
  23.  
  24. $this->assertSame(26,count($inputsSeen));
  25. $this->assertSame(26,count($outputsSeen));
  26.  
  27. }
  28.  
  29. function allRotorsDataProvider()
  30. {
  31. return(array(
  32. array(new Enigma_Rotor_I),
  33. array(new Enigma_Rotor_II),
  34. array(new Enigma_Rotor_III),
  35. array(new Enigma_Rotor_IV),
  36. array(new Enigma_Rotor_V),
  37. array(new Enigma_Rotor_VI),
  38. array(new Enigma_Rotor_VII),
  39. array(new Enigma_Rotor_VIII),
  40. array(new Enigma_Rotor_Beta),
  41. array(new Enigma_Rotor_Gamma),
  42. ));
  43. }
If we add an accessor function to Enigma_Reflector_Abstract, we can use a very similar test on our reflectors
  1. public function getFullMapping()
  2. {
  3. return($this->_fullMapping);
  4. }
in Enigma_ReflectorTest.php
  1. /**
  2.   * Make sure each Reflector's mapping is coherent
  3.   * @return null
  4.   * @dataProvider allReflectorsDataProvider
  5.   */
  6. function testCoherentReflectorIdentities(Enigma_Reflector_Abstract $reflector)
  7. {
  8. $mapping=$reflector->getFullMapping();
  9. $this->assertTrue(is_array($mapping));
  10. $this->assertSame(26,count($mapping));
  11.  
  12. $inputsSeen=array();
  13. $outputsSeen=array();
  14.  
  15. foreach($mapping as $i=>$o) {
  16. $this->assertFalse(isset($inputsSeen[$i]),'Input seen before');
  17. $this->assertFalse(isset($outputsSeen[$o]),'Ouput seen before');
  18. $this->assertSame(1,preg_match('/^[A-Z]$/',$i),'Input "'.$i.'" must be upper-case letter');
  19. $this->assertSame(1,preg_match('/^[A-Z]$/',$o),'Output must be upper-case letter');
  20. $inputsSeen[$i]=true;
  21. $outputsSeen[$o]=true;
  22. }
  23.  
  24. $this->assertSame(26,count($inputsSeen));
  25. $this->assertSame(26,count($outputsSeen));
  26.  
  27. }
  28.  
  29. function allReflectorsDataProvider()
  30. {
  31. return(array(
  32. array(new Enigma_Reflector_B),
  33. array(new Enigma_Reflector_C),
  34. array(new Enigma_Reflector_Bdunn),
  35. array(new Enigma_Reflector_Cdunn),
  36. ));
  37. }
These tests all - fortunately - pass, so the reflectors and rotors are at least coherent. A good time for checkin 14!

As we have concrete (final) implementations of each of our rotors and reflectors, we may consider doing the same for the Enigma machines.
We currenly have
  1. <?php
  2. class Enigma_Machine implements Enigma_Encryptor_Interface
  3. {
  4. /**
  5.   * Number of slots this machine has. Default to original three
  6.   *
  7.   * @var int
  8.   */
  9. protected $_numSlots=3;
  10.  
  11. //[...]
  12.  
  13. /**
  14.   * Does this machine have a steckboard? Some don't
  15.   *
  16.   * @var boolean
  17.   */
  18. protected $_hasSteckerBoard=false;
  19.  
  20. //[...]
  21.  
  22. public function __construct($numSlots=3, $hasSteckerBoard=true)
  23. {
  24. //[...]
  25. }
As with our rotors and reflectors, we can relegate this class to abstract and create new:

Enigma_Machine_C
Enigma_Machine_I
Enigma_Machine_M4

by removing the parameters from the constructor and fixing the $_numSlots and $_hasSteckerBoard properties:
  1. <?php
  2. abstract class Enigma_Machine_Abstract implements Enigma_Encryptor_Interface
  3. {
  4. /**
  5.   * Number of slots this machine has. Default to original three
  6.   *
  7.   * @var int
  8.   */
  9. protected $_numSlots=null;
  10.  
  11. //[...]
  12.  
  13. /**
  14.   * Does this machine have a steckboard? Some don't
  15.   *
  16.   * @var boolean
  17.   */
  18. protected $_hasSteckerBoard=null;
  19.  
  20. //[...]
  21.  
  22. /**
  23.   * Constructor
  24.   *
  25.   * @param $numSlots integer Number of Rotor slots
  26.   * @param $hasSteckerBoard boolean Does this machine have a steckerboard
  27.   * @return null
  28.   */
  29. public function __construct()
  30. {
  31. if($this->_hasSteckerBoard)
  32. { // Can implement this later!
  33. $this->_steckerBoard=new Enigma_SteckerBoard;
  34. }
  35.  
  36. for($i=0; $i<$this->_numSlots; $i++) {
  37. $this->_slots[$i]=new Enigma_RotorSlot;
  38. if($i>0) { //higher slots watch lower ones
  39. $this->_slots[$i-1]->registerTurnoverObserver($this->_slots[$i]);
  40. }
  41. }
  42. }
and the machines, in their own files of course:
  1. final class Enigma_Machine_C extends Enigma_Machine_Abstract
  2. {
  3.  
  4. /**
  5.   * Number of slots this machine has. Default to original three
  6.   *
  7.   * @var int
  8.   */
  9. protected $_numSlots=3;
  10.  
  11. /**
  12.   * Does this machine have a steckboard? Some don't
  13.   *
  14.   * @var boolean
  15.   */
  16. protected $_hasSteckerBoard=false;
  17. }
  18.  
  19. final class Enigma_Machine_I extends Enigma_Machine_Abstract
  20. {
  21.  
  22. /**
  23.   * Number of slots this machine has. Default to original three
  24.   *
  25.   * @var int
  26.   */
  27. protected $_numSlots=3;
  28.  
  29. /**
  30.   * Does this machine have a steckboard? Some don't
  31.   *
  32.   * @var boolean
  33.   */
  34. protected $_hasSteckerBoard=true;
  35. }
  36.  
  37. final class Enigma_Machine_M4 extends Enigma_Machine_Abstract
  38. {
  39.  
  40. /**
  41.   * Number of slots this machine has. Default to original three
  42.   *
  43.   * @var int
  44.   */
  45. protected $_numSlots=4;
  46.  
  47. /**
  48.   * Does this machine have a steckboard? Some don't
  49.   *
  50.   * @var boolean
  51.   */
  52. protected $_hasSteckerBoard=true;
  53. }
While we don't yet have any unit tests for the Machine classes, we can check our changes with the cli scripts, renaming the machine in testRig.php to Enigma_Machine_C, and the one in m4TestRigWithDeviceAndSteckers.php to Enigma_Machine_M4. As the scripts run exactly as before, we can be fairly confident, and check in revision 15.

Having done some housekeeping on our code, in our next episode we'll look at creating the Enigma_Signaller class to make it more user-friendly.

All content copyright Richard George (richard@phase.org), 2009-2010

Sponsored links to recommended books: