Forum

Challenge "Monoalphabetic substitution with camouflage — Part 1"

Challenge "Monoalphabetic substitution with camouflage — Part 1"  

  By: admin on Oct. 27, 2011, 9:41 a.m.

It is not difficult to break a monoalphabetic substitution but in this challenge an additional camouflage alphabet causes confusion.
Read more...

 Last edited by: admin on Oct. 31, 2021, 2:54 a.m., edited 1 time in total.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: fretty on Oct. 28, 2011, 12:05 a.m.

How is this system any different from using nulls in a substitution cipher?

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Veselovský on Oct. 28, 2011, 12:52 a.m.

Can you be a bit more specific, please?. What type of using "nulls" in a substitution cipher do you mean? There are plenty different methods.
If you specify your cipher then I can tell you if there is some difference or not.
Otherwise your question does not make much sense to me.
It is like asking "How is 5 any different from a positive integer"?

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: fretty on Oct. 28, 2011, 9:40 p.m.

The concept of using nulls in a substitution cipher is a well defined concept and has been so for hundreds of years. Any amateur cryptographer would know what I am talking about in my post above.

Nulls are exactly how they sound…symbols that mean nothing. So this "substitution with camouflage" is nothing more than shoving nulls in really.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: be on Oct. 29, 2011, 3:40 p.m.

The concept of using nulls in a substitution cipher is a well defined concept and has been so for hundreds of years. … So this "substitution with camouflage" is nothing more than showing nulls in reality.

Hello, thanks for your comments, but please be a bit more polite to each other.
First, I want to state, that this contest may and should also reuse concepts which are well-known to have fun and to achieve didactical goals. Secondly, there are different variants of nulls. An easy variant would be to add nulls after performing the encryption process at the sender side and just to discard them at the recipients side. Another variant (which is used here) is to add them to the enhanced plaintext alphabet and apply the encryption algorithm to them too, which makes it more interesting, as now nulls can be transformed to other "valid" plaintext letters.
I recommend for this forum more constructiveness:

  • not to discusswhether this special challenge uses an old concept or not;[/list:u]
  • but to discuss
  • e.g. what are the different variants, and what is their particular strength/weakness, and
    • e.g. what are possible ways to solve this challenge without doing so via brute-force.[/list:u][/list:u] Thanks, Bernhard

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: DarkFibre on Oct. 30, 2011, 4:04 a.m.

All I know is this problem is freaking hard. I tried attacking by hand a bunch of ways, they all failed. I wrote a (shotgun hill climbing?) program to evolve towards and answer, that failed. Wrote another program to try statistical attacks, that failed. Short of generating all ~10,000,000 possible combinations and trying to crack each one I'm running out of ideas.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Veselovský on Oct. 30, 2011, 11:36 a.m.

Hello, Darkbibre,
What do you think it is that makes it so difficult to solve?
What is your idea of an additional information (hint) that would help you to solve it?
Another small hint, is that one word of English sentence has exactly same spelling as one word of German sentence.
I know you could not be for 100% sure just from ciphertext, but at least it is easy to guess that two words have at least similar spelling.
So now you can be for 100% sure that they have the same spelling.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Veselovský on Oct. 30, 2011, 12:10 p.m.

If nobody gets any idea within a day or so, I will describe a method that significantly decreases the number of possibilities to check and that, I hope, would lead you to a solution.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: DarkFibre on Oct. 30, 2011, 8:58 p.m.

Apparently the algorithm in my first program only works on long ciphers, and that may be true for my other program, so it might not be as hard as I thought. I will try by hand some more using that hint.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Dano on Oct. 30, 2011, 11:07 p.m.

can you give a hint about the meaning of the 2 phrases?
abbout the content?

is very strong challange

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Veselovský on Oct. 31, 2011, 12:53 a.m.

can you give a hint about the meaning of the 2 phrases?

I can but I will not ;-) …you do not need it very much for being able to solve it.

All my challenges are such that at first I must be able to solve them in reasonable time and reasonable effort for appropriate level.
I do not make challenges of some difficult problems of which I have no idea how I would solve them if I were in the position of the users. (otherwise I would recommend it for publishing in level 3)

Perhaps tomorrow (actually its already today) I will describe a method how to solve it without a brute force. …and what was my intention how it should be solved.
…but it won't be too easy even with this method ;-)

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Veselovský on Oct. 31, 2011, 9:48 p.m.

