18

By "encrypting" passwords you are violating CWE-257: Storing Passwords in a Recoverable Format. But this is exactly what the French government wants. They want to be able to obtain the passwords of any user. By all accounts this is bad thing, and Bruce Schneier agrees.

So how can you satisfy this French mandate as well as maintaining a high level of security?

Matthew
  • 27,263
  • 7
  • 89
  • 101
rook
  • 47,004
  • 10
  • 94
  • 182
  • @Rook - StackExchange websites are not meant for "open discussion" threads. Please review the FAQ, as well as this post on the StackExchange blog: http://blog.stackoverflow.com/2010/09/good-subjective-bad-subjective/ The question should be re-formulated so that it is seeking to find an objective solution to a real-world problem. – Iszi Apr 10 '11 at 02:08
  • @Iszi okay it is a real world problem (websites with french users), and it has a definitive solution. – rook Apr 10 '11 at 02:41
  • See also [this discussion](http://stackoverflow.com/q/2283937/10080) over on SO, from a year ago... quite heated, in fact, and I'm glad to see none of the same rhetoric (yet) that there was over there. It's funny, some of the highest voted answers are just plain wrong, and all those that spoke to common sense and reasonable risk analysis were strongly downvoted (e.g. mine, near the bottom :) ) – AviD Apr 10 '11 at 08:54
  • @AviD♦ I remember that post, and I completely agree. I even say in my profile that the correct answer is almost never chosen. That is why you should test everything, and exploit is a form of a test. – rook Apr 10 '11 at 21:25
  • Heh, but in this case I was arguing *against* the veracity of any exploit based test, instead a conceptual risk analysis was called for. Also, if I'm not mistaken, you were in agreement with the accepted answer there ;) – AviD Apr 11 '11 at 05:18
  • @AviD♦ His solution was interesting, protecting users is a better approach to the legal dilemma. I think a secuirty system based on concept alone lacks foundation and will crumble like a house of cards. Mastery can only be obtained though the act of doing, not sitting on the sidelines watching it happen. – rook Apr 11 '11 at 05:40
  • @Rook you're right - I didnt notice that the currently accepted answer was changed since I read it, it used to be what is now the second answer. – AviD Apr 11 '11 at 05:52
  • re Mastery - the "act of doing" can only get you past the apprenticeship stage. Yes, it is absolutely necessarily required, but it's not the end of the path, it's the beginning. Yes, any theory (of non-breakability) should be verified by the "doing", however in some cases analysis *will* tell you that the results of your "doing" *just don't matter*. And that level of mastership cannot be obtained by just doing, without looking at the bigger picture. – AviD Apr 11 '11 at 05:55
  • @AviD♦ Would you drive in a car that was never given a crash test? What is the impact of head on collision? Will this bullet proof vest stop a 40 caliber round? Security systems in all forms must be tested. Software that fails and puts human lives at risk will be given a high severity metric by the DHS. Over the years I have come to value [the ones](http://www.kb.cert.org/vuls/id/584089) I [have collected](http://www.kb.cert.org/vuls/id/643049). – rook Apr 11 '11 at 06:03
  • @Rook do you think a car can be made safe simply by repetitive crash testing, without some thought and design? Again, I'm not testing is not necessary, I'm saying it's not all there is. What if the car is not safe when dropped from 50 feet in the air? Or the bulletproof vest wont stop a tank shell (or a rottweiller)? My point is that not everything that *can* be tested, *should* be tested (or needs to be) - some things *just don't matter*. But, I really think we're off context here... – AviD Apr 11 '11 at 06:08
  • @AviD♦ I honestly believe that people who don't write exploit code are bigger danger to the industry because they provide a false sense of secuirty. Perhaps we should agree to disagree. – rook Apr 11 '11 at 06:16
  • And I believe people who *only* write exploit code and exclude all else - especially risk analysis - are even bigger danger, because they misdirect limited security resources which might be better spent elsewhere, and cause the (non-security) business to perceive the security industry as hacks focused only on exploits not relevant to the business... So yes, we'll agree to disagree :). Much like compliance experts think that's the most important, and network pros see that as all important, etc, anyone with a narrow expertise tends to see that as the core, and everything else as unimportant. – AviD Apr 11 '11 at 06:37
  • I now see two different questions here. One is how to deal with the French law, the other is how to store passwords in a way which allows them to be recovered via a possibly offline process. Your various comments suggest that you don't really want to see discussion of how to interpret and/or satisfy the French law while protecting your users, so please edit the question to focus on the password escrow issue with a disclaimer like the one at http://stackoverflow.com/questions/2283937/ (of which this seems to be a duplicate, but it seems fine to discuss it here also). – nealmcb Apr 12 '11 at 01:46

5 Answers5

18

Don't force yet-another-password on your users. Use PKI, hardware tokens, or some other method like OAuth or OpenID that leverages some Identity Provider site which sits outside of whatever jurisdictions you're worried about.

Note that the actual requirements of the 2004 French law in question Loi pour la confiance dans l'économie numérique aka Act on Confidence in the Digital Economy are not clear and it seems that some reporting has misinterpreted or exaggerated the effects. For example it sounds like it may be sufficient to simply provide law enforcement with some other access to the user's account, e.g. for a child pornography investigation, in a way that doesn't tip the user off that their account is being accessed (as a typical password reset would).

nealmcb
  • 20,693
  • 6
  • 71
  • 117
  • At some point every web application ever requires a username and password. How is OpenID going to store passwords to comply with French law? You are dodging the question. – rook Apr 10 '11 at 08:35
  • 3
    @Rook, no he's not - in his solution, *there are no passwords*, to store or not store. The French law (I assume) does not require every website to *have* passwords, only to store *existing* passwords in a recoverable format. – AviD Apr 10 '11 at 08:55
  • 4
    @rook *If* the OpenID Identity Provider uses passwords to authenticate its users, it presumably just needs to be outside of the jurisdiction and thus not subject to the jurisdiction's laws. But of course OpenID IdPs can also use other non-password-based authn. And check the refs on "French Law" some more - this whole thing seems to be a misunderstanding. – nealmcb Apr 10 '11 at 13:22
  • @nealmcb - yeah, it does seem like it is the access requirement that is key. I'm getting various different versions of the reqs each day, so trying to figure out exactly how this thing is meant to play out is tricky. – Rory Alsop Apr 10 '11 at 15:23
  • @nealmcb This is not a legal question, no one here is a lawyer. – rook Apr 10 '11 at 18:05
  • 2
    @rook, we certainly welcome lawyers here since policy and compliance are major aspects of IT Security. And the question as posed refers to compliance with a law, so what the law means is very relevant. – nealmcb Apr 10 '11 at 18:58
  • 2
    @nealmcb, and dont forget, this is a technical law with security implications, so the lawyers *should* have been welcoming us over there, too... – AviD Apr 11 '11 at 05:22
  • @nealmcb my point was that I don't think OAuth and OpenID is magically outside of justification while my server in Virgina is. As long as you have French users, you have a problem. Shielding users from malicious governments is important, and using public key cryptography for authentication instead of passwords is a solid solution. – rook Apr 11 '11 at 19:12
  • 1
    @rook, Hmmm. Why do you think that a server in Virginia with French users would be affected by this French law? Do you have a citation for how French law would apply, if your organization has no legal or physical presence in France? We agree that PKI is one solid solution, and OpenID and OAuth can each be based on PKI with no passwords on any servers. – nealmcb Apr 11 '11 at 19:31
  • @rook, Sorry, I'm missing something. What question do you think I am not addressing? – nealmcb Apr 11 '11 at 19:37
  • @rook - OK, I think I figured out what you mean to ask here, and I made a request above for you to clarify that so we don't waste people's time debating the French law here. – nealmcb Apr 12 '11 at 01:49
6

Use Public Key Cryptography. Your server will only have the public key. This will allow the server to encrypt a password and then can compare cypher text in order to authenticate a user.

The private key should be on a drive inside a bank vault. If the french government demands a password, then you can access to the private key to decrypt the password.

rook
  • 47,004
  • 10
  • 94
  • 182
  • This is a big improvement on hackable passwords. But it does not protect users (even users outside the jurisdiction) against abuse of legal authority which can still get their password. If there really were jurisdictions which required plain text password storage, I wouldn't trust them to not abuse the law to get them when they wanted them. – nealmcb Apr 10 '11 at 13:26
  • 1
    You can only compare ciphertexts if you are using deterministic encryption with no randomness. This is not advisable since it will not be secure against chosen plaintext attacks (or chosen ciphertext attacks). – PulpSpy Apr 10 '11 at 15:53
  • 1
    @nealmcb Yeah I see what you are saying. I agree, France is evil. – rook Apr 10 '11 at 18:07
  • @PulpSpy I'm not sure what you are saying, you can still use a salt, and the same plaintext+public key will always produce the same cipher text. – rook Apr 10 '11 at 18:08
  • 1
    Why do you say France is evil? The BBC got it wrong, it seems, and I haven't seen a really good analysis yet of how France differs from most other governments in this respect. – nealmcb Apr 10 '11 at 18:54
  • @Rook If you use something like textbook RSA, encrypting the same message with the same key does give you the same ciphertext (which is probably what you are thinking about). But if you use something like RSA+OAEP or Elgamal, then encrypting the same message twice wil give you different (and indistinguishable) ciphertexts. This is because they input the message, key, and some randomness. Only the latter kind are secure against chosen plaintext attacks (or "semantically secure"), so a drawback of your scheme is you can't use CPA-secure encryption if that is important. – PulpSpy Apr 10 '11 at 20:01
  • @PulpSpy - CPA-secure? That's encryption that your accountant can't hack? – AviD Apr 11 '11 at 05:21
  • @PulpSpy: in the proposed system, the server must be able to verify a user password, so an attack by exhaustive search on the possible passwords (a "dictionary attack") is unavoidable: an attacker who gets a copy of the complete server storage can simulate the server on his own machines and test passwords at his leisure. Hence using a deterministic asymmetric encryption system is not a bug here, it is a feature... (but it means that "normal" asymmetric encryption cannot be used, which implies a custom protocol, which is almost invariably a bad idea). – Thomas Pornin Apr 11 '11 at 13:11
  • @Thomas: I'm not sure I agree. You are assuming an adversary gets the data but not the secret key, right? (Otherwise, an adversary could just directly decrypt.) In this scenario, a server can use its key to do a plaintext equality test between two CPA-secure ciphertexts. This thwarts a dictionary attack on the passwords and requires an exhaustive search on the key. (Of course, it means the decryption oracle needs to be online and is more complex.) An alternative: have the user encrypt her password client-side, fetch her ciphertext when logging in, and prove knowledge of the plaintext. – PulpSpy Apr 11 '11 at 17:35
  • @PulpSpy It would be difficult for an adversary to get a key inside a vault surrounded many feet of steal and cement. If anything I'd go with the route of each user generating their own key pairs and do away with weak passwords altogether. In your solution there is the possibility of replaying cipher text. – rook Apr 11 '11 at 18:57
  • @PulpSpy: I am assuming that the private key is in a safe, for password escrow, but the server does not have it under normal conditions (and thus cannot use it). I assume that the attacker gains knowledge of everything the server knows. The attacker can then simulate the whole protocol, which means he can check potential passwords. – Thomas Pornin Apr 11 '11 at 19:04
  • Ok, so I think we've reached the following consensus: if (a) the decryption key is not available for use during authentication, (b) users cannot be compelled to remember anything beyond their passwords, and (c) password equivalence must be decidable then: the only secrets can be the passwords themselves. I agree with this. And I can see that these were your (both of you) operating assumptions all along, I just was thinking outside of them for some wrong reason. – PulpSpy Apr 11 '11 at 19:28
4

This questions has been debated, in one form or another, for some time as the "key escrow" problem. There are fundamental problems with the architecture of giving a third party access to secured data. These are invariant to how you implement the cryptography. See this article for example.

I am interpreting the question as how to provide third party access to secured data: the debate about whether this actually corresponds to the current situation with the French government I'm considering tangential; and there are unsolvable risks with doing this by the nature of the problem. So consider this answer as making the best of a bad situation.

A set of requirements could be:

  1. The server has access to all the records
  2. The government can be granted access, but only to specific records
  3. It should be fairly efficient to register a new user
  4. It should be very efficient to authenticate a user
  5. It doesn't necessarily have to be that efficient to recover a record

There is actually a very nice solution to this problem with very modern cryptographic techniques, called functional encryption, however it is not efficient. With these types of schemes, the server can hold a master private key that allows them to decrypt any record and they can create a new private key that can only be used to decrypt specific records. This solves (1), (2) and (5), conflicts with (3) and does not provide (4).

In order to provide (4), I'd suggest a hybrid system where whatever existing password-based authentication system is being used is continued to be used to do (4), and it is augmented with an encryption of the user's record (including the password). If the record is provided to the government, once it has recovered the password, it can compare ensure it is the same password being used to authenticate the user.

An alternative to using function encryption would be for the server to encrypt the record with an appropriate encryption scheme that allows them to generate a "zero-knowledge" proof of what the record is each time the government asks for a record (instead of giving the private key). The proof could be encrypted during transit to the government (and one could even use a "designated verifier" proof to stop the government from sharing the proof with others).

None of these solutions will ever solve the fact that the government needs to be trusted not to abuse its authority, since protecting against this conflicts with the definition of the problem we are trying to "solve."

PulpSpy
  • 2,194
  • 15
  • 19
  • 1
    +1, although I really dont think we should be looking at crypto to solve access control... – AviD Apr 11 '11 at 05:25
2

Using PGP, there's no need to store a password. User signs up by submitting their public key. When they need to sign in, send the user some random text, have them sign and return it. Then verify their signature to authenticate them.

2

Store it twice. Once using PKI with a private key that isn't easily accessible and once using a non recoverable format, this way if you have to comply with a legal request you have a method to do so and you can use standard best practices for day-to-day authentication.

Yaur
  • 561
  • 4
  • 6
  • The security of such system is basically the weakest link. You might as well not bother with saving it in non-recoverable format and simplify your system with just the PKI-encrypted password. – Lie Ryan Jul 30 '14 at 12:24
  • @LieRyan How so? You wouldn't be able to validate the password with just the public key so dumping the non-recoverable format means that the web server needs access to the private key which you could otherwise keep air gapped from the internet. This in turn means that you are much more vulnerable to a compromised web server or internal threat. – Yaur Aug 01 '14 at 22:12