RSA public key

[niox]

Hey people
Im new here and thrilled to be here. I've been programming assembly for a year or so, mostly small projects. And now im doing yet another little project.

Since my latest project is a small PE that needs to communicate small chunks of data securely to my server, my solution is to base the encryption on the RSA public key algo (no way around using a public/private key algo).

Since my server will hold the pre generated private key and that server uses an existing RSA implementation, all i really need to have working in masm is encryption using the public key (so that encryption with the public key happens on the client side and the decryption of with the private key happens on the server side.).

The PE written in masm should be as portable as possible and of course the faster i can get this working the better.

So my question is; should i implement this RSA encryption myself? Or should i use the CryptoAPI (Crypt32.dll) in Windows?

I usually prefer implementing the stuff myself, but from my research so far it seems that this will be taking a while, since i have no experience handling big numbers in masm. But maybe i'm wrong?
How much time could i save using the CryptoAPI? And how much portability would i loose using CryptoAPI? 

Also whatever documents or guides you could point me at related either of the solutions would be appreciated.

Hope you got some advice for me :)


Best regards
Niox

[vanjast]

Do it yourself  :wink

[Slugsnack]

It is not advisable to create your own encryption standards unless you have a lot of experience. It might not necessarily be hard. But to create a secure one will require a lot more effort and expertise. If you intend your application only to be used on Windows then I would advise CryptoAPI. However if you also intend for your app to be portable to *nix you'll have to consider other options

[Eddy]

Hi Niox,

I develop and sell a crypto library, called HIME. It is not free but you can use it for free for testing purposes. The only limitation it then has is that it has a nagscreen that pops up regularly. There is no time limit for using it with the nagscreen. The library comes as a standard Windows 32 bits dll (so it is Windows-only).
http://www.devotechs.com/HIMEMain.html .

That said. According to me, your main concern with this project will very likely have to do with "your server using an existing RSA implementation".
If you use one RSA application on your server, and another one on your client, that is very likely going to cause you some headache figuring out how to let these two formats match.
Unless you wrote the server encryption yourself and know every detail about the key and data padding and formats.
You see, before encrypting data with RSA, the data is (or should be) padded; that is: extra data is added to your plaintext data before it is encrypted.
After decrypting, the padded bytes must be removed. In order to do that, you must know exactly the format of the data.
Also, RSA ciphertext is binary data. To send over the internet, that must be converted to ascii data, using formats like Base64 etc.

If you use the same cryptosystem on both client and server, you are spared from handling all this padding and formatting stuff because encryption and decryption then have complementary functions to handle this for you. In other words: in this case you could limit yourself to using high-level crypto functions. Whereas when using two different crypto systems, very likely you need to get your hands dirty handling some low-level formatting and byte filtering stuff.
Just something to consider.

Kind regards

[niox]

Hey guys thx for your answers

Slugsnack: Good point but im not creating my own encryption standard, just using the aldready existing RSA. I would think that i could implement it safely with some research. Even though its been a while, I do have some experience with cryptography although im nothing near an expert.

Eddy:
Very good point with the padding. But maybe i could get around this issue simply by encrypting for instance a 1024bit message with a 1024bit RSA key (1024 bit module number)?
Luckily i can easily modify the server implementation if this isn't the case.

Actually i already implemented a Base64 encoding routine in masm a while ago for the purpose as you suggest. However since then i realized it would be much easier and simpler just to make my own simple protocol that isn't restricted by ascii chars for this purpose. Of course there are some extra security considerations in doing that ..

You HIME library looks really nice. It might be overkill for this little project i will concider using it for testing as you suggest. :)

Kind regards
Niox

[niox]

Very good point with the padding. But maybe i could get around this issue simply by encrypting for instance a 1024bit message with a 1024bit RSA key (1024 bit module number)?

For anyone interested. This isn't possible if the padding specified in PKCS (#1) is used, which it is in many implementations of RSA. It seems likely to work with other padding schemes though.

[Eddy]

>by encrypting for instance a 1024bit message with a 1024bit RSA key (1024 bit module number)?
--- Yes, that is basically 'padding' what you are doing then.
One vital thing that you should consider when padding your plaintext upto the modulus length is this:
The padded plaintext must always be of smaller value than the modulus! Otherwise, decryption will fail!
In practice, you could do it like this. If the key generation function of your crypto package is good, the generated modulus (in case of a 1024 bit key strength) will have 1024 significant bits. By this I mean that the most significant bit of the modulus will be 1.
You can make sure that your padded plaintext is smaller than this modulus by adding bytes on the most significant side of the plaintext. Then, make the most significant bit of the padded plaintext zero. Now, the padded plaintext is smaller than the modulus.
To make sure, you can make the two most significant bits zero, or mathematically compare padded plaintext and modulus.

