linux-kernel - Re: [PATCH resend][CRYPTO]: RSA algorithm patch

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <a781481a0704121257v19c82552gac7f60784c7bafa@mail.gmail.com>
Date:	Fri, 13 Apr 2007 01:27:22 +0530
From:	"Satyam Sharma" <satyam.sharma@...il.com>
To:	"Indan Zupancic" <indan@....nu>
Cc:	"Tasos Parisinos" <t.parisinos@...ensis.com>,
	"Bill Davidsen" <davidsen@....com>,
	"Andi Kleen" <andi@...stfloor.org>, herbert@...dor.apana.org.au,
	linux-kernel@...r.kernel.org, randy.dunlap@...cle.com
Subject: Re: [PATCH resend][CRYPTO]: RSA algorithm patch

> > There are some other better reasons for the bloat in the GNU MP lib,
> > though. Tasos' code uses the rsa_cipher() as a dual-purpose primitive.
> > Feed it the plaintext (p), public exponent (e) and public modulus (n),
> > and you get the ciphertext (c = p^e mod n). Feed it the ciphertext,
> > private exponent (d) and public modulus, and you get the plaintext (p
> > = c^d mod n) back. All modern RSA implementations, however, prefer
> > preserving the prime numbers (p, q, and their other derivatives such
> > as d mod (p-1), d mod (q-1) and inverse of q modulo p) generated at
> > the time of key generation along with the private exponent as the
> > complete "private key" (this is what is recommended by PKCS#1 too)
> > which enables us to use the chinese remainder theorem to decrypt
> > faster than simply do an (expensive) modulo exponentiation again.
>
> Which, according to the Wikipedia page on RSA, is susceptible to timing
> attacks, which requires measures to counter that (that might be needed in
> Tasos' implementation too though).

Of course, I'd rather code to the PKCS#1 RSA Cryptography Standard
than an entry-level Wikipedia page :-) Timing attacks are particularly
problematic on smart cards (too slow, and with predictable operation
times, if not using constant-time crypto implementations) and not
really worthwhile in practice on any other platform where there's
enough noise around to make accurate timing difficult (that
hyper-threading "vulnerability" discovered some time back comes to
mind). Even so, constant-time crypto implementations do take care of
them, though I agree the GPG code too lacks that.

> > Of course, that would then *force* other users such as modsign to
> > re-implement their own library for their needs again, thus defeating
> > the exercise of merging this bare-bones MPI library into the kernel in
> > the first place, as you have mentioned.
>
> Not if they go the other way round and strip everything except DSA functionality.
> The question is, is an MPI library wanted, or do people just want RSA or DSA?

I do agree that only those parts of an MPI lib that are really needed
by any users must be included. But then we don't want to end up in a
situation where we merge such a small MPI library that code and/or
functionality are being sadly duplicated across users who want
different asymmetric cryptosystems (note the 2 DLMs in mainline, for
example). When we want to support both RSA and DSA, which require a
diverse set of MPI operations and primitives, I don't see how we can
still continue to retain the simplistic and "spartan" RSA-only MPI lib
that this code provides.

Cheers,
S
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/