So, we are back on the Wikileaks thing again. Despite my best arguments to myself, I could not convince me not to write about this. Moving swiftly on from my mild DID, we need to jump back in time a little. So, do you remember when the original Wikileaks stuff happened? Well, shortly after that, Wikileaks took a huge blow to the coffers. Visa, MasterCard, PayPal and others stopped accepting payments to Wikileaks' financial wing, shall we say?
Now, the reasons for stopping the payments varied, both on and off the record, but the gist of it was "violation of terms of service." Every time you sign up to another site, or install some software there is always a ToS or EULA that you have to agree to. Violating either basically constitutes breach of contract and you can be charged accordingly. So all these companies claimed breach of contract and shut down payments pending further investigations.
Now, this didn't sit well with some people on the Internet, namely Anonymous (pause for ironic effect.) Anonymous is basically a collection of individuals who post on forums, mostly 4chan, under known aliases. They are highly vocal about pretty much anything and participate in "hacktivism" and real activism, such as this. In truth it is slightly more complex than that and could fill a whole book, which I will probably never right, so somebody go ahead and do it, provided I am consulted and credited for the idea.
So, Anonymous are ticked off and decide to exact some payback (note the choice of words, specifically the usage of the word pay) on the payment proccessors. They look into their bag of tricks and whip out a classic: the DDoS attack (I will explain DDoS attacks in a future post). This was codenamed Operation Avenge Assange and came under the general umbrella of Operation Payback. I could explain the nuances, but I really don't want to get into, so sorry folks. Basically, they attacked various financial institutions and others and even took down Visa's and MasterCard's websites.
How it was actually done is kind of hazy, but as far as I know, people installed clients that would respond to an IRC trigger and act like a bot in a botnet (again, an explanation on botnets in a future post) to attack whatever target was named in the trigger. This would then allow a single person to have 100's and 1000's of computers attacking the desired target and thus lending more weight to the attack.
Now here's the thing, executing or participating in a DDoS is ILLEGAL. There is no room for discussion on this one. The legality of Wikileaks can be debated, but on this topic, the law is explicit. What they did was illegal, end of discussion.
Recently a few people have been arrested in connection to this, which they should be. Anonymous has retaliated saying that this should be considered a form of protest and freedom of speech and all manner of other things. Well, it's not protest, it's a crime. End of. They even went so far as to threaten the Government of the United Kingdom.
And throughout all of this, nobody realises the irony of the association between Wikileaks and Anonymous. Where Anonymous is rooted in the concealing of certain information, Wikileaks' founding principle is the full disclosure of information. I say nobody realised this, but Randall Munroe did and he showed it here. (PS xkcd = highly recommended by me)
I've said my piece and I'm done with this. I will post about the newer developments but in no real detail. As I've said before, this whole episode just pushed my buttons, so I'm going have as little to do with it as possible.
Monday, 31 January 2011
Friday, 28 January 2011
Why P= NP is important
So, there have been some developments in Wikileaks, but I think I will post those later, just to give some semblance of order to my blog, if not my brain. So we are now on P vs. NP and its relevance.
By, now I hope you are familiar with the P vs. NP problem, but for those of you who are not, see my previous posts here, here and here. Now that everybody should be up to speed, we proceed with the discussion. As you may or may not know, my area of speciality is known as cryptography. The finer points are covered in this post and so I will not repeat them.
For the rest of this post, I will consider only public key crypto, wlog, as it is more intuitive to explain than private key crypto. Most crypto schemes are based on what are know as "number-theoretic assumptions." These are problems in number theory, which we believe are hard to solve. A security proof is generally done by a technique known as reduction. We assume that we can break our scheme using algorithm A and based on that, we show that we can construct another algorithm B which will solve the problem contained in our assumption. Since we know that it is hard to solve the problem in the assumption, then we we know it is also hard to break our crypto scheme. This is broadly called the standard model.
The choice of assumption is very important. There are some well known assumptions, which are accepted to be hard, such as the Diffie-Hellman problems and the RSA assumption. However, one can also introduce a new assumption provided it is accompanied with a proof of intractability (read hard to solve). The main point is there should be some proof that your assumption is intractable, which generally means that is an NP type problem. And that is where the connection lies.
If P = NP, then there exists a polynomial time solution for all NP problems, thus all our assumptions can easily be solved and thus all our encryption schemes can be broken. So, if P = NP essentially cryptography falls flat on its face, or does it?
Membership into the class P is determined by the bounds of the solution to a problem. The most common way of representing this is big-O notation. The problem with this notation is that it hides too much information for my liking. If we have two algorithms A1 & A2 for solving a problem A and we want to decide which is more efficient, we can compare the big-O notation. What do you do if both A1 & A2 are O(n^15) (where ^ denotes exponentiation). Both are polynomial in time, but one may be worse than the other by a factor of 100's or even 1000's. Another fact is that a problem may have a polynomial time solution, but the order of the polynomial may be so large as to make the computation infeasible e.g. O(n^100).
So, cryptography could possibly still survive a valid P = NP proof, but that is contingent on several factors. Most of it will be everybody disagreeing on what the limits are on feasible computation and what is truly secure and what is not.
As a final thought, as a cryptographer, you mostly have to believe that P != (read not equal) NP, which I strongly do.
By, now I hope you are familiar with the P vs. NP problem, but for those of you who are not, see my previous posts here, here and here. Now that everybody should be up to speed, we proceed with the discussion. As you may or may not know, my area of speciality is known as cryptography. The finer points are covered in this post and so I will not repeat them.
For the rest of this post, I will consider only public key crypto, wlog, as it is more intuitive to explain than private key crypto. Most crypto schemes are based on what are know as "number-theoretic assumptions." These are problems in number theory, which we believe are hard to solve. A security proof is generally done by a technique known as reduction. We assume that we can break our scheme using algorithm A and based on that, we show that we can construct another algorithm B which will solve the problem contained in our assumption. Since we know that it is hard to solve the problem in the assumption, then we we know it is also hard to break our crypto scheme. This is broadly called the standard model.
The choice of assumption is very important. There are some well known assumptions, which are accepted to be hard, such as the Diffie-Hellman problems and the RSA assumption. However, one can also introduce a new assumption provided it is accompanied with a proof of intractability (read hard to solve). The main point is there should be some proof that your assumption is intractable, which generally means that is an NP type problem. And that is where the connection lies.
If P = NP, then there exists a polynomial time solution for all NP problems, thus all our assumptions can easily be solved and thus all our encryption schemes can be broken. So, if P = NP essentially cryptography falls flat on its face, or does it?
Membership into the class P is determined by the bounds of the solution to a problem. The most common way of representing this is big-O notation. The problem with this notation is that it hides too much information for my liking. If we have two algorithms A1 & A2 for solving a problem A and we want to decide which is more efficient, we can compare the big-O notation. What do you do if both A1 & A2 are O(n^15) (where ^ denotes exponentiation). Both are polynomial in time, but one may be worse than the other by a factor of 100's or even 1000's. Another fact is that a problem may have a polynomial time solution, but the order of the polynomial may be so large as to make the computation infeasible e.g. O(n^100).
So, cryptography could possibly still survive a valid P = NP proof, but that is contingent on several factors. Most of it will be everybody disagreeing on what the limits are on feasible computation and what is truly secure and what is not.
As a final thought, as a cryptographer, you mostly have to believe that P != (read not equal) NP, which I strongly do.
Tuesday, 25 January 2011
P=NP
Recently, a friend of mine pointed me to this possible solution to P vs. NP. Just to jog your memory, here's $20 (I know, it's a terrible joke and I apologise.) On a serious note, here is my previous post on the same problem. Now the key difference between the previous proof and this one is the result. Where as Vinay Deolaiker tried to show P != (read not equal) NP, Vladimir Romanov has tried to show P = NP.
In my last post, I didn't really cover the problem itself. As promised I will do so in this post. The P vs. NP problem is a problem in computational complexity, which I will explain at a very high level. The class P is of those problems which can be solved in polynomial time, which is conisdered to be analogous to efficient. These problems are considered "easy to solve." The class NP is problems which cannot be solved in polynomial time, but in superpolynomial time or worse. These problems are considered hard to solve. There is a bit more mathematical finesse to the whole problem, but this basic concept is sufficient for now.
The whole P vs. NP debate is based on the relationship between P and NP, i.e. is P = NP. If P = NP this means there exists a polynomial time (read efficient) solution to all NP problems. This doesn't tell us anything about the solutions for the problems, other than that they exist. If P != (read not equal) NP, then all NP problems cannot be solved in polynomial time (read efficiently.) There is a whole issue about problems being misclassified as NP, but we omit that as it is not necessary for this discussion.
What was discovered is that some NP problems, that can be written as another NP problem, known as reducing. An overly trivial example is how multiplication can be written as addition e.g. 3 x 7 = 7 + 7 + 7. Neither addition nor multiplication is NP, but the example will help you visualise the concept. Following this discovery, was the realisation that all other problems in NP could be reduced to certain other problem, which is known as NP-completeness. That is a problem is NP-Complete if all other NP problems can be reduced to it. All reduction to an NP-complete are polynomial in time (just trust me on this one.)
Now, this leads us to the basic structure of pretty much all P = NP proofs: A polynomial time solution problem to a NP-Complete problem. The logic is simple if there exists a polynomial time solution to problem C, then there exists a polynomial time for all NP problems P. To achieve this, we reduce P to C (which is polynomial in time) and then solve C (which is again polynomial.) A polynomial plus a polynomial is still a polynomial. Thus, all NP problems have a polynomial solution, which implies they are in P. Therefore P = NP QED.
Now, back to Romanov's proof. He has proposed a polynomial time solution for what is know as 3-Satisfiability or 3SAT. If you are unfamiliar with this problem read the Wikipedia entry on it for the basic idea. One of the most remarkable things about his proof, is that he has implemented it and released the code for it, available here. Some proofs, although efficient in theory, can not be realised in practice due to various implementation issues. Here what we have is not only a theoretical result, but a practical implementation of it as well, which is quite an achievement.
Now, on the the actual proof itself. After a first reading of this paper, I was fairly convinced that the proof is valid an will hold. But therein lies my folly. I then proceeded to properly read the paper and understand the proof and evaluate if it was valid or not. My evaluation would not be the best, but it would be a start. As I went on through the paper, I noticed something very disconcerting; some of the key points were not, in my opinion, explained well enough. Everything is explained, but some key points lacked sufficient detail, enough so as to make them seem more akin to magic than math.
Everything seems to check out, but as there is not enough detail on some of the main points, I am inclined to disregard this as a valid proof. Of course, I could be wrong, but that is up to domain experts to decide. I am tracking this story fairly closely and will post any updates I find. I'm sure you are wondering, "Why do you even care?" Very good question, which is shall explain in a future post.
In my last post, I didn't really cover the problem itself. As promised I will do so in this post. The P vs. NP problem is a problem in computational complexity, which I will explain at a very high level. The class P is of those problems which can be solved in polynomial time, which is conisdered to be analogous to efficient. These problems are considered "easy to solve." The class NP is problems which cannot be solved in polynomial time, but in superpolynomial time or worse. These problems are considered hard to solve. There is a bit more mathematical finesse to the whole problem, but this basic concept is sufficient for now.
The whole P vs. NP debate is based on the relationship between P and NP, i.e. is P = NP. If P = NP this means there exists a polynomial time (read efficient) solution to all NP problems. This doesn't tell us anything about the solutions for the problems, other than that they exist. If P != (read not equal) NP, then all NP problems cannot be solved in polynomial time (read efficiently.) There is a whole issue about problems being misclassified as NP, but we omit that as it is not necessary for this discussion.
What was discovered is that some NP problems, that can be written as another NP problem, known as reducing. An overly trivial example is how multiplication can be written as addition e.g. 3 x 7 = 7 + 7 + 7. Neither addition nor multiplication is NP, but the example will help you visualise the concept. Following this discovery, was the realisation that all other problems in NP could be reduced to certain other problem, which is known as NP-completeness. That is a problem is NP-Complete if all other NP problems can be reduced to it. All reduction to an NP-complete are polynomial in time (just trust me on this one.)
Now, this leads us to the basic structure of pretty much all P = NP proofs: A polynomial time solution problem to a NP-Complete problem. The logic is simple if there exists a polynomial time solution to problem C, then there exists a polynomial time for all NP problems P. To achieve this, we reduce P to C (which is polynomial in time) and then solve C (which is again polynomial.) A polynomial plus a polynomial is still a polynomial. Thus, all NP problems have a polynomial solution, which implies they are in P. Therefore P = NP QED.
Now, back to Romanov's proof. He has proposed a polynomial time solution for what is know as 3-Satisfiability or 3SAT. If you are unfamiliar with this problem read the Wikipedia entry on it for the basic idea. One of the most remarkable things about his proof, is that he has implemented it and released the code for it, available here. Some proofs, although efficient in theory, can not be realised in practice due to various implementation issues. Here what we have is not only a theoretical result, but a practical implementation of it as well, which is quite an achievement.
Now, on the the actual proof itself. After a first reading of this paper, I was fairly convinced that the proof is valid an will hold. But therein lies my folly. I then proceeded to properly read the paper and understand the proof and evaluate if it was valid or not. My evaluation would not be the best, but it would be a start. As I went on through the paper, I noticed something very disconcerting; some of the key points were not, in my opinion, explained well enough. Everything is explained, but some key points lacked sufficient detail, enough so as to make them seem more akin to magic than math.
Everything seems to check out, but as there is not enough detail on some of the main points, I am inclined to disregard this as a valid proof. Of course, I could be wrong, but that is up to domain experts to decide. I am tracking this story fairly closely and will post any updates I find. I'm sure you are wondering, "Why do you even care?" Very good question, which is shall explain in a future post.
Thursday, 20 January 2011
I've had about enough of Wikileaks
Well, I've been off silently fuming every time I hear the name "Wikileaks," which is why I haven't posted anything recently. But as promised in my previous post, this post will cover the blame part of the whole Wikileaks issue. (However, as this topic continues to annoy it will not be as lengthy as promised.)
So, here we go. The scenario is simple: Person X (I use an an anonymous name as I have no idea who actually did the leaking, but there are some suspects) had access to the US Diplomatic cables. I think its a safe assumption that X had some sort of clearance and/or was told not to share these cables with any unauthorised person(s). Another safe assumption would be that unauthorised persons includes me, possibly you and of course Wikileaks. Despite this, X decided to give the cables to Wikileaks.
We can see that this is obviously wrong, as in you will go to jail wrong. Blatantly illegal. Now the exact legality depends a few factors, such as if they had access to all the cables or some. If it was one person or many., the post the person is in, if the cables were classified and so on. Knowing now of these we cannot say much more and that is where I will leave it.
Moving on to Wikileaks, the law becomes a bit more grey. There are several issues involved here, the greatest of which being what jurisdiction does Wikileaks fall under? Which nation state's laws apply to them? This is quite a complex issue and still needs some resolving and legal catch up. Countries tend to be very cooperative on certain matters pertaining to the Internet, but there is still no really good legal framework. I still maintain that they are giving away stolen data, so intuitively that is wrong. See previous post for the whole whistle blowing or not issue.
Seeing as how they are now back in the news concerning the release of certain records from Julius Bär or Julius Baer Group. These records where leaked by former employee Rudolph Elmer. Elmer has since been detained and is being extradited to Switzerland to stand trial. Wikileaks has yet to publish the records, so we shall wait until they do so.
And on that note, I will leave this whole mess. I may or may not post something about any further revelations by Wikileaks. It all depends on how I feel about it at the time.
So, here we go. The scenario is simple: Person X (I use an an anonymous name as I have no idea who actually did the leaking, but there are some suspects) had access to the US Diplomatic cables. I think its a safe assumption that X had some sort of clearance and/or was told not to share these cables with any unauthorised person(s). Another safe assumption would be that unauthorised persons includes me, possibly you and of course Wikileaks. Despite this, X decided to give the cables to Wikileaks.
We can see that this is obviously wrong, as in you will go to jail wrong. Blatantly illegal. Now the exact legality depends a few factors, such as if they had access to all the cables or some. If it was one person or many., the post the person is in, if the cables were classified and so on. Knowing now of these we cannot say much more and that is where I will leave it.
Moving on to Wikileaks, the law becomes a bit more grey. There are several issues involved here, the greatest of which being what jurisdiction does Wikileaks fall under? Which nation state's laws apply to them? This is quite a complex issue and still needs some resolving and legal catch up. Countries tend to be very cooperative on certain matters pertaining to the Internet, but there is still no really good legal framework. I still maintain that they are giving away stolen data, so intuitively that is wrong. See previous post for the whole whistle blowing or not issue.
Seeing as how they are now back in the news concerning the release of certain records from Julius Bär or Julius Baer Group. These records where leaked by former employee Rudolph Elmer. Elmer has since been detained and is being extradited to Switzerland to stand trial. Wikileaks has yet to publish the records, so we shall wait until they do so.
And on that note, I will leave this whole mess. I may or may not post something about any further revelations by Wikileaks. It all depends on how I feel about it at the time.
Subscribe to:
Posts (Atom)
Subscribe To
Posts
All Comments