Re: El Gamal and Message Blocking

Mark Wooding <mdw@xxxxxxxxxxxxxxxx> wrote:

The usual approach is not to use ElGamal at all. It's unlikely to
be the droid you're looking for. See DLIES or ECIES.

ElGamal does implicitly, what you need to do explicitly using the
key encryption part of IES. IMO there is nothing wrong with ElGamal
and a symmetric cipher, besides that the encrypted key is longer.

ElGamal has extra pointless steps: it generates a key, encodes it as a
group element and encrypts it using a one-time pad. The IESes do a
simple half-ephemeral DH key-exchange, hash the resulting secret, and
use that as the key. The order of the operations is different: in
particular, an IES can't be given the key as an input, whereas ElGamal
can. It is this that lets the IES achieve stronger security
properties and greater efficiency.

IES is more efficient, and I wouldn't prefer ElGamal over it. Though
still there is nothing wrong with ElGamal, when used properly. Encoding
a key as a group element or the reverse operation is in almost all
implementations a matter of copying a byte array. Nothing much you
could do wrong here. If if you did something wrong in ElGamal's
key->group approach, you would likely make the same mistake in IES'
group->key approach as well.


Using ElGamal properly requires that (a) you work in a prime-order
group, [...]

You don't need to work in a prime order group. It would just make sense
to do so. The same requirement holds for DLIES as well. ECIES has some
other, more complex requirements, and I wouldn't use EC yet, but that's
personal taste.

This is just wrong. The semantic security of ElGamal is based on the
difficulty of the decision Diffie-Hellman problem. Indeed, it's
almost exactly equivalent.

[...]

To put it simply, then, ElGamal is secure in a particular group /if
and only if/ the decision Diffie-Hellman assumption holds in that
group.

A reference would have sufficed. But thanks anyway. =)


Now to the second part: the decision Diffie-Hellman assumption /does
not hold/ in groups with composite order. Why not? Suppose G has
order n = r h, where r and h are both not equal to 1. Then G has
precisely one subgroup of order r (note first that (n - 1)/r P has
order r, so it generates such a subgroup; then suppose A = a P has
order r, so a r is a multiple of n = h r, and a is a multiple of h,
but there are precisely r such multiples in the interval [0, n).)
Suppose we're given a triple (A, B, C). With probability r/n, A is in
the order-r subgroup. If this is a DH triple then C must also be in
the subgroup; otherwise r C = 0 only by coincidence, which happens
with probability r/n. Similarly for B.

It's true that the effect is quite minor when all the factors of n are
large (the the probability that A or B is in a given subgroup is at
most 1/r_0, where r_0 is the smallest prime factor of n).

The factors of the order of the group need to be large. In fact, you
don't even need to use a real generator. It suffices to generate a
large enough subgroup.


and (b) you can encode your messages as elements of this group (and
decode them again).

IES doesn't require that? You need to encode the key to the
symmetric cipher as an element of the group. No difference.

No you don't. In DLIES, the key comes out when you hash a group
element. That is, you must be able to encode a group element as an
octet string, rather than having to encode your message (usually an
octet string) as a group element.

True, but ...


Big difference: the encoding requirement is the other way around (and
much less onerous!).

.... that's the same implementational effort. It's copying byte arrays
(if at all).


Why? Their security is based on the same assumption as that of
ElGamal.

No, they're based on a different assumption, namely the (strong)
computational Diffie-Hellman assumption.

* The computational assumption: it is hard, given A = a P and B = b
P, to compute C = a b P.

* The decisional assumption: it is hard, given A = a P, B = b P, and
C, to decide /whether/ C was chosen eqyal to a b P or just chosen
uniformly at random. (You're assured that one of these
possibilities holds.)

* The /strong/ computational assumption: it is hard, given A = a P
and B = b P, to compute C = a b P, even if you have an oracle
which, given U and V, answers whether V = a U.

That's related to the way pure 'school-book ElGamal' is used. The
proper way to use it is to combine it with a strong symmetric cipher,
just like in an IES. Then ElGamal is based at least on the
computational assumption.

How the strong version makes a big difference is not clear to me. Even
if you had such an oracle, the chance of a "yes" answer (other than the
trivial pair A and P) would be neglible. Practically you would expect
it to say "no" anyway. Waiting for a "yes" answer would take the same
amount of time as brute-forcing 'a' right away.

There is one exception. DLIES and DL-ElGamal work in groups, where
there is always a 2-order subgroup generated by -1. The oracle would
tell you whether 'a' is odd or even, but that's also no problem, because
the Legendre symbol tells you anyway.


Regards,
Ertugrul.


--
http://ertes.de/

.