: RSA algorithm patch

From: Tasos Parisinos <[email protected]>

This patch adds module rsa.ko in the kernel (built-in or as a kernel module) and offers an API to do fast modular exponentiation, using the Montgomery algorithm, thus the exponentiation is not generic but can be used only when the modulus is odd, such as RSA public/private key pairs. This module is the
computational core (using multiple precision integer arithmetics) and does not
provide any means to do key management, implement padding schemas e.t.c. so the
calling code should implement all those as needed.

---
This module exports some symbols, through its header file include/crypto/rsa.h and does not use the glue code of include/crypto.h. This decision was taken because this glue code is not really suitable for asymmetric cryptography in my
opinion. First of all RSA is not a block cipher but a stream cipher. It does not
only have a key but also an exponent that are two different entities. And the most
important is that the key size can be of any length. So it is not practical -yet- to register the algorithm with the crypto api using a struct such as crypto_alg. So another module can include the file include/crypto/rsa.h and call its interface functions to create the operands for the modular exponentiation, execute the exponentiation and use the results. All these functions and structures are well documented kernel-doc style. Also in this way the calling in-kernel code can implement key management, padding schemas, hashing e.t.c as needed.

diff -uprN -X linux/Documentation/dontdiff \
linux.orig/crypto/Kconfig linux/crypto/Kconfig

@@ -440,6 +440,31 @@ config CRYPTO_CAMELLIA

See also:
<https://info.isl.ntt.co.jp/crypt/eng/camellia/index_s.html>

+config CRYPTO_RSA
+ tristate "RSA asymmetric cipher algorithm"
+ help
+ RSA asymmetric cipher algorithm.
+

+	  This module uses the montgomery algorithm to compute fast modular
+	  exponentiation. All operands of the modular exponentiation can be
+	  of any bit length, thus you can use any public and/or private key
+	  lengths.

+
+ If it is selected it will add approximately 8K to the kernel size.
+ Select M to build this as a module. The module will be called rsa.
+
+config RSA_AUX_OPERAND_SIZE
+ int "Size of the preallocated auxilliary operands"
+ default "128"
+ depends on CRYPTO_RSA
+ help

+	  The rsa module needs some preallocated space to avoid computation-time
+	  allocations. The 'rsa_op' is the struct used by the rsa module to hold
+	  a multi-precision integer operand. This struct maps such an integer on
+	  multiple 32bit limbs. Here you select the size (in 32bit limbs) of the
+	  preallocated auxilliary operands. This size should be close to the key
+	  sizes that are usually used.

+
config CRYPTO_TEST
tristate "Testing module"
depends on m
diff -uprN -X linux/Documentation/dontdiff \
linux.orig/crypto/Makefile linux/crypto/Makefile

@@ -46,5 +46,6 @@ obj-$(CONFIG_CRYPTO_ANUBIS) += anubis.o

obj-$(CONFIG_CRYPTO_DEFLATE) += deflate.o
obj-$(CONFIG_CRYPTO_MICHAEL_MIC) += michael_mic.o
obj-$(CONFIG_CRYPTO_CRC32C) += crc32c.o
+obj-$(CONFIG_CRYPTO_RSA) += rsa.o

obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o
diff -uprN -X linux/Documentation/dontdiff \
linux.orig/crypto/rsa.c linux/crypto/rsa.c

diff -uprN -X linux/Documentation/dontdiff \
linux.orig/include/crypto/rsa.h linux/include/crypto/rsa.h

@@ -0,0 +1,33 @@
+#ifndef _CRYPTO_RSA_H
+#define _CRYPTO_RSA_H
+
+/*
+ * struct rsa_op: multi-precision integer operand
+ * @data: array that holds the number absolute value
+ * @sign: 1 for negative, 0 for positive
+ * @size: significant number limbs
+ * @limbs: allocated limbs (sizeof data)
+ */
+struct rsa_op {
+	u32 *data;
+	int sign;
+	int size;
+	int limbs;
+};
+
+int	rsa_op_alloc(struct rsa_op **, int);
+
+void	rsa_op_free(struct rsa_op *);
+
+int 	rsa_op_init(struct rsa_op **, u8 *, u32, u32);
+
+int 	rsa_op_set(struct rsa_op **, u8 *, u32);
+
+int	rsa_op_copy(struct rsa_op **, struct rsa_op *);
+
+void	rsa_op_print(struct rsa_op *, bool);
+
+int 	rsa_cipher(struct rsa_op **, struct rsa_op *, struct rsa_op *,
+		   struct rsa_op *);
+
+#endif

You forgot to answer the most important question.

What would want to use RSA in the kernel and why?

-Andi

The main purpose behind the creation of this module was to create the cryptographic infrastructure to develop an in-kernel system of signed modules.

