Thanks to open-source hardware, there has never been so much choice and so much opportunity to learn.
My recommendations for today's tinkerer are: - Raspberry Pi (not fully open source but close enough) and the wiring Pi library http://wiringpi.com/ - The esp8266 boards: Super cheap Arduino compatible WIFI boards. - Any SAMD21 ARM cortex M0 board like the Arduino Zero, Sparkfun SAMD21 breakout, or the Adafruit Feather M0. - STM32 "blue pill" boards. Super cheap on ebay and powerfull.
In theory, you don't need hardware to be open source just to "tinker" with it. But in reality, if you want to truly learn stuff, open source hardware is great. You can take a look at the schematics, learn piece by piece from others: power supply circuits, reset, oscillators, micro-controllers,...
For example take a look at the Sparkfun SAMD21 breakout schematics here: https://cdn.sparkfun.com/datas... You'll see the leds, the usb, the battery power circuit, the micro-controller and headers, all nicely broken down in separate blocks that you can learn from and re-use.
After a while, you will be able to make your own boards. YES! ** That the best part of it all! **
Myself I started with a simple Arduino UNO and a couple of years later, I'm about to launch my own IoT Arduino compatible platform, fully designed and implemented in the garage of our house: http://omzlo.com/
I fully agree. I like the GTK+ API and I still continue to use it because shifting to another toolkit for my apps would be costly. But I'm loosing patience:
GTK+ development has become an unprofessional mess. Functions get deprecated even with minor version changes: you develop your app with version 3.xx and distribute it. Then people move to 3.yy (where yy>xx) and bang your app does not work anymore because someone decided to *remove* a function from GTK+ without any consideration for existing apps out there. Sometimes the fix involves a new function that does not exist in the previous version of the library, so you can't even find a real fix that would work with all versions from 3.xx and above. You just add some ugly preprocessor macros in your code to deal with different versions of GTK+ at source level...
With the safe harbour agreement american companies basically "promise" to follow some rules related to privacy, which are compatible with European values. But to make such an approach effective, someone has to verify that the "promises" are real and eventually impose sanctions if they are not. That someone is -- in theory -- the FTC.
The problem with safe harbor is that it is been very weakly enforced. In the first decade since it was created, there has been no real enforcement action that I've heard of. This gives the impression that Safe Harbor is pretty toothless. FTC has only recently (2014) began to enforce this framework, because Europeans threatened to abandon it.
My experience as an end-user in a research project:
I've tried to install OpenStack on a small group of 4 machines (a controller, a network manager and two compute node). It was a real mess to install. The documentation contains omissions and mistakes. You need to write your own shell scripts to get the work done (and redone). Understanding what went wrong from the cryptic python debug messages is like banging your head against a wall. The only way I finally was able to test things was to scale back to a "one-node" system (everything on the same machine) and use DevStack. That works great but it's really far from a "cloud". You need to be HP or RackSpace to get this working well I guess.
Contrast that with OpenNebula. This platform is much less hyped about but it works much better. Even when you hit a bump on the road, you can actually understand the logs, and even debug stuff yourself. I got a 4 node system working with all storage on iSCSI and I can add more compute nodes seamlessly.
Do you know what PFS is or how it works? Clearly the answer is "NO" but you should educate yourself.
The OP is right: smartcards mostly rely on symmetric algorithms. In fact the OP never said anything about PFS, and bank cards for example, which use RSA, do not implement PFS, because it is not needed in that context.
Do you know what a smart card is and how it works? Clearly the answer is "NO" but you should educate yourself;-)
Why is this even a thing? All reversible encryption (which in itself is a tautology) is searchable.
Plaintext record ID > Encryption+key+salt etc > Cyphertext record ID. Search for the cyphertext record ID. Bring encrypted record back from database. Encrypted record > Encryption > Plaintext record.
How is this a marketable product?!
Searchable encryption is more complicated than you think. For example if I encrypt the sentence "I like reading slashot" with traditional encryption I will get a block binary data that is meaningless. Now suppose I want to check if that block contains the word "slashdot"? Your "cyphertext record id" approach won't be of much help. You need a few tricks to do it correctly, notably adding some metadata and additional cryptographic mechanisms. To make things more complicated, you often need the encryption mechanism to be "format preserving": if you encrypt a string field you get a string field, if you encrypt a number field you get a number field, while traditional cryptography outputs binary data.
Note that you may have misunderstand how encryption works, if you believe that all reversible encryption is searchable. Good encryption is randomised: if you encrypt the same plaintext twice with the same key you get 2 different cypher-texts (to take your analogy, you must use different salts).
In practice hashing is often much less secure than encryption for passwords. The devil is in the details.
Here it seems that Adobe made some poor design choices in the encryption algorithm. Yet, despite these flaws, assuming the encryption key is not compromised they might still be better off with their encryption rather than a poor hash mechanism such as the one used for example by Sony and revealed in the playstation hack by anonymous.
In general if the encryption key is not compromised, then encryption provides much more security than pure hashing, or even hashing with a salt. The reason for that is that with encryption, the security of the password depends on the strength of the secret key. With hashing, the security depends of the strength of the password. This is a significant difference. So, if your password is 4 characters long, even the best hash algorithm will fail to protect from a brute force attack. However, if that same password is encrypted, you need to brute force the key which would take centuries assuming the key is long enough.
To be more precise: 1) Pure hashing (applying SHA1 alone for example) is almost the same as having no security at all. 2) Hashing with a salt is a bit better but still won't resist long given computational power offered by GPUs and cloud computing. 3) An iterated hash function with a salt is much better (see PKDF2), and buys you some security but still vulnerable from brute force attacks using GPUs and pooled cloud resources. 4) A "sequential memory-hard" hash function (with salt and iteration) such as "scrypt" is pretty safe today.
Unfortunately in reality most companies use either (1) or (2)...
The drawback of encryption is that you need to make sure that your key is safe. Once the key is compromised you're toast. This means that you should not put the key on the same system that is hosting the password database (it may sound evident, but I've seen it done). It requires putting the key in a HSM (Hardware Security Module) or in a distinct ultra secure server, distinct from the password database.
Of course, if you have the possibility to keep a key secure, the best option is to use a *keyed* hash function (an iterated salted version of HMAC for example), getting the benefits of both worlds...
The US has a lot to offer that Europe doesn't have, but when it comes to privacy, I think Europeans do have a strong lead:
* For a start Europeans have real privacy legislation (it's called Directive 95/46/EC). US Internet corporations will fight with big money against any similar initiative in the US.
* Each European Member State has a data protection authority that enforces privacy legislation, monitors the use of personal information and tries to educate the public. Some of these authorities even have inspection powers (see for example what they did over Streetview's interception of Wifi data). It has a little bureaucratic feel to it, but it works.
* Culturally in Europe, there's always a tendency to find a balance between each party’s legitimate interests and rights. Even in the workplace, people's right to privacy can't fully be obliterated by corporate needs.
The only caveat is that we are living more and more in a global world. My employer might be Chinese, my datacenters might be in the US, and my job might be in Europe. Which law applies then? That's the challenge!
I know this will surprise many slashdot readers but using your fingerprint as described by the poster for the purpose of clocking you in and out of work would be illegal in many countries accross Europe (with the possible exception of the UK). In France, for example, you can actually get fined by the data protection authority for doing so.
It's true that most of these devices don't store an image of your fingerprint but rather a "template" : a description of some special features of your fingerprint. But that doesn't change the problem.
Indeed, many data proctection authorities accross the EU consider that biometrics pose sevreall security and data protection issues and must therefore be used with caution. Fingerprint biometrics are of special concern, in particular when the biometric data (templates) are stored in a central database. The big problem with fingerprints is that we leave them everywhere, on all objects we touch. Someone can pick up your fingerprint and test it against the templates inside the database. (Sounds crazy or technically impossible ? It's much easier than you think : i've tested it myself, that's part of my job). There are other issues whith fingerprint biometrics that I won't detail here.
In the end data protection authorities in the EU consider that the use of a central fingerprint database is excessive if your only objective is only clocking people in and out. Instead, they encourage the use of a smartcard to store the biometric data : you show your finger to the biometric reader and it gets compared with the data stored in the smartcard. This solution offers the same benefits in terms of security but you keep control of your biometric data.
I wouldn't be so sure ! The application you describe is very particular.
In practice, smartcards are often used as tamperproof devices to represent a third party, such as a bank. In France, for example, the credit card smart cards carry the bank's private key (for a Gilou/Quisquater RSA variant) as well as some additionnal secret information. This information is not available for any reader but is used internaly for cryptographic computations.
I really don't understand the problem here. I never said that "relies on" is an equivalence relationship.
When you say that [Property A] relies on [Property B], the understanding is that [Property B] implies [Property A]. This is clearly not a bi-directional relationship. You can consider "rely on" to be an implication relationship written backwards. For example let X be a random variable, if you write [Property X*X>0] relies on [Property X>2], it means that [Property X>2] implies [Property X*X>0]. The real ambiguity was correctly highlighted by Glorat, who noted that "relies on" is not necessarily understood as "relies solely on" in every day English. Nonetheless, in many cryptographic publications you will find sentences such as "the security of X relies on the difficulty of the DDHP (Decision Diffie Hellman Problem)", which means in fact that the hardness of the DDH implies the security of X.
When you write [RSA is secure] relies on [Factoring is hard], you are saying that [Factoring is hard] implies [RSA is secure]. This is equivalent to the contrapositive statement: NOT[RSA is secure] implies NOT[Factoring is hard] or if you prefer [RSA is breakable] implies [Factoring is easy]. To prove this, you have to show that breaking RSA gives you a factoring algorithm. Since such a proof does not exist, then you cannot say that [RSA is secure] relies on [Factoring is hard].
On the other hand it is well known that [Factoring is easy] implies [RSA is breakable]. Consequently if we could prove the unproved implication above, we would immediately have a equivalence between the two properties, but that's another story.
For the justification of the contrapositive statement above, you can look in any book on logic.
I agree that if the difficulty of breaking RSA relies on the difficulty of factoring, then: if factoring is easy, RSA is broken.
However to prove that the difficulty of breaking RSA relies on the difficulty of factoring, you need to prove that breaking RSA will yield an efficient factoring algorithm. Such a proof does not exist yet.
Perhaps the difficulty of breaking RSA relies on a completely different property. It is entirely possible that, one day, someone can find a way to break the security of RSA without factoring the modulus. In that case, RSA will be broken but factoring might still be a difficult problem. Incidently, that would prove that the security of RSA does not rely on the difficulty of factoring.
Conclusion: though it's true that an efficient factoring algorithm would break RSA, we can not say -to this date- that the security of RSA relies on the difficulty of factoring.
I guess that in mathematical theorems, you will rarely find ambiguous terms such as "rely" but rather "is polynomialy reduced to" or the like.
In cryptographic publications, when you write that the security of a cryptosystem C relies on a certain difficulty D it means that if you have a algorithm that breaks C then you can use it to solve C. If you translate this in the current case, it means that: if RSA relies on factoring than any algorithm that breaks RSA could be used to factor composite numbers. I insist: this reduction has never been proved. I know that a lot of people misunderstand this type of resonning but it is very common in cryptography and in complexity theory. Again, if you don't believe me, feel free to open the Handbook of Applied Cryptography, or any other serious book on cryptography.
As I said before, it is interesting to see that the Rabin cryptosystem, which is based on "squaring modulo a composite" has been proved to rely on the difficulty of factoring and indeed, an algorithm which breaks Rabin can be used to factor large composites.
I use google often, however I don't rely on keyword search on a scientific method to find the truth:)
Recall that an NP-Complete problem A is called that way because there exists a polynomial time reduction between ALL NP problems and A. In fact if you simply find such a reduction between the factoring problem and any single known NP-Complete problem, you will become a famous man, because such a proof has never been found.
I agree that I went a little fast when I said that factoring was not NP, by abuse of langage. What I meant is that there is no proof that an efficient polynomial time algorithm does not exist, and moreover, finding such an polynonial algorithm would not yield P=NP.
As a side note, some recent work by D. Boneh at Stanford suggests that RSA MAY NOT BE EQUIVALENT TO FACTORING.
No. I stand by my original point.The security of RSA has not been proved to rely on the difficulty of factoring. There may be an easier attack that is not known to us yet. If we could prove that breaking RSA is equivalent to factoring we could say that the security of RSA relies on factoring and that no easier attack exists, but this has never been proved.
I also encourage you to revise your "math" memories: factoring has never been proved to be NP-complete or even NP. To my best knowledge efficient factoring algorithms are sub-exponential and there is no strong indication that a polynomial factoring algorithm does not exist.
For further information I encourage you to read the Handbook of Applied Cryptography, by Menezes et al. It will describe the above points more in detail.
NO ! RSA is not proved to rely on the difficulty of factoring
Indeed, since you insist on being precise, you should not write that RSA relies on the difficulty of factoring into primes because no one has ever proved that it's true.
The truth is that the best known attack on RSA is factoring, but that does not tell us that RSA and factoring are equivalent problems, though this is widely believed by many researchers.
On the other hand, the Rabin public key cryptosystem, which involves squaring with a RSA-type composite modulus has been proved to be equivalent to factoring.
Though the work presented at crypto 2001 may prove that it's not possible to provide program obfuscation in the general case, some other researchers have shown how to do obfuscating in more restrictive, yet powerfull scenarios.
For example, there is a paper that describes a method to do Function Hiding. This allows to compute a function on an untrusted host. A lot of problems can be modeled that way, and though we may never see methods to provide obfuscation in the general case, it does not rule out the possibility of obfuscating special classes of programs.
RFC 2627 is based on the key graph paradigm of Gouda, Lam & al. It's one of the best ideas to days but it still as some drawbacks: the main one is that many members leaving the group require the whole group to reliably recieve as many key update. There are mechanisms to achieve this, such as ECC or proactive rebroadcasting but they have quite a cost. Moreover, an often overlooked fact is that the distributed keys need to be authenticated to prevent others to send bogus key update messages. Again this adds a cost.
I'm not going to discuss all the details, but though I agree there are some solutions out there, I can tell you that may not scale well in large multicast application.
Besides technical issues related to multicast protocols (ex. core placement) there is one big problem which has stopped widespread use of multicast on the net: the lack of security mechanisms.
To take a simple example imagine pay-per-view TV implemented using multicast. We need a mechanism to restrict access to users who paid for the access. If such a mechanism does not exist, there will be very few commercial applications that use multicast.
To understand the difficulty of multicast access control, imagine the pay-per-view scenario. You encrypt traffic with a key. Then you give the key to the members who paid for access. However each time a member is added or removed from the group, you have to change that key. Otherwise if you use the same key, members joining the group will have access to past data and members leaving the group will still have access to future data. Now imagine that you have a million members, and one of them is removed from the group. How can you scalably send a new key to a million members while you make sure that the removed member does not recieve it?
Well, this is still a research area. Though there are some quite clever ideas, none of them provides a completely satisfactory solution.
Even for applications which don't require access control, there remains authentication issues. Perhaps CNN might be interested in TV multicasting, however, how can you make sure that the stream that you receive comes from CNN and not a bunch of hackers sending some kinky video? Well for live realtime streams this requires some form of authentication that needs to be fast and tolerate some data loss, etc... Again no perfect solution exists yet.
So I don't think you will see widespread use of multicast until these issues are solved. On the other hand, multicast will probably be used internaly in corporations, intranets and such.
Slashdot Mirror
Thanks to open-source hardware, there has never been so much choice and so much opportunity to learn.
My recommendations for today's tinkerer are:
- Raspberry Pi (not fully open source but close enough) and the wiring Pi library http://wiringpi.com/
- The esp8266 boards: Super cheap Arduino compatible WIFI boards.
- Any SAMD21 ARM cortex M0 board like the Arduino Zero, Sparkfun SAMD21 breakout, or the Adafruit Feather M0.
- STM32 "blue pill" boards. Super cheap on ebay and powerfull.
In theory, you don't need hardware to be open source just to "tinker" with it. But in reality, if you want to truly learn stuff, open source hardware is great. You can take a look at the schematics, learn piece by piece from others: power supply circuits, reset, oscillators, micro-controllers, ...
For example take a look at the Sparkfun SAMD21 breakout schematics here: https://cdn.sparkfun.com/datas...
You'll see the leds, the usb, the battery power circuit, the micro-controller and headers, all nicely broken down in separate blocks that you can learn from and re-use.
After a while, you will be able to make your own boards. YES! ** That the best part of it all! **
Myself I started with a simple Arduino UNO and a couple of years later, I'm about to launch my own IoT Arduino compatible platform, fully designed and implemented in the garage of our house: http://omzlo.com/
If "Every Major Advertising Group" hates this, then it shows that Apple is probably doing the right thing :-)
These guys killed "Do-Not-Track" in the US and made a joke of "cookie laws" in the EU. Looks like now they have found a stronger opponent.
These Chip and Pin cards are called "EMV" cards.
For those who are curious about what's inside those chips, check out Cardpeek, an open-source tool to read the contents of smart cards.
http://pannetrat.com/Cardpeek/
Lots of stuff in there.
I fully agree. I like the GTK+ API and I still continue to use it because shifting to another toolkit for my apps would be costly. But I'm loosing patience:
GTK+ development has become an unprofessional mess. Functions get deprecated even with minor version changes: you develop your app with version 3.xx and distribute it. Then people move to 3.yy (where yy>xx) and bang your app does not work anymore because someone decided to *remove* a function from GTK+ without any consideration for existing apps out there. Sometimes the fix involves a new function that does not exist in the previous version of the library, so you can't even find a real fix that would work with all versions from 3.xx and above. You just add some ugly preprocessor macros in your code to deal with different versions of GTK+ at source level...
With the safe harbour agreement american companies basically "promise" to follow some rules related to privacy, which are compatible with European values. But to make such an approach effective, someone has to verify that the "promises" are real and eventually impose sanctions if they are not. That someone is -- in theory -- the FTC.
The problem with safe harbor is that it is been very weakly enforced. In the first decade since it was created, there has been no real enforcement action that I've heard of. This gives the impression that Safe Harbor is pretty toothless. FTC has only recently (2014) began to enforce this framework, because Europeans threatened to abandon it.
My experience as an end-user in a research project:
I've tried to install OpenStack on a small group of 4 machines (a controller, a network manager and two compute node). It was a real mess to install. The documentation contains omissions and mistakes. You need to write your own shell scripts to get the work done (and redone). Understanding what went wrong from the cryptic python debug messages is like banging your head against a wall. The only way I finally was able to test things was to scale back to a "one-node" system (everything on the same machine) and use DevStack. That works great but it's really far from a "cloud". You need to be HP or RackSpace to get this working well I guess.
Contrast that with OpenNebula. This platform is much less hyped about but it works much better. Even when you hit a bump on the road, you can actually understand the logs, and even debug stuff yourself. I got a 4 node system working with all storage on iSCSI and I can add more compute nodes seamlessly.
Do you know what PFS is or how it works? Clearly the answer is "NO" but you should educate yourself.
The OP is right: smartcards mostly rely on symmetric algorithms. In fact the OP never said anything about PFS, and bank cards for example, which use RSA, do not implement PFS, because it is not needed in that context.
Do you know what a smart card is and how it works? Clearly the answer is "NO" but you should educate yourself ;-)
Why is this even a thing? All reversible encryption (which in itself is a tautology) is searchable.
Plaintext record ID > Encryption+key+salt etc > Cyphertext record ID. Search for the cyphertext record ID. Bring encrypted record back from database. Encrypted record > Encryption > Plaintext record.
How is this a marketable product?!
Searchable encryption is more complicated than you think. For example if I encrypt the sentence "I like reading slashot" with traditional encryption I will get a block binary data that is meaningless. Now suppose I want to check if that block contains the word "slashdot"? Your "cyphertext record id" approach won't be of much help. You need a few tricks to do it correctly, notably adding some metadata and additional cryptographic mechanisms. To make things more complicated, you often need the encryption mechanism to be "format preserving": if you encrypt a string field you get a string field, if you encrypt a number field you get a number field, while traditional cryptography outputs binary data.
Note that you may have misunderstand how encryption works, if you believe that all reversible encryption is searchable. Good encryption is randomised: if you encrypt the same plaintext twice with the same key you get 2 different cypher-texts (to take your analogy, you must use different salts).
It's called "searchable" encryption. It already exists in a few commercial products.
See for example:
http://www.ciphercloud.com/tec...
In practice hashing is often much less secure than encryption for passwords. The devil is in the details.
Here it seems that Adobe made some poor design choices in the encryption algorithm. Yet, despite these flaws, assuming the encryption key is not compromised they might still be better off with their encryption rather than a poor hash mechanism such as the one used for example by Sony and revealed in the playstation hack by anonymous.
In general if the encryption key is not compromised, then encryption provides much more security than pure hashing, or even hashing with a salt. The reason for that is that with encryption, the security of the password depends on the strength of the secret key. With hashing, the security depends of the strength of the password. This is a significant difference. So, if your password is 4 characters long, even the best hash algorithm will fail to protect from a brute force attack. However, if that same password is encrypted, you need to brute force the key which would take centuries assuming the key is long enough.
To be more precise:
1) Pure hashing (applying SHA1 alone for example) is almost the same as having no security at all.
2) Hashing with a salt is a bit better but still won't resist long given computational power offered by GPUs and cloud computing.
3) An iterated hash function with a salt is much better (see PKDF2), and buys you some security but still vulnerable from brute force attacks using GPUs and pooled cloud resources.
4) A "sequential memory-hard" hash function (with salt and iteration) such as "scrypt" is pretty safe today.
Unfortunately in reality most companies use either (1) or (2)...
The drawback of encryption is that you need to make sure that your key is safe. Once the key is compromised you're toast. This means that you should not put the key on the same system that is hosting the password database (it may sound evident, but I've seen it done). It requires putting the key in a HSM (Hardware Security Module) or in a distinct ultra secure server, distinct from the password database.
Of course, if you have the possibility to keep a key secure, the best option is to use a *keyed* hash function (an iterated salted version of HMAC for example), getting the benefits of both worlds...
The US has a lot to offer that Europe doesn't have, but when it comes to privacy, I think Europeans do have a strong lead:
* For a start Europeans have real privacy legislation (it's called Directive 95/46/EC). US Internet corporations will fight with big money against any similar initiative in the US.
* Each European Member State has a data protection authority that enforces privacy legislation, monitors the use of personal information and tries to educate the public. Some of these authorities even have inspection powers (see for example what they did over Streetview's interception of Wifi data). It has a little bureaucratic feel to it, but it works.
* Culturally in Europe, there's always a tendency to find a balance between each party’s legitimate interests and rights. Even in the workplace, people's right to privacy can't fully be obliterated by corporate needs.
The only caveat is that we are living more and more in a global world. My employer might be Chinese, my datacenters might be in the US, and my job might be in Europe. Which law applies then? That's the challenge!
I know this will surprise many slashdot readers but using your fingerprint as described by the poster for the purpose of clocking you in and out of work would be illegal in many countries accross Europe (with the possible exception of the UK). In France, for example, you can actually get fined by the data protection authority for doing so.
It's true that most of these devices don't store an image of your fingerprint but rather a "template" : a description of some special features of your fingerprint. But that doesn't change the problem.
Indeed, many data proctection authorities accross the EU consider that biometrics pose sevreall security and data protection issues and must therefore be used with caution. Fingerprint biometrics are of special concern, in particular when the biometric data (templates) are stored in a central database. The big problem with fingerprints is that we leave them everywhere, on all objects we touch. Someone can pick up your fingerprint and test it against the templates inside the database. (Sounds crazy or technically impossible ? It's much easier than you think : i've tested it myself, that's part of my job). There are other issues whith fingerprint biometrics that I won't detail here.
In the end data protection authorities in the EU consider that the use of a central fingerprint database is excessive if your only objective is only clocking people in and out. Instead, they encourage the use of a smartcard to store the biometric data : you show your finger to the biometric reader and it gets compared with the data stored in the smartcard. This solution offers the same benefits in terms of security but you keep control of your biometric data.
I wouldn't be so sure ! The application you describe is very particular.
In practice, smartcards are often used as tamperproof devices to represent a third party, such as a bank. In France, for example, the credit card smart cards carry the bank's private key (for a Gilou/Quisquater RSA variant) as well as some additionnal secret information.
This information is not available for any reader but is used internaly for cryptographic computations.
YEP, You can encrypt with a hash. Let H be a hash function. Let | denote concatenation and % denote XOR.
Let K be a secret key, to encrypt a message X=X1,X2,...,Xn you do:
Y0=(A random value)
for i=1 to n do Yi=Xi % H(Y0|K|i)
The encrypted text is Y0,Y1,Y2,...,Yn.
The decryption is obvious.
Without getting into details, this method is secure as long as H has a very random.
behavior.
I really don't understand the problem here. I never said that "relies on" is an equivalence relationship.
When you say that [Property A] relies on [Property B], the understanding is that [Property B] implies [Property A]. This is clearly not a bi-directional relationship. You can consider "rely on" to be an implication relationship written backwards. For example let X be a random variable, if you write [Property X*X>0] relies on [Property X>2], it means that [Property X>2] implies [Property X*X>0]. The real ambiguity was correctly highlighted by Glorat, who noted that "relies on" is not necessarily understood as "relies solely on" in every day English. Nonetheless, in many cryptographic publications you will find sentences such as "the security of X relies on the difficulty of the DDHP (Decision Diffie Hellman Problem)", which means in fact that the hardness of the DDH implies the security of X.
When you write [RSA is secure] relies on [Factoring is hard], you are saying that [Factoring is hard] implies [RSA is secure]. This is equivalent to the contrapositive statement: NOT[RSA is secure] implies NOT[Factoring is hard] or if you prefer [RSA is breakable] implies [Factoring is easy]. To prove this, you have to show that breaking RSA gives you a factoring algorithm. Since such a proof does not exist, then you cannot say that [RSA is secure] relies on [Factoring is hard].
On the other hand it is well known that [Factoring is easy] implies [RSA is breakable]. Consequently if we could prove the unproved implication above, we would immediately have a equivalence between the two properties, but that's another story.
For the justification of the contrapositive statement above, you can look in any book on logic.
I'll try to clarify my explanation.
I agree that if the difficulty of breaking RSA relies on the difficulty of factoring, then: if factoring is easy, RSA is broken.
However to prove that the difficulty of breaking RSA relies on the difficulty of factoring, you need to prove that breaking RSA will yield an efficient factoring algorithm. Such a proof does not exist yet.
Perhaps the difficulty of breaking RSA relies on a completely different property. It is entirely possible that, one day, someone can find a way to break the security of RSA without factoring the modulus. In that case, RSA will be broken but factoring might still be a difficult problem. Incidently, that would prove that the security of RSA does not rely on the difficulty of factoring.
Conclusion: though it's true that an efficient factoring algorithm would break RSA, we can not say -to this date- that the security of RSA relies on the difficulty of factoring.
I guess that in mathematical theorems, you will rarely find ambiguous terms such as "rely" but rather "is polynomialy reduced to" or the like.
I work in cryptography.
:)
In cryptographic publications, when you write that the security of a cryptosystem C relies on a certain difficulty D it means that if you have a algorithm that breaks C then you can use it to solve C. If you translate this in the current case, it means that: if RSA relies on factoring than any algorithm that breaks RSA could be used to factor composite numbers. I insist: this reduction has never been proved. I know that a lot of people misunderstand this type of resonning but it is very common in cryptography and in complexity theory.
Again, if you don't believe me, feel free to open the Handbook of Applied Cryptography, or any other serious book on cryptography.
As I said before, it is interesting to see that the Rabin cryptosystem, which is based on "squaring modulo a composite" has been proved to rely on the difficulty of factoring and indeed, an algorithm which breaks Rabin can be used to factor large composites.
I use google often, however I don't rely on keyword search on a scientific method to find the truth
Recall that an NP-Complete problem A is called that way because there exists a polynomial time reduction between ALL NP problems and A. In fact if you simply find such a reduction between the factoring problem and any single known NP-Complete problem, you will become a famous man, because such a proof has never been found.
I agree that I went a little fast when I said that factoring was not NP, by abuse of langage. What I meant is that there is no proof that an efficient polynomial time algorithm does not exist, and moreover, finding such an polynonial algorithm would not yield P=NP.
As a side note, some recent work by D. Boneh at Stanford suggests that RSA MAY NOT BE EQUIVALENT TO FACTORING.
Worth a read...
No. I stand by my original point.The security of RSA has not been proved to rely on the difficulty of factoring. There may be an easier attack that is not known to us yet. If we could prove that breaking RSA is equivalent to factoring we could say that the security of RSA relies on factoring and that no easier attack exists, but this has never been proved.
I also encourage you to revise your "math" memories: factoring has never been proved to be NP-complete or even NP. To my best knowledge efficient factoring algorithms are sub-exponential and there is no strong indication that a polynomial factoring algorithm does not exist.
For further information I encourage you to read the Handbook of Applied Cryptography, by Menezes et al. It will describe the above points more in detail.
NO ! RSA is not proved to rely on the difficulty of factoring
Indeed, since you insist on being precise, you should not write that RSA relies on the difficulty of factoring into primes because no one has ever proved that it's true.
The truth is that the best known attack on RSA is factoring, but that does not tell us that RSA and factoring are equivalent problems, though this is widely believed by many researchers.
On the other hand, the Rabin public key cryptosystem, which involves squaring with a RSA-type composite modulus has been proved to be equivalent to factoring.
Though the work presented at crypto 2001 may prove that it's not possible to provide program obfuscation in the general case, some other researchers have shown how to do obfuscating in more restrictive, yet powerfull scenarios.
For example, there is a paper that describes a method to do Function Hiding. This allows to compute a function on an untrusted host. A lot of problems can be modeled that way, and though we may never see methods to provide obfuscation in the general case, it does not rule out the possibility of obfuscating special classes of programs.
RFC 2627 is based on the key graph paradigm of Gouda, Lam & al. It's one of the best ideas to days but it still as some drawbacks: the main one is that many members leaving the group require the whole group to reliably recieve as many key update. There are mechanisms to achieve this, such as ECC or proactive rebroadcasting but they have quite a cost. Moreover, an often overlooked fact is that the distributed keys need to be authenticated to prevent others to send bogus key update messages. Again this adds a cost.
I'm not going to discuss all the details, but though I agree there are some solutions out there, I can tell you that may not scale well in large multicast application.
Besides technical issues related to multicast protocols (ex. core placement) there is one big problem which has stopped widespread use of multicast on the net: the lack of security mechanisms .
To take a simple example imagine pay-per-view TV implemented using multicast. We need a mechanism to restrict access to users who paid for the access. If such a mechanism does not exist, there will be very few commercial applications that use multicast.
To understand the difficulty of multicast access control, imagine the pay-per-view scenario. You encrypt traffic with a key. Then you give the key to the members who paid for access. However each time a member is added or removed from the group, you have to change that key. Otherwise if you use the same key, members joining the group will have access to past data and members leaving the group will still have access to future data. Now imagine that you have a million members, and one of them is removed from the group. How can you scalably send a new key to a million members while you make sure that the removed member does not recieve it?
Well, this is still a research area. Though there are some quite clever ideas, none of them provides a completely satisfactory solution.
Even for applications which don't require access control, there remains authentication issues. Perhaps CNN might be interested in TV multicasting, however, how can you make sure that the stream that you receive comes from CNN and not a bunch of hackers sending some kinky video? Well for live realtime streams this requires some form of authentication that needs to be fast and tolerate some data loss, etc... Again no perfect solution exists yet.
So I don't think you will see widespread use of multicast until these issues are solved. On the other hand, multicast will probably be used internaly in corporations, intranets and such.