Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Imagine that your lecturer and the undergraduate office have conducted a key exchange protocol after which both of them hold the string $X$. Yet, it is possible that a curious student sitting next to the lecturer in the bus may have gained some information $E$ about $X$. (Un)fortunately, the student eavesdropper Eve has gained only $1000$ bits of information $E$ about $X$ from the quick glance. If $X$ contains 1 million bits and was chosen randomly beforehand, describe how the lecturer and the undergraduate office can produce a fully secure key $K$ from $X$ to encrypt the final exam for electronic transmission, such that student eavesdropper Eve knows essentially nothing about the key $K$.

share|improve this question
Is this homework? The answer is to hash $X$, but I'll let you figure out the reasoning yourself. Note that if Eve truly only learned the individual values of 1000 of the million bits you can just hash 1256 bits to get a 256-bit security level, by the pigeonhole principle. – orlp Nov 22 '13 at 8:54
@nightcracker : $\:$ Could your suggestion be shown to be secure in the plain model? $\hspace{1.4 in}$ – Ricky Demer Nov 22 '13 at 9:53
@nightcracker I would guess you need a KBKDF here (e.g. HKDF or one of the NIST SP 800-108 algorithms). It's what's they are there for. Hashes may not be secure enough (in principle, I would think that just using SHA-2 would be secure enough in practice). – Maarten Bodewes Nov 22 '13 at 10:33
Probably, what is wanted is an argument that extracts a key $K$ from $X$ that Eve has no information about. If you just need a reasonable key size (say 256 bits), there's no need to use hash functions. Hint: partition and xor. – K.G. Nov 22 '13 at 10:52
HKDF (with SHA-2 as underlying hash) is the cleanest solution IMO. But a plain SHA-2 hash to extract the entropy would be perfectly fine. // In theory there are some provably secure constructions, in practice SHA-2 I'd prefer a proper hash like SHA-2 over all of them. – CodesInChaos Nov 22 '13 at 10:56
up vote 0 down vote accepted

I think that it's more proper for your title to be named "Why hashing the shared value to get session key?" Next I'll answer your question in my understanding.

The basic problem is to establish a shared key between Lecturer and undergraduate office securely. In the original Diffie-Hellman key-exchange protocol, Alice and Bob use the $g^{ab}$ as their session key. This basic DH protocol is based on CDH assumption, but CDH assumption alone can not ensure that we can use all the bits of $g^{ab}$ securely, it can only make sure that we can obtain a hard core bit which is unpredictable. So the straight idea is to run the protocol $k-times$ to get secure $k$ bits. But it's undesirable and inefficient. So, in order to make the weak bits of $g^{ab}$ as strong as others, usually we hash the shared value to get the final session key.

But another problem you need to consider is the key-exchange protocol's security, so that you can establish a session key between lecturer and undergraduate office. I think key-exchange protocol's security is more important. And it's vulnerable to kinds of attacks.As your question is not about it, so I just answer you question in my view.

share|improve this answer
The slightly less straight but still provably secure-if-CDH-is-hard idea is to run the protocol $\:\Theta(k/(\log(k)))\:$ times and obtain logarithmically many hard-core bits, as described on page 32 of this paper. $\hspace{1.06 in}$ – Ricky Demer Nov 23 '13 at 2:05
It is indeed possible to rely on the CDH assumption in the random oracle model, and for that you need to hash. However, it is better to reduce the security of the basic Diffie-Hellman key exchange protocol to the DDH (decisional Diffie-Hellman) assumption. The reason that you then need hash is to extract a close-to-uniform key from the group element that is obtained from the DH key exchange (since a group element is not uniformly distributed so you can't use it or a substring of it directly as a symmetric key). The same holds for ECDH. – Yehuda Lindell Aug 20 '15 at 16:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.