Morning sports fans! Yes, I've missed you too, but I'm having a super perfectionist phase and none of my posts seem good enough to publish. This should all blow over and there will quite a few post some time in the future. So, let's wind the clock back a smidge and remember one of the biggest fails of the year: The Great BlackBerry Outage of 2011! (Yeah, I'm expecting more to come.)
So, cast your mind back to October 10th-ish when the first reports of a RIM server crash came in. Millions of people were left without access to BBM and some Internet services, such as Facebook. Ah, the many jokes we made that they didn't see. Well it quickly spread to North America and then other planets! (BONUS QUESTION: How many of these planets do you know?) It was somewhat fitting that BlackBerry users who were fairly vain about BBM had it ripped from them for a couple of days. It was a good thing.
Eventually, RIM apologised, service and the status quo were restored. There was still the great debate of BlackBerry vs. iPhone, (as explained here by Jimmy Carr and Sean Locke on 8 out of 10 Cats) but the iPhone users had a little chip on their shoulder that said "We never have service outages." This was compounded by the fact the release of the iPhone 4S, and with it Siri, was imminent. Just to catch you up, Siri is the voice activated personal assistant that comes with the iPhone 4S. (For further details see this)
Anywho, Siri is now here and people are enjoying asking it silly questions, demonstrating which accents it can't understand and showing that it's only fully functional in USA. What I was, until recently, unaware of is that Siri runs in the cloud. I have no love for cloud computing, but will ignore that at this juncture. A couple of days a ago a failure caused Siri to be unable to connect to the Apple servers and thus not work. Wait, you mean Apple has service outages as well? *le gasp*! Well of course they do! The reason is simple,they seem to have overlooked a very basic principle of computer security: critical infrastructure.
What is critical infrastructure you ask? Good question! Critical infrastructure is an old-ish field which studies an setup and sees what it would take for that to stop working. The classical example is a very nice graph theoretic problem, which is quite nicely demonstrated by the London Underground map. Assume this your only means of transport. Pick any station and/or section of the map. The problem is can you make a single cut and isolate that station/section from the rest of the map? There are variants, such as the minimum number of cuts needed to isolate a station/section and also on other things such as electricity, water and gas supply. You get the gist of it all, right?
The same can be done for communication and telecommunication networks. This is normally done, but it can be a bit tricky. With wired communications, it's easy to draw up a graph-style map, with each wire as an edge and each node as a vertex. However the same is not really true of wireless communications. To stop wired communications between point A and B, you need to sever the wire joining them. It's not as clear what the equivalent for wireless communication is. There is also the issue that unlike wired devices, which are immobile, wireless devices by definition are mobile.
So, now do we consider simply the connection between the devices or do we also have to consider the location? Can we only consider one or do we have to consider both? If I go into a lift and lose wireless connectivity is that a failure of the network or the device or both or neither? If you are thinking such distinctions are a moot point, then you are pretty much correct. Yes, it's not a major issue, but it should not be completely overlooked. There are a lot more examples of this, but that would mean delving into technicalities, which I would rather not do.
And there is the issue of time. These things take time, quite often a lot of it. There are so many contingencies to consider, such as the classic CTO chokes on sushi, rest of the department is killed in a meteor strike and the only other guy who knows the password gets retrograde amnesia. Yes, that is a tad far-fetched and one should probably stop when retrograde amnesia is the most likely event in your scenario. The digital market thrives on speed. You need to get the next product out there 2 weeks before the previous one is launched.
So, as you can see, owing to several issues, the critical infrastructure analysis is possibly not done as well as it should be, which can cause these kinds of issues. On the other hand, you can do the most thorough analysis and the worst case scenario may still occur, thus causing an outage. So basically it's all a roll of the dice and remember "God doesn't play dice!"
Showing posts with label math. Show all posts
Showing posts with label math. Show all posts
Sunday, 6 November 2011
Wednesday, 29 June 2011
FIFTY!!! YAAAYY!!!
So, this is my 50th post. WOOHOOO!!! Enough with the celebrations, we have work to do. I decided to mark this momentous milestone, I will discuss the basics of cryptography. Now, I know I have covered some bits of this before, feel free to skip any parts you think you know. So, let's start by naming the three principle components of cryptography : Encryption, Signatures/Message Authentication Codes(MACs) and Proofs.
So, let's start with the first, and probably most well-known, section: Encryption. The scenario is simple, you have a message that you wish to communicate to somebody else, without anybody else finding out that message. The way to do this is encryption. Think back to when you were a kid and you and your friends made up a secret language. That could be viewed as a crude form of encryption, as can all languages. But now, lets talk about the more modern stuff.
An encryption scheme is basically two functions: and encryption function, which I will denote by ENC, and a decryption function, which I will denote by DEC. ENC takes a normal message and turns it into something unintelligible, called a ciphertext. DEC takes a ciphertext and turns it back into the message. To do this, both functions need some additional information, called a key. There are two flavours of encryption, both defined by the relation between the keys used by ENC and DEC. In symmetric or secret key encryption, both ENC and DEC use the same key, whereas in asymmetric or public key encryption, they use distinct but related keys.
Now you must be wondering where all these keys come from and how they get to the right people. For the asymmetric setting it's fairly simple. The receiver generates the keys and publishes the public encryption key, PK, and keeps the decryption key, SK, secret. The publication of PK leads to some very interesting problems, but that's out of scope, but worth mentioning. In the symmetric setting, it's a tad more complicated and this problem is a whole research area on it's own. Let's just say that there are clever ways of doing it in several circumstances.
Now signatures/MACs are essentially the same thing, with different key settings. MAC use symmetric keys and signatures use asymmetric keys. They both serve the same purpose, that is to authenticate the source of a message. For simplicity, I will refer to both of them as codes, which is an abuse of many notations, but will suffice for our purposes. All code systems have two functions: generate, denoted GEN, and verify, denoted VER, and they work as follows: generate takes in a message and outputs a tag and verify takes in a message and a tag and checks if the tag was indeed generated by the sender for that message.
Here we must note two very important things. Tags are both sender and message dependant. Thus a valid tag for one message, cannot be a valid tag for another message sent by the same person. Also, a valid tag for a message sent by one person cannot be a valid tag for the same message sent by another person. Thus the VER functions takes as input the message and the identity of the person, implicitly in the key. The main assumption here is that only the sender can generate a valid tag and thus any valid tag implies that the message was sent by them. This is very close to real world signatures and how we view them. Yes, I know that real signatures can be forged, but we also consider that in cryptography. There are some subtleties as to how this is done, but we shan't venture into that.
Finally, we come upon proofs. These are the least well-known and some would say the least understood of the three. The basic idea behind a proof system is that one party wants to prove to the other that a secret value x has some property. The property could be proven by revealing x, but then that would defeat the point of it being secret. So you need to somehow show that x has this property, but without revealing x. We seem to be in a bit f a pickle. That is, until our hero zero knowledge proofs show. These are protocols which allow you to prove certain statements about a value(s) without revealing the value and without the other person learning anything about the secret value.
A simple way to view this is by the simple statement: "Pick a card, any card!" Let's say I hand you a deck of cards and you pick one out at random and put it aside. Now I ask you what suit it is. You tell me it's a spade. I ask you to prove it. You could show me your card, but that's a secret right? Well, how about you show me 13 clubs, 13 hearts and 13 diamonds. *DING*! Now I know nothing more about your card than that it is in fact a spade. This example is great when explaining not only zero knowledge proofs, but also some of it's stranger variants. But that's all for later (read: maybe if I feel like, but don't hold your breath).
So, all in all, we covered the three basic concepts in cryptography because I'm too lazy to do real posts and the number 50 was just mainly an excuse. We hope to have a resumption of normal service soon-ish.
So, let's start with the first, and probably most well-known, section: Encryption. The scenario is simple, you have a message that you wish to communicate to somebody else, without anybody else finding out that message. The way to do this is encryption. Think back to when you were a kid and you and your friends made up a secret language. That could be viewed as a crude form of encryption, as can all languages. But now, lets talk about the more modern stuff.
An encryption scheme is basically two functions: and encryption function, which I will denote by ENC, and a decryption function, which I will denote by DEC. ENC takes a normal message and turns it into something unintelligible, called a ciphertext. DEC takes a ciphertext and turns it back into the message. To do this, both functions need some additional information, called a key. There are two flavours of encryption, both defined by the relation between the keys used by ENC and DEC. In symmetric or secret key encryption, both ENC and DEC use the same key, whereas in asymmetric or public key encryption, they use distinct but related keys.
Now you must be wondering where all these keys come from and how they get to the right people. For the asymmetric setting it's fairly simple. The receiver generates the keys and publishes the public encryption key, PK, and keeps the decryption key, SK, secret. The publication of PK leads to some very interesting problems, but that's out of scope, but worth mentioning. In the symmetric setting, it's a tad more complicated and this problem is a whole research area on it's own. Let's just say that there are clever ways of doing it in several circumstances.
Now signatures/MACs are essentially the same thing, with different key settings. MAC use symmetric keys and signatures use asymmetric keys. They both serve the same purpose, that is to authenticate the source of a message. For simplicity, I will refer to both of them as codes, which is an abuse of many notations, but will suffice for our purposes. All code systems have two functions: generate, denoted GEN, and verify, denoted VER, and they work as follows: generate takes in a message and outputs a tag and verify takes in a message and a tag and checks if the tag was indeed generated by the sender for that message.
Here we must note two very important things. Tags are both sender and message dependant. Thus a valid tag for one message, cannot be a valid tag for another message sent by the same person. Also, a valid tag for a message sent by one person cannot be a valid tag for the same message sent by another person. Thus the VER functions takes as input the message and the identity of the person, implicitly in the key. The main assumption here is that only the sender can generate a valid tag and thus any valid tag implies that the message was sent by them. This is very close to real world signatures and how we view them. Yes, I know that real signatures can be forged, but we also consider that in cryptography. There are some subtleties as to how this is done, but we shan't venture into that.
Finally, we come upon proofs. These are the least well-known and some would say the least understood of the three. The basic idea behind a proof system is that one party wants to prove to the other that a secret value x has some property. The property could be proven by revealing x, but then that would defeat the point of it being secret. So you need to somehow show that x has this property, but without revealing x. We seem to be in a bit f a pickle. That is, until our hero zero knowledge proofs show. These are protocols which allow you to prove certain statements about a value(s) without revealing the value and without the other person learning anything about the secret value.
A simple way to view this is by the simple statement: "Pick a card, any card!" Let's say I hand you a deck of cards and you pick one out at random and put it aside. Now I ask you what suit it is. You tell me it's a spade. I ask you to prove it. You could show me your card, but that's a secret right? Well, how about you show me 13 clubs, 13 hearts and 13 diamonds. *DING*! Now I know nothing more about your card than that it is in fact a spade. This example is great when explaining not only zero knowledge proofs, but also some of it's stranger variants. But that's all for later (read: maybe if I feel like, but don't hold your breath).
So, all in all, we covered the three basic concepts in cryptography because I'm too lazy to do real posts and the number 50 was just mainly an excuse. We hope to have a resumption of normal service soon-ish.
Monday, 20 June 2011
Let's talk money, digital money!
Alrighty then, I'm going to assume that everybody has some basic understanding of the concept of money. Next, I assume you all have some idea of how to spend money online using things like paypal, credit cards, debit cards and so forth. Also, the reason nobody that people shouldn't be able to steal your details and thus your money, if it's all done right, depends heavily on crypto. Best way to explain what I do, is to ask "Have you ever bought anything online?" When they answer in the affirmative, then I say "You're welcome."
All levity aside, let's talk about money. Money is official looking paper and bits of metal that carry some value. This value is backed by some central authority. This would normally be the central bank of the country, but could be larger such as the Eurozone. There's a whole lot of economics behind how and why this works, inflation, deflation, devaluation, exchange rates etc that I don't even pretend to understand. We all accept this at face value and move with our lives.
In the online world, it's basically the same thing. The authorities may have changed to credit card issuers, certification authorities and others, but the principle remains the same. Now, this idea doesn't sit too well with the über-privacy people. They are now afraid of all the digital "paper trail", if you will, that is created by all of this. They say that if we can use crypto to secure our transactions, then why not use it to preserve our privacy and create anonymity.
Well, there is quite a lot of cryptographic research in the field of what we like to call e-cash. All this research is completely agnostic of the economic aspects and focuses on the crypto stuff. Until a few days ago, I thought there was no real implementation of any sort of e-cash. Then I heard about Bitcoin. Just as a brief side-note, cryptographers love coins. It's some what of a convention that all randomness is generated using coins and that all e-cash schemes are described in terms of coins. There is good reasoning behind it, but I shan't go into details.
So, back to Bitcoin, which is "the first decentralised digital currency" according to the introductory video. They then go on to explain how it all works and what the advantages are. I'll just recap it for you, for completeness. Bitcoins works using identifiers called addresses, which are essentially random strings. Each user gets 1 when they download the client software. They can then create more so as to have different types of payments come and/or go to/from different addresses. All of these are tied to the same wallet. So if person has addresses a and b then sending money to either address would be the same. This is how anonymity is preserved.
When Bitcoins are sent from person to person, the transaction is hashed and signed. The hash value and digital signature are then verified by the the other users in the system. Once a transaction is verified, the Bitcoins are added to and subtracted from the relevant accounts. This is the decentralised aspect. In normal e-commerce transactions, the verification would be done by a centralised authority such as a bank or clearing house. With Bitcoins this is done in a peer-to-peer (P2P) manner. Another interesting thing is that Bitcoins are super divisible. You can go down to 0.00000001BTC. Which is the advantage of having a digital currency.
So I thought I'll give this a try. So, I downloaded the client software and started reading through the literature and all the wikis and got a feeling for how this all works. There is a whole sub-culture built based around bitcoins and it is quite fascinating. There are entire forums and IRC channels dedicated to the provision of trade in and using Bitcoins. However, as I dug deeper I discovered two very interesting points.
Firstly, Bitcoins are more of a commodity than a currency IMHO. I would like to think of Bitcoins as digital gold. This analogy is fairly apt given the way the currency works, especially with respect to generation. The generation of Bitcoins is called "mining" and involves essentially finding a pre-image for a hash function. Now this requires huge amounts of computations, but once done, a "block" is created. The creation of this block gives the creator some Bitcoins, at time of writing this stands at 50BTC. For those of us that do not have a super computer, there are still options.
The basic technique is called "pooled mining." Here what you do is you combine your computational power and split up the profits according to how much work you did. One way of doing this, if you have a reasonable large amount of computational power, is to join a mining pool. There are several ways this can be done and there are a few technical details that need to considered. Mostly these depend on a central server, which is ironically what Bitcoin was trying to avoid. For those of us with less computational power, there are alternatives, such as this (BTW if you are feeling really nice, you could try and generate a few coins for me here or you could just send some to 1KbnDDaS3UTAMZkqHSJwGuWgdApQr3wAqp).
However, there are other ways. Carrying on the gold analogy, there are people who own gold but have never even been near a mine. How? They buy it! The same goes for Bitcoins. There are some marketplaces where you can buy and sell Bitcoins for real money. It's fairly easy to compare to say a fresh fish market, let's say. Basically, the fishermen catch the fish (in this case they mine Bitcoins) and then go to a fixed place to sell it. The public knows this place and come there to buy some fish (or in our case Bitcoins). The reason I use the fish market analogy is that there is some haggling and negotiations involved, which is not unlike the Bitcoin marketplaces. In this places you can buy and/or sell Bitcoins for USD, GBP, EUR, or even SLL, the currency of Second Life. Not kidding on the last one.
Which sort of brings me to the second point. Even though Bitcoin is supposed to be decentralised, it seems to be doing it's best to achieve the exact opposite. The whole idea is to not trust this one monolithic central institution, but instead distribute the trust amongst all participants in the system, that is using P2P. There is always some sort of large trust placed in central entities, of varying size, but the point still remains. Transaction verification is still very much P2P, but not much else is. And therein lie the problems.
"With great power comes great responsibility" said Uncle Ben, rightly so. In the mining context, there are ways that servers and miners can cheat. The details of this are fairly technical and thus I will skip them. The essence is that if you control a large enough share of the mining pool, you can control the outcome of the pool, in that who receives how much money. Some people would argue that such attacks are infeasible, but I think they are possible. Further more, with all the multiple currency exchanges, it's not unlikely that somebody could be making, or trying to make, money speculating of price rises and drops. The problem here is that because it's so decentralised, there is the risk of somebody "making a run on the currency." I'm not entirely sure I know how that works, but I believe them.
The most recent problem that has surfaced is that of theft. All the "money" is stored locally on your hard drive in a single file called "wallet.dat". After reading a few of the forums, it became painfully obvious that everybody knows exactly what this file is and what it does. I thought to myself "That's quite a nice target for an attack". Hey presto, somebody did it. The thing with attacks of this kind is that they are pretty much untraceable. Remember, Bitcoin operates on anonymous identities, so even if you get the address that the money was sent to, you don't really learn anything.
So, there are some really cool things about Bitcoin and some not so cool things. I really have no strong opinions about it either way at this point in time. I am just going to let things develop and see what happens. There is a lot of talk about how these may be used to buy and sell drugs, which could lead to the whole thing being shut down, but we shall have to wait and see.
All levity aside, let's talk about money. Money is official looking paper and bits of metal that carry some value. This value is backed by some central authority. This would normally be the central bank of the country, but could be larger such as the Eurozone. There's a whole lot of economics behind how and why this works, inflation, deflation, devaluation, exchange rates etc that I don't even pretend to understand. We all accept this at face value and move with our lives.
In the online world, it's basically the same thing. The authorities may have changed to credit card issuers, certification authorities and others, but the principle remains the same. Now, this idea doesn't sit too well with the über-privacy people. They are now afraid of all the digital "paper trail", if you will, that is created by all of this. They say that if we can use crypto to secure our transactions, then why not use it to preserve our privacy and create anonymity.
Well, there is quite a lot of cryptographic research in the field of what we like to call e-cash. All this research is completely agnostic of the economic aspects and focuses on the crypto stuff. Until a few days ago, I thought there was no real implementation of any sort of e-cash. Then I heard about Bitcoin. Just as a brief side-note, cryptographers love coins. It's some what of a convention that all randomness is generated using coins and that all e-cash schemes are described in terms of coins. There is good reasoning behind it, but I shan't go into details.
So, back to Bitcoin, which is "the first decentralised digital currency" according to the introductory video. They then go on to explain how it all works and what the advantages are. I'll just recap it for you, for completeness. Bitcoins works using identifiers called addresses, which are essentially random strings. Each user gets 1 when they download the client software. They can then create more so as to have different types of payments come and/or go to/from different addresses. All of these are tied to the same wallet. So if person has addresses a and b then sending money to either address would be the same. This is how anonymity is preserved.
When Bitcoins are sent from person to person, the transaction is hashed and signed. The hash value and digital signature are then verified by the the other users in the system. Once a transaction is verified, the Bitcoins are added to and subtracted from the relevant accounts. This is the decentralised aspect. In normal e-commerce transactions, the verification would be done by a centralised authority such as a bank or clearing house. With Bitcoins this is done in a peer-to-peer (P2P) manner. Another interesting thing is that Bitcoins are super divisible. You can go down to 0.00000001BTC. Which is the advantage of having a digital currency.
So I thought I'll give this a try. So, I downloaded the client software and started reading through the literature and all the wikis and got a feeling for how this all works. There is a whole sub-culture built based around bitcoins and it is quite fascinating. There are entire forums and IRC channels dedicated to the provision of trade in and using Bitcoins. However, as I dug deeper I discovered two very interesting points.
Firstly, Bitcoins are more of a commodity than a currency IMHO. I would like to think of Bitcoins as digital gold. This analogy is fairly apt given the way the currency works, especially with respect to generation. The generation of Bitcoins is called "mining" and involves essentially finding a pre-image for a hash function. Now this requires huge amounts of computations, but once done, a "block" is created. The creation of this block gives the creator some Bitcoins, at time of writing this stands at 50BTC. For those of us that do not have a super computer, there are still options.
The basic technique is called "pooled mining." Here what you do is you combine your computational power and split up the profits according to how much work you did. One way of doing this, if you have a reasonable large amount of computational power, is to join a mining pool. There are several ways this can be done and there are a few technical details that need to considered. Mostly these depend on a central server, which is ironically what Bitcoin was trying to avoid. For those of us with less computational power, there are alternatives, such as this (BTW if you are feeling really nice, you could try and generate a few coins for me here or you could just send some to 1KbnDDaS3UTAMZkqHSJwGuWgdApQr3wAqp).
However, there are other ways. Carrying on the gold analogy, there are people who own gold but have never even been near a mine. How? They buy it! The same goes for Bitcoins. There are some marketplaces where you can buy and sell Bitcoins for real money. It's fairly easy to compare to say a fresh fish market, let's say. Basically, the fishermen catch the fish (in this case they mine Bitcoins) and then go to a fixed place to sell it. The public knows this place and come there to buy some fish (or in our case Bitcoins). The reason I use the fish market analogy is that there is some haggling and negotiations involved, which is not unlike the Bitcoin marketplaces. In this places you can buy and/or sell Bitcoins for USD, GBP, EUR, or even SLL, the currency of Second Life. Not kidding on the last one.
Which sort of brings me to the second point. Even though Bitcoin is supposed to be decentralised, it seems to be doing it's best to achieve the exact opposite. The whole idea is to not trust this one monolithic central institution, but instead distribute the trust amongst all participants in the system, that is using P2P. There is always some sort of large trust placed in central entities, of varying size, but the point still remains. Transaction verification is still very much P2P, but not much else is. And therein lie the problems.
"With great power comes great responsibility" said Uncle Ben, rightly so. In the mining context, there are ways that servers and miners can cheat. The details of this are fairly technical and thus I will skip them. The essence is that if you control a large enough share of the mining pool, you can control the outcome of the pool, in that who receives how much money. Some people would argue that such attacks are infeasible, but I think they are possible. Further more, with all the multiple currency exchanges, it's not unlikely that somebody could be making, or trying to make, money speculating of price rises and drops. The problem here is that because it's so decentralised, there is the risk of somebody "making a run on the currency." I'm not entirely sure I know how that works, but I believe them.
The most recent problem that has surfaced is that of theft. All the "money" is stored locally on your hard drive in a single file called "wallet.dat". After reading a few of the forums, it became painfully obvious that everybody knows exactly what this file is and what it does. I thought to myself "That's quite a nice target for an attack". Hey presto, somebody did it. The thing with attacks of this kind is that they are pretty much untraceable. Remember, Bitcoin operates on anonymous identities, so even if you get the address that the money was sent to, you don't really learn anything.
So, there are some really cool things about Bitcoin and some not so cool things. I really have no strong opinions about it either way at this point in time. I am just going to let things develop and see what happens. There is a lot of talk about how these may be used to buy and sell drugs, which could lead to the whole thing being shut down, but we shall have to wait and see.
Sunday, 20 February 2011
Just a litlle bit more on N vs. NP: Computational Complexity
So, after having a conversation with my friend Daniel (who will at some time help me redesign this blog), I realised that I had made one very big, and fairly erroneous, assumption with regards to P vs. NP: People know about computational complexity analysis. So, now I will correct that and explain computational complexity.
So, every computer program is basically a set of steps, which is called an algorithm. When designing any software, you first design the algorithm and then implement it. There are several reasons for this, the one of interest to us is complexity analysis. This is basically counting how many steps the program will take and how many CPU cycles are needed. The basic rule of thumb is that each addition, subtraction, multiplication, division, memory lookup and assignment take 1 CPU cycle.
Of course, this is just a heuristic measure and the actual time taken will depend on the actual hardware, but it gives us a fair idea. Another advantage is that it allows us to compare two algorithms for solving the same and find out which one is more efficient. Just to illustrate this, I will demonstrate one of the most classic examples: Adding up numbers from 1 to n.
The simplest way to do that is to have a counter and add each number to it in sequence. The pseudocode algorithm is below. Anything in green is a comment and is simply to explain what is happening.
counter += i; //Add i to the counter
next i //Increase the value of i by 1 and repeat above
output counter //Output the result
If we count the number of steps, we see we need 2 steps for initialisation (lines 1&2) and n additions and 1output. This gives a total of n+3 steps. Now we look at another way of doing this, by using this formula. In pseudocode, it would look like this:
output counter //Output the result
Now, if we count the steps, we get 1 for initialisation, 1addition, 1 multiplication, 1 division and 1 step for output. This gives us a grand total of 5 steps. Comparing that with the previous algorithm, we see that this is more efficient and does not depend on the actual input.
Most programs are more complex than this and have more complicated expressions for their running time. For these we use big-O notation. This gives us an approximate estimate of the effective running time. It also give us very nice and neat complexity classes. Looking at the example above, algorithm 1 has a running time linear in the input size, O(n), while algorithm 2 has constant running time, O(1). We also have logarithmic time O(log n), polynomial time O(n^c), exponentital time, O(c^n) and so on and so forth. Which, quite neatly brings us to the main problem: P vs. NP.
All problems in computing have a solution, but not all are efficient. Some solutions would takes minutes, others hours and some would take 100s of years to compute. Again, this all depends on your hardware, so actual time measures are not exactly useful. And, this is why we have P and NP.
All the problems that have a solution using an algorithm with time complexity that is polynomial, or less, are classed as P type problems. These can be solved in an acceptable amount of time, e.g. a couple of days. Any thing that takes more than polynomial time is classed as NP. The trick is that even though for small enough instances of NP problems, you can find a solution efficiently, it is the scaling that matters.
So, thus we can see how the above means this post makes a little bit more sense, I hope.
So, every computer program is basically a set of steps, which is called an algorithm. When designing any software, you first design the algorithm and then implement it. There are several reasons for this, the one of interest to us is complexity analysis. This is basically counting how many steps the program will take and how many CPU cycles are needed. The basic rule of thumb is that each addition, subtraction, multiplication, division, memory lookup and assignment take 1 CPU cycle.
Of course, this is just a heuristic measure and the actual time taken will depend on the actual hardware, but it gives us a fair idea. Another advantage is that it allows us to compare two algorithms for solving the same and find out which one is more efficient. Just to illustrate this, I will demonstrate one of the most classic examples: Adding up numbers from 1 to n.
The simplest way to do that is to have a counter and add each number to it in sequence. The pseudocode algorithm is below. Anything in green is a comment and is simply to explain what is happening.
int counter = 0; //Creates a counter, with an intial value of 0
int n = getUserInput(); //Asks the user to enter a number
for i = 1 to n //Repeat the following steps with i having a value from 1 to ncounter += i; //Add i to the counter
next i //Increase the value of i by 1 and repeat above
output counter //Output the result
If we count the number of steps, we see we need 2 steps for initialisation (lines 1&2) and n additions and 1output. This gives a total of n+3 steps. Now we look at another way of doing this, by using this formula. In pseudocode, it would look like this:
int n = getUserInput(); //Asks the user to enter a number
int counter = (n*(n+1))/2; //Creates a counter, and assigns it the value of the sumoutput counter //Output the result
Now, if we count the steps, we get 1 for initialisation, 1addition, 1 multiplication, 1 division and 1 step for output. This gives us a grand total of 5 steps. Comparing that with the previous algorithm, we see that this is more efficient and does not depend on the actual input.
Most programs are more complex than this and have more complicated expressions for their running time. For these we use big-O notation. This gives us an approximate estimate of the effective running time. It also give us very nice and neat complexity classes. Looking at the example above, algorithm 1 has a running time linear in the input size, O(n), while algorithm 2 has constant running time, O(1). We also have logarithmic time O(log n), polynomial time O(n^c), exponentital time, O(c^n) and so on and so forth. Which, quite neatly brings us to the main problem: P vs. NP.
All problems in computing have a solution, but not all are efficient. Some solutions would takes minutes, others hours and some would take 100s of years to compute. Again, this all depends on your hardware, so actual time measures are not exactly useful. And, this is why we have P and NP.
All the problems that have a solution using an algorithm with time complexity that is polynomial, or less, are classed as P type problems. These can be solved in an acceptable amount of time, e.g. a couple of days. Any thing that takes more than polynomial time is classed as NP. The trick is that even though for small enough instances of NP problems, you can find a solution efficiently, it is the scaling that matters.
So, thus we can see how the above means this post makes a little bit more sense, I hope.
Tuesday, 15 February 2011
A note on passphrase guessing time calculations
Alrighty then, I had few thoughts about these figures that I mentioned here and decided to some math. It all falls apart very quickly. If we actually crunch the numbers, the titular hacker's computing power changes for every equation and produces some interesting values. I will assume there is some rounding off that is done and thus we lose accuracy in the answer explaining the fluctuations.
Now, don't just take my word for it, you can join in at home. Grab a pen, paper and a calculator because we are dealing with HUGE numbers. Before we can begin, we need to do some housekeeping and define some variables. If you recall from my last post, I stated the 3 characteristics a good password should have, but we only consider the two under attack here that is length and complexity.
We define the complexity by the size of the alphabet, a, that is possible characters the password contains. For lower case a = 26, lower and upper case a = 52. With symbols it depends on how many symbols are considered valid, but in general, we have a = 52 + number of valid symbols. The length is fairly straightforward and self-explanatory. We define the total complexity of our password as
c = a^l (where ^ denotes exponentiation.)
Now, to calculate the time it would take for a hacker to guess your password, we need to know how many guesses they can make per second (or other appropriate time unit), which we denote by g. We can see that the time required is
t = c/g (in the worst case)
You may want to consider the average case, which is obtained by dividing by 2g instead of g.
If you compute g for lower case passwords with length 6 and 7, you see that there is a discrepancy in the g value. However, if you take the g from length 6 and plug it into the equation, you get a t of 4.333.... hours, which is close enough to the 4 hours they have stated. This lends credence to my rounding theory, but does not prove it.
The rest is left as an exercise for the reader. So, go on and give it a whirl. Try this with different combinations and see how long it would take somebody to crack your password.
Now, don't just take my word for it, you can join in at home. Grab a pen, paper and a calculator because we are dealing with HUGE numbers. Before we can begin, we need to do some housekeeping and define some variables. If you recall from my last post, I stated the 3 characteristics a good password should have, but we only consider the two under attack here that is length and complexity.
We define the complexity by the size of the alphabet, a, that is possible characters the password contains. For lower case a = 26, lower and upper case a = 52. With symbols it depends on how many symbols are considered valid, but in general, we have a = 52 + number of valid symbols. The length is fairly straightforward and self-explanatory. We define the total complexity of our password as
c = a^l (where ^ denotes exponentiation.)
Now, to calculate the time it would take for a hacker to guess your password, we need to know how many guesses they can make per second (or other appropriate time unit), which we denote by g. We can see that the time required is
t = c/g (in the worst case)
You may want to consider the average case, which is obtained by dividing by 2g instead of g.
If you compute g for lower case passwords with length 6 and 7, you see that there is a discrepancy in the g value. However, if you take the g from length 6 and plug it into the equation, you get a t of 4.333.... hours, which is close enough to the 4 hours they have stated. This lends credence to my rounding theory, but does not prove it.
The rest is left as an exercise for the reader. So, go on and give it a whirl. Try this with different combinations and see how long it would take somebody to crack your password.
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.
Tuesday, 10 August 2010
P vs. NP solved?
Again, I have been away for a while. I have been engulfed in my Master's Thesis (will possibly post that up as soon as its finished), which is taking up all my time. Despite that I had to come here and write a quick post about this (It will not be to my usual standard because it is rushed). Apparently we have a solution to a Millennium Problem. Just for those who are unaware, the Clay Institute of Mathematics set up the Millennium Problems, which are 7 open questions in Mathematics. These are not just any questions, but problems that have remained unsolved for hundreds of year. These are the hardest problems in Mathematics.
Previously, A proof of The Poincaré conjecture has be presented by Grigori Perelman, a Russian Mathematician. He did in fact refuse the $1M prize that goes with the Fields Medal, but the point remains, he was the first to solve a Millennium Prize Problem.
Of the 6 remaining, a proof has now emerged to the P vs. NP problem. Vinay Deolaiker of HP Labs has presented a proof that P !=(read not equal) NP. This Prof, if correct will have a massive effect on several areas of mathematics, but especially computer science and indeed cryptography. The proof is said to be 100 pages, but I cannot confirm nor deny this. I have not yet read it, but it is bound to be long. It is currently undergoing peer review, i.e. being checked and rechecked from very angle and being torn to bits by other Mathematicians.
I will try and keep you apprised of the developments and post more details about the problem and solution when i have time. Promise.
*EDIT*
So, If you follow the Link below in the comment posted by Jack, you will see some of the potential flaws in the proof. These may or may not hold and are being raised and addressed to check that the proof is robust. It may also be that there is a problem with the proof and it does not hold in its current form, but may hold with some modifications. As said before, time will tell.
Previously, A proof of The Poincaré conjecture has be presented by Grigori Perelman, a Russian Mathematician. He did in fact refuse the $1M prize that goes with the Fields Medal, but the point remains, he was the first to solve a Millennium Prize Problem.
Of the 6 remaining, a proof has now emerged to the P vs. NP problem. Vinay Deolaiker of HP Labs has presented a proof that P !=(read not equal) NP. This Prof, if correct will have a massive effect on several areas of mathematics, but especially computer science and indeed cryptography. The proof is said to be 100 pages, but I cannot confirm nor deny this. I have not yet read it, but it is bound to be long. It is currently undergoing peer review, i.e. being checked and rechecked from very angle and being torn to bits by other Mathematicians.
I will try and keep you apprised of the developments and post more details about the problem and solution when i have time. Promise.
*EDIT*
So, If you follow the Link below in the comment posted by Jack, you will see some of the potential flaws in the proof. These may or may not hold and are being raised and addressed to check that the proof is robust. It may also be that there is a problem with the proof and it does not hold in its current form, but may hold with some modifications. As said before, time will tell.
Subscribe to:
Posts (Atom)
Subscribe To
Posts
All Comments