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

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.
 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.
 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).
 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.
Received on Mon May 1 02:06:33 2006