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

daw@xxxxxxxxxxxxxxxxxxxxxxxx (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.

.

Relevant Pages

  • Re: Classical times
    ... a mistake. ... decide it is in their best interests to attack Iran, Pakistan, North ... statements made about what the government would be after Saddam was ...   I do NOT ...
    (rec.motorcycles)
  • Re: Dda so^ ta.i Ha. Vie^.n Hoa Ky` dda~ chua^?n y ddanh Iraq!
    ... This is not as sample as the shield that cover their counter attack like you ... "But most people point their fingers to Bush's administration, ... the men and women in uniform." ... Maybe the war is not a mistake. ...
    (soc.culture.vietnamese)
  • Re: Question about EspressoParts
    ... There are a handful of full service espresso parts dealers based in the USA. ... Most of them, including EPNW, are incredibly responsible to and participate ... will attack IT and if you post a problem someone will attack YOU. ... In my case, EP made a mistake. ...
    (alt.coffee)
  • Re: OT: katrina deaths at superdome/ massively over-hyped...
    ... they wanted the attack to take place? ... Every mistake anybody ever made anywhere was ... > I'd imagine the White House gets a constant stream of threats around the ... You're seriously a retard, because I have made in perfectly clear in this ...
    (rec.sport.tennis)
  • Re: My whites have gone yellow ish
    ... Firstly, most "grammar nazi" ... knowledge or intelligence of the poster who originally made the mistake. ... Please don't take this as a personal attack. ... I admit that I have hovered over the killfile button with some of your ...
    (uk.comp.sys.mac)