Solved

Crypto Challenge 17 Bonus Points

Posted on 2006-11-10
18
384 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
ScreenConnect 6.0 Free Trial

Explore all the enhancements in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI, app configurations and chat acknowledgement to improve customer engagement!

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

Ransomware-A Revenue Bonanza for Service Providers

Ransomware – malware that gets on your customers’ computers, encrypts their data, and extorts a hefty ransom for the decryption keys – is a surging new threat.  The purpose of this eBook is to educate the reader about ransomware attacks.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Does your audience prefer people in photos or no people? How can you best highlight what you’re selling? What are your competitors doing, and what can you do that is different and unique from them?  Continue reading to learn how to make your images …
Data breaches are on the rise, and companies are preparing by boosting their cybersecurity budgets. According to the Cybersecurity Market Report (http://www.cybersecurityventures.com/cybersecurity-market-report), worldwide spending on cybersecurity …
Microsoft Active Directory, the widely used IT infrastructure, is known for its high risk of credential theft. The best way to test your Active Directory’s vulnerabilities to pass-the-ticket, pass-the-hash, privilege escalation, and malware attacks …
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

770 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