Greetings sports fans! (I really like this. Yeah, this is going to be a thing from now on.) Today I want to fill you into one of the most asked question in the field of computer security: "Who should I tell about my latest discovery?" There are few possible answers to that questions, most commonly (in order of size): nobody, the people involved, the people affected, the research community, everybody and for completeness TeH I/\/t3W3bzzz!!1!! It's not always clear what the real answer is, or even if there is a real answer, as we shall soon see.
So, lets start of with the case I am most familiar with, as it is what I do, theoretical constructive cryptography. Sounds fancy, don't it? Basically, what I do is I look at existing schemes and try to make a better one, by either improving the extant scheme or creating a new one. In this case it's obvious that what you have now found should be shared with at least the research community and maybe the whole world if it has any real-world applications/impacts/etc. The same goes for the implementation side of cryptography.
one would assume advances in constructions or protocols are somewhat non-threating to the security of any other system. That is normally, the case, if we consider only the security of a system. A better version of a extant protocol may pose a financial threat to any parties selling the afore mentioned protocol, but it would not compromise it in any other way. The real difference is on "The Other Side of the Coin." (Heyooo!)
All silly self-referencing puns aside, what I am really referring to is cryptanalysis. These are the guys whose job it is to take cryptographic schemes and find ways to break them. They sound evil, right? Well they aren't. The idea behind cryptanalysis is to find out which schemes can and can not be broken by using a variety of techniques. If a given scheme, or indeed a class of schemes, is broken, it gives cryptographers insight to what they should not do. You may think of cryptanalysts as safety inspectors.
Now, here's the problem. Consider this, I make a new and particularly bad crypto scheme, let call it AVeryBadIdea or AVBI (C)(TM)(Pat. Pend.). I publish this scheme and I'm happy. A cryptanalyst has a look at it and breaks it completely within days of its publication. They publish the attack and life goes on. Number of people affected: 2. Doesn't sound like a problem? Well, consider the following scenario: I sell this very same cryptosystem to a couple of small time businesses to secure their data, blah, blah. Now when the attack comes out, number of people affected: 2 + all the people who bought AVBI.
Let's take this a step further. What is AVBI is used for something important, say credit cards. Well, then when if they system is broken, we have a problem. Now every credit card in existence is at threat of being used by malicious parties. Affected people: 2 + banks + credit institutions + everybody who has a credit card. Here the responsible thing to do is to tell the banks and credit institutions and they can try and find a remedy for it. The wrong thing to do is tell everybody else first.
Then you get into more complex issues. A large number of schemes have one "master secret." The gist of it is that if anybody knew this they could do whatever they wanted and not be found out. Suppose AVBI is now an industry standard of some description or the other. Somebody comes up with an attack that allows them to recover the master secret and indeed they do. What do they do? Tell the industry governing body? Sounds like a good idea right?
It is, if the concerned party/parties are not overtly hostile. The classical example of this is HDCP, as explained by Niels Ferguson. On the flip side you have the Stony Brook researchers who released the source code that allows you to do this. It's quite a grey area and I'm not sure there is a real right answer to this. There is a middle ground, which is publishing the idea of the attack, but not releasing the implementation. I believe this is what has been done by my colleagues at the Ruhr University of Bochum wrt their recent work on HDCP. However, this does also leave open the question: Could someone develop a similar attack on their own? It's possible, but then consider that the master secret is already out there, so is it really a bigger threat?
There is scope for even more potential pitfalls and possible permutations of the present problem regarding all participating parties (that's a lot of p's) and the water can get even more murky. Yes, there are clear cut consequences of cryptographic and cryptanalytic creations (and a few c's), but not always. There is so much room for error and personal judgment and it can be quite a burden trying to tackle such a dilemma. So in short, responsible disclosure can be an irresponsible thing to do.
Showing posts with label crypto. Show all posts
Showing posts with label crypto. Show all posts
Saturday, 26 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.
Saturday, 25 June 2011
Why is digital money may be a bad idea.
Basically right after I posted this, I read this. Kind of an "I told you so" moment. But apart from that I am at a lack of words for this. I've been staring at my screen for a couple of days now and I have nothing (useful or insightful) to write. Apart from the fact that this whole real currency-bitcoin exchange is a little bit hinky and this is one of the problems you can have with it. For this post, please insert the accustomed amount of wit, cynicism and all that jazz you are used to. Thanks :)
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, 12 June 2011
Quick post on how I may be kind of wrong.
If you know me at all, you will know that I have strong opinions on some things. If you don't know me, you now know that I have strong opinions on certain things. Now that everybody is caught up, let's all sit back and enjoy me being wrong-ish. I had a post earlier, which really is based on the fact that access to the Internet is a privilege, that some people abuse. Well now the United Nations has declared it a human right. My argument falls flat on it's face. I'm a big boy and I am willing to admit that in light of this, those arguments no longer hold water. Things change, people's ideas are made to be wrong, that's life.
Also, just a minor side-note: read this article!
Also, just a minor side-note: read this article!
Sunday, 13 February 2011
Passwords/phrases and client side storage
So, after we discussed this, we now move onto the promised post on where and how you should be storing your passwords. But before we get into that, we need to define the importance of passwords and password strength. But, we first need to discuss the term password, mainly the word part. People think, quite intuitively, that a password should be a single word, which is not the best idea. I prefer the term passphrase, implying multiple words and/or numbers and/or symbols. I will use the term passphrase from now on. With that out of the way, I think the next logical step is to discuss password strength.
Password strength is defined by 3 characteristics. The simplest is length, which is fairly obvious. The longer the password the harder it is to guess. I recently stumbled onto these figures, but take them with a grain of salt. They do not specify what kind of hardware was used to make these figures, so its all a bit iffy. Next is complexity, which is illustrated in the afore mentioned figures. (but just the general trend, the actually figures are still questionable). Simply put, if you have more complex passwords, with a combination of lower case, upper case, numbers and symbols, you increase the search space hugely. The third is memorability. There is no point of having "ASddeu43548&^&^ßß" as your password, because you will never remember it. A good password should be easily recalled. The higher each of these characteristics are, the stringer the password.
Now we move on to the classification of passwords. People have varying opinions on what the exact classifications are, but I use a 4-tier system, detailed below. For each tier we define the suggested password strength wrt the 3 characteristics using the terms High(H), Medium(M), Low(L). We express these as a 3-tuple of the form {Length, Complexity, Memorability} e.g. High length, medium to high complexity and low memorability is written as{H,M-H,L}
TIER I: The big guns; these are passwords for your financial accounts. Online banking, online shopping, or any account which has you financial details, PIN numbers for your ATM/debit/credit cards. These must be very memorable, hard to guess and very strong. You lose one of these, you will lose all your money.
Strength: {H,H,H}
TIER II: These are next in line in terms of importance: Login credentials. This is your school/university/office login name and password. This is how you login to systems at work (wlog) either when you are on the premises or remotely. If you lose these, then you can kiss your professional life goodbye.
Strength: {H,M-H,H}
TIER III: The mid-level identity theft type passwords: email and asocial networking. So your Facebook, HI5, LinkedIn, MySpace, GMail, Y!Mail, Hotmail, thismail, thatmail, and so on and so forth. Depending on how many e-mail addresses you have and what kind of emails you receive on them, the effects of the loss vary. If you lose your primary account's password, then the likelihood of identity theft is significant.
Strength: {M-H,M-H,M}
TIER IV: The throwaways. This is all the stuff you couldn't care less about. Logins for sites that you created just so that you could read certain articles for example. These do carry some risk, but there is a very small risk involved. This depends on several factors, which we will get into in a moment.
Strength: {M,M,L-M}
Now, we need to lay down some ground rules. No passwords should be shared across tiers. This is based on the principle of least privilege. Secondly, passwords from one tier are never stored with passwords from a lower tier. Thirdly, realisability limits; Tier 1 passwords should be unique, tier 2 & 3 should be reused sparsely, Tier 4 can be reused infinitely. Finally, each tier's passwords should be of similar strengths, as explained above. These rules and system in general are a guideline, which I try to follow, but there are grey areas. When in doubt, go for the safest option.
Now that we know how to classify our passwords, we now move onto storage of said passphrases. For tier 1 passwords, we need a highly secure storage, i.e. a password locker. These are programs that will store all your passwords for you in an encrypted form. To decrypt these, you need a master passphrase, which you define when you setup the locker. This passphrase can be thought of as as a tier 0 passphrase, which a mild abuse of notation. This master passphrase has to live in your head and must be of high length, complexity and memorability.
Next we go onto tier 2. These can be stored in programs, but need to be encrypted or locked with another master pass phrase. These should not as a rule be stored with the tier 1 passwords, but that rule tends to be broken for practicality's sake. It is quite annoying having multiple password lockers and it wouldn't be the worst thing if your most important passwords were kept together. If we do have a second password locker, we should treat the master passphrase as tier 1 password.
Now for tier 3, it you can save them in your browser, BUT, they must be encrypted with a master passphrase under all circumstances. Also you should avoid the use of cookies storing the session, caused by checking the "Remember me" check box. This is a big no-no. It's convenient, but it's not really secure. Alternately you could have a third password locker and store them there, encrypted with a tier 2 passphrase (I'm sure you can see the general trend here). If you have your tier 1 and 2 passphrases in a single locker, then this would be a second locker.
And now, tier 4. We all have a billion passwords for a billion sites that we that we use once a month or even less frequently. Theoretically, you could create a new password for each, but you will never be able to remember them all. These you can have your browser remember for you. This way you can have a unique arbitrary password for every single account. There is no real need for a master passphrase encryption, but it is recommended. As you may have guessed, this master passphrase would be a tier 3 passphrase.
These rules are quite rigid, but they are designed from a security point of view rather than a usability point of view. What is an acceptable loss of usability is very much a personal preference and that is up to you. You are welcome to bend and even break some of the rules, to make life easier for yourself. But, remember, you sacrifice security for usability and only you can strike the right balance for yourself. (I avoided saying "you have the power" because it sounds really cheesy) And so, there you have my guidelines for password storage. If in any way this makes the web just that much more secure, then I will have done my job.
Password strength is defined by 3 characteristics. The simplest is length, which is fairly obvious. The longer the password the harder it is to guess. I recently stumbled onto these figures, but take them with a grain of salt. They do not specify what kind of hardware was used to make these figures, so its all a bit iffy. Next is complexity, which is illustrated in the afore mentioned figures. (but just the general trend, the actually figures are still questionable). Simply put, if you have more complex passwords, with a combination of lower case, upper case, numbers and symbols, you increase the search space hugely. The third is memorability. There is no point of having "ASddeu43548&^&^ßß" as your password, because you will never remember it. A good password should be easily recalled. The higher each of these characteristics are, the stringer the password.
Now we move on to the classification of passwords. People have varying opinions on what the exact classifications are, but I use a 4-tier system, detailed below. For each tier we define the suggested password strength wrt the 3 characteristics using the terms High(H), Medium(M), Low(L). We express these as a 3-tuple of the form {Length, Complexity, Memorability} e.g. High length, medium to high complexity and low memorability is written as{H,M-H,L}
TIER I: The big guns; these are passwords for your financial accounts. Online banking, online shopping, or any account which has you financial details, PIN numbers for your ATM/debit/credit cards. These must be very memorable, hard to guess and very strong. You lose one of these, you will lose all your money.
Strength: {H,H,H}
TIER II: These are next in line in terms of importance: Login credentials. This is your school/university/office login name and password. This is how you login to systems at work (wlog) either when you are on the premises or remotely. If you lose these, then you can kiss your professional life goodbye.
Strength: {H,M-H,H}
TIER III: The mid-level identity theft type passwords: email and asocial networking. So your Facebook, HI5, LinkedIn, MySpace, GMail, Y!Mail, Hotmail, thismail, thatmail, and so on and so forth. Depending on how many e-mail addresses you have and what kind of emails you receive on them, the effects of the loss vary. If you lose your primary account's password, then the likelihood of identity theft is significant.
Strength: {M-H,M-H,M}
TIER IV: The throwaways. This is all the stuff you couldn't care less about. Logins for sites that you created just so that you could read certain articles for example. These do carry some risk, but there is a very small risk involved. This depends on several factors, which we will get into in a moment.
Strength: {M,M,L-M}
Now, we need to lay down some ground rules. No passwords should be shared across tiers. This is based on the principle of least privilege. Secondly, passwords from one tier are never stored with passwords from a lower tier. Thirdly, realisability limits; Tier 1 passwords should be unique, tier 2 & 3 should be reused sparsely, Tier 4 can be reused infinitely. Finally, each tier's passwords should be of similar strengths, as explained above. These rules and system in general are a guideline, which I try to follow, but there are grey areas. When in doubt, go for the safest option.
Now that we know how to classify our passwords, we now move onto storage of said passphrases. For tier 1 passwords, we need a highly secure storage, i.e. a password locker. These are programs that will store all your passwords for you in an encrypted form. To decrypt these, you need a master passphrase, which you define when you setup the locker. This passphrase can be thought of as as a tier 0 passphrase, which a mild abuse of notation. This master passphrase has to live in your head and must be of high length, complexity and memorability.
Next we go onto tier 2. These can be stored in programs, but need to be encrypted or locked with another master pass phrase. These should not as a rule be stored with the tier 1 passwords, but that rule tends to be broken for practicality's sake. It is quite annoying having multiple password lockers and it wouldn't be the worst thing if your most important passwords were kept together. If we do have a second password locker, we should treat the master passphrase as tier 1 password.
Now for tier 3, it you can save them in your browser, BUT, they must be encrypted with a master passphrase under all circumstances. Also you should avoid the use of cookies storing the session, caused by checking the "Remember me" check box. This is a big no-no. It's convenient, but it's not really secure. Alternately you could have a third password locker and store them there, encrypted with a tier 2 passphrase (I'm sure you can see the general trend here). If you have your tier 1 and 2 passphrases in a single locker, then this would be a second locker.
And now, tier 4. We all have a billion passwords for a billion sites that we that we use once a month or even less frequently. Theoretically, you could create a new password for each, but you will never be able to remember them all. These you can have your browser remember for you. This way you can have a unique arbitrary password for every single account. There is no real need for a master passphrase encryption, but it is recommended. As you may have guessed, this master passphrase would be a tier 3 passphrase.
These rules are quite rigid, but they are designed from a security point of view rather than a usability point of view. What is an acceptable loss of usability is very much a personal preference and that is up to you. You are welcome to bend and even break some of the rules, to make life easier for yourself. But, remember, you sacrifice security for usability and only you can strike the right balance for yourself. (I avoided saying "you have the power" because it sounds really cheesy) And so, there you have my guidelines for password storage. If in any way this makes the web just that much more secure, then I will have done my job.
Saturday, 12 February 2011
Passwords and server side storage.
OK, so some background reading here. I know it says I will post something about password lockers, but this is not it. Instead of considering where you store your password, we consider where they store you password. They being any website you have signed up for.
Now, it's obvious that they need to store your password. If not, the whole exercise would be pointless. The initial idea was to store the password in plaintext in a file in the server. BAD IDEA! If an attacker were to somehow get a hold of that file, you are screwed. Royally! The attacker now knows all your users' login credentials and can run amok doing all sorts of bad things. So, there were 2 bright ideas to fix this: encryption and hashing.
We note that both work in a similar way at the high level, which we will abstract as a function f. With these, when a user registers, we get the plaintext input of the password, pass and compute f(pass). We then store f(pass) instead of pass. When a user attempts to login, we get the password they entered login_pass and compute f(login_pass). We then check to see if f(login_pass) == f(pass). If they are the same, we conclude the user has entered the right password and let them in. If not, then they get an annoying error message.
Now, we straight away notice a problem: Collisions! If person A and person B both have the same password, then the stored value f(pass) will be the same. This means that if the attacker knows person A's password, they know person B's password. There is a very very small possibility that f(passA) = f(passB) and passA != (not equal) passB, but we will ignore this possibility. So, now what?
Well, the answer is salt. Well not exactly that kind of salt, but what we call a "random salt." Basically, this is a random bit-string, which or may not have some structure. So, we now have the modified password storage protocol as follows: A user registers with password pass. We compute f(pass+salt) and store (f(pass+salt), salt). When a user attempts to login, we get the password they entered login_pass and the stored salt. We compute f(login_pass+salt). We then check to see if f(login_pass+salt) == f(pass+salt). Thus, even if 2 users have the same password, the collision is not apparent due the salt. Now, they are secure, right?
Not quite yet. This depends on your choice of the function f. Let's start by discussing the symmetric key crypto option. You need to use a secure crypto scheme, such as AES, with a large enough key size. Then, we need to consider the key storage. If we store the key with the passwords file, then there is no security. If the attacker can access the password file, its safe to assume he can access the encryption key. Once, he has the encryption key, it's game over! But if you store the key safely in another location, even if the attacker gets the password file, there is still some security.
Now, we look at hash functions. You would need to use a collision-resistant hash function, which is not broken. Since the hash functions are not really keyed, there is no concern about key storage, so that makes things a bit easier. However the trade-off is the due to the fact that hash functions are designed to be computed quickly, the attacker has quite an advantage as detailed here.
Of course, the increased computational power attacks can also make it faster to break the symmetric crypto algorithm. How quickly this is don depends on known attacks for the algorithm. So, there is still a threat if your encrypted password file is compromised. Ask Gawker, they will tell you. This particular attack revealed some interesting statistics about passwords, shown here. More about these later.
For now, I have but one humble request for all admins on all servers out there: please store my, and everybody else's passwords securely. Although a lot of them do it right, some don't. This needs to change.
Now, it's obvious that they need to store your password. If not, the whole exercise would be pointless. The initial idea was to store the password in plaintext in a file in the server. BAD IDEA! If an attacker were to somehow get a hold of that file, you are screwed. Royally! The attacker now knows all your users' login credentials and can run amok doing all sorts of bad things. So, there were 2 bright ideas to fix this: encryption and hashing.
We note that both work in a similar way at the high level, which we will abstract as a function f. With these, when a user registers, we get the plaintext input of the password, pass and compute f(pass). We then store f(pass) instead of pass. When a user attempts to login, we get the password they entered login_pass and compute f(login_pass). We then check to see if f(login_pass) == f(pass). If they are the same, we conclude the user has entered the right password and let them in. If not, then they get an annoying error message.
Now, we straight away notice a problem: Collisions! If person A and person B both have the same password, then the stored value f(pass) will be the same. This means that if the attacker knows person A's password, they know person B's password. There is a very very small possibility that f(passA) = f(passB) and passA != (not equal) passB, but we will ignore this possibility. So, now what?
Well, the answer is salt. Well not exactly that kind of salt, but what we call a "random salt." Basically, this is a random bit-string, which or may not have some structure. So, we now have the modified password storage protocol as follows: A user registers with password pass. We compute f(pass+salt) and store (f(pass+salt), salt). When a user attempts to login, we get the password they entered login_pass and the stored salt. We compute f(login_pass+salt). We then check to see if f(login_pass+salt) == f(pass+salt). Thus, even if 2 users have the same password, the collision is not apparent due the salt. Now, they are secure, right?
Not quite yet. This depends on your choice of the function f. Let's start by discussing the symmetric key crypto option. You need to use a secure crypto scheme, such as AES, with a large enough key size. Then, we need to consider the key storage. If we store the key with the passwords file, then there is no security. If the attacker can access the password file, its safe to assume he can access the encryption key. Once, he has the encryption key, it's game over! But if you store the key safely in another location, even if the attacker gets the password file, there is still some security.
Now, we look at hash functions. You would need to use a collision-resistant hash function, which is not broken. Since the hash functions are not really keyed, there is no concern about key storage, so that makes things a bit easier. However the trade-off is the due to the fact that hash functions are designed to be computed quickly, the attacker has quite an advantage as detailed here.
Of course, the increased computational power attacks can also make it faster to break the symmetric crypto algorithm. How quickly this is don depends on known attacks for the algorithm. So, there is still a threat if your encrypted password file is compromised. Ask Gawker, they will tell you. This particular attack revealed some interesting statistics about passwords, shown here. More about these later.
For now, I have but one humble request for all admins on all servers out there: please store my, and everybody else's passwords securely. Although a lot of them do it right, some don't. This needs to change.
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.
Saturday, 17 July 2010
Password Storage
As you may or may not know, I have previously had a few not so pleasant words for people's activities on Facebook (cf. this post). I'm sure most people will agree that some people post unbelievable things on Facebook. Granted some of it user error, some of it is the interesting phenomenon called "Facebook rape" or simply "frape", but most of it is intentional. This has lead to the development of two very similar sites lamebook and failbook. The content is not all about people posting inexplicable things, but that is the gist of it. These sites have provided me with many hours of entertainment.
Now, you may be wondering what this has to do with password storage. This post is the link. So Ally stored all her passwords in a file, which I will for the sake of argument call pwd.doc. Now at this point that's a really bad idea. But then Ally thought about securing this file so she password protected it. Of course the most brilliant part is putting the password into the file itself, which as stated in the comments is like locking a copy of the key into a treasure chest. The pointlessness of that aside, Ally has now forgotten the password for pwd.doc, which is a bad thing.
What Ally has done is essentially a quick and easy password locker. The security of it debatable as Word document passwords can be relativly easily cracked. That aside, it is an excellent solution for what is just a bad situation. A recent study has shown that people have about 25 accounts requiring passwords and an average of 8 passwords. Each of these accounts has varying specifications for length, characters used, frequency of change and so on. This leads to sheer overload for the human brain.
The instant response is for people to write down all these passwords (as shown in the comments on the posts) which then creates a security threat. So the natural solution the that is a password locker. Instead of writing it all down on a piece of paper, you store it digitally and encrypt it. Which is is a password locker. There are several of these available on the net, ranging from free to £15 to any amount somebody thinks they can get away with. There are several issues to consider when creating a password locker, but that is for a later post. So Ally has essentially got a DIY password locker, which is now locked.
However, this was posted on Facebook, so that means that either:
a) Ally's Facebook password is stored in the browser,
b) Ally has the "Remember me" option ticked,
c) Ally remembers the password.
Going through each option one at a time, first up we have browser storage. Most people use their browsers password storage system, which stores passwords and then fills them in automatically to forms in web pages. This is an issue because a browser exploit could find all your passwords and we all know where that leads to. So door 1 has a goat behind it (for those of you unfamiliar with that reference cf. The Monty Hall Problem)
Lets look at the next option, "Remember me" which was covered in a previous post, in the 6th paragraph. So another goat
Finally, we assume Ally remembers the password. Well then, we can safely say it is more memorable that the password for pwd.doc. If we assume both passwords are equally memorable, then we can rule out this option. So we have a car, sort of. Lets say a goat-pulled car.
I could go on and on at length about passwords and their implications, but let's be honest, you'd rather hear it from someone. Bruce Schneier has several posts about passwords on his blog. Have a read through there if you are interested.
---NOTE: I will still post something about password lockers---
Now, you may be wondering what this has to do with password storage. This post is the link. So Ally stored all her passwords in a file, which I will for the sake of argument call pwd.doc. Now at this point that's a really bad idea. But then Ally thought about securing this file so she password protected it. Of course the most brilliant part is putting the password into the file itself, which as stated in the comments is like locking a copy of the key into a treasure chest. The pointlessness of that aside, Ally has now forgotten the password for pwd.doc, which is a bad thing.
What Ally has done is essentially a quick and easy password locker. The security of it debatable as Word document passwords can be relativly easily cracked. That aside, it is an excellent solution for what is just a bad situation. A recent study has shown that people have about 25 accounts requiring passwords and an average of 8 passwords. Each of these accounts has varying specifications for length, characters used, frequency of change and so on. This leads to sheer overload for the human brain.
The instant response is for people to write down all these passwords (as shown in the comments on the posts) which then creates a security threat. So the natural solution the that is a password locker. Instead of writing it all down on a piece of paper, you store it digitally and encrypt it. Which is is a password locker. There are several of these available on the net, ranging from free to £15 to any amount somebody thinks they can get away with. There are several issues to consider when creating a password locker, but that is for a later post. So Ally has essentially got a DIY password locker, which is now locked.
However, this was posted on Facebook, so that means that either:
a) Ally's Facebook password is stored in the browser,
b) Ally has the "Remember me" option ticked,
c) Ally remembers the password.
Going through each option one at a time, first up we have browser storage. Most people use their browsers password storage system, which stores passwords and then fills them in automatically to forms in web pages. This is an issue because a browser exploit could find all your passwords and we all know where that leads to. So door 1 has a goat behind it (for those of you unfamiliar with that reference cf. The Monty Hall Problem)
Lets look at the next option, "Remember me" which was covered in a previous post, in the 6th paragraph. So another goat
Finally, we assume Ally remembers the password. Well then, we can safely say it is more memorable that the password for pwd.doc. If we assume both passwords are equally memorable, then we can rule out this option. So we have a car, sort of. Lets say a goat-pulled car.
I could go on and on at length about passwords and their implications, but let's be honest, you'd rather hear it from someone. Bruce Schneier has several posts about passwords on his blog. Have a read through there if you are interested.
---NOTE: I will still post something about password lockers---
Friday, 26 March 2010
Small side-note
As I have been very busy the past couple of weeks, I haven't been keeping up-to-date with most of my TV viewing. I just recent managed to watch FlashForward S01E11. What made me laugh was the part where Dr. Simon Campos is trying to "brute force" an encryption algorithm. Their attempted accuracy made me laugh a little. As with the portrayal of most computer-based security in the media, they try, but fail at accuracy. Points for trying though.
Thursday, 11 March 2010
Fault-Based Attack on RSA
So, right in the wake of Ross Aderson's attack on Chip-And-Pin comes another scary story, this time on the famous RSA encryption scheme. Just as a quick detour, I will briefly go over the key concepts of private-/public-key cryptography. After which I will go over the attack and then the implications. Readers familiar with the concepts are welcome to skip over the next 4 paragraphs.
Private-key or symmetric cryptography involves 2 parties sharing some secret key K (and obviously a cryptographic scheme). Party A can then encrypt a message m, using K and get the resulting encryption or ciphertext c. This can then be transmitted to Party B (details of transmission and the various attacks there-in are skipped). Once Party B has received c then they can decrypt it using K and read m. Which is all fine and dandy, until you add in more people.
If you add in Party C to the system, then you need 2 more keys; 1 for A & C and 1 for B & C. IF you re-use the same key, then anybody can read the message, which is now what we want. As the system grows, the number of keys grows exponentially fast (for n users, you need (n(n-1))/2 keys). Even if you could generate and store that many keys, how do you give the keys to everybody in a secure manner? This is called the key distribution problem, which motivated public-key cryptography.
Public-key or asymmetric cyptography is based on the principal that every user creates 2 distinct but related keys, called the public key and private key. The public key, as the name suggests, is public and is published in "telephone directory" of sorts (details skipped, this leads to a few open problems). The secret key is kept secret, as the name so aptly states. Now when party A wants to send m to Party B, they look up B's public key in directory and encrypt it using that key and send c as above. B can then decrypt c using their secret key. "So that solves the problem, right?" Not quite, as public-key cryptography is much slower the private-key.
So this leads us naturally to a compromise: hybrid encryption. The principal is that you send 1 message using public-key cryptography, which contains a key for private-key cryptography. All communications from then onwards are done using private-key cryptography. Again this is just a brief idea, but should be sufficient to appreciate the problems given below.
What this attack does (full paper can be found here) is basically exploit a vulnerability that arises from the combination of hardware and software used to implement this scheme. As most of you are aware, computers have gotten really, really, REALLY fast. This is due to the fact that the transistors are getting smaller and smaller, hence allowing chip designers to fit more in the same space. Of course, this leads to the problem of bit errors; as they are smaller and closer together small changes in voltage/current/magnetic field can cause a single bit to flip, which will then propagate through the whole calculation. Having said that, there are solutions, which I really don't understand, so take my word for it, this problem is managed.
However you can still induce these errors, by passing a small, transient electrical pulse to the processor. These pulses last for less than 1 clock cycle, hence affecting at most 1 bit. Normally all this would do is give you an erroneous output, and be of no use to anybody, but this is where the software part comes in. This specific attack relies on the Fixed-Window Exponentiation (FWE) algorithm being employed. I will not detail the algorithm, those curious can look it up in the paper (link give above) and read up further if they so choose.
The basic operation in RSA is a single exponentiation, which is the message m raised to the secret key d (in standard RSA notation), which is md, modulo an RSA modulus N. Suffice to say, these calculations are not easy to perform on a chip and can be VERY SLOW. So there are several clever algorithms there that do these computations in an acceptable time, such as the FWE. it basically split the binary representation of d into "windows" and performs the calculations on that window and then moves on.
What the attack does, is induce a bit-error in the calculation, by send a small transient pulse, as described above. This generates a "broken" signature s', which the receiver will reject as incorrect. The attacker then gets broken signatures and based on some complex math, can start to extract single bits of the key. As the attacker learns more and more bits, it becomes easier to calculate the rest. I will at this point admit that even I am at a loss as to exactly how this works (mainly due to not having enough time to fully study the attack).
Although most people would think that this is just a theoretical result, but they did present the results of an experiment as well. They set up a system using an FPGA board running a SPARC-based Linux system. They managed to recover the key in 104 hours, which just over 4 days. It must be noted that this was achieved using 81 machines running a distributed algorithm, giving an estimated 1 year on a single system. Although, one must realise that most attackers would have control of several computers on which to run their algorithm, thus making the distributed system attack plausible.
So you make think "Why do I care about this RSA cryptography stuff?" Well simple, this is the basic scheme that is used in a hybrid key exchange as described above, to establish a secure connections. So if this attack is being run against you, after you have signed ~700 key-exchange messages, the attackers now know your private key.
But then you may think "700 messages is quite a lot!" Which in all fairness, for a single user, it probably is. But lets think of large corporations who on a daily basis engage in large numbers of secured connections with their customers for financial transactions(think of any medium to large e-retailer). Now they need to send signed certificates to large numbers of users (possibly in the thousands). If you were able to run this attack against them, well that would be a problem.
I'm fairly sure you would not be able to achieve the speeds of attack presented in the paper due to certain practical considerations, but you would still be in a fairly comfortable place. Even if it took you 20days to crack any retailer's secret key, that's not that bad. Once you have their secret key, you can then impersonate them very easily. Phising sites may look real, but cannot produce authentically signed certificates, which is where people sometimes catch on. With the secret key, you can sign certificates on behalf of the retailer and convince even the most aware and conscious users that you are legitimate. "Please enter your card details" and fraud ensues.
But now we look at the slightly less scary point of view: it's still fairly hard. It depends on a software/hardware combination. It is no trivial task to determine if a certain site's servers use that combination. Even if one were in possesion of such information, reliably accessing the communications channels and performing this attack would be another Herculean task. Furthermore, to remain in the spirit of this attack, one must do all of this UNDETECTED, which is easier said than done.
So, although this could be a major problem for some people, there is a simple solution: change the software. This removes half the vulnerability, and may be enough to completely invalidate this attack. Of course, you could also change all your hardware, but this more costly and a tad more difficult. There could be issues of your new hardware not working well with your old hardware, amongst other things.
But as I always say, they're two sides to the security coin; there is also the issue that it takes them 100 hours to recover a 1024-bit secret key, if you use a larger key (2048-bits or for really secure things 4096-bit) the complexity of the attack, and thus the time required, greatly increases. Also certain keys can be revoked, albeit with some difficulties. (the key revocation problem in itself entails at least at 2hour lecture, so let's no go there.) Key compromise is not the end of the world, it may cost you some reputation and issues with repaying your customers, but it may not kill you.
Private-key or symmetric cryptography involves 2 parties sharing some secret key K (and obviously a cryptographic scheme). Party A can then encrypt a message m, using K and get the resulting encryption or ciphertext c. This can then be transmitted to Party B (details of transmission and the various attacks there-in are skipped). Once Party B has received c then they can decrypt it using K and read m. Which is all fine and dandy, until you add in more people.
If you add in Party C to the system, then you need 2 more keys; 1 for A & C and 1 for B & C. IF you re-use the same key, then anybody can read the message, which is now what we want. As the system grows, the number of keys grows exponentially fast (for n users, you need (n(n-1))/2 keys). Even if you could generate and store that many keys, how do you give the keys to everybody in a secure manner? This is called the key distribution problem, which motivated public-key cryptography.
Public-key or asymmetric cyptography is based on the principal that every user creates 2 distinct but related keys, called the public key and private key. The public key, as the name suggests, is public and is published in "telephone directory" of sorts (details skipped, this leads to a few open problems). The secret key is kept secret, as the name so aptly states. Now when party A wants to send m to Party B, they look up B's public key in directory and encrypt it using that key and send c as above. B can then decrypt c using their secret key. "So that solves the problem, right?" Not quite, as public-key cryptography is much slower the private-key.
So this leads us naturally to a compromise: hybrid encryption. The principal is that you send 1 message using public-key cryptography, which contains a key for private-key cryptography. All communications from then onwards are done using private-key cryptography. Again this is just a brief idea, but should be sufficient to appreciate the problems given below.
What this attack does (full paper can be found here) is basically exploit a vulnerability that arises from the combination of hardware and software used to implement this scheme. As most of you are aware, computers have gotten really, really, REALLY fast. This is due to the fact that the transistors are getting smaller and smaller, hence allowing chip designers to fit more in the same space. Of course, this leads to the problem of bit errors; as they are smaller and closer together small changes in voltage/current/magnetic field can cause a single bit to flip, which will then propagate through the whole calculation. Having said that, there are solutions, which I really don't understand, so take my word for it, this problem is managed.
However you can still induce these errors, by passing a small, transient electrical pulse to the processor. These pulses last for less than 1 clock cycle, hence affecting at most 1 bit. Normally all this would do is give you an erroneous output, and be of no use to anybody, but this is where the software part comes in. This specific attack relies on the Fixed-Window Exponentiation (FWE) algorithm being employed. I will not detail the algorithm, those curious can look it up in the paper (link give above) and read up further if they so choose.
The basic operation in RSA is a single exponentiation, which is the message m raised to the secret key d (in standard RSA notation), which is md, modulo an RSA modulus N. Suffice to say, these calculations are not easy to perform on a chip and can be VERY SLOW. So there are several clever algorithms there that do these computations in an acceptable time, such as the FWE. it basically split the binary representation of d into "windows" and performs the calculations on that window and then moves on.
What the attack does, is induce a bit-error in the calculation, by send a small transient pulse, as described above. This generates a "broken" signature s', which the receiver will reject as incorrect. The attacker then gets broken signatures and based on some complex math, can start to extract single bits of the key. As the attacker learns more and more bits, it becomes easier to calculate the rest. I will at this point admit that even I am at a loss as to exactly how this works (mainly due to not having enough time to fully study the attack).
Although most people would think that this is just a theoretical result, but they did present the results of an experiment as well. They set up a system using an FPGA board running a SPARC-based Linux system. They managed to recover the key in 104 hours, which just over 4 days. It must be noted that this was achieved using 81 machines running a distributed algorithm, giving an estimated 1 year on a single system. Although, one must realise that most attackers would have control of several computers on which to run their algorithm, thus making the distributed system attack plausible.
So you make think "Why do I care about this RSA cryptography stuff?" Well simple, this is the basic scheme that is used in a hybrid key exchange as described above, to establish a secure connections. So if this attack is being run against you, after you have signed ~700 key-exchange messages, the attackers now know your private key.
But then you may think "700 messages is quite a lot!" Which in all fairness, for a single user, it probably is. But lets think of large corporations who on a daily basis engage in large numbers of secured connections with their customers for financial transactions(think of any medium to large e-retailer). Now they need to send signed certificates to large numbers of users (possibly in the thousands). If you were able to run this attack against them, well that would be a problem.
I'm fairly sure you would not be able to achieve the speeds of attack presented in the paper due to certain practical considerations, but you would still be in a fairly comfortable place. Even if it took you 20days to crack any retailer's secret key, that's not that bad. Once you have their secret key, you can then impersonate them very easily. Phising sites may look real, but cannot produce authentically signed certificates, which is where people sometimes catch on. With the secret key, you can sign certificates on behalf of the retailer and convince even the most aware and conscious users that you are legitimate. "Please enter your card details" and fraud ensues.
But now we look at the slightly less scary point of view: it's still fairly hard. It depends on a software/hardware combination. It is no trivial task to determine if a certain site's servers use that combination. Even if one were in possesion of such information, reliably accessing the communications channels and performing this attack would be another Herculean task. Furthermore, to remain in the spirit of this attack, one must do all of this UNDETECTED, which is easier said than done.
So, although this could be a major problem for some people, there is a simple solution: change the software. This removes half the vulnerability, and may be enough to completely invalidate this attack. Of course, you could also change all your hardware, but this more costly and a tad more difficult. There could be issues of your new hardware not working well with your old hardware, amongst other things.
But as I always say, they're two sides to the security coin; there is also the issue that it takes them 100 hours to recover a 1024-bit secret key, if you use a larger key (2048-bits or for really secure things 4096-bit) the complexity of the attack, and thus the time required, greatly increases. Also certain keys can be revoked, albeit with some difficulties. (the key revocation problem in itself entails at least at 2hour lecture, so let's no go there.) Key compromise is not the end of the world, it may cost you some reputation and issues with repaying your customers, but it may not kill you.
Friday, 5 March 2010
Slight edit on Chip-and-Pin
cf. my post on 25th Feb, there is a small correction. It adherently is possible to fool online terminals, however the point still remains that you can not fool the bank verifying the PIN
Thursday, 25 February 2010
Chip-and-PIN payement System "broken"
For those of you not familiar with the concept, I will go over it quickly. The "Chip-and-Pin" or EMV(Europay, MasterCard, VISA) system is the usage of Smart Cards, which is basically a card with a tamper-resistant chip on it, for payments via Debit/Credit cards. That is the "chip" part, so now for the "PIN", which a 4-digit code, which you use to verify that you are indeed authorised to use this card. (Some people give thier card and PIN to family members, friends, etc., which is an entire discussion in itself.)
So this system is in wide use in the United Kingdom and has become a vital part of everyday life. So obvioulsy any sort of major security failure woulde be catastrophic. Professor Ross Anderson has published such an attack, or so he claims. Even Bruce Schneier thinking its a big thing
He uses what is known as a Man-In-The-Middle attack. The basic concept is that the attacker places himself between two parties who wish to communicate. He then intercepts all communications and distorts them to serve his purposes, what ever they may be.
I would advise you watch the video demonstration which was aired on BBC Two, with the accompanying article. Go on, watch it, I can wait.
So after having seen the video, I would like to tell you why this is not the end of the world:
Agreed, that this is a technical flaw and indeed a security hole, at least from a theoretical point of view. Practically speaking, this can be done on any stolen card (doing it to your own card, while possible is pointless), but there are worse things you could do. As a consumer, if my card is stolen I perosnally don't care how my money was stolen, just that i get it back. So taking a slighty pragmatic view-point, I would say that this is an issue, but nothing to lose sleep over, that is unless you have already lost your Credit/Debit Card.
So this system is in wide use in the United Kingdom and has become a vital part of everyday life. So obvioulsy any sort of major security failure woulde be catastrophic. Professor Ross Anderson has published such an attack, or so he claims. Even Bruce Schneier thinking its a big thing
He uses what is known as a Man-In-The-Middle attack. The basic concept is that the attacker places himself between two parties who wish to communicate. He then intercepts all communications and distorts them to serve his purposes, what ever they may be.
I would advise you watch the video demonstration which was aired on BBC Two, with the accompanying article. Go on, watch it, I can wait.
So after having seen the video, I would like to tell you why this is not the end of the world:
- You need someone else's card. Arguably it is easy to get one, but the point is that if somebody has stolen your card, there are far worse things they can do than buy a bottle of water. There are several ways to use a card, without knowing the PIN, over the phone for example. Physical possesion of the card would allow you to use it in several circumstance without knowing the PIN.
- It only works in offline terminals. So you can't put it in an ATM or use it in any store where the transaction is verified online witht he bank. In that case, a cryptogram contain the PIN is sent to the bank which will then verify the PIN. You would well pressed to be able to fake that.
- You need a specific setup of reader, as the one used in the demo. Ofcourse one could get better at hiding the wire and the actual "performance" of the attack, but no amount of practice would allow you to hand a card with a wire on it to a merchant and not raise suspicions.
- The hardware and software is really non-trivial to construct. The script is in Python, which is a difficult language to master and all the harware is custom built. So really the kit is not absolutly accessible.
- If the card has been cancelled, this attack will not work. So again, because the attacker needs to steal your card, they only have the time between stealing the card and you reporting it stolen and cancelling your card.
Agreed, that this is a technical flaw and indeed a security hole, at least from a theoretical point of view. Practically speaking, this can be done on any stolen card (doing it to your own card, while possible is pointless), but there are worse things you could do. As a consumer, if my card is stolen I perosnally don't care how my money was stolen, just that i get it back. So taking a slighty pragmatic view-point, I would say that this is an issue, but nothing to lose sleep over, that is unless you have already lost your Credit/Debit Card.
Subscribe to:
Posts (Atom)
Subscribe To
Posts
All Comments