RE: I'll show you mine if you show me, er, mine
James A. Donald said: There seem to be a shitload of protocols, in addition to SPEKE and DH-EKE ... Can anyone suggest a well reviewed, unpatented, protocol that has the desired properties? Unpatented will be your biggest hurdle. I collaborated on the development of a strong password protocol with the explicit goal of having such a protocol that was not patented. For details, see: http://www.usenix.org/events/sec01/full_papers/kaufman/kaufman.pdf But while we got our employers to agree not to patent the algorithm, neither we nor they are willing to defend it against infringement claims by others. (It also has not been extensively reviewed. There is no particular motivation for anyone to do so since its performance is inferior to other schemes and its patent status is uncertain.) Basically, there is no way to establish that any technology is unpatented. The best you can do is hide behind someone with deeper pockets than you do who is doing the same thing. Like hiding behind IBM when using Linux. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: I'll show you mine if you show me, er, mine
--- begin forwarded text To: [EMAIL PROTECTED] Subject: Re: I'll show you mine if you show me, er, mine Date: Wed, 23 Feb 2005 12:14:04 -0800 (PST) From: [EMAIL PROTECTED] (Hal Finney) Sender: [EMAIL PROTECTED] 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
Re: I'll show you mine if you show me, er, mine
Reading the description from http://www.stealth-attacks.info/, it seems that Peter might be right. I think this is just a re-hash of already well established ideas. In the case of a sending the password back to B, its a very similar scenario to scene III where Athena suggests to Euripides that the ticket life-time be once off (once use), Euripides goes it would make using services on the network too difficult why not give it a time stamp for the duration of the person's work day - a ticket generating ticket. The play goes on from there, in the end Charon which is then quickly renamed Kerberos is made. Then 1988 now 2005, I would say thats about 13 years... :) Name of play is Designing An Authentication System: A Dialogue In Four Scence by Bill Bryant Arash Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]