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
Quagmire Iv Cipher Variations
Topic Started: Apr 22 2006, 01:05 PM (1,308 Views)
alice
Just registered
[ * ]
Howdy!

A while ago I created basically and exact duplicate of the Quagmire IV cipher, without knowing it. Updating the program I wrote (originally in PHP) in Python, I have created two distinct versions: one with a fixed-length repeated key, and the other auto-keyed.

I have been unable to find a good evaluation of the difficulty to crack auto-keyed ciphers, especially variations of Quagmire or Vigenere, and I'm curious. How "strong" is my cipher, relative?

A description of my cipher:

1. Given a base alphabet built of randomized unique characters, build a table derived from a passphrase with the base alphabet rotated by the offset of each character of the passphrase. An example alphabet of "AZBXCWDVEUFTGSHRIQJPKOLNM_" and passphrase of "BOB_DOLE" produces the following table:
Code:
 
* AZBXCWDVEUFTGSHRIQJPKOLNM_
----------------------------
B BXCWDVEUFTGSHRIQJPKOLNM_AZ
O OLNM_AZBXCWDVEUFTGSHRIQJPK
B BXCWDVEUFTGSHRIQJPKOLNM_AZ
_ _AZBXCWDVEUFTGSHRIQJPKOLNM
D DVEUFTGSHRIQJPKOLNM_AZBXCW
O OLNM_AZBXCWDVEUFTGSHRIQJPK
L LNM_AZBXCWDVEUFTGSHRIQJPKO
E EUFTGSHRIQJPKOLNM_AZBXCWDV

2. Encode plaintext using each row from the above table to translate each character sequentially, using the offset in the shifted alphabet as the offset in the original alphabet to transcribe. (Repeat the rows as required. The other variation uses the plaintext to continue the table ad. inf.) E.g. "TEST" encodes against rows "BOB_", giving the offsets 10, 14, 12, and 13, and looking up those offsets in the original alphabet gives the ciphertext "USTG".

3. To decode, look up the offset of each character of ciphertext in the original alphabet and transcribe from each row of the table sequentially.

The original alphabet I use is 85 characters containing every character reproduceable on a standard 101-key keyboard, scrambeled, and including a newline.

Example ciphertext using method 1, repeating passphrase, and the alphabet described above:
Code:
 
AQolX*>k
KbA}Zr|l]i@zd})#|)aUflXi+n$H)/~~QU!7=U9z3c#a{*]rf!}_FzdX=s~Ha>52K}|.3N"a2^2.**|Brk
z7c]ZDykK}lldi#FAVQ}*W)
+ru>r5Y6

Hints: (read one line at a time)
1. No newlines were used in the original message.
2. The passphrase is comprised only of characters in the range a-z, A-Z, and space.
3. The passphrase has personal significance.
4. The first 54 characters are a single sentence, ending in the word "challenge".
5. The first and second lines are missing a trailing space, each. ;D


If anyone could provide a detailed analysis, I would be eternally grateful! I've attached the program I wrote which created the above example ciphertext. You will need a working copy of Python and a text terminal to run it - rename it cipher.py. From a terminal type 'python cipher.py' and follow prompts. It will need to be modified to support input with newlines... :D

- Alice
Offline Profile Quote Post Goto Top
 
alice
Just registered
[ * ]
Attached is the updated cipher application. It supports the following command-line options:

Code:
 
[-Adev] [-a alphabet] [--] <keyphrase> [filename]
-A (autokey)
-d (decode)
-e (encode, default, can be omitted)
-v (verbose - displays sorted character distribution statistics)

The way I encoded my challenge is as follows:

Code:
 
mbevan@chupacabra ~ $ ./cipher.py -d -a "ABCDEFGHIJKLMNOPQRSTUVWXYZ-" KEYPHRASE alice.txt
VOMJGYKIRVIGPGXZLHUSCQ...
mbevan@chupacabra ~ $ ./cipher.py -a "ABCDEFGHIJKLMNOPQRSTUVWXYZ-" KEYPHRASE alice.txt
XKKUCUXGUWMRPBWLHBFRHR...

UPDATED: Now includes autokeying and distribution analysis!
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
Well, it wouldn't stop the NSA, but quagmires are NASTY to do by hand. :) But rot13 busted my quag-like in my Journal challenge. SO, they CAN be done, but they are HARD.