Is your plaintext always (considerably) smaller than the modulus length?
Because, (as you probably know) if the plaintext is large, public key encryption becomes very slow. In that case, you better use a different approach, using a combination of public key encryption (RSA) and secret key encryption (AES/Rijndael).

>Luckily i can easily modify the server implementation if this isn't the case.
---- That is definitely a benefit.

>You HIME library ... might be overkill for this little project i will concider using it for testing as you suggest. :)
---- It is a toolkit with lots of functions related to data security (it also has bignum math functions), and it might be overkill if you only need a few functions of it or if it is not for a commercial application.
But you can use it for free without any time limit.

Kind regards
Eddy

[Eddy]

Very good point with the padding. But maybe i could get around this issue simply by encrypting for instance a 1024bit message with a 1024bit RSA key (1024 bit module number)?

For anyone interested. This isn't possible if the padding specified in PKCS (#1) is used, which it is in many implementations of RSA. It seems likely to work with other padding schemes though.

---- Yes, your unpadded plaintext length must always be atleast one byte smaller than the modulus length. Otherwise, you cannot pad it.

[niox]

One vital thing that you should consider when padding your plaintext upto the modulus length is this:
The padded plaintext must always be of smaller value than the modulus! Otherwise, decryption will fail!
In practice, you could do it like this. If the key generation function of your crypto package is good, the generated modulus (in case of a 1024 bit key strength) will have 1024 significant bits. By this I mean that the most significant bit of the modulus will be 1.

Ouh yeah ok! So lets say the modulo had 0 on the most significant bit and 1 on the second most significant bit. That would in effect mean a 1023 bit encryption?
Was just checking and luckily my key does have all of the bits being significant, so at least this key will be fine for padded messages of 1024.

Is your plaintext always (considerably) smaller than the modulus length?
Because, (as you probably know) if the plaintext is large, public key encryption becomes very slow. In that case, you better use a different approach, using a combination of public key encryption (RSA) and secret key encryption (AES/Rijndael).

Yeah I'm only using RSA to transmit the key for a symmetric encryption algo.. I was planning on looking into something like TEA for that purpose, since its easy to implement. I haven't gotten to research the security of TEA, do you have any experience with this algo? This project is still just a hobby project so no need to have extremely good security but still i would like to know.

Thx for all your help so far :)

Niox

[Eddy]

So lets say the modulo had 0 on the most significant bit and 1 on the second most significant bit. That would in effect mean a 1023 bit encryption?

Correct!

Was just checking and luckily my key does have all of the bits being significant, so at least this key will be fine for padded messages of 1024.

A (good) public key generation routine makes sure that this is the case.

Yeah I'm only using RSA to transmit the key for a symmetric encryption algo..

That's the way to go, yes. Just make sure to generate a new (pseudo)random key for every new message.

...TEA, do you have any experience with this algo?

I once planned to integrate it into HIME, because the algo itself is simple and I expected it to be fast. But I did some research on it (back then) and the experts seemed to be in agreement that TEA was/is not terribly secure. I seem to remember that there where two versons of it at the time (about 4 years ago).
For symmetric key encryption I would recommend AES/Rijndael (or any other block cipher: TwoFish, BlowFish, CAST, Serpent,...) or even ARC4/RC4. RC4 is fast and still good to use, provided it is correctly used.

Kind regards

[vanjast]

The problem with the available crypto code is that it's probably been cracked already, which renders it useless if attacked by determined 'hackers', or the FED

Besides being a great educational exercise, if you create your own, your encrypted stuff stays secret for longer.
There's lots of nice juicy educational material out there and it's a good idea to move into the DSP area of encryption.
If you live in the USA, UK .. be warned the 'psycho boys' will be after you if you go public with very good encryption code - Remember PGP, they lay claim to your hard work.
:bg

[Ghandi]

Just on RSA, did anybody else see that RSA-768 was broken?

http://arstechnica.com/security/news/2010/01/768-bit-rsa-cracked-1024-bit-safe-for-now.ars?utm_source=rss&utm_medium=rss&utm_campaign=rss

HR,
Ghandi

[niox]

Yeah I'm only using RSA to transmit the key for a symmetric encryption algo..

That's the way to go, yes. Just make sure to generate a new (pseudo)random key for every new message.

For every new message? I imagined using the same key for each session with a possible maximum timeframe of for instance 4 hours.. That isnt good enough?

