RSA

RSA

[Michel Machado]

Hi there,

   I'm implementing a new network stack in Linux's kernel [1], and I
need a RSA implementation to keep the guarantees of the design [2].

   Searching the archive of Linux's mailing lists, I've found that
adding RSA to the kernel has been already tried, but it was left out
because the uses were not convincing then.

   I intend to submit my work [3, 4] when I get a reasonable working
version. Until there, could anyone point me to a working patch to add
RSA to the kernel? The old patch [5] doesn't integrate with the current
Crypto API.

   Is there hope to have RSA added to Linux? If not for a ready use,
it'd help to experiment with things that are still in the making.

[1] http://www.cs.cmu.edu/~xia/
[2] http://reports-archive.adm.cs.cmu.edu/anon/2011/CMU-CS-11-100.pdf
[3] git://github.com/AltraMayor/XIA-for-Linux.git
[4] git://github.com/AltraMayor/xiaconf.git
[5] http://lwn.net/Articles/228892/

-- 
[ ]'s
Michel Machado

Re: RSA

[Dmitry Kasatkin]

Hi,

Please look to the patch just before your email...
[RFC v1.1 2/5] crypto: ksign - digital signature verification support

It implements RSA verification for IMA/EVM.
May be it would be interesting to you.

- Dmitry

On 11/08/11 21:30, Michel Machado wrote:
> Hi there,
>
>    I'm implementing a new network stack in Linux's kernel [1], and I
> need a RSA implementation to keep the guarantees of the design [2].
>
>    Searching the archive of Linux's mailing lists, I've found that
> adding RSA to the kernel has been already tried, but it was left out
> because the uses were not convincing then.
>
>    I intend to submit my work [3, 4] when I get a reasonable working
> version. Until there, could anyone point me to a working patch to add
> RSA to the kernel? The old patch [5] doesn't integrate with the current
> Crypto API.
>
>    Is there hope to have RSA added to Linux? If not for a ready use,
> it'd help to experiment with things that are still in the making.
>
> [1] http://www.cs.cmu.edu/~xia/
> [2] http://reports-archive.adm.cs.cmu.edu/anon/2011/CMU-CS-11-100.pdf
> [3] git://github.com/AltraMayor/XIA-for-Linux.git
> [4] git://github.com/AltraMayor/xiaconf.git
> [5] http://lwn.net/Articles/228892/
>

Re: RSA

[Michel Machado]

Hi Dmitry,

   Thanks for pointing out that patch. I does make bringing a full RSA
API into the kernel easier, but it doesn't do it. I may end up doing it
myself, and could certainly use the MPI library you're adding with that
patch, but I'd rather not since I already have a lot on my plate.

-- 
[ ]'s
Michel Machado


On Thu, 2011-08-11 at 22:00 +0300, Dmitry Kasatkin wrote:
> Hi,
> 
> Please look to the patch just before your email...
> [RFC v1.1 2/5] crypto: ksign - digital signature verification support
> 
> It implements RSA verification for IMA/EVM.
> May be it would be interesting to you.
> 
> - Dmitry
> 
> On 11/08/11 21:30, Michel Machado wrote:
> > Hi there,
> >
> >    I'm implementing a new network stack in Linux's kernel [1], and I
> > need a RSA implementation to keep the guarantees of the design [2].
> >
> >    Searching the archive of Linux's mailing lists, I've found that
> > adding RSA to the kernel has been already tried, but it was left out
> > because the uses were not convincing then.
> >
> >    I intend to submit my work [3, 4] when I get a reasonable working
> > version. Until there, could anyone point me to a working patch to add
> > RSA to the kernel? The old patch [5] doesn't integrate with the current
> > Crypto API.
> >
> >    Is there hope to have RSA added to Linux? If not for a ready use,
> > it'd help to experiment with things that are still in the making.
> >
> > [1] http://www.cs.cmu.edu/~xia/
> > [2] http://reports-archive.adm.cs.cmu.edu/anon/2011/CMU-CS-11-100.pdf
> > [3] git://github.com/AltraMayor/XIA-for-Linux.git
> > [4] git://github.com/AltraMayor/xiaconf.git
> > [5] http://lwn.net/Articles/228892/
> >
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: RSA

