Encrypted Key Exchange
John Savard
One of the things mentioned in Applied Cryptography was a protocol,
still patented, called Encrypted Key Exchange.
The idea behind it is to use a short key, perhaps based on a PIN, to
encrypt a public key generated for a session. Then, that public key
can be used for transferring a long session key, for use with
conventional cryptography.
*In order for EKE to yield its full benefits, it is necessary that for
each possible value of the short key, in the case of a brute-force
search, the cryptanalyst will see a valid public key, and have to
solve a public-key problem for each value.*
Considering that fact, the peculiarities of EKE become apparent:
- it is indeed much better than sending one's session key, encrypted
with the short PIN key, and then encrypted using a public-key method.
In that case, one cracks one public-key problem, and then one can do a
quick brute-force search on the possible PIN values, since trying one
only involves doing the same operations as are done by the legitimate
decryptor - only more often.
- it doesn't work well with RSA.
Factoring the modulus is the 'real' hard problem behind the RSA
public-key system. Thus, if the modulus is not encrypted, the benefits
of EKE aren't really obtained; there is still only one public-key
problem to crack, and the operation that must be tried for each
possible PIN value is one done by the legitimate encryptor, although
admittedly for key setup.
But the recommendation of the system's inventors that the modulus not
be encrypted _is_ valid, because a modulus in RSA is *not* a sequence
of random bits. Disguising it as one, by a method not involving extra
key material (i.e. replacing it by a key + itself encrypted by that
key, or only encrypting the middle bits of the key), won't solve the
problem that the test for a valid modulus is fairly trivial: check for
small factors, and then for primality.
One could, perhaps, randomize a modulus in this way: replace the last
few bits of the modulus by random bits, then add a number indicating
that the modulus to be communicated is the N-th plausible modulus,
either above or below the value given. However, I think that this
method can also be easily defeated, just by using a slightly stronger
test for plausibility than the one used by the encryption system:
diminishing returns don't set in quickly enough.
One thing to note, though: although it isn't useful for the case where
no secret key can be exchanged (exchange the 'short' key via one
public key, and then you have two public key problems, and the trials
for the PIN are eliminated), the system isn't restricted to the case
where the secret key is short. A long secret key will increase the
number of public-key problems to be solved. Of course, the system
cannot be more secure than the length of the session key, and so, if a
long secret key is possible, EKE is only useful if an even longer
session key is practical, yet a secret key that long is not.
John Savard
Thomas Wu
sew...@butterflynetZZcom.ca (John Savard) writes:
> *In order for EKE to yield its full benefits, it is necessary that for
> each possible value of the short key, in the case of a brute-force
> search, the cryptanalyst will see a valid public key, and have to
> solve a public-key problem for each value.*
The distinguishing property of any strong password method is that
a brute force attack against the password is infeasible if the
attacker has to solve at least one "hard" problem to mount the
attack.
> Considering that fact, the peculiarities of EKE become apparent:
>
> - it is indeed much better than sending one's session key, encrypted
> with the short PIN key, and then encrypted using a public-key method.
It all depends on how the "public-key method" works. In a direct
authentication setup, the client doesn't store any keys, so this
implies that the public-key method is keyed off the user's password.
That is open to a dictionary attack, making it insecure. Embedding
a worldwide public/private keypair in the software is obviously a bad
idea.
> - it doesn't work well with RSA.
>
> Factoring the modulus is the 'real' hard problem behind the RSA
> public-key system. Thus, if the modulus is not encrypted, the benefits
> of EKE aren't really obtained; there is still only one public-key
> problem to crack, and the operation that must be tried for each
> possible PIN value is one done by the legitimate encryptor, although
> admittedly for key setup.
Since the RSA modulus is recommended as 1024-bits or larger, "cracking"
it is no easier than breaking someone's PGP key. This doesn't seem to
be much of a security issue.
> But the recommendation of the system's inventors that the modulus not
> be encrypted _is_ valid, because a modulus in RSA is *not* a sequence
> of random bits. Disguising it as one, by a method not involving extra
> key material (i.e. replacing it by a key + itself encrypted by that
> key, or only encrypting the middle bits of the key), won't solve the
> problem that the test for a valid modulus is fairly trivial: check for
> small factors, and then for primality.
Agree completely. IMHO, the biggest problem with this version of EKE
using RSA is the threat of someone inserting a fake modulus, either
as man-in-the-middle or as a fake host.
--
Tom Wu * finger -l t...@xenon.stanford.edu for PGP key *
E-mail: t...@cs.Stanford.EDU "Be conservative in what you send; be liberal
Phone: (650) 725-6969 in what you accept from others."
http://www-cs-students.stanford.edu/~tjw/ Visit my homepage!
David P Jablon
In article <344f97f6...@nntp.netcruiser> John Savard wrote:
>One of the things mentioned in Applied Cryptography was a protocol,
>still patented, called Encrypted Key Exchange.
>
>The idea behind it is to use a short key, perhaps based on a PIN, to
>encrypt a public key generated for a session. Then, that public key
>can be used for transferring a long session key, for use with
>conventional cryptography.
(FYI, links to several papers on this and related
methods are at <http://world.std.com/~dpj>.)
>*In order for EKE to yield its full benefits, it is necessary that for
>each possible value of the short key, in the case of a brute-force
>search, the cryptanalyst will see a valid public key, and have to
>solve a public-key problem for each value.*
>
>Considering that fact, the peculiarities of EKE become apparent:
This is an interesting premise, but certainly not a "fact".
EKE has significant benefits even if it "merely" relies
on solving one public key problem for its strength.
As Tom Wu points out in another follow-up post, many respectable
PK applications (such as PGP) are based on just one hard problem.
EKE's goal was to make dictionary attacks on the short key
as hard as cracking a PK problem, which can be made
arbitrarily hard by increasing the number of bits in the
PK method. If it cannot, then all PK cryptography is doomed.
The presumed additional goal of making key-cracking as hard as
solving N such problems, where N is the size of the short key,
seems admirable, but perhaps not such a big deal.
Isn't it easy enough just to pick a larger bit size for the
underlying PK problem, to effectively add log N bits of strength?
>- it [EKE] is indeed much better than sending one's session key, encrypted
>with the short PIN key, and then encrypted using a public-key method.
>
>In that case, one cracks one public-key problem, and then one can do a
>quick brute-force search on the possible PIN values, since trying one
>only involves doing the same operations as are done by the legitimate
>decryptor - only more often.
EKE was originally intended to replace methods where
"verifiable plaintext" is encrypted with the short PIN key,
such as challenge/response methods. It seems like you're
presumed alternative to EKE requires pre-supplied public-keys.
>- it [EKE] doesn't work well with RSA.
A detailed attack on RSA-EKE was published earlier this year,
which exploits the special construction of RSA keys.
The password-authenticated Diffie-Hellman methods such as
DH-EKE and SPEKE do not have the problem.
>Factoring the modulus is the 'real' hard problem behind the RSA
>public-key system. Thus, if the modulus is not encrypted, the benefits
>of EKE aren't really obtained; there is still only one public-key
>problem to crack, and the operation that must be tried for each
>possible PIN value is one done by the legitimate encryptor, although
>admittedly for key setup.
No, this sounds wrong. Neither legitimate party needs to
factor the modulus. One party knows the factors by using
multiplcation to construct the composite, not by the much
harder method of factoring. Cracking just one PK problem,
whether RSA, discrete log, or whatever, is certainly
more time consuming than a small number of hash or
exponential operations. Cracking one PK problem or a small
number of them seem to be roughly equivalent tasks.
>But the recommendation of the system's inventors that the modulus not
>be encrypted _is_ valid, because a modulus in RSA is *not* a sequence
>of random bits. Disguising it as one, by a method not involving extra
>key material (i.e. replacing it by a key + itself encrypted by that
>key, or only encrypting the middle bits of the key), won't solve the
>problem that the test for a valid modulus is fairly trivial: check for
>small factors, and then for primality.
>
>One could, perhaps, randomize a modulus in this way: replace the last
>few bits of the modulus by random bits, then add a number indicating
>that the modulus to be communicated is the N-th plausible modulus,
>either above or below the value given. However, I think that this
>method can also be easily defeated, just by using a slightly stronger
>test for plausibility than the one used by the encryption system:
>diminishing returns don't set in quickly enough.
>
>One thing to note, though: although it isn't useful for the case where
>no secret key can be exchanged (exchange the 'short' key via one
>public key, and then you have two public key problems, and the trials
>for the PIN are eliminated), the system isn't restricted to the case
>where the secret key is short. A long secret key will increase the
>number of public-key problems to be solved. Of course, the system
>cannot be more secure than the length of the session key, and so, if a
>long secret key is possible, EKE is only useful if an even longer
>session key is practical, yet a secret key that long is not.
Curious. You seem to be trying to apply EKE to a new problem,
to make a stored-PK method incrementally stronger. However,
EKE works even when there is no prior agreement between the two
parties using stored PKs or certificates.
I don't know if it would help in your problem, but
I had explored another variant called M-SPEKE, where
a Diffie-Hellman modulus was constructed from a shared
password. Cracking it should require the solution of
a discrete log problem for each possible password.
In general, rather than presuming that an attacker might crack
a PK problem, it seems more natural to presume that an attacker
might steal a private key from long-term storage.
EKE or equivalents can be used in combination with
stored-key systems to make the memorized secret an
*independent* factor.
------------------------------------------------------
David P. Jablon
Integrity Sciences, Inc.
d...@world.std.com
<http://world.std.com/~dpj/>
John Savard
d...@world.std.com (David P Jablon) wrote, in part:
>In article <344f97f6...@nntp.netcruiser> John Savard wrote:
>>Factoring the modulus is the 'real' hard problem behind the RSA
>>public-key system. Thus, if the modulus is not encrypted, the benefits
>>of EKE aren't really obtained; there is still only one public-key
>>problem to crack, and the operation that must be tried for each
>>possible PIN value is one done by the legitimate encryptor, although
>>admittedly for key setup.
>No, this sounds wrong. Neither legitimate party needs to
>factor the modulus. One party knows the factors by using
>multiplcation to construct the composite, not by the much
>harder method of factoring. Cracking just one PK problem,
>whether RSA, discrete log, or whatever, is certainly
>more time consuming than a small number of hash or
>exponential operations. Cracking one PK problem or a small
>number of them seem to be roughly equivalent tasks.
Perhaps my writing is not clear.
If the modulus is NOT encrypted, then the action which, as you correctly
say, "neither legitimate party needs to" do, needs only to be done ONCE by
the attacker.
Instead, what must be done N times (or, on average, N/2 times to be
precise) is, after having factored the modulus, use it to obtain d from e -
which one legitimate party does do - during key setup.
Although EKE is specifically pitched at password security, my interest in
it is in the "privacy amplification" it provides; two parties, with a short
secret key, are able to, in a realistic manner, exchange a very long key
with commensurate security. Considerably less secure protocols could be
used to protect passwords against dictionary attacks - and, in fact, EKE
alone doesn't protect against someone grabbing your password file, since
the host computer still needs to know the actual PIN.
John Savard
David P Jablon
In article <344f97f6...@nntp.netcruiser> John Savard wrote:
>>>Factoring the modulus is the 'real' hard problem behind the RSA
>>>public-key system. Thus, if the modulus is not encrypted, the benefits
>>>of EKE aren't really obtained; there is still only one public-key
d...@world.std.com (David P Jablon) wrote, in part:
>>No, this sounds wrong. Neither legitimate party needs to
>>factor the modulus. One party knows the factors by using
>>multiplcation to construct the composite, not by the much
>>harder method of factoring. Cracking just one PK problem,
>>whether RSA, discrete log, or whatever, is certainly
>>more time consuming than a small number of hash or
>>exponential operations. Cracking one PK problem or a small
>>number of them seem to be roughly equivalent tasks.
In article <3453ff4...@nntp.netcruiser>,
John Savard <sew...@XbutterflyXnetDELETEcom.CDN> wrote:
>Perhaps my writing is not clear.
>
>If the modulus is NOT encrypted, then the action which, as you correctly
>say, "neither legitimate party needs to" do, needs only to be done ONCE by
>the attacker.
>
>Instead, what must be done N times (or, on average, N/2 times to be
>precise) is, after having factored the modulus, use it to obtain d from e -
>which one legitimate party does do - during key setup.
>
>Although EKE is specifically pitched at password security, my interest in
>it is in the "privacy amplification" it provides; two parties, with a short
>secret key, are able to, in a realistic manner, exchange a very long key
>with commensurate security. [...]
To me, the applications "password security" and "privacy amplification"
sound like the same thing. In both cases a small shared secret
is amplified to create a large one.
You've argued that RSA-EKE does not suit your purposes because it
only requires solving one hard problem. Why do you want N/2 hard
problems? Using DH-EKE or SPEKE with a suitable Diffie-Hellman
group, the attacker can be required to solve one arbitrarily
hard problem, which should be equivalent to N/2 slightly easier
ones. Are there efficiency or other considerations here?
You also seemed to imply that less secure protocols can
protect passwords:
> [...] Considerably less secure protocols could be
>used to protect passwords against dictionary attacks - and, in fact, EKE
>alone doesn't protect against someone grabbing your password file, since
>the host computer still needs to know the actual PIN.
The host does not need to know the actual PIN. With Augmented EKE,
and other alternative extended protocols, the host stores a verifier
which is a one-way function of the secret, instead of storing the
secret itself. Both classes of protocol block a variety of
network attacks, including, but not limited to eavesdropper dictionary
attack. I don't see the appeal of "considerably less secure"
alternatives.
On the other hand, no network protocol can prevent brute force
attack on a stolen password-verifier when the password has insufficient
entropy. The efficiency of the dictionary attack may
be an important consideration, but the general solution here
seems be "keep the verifier secret".