rsa implementation question

[Bryan Olson]

Hi Heiko. I didn't mean any offense by "I agree with about half
of Heiko Wundram's response."  This is what I do for a living,
so I tend to sweat details and push points.


Heiko Wundram wrote:
 > Am Donnerstag, 12. August 2004 02:36 schrieb Bryan Olson:
 >
 >>There is a notion of blocks in many public-key ciphers,
 >>including RSA.  The modulus n in RSA is composite, not prime.
 >>The "only the notion" statement implies that integer modular
 >>arithmetic is the only base for public-key cryptography, which
 >>is not true.
 >
 > Pardon me, yeah, the modulus is composite, I should've rather said 
that most
 > public key ciphers work in Z{n}. And I know that it's pretty easy to
 > generalize ElGamal to work in other rings than Z, or take bucket 
public key
 > cryptography for example.

I don't know what "bucket public key" cryptography is.  Google
finds no matches.

Incidentally, ElGamal generalizes to groups; they don't have to be
rings. (Generalizes in the sense that it can verify what it
signs and decrypt what it encrypts; it's insecure in many
groups/rings).

 > I know of others, but: have you ever seen an implementation or use 
case of
 > some algorithm not working in Z{n}(*)? I have not, at least not when 
working
 > with computers.

Sure.  I worked for several years for Certicom, the leader in
elliptic-curve cryptography (ECC).  ECC is efficient, deployed,
and now part of the federal standard for digital signatures,
FIPS 186-2 (and the draft of FIPS 186-3).

 >>Try the book you cited, section 11.2.3, Note 11.10, Example
 >>11.11, and Remark 11.12.
 >>
 >>    http://www.cacr.math.uwaterloo.ca/hac/
 >
 > Yup, I read those, and yeah, I know what they are talking about, and 
yeah,
 > that's not what I said. It's not about decrypting to sign, encrypting to
 > verify, it's about the redundancy function.

Which decrypt-to-sign doesn't have.  In particular, look at your
code.  HAC says, "Selection of an appropriate [redundancy
function] is critical to the security of the system."  That's a
key place where your code falls down.

 > In case you use a proper hash
 > function (I'm talking about identity with SHAing before signing),
 > this attack blatantly fails,

Actually, I was the one who wrote "Always hash and pad, for any
size message," and included code that uses SHA-1.  Your follow-
up code didn't hash at all.  Since the attack fails for the
method I use, but works against yours, I don't see what you are
arguing.

 > as it would mean that you'd have to find hash collisions.
 > Even when I can easily find a m~ for which I have a valid signature m,
 > finding a plaintext for m~ which is meaningful should be impossible, 
due to
 > the hashing, for "long enough plaintext."

This one is subtle.  If I read your pseudo-code correctly, and
in the place of the message we assume a SHA-1 hash, then there
are 160 bits of hash digest, 16-bits of length, and the rest of
the bits are random.   Assuming the currently-most-popular RSA
key size, 1024 bits, the attacker has to control just 176 out of
1024 bits.  The verifier can check those 176 bits, but 847 or
848 bits can be anything.

I'm not sure off-hand how weak it is, but none of the currently-
respected signature methods allow a single hash digest to have
anywhere near 2^847 valid signatures in a 2^1024 signature
space.


 > And the example code I gave was not about leaving out hashing before 
putting
 > it throught the identity function as "redundancy", it was exactly about
 > reducing redundancy, which probably I was to stupid to explain 
correctly,
 > but I'll try now.

I can't read your mind.  I only knew what your post said your
code was about: "what I always implemented is something like
[...]".

The state-of-the art signature methods agree with you that some
randomness is a good thing.  The need for randomness in
signatures is not yet well-understood; it's an assumption of the
(relative) security proofs, but no one has yet proved it is
necessary.


 >>Don't do that, even for encryption.  See Bleichenbacher's
 >>attacks on RSA encryption:
 >>
 >>  http://www.bell-labs.com/user/bleichen/bib.html
 >
 >
 > Link doesn't work...

Hmm... works for me.  Odd.  Googling "Bleichenbacher" + "RSA"
should find it.


 > But anyway, look at the same book on page 288, (ii):
 >
 > "A pseudorandomly generated bitstring should be appended to the 
plaintext
 > before encryption (this is also called salting)."
 >
 > That's exactly what my little example was trying to do: append a salt 
to the
 > data which was being encrypted.

And that's why I didn't fault your example for lack of
randomness. (Though technically the message and length could
fill the block, and thus not allow any randomness.  That would
be a big mistake for encryption, and arguably a mistake for
signatures.)

If you have questions about these things, I suggest asking them
on sci.crypt.  My advice here is to use cryptosystems that
experts have already vetted; do not roll your own variants.


-- 
--Bryan