Hi, zyxt:
One generally needs to know a bit about the encryption algorithm
before one can successfully determine the key (using P and C). Here,
for example, you "know" that the encryption algorithm is symmetrical.
When the encryption algorithm is "known" or simply available in black
box form, then one can try a "brute force" attack to determine the
key. Various keys, often drawn from a "dictionary" of likely
passwords/keys, are used to encrypt P until a match with C is made, or
equivalently, the succession of keys is used to try and decrypt C into
P (given your comment about the symmetry of the algorithm).
When not only the encryption algorithm but the intact mechanism of
encrypting a preferred text using the unknown key is available, then
one can perform a "chosen plaintext attack". That is, one has extra
information if _you_ control the choice of P arbitrarily. Since keys
are of finite length, most "streaming" methods of encryption will
reveal their periodicity when asked to encrypt long strings of
repeating characters.
For a discussion of both of these topics, see:
http://www.shyfile.net/attack.html
The theoretically perfect encryption method is to use a "one-time pad"
key, randomly chosen, of length equal to the message. Then any
symmetric reversible mapping of characters such as an XOR between the
plaintext and key characters will produce a random result C, one
equally likely to be the ciphertext of any input (assuming a
sufficiently long random key).
So the likelihood of success in using P and C to determine the key
depends on having reasonably short keys or encryption algorithms that
are "defective" in some known way in propogating the randomness of the
key into the ciphertext.
If the job is done "right" (as with the one-time pad), the encryption
is secure, or at least as secure as the distribution of these keys is.
As a by-light, a company was recently formed to commercialize secure
distribution of one-time keys using ideas from quantum computing
theory; see:
"Magiq employs quantum technology for secure encryption"
http://www.eetimes.com/at/news/OEG20021105S0019
Here are selected sites that discuss plaintext attacks in the context
of specific algorithms/encryption methods:
"CSS (Content Scrambling System [for DVDs]): The Plaintext Attack"
http://www.tinyted.net/eddie/css_plaintext.html
"ELCOMSOFT: Password Recovery Software"
http://www.elcomsoft.com/prs.html
"Zip Key: a program to recover passwords for ZIP archives"
http://www.lostpassword.com/zip.htm
"CCC\Harvest Source Code Encryption Cracked by Chosen Plaintext
Attack"
http://www.securiteam.com/windowsntfocus/5BP0W003PQ.html
Please advise me if there are points you would like clarified in order
to have your question satisfactorily answered.
regards, mathtalk-ga |
Request for Answer Clarification by
zyxt-ga
on
05 Nov 2002 19:20 PST
I didn't ask how to take ciphertext and derive cleartext. Also, I've
read all the basic texts. Let me see if I can clarify. I know a
plaintext message. I know a ciphertext which represents the plaintext.
The question is, how can I select a key/algorithm pair that produces
the plaintext/ciphertext pair I have? An ideal solution would be to
have a way to cycle through arbitrary algorithms (for example, in a
crypto library), and for each, to cycle through likely keys, at each
point testing to see if the tested algorithm/likely key produces the
plaintext/ciphertext pair. Has anyone thought about this problem,
either mechanically, logically, or mathematically? Also, assuming a
heuristic exists to solve this kind of problem, would it only work for
ciphertext/plaintext pairs that were not randomly selected? In other
words, if the original ciphertext/plaintext pair were randomly
selected, is it always possible to find an algorithm/key pair that
would match them.
Put more broadly, perhaps this is not a crypto question, but a
question about transform functions. Assuming that an encryption/key
pairing is, in effect, a single function for transforming input to
output; is it possible to derive that function knowing only an assumed
input/output pair? And is it necessarily the case that the
input/output pair would have had to be initially produced through a
preexisting function for the kind of question I'm asking to be
solvable?
|
Clarification of Answer by
mathtalk-ga
on
05 Nov 2002 21:25 PST
Hi, zyxt:
If you ask whether an algorithm and a key can be found to transform
given P into given C, then the answer is yes:
Suppose the two texts P and C are of equal length (which seems a
reasonable restriction given your assumption of symmetric key
encryption). One gives the following encryption algorithm and key
pair:
Take the XOR of each pair of corresponding characters in P and C to
obtain string K.
Then encrypting P by XOR'ing it with K (as in a one-time pad key)
produces C.
Proof:
Let "^" denote the character by character XOR'ing of strings of equal
length.
K = P^C
P^K = P^(P^C) = (P^P)^C = C
//QED
Is it likely that this is the _same_ algorithm that was used
originally to encrypt P into C? No, not really. But it is one
particular algorithm/key pair that transforms P into C.
What would be convincing, as an empirical inference about the original
algorithm, would be if a "likely" one worked with a short key, much
shorter than the length of the message. The difficulty lies in
defining what would make an algorithm "likely" among all algorithms.
Can we create a "dictionary" of encryption algorithms, just as we can
create on for keys? Yes. Your question assumes about the encryption
algorithm that it uses a key and (if I understand your use of
"symmetric") the same key used for encryption can be used for
decryption. Unfortunately there are infinitely many such algorithms,
just as there are infinitely many keys. More to the point, unlike
with the notion of keys (which can be ordered by length and within
length, lexigraphically), there is no natural order among these
algorithms that would make it easy to choose a starting point (and
hence to assign greater probabilities to those algorithms near this
starting point, with smaller probabilities farther away from it).
If the "space" of algorithms were as simple as that of the keys, then
it would be sensible to proceed along the lines you suggest. But
there are a variety of families of encryption algorithms which can be
described, even within the overall "stream encoding" approach that
involves XOR'ing something with the next character in the key.
Instead of XOR'ing simply the next character from P, one might add to
that character the result of the previously encoded character (taken
modulo the size of the character/symbol set), then XOR that result
with the character from C. In this way the ciphertext needs to be
decoded from its beginning; there is no jumping in to the middle.
Most real world encryption algorithms depart from these relatively
easily broken "streaming" algorithms by introducing ideas of
permutation, rearrangement of the texts either at the character or bit
level. And again we face an infinite variety of algorithms for doing
the permutations. The RSA encryption and DES encryption use very
different means to produce a reversible "jumbling" of the bits that
make up a message. An older idea is to group the characters into a
square array, by rows, and then read them out by columns.
Another sort of encryption procedure is polyalphabetic substitution,
esp. good for removing information imparted by character frequencies
from messages.
So while it is always possible to define a transform from P to C,
actually one can always define infinitely many such transforms. That
by itself is not so big a difficulty as assigning a priori
probabilities to the algorithmic side of the transform. If we could
do this, then in principle one could apply Bayesian inference to argue
for the most probable algorithm/key pair (much as one can rationalize
short keys as being more probable than long ones).
regards, mathtalk-ga
|
Clarification of Answer by
mathtalk-ga
on
06 Nov 2002 09:00 PST
Hi, zyxt:
Your idea of looking for a tranform F such that F(P) = C has this
analogy with "find the sequence" problems:
A sequence begins 3, 5, 7, ... . Find the general formula.
From a mathematical standpoint there are infinitely many formulas that
provide these first few values, f(1) = 3, f(2) = 5, f(3) = 7. One
might "guess" a formula that uses polynomial interpolation or one
based on the sequence of odd primes. While a formula that explains
the sequence "simply" would likely be preferred to a complicated one,
either of these might be considered the most likely explanation
(again, depending on the context). These two formulas would lead to
different guesses about the next term in the sequence.
In your case the context would be supplied by a "dictionary" of
encryption algorithms. There is no such standard dictionary, although
Neal Stephenson has written a novel, Cryptonomicon, which is titled
after a fictious book of the same name originating in the 1600's that
supposedly is a compendium of the state-of-the-art on code making and
breaking. It is modelled after a real book, Mercury by John Wilkins
(1641), see here about halfway down the page:
http://www.well.com/user/neal/cypherFAQ.html
Of course Neal is a novelist, not a cryptanalyst, but in his novel
there are some quite realistic materials woven into his plot device,
of this compendium being updated down the ages.
For a Web site that provides a bit of real world flavor around
cryptology issues, I found this one interesting:
http://www.cryptonomicon.net/
Like many "portal" sites, the immediate content is perhaps not as
important as its collection of Web links. Registration is required to
access some portions of the site.
regards, mathtalk-ga
|
Clarification of Answer by
mathtalk-ga
on
07 Nov 2002 18:37 PST
Hi, zyxt:
Thanks for taking time to rate my answer; the feedback means a lot to me!
regards, mathtalk-ga
|
