M-209 : A New Ciphertext-Only Attack, by George Lasry
=====================================================
References
---------
- Ciphertext-only cryptanalysis of short Hagelin
M-209 ciphertexts, George Lasry et al., 2018, Cryptologia.

- A Methodology for the Cryptanalysis of Classical Ciphers 
with Search Metaheuristics ; Lasry, George ; 2018.
Download : https://kobra.uni-kassel.de/bitstreams
/14232b6a-d443-4cfd-b66f-fbc245b3a545/download

General Philosophy
--------------------
In his thesis, George Lasry developed a general strategy 
for attacking a cryptogram using Hill Climbing (or SA if needed):

- Do not use randomness to find a key neighboring an initial 
key (the initial key, however, is chosen randomly).

- Be as systematic as possible in searching for neighbors 
so as not to "forget" any possibilities.

The approach in the case of the M-209 Cryptogram attack
---------------------------------------------------------
- Use a procedure that generates Lug configurations.

For each Lug configuration, a procedure is called that searches 
for the Pins. The procedure generating the Lugs can check if 
the configuration complies with restrictions from the M-209 
user manuals. Furthermore, the procedure uses a classic Hill 
Climbing approach.

- The procedure generating the Pin configurations uses the SA 
approach. The SA approach is a specific form of HC, but it 
randomly accepts keys that are initially considered incorrect 
in the early stages and ultimately adheres to classical HC 
principles.

- The chosen fitness function involves summing the logarithm 
of the letter probabilities (monograms). In classical HC 
procedures, the IC (Intelligent Complexity) or bigrams are 
most commonly used.

Searching for Neighboring Lugs (Outer HC)
-----------------------------------------
- Canonical form of Lugs: We have a vector of 21 integers. 
The first 6 specify the lugs that are opposite a wheel and 
are alone on one of the 27 bars. The next 15 integers are 
associated with bars that support two lugs (this generates 
an overlap). Thus, the 7th integer contains the number of 
bars that have lugs opposite the first two wheels.

- Initially, we perform simple transformations: We increase 
the number of one type of bar and decrease the number of 
another type.

- When there are no more advances associated with the Lugs, 
we use more complex transformations: We increase the number 
of two types of bars and decrease the number of two other 
types.

Finding Neighboring Pins (Inner SA)
----------------------------------- 
The following transformations are used:

- The state of each pin on a single wheel is changed (from 
0 to 1 or from 1 to 0). This transformation is performed 
for all 6 wheels.

- The state of a pair of pins within the same wheel is 
changed. The pair must have different states (0 and 1 or 1 
and 0; if it is 11 or 00, nothing is done).

- The state of a pair of pins is changed, but one pin belongs 
to a wheel, and the other to an adjacent wheel.

- The state of all pins on a wheel is changed.

Note: Normally, the order of the transformations should 
change from one step to the next.

SA_inner() : Inner Simulated Annealing (the search for the Pins
----------------------------------------------------------------
- Input :
  . Lugs
  . Cryptogram (Abv : C)
- Output :
  . BestPins
- Algorithm :

Temperature := TemperatureZero
CollingFactor := 0.9
CurrentPins := BestPins := RandomPins()

for I=1 to 5 do
	for CandidatePins:= NeighborsPins(CurrentPins) do

		Score := Fitness(Decrypt(C, Lugs, CandidatePins) )
		Delta:= Score - Fitness(Decrypt(C, Lugs, CurrentPins))

		if (Delta > 0) or ((Random(0..1)< exp(-abs(Delta)/Temperature))
			CurrentPins := CandidatePins
			if Score > Fitness(Decrypt(C, Lugs, BestPins)) 
				BestPins:= CandidatePins
            break
	Temperature:= Temperature * CollingFactor
return BestPins


Hill Climbing outer (the search for the Lugs, call the Inner SA)
----------------------------------------------------------------
Note : This procedure is invoked multiples times (Shotgun) until
       a readable decryption is obtained.
- Input
  . Cryptogram (Abv : C)
- Output
  . BestLugs
  . BestPins

- Algorithm

BestLugs:= RandomLugs()

repeat
	Stuck:=true

	for CandidateLugs := NeighborsLugs(BestLugs) do
		CandidatePins := SA_inner(CandidateLugs, C)

		Score := Fitness(Decrypt(C, CandidateLugs, CandidatePins)
		
		if Score >  Fitness(Decrypt(C, BestLugs, BestPins) 
			BestLugs := CandidateLugs
			BestPins := CandidatePins
			Stuck := false
			break
until Stuk
return BestLugs, Bestpins

