Monday, 31 January 2011

Operation Payback/ Avenge Assange

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.

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.

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.

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.

Thursday, 16 December 2010

P vs. NP goes on

So if you remember, I wrote about a proof to the P vs. NP problem proposed by Vinay Deolalikar. Well, it turns out there are "fatal flaws" in his proof, thus rendering it invalid. So, unfortunately he can no longer get the Millennium Prize or the Fields Medal for this proof. However, he has provided a brand new way of looking at the problem and has no doubt inspired many researchers to follow his methodology or indeed even improve on it. Until then, we wait. It's been over a century, a couple more years can't really hurt.

Sunday, 12 December 2010

Gates of Hell

OK Internet, it's time we had a talk. Not every controversy has to end in the word "gate". Seriously, it's getting so annoying.

Firstly, not every little piece of news that is a tad controversial (which is practically all of them) deserves its own name. Learn to tone it down.

Secondly, the only scandal that ends in "gate" is The Watergate Scandal. Everything else can be and should be named after something else. It is named thus as the scandal revolved around a robbery of the Democratic Party Headquarters in the Watergate Complex.

Everything else that doesn't have a "gate" ending object central to it, should be named something else. Bigotgate, Chicanegate, Digggate, Cablegate, Whitewatergate, etc need to stop now.

Wikileaks

So, I've been away for a while. Between having minimal to no Internet and having no electricity, I have been less than connected to the Internet. That and I am fairly lazy, but still TIA. Now on to business.

I'm sure you have all heard of Wikileaks, the purported whistle blower website. It provides people with an anonymous "drop boxes", where they can submit documents detailing any wrongdoing. The site then goes on to state "our accredited journalists assess the submission. If it meets the criteria, our journalists then write or produce a news piece based on the document." It goes on further to describe ways of ensuring your anonymity when sending it via post and so forth. In theory this has provided whistle blowers with a way to expose wrongdoings. In theory.

I say purported as I do not believe it is a whistle blower site. Firstly, let us examine the concept of whistle blowing. It derives from the practice of policemen blowing a whistle to alert people around of the commission of a crime. It refers to a person who highlights something wrong that is happening, most in an organisation. Now, when I say wrong I mean illegal, but some people consider it includes immoral wrongdoings. So the site first came to prominence when it published Iraq/Afghanistan War Diaries. These gave details of operations and on the ground realities of the wars. They did bring to light some, for lack of a better term, disconcerting revelations. These could be considered whistle blowing, but there are many grey areas, which we overlook for the sake of argument and say this is valid whistle blowing. That, my friends, is where it all ends.

The next major publication was swiftly dubbed Cablegate (hate that name, cf.this post for the explanation). This was the leak of several secret diplomatic cables between Washington DC and diplomatic missions in several countries. Here's where we go from the legally ambiguous to outright illegal and the legitimacy of these leaks as whistle blowing is a little more than questionable.

To explain, let us detail the job of a diplomatic mission to another country. Most of us are familiar with the consular services, that is issuing visas, passports, etc, but that is only their public facing role. Diplomatic envoys are representatives of their sovereign government in a, presumably, friendly nation. It is their duty to not only represent their country, but also provide their country with information about the people, mainly politicians, of that country. As part of this duty, they send back profiles, if you will, on politicians to their government. These are sent in cables, which are
private communications.

Notice the emphasis on
private. Not only are these communiques private, but some of them are even classified. Granted, they may not be highly classified, but classified all the same. Only a limited number of people have access to these cables and presumably such access comes with a "do not tell anybody about this" clause. This is where the illegality comes in.

Whomsoever gave these cables to Wikileaks is guilty of a few crimes, depending which way you spin it. These range from the banal mail fraud to my personal favourite espionage. It's not even debatable if what these people did is wrong, it just is. Most of these cables do not expose any sort of wrongdoing at all.

As stated before diplomatic envoys report on local politicians. Although I would like to believe that these people are trained for and/or good at judging people, most of what they report is still personal opinion and conjecture. It is just inherent in this type of data. This is essentially office gossip at an international level. I'm pretty sure that someone somewhere has called their new Head of PR an "mistake-prone control freak" (my personal favourite quote out of all of the cables) and that is considered to be normal. Hence, no wrongdoing and thus no whistle blowing.


Furthermore, some of the "data" sent in the cables in nothing more than well crafted misinformation (this is completely ignoring the false cables that were released). Governments are aware that diplomats report back to their capital, as they have their own diplomats doing the same. So they may choose to feed a diplomat false information in the hope that their parent country will believe it and thus be manipulated into behaving a certain way. I will swiftly avoid any ethical or political debate by saying that all of that falls outside my purview.

Yes, I agree that there may be some cables whose leaking may have proved beneficial, but they are a minority. There is a saying in the security industry: "Even f you secure 99% of the system, you have still failed." The cables that potentially have a detrimental effect, though small in number, will have the greatest impact. Barring these, most of the cables' leakage and then release lead to nothing more than embarrassment for the governments involved.

And thus we see that the recent Cablegate (*shudder*) was basically neither legal nor legitimate whistle blowing. Effectively, Wikileaks are just fences for stolen digital data. Now this leaves us with the question of where the blame/responsibility lies. For that, I will put up another post, as it is quite a lengthy matter. That and you are probably really bored of reading this by now.

***SIDENOTE***
Just found this. No real relevance, but it's funny!