Subject: RE: [Cfrg] one question about ElGamal encryption over a subgroup

From: "Whyte, William" <[email-masked]>
Date: Wed, 15 Oct 2003 13:04:32 -0400

The canonical reference here is

Chae Hoon Lim, Pil Joong Lee, A Key Recovery Attack on Discrete 
Log-based Schemes Using a Prime Order Subgroup (1997)

http://citeseer.nj.nec.com/lim97key.html.

There are similar attacks on ECC key agreement/encryption protocols
in Adrian Antipa, Dan Brown, Alfred Menezes, Rene Struik, Scott 
Vanstone, Validation of Elliptic Curve Public Keys. The paper isn't
online as far as I know, but a Powerpoint can be obtained from

http://grouper.ieee.org/groups/1363/WorkingGroup/presentations/pkc3-v06.ppt

The ANSI X9F1 working group has considered issues of key validation
very carefully in developing the X9.42 and X9.63 standards for discrete 
log and EC discrete log encryption, respectively. Proper key validation,
either by the encrypter or by a trusted third party, prevents attacks
of these types.

Cheers,

William

===================================
William Whyte
Director, Cryptographic R&D
Chair, IEEE P1363 Working Group
NTRU Cryptosystems
5 Burlington Woods
Burlington, MA 01803
tel:  +1.781.418.2500
fax:  +1.781.418.2532

> -----Original Message-----
> From: David Kravitz [mailto:[email-masked]]
> Sent: Wednesday, October 15, 2003 12:09 PM
> To: 'Wang, Steve'; [email-masked]
> Subject: RE: [Cfrg] one question about ElGamal encryption over a
> subgroup
> 
> 
> Steve,
> 
> Although ElGamal encryption and DSS signing use similar math, 
> this does
> not imply that they are equivalent with respect to security.  In
> particular, in ElGamal the factorization of (p-1)/q is relevant and,
> depending on the application, small-subgroup attacks by non-compliant
> encryption taking advantage of oracles may have to be considered.
> 
> --- David
> 
> David W. Kravitz, Ph.D.
> Chief Scientist,
> SPARTA, Inc.
> 5875 Trinity Parkway
> Centreville, VA 20120
> 703.988.8606 (voice)
> 703.988.8599 (fax)
> [email-masked]
> 
> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Wang, Steve
> Sent: Thursday, September 11, 2003 9:14 AM
> To: [email-masked]
> Subject: [Cfrg] one question about ElGamal encryption over a subgroup
> 
> I have one question about the security of ElGamal encryption over a
> subgroup. The original ElGamal encryption uses a large prime p and a
> generator g. What will happen if the order of g is not p-1 but another
> prime q, which divides p-1? Is the encryption secure if q is 160-bit
> long?
> 
> It sounds to me that the same logic is used in DSS and thus 
> it should be
> fine.
> 
> Thanks, Steve
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
> 

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "Anton Stiglic" <[email-masked]>
Date: Wed, 15 Oct 2003 14:03:27 -0400

A bunch of these "issues" have been described (with references and all)
in a technical report I wrote that is available here:
http://crypto.cs.mcgill.ca/~stiglic/Papers/dhfull.pdf

The paper concentrated on DH agreement, but allot of the stuff also applies
to ElGamal cryptosystems...

--Anton

----- Original Message ----- 
From: "Whyte, William" <[email-masked]>
To: "'David Kravitz'" <[email-masked]>; "'Wang, Steve'"
<[email-masked]>; <[email-masked]>
Sent: Wednesday, October 15, 2003 1:04 PM
Subject: RE: [Cfrg] one question about ElGamal encryption over a subgroup

---

From: Daniel Brown <[email-masked]>
Date: Wed, 15 Oct 2003 15:04:15 -0400

Just to clarify:

a) Decryptors (not just encryptors) should validate every ephemeral DH 
public key that they receive. One should check that ephemeral public key 
is in the right range and has the right order.  In particular, if the 
group is Zp* and the ephemeral public key is y (= g^x), one checks that 
1<y<p-1 and y^q = 1 (mod p). This second check (of the order) helps to 
avoid small-subgroup attacks that recover potentially harmful information 
about the decryptor's private key.

b) The current version of ANSI X9.42 requires p to be at least 1024 bits 
long and q to be at least 160 bits long, which suggests that q smaller 
than p can be safely used.  X9.42 also includes the following useful 
table:
Table E.2 ? Approximate Equivalence of Keys In Bits To Known Best General 
Attacks
Symmetric
 Key Agreement Scheme p
Key Agreement Scheme q
 56/80
1024
 
160
  112
2048

224
  128
3072
 
256
  192
7680
 
384
    256
15360
 
512

NOTE:  DES uses 56 key bits, TDES using 3 distinct keys has an effective 
strength of 112 bits, and AES will support 128, 192 and 256 bit keysizes.
c) If "ElGamal encryption" means ephemeral-static (1-Pass) Diffie-Hellman 
combined with some form of symmetric encryption with a key derived from 
the DH shared secret, then ElGamal encryption has no integrity protection. 
 Therefore it is "malleable" and (thus) vulnerable to adaptive 
chosen-ciphertext attacks.   Bellare and Rogaway's DHAES encryption scheme 
extends ElGamal encryption with integrity protection, thereby avoiding 
these attacks.  In IEEE P1363a, this encryption scheme is being 
standardized under the name DL/ECIES.

d) ANSI X9.42 specifies various kinds of key agreement, but not encryption 
or key transport, per se.  Key agreement can be used to accomplish a 
similar goal to public-key encryption.  DHAES, SSL/TLS, SMIME, IPSec, and 
NIST Draft SP 800-56 all include ways of using basic DH key agreement as a 
stepping stone to encrypting a message. 

====================================
Dan Brown
(905) 501-3857
Certicom Research
5520 Explorer Drive, Suite 400
Mississauga, ON L4W 5L1
====================================