The best environment to deploy such functionality is in updating by remote, executable code (programs, libs and modules) on embedded devices running Linux, that have some form of kernel physical security, so one can't tamper the kernel, but can read it. In this case only a public key would be revealed. The vendor of the devices can sign and distribute/update executable code to the devices, and the kernel will not load/run any of them if they don't match with their signatures. The signature can be embedded in the elf, so this system is portable and centralized. Although this functionality can be achieved using userland helper programs this may create the need to physically secure entire filesystems which adds to the cost of developing such devices. In such cases one needs to use asymmetric cryptography because in the case of symmetric it would be very easy to give away the key and end with having all your devices being attacked.

There are already some systems that implement and utilize such functionality that use windows platforms, and other Linux distros that use userland programs to do so, assuming physical security of the host computer.

Moreover a same system that would use hashes is easier to brake and more difficult to update each time new code must be loaded to the host devices.

See also this thread

http://lkml.org/lkml/2007/3/19/447

So how do you plan to close the various interfaces that allow access to kernel memory?

I would suggest to discuss the high level design first before submitting code.

How would that physical security look like? Would it include DMA protection?

For example to do any useful form of graphics you need user controllable DMA, which can normally touch everything. There are various other similar "backdoors" for root.

I'm somewhat sceptical because all kernels will need access to the direct mapping to operate and there are also various interfaces that can be as root (ab)used to change it.

And when you can do that they can change function pointers and jump to arbitary code or change the kernel page tables and map arbitary code.

Disallowing all this would probably end up with a quite useless kernel.

Yes, at least the Vista variant was just broken. And its designers spent a lot of effort on it, but it didn't help.

-Andi

Please read the thread i gave you for some details for things you ask

Have in thought that we mostly talk here about embedded devices that run Linux in a very restricted environment where only specific applications are allowed to exist and run, there are no user logons and these applications need to be updated by remote once in a while over public networks. These applications need not be tampered with and must not be executed if they are, by someone that has hijacked the connection by any means. Such devices can have some tamper responsive hardware where the kernel (only) is protected in case someone tries to tamper one of these devices by hand (not over the network). You also need to have a centralized way of updating but a de-centralized way of key usage so that if a person tampers with one of these devices does not gain information that can be used to attack the other devices over the network (like what would happened if you used symmetric cryptography).

This is not a PC-security feature at all. Though it can be used in favour off other tricks like trip-wire and digsig and others). Of course such functionality could be easily by-passed in that case by someone root privileged with a good understanding of the system internals.

As for Vista, no comments.... :)

Best regards
Tasos Parisinos
-

I don't see much useful information in the thread. It's the same high level handwaving from you there as in this.

Ok so they don't X servers? But did you audit all the ioctls of all their drivers that they don't allow memory access? And plugged the other interfaces like io port access etc.?

And besides where is this code for review? There's a pretty firm policy to not integrate any code without users because that guarantees bitrot.

-Andi

Hi!

What kind of applications are we talking about here? I'd like to hack hardware I own.

Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

payment systems, EMV terminals, mobile phone applications

Tasos Parisinos
-

Hi!

I'd like to hack my cell phone, thank you. (Plus, cellphones do not contain physical security).
Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

I don't really see why this has to be in the kernel, even after reading your text below. This would be code which a tiny number of users would find useful, someone in the future might find exploitable, to perform a function which can be done in user space.

So to save cost on your end you want to make this feature part of the mainline kernel. Am I misreading your intent here?

Which make a good argument for doing asymmetric anyway, it would seem. That way any updates can be checked off the target machine and validated as authentic.

Exactly.

Having said all this, we have a boatload of other crypto in the kernel, if it's just the crypto module, like aes, anubis or micheal_mic, and is GPL compatible, some people may agree. But if this is an embedded system, and you have the patch, why not just apply it to your kernel and forget mainline?

Bill Davidsen <[email protected]>
  "We have more to fear from the bungling of the incompetent than from
the machinations of the wicked."  - from Slashdot

(Tasos was talking about the cost of securing whole file systems versus only the kernel binary.)

But if that "entire filesystem" is initramfs, I don't
see any problem. If it fits into the kernel, it also has enough room for an initramfs with a user space program with the RSA signing. I said this before, so please look up how initramfs works and tell us why that isn't sufficient for this case.

I suspect your answer will be because it isn't the only part and a lot other infrastructure is need in the kernel to do all the binary signing. But that code you didn't post, only a MPI module, however nice, which is only a partial solution to what you want to achieve. Combine that with the kernel policy to not merge unused code, and you're in the current situation.

Currently it's less than a cryptoapi module, as it only provide some functions to do multi-precision integer calculations, which happen to be the tricky part of implementing RSA.

That said, this implementation seems quite good, from a code size and complexity point of view. So for that alone I think it wouldn't be bad to merge this or a modified version of this, even if it's unused by the rest of the kernel, it might be useful for other users. The burden to carry it along for the kernel is quite small, while the code is worth something and might get improved by their users, in the end having a central place to collect them. So I think from an open source ecological point of view, it wouldn't be bad to merge it.

I see three possible way forwards (alternative is the status quo):

1) Move it to user space (into the initramfs embedded into the kernel). But you'd still need to add binary (modules, libs and programs) load hooks.