[kartikey bhatt]

hey i am gonna look at the code right now.
will keep in touch.

"Tom has indicated a few ways to go about this which I will send you."
waiting for details.

Joy Latten <latten@austin.ibm.com> wrote
>Great!!
>
>Our current goal is to just add RSA encryption and decryption
>to the kernel. We are interested in porting the bignum/mpi and
>rsa implementations from libtomcrypt, http://www.libtomcrypt.org.
>When I say we, I am referring to myself and my coworker, Serge Hallyn.
>You have probably seen a few notes between Serge and Tom, libtomcrypt's
>author, on lkml about RSA.
>
>Tom has indicated that the mpi will perhaps need some work in
>lower stack usage (mp_extpmod uses a bit), lower heap usage
>where possible, and remove any non-supported opcodes (e.g. integer 
>division).
>
>Tom has indicated a few ways to go about this which I will send you.
>
>Let me know when you get to take a look at the code.
>If you have any questions, please let me know. Thanks!!
>
>Joy
>
>
>
> >I would like to work on coding of algorithms and
> >especially developing mpi_t for kernel.
> >
> >Kartikey
> >
> >
> >>From: Joy Latten <latten@austin.ibm.com>
> >>To: kartik_me@hotmail.com
> >>CC: linux-kernel@vger.kernel.org, serue@us.ibm.com
> >>Subject: Re: RSA
> >>Date: Fri, 18 Jun 2004 21:56:10 -0500
> >>
> >>Great!! Thanks!  What are you interested in doing?
> >>
> >>Joy
> >>-------------------------------------------------------------
> >>
> >>
> >>i would like to contribute.
> >>
> >>On Tue, 15 Jun 2004, Joy Latten wrote:
> >>
> >>Is anyone working on implementing RSA encryption/decryption into the
> >>kernel's cryptoapi? If not, I was considering starting such a project.
> >>
> >>James wrote:
> >>
> >>Not that I know of.  Would you be looking at this in terms of a generic
> >>asymmetric crypto API?
> >>

_________________________________________________________________
Pay Cash on delivery on lakhs of products. 
http://go.msnserver.com/IN/50757.asp Only on Baazee.com

Re: RSA

[tom st denis]

--- kartikey bhatt <kartik_me@hotmail.com> wrote:
> hey i am gonna look at the code right now.
> will keep in touch.
> 
> "Tom has indicated a few ways to go about this which I will send
> you."
> waiting for details.

Um to clear up something here.  Joy and Serge are going to be the
developers on this module.  I'm just helping out where I can with my
knowledge of crypto/math/LibTom internals.  

Specifically a good starting place is to rip "mpi.c" out of LibTomCrypt
and start stripping it down.  You don't need things like the
Karatsuba/Toom-Cook multipliers, Jacobi symbol, various prime functions
[next_prime, fermat testing, etc].  You won't need the diminished radix
and Barrett reduction algorithms, etc, etc, etc.

In a recent project [see my C.V. for details] I managed to get a
"optimized for size" mpi.c down from 29KB to 5KB on an x86 with GCC.

Naturally this won't be that small since you want to leave in things
like the Comba mult/sqr algorithms and the full exptmod routine.  But
definitely around 7-10KB is possible on the x86.  

Then of course you have the RSA routines on top of that.  Depending on
whether you need PKCS #1 v2 or v1.5 you can do one of two things.  I
have both v2 and v1.5 padding in LibTomCrypt [and specifically in the
v0.97 release I reduced the stack usage to way south of 4KB].  So if
you're using v1.5 you'll have to write your own rsa encrypt/sign code
[I have a key-gen and CRT optimized exptmod you can rip off].  

On the plus side all of my code is ISO C portable, thread safe and well
tested [been used by quite a few people].  There are enough goodies in
LibTomCrypt to make this happen and you're all entitled to
rip/relicense as required ;-)

