| 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: |
| Alphadiego Challenge | |
|---|---|
| Tweet Topic Started: Feb 15 2006, 12:41 PM (940 Views) | |
| insecure | Feb 15 2006, 12:41 PM Post #1 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
I have recently (a few minutes ago as I write this) posted the source code for a second version of my "Diego" algorithm elsewhere on this forum. This second version works only in the domain of alphabetic characters. It ignores all non-alphabetic characters, and writes its output in five-letter groups. I asked my wife to imagine herself to be a British spy in WW2 Germany, and to compose a message for transmission back home. I did not allow myself to see this message. I then asked her to compose a key by typing gibberish on the keyboard. I did not allow myself to see the key, either. I am therefore in a position to take part in this challenge myself. Strictly speaking, I do have access to the plaintext and the key, but of course I'm not planning to peek. I can tell you that the keyfile is 39 bytes in length, and that this probably includes some non-alphabetic characters (which will be discarded) and at least one newline character. So we have an upper limit of 38 on the keylength. (By "key", here, I mean the sequence of characters which is used for initialising the key grid.) This is probably sufficiently long to make brute force an unattractive option, so we must resort to analysis. Here is the ciphertext:
So far so bad - but I do have one tiny little clue, a crib. Frankly, I think we're going to need it, so I'll write it here in clear: MOON Okay, folks, that's it - any ideas? |
![]() |
|
| Donald | Feb 15 2006, 02:21 PM Post #2 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
Yowza, a randomized key huh? Rational, yes, but so much for key side attacks.
Not much. Since we always shift the letter that was just encrypted, we know that if a(plain)=b(crypt) at position 1, a can NOT equal b at position 2. As a matter of fact, a can not equal be again for a MINIMUM of 9 letters (I quoted 8 earlier, I don't know what I was thinking, it's nine). It will usually be more than 9, but 9 is the absolute minimum. It's not much, but we may be able to use it at points. For example, with our teensy tinsy crib, MOON, we KNOW that the OO must encrypt to two different letters. So moon could NOT be LVVP, GQQF, FGGS, VNNW, XTTF, WAAU, FWWA, or RYYH. hmmm. Well, that didn't help much. If we had a LONGER crib we could use the information on non consecutive letters as well. For example, if we knew the phrase "red roses" appeared in the message, we would have the pattern 12*1*323. It could only go into the crypt text in places where the 1's, 2's and 3's didn't match each other. For another point of entry, I'm thinking those double letters in the encryption may be telling us something important. They can only happen when the plain text letters were consecutive left and right or down and up. We know the "base" square is alphabetical, so this limits the possible combinations. And since we KNOW that we start on an UP shift, we know whether it is left-right or up down.
Take LVVP, for example. The VV starts on an odd number, so we know that after the first V, we shifted UP. So since the second letter encrypted to V as well, it had to be directly above the first letter. VV could equal any of these: AV BW CX DY EZ FA GB HC ID KE KF MG NH OI PK QL RM SN TO UP VQ WR XS YT UZ But nothing else. in GQQF however, the QQ starts on an even number, so the second Q had to be to the RIGHT of the first, which gives us the possibilities: AB BC CD DE EA FG GH HI IK KF LM MN NO OP PQ QR RS ST TU UQ VW WX XY YZ ZV Obviously we can eliminate a LOT of these as highly improbable. Again, its not much to go on, but it's something. |
![]() |
|
| insecure | Feb 15 2006, 02:38 PM Post #3 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
Firstly, I disagree with you about A->B not repeating for a min of 9. I think it's a minimum of 5. Secondly: We can trivially set up trial key initialisers* and invoke Alphadiego in decrypting mode. Here is the output for the trial key initialisers* :
As you can see, it has some tantalising sequences: "VODAY" could be a coincidence, of course, but might not be. Is "PAMIC" significant? I don't know. * edited - was (incorrectly) "grids". |
![]() |
|
| insecure | Feb 15 2006, 03:02 PM Post #4 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
Sorry, folks, but I've inadvertently misled you. The traffic analysis I gave earlier was incorrect. I've just discovered this in conversation with my wife. I was trying to get a longer crib out of her, and she said "silvery". At this point, my suspicions were aroused, and I checked. The plaintext has nothing whatsoever to do with WW2 ! Apologies. I withdraw the challenge, and I'll set up another one in its place, although quite how to do this in such a way that I can take part, without trusting someone in my family to be able to compose a simple message on a given theme without lapsing into pseudolyrical nonsense, is beyond me at present. |
![]() |
|
| Donald | Feb 15 2006, 03:56 PM Post #5 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
Just grab a random verse from the Bible of a certain length. Pick the keyword to mix by from the dictionary, combine words till you get the length you want, but for this difficult of a challenge, I don't think it needs to be REAL long. then have your wife look at the text and pick a crib. (or have the program pick a random word or sequence of words from the text according to some parameters)
It CAN'T repeat in 5, because every other shift is UP. to get from A->B BACK to A->B we must have 5 right shifts, and there have to be 4 UP shift inbetween them. And another point. To restate the obvious, the key shifts, but the plain remains fixed. SO, not only do we know that it requires a minimum of 9 shifts to get the same key letter back over the same plain letter. we can put a min and max on how far a key letter can travel in so many letters of plain text. This tells us that our crib (MOON) can not have had ANY repeated letters in the crypt text. Too bad our crib wasn't NOON! Then we might have been able to lock it into a double sequance. For the new crib, what would be REALLY good would be a sequence that contained at least two combinations of consecutive letters (up or right) so that we could guarantee one of them would result in a double letter in the crypt. (there are more complicated patterns that would work as well) But hey, cribs can't always be ideal.
I think we may also be able to do something with shift trees: In our previous crypt text we have the sequance: WG SF GG SW G The S's are only 4 letters apart, And we KNOW that the crypt S was shifted UP after the first encryption. So you can create a "tree" of possible shift combinations. This tree assumes that the first crypt S was a plain A. asterisks represent that some row or collumn was shifted that our crypt letter was not in.
a-v-w-r-s (our shift tree) a-v-w-r-* a-v-w-*-x a-v-w-*-* a-v-*-q-r a-v-*-q-* a-v-*-*-w a-v-*-*-* So, IF our first crypt S=plain a, then the second crypt S can ONLY equal plain S, R, W, X, Q or V. Multiply that by the 25 posibilities for what the first S could be and we only have 150 possible combinations for these two S's. Thats still a lot, but its a lot less than 625. and the G SF GG SW G gives us an even more limited range. We have only three shifts from the first G to the second, that gives us a tree like: a-b-w-x a-b-w-* a-b-*-c a-b-*-* so if the first G=plain A then the second G has to equal plain X, W, C or B. Only 100 possible combinations over the entire alphabet. And then we know that the third G represents the plain text letter directly above the plain text letter represented by the second G. and then another 3 shift to the fourth G. The W's are 7 shifts apart which is going to make for a very large tree. Now seperatly, these may not tell us much. BUT, these numbers are certainly within the possibilites of a computer search. If we combine all of the posibilites for W, S and G we will have 8 letters out of a 9 letter sequance and we might be able to narrow the possibilites down to only one combination that works. Ok, again, it's not much, and I'm not certain how much we can do with it. |
![]() |
|
| insecure | Feb 15 2006, 05:35 PM Post #6 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
Either I'm not thinking straight, or you're not thinking straight. I think it's me. But, in thinking that it's me that isn't thinking straight, I might not be thinking straight. For the time being, though, I'll go with the flow. It's either that, or sit down and work out why I'm right (which I am very probably not). |
![]() |
|
| Donald | Feb 15 2006, 06:01 PM Post #7 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
Ha! It seems more likely that MY thinking is muddled. I'll detail the muddle: Note that we start with a shift right, and the shift rights are always in the SAME row as the letter we are tracking, and the shift ups are always in a different row. If these conditions don't hold, the cycle time is longer.
I see we have a NEW challenge now, cool! |
![]() |
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · Challenges · Next Topic » |





![]](http://z2.ifrm.com/static/1/pip_r.png)



12:25 AM Jul 11