Finding encrytion algorithm
hi, suppose a cryptanalysis only has encrypted data-how is going 2 know which is the encrytion algorithm used 2 encrypt the data ,so that he can effeciently cryptanalyse if 1:>he has large amount of cipher text only 2:>has large amount of plain text and corresponding cipher text. There r so many encryption algorithms,how does he know which algorithm was used? Regards Data. __________________________________________________ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com
On Thu, 11 Jul 2002, gfgs pedo wrote:
suppose a cryptanalysis only has encrypted data-how is going 2 know which is the encrytion algorithm used 2 encrypt the data ,so that he can effeciently cryptanalyse if
1:>he has large amount of cipher text only 2:>has large amount of plain text and corresponding cipher text.
There r so many encryption algorithms,how does he know which algorithm was used?
Depends on how they got the source. They may know it's one of 5 possible choices because of the person who sent (or received) it. If it's just found on a disk in a garbage dump with no connections to anyone, it's a bit tougher. But every algorithm has some statistical signature and if you've got enough cipher text you can compare that signature with known algorithms to home in on fewer choices. I'm not sure having the plaintext helps much more, but you could use random keys to create several ciphertexts with known algorithms and compare the statistics just to see if they compare better. It's definitly challenging :-) Patience, persistence, truth, Dr. mike
* Mike Rosing <eresrch@eskimo.com> [020711]:
Depends on how they got the source. They may know it's one of 5 possible choices because of the person who sent (or received) it. If it's just found on a disk in a garbage dump with no connections to anyone, it's a bit tougher. But every algorithm has some statistical signature and if you've got enough cipher text you can compare that signature with known algorithms to home in on fewer choices.
Do you have any references for this? A quick google search was less than revealing. Thanks in advance.
Patience, persistence, truth, Dr. mike
-- All that is not strictly forbidden is now mandatory.
On Thu, 11 Jul 2002, Ryan Sorensen wrote:
Do you have any references for this? A quick google search was less than revealing.
There was a discussion (probably several) a few years ago on sci.crypt. If you point at usenet and try lots of different combinations of keywords I'm sure you'll find something. Since I've never done it, I don't have any direct references, I just remember some of the discussion. A question on sci.crypt might get you a lot too. Patience, persistence, truth, Dr. mike
Mike Rosing wrote:
On Thu, 11 Jul 2002, gfgs pedo wrote:
suppose a cryptanalysis only has encrypted data-how is going 2 know which is the encrytion algorithm used 2 encrypt the data ,so that he can effeciently cryptanalyse if
1:>he has large amount of cipher text only 2:>has large amount of plain text and corresponding cipher text.
There r so many encryption algorithms,how does he know which algorithm was used?
Depends on how they got the source. They may know it's one of 5 possible choices because of the person who sent (or received) it.
It may not matter much. Suppose it could be one of a hundred algorithms, a dozen of which you know how to break. If it is important and you have the resources, you just try all twelve breaks. If one works, then you know the algorithm. If not, you don't care; you know it's one you cannot break, so details are not important. Doing this is only at worst 12 times harder than breaking a single known cipher. If some of your 12 breaks are easy, then total effort is much less than 12 times the hardest cipher. When we're talking about 2^40 steps to break a laughably weak cipher and > 2^100 for a good one, making it 12, or 1000, times harder is not a very interesting difference.
If it's just found on a disk in a garbage dump with no connections to anyone, it's a bit tougher.
Then you've no reason to think it is important enough to be worth breaking. You can still try.
But every algorithm has some statistical signature
No. Any good algorithm should produce output that looks /exactly/ like random noise, hence they should all look like each other. This may not be precisely true, but all decent algorithms will look random enough to make distinguishing quite difficult.
and if you've got enough cipher text you can compare that signature with known algorithms to home in on fewer choices.
I'm not sure having the plaintext helps much more, but you could use random keys to create several ciphertexts with known algorithms and compare the statistics just to see if they compare better.
It's definitly challenging :-)
On Thu, 11 Jul 2002, Sandy Harris wrote:
No. Any good algorithm should produce output that looks /exactly/ like random noise, hence they should all look like each other.
Wrong, not all RNG's have the same statistical output. There is -nothing- in the requirement for a RNG that requires it (radiation sources are not equiprobable for example, they're much more 'zero' than 'one'). There may be boundary conditions on crypto applications that require equiprobable distributions with respect to characters or strings (that 'k' thing again, see Knuth). But that doesn't apply to -all- RNG's or their applications by a long shot. Also, 'random noise' is redundent. 'Noise' is by -definition- random, otherwise it wouldn't be noise, it would have a correlation factor, once you found it you could remove the noise (assuming of course its computationaly tractible). -- ____________________________________________________________________ When I die, I would like to be born again as me. Hugh Hefner ravage@ssz.com www.ssz.com jchoate@open-forge.org www.open-forge.org --------------------------------------------------------------------
hi, eer..I think we need a defenition of an Rng & Prng that every 1 should agree on. would this help? RNG & PRNG ---------------- 1:>A RNG has an infinite period where as a PRNG has a defenite period after which the sequence will repeat. Atmospheric noise,Radiation decay are examples of RNG's.(Difference) 2:>An RNG & PRNG should pass a series of radomness tests. (Similarity) 3:>For the same set of input parameters,a RNG always give a different output. A PRNG always gives the same set of outputs for the same input parameters (Difference) would any 1 also like 2 review http://www.ircsuper.net/~neo/prng.html thanx. Regards Data. --- Jim Choate <ravage@einstein.ssz.com> wrote:
On Thu, 11 Jul 2002, Sandy Harris wrote:
No. Any good algorithm should produce output that looks /exactly/ like random noise, hence they should all look like each other.
Wrong, not all RNG's have the same statistical output. There is -nothing- in the requirement for a RNG that requires it (radiation sources are not equiprobable for example, they're much more 'zero' than 'one'). There may be boundary conditions on crypto applications that require equiprobable distributions with respect to characters or strings (that 'k' thing again, see Knuth). But that doesn't apply to -all- RNG's or their applications by a long shot.
Also, 'random noise' is redundent. 'Noise' is by -definition- random, otherwise it wouldn't be noise, it would have a correlation factor, once you found it you could remove the noise (assuming of course its computationaly tractible).
--
____________________________________________________________________
When I die, I would like to be born again as me.
Hugh Hefner ravage@ssz.com www.ssz.com jchoate@open-forge.org www.open-forge.org
--------------------------------------------------------------------
__________________________________________________ Do You Yahoo!? Yahoo! Autos - Get free new car price quotes http://autos.yahoo.com
A RNG is a character or string generator whose generation algorithm prevents prediction of the next output if one knows all the previous outputs and the algorithm. In other words if you know everything there is to know about the generator your odds of predicting the next output state are even - pure luck - 'Fair'. A PRNG is one that fails the RNG test. Read Knuth, you should also check out, Exploring Randomness G.J. Chaitin ISBN 1-85233-417-7 Has some interesting insite on randomness, some of his propositions are not exactly same old same old. Interesting read. On Sat, 13 Jul 2002, gfgs pedo wrote:
hi,
eer..I think we need a defenition of an Rng & Prng that every 1 should agree on.
would this help?
RNG & PRNG ----------------
1:>A RNG has an infinite period where as a PRNG has a defenite period after which the sequence will repeat. Atmospheric noise,Radiation decay are examples of RNG's.(Difference)
2:>An RNG & PRNG should pass a series of radomness tests. (Similarity)
3:>For the same set of input parameters,a RNG always give a different output. A PRNG always gives the same set of outputs for the same input parameters (Difference)
would any 1 also like 2 review
http://www.ircsuper.net/~neo/prng.html thanx.
Regards Data.
-- ____________________________________________________________________ When I die, I would like to be born again as me. Hugh Hefner ravage@ssz.com www.ssz.com jchoate@open-forge.org www.open-forge.org --------------------------------------------------------------------
hi, thanx Mr Jim. Data. __________________________________________________ Do You Yahoo!? Yahoo! Autos - Get free new car price quotes http://autos.yahoo.com
On Saturday, July 13, 2002, at 09:48 AM, gfgs pedo wrote:
that every 1 should agree on.
would any 1 also like 2 review
For starters, why don't you start writing in standard English? Even if English is not your first or second language, using such "cutisms" as "u" for "you" and "any 1" for "anyone" is much more misleading than using the standard, defined words. We mostly get rid of Choate's rants, we get rid of nearly all of "mattd" spews, but now we have "gfs pedo" as our new nutcase. Some sort of conservation of strangeness, I guess. Or, in your non-Earth language: u ask more quest shuns than any 1 kneads too..i peep u r a troll. --Tim May
On Sun, 14 Jul 2002, Tim May wrote:
For starters, why don't you start writing in standard English?
Even if English is not your first or second language, using such "cutisms" as "u" for "you" and "any 1" for "anyone" is much more misleading than using the standard, defined words.
Get up on the wrong side of bed today Tim? Must have smacked your nose pretty good to get that bent out of shape for something that trivial.
We mostly get rid of Choate's rants, we get rid of nearly all of "mattd" spews, but now we have "gfs pedo" as our new nutcase. Some sort of conservation of strangeness, I guess.
give the kid a break. He's trying to learn something, and you're being unpleasant about it may simply make him try to piss you off. I know that's what my kids to for me :-)
Or, in your non-Earth language:
u ask more quest shuns than any 1 kneads too..i peep u r a troll.
Not quite as good a third grader, but not bad Tim. If you actually were a soccer mom you might have a better attitude about teaching nettequite. But you just drive like one. Patience, persistence, truth, Dr. mike
On Thu, 11 Jul 2002, Sandy Harris wrote:
Doing this is only at worst 12 times harder than breaking a single known cipher. If some of your 12 breaks are easy, then total effort is much less than 12 times the hardest cipher. When we're talking about 2^40 steps to break a laughably weak cipher and > 2^100 for a good one, making it 12, or 1000, times harder is not a very interesting difference.
Yup.
No. Any good algorithm should produce output that looks /exactly/ like random noise, hence they should all look like each other.
This may not be precisely true, but all decent algorithms will look random enough to make distinguishing quite difficult.
At the binary level with no headers, "good" algorithms should definitly look alike. There's always some data left by the implementation tho, so in practice you've got some foothold. But I'm willing to bet that encrypting megabytes of 0x00000's with the same keys on different ciphers whould show some kind of statistical foothold. "looking" like random and "being" random aren't the same. Especially if you've got an army of mathematicians to keep busy :-) But since I've never actually done it, I don't know how big that army needs to be. Patience, persistence, truth, Dr. mike
hi, thanx for the replies. one doubt escpecially on this.
But every algorithm has some statistical signature and if you've got enough cipher text you can compare that signature with known algorithms to home in on fewer choices.
can u pls explain how they have statistical signatures,pls- may be using SPN's, i have tried ANSI X9.17 key generation with GOST-it did have a negligably small skew-it makes me wonder what statistical signature they have.The negligable skew is a weakness but not high enough to compramise the security of the key used from the ANSI x9.17 key gen method. pls explain. thank u veru much. Regards Data. --- Mike Rosing <eresrch@eskimo.com> wrote:
On Thu, 11 Jul 2002, gfgs pedo wrote:
suppose a cryptanalysis only has encrypted data-how is going 2 know which is the encrytion algorithm used 2 encrypt the data ,so that he can effeciently cryptanalyse if
1:>he has large amount of cipher text only 2:>has large amount of plain text and corresponding cipher text.
There r so many encryption algorithms,how does he know which algorithm was used?
Depends on how they got the source. They may know it's one of 5 possible choices because of the person who sent (or received) it. If it's just found on a disk in a garbage dump with no connections to anyone, it's a bit tougher. But every algorithm has some statistical signature and if you've got enough cipher text you can compare that signature with known algorithms to home in on fewer choices.
I'm not sure having the plaintext helps much more, but you could use random keys to create several ciphertexts with known algorithms and compare the statistics just to see if they compare better.
It's definitly challenging :-)
Patience, persistence, truth, Dr. mike
__________________________________________________ Do You Yahoo!? Yahoo! Autos - Get free new car price quotes http://autos.yahoo.com
On Sat, 13 Jul 2002, gfgs pedo wrote:
can u pls explain how they have statistical signatures,pls-
may be using SPN's, i have tried ANSI X9.17 key generation with GOST-it did have a negligably small skew-it makes me wonder what statistical signature they have.The negligable skew is a weakness but not high enough to compramise the security of the key used from the ANSI x9.17 key gen method. pls explain. thank u veru much.
You're on the right track. Take several encryption algorithms of your choice, then use a fixed IV, and the same sets of keys, and encrypt blocks of 0's. For each algorithm, compute several sets of staticstics (a la NIST or DIEHARD). With 100 blocks of 10 Megabytes (100 different keys) you should see some interesting differences. Remember, your question originally was "how can you tell which algorithm", not "how do you find the key". Let us know what you find out :-) Patience, persistence, truth, Dr. mike
Perhaps a simpler example. Let's look at a 'fair' coin and what that means in the real world. A normal coin (or any nDx for that matter [1]) for short sequences is random. In other words if you record a game sequence and then replay the game the die sequence won't have any statistical correlation. Knowing what happened last time won't help you this time, the 'window of opportunity' with respect to statistical bias isn't large enough, so the game is 'fair'. But!, if you throw that coin once a second for a billion years you will find that -no- coin is really -fair-. This goes back to k-sequences and Knuth. Go back and then start throwing it again, and if your sequence is long enough you can use this known bias from the first experiment to increase your percentage of 'hits' in the second sequence. In other words you can now prove experimentaly the coin isn't fair and what that bias is. This is related to 'Hypothesis Testing'. It's rather strange, but I happen to be rereading a book, "The Mathematical Sciences: A Collection of Essays" (LoC# 69-12750) put out by some group called COSRIMS in about 1969. I remember the book because somebody gave it to me (I was about 9 or 10 at the time) to read, and it has an insane bright yellow cover. I recently came across it again in a used bookstore for $10 so I bought it. It's basically a bunch of chapters on various issues of math research with the intent of focusing high school and undergrads to pursue mathematical careers by giving examples of what you might be working on. The chapter "Statistical Inference" (by J. Kiefer) uses an example of a coin and a 3-run sequence to determine the actual bias of the coin (the example is very simple, the coin is very biased). You should be able to still find the book in public libraries and college libraries. I'm sure more modern texts on hypothesis testing will be just as relevant. The vast majority of RNG's that we use are really PRNG's, we just don't collect enough data on them to be able to demonstrate that. Or the sequence of interest is so short we dont' care. [1] A coin is a 1D2, two coins would be 2D2, for example. Who said wargaming was worthless ;) On Sat, 13 Jul 2002, Mike Rosing wrote:
On Sat, 13 Jul 2002, gfgs pedo wrote:
can u pls explain how they have statistical signatures,pls-
may be using SPN's, i have tried ANSI X9.17 key generation with GOST-it did have a negligably small skew-it makes me wonder what statistical signature they have.The negligable skew is a weakness but not high enough to compramise the security of the key used from the ANSI x9.17 key gen method. pls explain. thank u veru much.
You're on the right track. Take several encryption algorithms of your choice, then use a fixed IV, and the same sets of keys, and encrypt blocks of 0's. For each algorithm, compute several sets of staticstics (a la NIST or DIEHARD). With 100 blocks of 10 Megabytes (100 different keys) you should see some interesting differences.
Remember, your question originally was "how can you tell which algorithm", not "how do you find the key". Let us know what you find out :-)
Patience, persistence, truth, Dr. mike
-- ____________________________________________________________________ When I die, I would like to be born again as me. Hugh Hefner ravage@ssz.com www.ssz.com jchoate@open-forge.org www.open-forge.org --------------------------------------------------------------------
hi, Does a fair coin exist in real world? Like as according to Allan Turing-an event is defined by set of certain parameters governing the event at that instant. by redoing the same experiment-do we always have the same set of parameters that previously defined the coin. it is said that atmospheric noise is random but how can we say for sure. what if the parameters giverning atmospheric noise vary frm time 2 time. may be at a later stage an additional parameter may govern atmospheric noise or may be a parameter may be removed,we cant say that for sure. like the earth & moon attract each other,no 1 knows why,it is a physical observation & based on it we make a matahmetical model,what if one day-2 bodies with mass start repelling each other? then an extra parameter would govern it & we will have 2 change the mathametical mode considering this additional parameter. so can we say atmospheric noise is random or a coin flipping is random-only because it passes die hard test or other randomness tests-which is an indicator of randomness with the current defenition of parameters in determing randomness? is there truly random or that we can say with certain degre of confidence that they are nearly random as all current evidence poits so. Regards Data. --- Jim Choate <ravage@einstein.ssz.com> wrote:
Perhaps a simpler example. Let's look at a 'fair' coin and what that means in the real world.
A normal coin (or any nDx for that matter [1]) for short sequences is random. In other words if you record a game sequence and then replay the game the die sequence won't have any statistical correlation. Knowing what happened last time won't help you this time, the 'window of opportunity' with respect to statistical bias isn't large enough, so the game is 'fair'.
But!, if you throw that coin once a second for a billion years you will find that -no- coin is really -fair-. This goes back to k-sequences and Knuth. Go back and then start throwing it again, and if your sequence is long enough you can use this known bias from the first experiment to increase your percentage of 'hits' in the second sequence. In other words you can now prove experimentaly the coin isn't fair and what that bias is.
This is related to 'Hypothesis Testing'. It's rather strange, but I happen to be rereading a book, "The Mathematical Sciences: A Collection of Essays" (LoC# 69-12750) put out by some group called COSRIMS in about 1969. I remember the book because somebody gave it to me (I was about 9 or 10 at the time) to read, and it has an insane bright yellow cover. I recently came across it again in a used bookstore for $10 so I bought it. It's basically a bunch of chapters on various issues of math research with the intent of focusing high school and undergrads to pursue mathematical careers by giving examples of what you might be working on. The chapter "Statistical Inference" (by J. Kiefer) uses an example of a coin and a 3-run sequence to determine the actual bias of the coin (the example is very simple, the coin is very biased). You should be able to still find the book in public libraries and college libraries. I'm sure more modern texts on hypothesis testing will be just as relevant.
The vast majority of RNG's that we use are really PRNG's, we just don't collect enough data on them to be able to demonstrate that. Or the sequence of interest is so short we dont' care.
[1] A coin is a 1D2, two coins would be 2D2, for example. Who said wargaming was worthless ;)
On Sat, 13 Jul 2002, Mike Rosing wrote:
On Sat, 13 Jul 2002, gfgs pedo wrote:
can u pls explain how they have statistical signatures,pls-
may be using SPN's, i have tried ANSI X9.17 key generation with GOST-it did have a negligably small skew-it makes me wonder what statistical signature they have.The negligable skew is a weakness but not high enough to compramise the security of the key used from the ANSI x9.17 key gen method. pls explain. thank u veru much.
You're on the right track. Take several encryption algorithms of your choice, then use a fixed IV, and the same sets of keys, and encrypt blocks of 0's. For each algorithm, compute several sets of staticstics (a la NIST or DIEHARD). With 100 blocks of 10 Megabytes (100 different keys) you should see some interesting differences.
Remember, your question originally was "how can you tell which algorithm", not "how do you find the key". Let us know what you find out :-)
Patience, persistence, truth, Dr. mike
--
____________________________________________________________________
When I die, I would like to be born again as me.
Hugh Hefner ravage@ssz.com www.ssz.com jchoate@open-forge.org www.open-forge.org
--------------------------------------------------------------------
__________________________________________________ Do You Yahoo!? Yahoo! Autos - Get free new car price quotes http://autos.yahoo.com
On Sunday, July 14, 2002, at 05:45 AM, gfgs pedo wrote:
hi,
Does a fair coin exist in real world?
Like as according to Allan Turing-an event is defined by set of certain parameters governing the event at that instant.
by redoing the same experiment-do we always have the same set of parameters that previously defined the coin.
No, certainly not. We have limited measurement precision, currently something like 12 decimal places for most mass/gravity/thing parameters. Even our theory of QED is "only" good to about 23 decimal places, less in any real world laboratory. The result? The errors will come "marching in" from beyond, resulting in variations in coin tosses, billiard table evolutions, etc. Cf. a large body of (mostly old) stuff on this. Google is your friend.
it is said that atmospheric noise is random but how can we say for sure.
No, no sequence (of bits, symbols, pressures, etc.) can ever be "proved" to be "random." Cf. Chaitin, Kolmogorov, or more popular accounts in, say, Rucker's "Mind Tools." Also covered in archives of this list. You ask a lot of questions. I encourage you to find some of the basic books, use Google, and to think deeply about questions before phrasing them here. --Tim May
On Sun, 14 Jul 2002, Tim May wrote:
On Sunday, July 14, 2002, at 05:45 AM, gfgs pedo wrote:
You ask a lot of questions. I encourage you to find some of the basic books, use Google, and to think deeply about questions before phrasing them here.
Ignore Tim. Keep asking your questions. -- ____________________________________________________________________ When I die, I would like to be born again as me. Hugh Hefner ravage@ssz.com www.ssz.com jchoate@open-forge.org www.open-forge.org --------------------------------------------------------------------
On Sun, 14 Jul 2002, gfgs pedo wrote:
hi,
Does a fair coin exist in real world?
Depends on what you mean by fair and how long you have to throw it to get a usable string. If you're using it to play a game over the span of a few minutes to a few days, probably most coins are 'fair'. If you need to use it over a very long period (very few current applications I'll grant you ) then no coin is 'fair'. Note that this bias of the coin isn't a function of air resistance, it would still show the bias in space; though it might be a bit different in atmosphere than in space - the faces are not the same. What makes the difference is the distribution of mass and where the resultant CG is located. Any two coins will have a slightly different CG location within the volume of the coin.
Like as according to Allan Turing-an event is defined by set of certain parameters governing the event at that instant.
by redoing the same experiment-do we always have the same set of parameters that previously defined the coin.
See 2nd Law & Uncertainty Principle.
it is said that atmospheric noise is random but how can we say for sure.
A thunderstorm is not random. By 'atomospheric noise' you're making refrence to the individual particles that strike your eardrum (seashore in a shell effect). Not quite the same thing, your wording is too vague to be meaningfull.
so can we say atmospheric noise is random or a coin flipping is random-only because it passes die hard test or other randomness tests-which is an indicator of randomness with the current defenition of parameters in determing randomness?
Actually these tests are not perfect and are used on 'short' strings. A string from a supposad RNG that's only a few million billion gigabytes long isn't a very long string. It's also probably not boing to be used for very long at each invocation, so the discrepency is below the error. The point is these tests are statistical. They say, only with a certain degree of confidence (in other words "I could be wrong") that the string looks 'random'.
is there truly random or that we can say with certain degre of confidence that they are nearly random as all current evidence poits so.
Several physical systems, radioactive decay and magnetic pendulums being my two favorite examples, are random by definition. If they aren't then the world would be a lot different place than it is. -- ____________________________________________________________________ When I die, I would like to be born again as me. Hugh Hefner ravage@ssz.com www.ssz.com jchoate@open-forge.org www.open-forge.org --------------------------------------------------------------------
i meant cryptanalyst-hope i spelled that rite :-) Data. __________________________________________________ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com
participants (6)
-
gfgs pedo -
Jim Choate -
Mike Rosing -
Ryan Sorensen -
Sandy Harris -
Tim May