Solved

Crypto Challenge 17 Bonus Points

Posted on 2006-11-10
18
382 Views
Last Modified: 2008-02-01
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
Comment
Question by:KelvinY
  • 10
  • 3
  • 2
  • +2
18 Comments
 
LVL 16

Accepted Solution

by:
Peter Kwan earned 100 total points
ID: 17925341
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
 
LVL 8

Author Comment

by:KelvinY
ID: 17925356
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
 
LVL 8

Author Comment

by:KelvinY
ID: 17938924
Clue for Q2: The same error was committed when encrypting the title and instructions and when encrypting the two challenge messages.
0
 
LVL 16

Expert Comment

by:Peter Kwan
ID: 17945377
May I have a guess that the error is:
The key is part of the plaintext?
0
 
LVL 8

Author Comment

by:KelvinY
ID: 17945716
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
 
LVL 13

Expert Comment

by:Mark_FreeSoftware
ID: 17974086

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
 
LVL 8

Author Comment

by:KelvinY
ID: 17975943
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
 
LVL 13

Expert Comment

by:Mark_FreeSoftware
ID: 17976055

then i would guess you are talking about omitting the spaces?
0
 
LVL 8

Author Comment

by:KelvinY
ID: 17976413
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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 8

Author Comment

by:KelvinY
ID: 17994476
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
 
LVL 2

Assisted Solution

by:Gieron
Gieron earned 50 total points
ID: 17994890
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
 
LVL 8

Author Comment

by:KelvinY
ID: 17994954
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
 
LVL 16

Expert Comment

by:Peter Kwan
ID: 17995166
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
 
LVL 8

Author Comment

by:KelvinY
ID: 17995441
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
 
LVL 17

Assisted Solution

by:Thibault St john Cholmondeley-ffeatherstonehaugh the 2nd
Thibault St john Cholmondeley-ffeatherstonehaugh the 2nd earned 100 total points
ID: 18005117
A XOR C = M
B XOR C = N
M XOR N = C

I wish I'd thought of that!
0
 
LVL 8

Author Comment

by:KelvinY
ID: 18005216
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
 
LVL 17
ID: 18005267
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
 
LVL 8

Author Comment

by:KelvinY
ID: 18007352
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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

What is Backup? Backup software creates one or more copies of the data on your digital devices in case your original data is lost or damaged. Different backup solutions protect different kinds of data and different combinations of devices. For e…
In this article, I will show you HOW TO: Perform a Physical to Virtual (P2V) Conversion the easy way from a computer backup (image).
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now