2) Flesh it out into a ready to use, full blown RSA cryptoAPI module. Whatever you said earlier, whether you want or not, it's just a block cipher, with the modulo as block size (I suspect there's some room for code simplification when assuming fixed block sizes too, by allocating blocksize * 2 space instead of resizing when needed).

3) Go all the way, and post all the other kernel modifications too, to get the whole binary signing you want to achieve.
Advantage will be that in the end you'll end up with something scrutinized to death. Disadvantage is that it will be scrutinized to death, as that can take a lot of time. Maybe you'll end up with a new LSM module, who knows?

The list is in increasing order of difficulty and quality of your end code.

It would help if you could find others who also wants something similar and work together to get it into the kernel. But even if the last step fails, you still have had people reviewing your code. And failing even that, you at least shared your code with the rest of the world, which is already something good (and required by the GPL. But doing it in the open is much more laudable than hiding it on a website).

Greetings,

Indan

This would probably be the best solution, to provide most of the hooks while presenting the cryptoAPI for others to use if they wish. Good suggestion.

I think you have covered the possibilities, my read is that your item number two is most likely to be accepted.

Bill Davidsen <[email protected]>
 "We have more to fear from the bungling of the incompetent than from
the machinations of the wicked."  - from Slashdot

Hello to everybody

-----

Firstly i want to thank everybody for reviewing this code and posting all your usefull comments

-----

Secondly i would like to give a generic (as possible) example of use of this module. More and more nowadays Linux has started to be ported and running in a wide variety of devices that are mostly described by the word embedded, from mobile phones and smart phones to gadgets and multimedia players and from routers to payment, identification, access and security systems. There is also the big arena of industrial digital equipment as plc, motion controllers e.t.c. These devices were running till now some other on-chip and in many cases proprietary operating systems. The processors and the resources used where a lot less than a full fledged OS needs to run on. Exception to all these devices where some pda's. But now the processors used in embedded devices have evolved a lot and while hardware is getting faster and cheaper the cost of creating and maintaining the os has grown to a point where more and more designers need to use either Linux or some OS of the windows family (CE, XP embedded, mobile). The time is close where you are going to have the resources on-chip to download and run a kernel from within a chip. As anyone can understand these devices are not like servers, for example, hidden away in some well protected computer room, with dedicated administrators and they can't be compared at all with workstations and personal computers where noone usually spents time to intrude, unless to practice his hobby. Most if not all of the designers and vendors of such digital devices will very soon need to have a way of centrally and transparently updating the software and personalization data in such devices in a secure way over public networks.

If you are a vendor of a smart phone, a router, or worst, a point of sale terminal you care about three things. The first is that the end user can't open the device to probe it or alter it in a way that would create fraud. For example a salesman could alter a credit card reader to see all cards as genuine and do offline transactions. The second is that you dont want any eavesdropper hijacking connectionsto such devices and replacing your updates with his in a way that could create fraud. In that case the problem could be severe because you don't have a user's device altered but possibly hundrends of them. And the third thing is to do the first two as cheap as you can because in the embedded world, as one can understand competition is tough.

The first need is solved generally by embedding hot data in security access modules and hot software on chips or cryptomemories bla bla. Security can range from tamper resistance to tamper rensonsiveness in means of such casings that could detect any kind of intrusion attempt and erase all critical stuff, rendering a device useless. For an example think of a processor that has all its critical software and data inside it, on volatile memories. When this chip is not powered it uses an internal (or external) battery to keep these data alive. This chip can have sensors of heat, humidity, oscillator frequency imbalancies, short circuits, currents going in and out of its pins, even light, and be configured and programmed in a way to erase all critical data and software when some of the above variables goes out of envelope.

The second need is solved by authentication and encryption. The system of authentication must be asymmetric because if it is symmetric and the first need is not well implemented then you may get really exposed. Of course you have to secure first the software that does this authentication on the device.

We at Sciensis are designing embedded systems and we had the need to create such
a system for authentication. We have built it into the Linux kernel because this
is neat, simple and costs less to implement. As Indan said, in generic, its more
difficult to secure entire filesystems and this gets even more difficult when
you have your filesystem on removable media such as mmc or sd-cards. So we
thought, hell why not give it to others as well so we GPL'd it. It was first developed on an AVR32 so it is put for review on www.avr32linux.org (to be honest it was published there rather late) and also given to you to review as well
because all flavours of embedded Linux whether they are run on ARM or AVR or PPC
BLACKFIN etc are all derived from the mainline, so having it as portable code in the
mainline you make it accessible to all these fellows wanting to use it in the
embedded world. Well it will be quite useless for your PC so dont select it when
you compile your kernel. Yes this thing does not have other in-kernel users yet
but i always wondered who uses khazad cipher algorithm, lol. (ok i suppose all
these symmetric cryptographic and digest options are all for IPSec, but khazad
(?!), come on guys). I understand codebloat, firm policies, bitrot e.t.c but how
can a thing be published and used if it is not brought out to the light?

-----
Thirdly some technical stuff that Indan brought up

