Welcome Guest [Log In] [Register]
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:

Username:   Password:
Add Reply
Alphadiego - The Official Challenge
Topic Started: Feb 15 2006, 05:52 PM (1,067 Views)
insecure
NSA worthy
[ *  *  *  *  *  * ]
Let's try this again.

Code:
 

GNQUB RLNCB PCFGS PCPPT LVTRE BMPYS NCYXA QTPSE
LIEXR EASKU CVDBL PHLUB SRHOC RMFOC SOELQ DDDBU
GCDKI UBRLY UEUIE DOYVD BMAUO MQHQZ OBAQD QZCSI
NGKES UXWKD CWQLP HHSZS YPEDM COEAC NCGHE IWVMZ
BFGEV KFXAA OFFHX SDWGF LOSOX BLSWL MLKQE SCBPZ
TWRFQ UBFFR NBZAY GCZTS EPWRG MZNXE EDQGX NZYNK
XBFYL GYRH


Crib: COMMANDOS


Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
This is a bit short, any chance we could get something longer than this? Maybe twice the length?
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
"rot13"
 
This is a bit short, any chance we could get something longer than this? Maybe twice the length?

Gonna be a nightmare in ANY case. A seriously patterned crib could be a big help as well. BUT, the enemy never cooperates. :)

The DDD looks interesting, it has to be a sequence in the shape of a backwards L, like NOI or TUP. other promising sections:

FX AA OF FH X
LS WL ML
SP CP PT
QH QZ OB AQ DQ

Hmmm, I just realized something. We might have a Kaisiki-ish kind of attack possible on this. Repeat sequences that start on the same odd/even border will not (probably) repeat the same letters, but they WILL repeat the same patterns. for example, if we had two sequences like DG GD OD and LM ML RL, they would very likely be the same plain text. But that is NOT going to be easy to eyeball, but it may help us place our crib. I encrypted COMMANDO on an odd border and even border using an unkeyed alphabet, the resulting patterns were:

c=odd= colrardt = 12 34 54 67
c=even=comlembn = *1 23 45 36 7*

A quick eyeball (not very accurate) found these possible matches in our crypt text:

FG SP CP PT
OB AQ DQ ZC
GF LO SO XB
OE AC NC GH
*P SE LI EX R
*B FY LG YR H
Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
I'm afraid I can't persuade the Britisher spy to extend his message, but I have managed to trick him into sending another message using the same key. What is more, we had an agent in place at a very convenient moment, so we even know what the plaintext of this extra message is! Unfortunately, our interception facility missed the beginning of the encrypted message.

The full plaintext of the additional message is: "I will need some replacement valves for my radio set if I am to transmit many more messages, as the ones I have are on their way out."

Here is what we managed to intercept:

Code:
 

HOKQO GINRK GSUQH WUBAA IVRAR AXFKP BQIAH QWFQR
FZIME AZWKA CIGM


This corresponds to the last 54 characters of the message: "transmit many more messages, as the ones I have are on their way out" - I hope that this additional information will lead to an early crack.

Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
Okay, once I got my cribbing program working, it was just a matter of working through one letter at a time. I have cracked the message and this is it:


mr schultz could you please have four kilograms of sausages and six kilograms of mincemeat to my shop location of naval base is on an island near denmark it must be assimilated if operation hawk is to be successful main defence are westward facing fishing trawler should get commandos to safe zone out

The key was:

YHUWO
AZBTK
XGEFI
LPQRV
MNDSC



Now, before your eyes totally pop out of their sockets, let me say that although I cracked the message, I did NOT crack the Diego cipher. As I was trying to write some programs to analyze the data, I couldn't get my program to decrypt a message with a known key. After a little analysis, I realized that this was due to a bug in the alphadiego program. The bug is here:
Code:
 

     if(encmode == CIPHER)
    {
      row = chartoindex(inch) / UCHARMAXROOT;
      col = chartoindex(inch) % UCHARMAXROOT;
      outch = key[row][col];
      shiftchar = chartoindex(outch);
    }


and here:
Code:
 

           outch = indextochar(row * UCHARMAXROOT + col);
          found = 1;
          shiftchar = chartoindex(inch);


The bug is that the shiftchar is backwards. In the first instance, it should be chartoindex(inch) and in the second it should be chartoindex(outch). The result of this bug is that the amount of the shift is determined by the CIPHERTEXT instead of the plaintext. Since I know the ciphertext, I can compute all the shifts. So all I do is take an unknown CT letter and try it at all possible places in the key. It is easy to shift through every one. With a longer message I was able to figure out each letter using statistics, but with the shorter one, there weren't enough samples per letter so I had to use my brain.
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
Ha! Congratulations rot13! Cryptographers HATE those implementation bugs, and Cryptanalysts love them. :)

This one, since it was consistant, was difficult to detect! I'm not surprised it got past testing.
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
Yeah, I was in the middle of typing up a message about the bug and then I thought that since it made it so much easier to crack the text, I'd go ahead and crack it first. I figure that's the closest I'm going to come to cracking it. :) Once the bug is fixed, the cipher is WAY harder.
Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
Oops, as they say. Thanks for the debug. I've fixed up the code as suggested.