Which brings me to one important observation: including space (underscore) in your cipher reduces security signifigantly. That is, if you encrypt spaces in the plain text. Even in a Vig or Quag, having a space character available can be a big clue for cryptanalysis. If this were AES or something like that, it would be immune even to known plain text attacks. But pen and paper ciphers arent, and even a nasty quag like this is vulnerable to cryptanalysis. So, while marking word divisions is a nice advantage for the authorized decryptor, its also an advantage for the unauthorized decryptor.

Offline Profile Quote Post Goto Top
 
Revelation
Member Avatar
Administrator
[ *  *  *  *  * ]
This is not a Quagmire IV according to this document. This looks like a vigenere made from a mixed alphabet. This challenge is interesting and looks good. :)
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN
RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN
RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN
RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN
RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
"revelation"
 
This is not a Quagmire IV according to this document.

No, its just Quag Like. :) There are LOTS of variations on the Quag.
Offline Profile Quote Post Goto Top
 
alice
Just registered
[ * ]
As far as I can tell, mine is much more flexible on the whole, and is based on Quagmire IV even before I knew Quagmire existed. Here's why:

1. With a key length of one and a simple A-Z alphabet (without space) mine (I'll be calling it Cheshire from now on) turns into a simple Caesar cipher.

2. With a key length of the entire message, Cheshire turns into a perfect one-time pad.

3. With a scrambeled alphabet the shifts will be unpredictable unless the original alphabet - and order - is known.

4. The shifting nature of the alphabet (as the keyphrase is used up) tends to average letter distribution. In my "simple" challenge:
Code:
 
Character: - 13 (4.94)
Character: T 7 (2.66)
Character: E 7 (2.66)
Character: O 5 (1.90)
Character: S 16 (6.08)
Character: A 9 (3.42)
Character: I 7 (2.66)
Character: D 14 (5.32)
Character: N 8 (3.04)
Character: H 13 (4.94)
Character: R 14 (5.32)
Character: U 5 (1.90)
Character: L 14 (5.32)
Character: W 7 (2.66)
Character: P 7 (2.66)
Character: G 13 (4.94)
Character: F 6 (2.28)
Character: Q 11 (4.18)
Character: V 20 (7.60)
Character: C 14 (5.32)
Character: Y 11 (4.18)
Character: M 10 (3.80)
Character: Z 7 (2.66)
Character: B 6 (2.28)
Character: K 8 (3.04)
Character: J 7 (2.66)
Character: X 4 (1.52)

I can tell you that the top four characters in the cleartext were 50 (19%), 25 (9.5%), 25, and 21 (8%). In the above distribution there are only a handful of characters above 5%!

Now to the reason Cheshire is a Quagmire IV-style cipher: in Quagmire IV the pt key is used to perturb the alphabet, whereas mine the pt key covers the whole alphabet (or doesn't). In this way the encoded content is limited to only the characters in pt. I ignore ct, instead re-using the original pt-driven alphabet. The indicator in Quag is the keyphrase in Cheshire. Basically the same. (I had a better description of Quagmire on
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
"alice"
 
With a key length of the entire message, Cheshire turns into a perfect one-time pad.

Well, it's not PERFECT unless the key is TRUELY random. But I think I understand what you mean. :)
Offline Profile Quote Post Goto Top
 
kryptosfan
Member Avatar
Kickass member
[ *  *  *  *  *  * ]
With a truly random key why wouldn't I just use OTP in the first place? I thought Friedman figured out the weaknesses of a running-key Vigenere in 1920?

I will admit that self-synchronous dynamic substitution is ***** to solve for folks like me with our monkey paws but I didn't think autokey Vigeneres stood up to this forum's cryptanalysis programs?
OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
Offline Profile Quote Post Goto Top
 
james
Elite member
[ *  *  *  *  * ]
In Alice's cipher the plain mixed alphabet and the cipher mixed alphabets are all the same, and the cipher alphabets are shifted with regard to the plain. This is a Quagmire 3, as members of the ACA will recognise.

The inclusion of a space character is a feature that is not used in the ACA.

A Quagmire 3 cipher is usually included in each issue of The Cryptogram and is regularly solved by a number of the Krewe with the help of a crib.
Offline Profile Quote Post Goto Top
 
kryptosfan
Member Avatar
Kickass member
[ *  *  *  *  *  * ]
I didn't know I needed an ACA card to be here.
OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · General · Next Topic »
Add Reply