1. Indan you have commented on an earlier patch that the multiplication algorithm can be optimized a lot. Please post anything you have in mind because that code is executed a lot.

2. Making it a full blown Crypto API is possible, because RSA can be seen as a
block cipher and you can hard code and compile the fixed size of the modulus and
thus simplify code as well, but this will make it less generic and cumbersome in
runtime (except if we add some kernel boot parameters). But there is a problem
with exponents... how would you pass them around using the current Crypto API
structs? Would it be wiser to take this module out of Cryptocraphic Options menu and put it in the Library routines menu?

3. We decided not to GPL other parts of the binary signing mechanism because this are covered by some NDAs. So i must leave that to others to develop, or come back with a very-very different version of these parts and this will take time.

I think it is worth to try to make a version which will use the crypto api glue code and re-post...

Best regards
Tasos Parisinos
-

Hi,

I'd hope that for a smart phone and a router the owner can install whatever he wants (that is, he has the private key). As for the card reader, I'd hope that using a modified card reader isn't enough for fraud to succeed, or else the whole thing is designed stupid. That said, the credit card system seems insecure anyway, with readers being able to steal useful information.

These are real problems.

Read: http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-630.pdf

There are other similar papers. The conclusion is that if someone really wants it, he will get it from your device. Not sure if it was this paper or another one, but volatile memory can be read out after the power went off. It's even possible to retrieve overwritten data if it wasn't done very carefully, both RAM and flash.

If the tampering is done for a very short time, the detectors will probably miss it. Or the tampering is done with the one thing the device wasn't protected against. Or they think up some new way to bypass the protections.

Anyway, the question is what you're trying to protect. In general it's to keep the code hidden, because there are plenty of obscure companies that steal that expensive code and use it for their products. But it can also be a private key or something.

True. (Though asymmetric doesn't mean it has to be RSA. ;-)

Yes. But with that comes the obligation to publish your code under the GPL to your customers, keep that in mind.

Only true if that filesystem isn't initramfs embedded in the kernel library! Then it gets the same protection as the kernel for free.

You did? We only saw a MPI implementation, nothing more. All the above mentioned arguments and reasoning only applies to a complete implementation, not to an incomplete partial solution, which on its own is useless. Don't mix up the binary signing thing with a nice stand alone RSA crypto module.

That said, it was nice to share the RSA code, no matter what.

I fully agree with this, but only for a RSA crypto API module.

I've no time right now, but I'll look it up when you've posted the crypto API version.

As far as the memory management, I didn't mean to hardcode the size of the modulus, but to have a hard coded limit (e.g. 4096 bits). The modulus can vary, as long as it's less than the limit. As for the block size, it depends on what scheme you use. In general the block size isn't exactly equal to the modulus, but smaller, and the message is padded in some way. It depends on how you sign the binary hash. So maybe it's best to move that decision to the user of the RSA module, and indeed use the modulus as block size, in which case it would be variable and depend on the key used. No idea how well the current crypto API copes with that, it might be a problem.

I don't know, I didn't look into the details yet. But I assume that at worst you use a struct as key, and pass that transparently through the crypto API part. But maybe there are better ways. Can try it out and use what seems best I suppose.

Well, you don't have much choice in the matter when using GPL software, I'm afraid. You don't have to release it to everyone, only to your customers, but they're free it give to anyone else they want. If that's not possible because of some NDA, then you may not distribute the GPL code. The whole point of using GPL is that if someone modifies the code, he's required to give back the modifications.

And squeezing out of this isn't possible in your situation as you don't have a separate binary module, but have modified kernel code and are distributing the whole.

But I don't see why you're so mysterious about the rest anyway, because it looks rather trivial to implement such binary signature checking thing. If it isn't trivial, then small chance it's secure...

At least I won't ever buy "secure" hardware from any vendor who's mysterious about the implemented protections. Because time after time it was proven that no matter how obscure the protection is done, it's always bypassed if it couldn't stand on its own. (Example: The GSM encryption used. Both reverse engineered and broken.)

Yes, certainly, independently from the rest of the implementation, which you might need to move to userspace if you're really coy about it. (Though if it's only because of the stupid NDA, then I'd consider replacing the NDA part with something of your own. NDA's imply money drain.)

Greetings,

Indan

Well with old credit cards (magnetic) it was possible (as a matter of fact it was trivial) With new chip cards its a lot harder but still possible, only the risk is smaller in means that the fraud will be very limited.

I didn't have time to read the pdf but i will. As for erasing ram it usually means to also scramble it and there are chips that advertise that can do this in 1 cycle. Well reaching the bus or ram to probe it is another thing. Most die in such chip are also hidden under protective meshes so it takes some time. What you said is true, systems are created and broken, the question is what you have to hide and whether the person that wants to break it has the money the will the knowledge and the equipment to do it. Because if he is to spend a million euro only to create fraud of half a million euro then he wont do it. That has to do with risk management.

Sure, but its just more standardized and widely used