Tom


		
__________________________________
Do you Yahoo!?
Yahoo! Mail - Helps protect you from nasty viruses.
http://promotions.yahoo.com/new_mail

Re: RSA

[kartikey bhatt]

I would like to work on coding of algorithms and
especially developing mpi_t for kernel.

Kartikey


>From: Joy Latten <latten@austin.ibm.com>
>To: kartik_me@hotmail.com
>CC: linux-kernel@vger.kernel.org, serue@us.ibm.com
>Subject: Re: RSA
>Date: Fri, 18 Jun 2004 21:56:10 -0500
>
>Great!! Thanks!  What are you interested in doing?
>
>Joy
>-------------------------------------------------------------
>
>
>i would like to contribute.
>
>On Tue, 15 Jun 2004, Joy Latten wrote:
>
>Is anyone working on implementing RSA encryption/decryption into the
>kernel's cryptoapi? If not, I was considering starting such a project.
>
>James wrote:
>
>Not that I know of.  Would you be looking at this in terms of a generic
>asymmetric crypto API?
>
>_________________________________________________________________
>Screensavers for every mood! Jazz up your screen!
>http://www.msn.co.in/Download/screensaver/ Bring your PC to life!
>

_________________________________________________________________
Expressions unlimited! The all new MSN Messenger! 
http://server1.msn.co.in/sp04/messenger/  Change the way you communicate!

Re: RSA

[Joy Latten]

Great!! Thanks!  What are you interested in doing?

Joy
-------------------------------------------------------------


i would like to contribute.

On Tue, 15 Jun 2004, Joy Latten wrote:

Is anyone working on implementing RSA encryption/decryption into the
kernel's cryptoapi? If not, I was considering starting such a project.

James wrote:

Not that I know of.  Would you be looking at this in terms of a generic
asymmetric crypto API?

_________________________________________________________________
Screensavers for every mood! Jazz up your screen! 
http://www.msn.co.in/Download/screensaver/ Bring your PC to life!

Re: RSA

[kartikey bhatt]

i would like to contribute.

On Tue, 15 Jun 2004, Joy Latten wrote:

Is anyone working on implementing RSA encryption/decryption into the
kernel's cryptoapi? If not, I was considering starting such a project.

James wrote:

Not that I know of.  Would you be looking at this in terms of a generic
asymmetric crypto API?

_________________________________________________________________
Screensavers for every mood! Jazz up your screen! 
http://www.msn.co.in/Download/screensaver/ Bring your PC to life!

RSA

[Joy Latten]

Is anyone working on implementing RSA encryption/decryption into the
kernel's cryptoapi? If not, I was considering starting such a project.

Regards,
Joy Latten

Re: RSA

[James Morris]

On Tue, 15 Jun 2004, Joy Latten wrote:

> Is anyone working on implementing RSA encryption/decryption into the
> kernel's cryptoapi? If not, I was considering starting such a project.

Not that I know of.  Would you be looking at this in terms of a generic 
asymmetric crypto API?


- James
-- 
James Morris
<jmorris@redhat.com>

Re: RSA

[Serge E. Hallyn]

(repeating a privately posted question for all to respond)

Is a separate generic assymetric crypto API really necessary?

The cryptoapi usage model is to do a setkey before any encrypt or decrypt.
The setkey will be done with either a public or private key.  So there is no
need to have a public_key_alg with separate public_encrypt and
private_encrypt functions, as this distinction is implied at the setkey
time.  So our plan was to just add another crypto_alg for rsa_1024.

If anyone can point out why this is insufficient, then we will certainly
reconsider.

thanks,
-serge

Quoting James Morris (jmorris@redhat.com):
> On Tue, 15 Jun 2004, Joy Latten wrote:
> 
> > Is anyone working on implementing RSA encryption/decryption into the
> > kernel's cryptoapi? If not, I was considering starting such a project.
> 
> Not that I know of.  Would you be looking at this in terms of a generic 
> asymmetric crypto API?
> 
> 
> - James
> -- 
> James Morris
> <jmorris@redhat.com>

