Forum

Challenge "Substitution Cipher with Non-Prefix Codes"  

  By: admin on June 15, 2011, 11:01 a.m.

Usually prefix-free codes are used for encryption because it makes the decryption process easier at the receiver's end. However, this challenge deals with a substitution cipher with non-prefix codes. This should be broken by performing a "ciphertext-only attack".
Read more...

 Last edited by: admin on July 22, 2022, 6:11 p.m., edited 1 time in total.

Re: Challenge  

  By: randall77 on Oct. 30, 2011, 1:40 a.m.

I'm not sure I understand what you mean by "successful decryption" in this case. I always imagined "successful" ~= "unique", but that isn't the case here. For instance, your example can also be decrypted like this:

the quiet brow pyre jump sow jog theme pry dog
they rod pet brown fox jug dry wow jog theme pry dog

it all depends on the dictionary. I get 110 different decryptions, even after I get rid of some questionable entries from my /usr/share/dict/words.

Maybe you have a smallish dictionary for which the decryption is unique?

Re: Challenge  

  By: Veselovský on Oct. 30, 2011, 3:19 a.m.

It surely is not unique. But they probably want a meaningful sentence (sentences) in English.
Same way as you found another possible solution for their Introductory Example I see a "possible solutions" for their challenge ciphertext.
For example first "1" represents "p" and the rest of ciphertext represents "i"… so I got a word from dictionary: "pi"
Similarly would work do, he, is… plenty of them
Same way you can find "possible" solution with more letters (but not too many)…
I am sure you would be able to find appropriate substitution for simple meaningful sentence like for example "it rains" that would comply with the given ciphertext.
…But I doubt they would accept any of these "solutions" :-D
So I think their required solution is a longer meaningful sentence or more sentences.

I personally think that the problem as it is stated in PDF file is solvable in many different ways (if I haven't overlooked something).
Perhaps if there was an upper bound for the length of substitution sequence for one character, then I am inclined to think there would be the only one meaningful and grammatically correct solution, just the one that they want. But I do not see anything in the description like upper bound.
There is just said that "the length of the strings varies"… this means to me that a particular letter can be represented by a string of length 573, which would produce the mentioned above "solutions" of two-letter long words.
It is too late… I hope I do not write nonsenses :-DDD

Re: Challenge  

  By: stamp on Oct. 30, 2011, 6:06 p.m.

These are all good questions/comments. Clearly, there can be no unique solution as the problem is stated. So, here's some additional info that will help: All letters were encrypted using bit-strings of length 5 or less.

Now, it still might be possible to find multiple solution, but I suspect it will be a very small number, even with an unabridged dictionary. That is, if you solve the problem, you should be able to eyeball the "correct" solution from any list of "valid" solutions.

Sorry that we did not provide a clearer statement of the problem.

Mark Stamp

Challenge  

  By: Theofanidis on Aug. 7, 2012, 10:32 a.m.

These are all good questions/comments. Clearly, there can be no unique solution as the problem is stated. So, here's some additional info that will help: All letters were encrypted using bit-strings of length 5 or less.
Mark Stamp

Hello,

could you reveal how many characters does the plaintext has, because it will help me evaluate a complex procedure in which too many parameters are missing. i.e. if the plaintext contains 120 letters or 240 letters i will limit somehow these parameters. i believe that even so the challenge should remain in level 3.

if you think that this information is a very crucial hint, maybe you should inform me by PM as it is forbidden to reveal such things in this forum

Best regards
george

Re: Challenge  

  By: stamp on Aug. 8, 2012, 2:55 a.m.

Hello,

could you reveal how many characters does the plaintext has, because it will help me evaluate a complex procedure in which too many parameters are missing. i.e. if the plaintext contains 120 letters or 240 letters i will limit somehow these parameters. i believe that even so the challenge should remain in level 3.

if you think that this information is a very crucial hint, maybe you should inform me by PM as it is forbidden to reveal such things in this forum

Best regards
george

George,

There are exactly 150 characters in the plaintext. If you can solve it with this additional info, I'd definitely still rate it as a level 3 challenge.

Mark Stamp

Re: Challenge  

  By: Nelson143 on Nov. 15, 2014, 5:56 a.m.

Is a simple columnar transposition considered as easy to solve?
Why not first try to test simple columnar transposition and then double?
What is more secure, to use double columnar transposition with both key lengths around 20 or simple columnar transposition with one key of length around 33 to 40?

Re: Challenge "Substitution Cipher with Non-Prefix Codes"  

  By: george4096 on Jan. 5, 2022, 7:52 p.m.

Hello

I am trying to solve this very interesting challenge, with a couple of new ideas, and an interesting vulerability, which I am happy to share (privately).

Question: In the attached PDF (and in the referenced Master thesis), the example employs almost only code values which start with a leading 1 (e.g., a = 1001 , b = 10100, c = 1100, etc..), except for the letter 'r' which is mapped to 0. There are no codes longer than that starting with a leader 0 (e.g., '0011' or '01').

Is it safe to assume that this is also the case for the challenge here? This woud not make the challenge an easy one, but it would somehow help to reduce the size of the key space (from 62 code options, to only 32) and the workload of certain algorithms.

Thanks again for this very nice challenge.

PS: I appreciate this challenge is from quite a while ago, and it might be difficult to find the original material used to create it :-)

George Lasry


Currently 22 guests and 0 members are online.
Powered by the CrypTool project
Contact | Privacy | Imprint
© 2009-2024 MysteryTwister team