Ciphertext-only attack on Pins, 2014, by Jean-François BOUCHAUDY (MySelf) ========================================================================= Introduction ------------ I think G. Sullivan's algorithm is very complex. That's why I wrote a program based on a very simple algorithm, but may be less efficient that Sullivan's one. Algorithm --------- 1. Generate initial random pins setting, decrypt and compute an inital score with the fitness function 2. Repeat the following steps. Exit from loop if the fitness function no longer improves the score for a predetermined number of loops (for example, 5000 steps) 2.1. Randomly toogle a Pin 2.2. Decrypt and Compute the fitness function 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 : I tried several fitness functions : - IC (Index of Coincidence) - UNI (Unigram) - BIG (Bigram) - TRI (Trigram) 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_PINSa.py -h # Online Help usage: -c crypto The cryptogram -M method The method (IC, UNI, BIG,TRI,...), default: IC -m file_method The file used with method -l letter The letter (shift, default: Z -L lugs The lugs (ex: 1:5:4:13:2:7) -O overlaps The overlaps (ex: 0:0:1...:1:1) -t tries Number of tries, default: 15 ========= 1) I try the Unigram fitness function $ python HC_PINSa.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 -t 5000 0 >>>MAX SCORE: 29950.0 == ENIAEQCPFNEDZEDKCZKMEZDNMCHVNOBDDSZSOTCSCNNBAHTSE N CLE: 111011100000001001101010011100110001110100101100011101011111101011000 10111001010010010100100110110101100110010010011001001011110011 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 5001 12.0703508854 1 >>>MAX SCORE: 31779.0 == HZFSZQLZNEZCZTQALPNUMCMZTLZTEGVAOPZVDREBSUNUZNUDM L CLE: 111001111011110100100010011100010010101000110000110101010000110000010 00011110010101001111010010100100001010111001101101010011100001 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 10002 23.203150034 4 >>>MAX SCORE: 32556.0 == AAZWMDZQOCMZQIDMRWZHNNVEIILZZSVZJWZPBTSBQEECLEZZO H CLE: 000011101100110111000000001010101010100010100001111000111110011010101 01010101110100110101110001101101100001100110011011111001010010 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 25005 57.3394870758 6 >>>MAX SCORE: 44196.0 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHEZKEYZW H CLE: 001011001100000110010010011011001010101000010010011011010011011010110 00111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 35007 79.6190919876 ========= 2) I try the IC (Index of Coincidence) fitness function $ python HC_PINSa.py -c MSGS/wiki2.cry -M IC -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 -t 5000 0 >>>MAX SCORE: 0.0497711857215 == WAATWFDGTBCCTNMBQMLDVZNXCGLCFRFCSNZTAZRGV LXVOFNCGM CLE: 1100010101010100011111000010010001111001100111000111110110110 0111101101001000001101010110001000000100100001111100001010111001111110 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 5001 11.569336175 9 2 >>>MAX SCORE: 0.0509789073057 == KWXBPIZPQLNPQPJLMWLPWNJZHSRVUPPMVZIHXWCNN JFLTDUTTV CLE: 0101011110010100010111111010000111001100111100101010100110111 0110100011110111011010010111010110111000111000000111010101011111100010 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 15003 33.91604900 36 9 >>>MAX SCORE: 0.0527611126706 == ERBHWPNUHEGEQAPJUPDOECHKEBHSIQELBSLVEZLZW AYEFLVJQH CLE: 1111011110111000111111101110110000011110000111110111101000001 0001010010010001011011100110110101100100110000010110011011001011010001 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 50010 109.4000370 5 32 >>>MAX SCORE: 0.0893452843368 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZ THEZKEYZWH CLE: 0010110011000001100100100110110010101010000100100110110100110 1101011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 165033 361.384520 054 ========= 3) I try the Bigram fitness function $ python HC_PINSa.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 -t 5000 0 >>>MAX SCORE: 3180.54816499 == AOPOLYOAGWZNRMYFZSLZAROZRWZTIOVAZHSLEFRTUTU NNOZJLZ CLE: 001101001110101111010010011010111000111010011100000001110110101 11001101100110111000100100010111100001000011001001111111101001010001 [4, 8, 1 , 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 5001 11.8078451157 3 >>>MAX SCORE: 4477.61651039 == TOZENCIPHERZAZMESSAGEZTHEZOPERATORZSETSZTHE ZKEYZWH CLE: 001011001100000110010010011011001010101000010010011011010011011 01011000111110001100101101100011101110100001010110011101111011010101 [4, 8, 1 , 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 20004 45.9871180058 ========= 4) I try the Trigram fitness function $ python HC_PINSa.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 -t 5000 ... 127 >>>MAX SCORE: 1463.94274937 == TZKNNOONGZWNZCDMCGTTLZNEDZVZFGVVHROZPFKSB SELDEXIFX CLE: 0010111001001001110111101110001011011100011101100001010100110 1101110001101001000100101101000101100011101111011110011100011100100101 [4, 8, 1, 3, 12, 2] [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] 640128 1461.49412 107 After half an hour, no success. Trigram is not a good fitness function in this situation.