rationale for one-way function in a key agreement scheme
in [Cryptography]
|
From: Rainer Urian on 27 Feb 2010 07:47 Hi, I wonder what is the reason for using a one-way function in a key agreement scheme. For instance, in an ECDH scheme Alice and Bob share a secret point Z after exchanging their public keys. From Z there will be derived the symmetric secret key by a one-way function. I wonder what is the rationale behind this one-way function. Would it be unsafe to just use parts of Z as the symmetric key (or a non-one-way function f(Z) ) ? Thanks, Rainer
From: Thomas Pornin on 27 Feb 2010 11:35 According to Rainer Urian <rainer(a)urian.eu>: > I wonder what is the rationale behind this one-way function. Would it be > unsafe to just use parts of Z as the symmetric key (or a non-one-way > function f(Z) ) ? ECDH has a lot of mathematical structure in it. It security lies in the computational infeasibility to compute abG from aG and bG; but that infeasibility does not mean that the attacker cannot compute a part of abG. If you use a n-bit curve, discrete logarithm has cost O(2^(n/2)); this means that, possibly, an attacker could guess half of the resulting n-bit abG value while still not contradicting the alleged safety of the Diffie-Hellman primitive. I do not claim that I know how to guess bits of the result; but I cannot claim that it is not feasible. Using only parts of the ECDH result means that you walk outside of the carefully trodden path which cryptographers have traced in the last 30 years. In other words, the ECDH result is worth "n/2 bits" only if you use the complete result. If you have a 256-bit curve, you get the "128-bit security" only if the 128-bit symmetric key you use is derived from the whole 256-bit ECDH result. A hash function is just the right tool to use, to reduce a 256-bit value (with 128-bit entropy) into a 128-bit symmetric key without losing some of that entropy. --Thomas Pornin
From: Kristian Gj�steen on 27 Feb 2010 15:42 Rainer Urian <rainer(a)urian.eu> wrote: >I wonder what is the reason for using a one-way function in a key agreement >scheme. >For instance, in an ECDH scheme Alice and Bob share a secret point Z after >exchanging their public keys. From Z there will be derived the symmetric >secret key by a one-way function. >I wonder what is the rationale behind this one-way function. Would it be >unsafe to just use parts of Z as the symmetric key (or a non-one-way >function f(Z) ) ? Decision Diffie-Hellman says that, given aP and bP, you know nothing about abP. In other words, you don't need to worry about how you deduce keys from abP. However, in many protocols, the attacker will often have access to keys derived from points related to abP. If keys are derived in a too "trivial" manner, these keys might be related to keys derived from abP. But if we use a random-oracle-style hash function, we destroy any relationship and the related keys usually turn out useless. Note that we need more than "one-way-ness", we need some random oracle-like properties. One good example is hashed-Diffie-Hellman (ECIES is the main example scheme). A few more half-baked remarks (someone will probably explain why they are incorrect): Another reason is to get provable security. I don't remember exactly, but I think there's a provably secure Korean signature scheme which is essentially a variant of DSA, but where reduction modulo some prime is replaced by a hash. Similarily, HMQV is (superficially) derived from MQV by hashing instead of reducing modulo some prime. Neither application of hashing significantly improves real security, but we get provable security... -- Kristian Gj�steen
From: Joseph Ashwood on 27 Feb 2010 16:15 "Rainer Urian" <rainer(a)urian.eu> wrote in message news:hmb489$4vb$02$1(a)news.t-online.com... > I wonder what is the reason for using a one-way function in a key > agreement scheme. > For instance, in an ECDH scheme Alice and Bob share a secret point Z > after exchanging their public keys. From Z there will be derived the > symmetric secret key by a one-way function. > I wonder what is the rationale behind this one-way function. Would it be > unsafe to just use parts of Z as the symmetric key (or a non-one-way > function f(Z) ) ? Actually it serves several purposes. The one-way function (typically a hash) gives a fixed size regardless of the size of the public keys. The one-way function also serves as a buffer preventing leakage of a key from leaking the shared secret. The third offering off the top of my head is entropy smoothing, if there is a small bias found in output of the secret sharing scheme it can still be protected by using an entropy smoothing algorithm like the one-way function. The last is use as a compressor, as Thomas pointed out, the various public key algorithms are not perfectly entropy dense, a 128-bit equivalent strength will be much larger than 128 bits, by compressing the larger value to (or close to) maximum entropy density. This isn't necessarily the complete list of reasons, in fact I'm quite certain it isn't, but these are good reasons for the one-way function. Joe
From: Rainer Urian on 28 Feb 2010 17:01 "Kristian Gj�steen" <kristiag+news(a)math.ntnu.no> schrieb im Newsbeitrag news:hmc02v$l5l$1(a)orkan.itea.ntnu.no... > Another reason is to get provable security. I don't remember exactly, > but I think there's a provably secure Korean signature scheme which is > essentially a variant of DSA, but where reduction modulo some prime is > replaced by a hash. Similarily, HMQV is (superficially) derived from > MQV by hashing instead of reducing modulo some prime. > > Neither application of hashing significantly improves real security, > but we get provable security... regarding provable security and especially HMQV you should read the AMS article by N. Koblitz: www.ams.org/notices/200708/tx070800972p.pdf and the "letters to the editor" of the poor victims ..... www.ams.org/notices/200711/tx071101454p.pdf this is real high-quality fun .... ------- Rainer
|
Next
|
Last
Pages: 1 2 Prev: Keyspace size of a synchronous stream cipher Next: Advantages of digital signatures over MACs? |