I am a professional research cryptographer. There are many misstatements in the comments so far (what else should one expect, it's Slashdot.....)
Here are some facts to fix the clutter:
1. Shor's algorithm works on quantum computers and can factor integers in polynomial time. This breaks all public-key systems that depend on the hardness of factoring, including RSA, Rabin, Paillier, and XTR.
2. A different version of Shor's algorithm also computes discrete logarithms (again, in poly time). This breaks all public-key systems that depend on the hardness of discrete log, over *any* cyclic group. This includes ElGamal, even over "exotic" groups like those associated with elliptic curves.
3. Nevertheless, factoring and discrete log are different beasts and are not known to be equivalent to each other. Still, Shor's algorithm (in different versions) solves them both.
4. Shor's algorithm does not yet break all known public-key cryptosystems. Systems based on lattices, for example, do not appear to be affected as of yet. These include Ajtai-Dwork and a couple systems by Regev. NTRU is based on lattices, but is based on some not-so-natural assumptions (i.e, the assumption that "NTRU is secure").
5. Public key encryption is (probably) *not* equivalent to trapdoor permutations (or even trapdoor one-way functions). TDPs are a much stronger notion and are not strictly needed to do secure public-key encryption. For example, ElGamal and lattice-based systems are not based on trapdoor primitives per se.
Shor's Algorithm, which solves an NP-whatever problem in (log n)^3 time, works because it draws computational power from another universe.
Whoah, whoah. Shor's Algorithm solves the factoring problem, which is almost certainly NOT NP-complete. (If it were, then NP would equal coNP, which would be almost as surprising as if NP equalled P.)
Solve any problem polynomially reducable to SAT/3-SAT
You have your reducibility direction mixed up: even really easy problems (like sorting, or outputting "2") are reducible to SAT. It's the hard problems that SAT reduces to.
Not that this matters, because quantum computing is very unlikely to be able to solve NP-complete problems. It does seem to help with very structured problems like factoring, though. No, factoring is (almost definitely) not NP-complete.
Further, show it being done in polynomial-time with respect to the problem size.
Polynomial-time is an asymptotic notion. It can't be verified for a particular problem size (or finite set of problem sizes). It is purely an analytical concept, not an experimental/testable one.
There are ways of encoding the watermarks that are resistant to such "collusive attacks." They allow the distributor to decode at least one of the original versions, even from a "noisy" version that resulted from a diff like you described. The techniques go by many names: collusion-secure fingerprints, fingerprinting codes, traceability codes... the concept is the same, though.
Whether these codes are actually implemented, I have no idea.
Functional languages conform to lambda calculus, which has been shown to be Turing equivalent, which means that any program that can be computed on a Turing machine can be solved using Lambda calculus.
And for this reason, checking correctness of code cannot be automated, for that would solve the Halting Problem.
Not that functional programming isn't great. You're just overselling it.
You are right; however, Shamir first observed that Reed-Solomon error correction also has nice secrecy properties. That is, even if you have one share less than the number required to reconstruct, you actually have no information about the secret at all. This can be a good thing if you are distributing your data among potentially untrustworthy servers.
Quite a few people are proposing a compromise trust model like ssh has, where the browser UI would change so as to warn you when you're about to encrypt to an unexpected public key.
This model has some good things going for it, but I don't see it as very useful for stopping phishing.
Phishers don't use the same domain name as the legitimate site. So the browser won't warn you "the key for paypal.com has changed! danger!" If the phisher bothers to self-sign at all, at most the browser will say "you're talking to a site you haven't visited before." Which is exactly the message the user got when she visited paypal.com for the first time, and for every other new site she visits. The user will become completely innoculated to these kinds of messages. (The model works better for ssh, because most people only ssh to a few boxes in their life.)
Even worse, the user only gets these warning if the phisher uses self-signed certs in the first place, which he has little reason to do. He can make his site look like "the real thing" in almost every way (except for the tiny browser or yellow location bar), and that's the root of the problem.
You're confusing the certificate/signing authority (CA) with the identity of the certificate owner. The CA, i.e. who vouches for the certificate is not as important -- Firefox comes with a list of trusted root CAs, and for the most part people don't muck with that. It's the identity of the website, i.e. who the browser is talking to, that really matters to the user. Right now the only way to get this info in firefox is to inspect the certificate manually, even though this is arguably the most important thing the user should know when visiting an SSL-enabled site.
Of course until you get phished to a site owned by "PayPa1 Inc."*
Yeah, but that's the job of the CA: to filter out bogus domain names and entity names. Granted, the CAs don't do their jobs too too well, but I think they would refuse such a blatant fraud.
It looks like Opera is not showing the signing authority (that would be Verisign), but is showing the certificate owner (that would be PayPal). Good for them.
"Most browsers have certificates set up and secure connections, but the browser view only shows a padlock - it doesn't tell you who owns the certificate."
I still can't believe that, to this very day, there is no major browser that displays the right information about a certificate by default! This is the whole point of a certificate: it tells you that paypal.com actually belongs to a real-world entity named "PayPal Inc."
At the very least, when connected via SSL to a site with a valid cert, the browser address bar should have an extra line that names the real-world entity. A yellow padlock and location bar tell you nothing about who you're really talking to. You shouldn't have to manually examine the certificate to find out this information.
Does anyone have any idea why even Firefox, with all its other great usability and security innovations, still gets this basic thing wrong??
What about extracting the placeholder and the public key, then replacing the software with your own version that ALWAYS outputs the encrypted placeholder regardless of the input?
Obfuscation doesn't prevent you from changing the functionality of the code. If you have control over the code that is running on a router, then of course you can just delete the filtering code entirely, or replace it with whatever you want.
All that obfuscation does is prevent you from understanding what the original code does, even if you examine/run/make changes to that code. Forcing the original, proper code to run on a router is another matter entirely.
C'mon, now you're showing an utter lack of knowledge of this work.
Of course every processor has branch instructions. But the obfuscated programs don't ever use those branch instructions -- at least not when comparing the input to the desired keywords. You do acknowledge that it is possible to write a computer program that doesn't perform any branches, don't you?
As I've said several times before, the output is basically an encrypted yes/no bit. However, there is no place or time in the program execution where this bit is every explicitly computed. Instead, the output ciphertext is constructed implicitly, via clever number theory, as the program runs -- in a straight line, without any branches. This theme of computing implicitly on ciphertexts is actually quite common throughout cryptography in other applications.
Look, you don't have to believe me; read the paper. The introduction is quite accessible and gives good intuition about how this can be possible.
Here is the money quote from the paper: "both matching and non-matching documents appear to be treated precisely the same way. The machine, or anyone else who views the execution is totally unaware if condition is satisfied, as it is executed as a strait-line [sic] code, where condition is never known unless you can break the underlying encryption scheme."
So, there are no conditional statements in the resulting code.
It doesn't work like that. At some point in the program, the program does a check equivalent to:
if(hash(word)==hash_were_looking_for)
The code doesn't have to do any such thing, and you are arguing from incredulity ("I don't see how it could be done any other way"). Fortunately, solid mathematical proofs destroy this fallacy.
In the "plain" obfuscation model, it is not successful reverse-engineering to discover when you've got the correct password, because you can discover that when you have a black-box too.
For "public-key" obfuscation, the output is an encrypted answer, and none of the branches reveal any useful information about the output or whether the input matched the desired words. Calculations just proceed unconditionally on encrypted values, without any explicit tests or branches being performed on the unencrypted data itself. Read the paper if you don't believe it.
That doesn't seem very new or very useful, really. Moreover, even with salting, you'd have to think that dictionary attacks were quite feasible.
The newness and usefulness is the strength of the definition of obfuscation. It goes far beyond just "hash and compare equality" -- a lot of sophistication is needed to construct an obfuscator that satisfies the rigorous definition of security.
A second aspect is that for this application, the adversary is not told whether the input matched the keywords or not, because the yes/no output is encrypted in the key of a third party. So dictionary attacks are useless, because the adversary can't tell when he's succeeded.
In fact, these matching algorithms are done in a way much similar to password hashing (though they require much more sophistication).
You mention a dictionary attack, which is certainly something an adversary could attempt. There are two models: in the "plain" obfuscation model, a dictionary attack may succeed, but this doesn't break anything -- if you were given a black-box that truthfully answers "is the password X?" then you could also run a dictionary attack on that. So that doesn't count as "figuring out how the code works."
In the other model, the output of the program is encrypted, and the adversary doesn't know how to decrypt it (but a third party does). This is akin to getting a black-box that takes inputs, and outputs nothing to the adversary (but still performs some computation on the input and gives it to a third party). In this model, a dictionary attack doesn't work, because you never get confirmation of whether your guess is correct. Still, the third party who decrypts the output learns all of the inputs (or just the ones that the program flags), without the adversary knowing how that flagging is being performed, or what terms are being flagged.
But how does this stop me from installing a debugger and using a disassembler to read the code in assembly?
It doesn't, and it's doesn't try to. You are allowed to have full access to the obfuscated code. Still, having all this access doesn't allow you to learn (for example) what strings the code is "grepping" for in the input. Whether there is a match or not, the execution path of the code remains the same, but it produces different outputs.
If this sounds like magic, yes, it pretty much is. But so does public-key cryptography to most people, and there are ways to do that too.....
Slashdot Mirror
I am a professional research cryptographer. There are many misstatements in the comments so far (what else should one expect, it's Slashdot.....)
Here are some facts to fix the clutter:
1. Shor's algorithm works on quantum computers and can factor integers in polynomial time. This breaks all public-key systems that depend on the hardness of factoring, including RSA, Rabin, Paillier, and XTR.
2. A different version of Shor's algorithm also computes discrete logarithms (again, in poly time). This breaks all public-key systems that depend on the hardness of discrete log, over *any* cyclic group. This includes ElGamal, even over "exotic" groups like those associated with elliptic curves.
3. Nevertheless, factoring and discrete log are different beasts and are not known to be equivalent to each other. Still, Shor's algorithm (in different versions) solves them both.
4. Shor's algorithm does not yet break all known public-key cryptosystems. Systems based on lattices, for example, do not appear to be affected as of yet. These include Ajtai-Dwork and a couple systems by Regev. NTRU is based on lattices, but is based on some not-so-natural assumptions (i.e, the assumption that "NTRU is secure").
5. Public key encryption is (probably) *not* equivalent to trapdoor permutations (or even trapdoor one-way functions). TDPs are a much stronger notion and are not strictly needed to do secure public-key encryption. For example, ElGamal and lattice-based systems are not based on trapdoor primitives per se.
Shor's Algorithm, which solves an NP-whatever problem in (log n)^3 time, works because it draws computational power from another universe.
Whoah, whoah. Shor's Algorithm solves the factoring problem, which is almost certainly NOT NP-complete. (If it were, then NP would equal coNP, which would be almost as surprising as if NP equalled P.)
And please, can we quit calling them "computer security researchers"?
We can't in this case because these people really are computer security researchers. They are top academics from strong institutions.
In high school I wrote a program for a physics project that showed electromagnetic wave propagation and interference.
Funny -- when I read this first sentence, I immediately thought, "hey, that sounds a lot like Chris Burke's project."
Indeed, upon seeing the identity of the commenter, I discovered how right I was.
You never showed me the bug, though.
Just wait 18 to 24 months before doing the deed.
(Oddly, the captcha for posting this was the word 'acquit'....)
Solve any problem polynomially reducable to SAT/3-SAT
You have your reducibility direction mixed up: even really easy problems (like sorting, or outputting "2") are reducible to SAT. It's the hard problems that SAT reduces to.
Not that this matters, because quantum computing is very unlikely to be able to solve NP-complete problems. It does seem to help with very structured problems like factoring, though. No, factoring is (almost definitely) not NP-complete.
Further, show it being done in polynomial-time with respect to the problem size.
Polynomial-time is an asymptotic notion. It can't be verified for a particular problem size (or finite set of problem sizes). It is purely an analytical concept, not an experimental/testable one.
There are ways of encoding the watermarks that are resistant to such "collusive attacks." They allow the distributor to decode at least one of the original versions, even from a "noisy" version that resulted from a diff like you described. The techniques go by many names: collusion-secure fingerprints, fingerprinting codes, traceability codes... the concept is the same, though.
Whether these codes are actually implemented, I have no idea.
Functional languages conform to lambda calculus, which has been shown to be Turing equivalent, which means that any program that can be computed on a Turing machine can be solved using Lambda calculus.
And for this reason, checking correctness of code cannot be automated, for that would solve the Halting Problem.
Not that functional programming isn't great. You're just overselling it.
The main argument is that the public's errors cancel out.
But the whole point of the article was to debunk this argument!
Errors do not cancel out; they are systematically biased and reinforce each other.
The receipt does not reveal for whom you voted.
It only allows you to verify that your vote was counted in the final tally.
You are right; however, Shamir first observed that Reed-Solomon error correction also has nice secrecy properties. That is, even if you have one share less than the number required to reconstruct, you actually have no information about the secret at all. This can be a good thing if you are distributing your data among potentially untrustworthy servers.
Eight and five will make eleven.
Really?
Ask and ye shall receive:
phishfighting.com
Quite a few people are proposing a compromise trust model like ssh has, where the browser UI would change so as to warn you when you're about to encrypt to an unexpected public key.
This model has some good things going for it, but I don't see it as very useful for stopping phishing.
Phishers don't use the same domain name as the legitimate site. So the browser won't warn you "the key for paypal.com has changed! danger!" If the phisher bothers to self-sign at all, at most the browser will say "you're talking to a site you haven't visited before." Which is exactly the message the user got when she visited paypal.com for the first time, and for every other new site she visits. The user will become completely innoculated to these kinds of messages. (The model works better for ssh, because most people only ssh to a few boxes in their life.)
Even worse, the user only gets these warning if the phisher uses self-signed certs in the first place, which he has little reason to do. He can make his site look like "the real thing" in almost every way (except for the tiny browser or yellow location bar), and that's the root of the problem.
You're confusing the certificate/signing authority (CA) with the identity of the certificate owner. The CA, i.e. who vouches for the certificate is not as important -- Firefox comes with a list of trusted root CAs, and for the most part people don't muck with that. It's the identity of the website, i.e. who the browser is talking to, that really matters to the user. Right now the only way to get this info in firefox is to inspect the certificate manually, even though this is arguably the most important thing the user should know when visiting an SSL-enabled site.
Of course until you get phished to a site owned by "PayPa1 Inc."*
Yeah, but that's the job of the CA: to filter out bogus domain names and entity names. Granted, the CAs don't do their jobs too too well, but I think they would refuse such a blatant fraud.
It looks like Opera is not showing the signing authority (that would be Verisign), but is showing the certificate owner (that would be PayPal). Good for them.
Best comment in the interview:
"Most browsers have certificates set up and secure connections, but the browser view only shows a padlock - it doesn't tell you who owns the certificate."
I still can't believe that, to this very day, there is no major browser that displays the right information about a certificate by default! This is the whole point of a certificate: it tells you that paypal.com actually belongs to a real-world entity named "PayPal Inc."
At the very least, when connected via SSL to a site with a valid cert, the browser address bar should have an extra line that names the real-world entity. A yellow padlock and location bar tell you nothing about who you're really talking to. You shouldn't have to manually examine the certificate to find out this information.
Does anyone have any idea why even Firefox, with all its other great usability and security innovations, still gets this basic thing wrong??
What about extracting the placeholder and the public key, then replacing the software with your own version that ALWAYS outputs the encrypted placeholder regardless of the input?
Obfuscation doesn't prevent you from changing the functionality of the code. If you have control over the code that is running on a router, then of course you can just delete the filtering code entirely, or replace it with whatever you want.
All that obfuscation does is prevent you from understanding what the original code does, even if you examine/run/make changes to that code. Forcing the original, proper code to run on a router is another matter entirely.
C'mon, now you're showing an utter lack of knowledge of this work.
Of course every processor has branch instructions. But the obfuscated programs don't ever use those branch instructions -- at least not when comparing the input to the desired keywords. You do acknowledge that it is possible to write a computer program that doesn't perform any branches, don't you?
As I've said several times before, the output is basically an encrypted yes/no bit. However, there is no place or time in the program execution where this bit is every explicitly computed. Instead, the output ciphertext is constructed implicitly, via clever number theory, as the program runs -- in a straight line, without any branches. This theme of computing implicitly on ciphertexts is actually quite common throughout cryptography in other applications.
Look, you don't have to believe me; read the paper. The introduction is quite accessible and gives good intuition about how this can be possible.
Here is the money quote from the paper:
"both matching and non-matching documents appear to be treated precisely the same way. The machine, or anyone else who views the execution is totally unaware if condition is satisfied, as it is executed as a strait-line [sic] code, where condition is never known unless you can break the underlying encryption scheme."
So, there are no conditional statements in the resulting code.
It doesn't work like that. At some point in the program, the program does a check equivalent to:
if(hash(word)==hash_were_looking_for)
The code doesn't have to do any such thing, and you are arguing from incredulity ("I don't see how it could be done any other way"). Fortunately, solid mathematical proofs destroy this fallacy.
In the "plain" obfuscation model, it is not successful reverse-engineering to discover when you've got the correct password, because you can discover that when you have a black-box too.
For "public-key" obfuscation, the output is an encrypted answer, and none of the branches reveal any useful information about the output or whether the input matched the desired words. Calculations just proceed unconditionally on encrypted values, without any explicit tests or branches being performed on the unencrypted data itself. Read the paper if you don't believe it.
That doesn't seem very new or very useful, really. Moreover, even with salting, you'd have to think that dictionary attacks were quite feasible.
The newness and usefulness is the strength of the definition of obfuscation. It goes far beyond just "hash and compare equality" -- a lot of sophistication is needed to construct an obfuscator that satisfies the rigorous definition of security.
A second aspect is that for this application, the adversary is not told whether the input matched the keywords or not, because the yes/no output is encrypted in the key of a third party. So dictionary attacks are useless, because the adversary can't tell when he's succeeded.
In fact, these matching algorithms are done in a way much similar to password hashing (though they require much more sophistication).
You mention a dictionary attack, which is certainly something an adversary could attempt. There are two models: in the "plain" obfuscation model, a dictionary attack may succeed, but this doesn't break anything -- if you were given a black-box that truthfully answers "is the password X?" then you could also run a dictionary attack on that. So that doesn't count as "figuring out how the code works."
In the other model, the output of the program is encrypted, and the adversary doesn't know how to decrypt it (but a third party does). This is akin to getting a black-box that takes inputs, and outputs nothing to the adversary (but still performs some computation on the input and gives it to a third party). In this model, a dictionary attack doesn't work, because you never get confirmation of whether your guess is correct. Still, the third party who decrypts the output learns all of the inputs (or just the ones that the program flags), without the adversary knowing how that flagging is being performed, or what terms are being flagged.
But how does this stop me from installing a debugger and using a disassembler to read the code in assembly?
It doesn't, and it's doesn't try to. You are allowed to have full access to the obfuscated code. Still, having all this access doesn't allow you to learn (for example) what strings the code is "grepping" for in the input. Whether there is a match or not, the execution path of the code remains the same, but it produces different outputs.
If this sounds like magic, yes, it pretty much is. But so does public-key cryptography to most people, and there are ways to do that too.....