Ciphertext-only attack on Pins, 2015, by George Lasry ===================================================== Introduction ------------ In 2014, George Lasry solved several problems of my M-209 Challenge. He used the Hill Climbing Algorithm. In 2015 he published in Cryptologia his algorithm using a fitness function ADE dedicated to solve known-plaintext problems. I wrote a program based on his algorithm. I used it to solve many problems, in particular, ciphertext-only attack on Pins ones. Algorithm --------- Here's my adaptation of George Lasry's algorithm (searching for Lugs has been removed): 1. Generate initial random pins setting, Decrypt and compute an inital score with the fitness function. 2. Repeat the following steps until the fitness function no longer improves. 2.1. Repeatedly perform the Toggle transformation as long as the fitness function gives a better score. Each Pin is considered in turn. 2.1.1. Toogle the state of one the pins of one of the wheels. This means that if the pin is currently effective, then set it to ineffective, and if it is currently infeffective, then set it to effective. 2.1.2. Decrypt and Compute the fitness function 2.1.3. If the score with the new pins setting is better, keep the new pins setting. Otherwise, discard the new pins setting. 2.2 Repatedly perform the Swap transformation as long as the fitness function gives a better score. Each pair of pins is considered in turn. 2.2.1. For a pair of pins, where the pins are not in the same state, toggle the state of both bins. For this transformation we consider any pair of pins, i.e. Either two pins in the same wheel or in different wheels. 2.2.2. Decrypt and Compute the fitness function 2.2.3. If the score with the new pins setting is better, keep the new pins setting. Otherwise, discard the new pins setting. 3. If the new score if better that better score, fix the better score to the new one and print this score, the key and the beginning of the plain text discovered. 4. Repeat from step 1, i.e. restart with new random pins setting. Stop if the predetermined number of loops is reached. Remark : The swap transformation is inspired by Sullivan's algorithm. If the message is long (about 500 characters), IC, UNI and BIG are good functions else if the message is short (about 200 characters), UNI is the best function. Examples -------- In the following examples, I tried to solve a ciphertext of about 500 characters (wiki2.cry). I know the Lugs (4:8:1:3:12:2) and the overlaps (2-4,4-6,5-6). I used statistics based on English texts with spaces replaced by "Z" letters (like the M-209 convention). My software finds Pins setting and Plain text. $ cat MSGS/wiki2.cry # The Cryptogram APQGD JBTIH IWNOK CNSDS DXGPK DSAGX TDMZL SKHCO UBVOA DBCZI KZHWB JZQCZ UTFIW GEHME JWVHX CZZBU JDMZE VXPKL IUJZA FFZGC GDAQG KGHDE CAXMP RYLOL TKTIM PEYQK GVUMJ XXKWO BLKEV PHHWE JRVKW AHTHW ZHBWN OJGMP EADMB ITTYZ DIUSS UWVFP DRXUS RSSJE JJYAQ AYLRB XHICN CDKER VAHQE AAYIC WPWCK KUJMX VARAJ VTZPT VLVTD YJEYW VTAKC WWXMD PWKHF OUARN ZGLFC DOPYS CADQL LCQQW KVAXI GZBIV XFTME ODBPA LITHH PIRQE RWULW HYNUI YAIVP ACOWT LDOLO ADBZM XUYOG GLKGB DHHQG LPELQ OLUYT XJFUX MSCXU CHXWI CXLVP NODAH FQLWD JHAUC FRLXC ODKIT OPCBW KWORV OKZNE IPBSV ETWFY XDFNK SSIKS IMIPK PXVFB FZWVH YNDGK XDJJV SDJWQ TPFRU DRIKQ OXCYX OFQHY OCHKL LRZWG KFAKA WKYHT VVVLG GDAIQ DOASL $ python HC_KPC.py -h usage: -c crypto The cryptogram -M method The method (BIG,TRI,...), default: ADE -m file_method The file used with method -l letter The letter (shift, default: Z -P pins The Pins -L lugs The lugs (ex: 1:5:4:13:2:7) -O overlaps The overlaps (ex: 0:0:1...:1:1) -S list Skip P(ins), L(ugs), O(verlaps) -t tries Number of tries, default: 15 ==========1) Fitness Function: IC (Index of Coincidence) $ python HC_KPA.py -c MSGS/wiki2.cry -M IC -m IC -L 4:8:1:3:12:2 -O 0:0:0:0:0:0:1:0:0:0:0:0:0:1:1 -S LO -t 5000 0 >>>MAX SCORE: 0.0468400127953 == PXEOQTPRZWZECZESNHDBZDHJENQNCNLLAWCXFVSUAUEPZXJELE CLE: 00100111001011101000010001001011101010110111100110001100111000111111011101110101010101100000000000010111101011101010010111011000010 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 1 >>>MAX SCORE: 0.0503521977269 == OKKLAFTKMIOSBELTZPMLOZOTGTXYZTVSDBKWTUZMBTTHTZZJOJ CLE: 00100101010011011110001010000111110011001110001011110000010101111111000001111111100110101011000101111110000111011001111111100111101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 2 >>>MAX SCORE: 0.0559468863632 == UNYXQFXQLTGXWOXFYHAFLHBDAWJTLYCLCCDOFINQLOZTWLPORP CLE: 10011010111110100100110110010001101100011010111101001011110100100010010011111001111101011100001111100000101000101011101110011001011 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 45 >>>MAX SCORE: 0.068317872321 == ENDIJGMLLINDDVQAOWERADALEDKLIVWXSNDVAXLVXDAFOAUDZL CLE: 11010011001110100110110110101100101010100001001001101001001101101011000111110001100101111100011101110100000010110011101110011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 51 >>>MAX SCORE: 0.0893452843368 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] ==========2) Fitness Function: Bigram $ python HC_KPA.py -c MSGS/wiki2.cry -M BIG -m m209 -L 4:8:1:3:12:2 -O 0:0:0:0:0:0:1:0:0:0:0:0:0:1:1 -S LO -t 5000 0 >>>MAX SCORE: 3216.01220062 == PRUEWBGNUIBANTENLOIUENTZFAQOENHAWEZHBTNAROUADAKBEN CLE: 00111110010001111001011010100111010010010011110001101111110101100101111101111010101101001101101000100001001000100010101001100110100 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 30744 51.5003969669 2 >>>MAX SCORE: 4477.61651039 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 53952 89.7419219017 ==2Bis) Fitness Function: Bigram. We know Pins Setting but we don't know Lug Setting !!! $ python HC_KPA.py -c MSGS/wiki2.cry -M BIG -m m209 -S P -P 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 -t 500000 0 >>>MAX SCORE: 2687.86942563 == ZNGAQXJZOJGXFZNEZUCCFATIKIWJIXGUPUBOHUPTYRDEGNVHUE CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [3, 1, 2, 4, 7, 10] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 1 >>>MAX SCORE: 2841.74466644 == ZOFIJXCZNJPOWTMNSMJVNZTHKZOKJXGTONTWJTHDPREVOONZLL CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 2, 1, 12, 7, 2] [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1] 2 >>>MAX SCORE: 2876.36254533 == TLETATIZMUOTVVRKOXOSOETMFEODPSAYTEEHLYIGORBUZKNZQL CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [1, 8, 6, 12, 3, 2] [0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 5] 4 >>>MAX SCORE: 2974.79353345 == YPDEOWIZLJLUAZMJYSEBJZTHIEUKJVFTOSZSJTNZTREZKOTERF CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [5, 3, 1, 7, 6, 7] [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2] 6 >>>MAX SCORE: 3017.94140886 == APGEOWIDOKEZIAMEAYHAMZTHENDJERHTWSFSFBMTBVYHKLYGWI CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [5, 1, 9, 2, 6, 9] [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 5] 14 >>>MAX SCORE: 3023.91488073 == YOELGRIEMPBZEZMEVDLVPZTHYNCEELFTZKKZEEHVXWTDRIYCWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 5, 12, 3, 1, 5] [0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 3] 16 >>>MAX SCORE: 3274.60048084 == TOZRCRIAHQGZAZMEREMVQZTHTKZEEGATAGLFEFHATSTZXDYYWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 9, 13, 3, 1, 1] [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 4] 30 >>>MAX SCORE: 3453.19058703 == AOGENCCWOERTATMLSMHALZTHLZOPEYHTORTSETMZTOEZKLSZQO CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 2, 1, 10, 12, 2] [0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 1, 4] 52 >>>MAX SCORE: 3852.15277328 == TOZENCIPHERYAZMDSRAGEZTHEZOPFRATPRYSFUSZTHFZKEXZVH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 2, 2, 12, 2] [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 3] 169 >>>MAX SCORE: 4477.61651039 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 3] ==========3) Fitness Function: Unigram $ python HC_KPA.py -c MSGS/wiki2.cry -M UNI -m m209 -L 4:8:1:3:12:2 -O 0:0:0:0:0:0:1:0:0:0:0:0:0:1:1 -S LO 0 >>>MAX SCORE: 44196.0 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 9499 21.1544539928 ==========4) Fitness Function: Trigram $ python HC_KPA.py -c MSGS/wiki2.cry -M TRI -m m209 -L 4:8:1:3:12:2 -O 0:0:0:0:0:0:1:0:0:0:0:0:0:1:1 -S LO -t 5000 0 >>>MAX SCORE: 1418.68509486 == AZGZSZUNECNQULIDCUBEIZWEZSTZUBSEASZSXHSTZOFTWETZNF CLE: 10111110000010011010001000111001101110011110111001111000011111101010111100100011010111111000000101001100001010101011010010110101101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 26207 61.7685990334 7 >>>MAX SCORE: 1494.98321924 == PYYXEQIKFDLQATLQZQKCDZTTLESPXPGWONIETESTTHPXKAZANS CLE: 00001000010010101001100000001100101010010100011001100100001100101001000011100001100001101111010101110111011010010011001101010110101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 125269 292.248418093 23 >>>MAX SCORE: 1527.13538191 == TRYPMDHNGENPOWMJMSZFLZPOLZORDZPHRQZSYVSVASOYLLZINA CLE: 00001000110000011001001000101110101111010001101001101011001100111101101101111001000001101010001101000100001011010010111111001101110 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 453810 1045.502702 28 >>>MAX SCORE: 1558.06118558 == ALEEPFWKHZNEXZREDUGXEZEJJTQTERYIVCPGZESTSFELMFZJWL CLE: 10101110110011010001010010111000110011101011001000101100001001111111000111011000100101100111011101100001001010111001101111010000110 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 518014 1193.41308999 41 >>>MAX SCORE: 3410.90166248 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 779606 1775.1785202 ===========5) Fitness Function: Quadrigram $ python HC_KPA.py -c MSGS/wiki2.cry -M QUA -m m209 -L 4:8:1:3:12:2 -O 0:0:0:0:0:0:1:0:0:0:0:0:0:1:1 -S LO -t 5000 0 >>>MAX SCORE: 284.123382276 == GRYNSEZGNOXGAGJFOHRUHXTETYZRISQAIZZLIONNVRAZKXUTEZ CLE: 01011010100110011010101001011000111111000000110111001001100010011101101001000001101001001100011110001100110011100101111110011101110 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 22161 43.8545498848 1 >>>MAX SCORE: 295.511361545 == PXWJHOQUNXGYIHDSAYEPQHSZPXOUXNCNMQCROCIHTULDZASHPQ CLE: 00010111010111110100111001111111001001111010110110111010100001111011001001100100000101100110001100111010100101011010110011011101101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 48104 94.1875090599 5 >>>MAX SCORE: 301.447043967 == ZHCQILNQHZNOZMURYZLAJXPWFGWMIZUFODDWMPWFZXGFEETIUS CLE: 01111010100000010101010010111001000011101101111100110111111001101101011011001010110110011100001101001010111111010011111010011110001 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 111349 216.199028969 8 >>>MAX SCORE: 317.820318669 == TXRUMPAZWTZSPIZAUSLFNHTVLEZIPRVDDEZWYWTGIUPHMQHSOD CLE: 10000001110100110011101010101101111001110011110001100110101101111001100011101010000000100110011010001000001101010111101111101100111 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 169668 329.313992023 12 >>>MAX SCORE: 317.960300256 == FRPOSZMUUHZACTEFURTSZRNXEMYGTNDLQMRLEFMOJYYWVJGWCL CLE: 01001000001001111100000001101001111011010001110000001000100101100100111100111001100110000000001010110100010001101110111001001111101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 249426 484.05787611 27 >>>MAX SCORE: 343.683799672 == TDKOWKYLWPOCZXPFQSXFNNMNGOODPSDTSOYSZLSLMQPIYCNJRH CLE: 10111001110101111000010000101100111010000001011001110000101101101011001111110001110100110000011011110100011101011011101100011100001 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 521216 1008.409307 86 >>>MAX SCORE: 344.363023135 == OAYPFQJNFPGDNOKWNIDPQSTZALLWTDZHORLDOACGQZTTHEZWOR CLE: 10001111111110110101001001100111100011111011001001111101111101101100101011110010011011111110110110100111100101000001001000000110100 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 1606323 3106.83952498 88 >>>MAX SCORE: 358.934612791 == DQZJMJSSVIGHBMONTUCOIWOZPOMGFSNDDQRKFECTERYZTLAXQC CLE: 01011101101001101001111000010110000101010000000100001111100011110011001001111000110001101101101011000100100011111001100100101111001 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 1666633 3222.99540901 109 >>>MAX SCORE: 2507.26218913 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0] NoD: 2118576 4095.88875103 ===========6) Message of 250 characters, Fitness Function: Unigram $ python HC_KPA.py -c MSGS/w2_250.cry -M UNI -m m209 -L 4:8:1:3:12:2 -O 0:0:0:0:0:0:1:0:0:0:0:0:0:1:1 -S LO -t 5000 0 >>>MAX SCORE: 17030.0 == ORDISABQZDWAZZEZNSZHEDPZTELHZNCMYNEKZUTTUNAPLENLEE CLE: 00100000111000101100000100101000101011000000110101011000010000100010000010111011001111111111101000110100001011100010111100101011000 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 18118 18.3801600933 1 >>>MAX SCORE: 17277.0 == ZMDIEDCPEGNSWZMNZRBTZZBZEINOISNZRTZHZHTZAFPZDZUHXZ CLE: 10101000000010010111001010111110100011101001000001101001100101100010010100011101100100101110110101000101001010010011100010111101101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 27847 28.7766549587 4 >>>MAX SCORE: 17422.0 == ZRDTWKCOERCTAAEFZUZAZDIZELLSTOTBSIZHBEVZZRAEEEUNFV CLE: 11111010101000111111001010111100100010001001110001101010001000100010000111011111100111111110110110000001001011110000011001110010001 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 119794 114.764223099 8 >>>MAX SCORE: 17626.0 == TZKEKDIOHCNCNRFOZCTXIZEZIZTZJYZTNTIEJSPTSHPIEMTHXK CLE: 11101000100011011101001000110000110111100111101001100101111101111010010010110101000101111100111101110111111010010011011011000101100 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 195135 185.4448421 15 >>>MAX SCORE: 20091.0 == TOZENCINHENZAZMEOSZUEZTHEZOQDRATORZSATSZTGAZEAYZWE CLE: 00101000010000011001001000101100100010100001001001101101001001101011000111110001100101101100001101110100001010110011111111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 316577 299.043450117 The Unigram Fitness Function gives a "almost" complete key. We are able to find the true key with the Quadrigram Fitness Function, but with the starting Pin settings found in the previous step: $ python HC_KPA.py -c MSGS/w2_250.cry -M QUA -m m209 \ -L 4:8:1:3:12:2 -O 0:0:0:0:0:0:1:0:0:0:0:0:0:1:1 -S LO -P 00101000010000011001001000101100100010100001001001101101001001101011000111110001100101101100001101110100001010110011111111011010101 -t 5000 0 >>>MAX SCORE: 1080.41771724 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZWH CLE: 00101100110000011001001001101100101010100001001001101101001101101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] NoD: 8844 11.649075985