I once planned to integrate it into HIME, because the algo itself is simple and I expected it to be fast. But I did some research on it (back then) and the experts seemed to be in agreement that TEA was/is not terribly secure. I seem to remember that there where two versons of it at the time (about 4 years ago).
For symmetric key encryption I would recommend AES/Rijndael (or any other block cipher: TwoFish, BlowFish, CAST, Serpent,...) or even ARC4/RC4. RC4 is fast and still good to use, provided it is correctly used.

Oh i see, well maybe i should consider RC4 then since its simple to implement. Implementing the other ones would take soo long i suspect, don't you agree?



Best regards
Niox

[Eddy]

The problem with the available crypto code is that it's probably been cracked already, which renders it useless if attacked by determined 'hackers', or the FED
.... if you create your own, your encrypted stuff stays secret for longer.

--- Not quite. This is a common laymans misconception.
The benefit of using generally accepted crypto algorithms (such as RC4, AES/Rijndael, DES3, etc.) is that they are designed by real cryptographers (experts in their field of work) and that the algorithms receive a lot of scrutiny. Meaning, that every Crypto Tom, Crypto Dick and Crypto Harry is trying to 'break' it, trying to get their names in the papers. You can rest assured that if AES or any other generally accepted crypto algo was actually 'broken', it would be headline news (See the news today about 768 bit RSA). If no such news is published, that means that these algos are still secure.

Creating your own crypto algorithm is fun, by all means. I once did it too. It is easy to write an algorithm that turns readable text into gibberisch characters. Such algorithms are perfect for preventing your kid sister from reading your 'personal' mail messages. However, it will take expert crytographers about 3 minutes max to decrypt your 'cipher text' back into plaintext. Especially with the tools that these people have.
Cryptography is a very specialised field of expertise. Especially designing encryption algorithms is not for the faint of heart, atleast if you want to be taken seriously.

if you create your own, your encrypted stuff stays secret for longer.

---- Particularly this sentence is a big 'no no!' in cryptography!
It is in fact the opposite! If you rely on the secrecy of your algorithm for your data to be secure, it will only be a matter of time before someone reverse engineers your code and will unravel your algorithm, rendering it useless.
In encryption, the rule is this: for a secure encryption algorithm, the security lies only (!) in the key, not in the algorithm. Because the algo will be unraveled sooner or later.
That's why, in the recent years, any encryption algo that wants to be taken seriously has its source code published for scrutiny.

Remember PGP, .

Yep, Paul Zimmerman fought hard to provide us good citizens with solid crypto software.  :U

Kind regards

[Eddy]

Just on RSA, did anybody else see that RSA-768 was broken?

Yes, I read it today.
There is one thing that needs to be clarified. And that is the meaning of the word 'broken' in this context.
For us layman, if we hear that an algorithm is 'broken' we tend to think that all of our data, encrypted with that algorithm, can be read by an attacker without any effort, and especially without knowing the key.
That is totally not so.
You must know that you can decrypt ciphertext by brute-forcing it. That is, you can 'simply' try every possible key for that algo and see if any key decrypts the ciphertext into readable text.
For example, if you were to invent an encrypton algo that allows the use of 100 possible different keys, an attacker would only have to try to decrypt your ciphertext with all of the 100 possible keys.
One of the 100 possible keys would decrypt your ciphertext into readable text. That is brute-forcing an encryption algo.
The strength of todays common encryption algos lies in the fact that they have an enormous amount of possible keys.
For example, AES-256 (from the hand of my fellow countrymen Joan Daemen and Vincent Rijmen) has 2^256 possible keys. That is: 115792089237316195423570985008687907853269984665640564039457584007913129639936 keys.  :bg
Brute-forcing that would take an enormous amount of time, even with a giant cluster of todays computers, so it is considered unfeasable.
Of course, with increasing performance of computers, that time will decrease in the future, requiring the need of stronger keys or stronger algos.
Now, back to an algorithm being considered 'broken'.
If it is published that an algo is 'broken' it means that a team of specialists has found a way of decrypting ciphertext back into plaintext with an effort (slightly) less than the effort required to brute-force it.... And sometimes there are even some special requirements that the plaintext/ciphertext needs to fullfil.
What does it mean in practice? Say that RSA 768 bits takes 1500 years on one pc to brute force it. If cryptographers find a way so that it only takes them 1499 years to decipher the ciphertext, they consider the algo broken .... No more, no less.
Do you now need to worry if your sensible data is encrypted with RSA 768 bits? Not very likely. The signal this should give you is that you should consider encrypting your data in the near future with a stronger key. That's all...

Kind regards