Re: RSA

[tom st denis]

--- "Serge E. Hallyn" <serue@us.ibm.com> wrote:
> (repeating a privately posted question for all to respond)
> 
> Is a separate generic assymetric crypto API really necessary?

It depends on how the symmetric crypto API has been implemented
[warning: I'm a kernel looking-at-code newbie so I'm just chiming in my
crypto two cents ;-)].

> The cryptoapi usage model is to do a setkey before any encrypt or
> decrypt.
> The setkey will be done with either a public or private key.  So
> there is no
> need to have a public_key_alg with separate public_encrypt and
> private_encrypt functions, as this distinction is implied at the
> setkey
> time.  So our plan was to just add another crypto_alg for rsa_1024.

In essence for a digsig module you'll require the ability to 

1.  import a PK key [from a binary packet or a cert, preferably the
former].
2.  free a PK key from memory (no need to waste dynamic resources like
bignums while not being used).
3.  ability to sign/verify/encrypt/decrypt which amounts to a exptmod
and PKCS #1 [v2.0 preferably] padding.

An API exactly mirroring the symmetric side won't really work 100%. 
For instance, symmetric operations are not likely to fail [I don't know
how error handling is performed].  Also decrypt/verify ops may fail
hard [due to lack of heap] or soft [invalid packet].

It would probably make more sense to design a simple API for PK crypto
[say support RSA/ECC/DH/DSA ;-)] then to mash the symmetric crypto API
into something compatible.

On a side note I've been contacted about my interest in making this
happen [hence my reply here].  I'm offering my public domain
LibTomCrypt [and indirectly LibTomMath] for the task.  Currently I'm
working on reducing the stack usage in LibTomCrypt's PK operations.

What I propose is we can port LibTomCrypt's [by stripping out stuff
that isn't required like symmetric crypto] PK code to a kernel module
to be released under the GPL.  Since the code is already public domain
[and I personally wrote all of the relevent code myself == no copyright
issues] there shouldn't be any problems with this.

As I said I'm not really a kernel-coder.  Actually just recently I've
moved from 2.4.26 to 2.6.6.  So mostly I'd like to see someone else
head up this task and I'd provide help porting LibTomCrypt.

Tom


		
__________________________________
Do you Yahoo!?
Yahoo! Mail is new and improved - Check it out!
http://promotions.yahoo.com/new_mail

Re: RSA

[Serge E. Hallyn]

> In essence for a digsig module you'll require the ability to 
> 
> 1.  import a PK key [from a binary packet or a cert, preferably the
> former].

Parsing a certificate into precisely the format needed by cryptoapi
will be a task for user-space.  At least that was our plan.  Cryptoapi
can check for validity and return -EINVAL if there's a problem, but
shouldn't have to do any complicated parsing.

> 2.  free a PK key from memory (no need to waste dynamic resources like
> bignums while not being used).
> 3.  ability to sign/verify/encrypt/decrypt which amounts to a exptmod
> and PKCS #1 [v2.0 preferably] padding.

where
	sign = private_encrypt (setkey(privkey); encrypt();)
	verify = public_decrypt (setkey(pubkey); decrypt();)
	encrypt = public_encrypt (setkey(pubkey); encrypt();)
	decrypt = private_decrypt (setkey_privkey(); decrypt();)
so thus far the cipher tfm and algs suffice.

> An API exactly mirroring the symmetric side won't really work 100%. 
> For instance, symmetric operations are not likely to fail [I don't know
> how error handling is performed].  Also decrypt/verify ops may fail
> hard [due to lack of heap] or soft [invalid packet].
>
> It would probably make more sense to design a simple API for PK crypto
> [say support RSA/ECC/DH/DSA ;-)] then to mash the symmetric crypto API
> into something compatible.

Wow.  Death due to a lack of heap was not something I had considered.

So, since the include/linux/crypto.h:cipher_alg struct's encrypt and decrypt
functions return void, we may need to create a assymetric_alg struct whose
functions can return an error.