I understand and i agree, thing is that i dont decide about which parts are given GPL.
While the RSA module is given standalone, it can be still used by others to develop
their own signing and authenticating mechanisms. For example some will decide to do hashing of code with md5 while others with sha1 and some will do padding compliant with pkcs1 other will implement other schemas e.t.c. I want to say although this is not
really ready to be used for binary signing, it has the advantage to provide basic functionality
and freedom to other developers to implement their own schemas.

people think that by hiding implementations (which can be reverse engineered of course) will make it more difficult to break. Well i agree with you but... its not in my hands. So i will come back with these parts replaced with some of my own

And a question
Can someone provide me with a full list of kernel functions where code is loaded?

Best regards Tasos Parisinos

Hello,

Firstly, I'd like to steer clear of all the RSA-in-kernel-or-userspace / MPI-in-kernel-or-userspace arguments. True, MPI / RSA / (PKI? that even requires some knowledge of ASN.1 etc to parse certificates) do add a lot of bloat to the kernel. That said, I don't see any other reason to _not_ do asymmetric crypto in the kernel either. In some situations, that in fact simplifies the overall system by avoiding the use of additional userspace components / daemons to do the key management stuff.

I do have some comments on the submitted patch, though:

1. First, sorry, I don't think an RSA implementation not conforming to PKCS #1 qualifies to be called RSA at all. That is definitely a *must* -- why break strong crypto algorithms such as RSA by implementing them in insecure ways? It shouldn't be too difficult for you to add, and you _can_ still allow the user to choose the appropriate padding scheme by taking it as an argument to the encrypt / decrypt API functions (some possibilities I can think of are PKCS#1 v1.5 padding, v2.0 i.e. OAEP padding, or null padding).

2. Of course, you can forget about what digest was used to compute the plaintext input to RSA. We don't really care, as RSA should never be used to operate on multiple blocks anyway and no real-world hybrid cryptosystem uses it in such a way either. (RSA could be thought of as a block cipher of block size == modulus size)

3. Please, try to re-use the MPI library from GnuPG that has already been ported to the kernel -- not the mainline tree, but most distributions such as Red Hat, Fedora, Debian, Suse(?) have maintained an MPI library in crypto/ for the modsign stuff for years now -- that would make your entire RSA module merely a set of wrappers (implementing PKCS#1) to the core modular exponentiation functions in that MPI library. It also contains implementations of optimized algorithms for a lot of the mathematics involved, so you have only to benefit from utilizing a library that has been used, maintained and tested for years.

4. Anything in crypto/ belongs to the CryptoAPI. You definitely need to integrate with it.

Because it can all be done in userspace? Can trap all binary loading from user-space too, though that must be done carefully, without changing the kernel.

It's still RSA, that it's not enough to get a complete and secure crypto system doesn't mean it isn't RSA anymore. Maybe you're right and having RSA without the rest makes no sense. But things like padding schemes change, the core RSA algorithm does't, so I think when adding anything that's unused by the rest of the kernel it has more chance if it's a low maintenance bare RSA implementation.

Right, and that MPI implementation isn't merged. Perhaps a smaller, simpler, not complexified by optimisations version has more chance. RSA is damn slow anyway, so better to concentrate on other things than speed, IMHO.

That said, perhaps the different groups could concentrate on one implementation they all agree on? That's the main advantage of having it mainline, that there's a common place to cencentrate all effort into.

But keep in mind that it's a precaurious balance, at least that's how I see it. Right now it's about a rather static 800 lines of code which implements some common algorithms. Not much bloat, low maintenance, over all not much reason to not merge it, except that it isn't used by the rest of the kernel.

If you're going to add the full kitchen sink, it might not look that appealing anymore, and merging it will become much harder, especially as no one provided good arguments why it can't be done in user space.

Perhaps, with that in mind, it's better to not merge the bare RSA version either, as it might give false hope for more, because it looks like most implementations should be done in user space (either because that's better anyway, or because of legal reasons).

Greetings,

Indan

Before merging anything there would need to be clear applications (with patches, discussions etc.)

In general code with no users is not merged because it will just bitrot.

-Andi

Aarghh ... just the argument I wanted to steer clear of, isn't this? Continuing, however, we _can_ do a lot of things in userspace, but still might choose to do them in the kernel, for various reasons in each case (performance, convenience, application transparency etc etc). So many things come to mind -- filesystems, readahead, the cryptoapi itself -- some less controversial, and some more so.

Of course, once an infrastructure is indeed merged into the kernel, it better already have (or quickly develop) some users for itself. If it doesn't, it does end up as rot. If it does, that pretty much solves the maintenance problem there itself.

Getting specific to *this* particular case, I _can_ think of other users in the kernel that could gladly use general asymmetric crypto capabilities added to the cryptoapi -- encrypting file systems, module signing (as of now they've just implemented DSA directly for themselves, not through the cryptoapi) to name a few.

Well, then *all* the users of the RSA cryptoapi code would end up duplicating the PKCS padding for themselves! (because if we don't care about padding in a "low-maintenance-bare-RSA-implementation", then we might as well not implement any RSA crypto at all :-) Also, padding schemes are careful cryptographic constructions -- much like ciphers themselves. Much thought has gone into PKCS#1 over the years (and it's later revisions). We wouldn't want users to re-invent some kind of insecure padding for themselves.

The way I think about this is: (1) RSA without PKCS#1 makes no sense, and (2) PKCS#1 is *defined* only for RSA. Combine (1) and (2), and it makes *all* sense to encapsulate the two in just one module.

Coming to padding standards, RSA has been around for ~20 years now, and only 3 PKCS#1 padding schemes were ever defined (at least AFAICR). That's not something that changes so frequently as to not implement it in the core RSA code itself, especially when the penalties of not doing so could be quite embarrassing indeed.

If RSA is slow, then optimizing it to make it fast (and thus have more impact on relative performance) should make *more* sense, shouldn't it? That MPI implementation is derived from GPG, which has been around for a decade now. I'd much rather prefer well-known and well-understood code that has been used, tested and maintained for a decade than some recent/unused contraption, thank you.

Hmmm ... and again I'll excuse myself from the debate whether to *actually* merge MPI and asymmetric crypto capabilities into the mainline tree or not -- it's all about whether the potential users named earlier really want to be able to do all that stuff in-kernel or wouldn't mind writing userspace components for it.

Cheers,
S

Yes, but currently those users are more or less hidden and working independently.

The potential for users is the bare minimum expected, next step is that there are any and them agreeing on common implementations.

Very good points there, you're right.

I prefer clear, simple code that is easily audited to be correct or at least not cause problems, which is small enough to not add much bloat. I don't care about "very slow" or merely "slow" code. RSA/DSA isn't used as a symmetric block cipher, where it does make sense to optimize it to death.

judged by its quality, not by its heritage.

I know you didn't want to talk about the user versus kernel space question, but I think it's a very important and interesting one. As you said, GPG is there around for years and tested, why making a new implementation in the kernel? Your argument holds for the whole as much as for parts of the infrastructure.

And whether they can agree on a common implementation. If they all just want to do their own thing, and not combine resources, then it doesn't make any sense to merge anything at all, as it would be ignored anyway.

As for the userspace issue, I get the impression that they didn't consider it very well, ignoring things like initramfs versus main filesystem and so on. It's also a gradual thing, some things can be done best in the kernel, and others in user space. Another alternative is to push it up into the boot loader. ;-)

Greetings,

Indan

Hi Indan,

Agreed, the GPG MPI library *is* significantly larger -- I'm looking at the Fedora 4 kernel source here and their crypto/mpi/ comes to about 5000 lines (not including comments). But there are reasons for this -- they export far too many MPI operations. I suspect they just ported the *entire* GNU MP lib.

For example, there's crypto/mpi/longlong.h, worth 1500 lines of ugliness in itself. I see arch-specific assembly there for processors that Linux doesn't even support. Wow.

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.

Also, DSA signature generation and verification (which is what the modsign guys use) doesn't exactly utilize the same MPI operations as RSA does. If we really don't care about speed and DSA, we could strip that library down to the basic and RSA-only operations Tasos' code provides, and I'm quite sure we'd end up somewhere close to 1000 lines there too.

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.

[...]

Yes, that "common implementation" bit is definitely crucial, which is why merging a solid, feature-rich and fast MPI library could become all the more important, in my opinion.

Very true, it does make sense to explore userspace possibilities first.

Cheers,
S

Hello,

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).

