DISQUS

Matasano Chargen: Halvar Flake and Nate Lawson on Alternative Padding Schemes

  • Adam Morrison · 3 years ago
    e=2 is not a valid RSA exponent, since it's not coprime to (p-1)(q-1).
  • Nate · 3 years ago
    No. e=2 is Rabin, a variant of RSA.
    http://www.x5.net/faqs/crypto/q37.html
  • sargon · 3 years ago
  • Adam Morrison · 3 years ago
    Yeah, Rabin is a variant of RSA; it's not RSA.

    It's not RSA, because the signing algorithm is totally different.

    It's not RSA, because PKCS#1 says so [PKCS#1 v2.1, sec 3.1].

    It's not RSA, because if you try using e=2 in any decent RSA implementation, you won't get past the key generation phase, and things will break horribly even if you do.

    You just spent an entire blog post explaining how cryptography is hard to get right, and how the minute details of the implementation matter. Isn't it also important to know which algorithm is being used?
  • Thomas Ptacek · 3 years ago
    I think we can all easily reach a consensus that Rabin keys are "NOT" PKCS#1 v2.0 or above.

    Is there any way to have a conversation that doesn't involve us delving into the definitions of what "variant" means, or questioning the legitimacy of various sources (even I can cite credible sources that say e=2 is RSA --- for instance, Ferguson and Schneier, p 231, discussing how to choose the public exponent for RSA)?

    I'm also going to call you on comparing a blog post to an implementation of RSA.

    You seem sharp. What are your technical critiques on the posts so far?
  • Nate · 3 years ago
    1a. Rabin uses a small exponent (e=2)
    1b. RSA can use e=3
    2a. Rabin security is based on the difficulty of factoring N (p*q)
    2b. RSA, ditto
    3a. Rabin requires special formatting and redundancy checking of the result (i.e. that M is a quadratic residue mod N)
    3b. RSA requires special formatting and redundancy checking of the result (i.e. PKCS)

    In refuting the argument that small exponents in RSA are the cause of the problem (not an implementation flaw), it's perfectly legitimate to include Rabin as a counter example.

    The lesson remains: proper redundancy checking is vital to security in public key crypto, no matter what the public exponent. I hope you can agree.
  • Adam Morrison · 3 years ago
    I agree with everything you said, except the reference to Rabin's system as "low exponent RSA", which is wrong both from a technical and historical perspective.

    The details we already mentioned, plus a paper or two, affirm this assertion. If e=2 were to RSA as e=3 is, there'd be nothing to debate.

    Even Ferguson and Schneier, in that footnote you cited, allude to these differences (lthough arguably too mildly).

    I just thought that, seeing as how the series started by explaining how the little details matter, it's important not to gloss over the difference between RSA and Rabin.
  • Adam Morrison · 3 years ago
    I agree with everything you said, except the reference to Rabin's system as "low exponent RSA", which is wrong both from a technical and historical perspective.

    The details we already mentioned, plus a paper or two, affirm this assertion. If e=2 were to RSA as e=3 is, there'd be nothing to debate.

    Even Ferguson and Schneier, in that footnote you cited, allude to these differences (although arguably too mildly).

    I just thought that, seeing as how the series started by explaining how the little details matter, it's important not to gloss over the difference between RSA and Rabin.