Now, what you say intrigues me. Here we have a very simple cipher - so simple it's basically pencil-and-paper - and yet you're saying it's really, really hard to crack. Now, I happen to agree with you - every time I try to find a way in, my attacks sort of slither off like it's covered in oil - but surely a pencil-and-paper cipher shouldn't be this hard? (Yeah yeah okay, OTP is pencil-and-paper, but you know what I mean.)

Here's a new challenge, worked up using the fixed program. I've supplied considerably more ciphertext this time.

Code:
 

YTGMT YLKDC YGPVE FLSMN GKYZV PHMHT KMEGI ZISBH
OBYCT CTGIC EKNGK PIHCZ NINEE ACBTW XOKZN NCQXT
SLIKI SSNZF KOVYV AQYZS MIHPP BBBWK WCRLB GISRU
UUUKC CTXKM MIOKO VWGEA UPPFZ EGVSB BAAES ELKKI
UHCTI SYYVR VODUD XBOWY BUDUS CTVHW CKQOZ LDOTG
LWVRR FUOOO OTDPW LXWOZ XHSAE KQQOI TWWKX GFQWY
NFICE WWXYZ ACDCH IDYEX VWFDH GWZWK APWVY PPCMF
FKMWO IVNMR TXXWX TXTEC HGXOD HHSFM HHELP BBBBI
NHRHC KOACL IFRZG EBYTG YMRCN HNIHK KKKVI TIDMT
CPNLT DMLZU LQREE NVROP BKONX HLECQ ASBXG OSGRM
OALMF MSGPK NOFLN RUCKX CXRIV TPQYD DDDEG IVIHT
OYYYP GVVNL XZAAI IGTQS VIZRU YAXKT MFYPZ EXBKG
ZCLUT ETHVE EWNVZ USCGF FZEGK CNFCK UGKBI DSLOI
UYTSG NHRNX IYXLQ VKVKR ENRUH UVSMK KGKRB GYALQ
OSWTS OXLWB I


I am intrigued by the occasional bursts of repeated letters - OOOO on one occasion, BBBB on another, DDDD on another. The run WWXYZ is curious, but probably irrelevant? But the repeated run - ah, hang on... that means we're chasing the ciphertext letter around the key grid. Which means it's one of a limited number of possibilities. It's either a HERE-UP-RIGHT-UP or a HERE-RIGHT-UP-RIGHT pattern, and we can tell which by careful counting, on the BASE grid.

There's an attack there, I think.

Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
HERE-RIGHT-UP-RIGHT patterns on the base grid:

ABWX
BCXY
CDYZ
DEZV
EAVW
FGBC
GHCD Not unimaginable ("a tough CD to give away")
HIDE English word
IKEA :rofl: Also, consider "like a rose"
KFAB Legal (e.g. "a mask fabricated from cotton")
LMGH Legal (e.g. "the calm ghost didn't go wooo")
MNHI Legal (e.g. "the autumn hit hard this year")
NOIK Legal (e.g. "no Ikea sale today!")
OPKF
PLFG
QRMN
RSNO
STOP English word
TUPL ("tuple", "quintuplet", "get up later")
UQLM
VWRS
WXST
XYTU
YZUQ
ZVQR

Of the two, "hide" and "stop" look particularly promising, but I've marked up some other legal combinations of letters. I don't claim to have spotted all the legal combos, though.

HERE-UP-RIGHT-UP patterns don't look quite so promising, but some are legal in English (for example, NHID appears in "seven hidden mines":

AVWR
BWXS
CXYT
DYZE
EZVQ
FABW
GBCX
HCDY
IDEZ
KEAV
LFGB
MGHC
NHID
OIKE
PKFA
QLMG
RMNH
SNOI
TOPK
UPLF
VQRM
WRSN
XSTO
YTUP
ZUQL

Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
insecure
Feb 16 2006, 08:21 AM
Now, what you say intrigues me. Here we have a very simple cipher - so simple it's basically pencil-and-paper - and yet you're saying it's really, really hard to crack. Now, I happen to agree with you - every time I try to find a way in, my attacks sort of slither off like it's covered in oil - but surely a pencil-and-paper cipher shouldn't be this hard? (Yeah yeah okay, OTP is pencil-and-paper, but you know what I mean.)

You could also do an Enigma cipher with pencil and paper, writing down the rotors and all. It is probably an amount of work similar to this one. Although Diego seems tough to crack, there are some aspects of it that make not such a good pencil&paper cipher. First, the patterns of the letters - the repeats and all - are detemined solely by the plaintext and not at all by the key. A given plaintext encrypted with two different keys has repeats in exactly the same areas. That's undesirable with any cipher.

Second, Diego is somewhat unforgiving if you get a single character wrong because you may end up shifting the wrong row or column. Most of the p&p ciphers can tolerate incorrect letters, even Enigma can. I think this aspect of it also leads to why it is hard to crack, so it is a trade-off.

