We all know about tracking cookies and privacy. However, according to EFF it isn't necessary to use cookies to do a fair job of tracking your browser activities. According to their research browsers give 10.5 bits of identifying information in the userAgent string, which is supplied to the web server with every request. This is around a third of the information required to uniquely identify you.
They have set up a website to gather more data and give you a 'uniqueness' indicator for your browser, which you can find here. This data set is growing quite rapidly and will tell you how many of the userAgent strings they have received that are the same as yours. I managed to find a machine to test that was unique amongst the 195,000 machines they have tested. This means that someone could potentially track that machine even if cookies are disabled. Even if you come out with the same userAgent string as others, you can be narrowed down by using geolocation of your IP, browser plugins, installed fonts, screen resolution, etc. This isn't a new idea and others have tried it, like browserrecon. Of course if you have a static IP address then you are fairly easy to track anyway.
Various suggestions are made to help protect yourself, such as don't allow scripts to run on untrusted websites, which is fairly obvious. However, although this may reduce the amount of data given out from highs of 15.5 bits on a Blackberry or 15.3 bits on Debian, this won't stop the whole problem. It seems like the worst devices for giving out identifying information are Blackberry and Android phones, with minimum figures of over 12 bits. The best combination would seem to be FireFox running on Windows, which can be controlled down to only 4.6 bits (although highs are around double this), but this could just be because it's the most common combination.
What can you do? Don't visit untrusted sites. Also, you could change your userAgent string. It is just a text string stating the capabilities of your machine so that the web server can customise content to suit you. However, there is no real harm in tweaking this to fall in line with more common strings so that you are harder to track. You have to be careful here, because just removing most of the information will probably make your userAgent string unique. Alternatively, you could regularly change the string. Perhaps browsers should change the string with every connection? Plugins could do this, like User Agent Switcher. This would allow you to use different strings across different sites. Maybe hiding certain activities by temporarily switching the userAgent string would be useful.
FireFox and Opera are both quite easy to configure - type about:config or opera:config in the address bar respectively and navigate to the userAgent options. Internet Explorer is slightly more trickey, in that you have to make a registry change to alter the userAgent string. Navigate to [HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Internet Settings\5.0\User Agent] in regedit. Here you can create string values for 'Compatible', 'Version' and 'Platform' to control what is sent. Under the 'Post Platform' key are a whole bunch of additional parameters that will be added to the string, so you can change or remove these.
Friday, 29 January 2010
Friday, 15 January 2010
How secure is your AV Product?
We all use (or at least we should all use) an Anti-Virus (AV) product on our computer to protect it from malware (yes, that includes you Mac and Linux users as well). Rogue Anti-Malware is on the increase and users should be wary of what they install, but if we do choose a big vendor and pay money for it, does it protect our machine from all threats?
Well the answer is no. No security product can be 100% secure, but how secure are they actually? There have been a number of recent surveys and their results show that things are probably improving, but there's still a significant gap. AV-Comparatives.org showed that in their tests, G Data was the best with a 99.8% detection rate of known malware, with Norman being the worst of the 16 at 84.8%. Known malware was taken to be malware from a period of one year that ended 8 months prior to the test. This is important to stress; these weren't new malware instances, these were old known malware that all vendors will have seen and had time to develop their product to combat.
There's another potential issue as well. What settings do you use on your AV product? Do you use the default settings? Several products do come with the highest protection set as default, but not all. Kaspersky, Symantec and Sophos, for example, don't have the highest security settings by default (although Sophos, to their credit, asked AV-Comparatives to test them with default settings, unlike the other two who asked to be tested with settings changed to high security). McAfee use a cloud-based technology called Artemis, which is on by default, but requires an internet connection. Their test scores come down from 98.7% detection rate when online to 92.6% when offline. So be wary about the settings that you use and the mode of use as well, as it can make a big difference.
AV-Test.org also performed similar tests with more current malware, with similar results. In their tests, Symantec came out top with a score of 98% malware detected and Trend Micro with 83.3%. I'll pick out a few big names so that I can give you average figures from both testing labs.
This isn't the full story though. The above tests are detected existing malware. There are two other metrics that we need to look at. The first of these is the removal or blocking rate. This is the percentage of malware instances that were blocked or removed by the AV product. The others will have infected the machine. AV-Test.org correctly point out that this is a much more important metric than detected malware, as if an AV product detects it but still allows it to install, then you are only marginally better off than if you didn't know about it at all - your machine is still infected. Their tests show that the blocking rates are a chunk down from the detection rates, with the best now being PC Tools at 94.8% and the worst being CA Internet Security at 73.5%. Blocking rate figures for the set of AV products are also given in the table above.
The final thing to consider is the detection rate of new malware that hasn't been seen before, i.e. from live attacks. Cyveillance performed a set of tests sending live attack malware through a set of the top AV products on a daily basis to see how they performed. In their tests, cloud-based McAfee came out top at 44% and VirusBuster bottom on 16%. AV-Comparatives performed a similar test and came out with slightly better results, ranging from AVIRA on 74% down to Norman on 32%. Again, I have averaged their figures to include in the table above.
Conclusion: you could use more than one AV product as long as they don't conflict. However, it is essential that you keep the product up-to-date at all times and configure it for maximum protection.
Well the answer is no. No security product can be 100% secure, but how secure are they actually? There have been a number of recent surveys and their results show that things are probably improving, but there's still a significant gap. AV-Comparatives.org showed that in their tests, G Data was the best with a 99.8% detection rate of known malware, with Norman being the worst of the 16 at 84.8%. Known malware was taken to be malware from a period of one year that ended 8 months prior to the test. This is important to stress; these weren't new malware instances, these were old known malware that all vendors will have seen and had time to develop their product to combat.
There's another potential issue as well. What settings do you use on your AV product? Do you use the default settings? Several products do come with the highest protection set as default, but not all. Kaspersky, Symantec and Sophos, for example, don't have the highest security settings by default (although Sophos, to their credit, asked AV-Comparatives to test them with default settings, unlike the other two who asked to be tested with settings changed to high security). McAfee use a cloud-based technology called Artemis, which is on by default, but requires an internet connection. Their test scores come down from 98.7% detection rate when online to 92.6% when offline. So be wary about the settings that you use and the mode of use as well, as it can make a big difference.
AV-Test.org also performed similar tests with more current malware, with similar results. In their tests, Symantec came out top with a score of 98% malware detected and Trend Micro with 83.3%. I'll pick out a few big names so that I can give you average figures from both testing labs.
| Product | Existing Detection | Blocking | Live Detection |
|---|---|---|---|
| Symantec | 98.2% | 92.8% | 35.5% |
| Kaspersky | 96.1% | 89.9% | 41.0% |
| McAfee | 93.0% | 86.7% | 45.5% |
| AVG | 93.1% | 84.2% | 40.0% |
| F-Secure | 91.9% | 80.2% | 42.0% |
This isn't the full story though. The above tests are detected existing malware. There are two other metrics that we need to look at. The first of these is the removal or blocking rate. This is the percentage of malware instances that were blocked or removed by the AV product. The others will have infected the machine. AV-Test.org correctly point out that this is a much more important metric than detected malware, as if an AV product detects it but still allows it to install, then you are only marginally better off than if you didn't know about it at all - your machine is still infected. Their tests show that the blocking rates are a chunk down from the detection rates, with the best now being PC Tools at 94.8% and the worst being CA Internet Security at 73.5%. Blocking rate figures for the set of AV products are also given in the table above.
The final thing to consider is the detection rate of new malware that hasn't been seen before, i.e. from live attacks. Cyveillance performed a set of tests sending live attack malware through a set of the top AV products on a daily basis to see how they performed. In their tests, cloud-based McAfee came out top at 44% and VirusBuster bottom on 16%. AV-Comparatives performed a similar test and came out with slightly better results, ranging from AVIRA on 74% down to Norman on 32%. Again, I have averaged their figures to include in the table above.
Conclusion: you could use more than one AV product as long as they don't conflict. However, it is essential that you keep the product up-to-date at all times and configure it for maximum protection.
Pragmatic Approach to Security
When dealing with security, we must be pragmatic. The resources that an organisation can dedicate to security are limited in terms of time, staff, budget, expertise, etc. Also, perfectly secure systems do not exist - accidents, attacks and penetrations will happen in the end, so plan to deal with them at the outset. Recovery after a breach must be just as much of the planning as the mitigation of the breach in the first place. We all insure our cars, hoping never to call on it, and then try desperately to avoid having any accidents, getting the car stolen or vandalized. However, in the end, a lot of us will end up claiming on the insurance at some point, no matter how careful we are. The same is true of security.
We have to see the bigger picture and align the use of resources with the company's mission. There comes a point when a small amount more security costs a lot more money, time, management effort and is much less user-friendly. Wouldn't it impact the business less if we take the hit and recover quickly and smoothly? Often the answer is yes. We have to find the optimal solution for that particular organisation. The graph above shows that as we increase the security of our system the cost associated with breaches of security comes down, as we have fewer breaches. However, this cost will never be zero, as we will always have breaches. Indeed, breaches may still cost a lot of money but, hopefully they will be few and far between. Conversely, as our security increases, the cost of our countermeasures goes up. Therefore, the total cost will decrease with more security initially, then increase again as the countermeasures become increasingly expensive for less and less improvement to security.
These curves and the overall graph will be different for each organisation. The point I'm trying to make is that we should accept that there is no perfect security, do the best job we can, given the resources allocated, and plan for how we will recover from any breaches in security, be they minor or major. The problem comes when deciding what assets should be given priority and what is the best allocation of resources for a specific organisation. This is where security risk assessments come in. For more about security assessments and risks, see my previous post.
We have to see the bigger picture and align the use of resources with the company's mission. There comes a point when a small amount more security costs a lot more money, time, management effort and is much less user-friendly. Wouldn't it impact the business less if we take the hit and recover quickly and smoothly? Often the answer is yes. We have to find the optimal solution for that particular organisation. The graph above shows that as we increase the security of our system the cost associated with breaches of security comes down, as we have fewer breaches. However, this cost will never be zero, as we will always have breaches. Indeed, breaches may still cost a lot of money but, hopefully they will be few and far between. Conversely, as our security increases, the cost of our countermeasures goes up. Therefore, the total cost will decrease with more security initially, then increase again as the countermeasures become increasingly expensive for less and less improvement to security.
These curves and the overall graph will be different for each organisation. The point I'm trying to make is that we should accept that there is no perfect security, do the best job we can, given the resources allocated, and plan for how we will recover from any breaches in security, be they minor or major. The problem comes when deciding what assets should be given priority and what is the best allocation of resources for a specific organisation. This is where security risk assessments come in. For more about security assessments and risks, see my previous post.
Friday, 11 December 2009
Contactless Credit Card and ID Card Skimming
This news post was brought to my attention, showing a steel-woven wallet to keep RFID credit cards safe. To some this may sound a bit far fetched and to others nothing new or to worry about, but hear me out.
With new contactless credit cards you can make small purchases without resorting to the Chip-and-PIN transaction that is most common. Instead, you just 'touch' your card on the reader and away you go. The problem with this is that you cannot turn your card off. I can bring the reader to you; I just need proximity. These readers are small and pocketable, and I can read your card without you taking it out of your pocket. The more high-powered my reader, the further away from you I can be to read your card. Initially, the cards gave out the name on the card, the card number and the expiration date. After people showed that it was easy to skim this information off the card, most have removed the cardholder's name from this list. They have also introduced transaction IDs to help protect the cards from being cloned. However, as the introduction of RFID identity cards increases, we will be giving the cardholder's name out again on those.
It has been argued that it is more productive to attack the databases of card details, and still far too easy, so people won't bother trying to read the cards in your wallet. However, I can still obtain a legitimate payment reader and just read your details off and collect your money directly, even if I can't clone the card. In the UK, these contactless transactions are for small amounts of money (£5-£10 typically), but I can collect that from you without your knowledge in a variety of ways. I can use a small pocket device to take a payment from your card directly, but this has to be one at a time and, in some countries, only for small amounts of money. (See the video below for a mobile phone that can process contactless credit card transactions.)
Maybe this isn't worth it to anyone but a petty criminal, but it is relatively easy and cheap. Another way would be to go to a crowded area (public celebrations or gatherings of tens or hundreds of thousands of people for example) and use a high-powered reader to read lots of cards at once. If I can steal £10 from 100,000 people, that's £1m in an afternoon! Somewhere in the region of half a million people gather in Trafalgar Square, and environ, for the New Year celebrations and similar numbers for the Chinese New Year celebrations a little while later.
RFID readers are all over the place and we don't pay them any mind. Shops use RFID readers to catch shoplifters at the entrances. Do you categorically know that they aren't reading your cards instead of catching shoplifters? Would you notice an extra £10 transaction in a shop that you did buy something in? All of our buses and tube stations in London use RFID readers for ticketing. A vast number of commuters will have their Oyster card in their wallet or purse along with their other cards. They don't remove the Oyster card to touch it, they just touch the whole wallet. I could read the other card information at the same time. In fact, do we know that these details aren't logged and just ignored? If they are logged, then maybe we could attack Transport for London's computer system and extract people's credit card details.
With new contactless credit cards you can make small purchases without resorting to the Chip-and-PIN transaction that is most common. Instead, you just 'touch' your card on the reader and away you go. The problem with this is that you cannot turn your card off. I can bring the reader to you; I just need proximity. These readers are small and pocketable, and I can read your card without you taking it out of your pocket. The more high-powered my reader, the further away from you I can be to read your card. Initially, the cards gave out the name on the card, the card number and the expiration date. After people showed that it was easy to skim this information off the card, most have removed the cardholder's name from this list. They have also introduced transaction IDs to help protect the cards from being cloned. However, as the introduction of RFID identity cards increases, we will be giving the cardholder's name out again on those.
It has been argued that it is more productive to attack the databases of card details, and still far too easy, so people won't bother trying to read the cards in your wallet. However, I can still obtain a legitimate payment reader and just read your details off and collect your money directly, even if I can't clone the card. In the UK, these contactless transactions are for small amounts of money (£5-£10 typically), but I can collect that from you without your knowledge in a variety of ways. I can use a small pocket device to take a payment from your card directly, but this has to be one at a time and, in some countries, only for small amounts of money. (See the video below for a mobile phone that can process contactless credit card transactions.)
Maybe this isn't worth it to anyone but a petty criminal, but it is relatively easy and cheap. Another way would be to go to a crowded area (public celebrations or gatherings of tens or hundreds of thousands of people for example) and use a high-powered reader to read lots of cards at once. If I can steal £10 from 100,000 people, that's £1m in an afternoon! Somewhere in the region of half a million people gather in Trafalgar Square, and environ, for the New Year celebrations and similar numbers for the Chinese New Year celebrations a little while later.
RFID readers are all over the place and we don't pay them any mind. Shops use RFID readers to catch shoplifters at the entrances. Do you categorically know that they aren't reading your cards instead of catching shoplifters? Would you notice an extra £10 transaction in a shop that you did buy something in? All of our buses and tube stations in London use RFID readers for ticketing. A vast number of commuters will have their Oyster card in their wallet or purse along with their other cards. They don't remove the Oyster card to touch it, they just touch the whole wallet. I could read the other card information at the same time. In fact, do we know that these details aren't logged and just ignored? If they are logged, then maybe we could attack Transport for London's computer system and extract people's credit card details.
Maybe people won't do this with credit cards. What about large banks or other companies that use RFID door entry cards and ID cards? I could read their ID and possibly gain access to their building. Will the ID give me a username to work with? If I can gain physical access to a bank building then I have a huge array of attack vectors at my disposal; it is critical to keep the hackers out.
Even if a hacker can't clone these types of cards, they can still collect information about people and about companies. It is perfectly possible to identify all the employees of a company using RFID cards for door entry, as you can have a high-powered reader near their entrance or at public transport stations. This now gives a social engineer a target and some information to use. Maybe we should all be holding our wallets over the top of shop gates and away from other readers or buy one of the shielded wallets from people like ID Stronghold or Herrington.
Friday, 4 December 2009
Proposed Pseudo-Code for Hacking Process
It is quite common in Information Systems to use pseudo code to describe a process. I have often thought that the same principle can be applied to the process of hacking an organisation, which may help people understand the process and how to protect themselves. Below is my proposal for this pseduo-code for the hacking process. This is very much a work in progress. I would welcome feedback on it and I will update it as suggestions are made or as I feel it needs revising.
organisation = proposed target
organisation.footprint(value, effort, risk)
profit = value - (effort * risk)
if profit > 0 then
organisation.enumerate()
select attack_type
case DoS
engage_botnet(myBotnet)
myBotnet.launchDDoS(organisation)
case Access
organisation.gainAccess(myAccount)
myAccount.Elevate()
organisation.installBackdoor(myAccount)
organisation.cleanUP()
end select
else
exit
end if
This highlights the fact that we only need enough security to make it not worthwhile attacking, i.e. it will cost the attacker more to compromise our system than they will gain. Who would spend £1m to get £10 worth of information? We don't need (indeed cannot have) absolute security, just enough to protect our system. It also highlights another interesting point. Perhaps we should make our countermeasures public - not the actual implementational details or versions, but the fact that they are in place, e.g. that we have an IDS. Consider blatant versus hidden CCTV cameras. Cameras in plain sight deter most criminals, whereas hidden cameras spy on criminals while they perpetrate their crime.
We want to make the risk of being caught/prosecuted value high, so that hackers require a higher value:effort ratio, which we won't give them. Given two identically protected organisations with the same value, would you attack the one that doesn't monitor activity or the one that does?
Obviously, the above is very vague and doesn't provide methods to complete these tasks, but that is not the point of this post. Backdoors and Trojans are usually relatively easy to install if you have the right level of access to the system, so much of your security is going to hang on stopping a hacker from gaining access. Gaining access to an organisation is usually performed in one of four main ways:
organisation = proposed target
organisation.footprint(value, effort, risk)
profit = value - (effort * risk)
if profit > 0 then
organisation.enumerate()
select attack_type
case DoS
engage_botnet(myBotnet)
myBotnet.launchDDoS(organisation)
case Access
organisation.gainAccess(myAccount)
myAccount.Elevate()
organisation.installBackdoor(myAccount)
organisation.cleanUP()
end select
else
exit
end if
This highlights the fact that we only need enough security to make it not worthwhile attacking, i.e. it will cost the attacker more to compromise our system than they will gain. Who would spend £1m to get £10 worth of information? We don't need (indeed cannot have) absolute security, just enough to protect our system. It also highlights another interesting point. Perhaps we should make our countermeasures public - not the actual implementational details or versions, but the fact that they are in place, e.g. that we have an IDS. Consider blatant versus hidden CCTV cameras. Cameras in plain sight deter most criminals, whereas hidden cameras spy on criminals while they perpetrate their crime.
We want to make the risk of being caught/prosecuted value high, so that hackers require a higher value:effort ratio, which we won't give them. Given two identically protected organisations with the same value, would you attack the one that doesn't monitor activity or the one that does?
Obviously, the above is very vague and doesn't provide methods to complete these tasks, but that is not the point of this post. Backdoors and Trojans are usually relatively easy to install if you have the right level of access to the system, so much of your security is going to hang on stopping a hacker from gaining access. Gaining access to an organisation is usually performed in one of four main ways:
- Malware
- Sniffing
- Direct Attack
- Social Engineering
- Installing Antivirus/Antispyware
- Latest OS and Application Patches
- Enterprise-level firewall, with IDS/IPS, AV, etc.
- Personal firewalls on all mobile devices
- Secure, hardened configurations
- Browser lock-down
- Encrypted communication (e.g. SSL/TLS, VPN, etc.)
- User Education!
The last point is often overlooked as a critical security practice. Please feel free to comment.
Thursday, 26 November 2009
Blackboard (in)Security
The University recently recently paid for a vulnerability assessment and penetration test, which came back saying that, apart from a few minor things, everything was fine and secure. I take issue with this finding for several reasons, most of which I won't go into here. Now, I haven't actually seen the report produced by the company, but I have had verbal reports from the IT technicians that 'nothing serious' was found.
The University uses a hateful product called Blackboard as a Virtual Learning Management System. This is a web-based application allowing access to learning materials, grades, etc., from anywhere in the world. The problem is that it doesn't use an encrypted connection and uses a simple Session ID cookie to assert that you are an authenticated user. There are two problems with this. Firstly, if I capture your cookie and send it with my HTTP request, then I will be treated as you and can see or do anything as you. Secondly, and much more importantly, is that the username and password are sent in plaintext!
I shouldn't have to explain why this is such a bad idea, but I can't understand why this wasn't picked up as a major security hole. A simple packet sniffer will pick up anyone's username and password, giving full access to the network and other services, such as email, home directories, etc. The trouble is that it's not just students who login to this service, all the academics and admin staff do as well. You can imagine what could be done by grabbing a lecturer's username and password.
How easy is it to actually launch a sniffing attack? Well, surprisingly easy (unless you are a pen tester, in which case it won't surprise you at all). Consider the fact that people do connect to this service from public wireless hotspots or from shared networks, such as the halls of residence or the university network itself. It isn't difficult for someone to sniff the network and extract the user's password. 'MAJOR SECURITY WEAKNESS' not 'nothing serious'.
I advise people to connect to Blackboard instances via SSL connections at the very least. It doesn't stop all the attacks, but it will stop simple packet sniffing.
The University uses a hateful product called Blackboard as a Virtual Learning Management System. This is a web-based application allowing access to learning materials, grades, etc., from anywhere in the world. The problem is that it doesn't use an encrypted connection and uses a simple Session ID cookie to assert that you are an authenticated user. There are two problems with this. Firstly, if I capture your cookie and send it with my HTTP request, then I will be treated as you and can see or do anything as you. Secondly, and much more importantly, is that the username and password are sent in plaintext!
I shouldn't have to explain why this is such a bad idea, but I can't understand why this wasn't picked up as a major security hole. A simple packet sniffer will pick up anyone's username and password, giving full access to the network and other services, such as email, home directories, etc. The trouble is that it's not just students who login to this service, all the academics and admin staff do as well. You can imagine what could be done by grabbing a lecturer's username and password.
How easy is it to actually launch a sniffing attack? Well, surprisingly easy (unless you are a pen tester, in which case it won't surprise you at all). Consider the fact that people do connect to this service from public wireless hotspots or from shared networks, such as the halls of residence or the university network itself. It isn't difficult for someone to sniff the network and extract the user's password. 'MAJOR SECURITY WEAKNESS' not 'nothing serious'.
I advise people to connect to Blackboard instances via SSL connections at the very least. It doesn't stop all the attacks, but it will stop simple packet sniffing.
Wednesday, 11 November 2009
Secret Sharing Algorithm for Protecting Files in the Cloud
Data stored in the cloud can be compromised or lost (see my previous post). So, we have to come up with a way to secure those files. We can encrypt them before storing them in the cloud, which sorts out the disclosure aspects. However, what if the data is lost due to some catastrophe befalling the cloud service provider? We could store it on more than one cloud service and encrypt it before we send it off. Each of them will have the same file. What if we use an insecure, easily guessable password to protect the file, or the same one to protect all files? I have often thought that secret sharing algorithms could be employed to good effect in these circumstances instead.
What are secret sharing algorithms? They are algorithms that will share a secret between several parties, such that none of them can know the secret without the help of others. Either all or a subset of them will need to get together and put their parts together to obtain the original secret. A simplistic solution can be achieved by XORing the secret with a random number, then giving the result to one party and the random number to the other. Neither one can find out what the secret was without the other. To retrieve the secret they only need to XOR the two parts together again. This can be extended to any number of parties.
A more sophisticated way would be to allow the secret to be retrieved from a subset of the parts distributed. In the previous example, if any of the parties loses their part, or refuses to disclose it, then nobody can reveal the secret. This isn't much good if one of our cloud service providers fails. On the other hand, if we can share the secret between three people, but only require any two to regenerate the original, then we have some redundancy. This is an example of a (k,n) threshold scheme with k=2 and n=3.
How do we achieve this though? Well, Adi Shamir proposed a simple secure secret sharing algorithm. It is based on drawing graphs. To uniquely define a straight line, you need two points on that line. Similarly, to define a parabola you need three points. A cubic requires four, etc. So, we can distribute points on a line to each party we want to share the secret with. The order of the line will determine how many of them need to get together to regenerate it. So, we could define a random straight line and distribute three points on it to three different parties. However, only two of them need to get together to regenerate the original secret.
We set up a (k,n) threshold scheme by setting the free coefficient to be the secret and then choosing random numbers for each of the other coefficients. The polynomial then becomes the following:
where a0 is our secret. Now we can distribute points on the line to each of the n parties simply by calculating y for a series of different values for x. We can use the Lagrange Basis Polynomials to reconstruct the equation of the line from k points. However, we do not need to reconstruct the whole line, we are only interested in the free term. This simplifies the equations that we need to use. For example, if we have a straight line, then we only need two points (x0,y0) and (x1,y1). We can then calculate a0 as follows:
Similarly, for a parabola and three points (x0,y0), (x1,y1) and (x2,y2) we have:
This should be fairly simple to implement and use. You would need to sign up to a few cloud services, but you wouldn't have all your eggs in one basket and you wouldn't be reliant on weak passwords.
What are secret sharing algorithms? They are algorithms that will share a secret between several parties, such that none of them can know the secret without the help of others. Either all or a subset of them will need to get together and put their parts together to obtain the original secret. A simplistic solution can be achieved by XORing the secret with a random number, then giving the result to one party and the random number to the other. Neither one can find out what the secret was without the other. To retrieve the secret they only need to XOR the two parts together again. This can be extended to any number of parties.
A more sophisticated way would be to allow the secret to be retrieved from a subset of the parts distributed. In the previous example, if any of the parties loses their part, or refuses to disclose it, then nobody can reveal the secret. This isn't much good if one of our cloud service providers fails. On the other hand, if we can share the secret between three people, but only require any two to regenerate the original, then we have some redundancy. This is an example of a (k,n) threshold scheme with k=2 and n=3.
How do we achieve this though? Well, Adi Shamir proposed a simple secure secret sharing algorithm. It is based on drawing graphs. To uniquely define a straight line, you need two points on that line. Similarly, to define a parabola you need three points. A cubic requires four, etc. So, we can distribute points on a line to each party we want to share the secret with. The order of the line will determine how many of them need to get together to regenerate it. So, we could define a random straight line and distribute three points on it to three different parties. However, only two of them need to get together to regenerate the original secret.
We set up a (k,n) threshold scheme by setting the free coefficient to be the secret and then choosing random numbers for each of the other coefficients. The polynomial then becomes the following:
where a0 is our secret. Now we can distribute points on the line to each of the n parties simply by calculating y for a series of different values for x. We can use the Lagrange Basis Polynomials to reconstruct the equation of the line from k points. However, we do not need to reconstruct the whole line, we are only interested in the free term. This simplifies the equations that we need to use. For example, if we have a straight line, then we only need two points (x0,y0) and (x1,y1). We can then calculate a0 as follows:
Similarly, for a parabola and three points (x0,y0), (x1,y1) and (x2,y2) we have:
This should be fairly simple to implement and use. You would need to sign up to a few cloud services, but you wouldn't have all your eggs in one basket and you wouldn't be reliant on weak passwords.
Subscribe to:
Posts (Atom)