[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
?
Solved

Crypto Challenge 17 Bonus Points

Posted on 2006-11-10
18
Medium Priority
?
392 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 3
  • 2
  • +2
18 Comments
 
LVL 16

Accepted Solution

by:
Peter Kwan earned 400 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
Are You Ready for GDPR?

With the GDPR deadline set for May 25, 2018, many organizations are ill-prepared due to uncertainty about the criteria for compliance. According to a recent WatchGuard survey, a staggering 37% of respondents don't even know if their organization needs to comply with GDPR. Do you?

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

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

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

Ransomware, the malware that locks down its victim’s files until they pay up, has always been a frustrating issue to deal with. However, a recent mobile ransomware will make the issue a little more personal… by sharing the victim’s mobile browsing h…
With so many activities to perform, Exchange administrators are always busy in organizations. If everything, including Exchange Servers, Outlook clients, and Office 365 accounts work without any issues, they can sit and relax. But unfortunately, it…
In this video, Percona Solution Engineer Rick Golba discuss how (and why) you implement high availability in a database environment. To discuss how Percona Consulting can help with your design and architecture needs for your database and infrastr…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…

650 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