Ciphertext-only attack on Pins, 2002, by Geoff Sullivan
=======================================================

Introduction
------------
In a Cryptologia article, Geoff Sullivan published a method to attack 
ciphertext ciphered with Hagelin machine like CD-57 or M-209. He decided 
to limit his investigation to messages of realistic size, no more than 
500 characters long. His method was based on Hill Climbing algorithm. His 
program search only Pins settings. The Lugs settings is supposed known.


Algorithm
---------

1. Ranomly set 40% of the pins in ARRAY to the active state.

2. Decrypt the message, using ARRAY and obtain a score (with a fitness 
   function) for this pin pattern. 

3. Save a copy of ARRAY in SAVE.

4. Swap and score all pin pairs in ARRAY. Retain only the pair swaps that 
   increase the score. Record any higher score in a log file.

5. If the score for ARRAY is less than the score for SAVE then copy SAVE 
   to ARRAY. Otherwise copy ARRAY to SAVE.

6. Introduce some small random variation in ARRAY, keeping the number of 
   active pins constant. The amount of variation may be decreased as the 
   score increases.

7. Loop back to step 4 for typically 125 loops.

8. Apply a fresh random restart to ARRAY, increasing the number of pins 
   randomly set to the active state by one.

9. Loop back to step 2 while the number of active pins in ARRAY is less
   than 60 %.

10. Examine the log file for successful entries.

Several fitness functions were considered : Index of Coincidence, Unigram 
counting, bigram or trigram system. Bigrams proved to be the better detector.

Conclusion
----------
With an M-209 cipher of message length 500 characters, a success of 100%
is achieved. With a message length of 250 characters the success rate is
reduced to 60%. For the CD-57 cipher Hill Climbing wtih a message length
characters a success rate of 57% is achieved.

References
----------
"Cryptanalysis of Hagelin machine Pin Wheels", by Geoff Sullivan (2002), 
Cryptologia, 26:4, 257-273.