> What I propose is we can port LibTomCrypt's [by stripping out stuff
> that isn't required like symmetric crypto] PK code to a kernel module
> to be released under the GPL.  Since the code is already public domain
> [and I personally wrote all of the relevent code myself == no copyright
> issues] there shouldn't be any problems with this.
>
> As I said I'm not really a kernel-coder.  Actually just recently I've
> moved from 2.4.26 to 2.6.6.  So mostly I'd like to see someone else
> head up this task and I'd provide help porting LibTomCrypt.

Thanks, Tom.  This is precisely what we were hoping.

thanks,
-serge

Re: RSA

[tom st denis]

--- "Serge E. Hallyn" <serue@us.ibm.com> wrote:
> > In essence for a digsig module you'll require the ability to 
> > 
> > 1.  import a PK key [from a binary packet or a cert, preferably the
> > former].
> 
> Parsing a certificate into precisely the format needed by cryptoapi
> will be a task for user-space.  At least that was our plan. 
> Cryptoapi
> can check for validity and return -EINVAL if there's a problem, but
> shouldn't have to do any complicated parsing.

Sounds reasonable.  Though it would be cooler if the module handled
making/export/import of the key.  Nice and self-contained ;-)

> > 2.  free a PK key from memory (no need to waste dynamic resources
> like
> > bignums while not being used).
> > 3.  ability to sign/verify/encrypt/decrypt which amounts to a
> exptmod
> > and PKCS #1 [v2.0 preferably] padding.
> 
> where
> 	sign = private_encrypt (setkey(privkey); encrypt();)
> 	verify = public_decrypt (setkey(pubkey); decrypt();)
> 	encrypt = public_encrypt (setkey(pubkey); encrypt();)
> 	decrypt = private_decrypt (setkey_privkey(); decrypt();)
> so thus far the cipher tfm and algs suffice.

With the remark that you still have to apply/remove_and_check padding 
to/from the packets.  

> > An API exactly mirroring the symmetric side won't really work 100%.
> 
> > For instance, symmetric operations are not likely to fail [I don't
> know
> > how error handling is performed].  Also decrypt/verify ops may fail
> > hard [due to lack of heap] or soft [invalid packet].
> >
> > It would probably make more sense to design a simple API for PK
> crypto
> > [say support RSA/ECC/DH/DSA ;-)] then to mash the symmetric crypto
> API
> > into something compatible.
> 
> Wow.  Death due to a lack of heap was not something I had considered.
> 
> So, since the include/linux/crypto.h:cipher_alg struct's encrypt and
> decrypt
> functions return void, we may need to create a assymetric_alg struct
> whose
> functions can return an error.

Trust me.  I am most wise in the ways of crypto coding :).

For the most part my LTC [and indirectly LibTomMath] routines are lean
on the heap.  I haven't checked [recently] but I'm sure a RSA-1024
exptmod, for instance, requires around 6K of heap [shouldn't be more
than 8K]. Most of that is taken by the RSA's CRT params and the
exptmod's sliding window.

Definitely not a heavy operation but you have to trap errors obviously.

Tom


		
__________________________________
Do you Yahoo!?
Read only the mail you want - Yahoo! Mail SpamGuard.
http://promotions.yahoo.com/new_mail 

Re: RSA

[Kristian Sørensen]

Hi!

The Umbrella project (umbrella.sf.net) also needs the ability to use
public key cryptography within the Linux kernel (though only to verify
signatures).

We were planing to implement RSA or ElGamal (porting some of GPG) to the
kernel for that purpose. However, if this project gets started, we will
be very interested. In the automn we might also have some development
hours to contribute with :-)

Cheers, KS.

On Tue, 2004-06-15 at 11:44, Joy Latten wrote:
> Is anyone working on implementing RSA encryption/decryption into the
> kernel's cryptoapi? If not, I was considering starting such a project.
> 
> Regards,
> Joy Latten
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
-- 
Kristian Sørensen <ks@cs.auc.dk>