Re: gnupg rsa question // why use e of 41 ?

daw@taverner.cs.berkeley.edu (David Wagner) writes:

>Unruh wrote:
>>Nuts. RSA without proper padding is still RSA. The manipulations are
>>identical. It is an implimentation mistake. And the ways to pad are legion.

>Nuts to you too. The padding mode is part of the algorithm. The spec has
>to state what padding mode is in use; this detail is crucial for security,
>and crucial for interoperability. If the spec doesn't specify what
>padding mode will be used, the spec doesn't provide enough information
>to allow two implementations to interoperate. Any spec that fails to
>specify the padding mode is deficient.

>Any implementation that grossly fails to even try to implement the
>algorithm in the spec has serious problems, problems that are far worse
>than a mere implementation mistake. Implementation mistakes refer to
>trying in good faith to implement the right algorithm, but unintentionally
>getting some detail wrong; that's a very different kind of mistake from
>willfully implementing the wrong algorithm.

>>>With improper padding, even e=65537 is insecure.
>>
>>Well, no. The probability of happening to have a clear text of length
>>1024/65537 is miniscule. So miniscule it is zero.

>Perhaps you are unaware of some of the attacks on unpadded RSA.
>I'm not just making this up; e=65537 without padding really is insecure.
>I'll list a few example attacks:
> 1) Hastad's broadcast attack.

A bit unlikely for 65537.

> 2) The lack of semantic security (due to the absence of randomness)
> means that you can recover M given M^e (mod n), if the message space
> has low entropy, just by trying all possible values of M, raising
> them to the e-th power, and seeing which yields the observed ciphertext.

Agreed.
> 3) There are attacks (e.g., chosen ciphertext attacks) based on the
> homomorphic properties of unpadded RSA.
> 4) The Franklin-Reiter attack: if you encrypt two messages M,M' that
> satisfy a relationship M' = f(M) for some polynomial f, then an attacker
> can recover M and M' in time O(e^2).

Since all messages are related by a polynomial, this would say all messages
can be decrypted. (M1=M2+(M1-M2)) I assume you mean related by a publically
known polynomial.

> 5) There are likely to be chosen-ciphertext reaction attacks, along
> the lines of Bleichenbacher's attack on PKCS#1.

??

>It sounds like maybe you weren't aware about all of these attacks.
>If that is correct, with all due respect, you can't have an informed
>opinion on the security properties of unpadded RSA without understanding
>the known attacks on unpadded RSA.

I accept my chastisement. Thanks for the information.
Received on Mon May 1 02:06:34 2006