Subject: [Cfrg] EC ElGamal Encryption security analysis

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 00:06:41 -0400

Where can I find some papers that look at the security of ElGamel 
Encryption?

http://en.wikipedia.org/wiki/ElGamal_encryption has a short section and 
I find the part about ElGamal encryption is unconditionally malleable of 
interest.  What is 2m?  Is this the math 2 times m?  Since m is really a 
large integer when used in the context of this algorithm?

This if m is n|s where n is a known nonce and s is the random session 
secret, then Alice will be able to determine that the message received 
was sent by Bob and not an attack message.  Or is 2m just meaning a 
second cleartext?

So I want to understand a bit more about the security here, particularly 
where the cleartext being sent consists of a known nonce and a secret.  
Is there a perferred order, n|s or s|n, for example.

---

From: "Richard L. Barnes" <[email-masked]>
Date: Thu, 24 Jun 2010 00:13:24 -0400

2m is literally "2 times m".  Since at the start of things, you're  
mapping your messages into some set of integers, you can perform math  
on them :)

More generally, if you've got a message m that you know encrypts as  
(c1, c2), then you can compute the encrypted version of any other  
message m': You just compute a multiplier k=m'/m and the encrypted  
version of m' is (c1, k*c2).

On Jun 24, 2010, at 12:06 AM, Robert Moskowitz wrote:

> http://en.wikipedia.org/wiki/ElGamal_encryption has a short section  
> and I find the part about ElGamal encryption is unconditionally  
> malleable of interest.  What is 2m?  Is this the math 2 times m?   
> Since m is really a large integer when used in the context of this  
> algorithm?
>
> This if m is n|s where n is a known nonce and s is the random  
> session secret, then Alice will be able to determine that the  
> message received was sent by Bob and not an attack message.  Or is  
> 2m just meaning a second cleartext?
>
> So I want to understand a bit more about the security here,  
> particularly where the cleartext being sent consists of a known  
> nonce and a secret.  Is there a perferred order, n|s or s|n, for  
> example.
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 00:33:35 -0400

> version of m' is (c1, k*c2).

So if m is a session key, this is a DoS attack against the use of that 
key, as Alice will have a different key than Bob. If the message that 
sent (c1, c2) is MAC authenticated with m, then Alice will know that it 
was altered. The attacker does not know what m is so does not know what 
m' is. The attacker is just able to build (c1, k*c2), but could not 
construct the MAC with m'. So the message would fail authentication and 
Alice will drop it as forged. Yet Another Interesting DoS. ???

I think I am following what this is about...

>> malleable of interest. What is 2m? Is this the math 2 times m? Since 
>> m is really a large integer when used in the context of this algorithm?
>>
>> secret, then Alice will be able to determine that the message 
>> received was sent by Bob and not an attack message. Or is 2m just 
>> meaning a second cleartext?
>>
>> particularly where the cleartext being sent consists of a known nonce 
>> and a secret. Is there a perferred order, n|s or s|n, for example.
>>
>>

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 24 Jun 2010 16:44:11 +1200

Robert Moskowitz <[email-masked]> writes:

>http://en.wikipedia.org/wiki/ElGamal_encryption has a short section and I
>find the part about ElGamal encryption is unconditionally malleable of
>interest. What is 2m? Is this the math 2 times m? Since m is really a large
>integer when used in the context of this algorithm?

For things like this, Wikipedia is not a primary source of information, it's a
source of links to information (and sometimes not even that). If you want
in-depth coverage I'd recommend the Handbook of Applied Cryptography, which
you can either buy (or get from a library), or download from
http://www.cacr.math.uwaterloo.ca/hac/.

Peter.

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 06:11:58 -0400

On 06/24/2010 12:44 AM, Peter Gutmann wrote:
> Robert Moskowitz<[email-masked]>  writes:
>
>    
> source of links to information (and sometimes not even that).

That was what I was implying.  Wiki was only giving some hints of 
issues.  I want some solid papers that I might have the possiblity to 
plow through...

>   If you want

I will pull my copy off the shelf and see what it has to teach me on this.