I am also thinking that it should be pretty vulnerable to dictionary attacks. You can get common phrases and compute their repeat signature and see if there are any sequences that match that.
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
I agree that one weakness in this quite strong cipher is that pattern issue. You don't actually have to KNOW the key to crack this cipher. If the right patterns show up, you can rebuild a large portion of the keysquare as it was right in the middle of the encryption. Then work forward and backwards to recover the rest of the plain text.

Now I'm not saying that is EASY to do, not even close. But it is a vulnerability. Known plaintext seriously compromises diego.

On the new challenge, those quadruple repeats, NICE! I'm guessing STOP, there are just so many of them that a telegraph style message would be the best explanation. Although HIDE is not unreasonable.

Did you notice the word "HELP" right in the middle! :)

As for the careful counting, the first thing I've been doing with these ciphers is reformating them into pairs, then its very obvious where your up and right shifts are.
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
"Insecure"
 
Here we have a very simple cipher - so simple it's basically pencil-and-paper - and yet you're saying it's really, really hard to crack.

pencil and paper can be NASTY to crack. Even something so simple as a short playfair without a good crib can be very difficult, even for an expert. (although there is a program out there that makes quick work of a long playfair, not certain how it would perform on a short one, i need to test that)

One main reason pen and paper isn't considered "secure" is that they simply can't stand up to large volumes of traffic. I note that no one has attempted my known plaintext "impractical-1" cipher challenge yet. :) And I don't blame them. Diego is worth attacking because it is simple to use, and has some intriguing holes. Impractical-1 is NOT simple to use, (thus the name) and while I'm certain it has holes (rot13 pointed out a possible approach), instead of looking "intriguing", they look dull and TEDIOUS.

For example, I think if you put up a "PlayDiego" (or whatever we decided to call it) version of this challenge, it probably wouldn't be worth the bother to attack it. All of the "interesting" parts of the cipher would be hidden too deep to get at because the cipher text letters we see would NOT necessarily tell us everything about what was being shifted.
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
Dang, I was approaching this the hard way. The "shift trees" are extremely simple (as everyone else probably realized) Each shift just defines a block of possible characters a particular letter could have moved to. and its an actual BLOCK. DUH! Thats obvious and inherent in the rules. If you start with an up shift, the block is directly above and to the right of the first letter. If you start with a right shift, the block is directly to the right and above the first letter.

numbers are X(width) x Y(depth)

shift 9up = 5x5 block (25 letters)
shift 9rt = 5x5 block (25 letters)
shift 8up = 5x4 block (20 letters)
shift 8rt = 4x5 block (20 letters)
shift 7up = 4x4 block (16 letters)
shift 7rt = 4x4 block (16 letters)
shift 6up = 4x3 block (12 letters)
shift 6rt = 3x4 block (12 letters)
shift 5up = 3x3 block ( 9 letters)
shift 5rt = 3x3 block ( 9 letters)
shift 4up = 3x2 block ( 6 letters)
shift 4rt = 2x3 block ( 6 letters)
shift 3up = 2x2 block ( 4 letters)
shift 3rt = 2x2 block ( 4 letters)
shift 2up = 2x1 block ( 2 letters)
shift 2rt = 1x2 block ( 2 letters)
shift 1up = 1x1 block ( 1 letter)
shift 1rt = 1x1 block ( 1 letter)

So, if you have the sequence XZ YM X and you KNOW that the first X is a plain "V", then the second X (4 shifts away, starting with an up shift) can ONLY be one of V,W,X,Q,R,S.

Which becomes quite significant when you have a sequance like we do in this particular message: TX XW XT XT

x1:25 <-25 possible letters for the first X
x2:1 <-for each of those, only 1 possible letter for the 2nd X
x3:2 <-for each of those, only 2 possible letters for the 3rd X
x4:2 <-for each of those, only 2 possible letters for the 4th X

t1:25 <-25 possible letters for the first T
t2:9 <-for each of those, only 9 possible letters for the 2nd T
t3:2 <-for each of those, only 2 possible letters for the 3rd T

w1:25 <-25 possible letters for the single W.

So, 25*1*2*2=100 possible combinations for the X's
and 25*9*2=450 possible combinations for the T's.

The X's alone could be eyeballed and might reveal a solution. and thats only 45,000 total possible combinations that would give us all but 1 letter of a 8 character section. That's a LOT better than the 6,103,515,625 we would have to try normally. Even adding in the W only raises the total to 1,125,000, still easily computer approachable. And with an 8 character stretch, it ought to be possible to do a dictionary scan and eliminate all combinations that don't get at least one hit.

Is this how your crib dragging program is working rot13?
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
I haven't really started attacking the real Diego yet. As I was working on cracking the other one last night, I was also trying to solve E-7 from the Nov-Dec 05 Cryptogram. I pretty much have it now. I have a few more aristocrats to solve and I will have solved all but 1 in the whole issue. I just can't get AC-798. :( Once I get that done I can spend a little more time on Diego.
Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
I've tried attacking AlphaDiego with a GA scoring on monogram frequency analysis. It didn't do so well. Curious. I'm considering shifting to bigrams.


Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · Challenges · Next Topic »
Add Reply