Doing MPI well is already tricky. Doing it in such way that most side-channel attacks don't work is challenging, and brings already code bloat and complexity with it. Doing all the previous with compact and simple code is hard. Speed is the last thing I'm worried about.

I'd rather start with good and simple code, and speed it up without adding too much complexity gradually, case by case.
(Though I'm not the one with any interests here, so my opinion isn't worth much.)

That's nice. But then you lose more or less all advantages of using an existing implementation, don't you? Anyway, how much different would that code be from Tasos'?

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?

You want feature-rich and fast, I prefer dense, clean and spartan, what would others prefer? Perhaps deciding on a common implementation is harder than it looks.

Greetings,

Indan

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.

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

Noise can be filtered out, and combined attacks can give enough information. (E.g. throw in power usage or other measurements.) There are ways to add noise to the timing, but still using those optimisations. The point was that they add extra code and complexity.

(Personally I think RSA-like asymmetric encryption has so many, often subtle problems, with complex, hard to get secure implementations, that it's something I'd avoid using as much as possible. Unfortunately there's not much alternative.)

That's because for side-channel attacks you need physical access to the hardware, something for most machines means security is breached anyway. But when this code is going to be used to sign things by embedded devices (with a local, secret key), it can be important.

For checking signatures the key is known and all this doesn't matter, but we're talking about a common implementation. It are things to keep in mind.

We won't know until those users show themselves. Until then, we can only speculate. Right now there is only user, with another one lurking in the background.

Greetings,

Indan

But timing attacks are not exclusive to RSA / asymmetric cryptosystems. Such (side channel / timing / power measurement / bus access) attacks are possible against AES, etc too.

Of course, now we're really moving into a different realm -- I guess in security there is always a threshold, and you really needn't care beyond a particular threat perception level. I don't see how even the existing cryptoapi (or *any* security measure in the kernel for that matter) stands up to the kind of attacks we're talking about now.

I think the original idea was to generate signatures at a centralized place (not on an embedded system) and only *verify* them using *public* keys on the embedded systems? For most common implementations, as I suggested, you only need bother yourself upto a certain security threshold.

True, but those are often easier to protect, or are less vulnerable in the first place. (E.g. it isn't very hard to make a constant time AES implementation. The operations it does are independent of the key.)

True, and very specialized hardware is needed in such cases anyway, so arguing that it's not the kernel's task to protect against such attacks is valid. But it are interesting attacks, and people should be aware of them, instead of blindly trusting any security measure (not implying anyone here does, I mean in general).

Yes, but it depends on how the code is used. It is supposed to be generic code, so whether someone wants to use it for signing or not is an open question. So far it seems only signature checking is needed, and that simplifies a lot, but if that isn't the case more questions pop up, like where the security threshold should be.

The user with the tightest requirements more or less dictates the implementation.

All in all, to get anything merged at all in the kernel it seems at least the following needs to happen:

- Future users speaking up and uniting.

- Figuring out their needs (so overlapping needs can make it into common code, and other decisions can be made, as where the kernel and user space border should be.)

- Deciding on a commonly agreed security threshold, and making that explicit.

- Coding it all up and keeping it in sync with mainline.

I don't see this happening soon. But a good start would be if someone who cares about this sets up a mailing list or website to collect all users and information.

Good night,

Indan

Yes, Satyam Sharma is 100% correct. Unpadded RSA makes no sense. RSA is not secure if you omit the padding. If you have a good reason why RSA needs to be in the kernel for security reasons, then the padding has to be in the kernel, too. Putting plain unpadded RSA in the kernel seems bogus.

I worry about the quality of this patch if it is using unpadded RSA. This is pretty elementary stuff. No one should be implementing their own crypto code unless they have considerable competence and knowledge of cryptography. This elementary error leaves reason to be concerned about whether the developer of this patch has the skills that are needed to write this kind of code and get it right.

People often take it personally when I tell them that they do are not competent to write their own crypto code, but this is not a personal attack. It takes very specialized knowledge and considerable study before one can write your own crypto implementation from scratch and have a good chance that the result will be secure. People without those skills shouldn't be writing their own crypto code, at least not if security is important, because it's too easy to get something wrong. (No, just reading Applied Cryptography is not good enough.) My experience is that code that contains elementary errors like this is also likely to contain more subtle errors that are harder to spot. In short, I'm not getting warm fuzzies here.

And no, you can't just blithely push padding into user space and expect that to make the security issues go away. If you are putting the RSA exponentiation in the kernel because you don't trust user space, then you have to put the padding in the kernel, too, otherwise you're vulnerable to attack from evil user space code.

It is also not true that padding schemes change all the time. They're fairly stable. Pick a reasonable modern padding scheme and leave it.

Hello,

Next time, please do a reply-all so CC's aren't dropped.

It seems you jumped halfway in, missing some background info, I'll try to clarify some things.

He is correct, I only argued that's it can still be named RSA (which Satyam disputed), no matter what critical features are missing for a complete infrastructure.

I don't know if you read the patch, but right now it's only a multi-precision integer implementation, useful to implement RSA. The rest, including the binary checking, is missing. We're pondering a bit about what, in the end, would be useful to have in or around the kernel.

As said above, the patch is only an MPI implementation, not RSA, and neither the rest to make it useful, like a crypto API interface and padding.

So we can't really judge the developer's skills or crypto knowledge.

It does point out that having a hidden implementation can never foster much trust, as no one can read the code and judge if it's good or not.

To a certain degree you're right, but the nice thing about open source is that people who know better can spot errors, and if those are fixed, it can happen that an "incompetent" person created something excellent. Maybe not at first, but in the end. (I suspect that a good coder with no crypto knowledge, but with feedback from experts, can implement something better than one expert with mediocre coding skills.)

The code should be judged, not the people writing it. Besides, it isn't always that hard to get something secure, if things are kept simple and straightforward. E.g. writing a secure AES implementation isn't magic. RSA is much more complex though. (Rather ironic, as the theory behind RSA is simple, but the implementation hairy. With AES it's exactly the opposite. The coder doesn't need to understand the algebra behind it, knowing that it can be done with a simple table lookup is enough).

In general the tricky part is around the crypto implementation itself, how it's used, key management, etc. (Though the border is vague, so maybe you included all that when saying "crypto implementation".)

The code posted has no such errors, see above. Maybe the part that wasn't has, who knows.

True, but the code wasn't put into the kernel for security reasons. Why it was remains a bit of a mystery, but it looks like it was for convenience.

Greetings,

Indan

Hello again

As i formerly stated there was some 'management' mixup (and don't want to believe that it had to do with
my code and crypto competence :), anyway no offence about that, really) about what to submit and what not. Now things are getting a lot clearer and i think that we will be able to submit all the patches in order to have:

The rsa module patch as is now with the following additions

1. Padding as PKCS#1 specificates
2. Crypto API glue code

And another patch that will be the code authenticating mechanism.

These two will be a complete binary authenticating mechanism to be used in embedded Linux much the way it was described on a previous post of mine.

The above will take some time as they will be reworked significantly based on the experience gathered through this discussion

If this code organization is done, should this go in crypto as rsa module + binary signing module
or should be made as one unique module for code authentication (hiding the rsa implementation inside it) and putting it somewhere else (not in crypto)?

-----

Sharma really made a point about excluding padding from this module and leaving it to userspace or other in-kernel code. It should be added in the module, as it is the only to be used anyway be everyone. Also Indan is right, this module was supposed to be a simple mpi implementation to do modexp using the montgomery algorithm to be used for binary authentication, but if it is to turn it into real RSA it should have padding and crypto API glue code.

-----

Indan has said:
I don't see this happening soon. But a good start would be if someone who cares about this sets up a mailing list or website to collect all users and information.

I think that this is a nice idea, so i will try setup such a spot to be able to discuss and share code.

-----

I created this code taking Indan's way of looking at things. Not porting something like the whole gmp but just re-implementing only the needed mpi code. This as a result can be a clear and robust and really easy to audit, basis for future implementations and addons. The drawback is that it does not provide generic mpi functions to be used in other places as well. The question is:

If a full mpi kernel lib would be big and complex and randomly used then it is better to have distinct little modules, implementing their own needed mpi functionality, isn't that so?

When there will be lots of them modules depending heavily on mpi calculations then those could be reworked to reach that point and in that case you would have less complexity and code size.

-------

There was also big discussion about implementing CRT to do modexp with the private key.
In my view although this could be implemented in the RSA module in order for it to be generic
it is susceptible to timing and other attacks and i would personally would not use it neither i would
keep such keys on a plain filesystem on an embedded device on the market. That is why there is
only the implementation of the montgomery exponentiation in my patch to be used with public keys
and exponents to authenticate code on embedded devices as described in detail in a previous message. Excluding the use of private keys and CRT also makes code a lot simpler. I tell you again this module is not created for PC security. It is created to address a specific need on embedded devices. Whether
it will be used by a PC user to cipher/decipher data on his disk is ok with me but really in that case there
is no added security anyway.

The question there is:

Create a generic and complex RSA module to be used by anyone even on PCs (where it could be done easily (and much with the same safety) on userland) or create a cut-down and specific authenticating mechanism (using RSA) to authenticate code, that would be able to be used by all Linux embedded users at first (and for naive and unsafe usage in PC world)?

Bye for now
Tasos Parisinos
-

Those can be peeled off. But the paper I linked to concentrates on other kinds of attacks.

Quote:

"One of the main contributions of this thesis is fault injection attacks done in a semi-invasive manner which can be used to modify the contents of SRAM and change the state of any individual transistor inside the chip. That gives almost unlimited capabilities to the attacker in getting control over the chip operation and abusing the protection mechanism. Compared to non-invasive attacks, semi-invasive attacks are harder to implement as they require decapsulation of the chip. However, very much less expensive equipment is needed than for invasive attacks. These attacks can be performed in a reasonably short period of time. Also they are scalable to a certain extent, and the skills and knowledge required to perform them can be easily and quickly acquired. Some of these attacks, such as an exhaustive search for a"

It gives a good overview of all kind of other attacks and defences too. Personally I find the non-invasive attacks the most interesting. (The pdf is 12 MB, for the low bandwidthers.)

Very true, and the right way to look at it. (Vendors should say "it costs about $X to break this chip", instead of saying that it's secure, and then not giving guarantees.)

No, the kernel licence and others do. But you can't edit the kernel and distribute it without releasing those modifications under the GPL.

What else is there except the signing and binary loading hooks? Perhaps some caching, but not much more, is there? I'm a bit baffled about what's kept hidden here, as there doesn't seem much to hide, except perhaps other, independent "protections", but we weren't talking about those.

I don't know anything about your company, but I bet the marketing people are more in favour to keeping it hidden than the security people. I'd ask the legal people for the kernel parts though.

Counter questions:

- Why should we give that list if you're not going to release the code you're going to write? Or in other words, why should we help you?
(But if you're going to open it up, try to find people interested in the same functionality so you can work together on it. Not me, I'm just a passer-by.)

- That you ask for that list implies that you're not going to audit the whole kernel source for such functions. That might imply, to some, that your security code isn't as secure as it should be. People make mistakes, forget things, so on. Both you and people providing a list. And such mistakes are easiest spotted when more people look at the code. But that's not possible when the code is hidden. Then only the ones with malicious intents keep looking. So perhaps it's harder to spot deficiencies in closed source protection code, but it will probably have more of it too. Your choice, you take the risk.

Greetings,

Indan