Re: I'll show you mine if you show me, er, mine
-- > > However, techniques that establish that the parties share a > > weak secret without leaking that secret have been around > > for years -- Bellovin and Merritt's DH-EKE, David Jablon's > > SPEKE. And they don't require either party to send the > > password itself at the end. > They are heavily patent laden, although untested last time I > looked. This has been discouraging to implementers. There seem to be a shitload of protocols, in addition to SPEKE and DH-EKE A password protocol should have the following properties: 1. It should identify both parties to each other, that is to say, be secure against replay and man in the middle attacks, in particular, strong against phishing.. It should be secure against replay and dictionary attacks by an evesdropper or man-in-the-middle. Such an attacker should be able to no better than someone who just tries repeatedly to log on to the server with a guessed password 2. It should be as strong as practical against offline attacks by the server itself. The server operators, or someone who has stolen information from them, should not know the users password, and dictionary attacks should be sufficiently expensive that a strong password (not your ordinary password) is secure. Can anyone suggest a well reviewed, unpatented, protocol that has the desired properties? --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG A8bCmCXDTAX2Syg907T7uRpajs77l9CqLEii+ezP 42zQDcP3xJXtcLPSgCVa55kew+ALkrQ/I50PFm9lC
Re: I'll show you mine if you show me, er, mine
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 * "James A. Donald" <[EMAIL PROTECTED]> [2005-03-08 12:25 -0800]: > > > However, techniques that establish that the parties share a > > > weak secret without leaking that secret have been around > > > for years -- Bellovin and Merritt's DH-EKE, David Jablon's > > > SPEKE. And they don't require either party to send the > > > password itself at the end. > > > They are heavily patent laden, although untested last time I > > looked. This has been discouraging to implementers. > > There seem to be a shitload of protocols, in addition to SPEKE > and DH-EKE These are classed as 'strong password protocols', and include protocols like SRP (implemented in cyrus sasl I think, but not used commercially anywhere that I know of - sure cyrus sasl is, but those that use is typically only support a couple of authentication methods, and SRP isn't one of them) and PDM (Password Derived Moduli). They have in common the use of Diffie-Hellman exchange, or slightly modified versions of it. > A password protocol should have the following properties: > > 1. It should identify both parties to each other, that is to > say, be secure against replay and man in the middle attacks, in > particular, strong against phishing.. It should be secure > against replay and dictionary attacks by an evesdropper or > man-in-the-middle. Such an attacker should be able to no > better than someone who just tries repeatedly to log on to the > server with a guessed password > > 2. It should be as strong as practical against offline attacks > by the server itself. The server operators, or someone who has > stolen information from them, should not know the users > password, and dictionary attacks should be sufficiently > expensive that a strong password (not your ordinary password) > is secure. I'm not sure how the DH aspect plays into these properties. These protocols all exist in an 'augmented' form (except SRP which has no other form) which adds the property that ownership of the server database does not facilitate impersonation. That seems sufficient. > Can anyone suggest a well reviewed, unpatented, protocol that > has the desired properties? SRP, augmented PDM, both are good and unpatented, but SPEKE claims dominion over all of them. Despite the fact that DH-EKE predates it, and DH is the foundational technology. Thus, most people think the patent is silly nonsense, but are unwilling to test it by (say) including full SRP support in a popular and successful software product. Of course, my assumptions about there being no such products are exactly that. If there are such products I would be very interested to hear about them. .. BTW, in case it isn't obvious, as I wrote this mail I was referencing the Kaufman, Perlman and Speciner 'Network Security' book for verification. I had a close encounter with the politics of this patent a couple of years ago though, and have directly observed its chilling effect. salaam-shalom 2005-03-08 @ 13:28 -0800 - -- G. Hopper, there were a thousand subterfuges = 353 2048R/49AFAFC8 472B 0E78 FCD8 41C1 172B 11F6 90E1 0E2A 49AF AFC8 JID: [EMAIL PROTECTED] -BEGIN PGP SIGNATURE- iQEVAwUBQi4ZpJDhDipJr6/IAQqjqAf+MeCDsc8XOUKPkhIcWOj8B+Nck8cIbYYD SKayJ25dhJiCdm7qzzyydL0hzqb4Jlre8WE+IxU9RZXYbfw6d8XV0kU27LMjRHIm +ppn/yo54wOVBp2lq7TLw5Wjurn4Uo8Ltestt7tdCzEgn4bPrs0c3grMQLBaEZzb axQAOszUfV3UNjz/zURnOz/AuvNYbSeJXqdq5OkRtP7Cyyb5mtfLZ+X1odCWZ4xW 7tGAS8N6RhDtC303lbgINxcrbQdUxhatVRWR2n1uCa58rWxbmO2s1DpvE4NfQTNR f/2K59Of1lExfW09boPKgLmpY8ghSBMhZB3biAON/VH5f0hjFlo4+Q== =Aw9j -END PGP SIGNATURE-
Re: I'll show you mine if you show me, er, mine
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 * "Whyte, William" <[EMAIL PROTECTED]> [2005-03-03 22:24 -0500]: > I haven't read the original paper, and I have a great deal of > respect for Markus Jakobsson. However, techniques that establish > that the parties share a weak secret without leaking that secret > have been around for years -- Bellovin and Merritt's DH-EKE, > David Jablon's SPEKE. And they don't require either party to > send the password itself at the end. They are heavily patent laden, although untested last time I looked. This has been discouraging to implementers. (note, a well-informed and smart person (read 'author of similar protocol') tells me the patent(s) may well be unsupportable, but no-one has thus far been willing to test the water.) salaam-shalom 2005-03-07 @ 12:13 -0800 - -- G. Hopper, look on while Venus keeps ever by = 353 2048R/49AFAFC8 472B 0E78 FCD8 41C1 172B 11F6 90E1 0E2A 49AF AFC8 JID: [EMAIL PROTECTED] -BEGIN PGP SIGNATURE- iQEVAwUBQiy2GpDhDipJr6/IAQptdwgAp2rMxffR27jKXfiEtJFN6VKyodFZ85Mz z6ElscrDMeNCZHtcxeALsa+YNmmdnmwdRcvOtD1NUG7SvhAmBrJH5/x1ABkrelUI WsQPcgxgyytveLTSejO5Va9l5xlv8KDLHdGzVTo0weZ5qMXKZt9bVgSSL/aN9LJv 0wkGVx5dHxcM9B81WVFfOkrpyaea3/bylqcWFRQMp/EIw2KnK2aWr8nV1+ZCTiFY lAX8M7+iMQYaDSGIar9RIGp2GcBkKbEjVr8fUR3KOietLMQyVpG5xdnDORq2ovXS LX0G/AWXOUtttWiLYlUkWsXKko0MMAe86ntPQVtkdjXAUdsI23xEdg== =n82A -END PGP SIGNATURE-
RE: I'll show you mine if you show me, er, mine
I haven't read the original paper, and I have a great deal of respect for Markus Jakobsson. However, techniques that establish that the parties share a weak secret without leaking that secret have been around for years -- Bellovin and Merritt's DH-EKE, David Jablon's SPEKE. And they don't require either party to send the password itself at the end. William > -Original Message- > From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] > Sent: Wednesday, February 23, 2005 7:30 AM > To: cryptography@metzdowd.com; [EMAIL PROTECTED]; > [EMAIL PROTECTED] > Subject: Re: I'll show you mine if you show me, er, mine > > > "R.A. Hettinga" <[EMAIL PROTECTED]> forwarded: > > >Briefly, it works like this: point A transmits an encrypted > message to point > >B. Point B can decrypt this, if it knows the password. The > decrypted text is > >then sent back to point A, which can verify the decryption, > and confirm that > >point B really does know point A's password. Point A then > sends the password > >to point B to confirm that it really is point A, and knows > its own password. > > Isn't this a Crypto 101 mutual authentication mechanism (or at least a > somewhat broken reinvention of such)? If the exchange to > prove knowledge of > the PW has already been performed, why does A need to send > the PW to B in the > last step? You either use timestamps to prove freshness or > add an extra > message to exchange a nonce and then there's no need to send > the PW. Also in > the above B is acting as an oracle for password-guessing > attacks, so you don't > send back the decrypted text but a recognisable-by-A > encrypted response, or > garbage if you can't decrypt it, taking care to take the same > time whether you > get a valid or invalid message to avoid timing attacks. Blah > blah Kerberos > blah blah done twenty years ago blah blah a'om bomb blah blah. > > (Either this is a really bad idea or the details have been > mangled by the > Register). > > Peter. > > > - > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to > [EMAIL PROTECTED] >
Re: I'll show you mine if you show me, er, mine
| >Briefly, it works like this: point A transmits an encrypted message to point | >B. Point B can decrypt this, if it knows the password. The decrypted text is | >then sent back to point A, which can verify the decryption, and confirm that | >point B really does know point A's password. Point A then sends the password | >to point B to confirm that it really is point A, and knows its own password. | | Isn't this a Crypto 101 mutual authentication mechanism (or at least a | somewhat broken reinvention of such)?... The description has virtually nothing to do with the actual algorithm proposed. Follow the link in the article - http://www.stealth-attacks.info/ - for an actual - if informal - description. -- Jerry
Re: I'll show you mine if you show me, er, mine
>The description has virtually nothing to do with the actual algorithm >proposed. Follow the link in the article - http://www.stealth-attacks.info/ - >for an actual - if informal - description. > > There is no actual description publically available (there are three completely different protocols described in the press). I talked to the author about this; he sent me a fourth, somewhat reasonable document. At *best*, this is something akin to SRP with the server constantly proving its true nature with every character (yes, shoulder surfers get to attack keys one at a time). It could get pretty bad though, so rather than support it or bash it, I'd just reserve judgement until it's publically documented at Financial Crypto. --Dan
Re: I'll show you mine if you show me, er, mine
On Thu, 24 Feb 2005, Peter Gutmann wrote: > (Either this is a really bad idea or the details have been mangled by the > Register). No, it's just a really bad idea. A small group of us looked at this a few weeks ago when it was announced, and while none of us are professional cryptographers, we all thought this was just, well, silly. -- Yours, J.A. Terranson [EMAIL PROTECTED] 0xBD4A95BF "Quadriplegics think before they write stupid pointless shit...because they have to type everything with their noses." http://www.tshirthell.com/
Re: I'll show you mine if you show me, er, mine
Markus Jakobsson is a really smart guy who's done some cool stuff, so I think this is probably better than it sounds in the article. His web site is http://www.informatics.indiana.edu/markus/ but I don't see any papers there that sound like what the article describes. I tried to reverse engineer the protocol from the article, and the results are below. But first let me put this into context. The security property seems to be that you send something to the server, and it sends you back something that proves that it knows your password. But neither a passive eavesdropper nor a MITM can learn anything about your password from observing or influencing the exchange. The best an attacker can do is to try to brute force your password by guessing it repeatedly and trying each guess out at the server. And this can be easily prevented by having the server refuse to answer more than a few bad password attempts. Note that this is different from simple PK based authentication, because the secret is human memorizable. And it's different from, say, having the server respond with a keyed hash of your passphrase, because an eavesdropper could then do an offline brute force search. The key feature is that the only attack is online brute forcing. There are already a lot of protocols in the literature which do this, often performing key agreement at the same time. The original one and most famous was SPEKE. There is a long list of such protocols at http://grouper.ieee.org/groups/1363/passwdPK/submissions.html. I don't know what properties this new protocol has that the old ones don't. Maybe it does have some and I am missing the point. Or there might be some patent issues that it is trying to work around. Anyway, here's my attempt at mimicking the protocol, based on the description of envelopes and carbon paper. You have a password, and so does the site you will login to. (Or, maybe the site has a salted hash of your password; you could use that instead.) You set up a homomorphic encryption system. This is one where you can send an encrypted value to someone else, and he can do certain operations on the encrypted value, like multiplying it by a constant. In this case I think we only need to encrypt the value 1, and let the other guy multiply by his constant, which makes it simpler. I think ElGamal could work: you encrypt 1 as (g^k, y^k), where you'd make up a key y = g^x on the spot. You send this to the other guy who picks a random power j and raises both elements to that power, then multiplies the 2nd one by c: (g^(k*j), y^(k*j) * c), and sends it back to you. This is now a valid ElGamal encryption of c. But an observer can't tell what c is. For a first cut at this protocol, you take each bit of the password (or salted hash) and create two encryptions of m = 1. It would look like this: E(1) E(1) E(1) E(1) E(1) ... E(1) E(1) E(1) E(1) E(1) ... You send all these to the server. The server knows your password (or salted hash) and, for each pair of encrypted values, multiplies the one corresponding to password bit b_i by some constant c_i. The other one of the pair, corresponding to !b_i, it multiplies by a random r_i. The server sets it up so that the sum of all the c_i is zero. Then it sends all of them back to you. If your passphrase started 01101... it would be: E(c_1) E(r_2) E(r_3) E(c_4) E(r_5) ... E(r_1) E(c_2) E(c_3) E(r_4) E(c_5) ... Now, you decrypt just the ones corresponding to the bits b_i and add up the decrypted plaintexts, giving you sum of c_i. If the result is zero, you know the server knew your password (or salted hash). Actually this is not quite right, because the article says that you are not supposed to be able to decrypt both ciphertext values in the pair that corresponds to a password bit. Otherwise an imposter might be able to figure out your passphrase by doing one interaction with the server, then finding an element from each pair such that they all sum to zero. This is kind of knapsacky and it might not be that hard, I'm not sure. So I think what you could do is to send a valid ElGamal encryption of 1, and a bogus value which is not an ElGamal encryption of anything. But the remote party wants to be sure that you can't decrypt them both. One way to achieve this is to arrange that the first members of each pair, g^k in the good encryption, multiply to some fixed value F for which the discrete log is not known. Maybe it's the hash of "I don't know if this will work." You can't know the DL of that hash, so you can't find two g^k values which multiply to that hash. That means that if you have a pair of ElGamal ciphertexts which have this property, only one is a real, valid ElGamal ciphertext and so only one is decryptable (I think!). So you would send, in the example above: (g^k0, y^k0)(F/g^k1, junk) (F/g^k2, junk) (g^k3, y^k3) ... (F/g^k0, junk) (g^k1, y^k1)(g^k2, y^k2) (F/g^k3, junk) ... When the server did
Re: I'll show you mine if you show me, er, mine
-- On 24 Feb 2005 at 2:29, Peter Gutmann wrote: > Isn't this a Crypto 101 mutual authentication mechanism (or > at least a somewhat broken reinvention of such)? If the > exchange to prove knowledge of the PW has already been > performed, why does A need to send the PW to B in the last > step? You either use timestamps to prove freshness or add an > extra message to exchange a nonce and then there's no need to > send the PW. Also in the above B is acting as an oracle for > password-guessing attacks, so you don't send back the > decrypted text but a recognisable-by-A encrypted response, or > garbage if you can't decrypt it, taking care to take the same > time whether you get a valid or invalid message to avoid > timing attacks. Blah blah Kerberos blah blah done twenty > years ago blah blah a'om bomb blah blah. > > (Either this is a really bad idea or the details have been > mangled by the Register). It is a badly bungled implementation of a really old idea. An idea, which however, was never implemented on a large scale, resulting in the mass use of phishing attacks. Mutual authentication and password management should have been designed into SSH/PKI from the beginning, but instead they designed it to rely wholly on everyone registering themselves with a centralized authority, which of course failed. SSH/PKI is dead in the water, and causing a major crisis on internet transactions. Needs fixing - needs to be fixed by implementing cryptographic procedures that are so old that they are in danger of being forgetten. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG Dn3N69hcbr+mL/HUTw8OhGtKmD9rHYOMN4NTBkIY 47AOCXrb7e35xm5QBsHbFVr/jfm+XwTUvzdiytKpG
Re: I'll show you mine if you show me, er, mine
"R.A. Hettinga" <[EMAIL PROTECTED]> forwarded: >Briefly, it works like this: point A transmits an encrypted message to point >B. Point B can decrypt this, if it knows the password. The decrypted text is >then sent back to point A, which can verify the decryption, and confirm that >point B really does know point A's password. Point A then sends the password >to point B to confirm that it really is point A, and knows its own password. Isn't this a Crypto 101 mutual authentication mechanism (or at least a somewhat broken reinvention of such)? If the exchange to prove knowledge of the PW has already been performed, why does A need to send the PW to B in the last step? You either use timestamps to prove freshness or add an extra message to exchange a nonce and then there's no need to send the PW. Also in the above B is acting as an oracle for password-guessing attacks, so you don't send back the decrypted text but a recognisable-by-A encrypted response, or garbage if you can't decrypt it, taking care to take the same time whether you get a valid or invalid message to avoid timing attacks. Blah blah Kerberos blah blah done twenty years ago blah blah a'om bomb blah blah. (Either this is a really bad idea or the details have been mangled by the Register). Peter.