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 (Index of Coincidence) 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