• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 394
  • Last Modified:

Crypto Challenge 17 Bonus Points

Seeing as Crypto challenge 17 ( http://www.experts-exchange.com/Miscellaneous/Puzzles_Riddles/Q_22056129.html ) could be a toughy I thought I would open a thread with a few bonus points available. I envision this thread consisting of four questions, which I will post one by one as each part is answered.

Question 1 for 100 points: What do the title and instructions for Crypto challenge 17 say?
0
KelvinY
Asked:
KelvinY
  • 10
  • 3
  • 2
  • +2
3 Solutions
 
Peter KwanCommented:
Key: TWO
Title: TWO KEY OR NOT TWO KEY
Instruction:
The challenge for this week takes a slightly different direction Instead of giving you one message to crack I am providing two along with the fact that a very basic error has been committed in encrypting these messages Your mission should you choose to accept it is to recover the key to these messages and post it for the points
0
 
KelvinYAuthor Commented:
Well done pkwan, the first points are yours. Now for next question.

Question 2 for 100 points: What was the very basic error committed in encrypting these messages?
0
 
KelvinYAuthor Commented:
Clue for Q2: The same error was committed when encrypting the title and instructions and when encrypting the two challenge messages.
0
A Cyber Security RX to Protect Your Organization

Join us on December 13th for a webinar to learn how medical providers can defend against malware with a cyber security "Rx" that supports a healthy technology adoption plan for every healthcare organization.

 
Peter KwanCommented:
May I have a guess that the error is:
The key is part of the plaintext?
0
 
KelvinYAuthor Commented:
pkwan,

Have as many guesses as you like. In this case, while the key is part of the plaintext in the title and instructions, which is not a good idea, that is not the error in the challenge codes. Using a weak key still produces reasonable ciphertext from the Vigenere cipher, which was used for the title and instructions. A different cipher was used for the challenges. I normally implement these challenges in such a way that there is a weakness, so that the experts have a reasonable chance of breaking the codes. Choosing weak keys is one of the ways that this is done.

The actual error does have something to do with the way that the key is used.
0
 
Mark_FreeSoftwareCommented:

The critical weakness in the Vigenère cipher is the relatively short and repeated nature of its key. If a cryptanalyst discovers the key's length then the cipher text can be treated as a series of different Caesar ciphers, which individually are trivially broken. The Kasiski and Friedman tests help determine a ciphertext's key length.
0
 
KelvinYAuthor Commented:
Mark_FreeSoftware,

Those are good points about the Vigenere cipher, which was used for the title and instructions of Cipher challenge 17. What I'm actually interested in is the basic error that was committed in encrypting the two challenge texts, for that challenge, with the XOR cipher.
0
 
Mark_FreeSoftwareCommented:

then i would guess you are talking about omitting the spaces?
0
 
KelvinYAuthor Commented:
Mark_FreeSoftware,

It's not the spacing. The error that I am interested in makes it easier to recover the encryption key from the messages.
0
 
KelvinYAuthor Commented:
The experts seem to be flagging on this one, so let me supply a very broad hint. The basic error that I am refering to makes it particularly easy to recover the encryption key from messages that are encrypted using the XOR cipher.
0
 
GieronCommented:
Part of the key is the same as part of the plain text. But more specifically the error is that that part of the plain text is encrypted with the matching part of the key.

That didn't make much sense. I give an example:

Key: rataxex
Plain text: They pay taxes
Encrypt with some sort of XOR (^)

Encrypted text:

T ^ r = 8
h ^ a = 7
e ^ t = 2
y ^ a = 6
_ ^ x = 2
p ^ e = 6
a ^ x = 5
y ^ r = 4
_ ^ a = 2
t ^ t = 0
a ^ a = 0
x ^ x = 0
e ^ e = 0
s ^ x = 1

Encrypted text: 87262654200001

The point is that when the key and the plain text lines up the XOR produces zeroes. The rest of the numbers I just made up :)
0
 
KelvinYAuthor Commented:
Gieron,

Still not quite what I'm after. The error that I am refering to introduces a weakness that may be taken advantage of by the observation that you have made here, in a way.
0
 
Peter KwanCommented:
Actually, the XOR cipher can be also solved by the Kasiski test. That means, by examining the position differences of the most occuring digraphs, and the key length is the multiple of the HCF of the difference. For example, in ciphertext 1, the HCF of the position differences of the most occuring digraph is 10. Then I will guess the key length should be 10.

Once the key length is determined, a brute force search can be used to retrieve the key.
0
 
KelvinYAuthor Commented:
pkwan,

You're on the right track. The Kasiski method or the index of coincidence can be used to determine the key length for an XOR cipher. In my EE challenges I use fairly short keys, but in reality much longer keys would be used, making it harder to attack with brute force. There is a fundamental error, made when encrypting several messages, that will allow an XOR to be cracked without brute force, or even having to know the key length and it is this error that I deliberately committed when composing the challenge.
0
 
Thibault St john Cholmondeley-ffeatherstonehaugh the 2ndCommented:
A XOR C = M
B XOR C = N
M XOR N = C

I wish I'd thought of that!
0
 
KelvinYAuthor Commented:
RobinD,

I think that's close enough. It's actually

A XOR C = M
B XOR C = N
M XOR N = (A XOR C) XOR (B XOR C)
  = (A XOR B) XOR (C XOR C) [XOR is associative]
  = A XOR B

If you use the same key for more than one message then all you have to do is XOR the messages together and the key drops out, leaving you with plaintext XORed against plaintext. Using the redundancy in the language you can then separate the plaintexts and recover the key. For example, Gieron pointed out above that the same characters XORed together produce a zero.

I think I'm going to hand out points now. I had been planning to work up to this conclusion in four stages, but nobody came up with the quick answer to part 2, which was that you should not use the same key more than once. It's not a good idea with most ciphers, but the properties of the XOR operation mean it introduces a particularly exploitable weakness.
0
 
Thibault St john Cholmondeley-ffeatherstonehaugh the 2ndCommented:
Thanks!

I did a little test and my formula worked,

1 xor 3 =2
2 xor 3 =1
1 xor 2 =3

I can see now that I should have tested a little further, perhaps with the texts themselves or just some bigger numbers.


0
 
KelvinYAuthor Commented:
RobinD

That works because the 1 and 2 have no bits in common. I suppose it is a good idea to base an empirical observation on more than one data point. :)
You got the points anyway because you were the first to point out that there is something special about the XOR operation.
0

Featured Post

What Security Threats Are We Predicting for 2018?

Cryptocurrency, IoT botnets, MFA, and more! Hackers are already planning their next big attacks for 2018. Learn what you might face, and how to defend against it with our 2018 security predictions.

  • 10
  • 3
  • 2
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now