| Welcome to Crypto. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
| Brute Forcing The Adfgvx Cipher | |
|---|---|
| Topic Started: Apr 19 2008, 08:06 AM (2,741 Views) | |
| osric | Mar 17 2009, 04:29 PM Post #31 |
|
Advanced Member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
I chanced on this discussion thread and decided to try solving ADFGVX with my Churn algorithm, developed from Simulated Annealing specifically to break classical ciphers (Bifid, Playfair, Digrafid and the other such ciphers of the American Cryptogram Association) without using a crib. I decided to start with the simpler ADFGX cipher, using a 5x5 square of 25 letters and a transposition key of 5 columns. A 120-letter plaintext enciphered this way solves in a few seconds without using a crib. I'm now modifying the program to solve ADFGVX using a 6x6 square of 26 letters integers 0 to 9, again with a transposition key 5 columns wide. I am not clear what the best performance achieved by the group is, in terms of message brevity, size of square, width of transposition key, length of crib used (if any) and solving time. Could someone please update me on this? I am of course happy to share any aspect of the Churn approach if it's of interest. Edited by osric, Mar 17 2009, 05:01 PM.
|
 |
 
|
| osric | Mar 18 2009, 08:55 PM Post #32 |
|
Advanced Member
|
I have now developed a program to solve an ADFGVX-enciphered 120-letter plaintext with a transposition key of 5 columns & a substitution key of 36 characters made up of mixed letters of the alphabet and integers 0 to 9. Following ACA practice 1 follows A, 2 follows B....and 0 follows J. No crib was used. In the first stage the program finds the transposition key. This is done either by brute force, hillcimbing and scoring with log tetragraphs each key; or alternatively by hillclimbing both keys. This takes 20 seconds for the 120 perms of a 5-transposition and in that time the hillclimbing route also settles on the correct key. In neither case is the solution found, just the correct transposition key. Then in the second stage, using the correct transposition key, the substitution key is churned to give the solution. This takes 10 seconds or so. I tried the same approach with a cipheretxt resulting from a 6x6 square and an 8-wide transposition key, as below: GXDDXGVGXXADAGXAAADAAAGDXDXADDXAFFFAFAAXXADDFFVDFFFADDFDGVDDXADAFXDFVDAAFXFAADF DAFADAADAVFXFDDAGXGGDXAAVXXXXDDVAGDGXGDAGVGXDGDADDDGGDDDDGGAXXAADDGGAGXXGXDX GFDDGAAADFVAGDVAFXFXXAGFXFDADAFGXXGDADAGDXADVXGDDGXDGGGDXAGXAFDADAFGDAGGFAADD AAAGAFDADDDAVF. In the first attempt to find the transposition key, again not using a crib (which took 2 hours to consider the 8! perms involved) the program came up with the wrong key but a number of recognisable words in the plaintext. Actually this incorrect transposition key has the digrams reversed. Common letters in the recognisable words quickly lead to finding the correct transposition key. In a second run the correct transposition key was found and again in a third run. Recovering the plaintext using the transposition key is a matter of 10 seconds for my Churn algorithm. I am going to look for a faster algorithm than brute force to find the transposition key. Does anyone have access to actual ADFGVK keys used by the German Army in the 1st World War? Edited by osric, Mar 19 2009, 01:13 PM.
|
|
|
|
| jdege | Mar 20 2009, 04:28 AM Post #33 |
Elite member
|
How are you scoring the transposition key? |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
| osric | Mar 20 2009, 07:41 AM Post #34 |
|
Advanced Member
|
jdege, As described above, with log tetragraphs. I am not clear what the best performance achieved by the group is, in terms of message brevity, size of square, width of transposition key, length of crib used (if any) and solving time. Could you update me on this? |
|
|
|
| jdege | Mar 20 2009, 01:40 PM Post #35 |
|
Elite member
|
I'm not sure that anyone other than Revelation has actually tried this. It's on my list, but there's a lot in front of it. As for your "log tetragraphs", I understand, and have used, log tratragraphs in hillclimbers. But that was in single-stage encryptions. Where I could compare the tetragraph statistics of the provisional plaintext to the statistics of ordinary text. And that's not the case, here. If you correctly reverse the transposition, you are left with a ciphertext - enciphered with a simple substitution. These aren't hard to break, but first you have to recognize that you have correctly reversed the transposition. You can't do that by comparing the contact statistics of the ciphertext with ordinary text. Not directly., because of the remaining substitution Or at least, I'd not expect it to work. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| osric | Mar 20 2009, 03:35 PM Post #36 |
|
Advanced Member
|
jdege, I am afraid you have got completely the wrong impression from my description of what the algorithm is doing! The log tetragraphs are used for scoring plaintext, not the transposed ciphertext. For each perm of the transposition key, a transposed ciphertext is created. This is then hillclimbed, using 10 successive random substitution keys. The hillclimbing of each of these 10 substitution keys is prolonged for approx 15,000 key changes. Each plaintext produced is scored with log tetragraphs. The highest scoring plaintexts, transposition keys and substitution keys are displayed. Once all perms have been considered, the highest scoring is usually the correct transposition key. The plaintext is not good at this stage, though it's good enough for the log tetragraphs to have distinguished between the right transposition key and the rest. Having found the correct transposition key, my Churn program finds the correct substitution key and plaintext in 10 seconds or less. This stage, as you say, is easy. As a general comment, ic's and log digraphs are useless for solving ciphers based on short plaintexts of 100 letters or so -- as in this case. Here you need log tetragraphs. For long ciphers, like Simon Singh's Playfair challenge which had 540 letters of ciphertext, scoring with ic or log digraphs will provide a solution. It sounds from what you've said that an ADFGVX cipher would be a good challenge for this group. Let me know when you have read this and I shall delete it all prior to issuing a challenge on the main page. |
|
|
|
| jdege | Mar 20 2009, 04:57 PM Post #37 |
|
Elite member
|
Ah-ha. I'd been looking at this problem, trying to find a statistic that would come through the substitution cipher, and not finding any that would work on short texts. I'd considered doing a full hill-climb on the result of every trial transposition decrypt, but eliminated that as being far too expensive. I hadn't considered that doing a fast, limited hill-climb might provide good enough results to use as a scoring function. This is a new idea, to me. Is this your own insight? Or have you seen this technique used elsewhere? (As for the challenge, there were never more than a handful of active participants in this forum, and we've all pretty much gone silent for the last year or so. Throw it out, if you like. You may draw some of them out of the woodwork. Personally, I'm not going to be able to look at it until July or August.) |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| osric | Mar 20 2009, 08:22 PM Post #38 |
|
Advanced Member
|
Yes this is my insight, but I would be surprised if some of my ACA colleagues haven't had the same thought! I use this technique for other Transpositions when the occasion demands. An example is solving the Myszkowski cipher, which I find is best done with a genetic algorithm. An initial requirement is to find the period, and trying all reasonable periods with a limited Hillclimb works well. Equally it is useful for really difficult Columnar transpositions, of 20 columns or more but with the actual number unknown. Also the Amsco cipher of unknown period. I've improved the effectiveness of my ADFGVX transposition algorithm today and so far am getting a solution every run. But as we know 'one swallow doesn’t make a Summer' when dealing with stochastic algorithms. |
|
|
|
| osric | Mar 22 2009, 10:43 AM Post #39 |
|
Advanced Member
|
Further 'insights' have reduced solving time to less than a minute when an 8 column transposition key is used. |
|
|
|
| jdege | Mar 23 2009, 10:10 PM Post #40 |
|
Elite member
|
You're still brute-forcing the transposition key, right? Eight columns only gives you 40,320 permutations, so you wouldn't expect it to take very long, yet. How well does your method work when you're hillclimbing the transposition key, as well? |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| osric | Mar 24 2009, 07:32 AM Post #41 |
|
Advanced Member
|
jdege, I love these comments about how easy it is to solve a problem from those who haven't actually managed to do it themselves! I've posted a challenge cipher -- why not show us how easy it is? and I will be the first to applaud. With regard to hillclimbing both transposition key and substitution key, I found in practice that was a bad idea for the ADFGVX cipher. The fact that the transposition key is fractionated makes it ineffective. For the Nicodemus cipher (a combined Vigenere and Transposition) where the transposition key is not fractionated, it works fine. But maybe you will find a way through that I have missed -- so why not give it a go and tell us what you find? If you get stuck, come back and I'll brief you on a nice variation on this theme that forms a second stage of my solving process, though I Churn rather than Hillclimb. |
|
|
|
| jdege | Mar 24 2009, 12:27 PM Post #42 |
|
Elite member
|
I've posted the code for my cryptarithm breaker to this forum. It brute-forces all permutations of the 10 digits. Or the 9, the 11, 12, or occasionally 13 that you occasionally see in the Cm. So it's not like I've no experience in the execution times of exhaustive searches of permutations. My program brute-forces 10-digit cryptarithms in less than 15 seconds. 11-digit in 2-1/2 minutes, 12-digit in half-an-hour. The MA2009 Cm had a 13-digit. That took nearly seven hours. If your program will handle transposition periods of 8 in under a minute, your going to be able to handle periods of 9, 10, and 11, just by waiting longer, but a period of 12 will take more than a week, and a period of 13 will take close to four months. My understanding was that the Germans used 15 or greater. Your method would not have been able to break them, on ordinary computer hardware. For longer transposition periods, some sort of heuristic search of the transposition key space is necessary, since it can be far too large to brute-force. It sounds as if your attempts at hill-climbing didn't work. It seems to me that the next logical step is to figure out why, and to find a heuristic search that does work. As for my own efforts, as I said, my time in this area is allocated until July or August. I may give it a shot, then. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| osric | Mar 24 2009, 05:20 PM Post #43 |
|
Advanced Member
|
jdege, First let me make a few comments on your brute force cryptarithm programs, which I hope you will find helpful. In essence the times you quote are very slow. For a base-10 cryptarithm my brute program goes through all perms in 2 seconds, and for a base-12 cryptarithm in four and a half minutes (on my old 2.3GHz PC). I suspect that either you are not using the fastest algorithm for generating perms, or your method of handling numbers is not optimum (or your computer is very old! which I doubt). As an example this base-12 solved in 99 seconds with my brute force program: SIGHT+SOUND+SCENT=TTHESN; TASTE+TOUCH=EIIOD. As a second comment, hillclimbing is much faster and thus much better for the higher bases. For example the base-12 addition above solves in less than one second. For this reason I don’t use brute force any more. Fastest of all, and useful for really high bases, is a method called intelligent brute force which I have written about in the Cm. If you would like to see any of my programs (written in C++) I’d be happy to send them to you. Turning now to ADFGVX, I am afraid I am not finding your inputs helpful to develop or improve my algorithm. It’s been self-evident since the beginning of this thread that ANY algorithm based on brute force will take too long to solve ADFGVX with a transposition key of 15 to 20. Even brute forcing a base-20 cryptarithm (a trivial task compared with solving ADFGVX) would take thousands of years! Your comment 'find a heuristic search that does work' is of no more help than ‘find a way of making gold out of lead’! When you have the time to devote to this topic, and can suggest something of practical use, I assure you I shall be all ears. |
|
|
|
| jdege | Mar 25 2009, 01:34 PM Post #44 |
|
Elite member
|
First, are you Anchises? Hello, I am Peristalsis.
I'm running on a 1.2GHz AMD Sempron. I'm a computer programmer - I have no interest at all in chasing the latest computer hardware. And as for my cryptarithm program, it was something I threw together in a hurry because I have absolutely no interest in cryptarithms. I'm sure that there are faster ways of doing things.
I would be interested.
And I'm afraid you're not going to find much help from anyone in this forum. There are only three or four of us who seem to have written hill-climbers, and perhaps only one of us who's ever tried to apply them to ADFGVX, and he seems to have had far less success than you have had.
Actually, I was thinking of Jim Gillogly's publication of his ciphertext only solution for Enigma. His solver would work reliably on most messages over, IIRC, 420 characters. And since he'd found several messages of over 420 characters within the archives of historical Enigma messages, he concluded that it would have worked at least part of the time on the original traffic. Someone else pointed out that those longer messages were in fact concatenations of multi-part messages, and that no individual part ever exceeded 200 characters, at which length Gillogly's attack never worked at all. You've developed an attack that works on a sophisticated WWI cipher, had they used keys that were half the length of the keys they actually used. I don't mean that to belittle your work, just as I don't mean to belittle Gillogly's work. I'm just fascinated that these guys - who could never have foreseen the types of attacks you've developed, nevertheless had enough foresight to choose message and key lengths that would have forestalled them.
What was it Reagan used to say? "They say there aren't any simple answers. They're wrong. There are simple answers, there just aren't any easy answers."
If I were to address this problem, I'd be doing exactly what you have been doing. 1st. make sure that the attack on the substitution phase worked. 2nd, make sure that the scoring routine worked - by testing with exhaustive search of small transposition keys 3rd, try to work out where it is, or why it is, that a heuristic search of the transposition key space goes wrong. In that, I can think of two possibilities. 1, the scoring routine doesn't give the highest score to the right anwser. Or 2, the adjacency search doesn't include keys that really should be considered neighbors. (I'm thinking of the way that Playfair breakers often work better when you include flipped key squares, instead of just swapped letters, as neighboring keys). I'd think you'd be already be certain that your scoring routine was successfully assigning the highest score to the proper transposition. When you were trying to hill-climb the transpositions, what were you considering as neighboring keys? |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| dabombguyman | May 25 2009, 08:56 PM Post #45 |
Just registered
|
If you think about it, the 3 step ADFGVX (with 3 keys, one for each step) could turn just about any plaintext into almost any cipher text, meaning that it's possible that two different plaintexts (of the same length) could end with the same cipher text, this would make it unbreakable without the keys. Unless someone can prove that you can't turn two different P-texts into the same cipher text. |
| Q3J5cHRvZ3JhcGh5IGlzIGFuIGFydCBmb3Jt | |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · General · Next Topic » |
10:52 AM Nov 23
