Many commenters are claiming "it is always possible to reverse-engineer a program!," using such reasons as "you can always watch the processor perform the instructions and eventually figure it out."
Let me tell you, as a cryptographer, that these claims are false. The recent field of program obfuscation gives surprisingly strong ways to prevent reverse-engineering, in a very rigorous and strong way.
Not every program can be obfuscated (this has been proven). However, programs that fit a certain template (like: "check if the input string matches the user's password") can be obfuscated. What this means is that you can give the program's entire code to the adversary -- he can run it on his own computer (no DRM required) on whatever inputs he likes, alter it, stretch it, twist it, whatever. After all this he still will not be able to guess the password, any more than if he had some mathematically-perfect black-box that truthfully answered the question: "is [X] the password?" (Actually the definition is even stronger than this, but that's the gist of it.)
Yes, this seems extremely hard to do -- after all, the adversary has complete and total power over the code that is running. Yet it can be done, rigorously and provably, if you're willing to believe that there are some number-theory problems out there (like RSA) that are hard to solve.
For the work described in the article, it sounds like the "black-box" does something like the following: if your input string contains some "watch words," then the output is the same as the input, but encrypted under the government's key. If your input string is "benign," then the output is just "THIS WAS A BENIGN INPUT", encrypted in the government's key -- i.e., it ignores any benign input and replaces it with a placeholder. By running the obfuscated program and looking at the output, you can't tell if the input was flagged or not. Even while watching the program run, you can't tell if the program is flagging the input or not (or learn anything about the government's key). When the government collects the output and decrypts it, it only sees the flagged inputs, as the rest have been ignored.
As I've said, none of this depends on the program requiring any DRM or TPM or any other specialized hardware. It only relies on the mathematics.
The problem with proofs such as this is that they assume broad axioms that in reality might not be true in the hardware.
Nah, side-channels have nothing to do with it. Even though the article doesn't mention it, the authors are doing rigorous program obfuscation. In the security model for this problem, the adversary gets access to the code and can do whatever he wants to it: run it (on whatever architecture he pleases) on different inputs, insert or delete instructions, slow it down, speed it up, whatever. The definitions are totally hardware-independent. With all this power, the adversary still cannot learn anything about what the program does, other than what he could learn by having "black-box" access to whatever function the program computes (i.e., we allow him to pick inputs and see the correct outputs).
The only catch is the proofs of security usually make some non-standard assumptions about number-theory problems (think RSA, but much weirder). These assumptions are independent of computer architecture, and only relate to whether certain abstract mathematical problems are easy or hard to solve.
Until such time, I call bollocks and I refuse to believe an "impossible to reverse-engineer" piece of code ever exists.
They're solving the problem of program obfuscation for a certain class of programs. It's known that obfuscation is impossible in general, but for certain classes of programs (like "check if the input text equals a specific string") it can be done. (If you're willing to believe some new, non-standard number theoretic assumptions that seem plausible.)
Yes, it is tough to prove that the obfuscator really works correctly. However, there are very good, rigorous definitions of what obfuscation means, and these definitions are independent of computer architecture/tracing the code execution/whatever. The definitions are very strong, and if you can rigorously prove that your obfuscation scheme satisfies them, then you really do have strong assurances that the code can't be reverse-engineered.
You are referring no doubt to quantum cryptography.
I was not referring to quantum cryptography. I was referring, just as an example, to lattice-based cryptography, which is completely classical. And yet we don't know how to break it using quantum computers.
To make a long story short, the number of steps to do factoring on a quantum computer is approximately the square root of the number of steps required on a classical computer.
It's must better than that: after all, if what you say is true, then factoring would go from subexponential-time (on a classical computer) to... still subexponential-time (on a quantum computer).
The reality is that there is no general "speedup factor" that quantum always gives. However, for factoring, it takes us from about 2^(cube root(n)) down to polynomial(n). That's neither an exponential speedup nor a square-root speedup, but it's "closer" to an exponential speedup and is very significant.
This breakthrough completely renders useles the concept of the so-called one-way function.
Settle down, and don't believe the hype.
So far, we don't know of any efficient quantum algorithms for solving the main problems on lattices. One-way functions and encryption schemes can be based on these lattice problems, too.
There is no general result that says "quantum computers can invert all functions." One-way functions are still believed to exist, even in the face of quantum computing.
To even find a polynomial time algorithm is to prove that P=NP
As another poster has said, and as I wrote below, factoring is very unlikely to be NP-hard. Therefore finding a poly-time factoring algorithm would not prove that P=NP. It very well could be the case that factoring is easy, and P != NP.
Instruction in math, engineering, and sciences is abysmal. At least, according to the author.
I had some phenomenal instructors at my own Smartypants U, but there were some bad ones, too. And even the best of them sometimes failed to communicate the concepts well. Ideally there would be plenty of instructors who can really capture the students' imagination and communicate the joy and beauty of the ideas underlying mathematics, computer science, and engineering. Lord knows that these fields have no shortage of beautiful and powerful ideas.
However, it seems to be true that teaching is undervalued in the typical faculty job. There aren't many reliable metrics taken, and of those that are, there seems to be little accountability for poor performance. For research output, on the other hand, judgement is precise and swift. Under such a regime, how can one blame a professor for focusing on his research? Certainly there are many cases of faculty who are brilliant researchers and teachers, but in the more marginal cases, it's typically the teaching that gets the short end of the stick.
For the long-term health of mathematics and science, I think more focus must be on inspiring students within those fields, and that requires uniformly good teaching and advising. How we get there, I have no idea.
Your suggestion is just pushing the dirt under the carpet, though.
If you're going to have a large internal state, you might as well use the entire state as the output. To do otherwise is to open yourself to attacks on the "state -> output" compression function, which may be the weakest link (and probably is, given the short output). And if you're going to pay the computational cost to maintain so much state, it's a waste to throw it all away by choosing a weaker (shorter) output length.
The newer hashes, such as Whirlpool, do not have this problem.
I don't think you are right about this. Although it does not exactly use the Merkle-Damgard structure, Whirlpool is still iterative. If you find a collision between two short messages of the same length, then Whirlpool's internal state collides. From there you can extend both messages with the same string, maintaining the same internal state, padding and byte counts be damned.
Any iterative hash is going to have this issue. It really seems like there is nothing you can do to mitigate it, short of a massive design change (which would affect efficiency).
The known attacks produce MD5 collisions with the same length!!
Padding and byte-counts and so forth are a red herring and provide no mitigation. The basic colliding messages are all exactly 1 block long. From there you can do message-extension. Any hash function with this so-called Merkle-Damgard structure is vulnerable to length extension attacks. And yes, this is true of Whirlpool too (in contrast to another poster's assertion): if you find two messages with the same hash and the same length, you can extend them both with the same string and continue to get collisions.
All I'm saying is that the phrase "encrypted with the private key" is, in general, nonsensical. Ditto for "decrypted with the public key."
For particular schemes, the keys might be interchangeable. But the original poster asserted this about public-key crypto in general, which is a widely-held misconception that ought to be fixed.
Also, even with RSA you don't get authenticity by simply raising the message to the private key; there are easy forgery attacks for that. So it's not accurate to say that RSA signatures are simply "encrypting the message with the private key."
As far as I am aware, predicting a md5 collision has not been done.
I don't know what you mean by "predicting," but yes, concrete MD5 collisions exist. I.e., two files, with different contents, that have the same MD5 hash (and the same size, to boot). They are printed in the paper that first announced the MD5 break. Further work has shown that additional collisions can be generated at will in minutes on a common laptop computer.
Any data encrypted with a private key can be decrypted only with the public key.
This isn't true, and doesn't even make any sense.
Yes, for the particular plain-vanilla RSA scheme, the private key and public key are more-or-less "interchangeable."
For other public-key encryption schemes (e.g., ElGamal or Cramer-Shoup or Rabin or...), the keys are not interchangeable; they're completely different mathematical objects. You can't decrypt anything with the public key. You can't encrypt anything with the private key.
Further, plain-vanilla RSA is not, and should not be used for encryption or authentication. Extra padding, hashing, and other operations are needed to make it secure against realistic attacks. Therefore, public and private keys are not interchangeable for any kind of real-world crypto based on RSA.
Further, Lynn himself admitted that the vulnerability had already been patched by a Cisco update.
One specific buffer overflow vulnerability was patched. But Lynn's presentation was a general approach to exploit any buffer overflow, with dire consequences. There is likely more exploitable code inside those routers; it's just a matter of time before some is found. At that point Lynn's attack could be executed.
Monzy and MC Plus+ are two computer science geekstas who started a rap feud with each other, ala Eminem and Cannabis or whatever... Monzy's "Drama in the PhD" is hilarious!
I'm sure I'm not the first to have thought of this idea, but it seems to me that the length of copyright is an unstable equilibrium. Here's why:
For a given term length, a creator can anticipate how much revenue he is likely to earn before his copyright expires. This dictates the amount of investment he can afford to put into his work. If the term is long enough to allow him large profits, he gains wealth and influence to have the term extended. Longer terms lead to larger investments in future works, greater profits, more influence, and still longer terms. The effect is bigger and bigger budgets for works.
Conversely, if the length of the term is too low, investment in works will be low, and fewer works will be created, especially those that would require large budgets. Copyright terms stay low, or even decrease due to lack of lobbying powers.
Copyright law should aim to hit the "sweet-spot" where things stay stable. Of course, this is impossible: minor variations in the economics of production will push the pendulum to one extreme or another. Decreasing publication costs, for example, would increase profits and start the vicious cycle.
Of course, all of this assumes a very money-driven view of whether and how works are created, i.e. that works are created primarily to make money. If investment in a work is not tied to its potential monetary returns (that stem directly from a copyright monopoly), we'd still see works being created. I think Open Source is a good example of this phenomenon. Some people do it for the love; large companies do it to demonstrate expertise and cultivate service contracts.
In short, wherever the economic model allows decent profits in the absence of a government-enforced monopoly, copyright and similar monopolies should be heavily restricted. This seems to be the case for software and other intangibles. However, when the only method to recoup investments is through monopoly (and this claim should be heavily contested), copyright and patents, etc. are a bit more reasonable. Perhaps pharmaceuticals would fall into this category (at least today).
Enumeration is not the most efficient way to solve, e.g., SAT, which is NP-complete.
For example, if there is a certain clause (x1 OR x2 OR x3) in a SAT instance, I have no need to "try" any assignment that sets x1=x2=x3=false. There are exponentially many such assignments; I can skip them all.
This algorithm remains exponential-time, but it skips over one-eighth of all assignments.
Slashdot Mirror
Many commenters are claiming "it is always possible to reverse-engineer a program!," using such reasons as "you can always watch the processor perform the instructions and eventually figure it out."
Let me tell you, as a cryptographer, that these claims are false. The recent field of program obfuscation gives surprisingly strong ways to prevent reverse-engineering, in a very rigorous and strong way.
Not every program can be obfuscated (this has been proven). However, programs that fit a certain template (like: "check if the input string matches the user's password") can be obfuscated. What this means is that you can give the program's entire code to the adversary -- he can run it on his own computer (no DRM required) on whatever inputs he likes, alter it, stretch it, twist it, whatever. After all this he still will not be able to guess the password, any more than if he had some mathematically-perfect black-box that truthfully answered the question: "is [X] the password?" (Actually the definition is even stronger than this, but that's the gist of it.)
Yes, this seems extremely hard to do -- after all, the adversary has complete and total power over the code that is running. Yet it can be done, rigorously and provably, if you're willing to believe that there are some number-theory problems out there (like RSA) that are hard to solve.
For the work described in the article, it sounds like the "black-box" does something like the following: if your input string contains some "watch words," then the output is the same as the input, but encrypted under the government's key. If your input string is "benign," then the output is just "THIS WAS A BENIGN INPUT", encrypted in the government's key -- i.e., it ignores any benign input and replaces it with a placeholder. By running the obfuscated program and looking at the output, you can't tell if the input was flagged or not. Even while watching the program run, you can't tell if the program is flagging the input or not (or learn anything about the government's key). When the government collects the output and decrypts it, it only sees the flagged inputs, as the rest have been ignored.
As I've said, none of this depends on the program requiring any DRM or TPM or any other specialized hardware. It only relies on the mathematics.
The problem with proofs such as this is that they assume broad axioms that in reality might not be true in the hardware.
Nah, side-channels have nothing to do with it. Even though the article doesn't mention it, the authors are doing rigorous program obfuscation. In the security model for this problem, the adversary gets access to the code and can do whatever he wants to it: run it (on whatever architecture he pleases) on different inputs, insert or delete instructions, slow it down, speed it up, whatever. The definitions are totally hardware-independent. With all this power, the adversary still cannot learn anything about what the program does, other than what he could learn by having "black-box" access to whatever function the program computes (i.e., we allow him to pick inputs and see the correct outputs).
The only catch is the proofs of security usually make some non-standard assumptions about number-theory problems (think RSA, but much weirder). These assumptions are independent of computer architecture, and only relate to whether certain abstract mathematical problems are easy or hard to solve.
Until such time, I call bollocks and I refuse to believe an "impossible to reverse-engineer" piece of code ever exists.
They're solving the problem of program obfuscation for a certain class of programs. It's known that obfuscation is impossible in general, but for certain classes of programs (like "check if the input text equals a specific string") it can be done. (If you're willing to believe some new, non-standard number theoretic assumptions that seem plausible.)
Yes, it is tough to prove that the obfuscator really works correctly. However, there are very good, rigorous definitions of what obfuscation means, and these definitions are independent of computer architecture/tracing the code execution/whatever. The definitions are very strong, and if you can rigorously prove that your obfuscation scheme satisfies them, then you really do have strong assurances that the code can't be reverse-engineered.
Whoops, wrong sub-thread. Please interpret parent in the proper context :).
You are referring no doubt to quantum cryptography.
I was not referring to quantum cryptography. I was referring, just as an example, to lattice-based cryptography, which is completely classical. And yet we don't know how to break it using quantum computers.
You are correct that the grandparent is nonsense.
... still subexponential-time (on a quantum computer).
However, QC is faster than you state:
To make a long story short, the number of steps to do factoring on a quantum computer is approximately the square root of the number of steps required on a classical computer.
It's must better than that: after all, if what you say is true, then factoring would go from subexponential-time (on a classical computer) to
The reality is that there is no general "speedup factor" that quantum always gives. However, for factoring, it takes us from about 2^(cube root(n)) down to polynomial(n). That's neither an exponential speedup nor a square-root speedup, but it's "closer" to an exponential speedup and is very significant.
This breakthrough completely renders useles the concept of the so-called one-way function.
Settle down, and don't believe the hype.
So far, we don't know of any efficient quantum algorithms for solving the main problems on lattices. One-way functions and encryption schemes can be based on these lattice problems, too.
There is no general result that says "quantum computers can invert all functions." One-way functions are still believed to exist, even in the face of quantum computing.
To even find a polynomial time algorithm is to prove that P=NP
As another poster has said, and as I wrote below, factoring is very unlikely to be NP-hard. Therefore finding a poly-time factoring algorithm would not prove that P=NP. It very well could be the case that factoring is easy, and P != NP.
What did I write that is inconsistent with the wikipedia entry?
"Integer factorization is widely suspected to be outside both of those classes [NP-complete and co-NP-complete]."
Just because a problem is outside P, doesn't mean it's NP-hard. Which is exactly what I said to start with.
And will not be, unless P=NP, or we use some form of new computers.
Factoring is almost certainly not NP-hard. It could very well be that P != NP, and yet factoring is easy.
The "correct" way is for the paper vote itself to be the official ballot -- not just a backup in case of a recount.
Instruction in math, engineering, and sciences is abysmal. At least, according to the author.
I had some phenomenal instructors at my own Smartypants U, but there were some bad ones, too. And even the best of them sometimes failed to communicate the concepts well. Ideally there would be plenty of instructors who can really capture the students' imagination and communicate the joy and beauty of the ideas underlying mathematics, computer science, and engineering. Lord knows that these fields have no shortage of beautiful and powerful ideas.
However, it seems to be true that teaching is undervalued in the typical faculty job. There aren't many reliable metrics taken, and of those that are, there seems to be little accountability for poor performance. For research output, on the other hand, judgement is precise and swift. Under such a regime, how can one blame a professor for focusing on his research? Certainly there are many cases of faculty who are brilliant researchers and teachers, but in the more marginal cases, it's typically the teaching that gets the short end of the stick.
For the long-term health of mathematics and science, I think more focus must be on inspiring students within those fields, and that requires uniformly good teaching and advising. How we get there, I have no idea.
Your suggestion is just pushing the dirt under the carpet, though.
If you're going to have a large internal state, you might as well use the entire state as the output. To do otherwise is to open yourself to attacks on the "state -> output" compression function, which may be the weakest link (and probably is, given the short output). And if you're going to pay the computational cost to maintain so much state, it's a waste to throw it all away by choosing a weaker (shorter) output length.
The newer hashes, such as Whirlpool, do not have this problem.
I don't think you are right about this. Although it does not exactly use the Merkle-Damgard structure, Whirlpool is still iterative. If you find a collision between two short messages of the same length, then Whirlpool's internal state collides. From there you can extend both messages with the same string, maintaining the same internal state, padding and byte counts be damned.
Any iterative hash is going to have this issue. It really seems like there is nothing you can do to mitigate it, short of a massive design change (which would affect efficiency).
The known attacks produce MD5 collisions with the same length!!
Padding and byte-counts and so forth are a red herring and provide no mitigation. The basic colliding messages are all exactly 1 block long. From there you can do message-extension. Any hash function with this so-called Merkle-Damgard structure is vulnerable to length extension attacks. And yes, this is true of Whirlpool too (in contrast to another poster's assertion): if you find two messages with the same hash and the same length, you can extend them both with the same string and continue to get collisions.
All I'm saying is that the phrase "encrypted with the private key" is, in general, nonsensical. Ditto for "decrypted with the public key."
For particular schemes, the keys might be interchangeable. But the original poster asserted this about public-key crypto in general, which is a widely-held misconception that ought to be fixed.
Also, even with RSA you don't get authenticity by simply raising the message to the private key; there are easy forgery attacks for that. So it's not accurate to say that RSA signatures are simply "encrypting the message with the private key."
The research lab is only concerned with animal dental hygiene. The mice just have really bad plaque.
As far as I am aware, predicting a md5 collision has not been done.
I don't know what you mean by "predicting," but yes, concrete MD5 collisions exist. I.e., two files, with different contents, that have the same MD5 hash (and the same size, to boot). They are printed in the paper that first announced the MD5 break. Further work has shown that additional collisions can be generated at will in minutes on a common laptop computer.
Any data encrypted with a private key can be decrypted only with the public key.
...), the keys are not interchangeable; they're completely different mathematical objects. You can't decrypt anything with the public key. You can't encrypt anything with the private key.
This isn't true, and doesn't even make any sense.
Yes, for the particular plain-vanilla RSA scheme, the private key and public key are more-or-less "interchangeable."
For other public-key encryption schemes (e.g., ElGamal or Cramer-Shoup or Rabin or
Further, plain-vanilla RSA is not, and should not be used for encryption or authentication. Extra padding, hashing, and other operations are needed to make it secure against realistic attacks. Therefore, public and private keys are not interchangeable for any kind of real-world crypto based on RSA.
They are hashing algorithms, a totally different beast.
Wait a minute, you don't sound sorry at all!
Further, Lynn himself admitted that the vulnerability had already been patched by a Cisco update.
One specific buffer overflow vulnerability was patched. But Lynn's presentation was a general approach to exploit any buffer overflow, with dire consequences. There is likely more exploitable code inside those routers; it's just a matter of time before some is found. At that point Lynn's attack could be executed.
Monzy and MC Plus+ are two computer science geekstas who started a rap feud with each other, ala Eminem and Cannabis or whatever... Monzy's "Drama in the PhD" is hilarious!
I'm sure I'm not the first to have thought of this idea, but it seems to me that the length of copyright is an unstable equilibrium. Here's why:
For a given term length, a creator can anticipate how much revenue he is likely to earn before his copyright expires. This dictates the amount of investment he can afford to put into his work. If the term is long enough to allow him large profits, he gains wealth and influence to have the term extended. Longer terms lead to larger investments in future works, greater profits, more influence, and still longer terms. The effect is bigger and bigger budgets for works.
Conversely, if the length of the term is too low, investment in works will be low, and fewer works will be created, especially those that would require large budgets. Copyright terms stay low, or even decrease due to lack of lobbying powers.
Copyright law should aim to hit the "sweet-spot" where things stay stable. Of course, this is impossible: minor variations in the economics of production will push the pendulum to one extreme or another. Decreasing publication costs, for example, would increase profits and start the vicious cycle.
Of course, all of this assumes a very money-driven view of whether and how works are created, i.e. that works are created primarily to make money. If investment in a work is not tied to its potential monetary returns (that stem directly from a copyright monopoly), we'd still see works being created. I think Open Source is a good example of this phenomenon. Some people do it for the love; large companies do it to demonstrate expertise and cultivate service contracts.
In short, wherever the economic model allows decent profits in the absence of a government-enforced monopoly, copyright and similar monopolies should be heavily restricted. This seems to be the case for software and other intangibles. However, when the only method to recoup investments is through monopoly (and this claim should be heavily contested), copyright and patents, etc. are a bit more reasonable. Perhaps pharmaceuticals would fall into this category (at least today).
Enumeration is not the most efficient way to solve, e.g., SAT, which is NP-complete.
For example, if there is a certain clause (x1 OR x2 OR x3) in a SAT instance, I have no need to "try" any assignment that sets x1=x2=x3=false. There are exponentially many such assignments; I can skip them all.
This algorithm remains exponential-time, but it skips over one-eighth of all assignments.