There are 24 different letters in the first cipher text and 24 different letter in the second one.
There are 42504 (24!/((24-5)! 5!)) possibilities to choose 5 letters from set of 24 different letters.
So this problem is solvable by the most basic brute-force checking all 42504 possibilities.
Each possibility is represented by a ciphertext from which 5 different letters has been removed.
(each 5-letter set represents possible guess for camouflage letters of which we get rid off)
We do not have to solve both ciphertexts, because if we found solution for the first one, then using same key for decryption we can decipher also the second one.
So there are 42504 possibilities to check for possible monoalphabetic substitution.
I think it is possible to solve it by brute-force.

Another way to solve it:
The camouflage alphabet is very short compared to the plaintext alphabet. The shorter the camouflage alphabet is the bigger number of occurrence there is for particular letter of camouflage.
For example if camouflage alphabet was only one letter long, say "a", than to camouflage whole text we need to use it many times, which increase its occurrence it the ciphertext, so it means that the letter with the most frequency of occurrence would be with high probability the camouflage one.
Here we have camouflage alphabet of length 5, which means that there is high probability that letters that represents camouflage are among the more frequent letters.
Other way said, letters in ciphertext with small frequency are most likely the meaningful one (i.e. not camouflage). But there is still chance that, say ,one letter of camouflage can occur among the letters of small frequency.
So we count occurrence of letters of both ciphertexts separately, then choose upper bound for occurrence, say 3, and we presume that all characters that occur less or equal to 3 are the meaningful one.
Other way said, we presume that all camouflage letter are among letters of occurrence 4 or more.
So we have two sets… one set represents most frequent letters from first cipher text and second one from second ciphertext.
We know that both ciphertext contain same letters of camouflage, so we make an intersection of the mentioned two sets. This intersection reduces the possibilities of letters from we have to choose 5 letters that represents camouflage.
So now we do not have to check all 42504 cases, but we reduced it to number slightly bigger than 100 possibilities to check. (we do not have to choose 5 from 24, but 5 from much smaller number)

Now we can use brute-force attack only on those reduced set.

But we have additional information that there is a word of same spelling in both ciphertexts and we know that plaintexts have same meaning so it is probable that there are words in English which have their equivalents in German. All this additional should help you to find the solution even without a brute-force.

Hope it is understandable. My Explanation in English is limited.
If this was not enough then I will disclose one letter of camouflage, but I hope this would not be necessary.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Dano on Nov. 1, 2011, 12:19 a.m.

i will try more in the next days…

but bruteforce of 42000 possible…. is not pen and paper ;)

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: Veselovský on Nov. 1, 2011, 12:56 a.m.

What 24000 possibilities???
I wrote, that by simple counting of letters you can reduce all 42504 possibilities to some more than 100. And we haven't still used the fact about two words of same spelling. This fact reduces it even more.
There are 77 characters in first ciphertext and 91 characters in second one.
By simple counting of all 168 characters you found a reduction from 42504 to roughly 100. It is significant reduction.
I guess you do not need a computer to count up to 168 ;-)

And there is still the fact with the same meaning…

What is interesting is that your guess for upper bound does not have to be 3, even with upper bound 2 there is reduction, but slightly smaller… even more if you select as upper bound 1 the cases still can be reduced to less than 100 possibilities in the end.

Even if you select as upper bound 0 (i.e. no upper bound at all) you still can reduce it to some more than 3000. But as I sad, the camouflage alphabet is too short compared to plaintext alphabet so it is very probable that camouflage letters are among letters with bigger occurrence.

Re: Challenge "Monoalp. substitution with camoufl. - Part 1"  

  By: DarkFibre on Nov. 1, 2011, 5:33 a.m.

Using your hints I found 2 definite nulls and 7 possibles (2 of which seemed likely). I tried the 5 combinations that seemed most promising with the best English cryptogram solver I know of and none worked. So I tried all 35 likely combinations, none worked. For good measure I then generated all 126 possible null combinations, tried them all, none worked.

I then assumed there must be something wrong with the English part but that you had tested the German part. So I generated and tested the 35 most likely combinations, none worked.

I have now invested more hours on this than I have on a lot of level IIs.

It seems either the ciphers are garbled or your hints are wrong. Are you sure all the nulls were used 4 or more times in both ciphers? If not that adds another 8,500 combinations that need to be brute forced.


Currently 12 guests and 0 members are online.
Powered by the CrypTool project
© 2009-2021 MysteryTwister team