Why are the random exponents so much bigger in the Socialist Millionaire protocol versus Diffie-Hellman key exchange?

Question

Section 8, Security considerations, of RFC3526, which defines groups used for Diffie-Hellman has a table recommending some random exponent sizes. In particular, it says:

• The strength of a key exchanged using the 1536 bit group has
  • about 90 bits strength for a 180 bit random exponent
  • about 120 bits of strength for a 240 bit random exponent

On the other hand, the Off-the-Record protocol spec, which uses that 1536 bit DH group, says:

The random exponents are 1536-bit numbers.

I'm not adhering to the OTR spec, because I'm just using the SMP part of it. But I'm interested to find out:

What is the reason to use these comparatively huge random exponents, when a DH key exchange gets what I would call "enough" strength at far lower exponent sizes? I'm interested because 240 bit random numbers make the authentication go a lot quicker.

As a bonus: how does SMP using the 2048, or 4096 bit groups with smaller random exponents compare to using the 1536 bit group with large random exponents?

Answer 1

For Diffie-Hellman, adequate security is achieved provided that:

• we work modulo a prime $p$ big enough to resist discrete logarithm (1536 bits are sufficient);
• the order of the subgroup generated by $g$ is a multiple of a big-enough prime integer $q$ ($q$ should have length $2n$ bits to achieve $2^n$ security);
• the private exponents are randomly chosen in a big enough range ($2n$-bit exponents to reach $2^n$ security).

The first two conditions are necessary for the discrete logarithm to be hard. But having hard discrete logarithm is not necessarily sufficient for the security of the cryptographic algorithm which uses that group. Diffie-Hellman appears to be reasonably secure with the conditions above. However, other protocols require a bit more. A prime example is DSA. With DSA, you work in a subgroup of size $q$ (a prime integer) generated by a conventional value $g$ modulo a big prime $p$; whenever you sign, you select a random $k$ modulo $q$ (that's a "secret exponent"). $k$ must be chosen uniformly in the $[1...q-1)]$ range; simply choosing a "big enough" $k$ is not sufficient: any bias in the selection of $k$ can be exploited to rebuild the private key from the observation of several signatures (many signatures, if the bias is slight).

So your question is: is SMP more like Diffie-Hellman, i.e. tolerates that private exponents be chosen in a subrange, or more like DSA, for which uniform selection in the whole range is necessary ? Barring any explicit indication to the contrary, it is safer to assume that uniform selection in the whole range should be used. In particular, it seems to me that non-uniform selection may imply exploitable biases in the zero-knowledge proofs which are sent along the SMP values.