Have you ever tried to cross-compile it?

[GeorgeKalovyrnas]

Hi,
I have tried to cross-compile it for ARM (very restricted) architecture.
The cross compilation was successful. But when trying to run the application I get always std::bad_alloc exception.
The very same code works just fine on my laptop.
Can you suggest a way to find the error?

Thanks and regards

[calccrypto]

Hi. I have never tried to cross compile OpenPGP for ARM. I suggest running the code with gdb to find out where the error is coming from. You might just be out of memory.

[calccrypto]

@GeorgeKalovyrnas Have you gotten a diagnosis of what's going on?

[GeorgeKalovyrnas]

No, not yet.
I doubt that it's an "out of memory" issue, because the file is really small (less than 30 Kb).
I tend to believe that there is some stack (?) corruption, maybe because of bad configuration of cross compilation.

For sure there will be an issue with larger files.
The problem in latter case is that everything (decompression, decryption) is happening in-memory.

Is it difficult to substitute some parts of the code, with calls from OpenSSL stack (already cross-compiled)?

[calccrypto]

I do not know how difficult it would be to use the OpenSSL stack, as I have never used it. It might be an interesting project to add an abstraction layer to allow for switching between the stuff I wrote and OpenSSL.

Can you tell me what packages you are using/steps you are taking to cross compile OpenPGP? I tried cross compiling for armhf a few days ago, but my lack of experience with cross compiling stopped me pretty early on.

[GeorgeKalovyrnas]

As it seems the out of memory issue is happening in function S2K3::run().
The S2K3::coded_count(count) returns 32505856, with count = 239.
Is this normal?

[calccrypto]

Yes. That looks correct according to RFC 4880 sec 3.7.1.3

The count is coded into a one-octet number using the following
formula:

   #define EXPBIAS 6
       count = ((Int32)16 + (c & 15)) << ((c >> 4) + EXPBIAS);

The above formula is in C, where "Int32" is a type for a 32-bit
integer, and the variable "c" is the coded count, Octet 10.

The issue might be that the 32505856 octets are required:

If the hash size is less than the key size, multiple instances of the
hash context are created -- enough to produce the required key data.
These instances are preloaded with 0, 1, 2, ... octets of zeros (that
is to say, the first instance has no preloading, the second gets
preloaded with 1 octet of zero, the third is preloaded with two
octets of zeros, and so forth).

meaning that I have to do something like this:

data = <32505856 octets>
hash(data) + hash('\x00' + data) + hash('\x00\x00' + data) + ...

which generates lots of temporary data (especially without std::string_view). This preloaded octets acts like another salt, preventing the data from being hashed beforehand and being stored in a compact manner.

[calccrypto]

Give f797d7d a try. I reduced the amount of duplicate data being generated by a bit. Maybe that might help?

[GeorgeKalovyrnas]

Obviously, since hashing requires 32505856 byes (32Mb) it's impossible for my device to cope with this size. So, I assume that "out-of-memory" issue is a normal consequence!
I'm sorry that I wasn't observant enough to see the implementation of S2K3::coded_count(count) member function.
I don't know how it's possible to overcome this memory limitation.

[calccrypto]

Darn. I suppose it is possible to regenerate the data for each round , but that would be agonizingly slow.

[calccrypto]

Repeatedly regenerating the context is faster than combining it all together. 25bf52e

[GeorgeKalovyrnas]

Amazingly good job!
It's working like a charm.
The only issue that I have now is the deadly slow decryption of key!
For my device it takes two and a half minutes for the decryption.

[calccrypto]

How big is your key?

[GeorgeKalovyrnas]

How should I measure it?
(Sorry for my ignorance!)

[calccrypto]

If you dump your public key, it will tell you:

$ cli/OpenPGP show tests/testvectors/gpg/Alicepub
Old: Public-Key (Tag 6)
    Version: 4 - New
    Creation Time: Sun Jun 22 12:50:48 UTC 2014
    Public Key Algorithm: RSA (Encrypt or Sign) (pka 1)
--> RSA n (2048 bits): bc047e94d471f3ccbd525d6a6f8e17f7b1f00527c722c3913ce787fbd0090e3af8be7e59410f63b3983a9507b761045c11510e62f5a8cfbcdc180976a4c225737b8e06d8531f38c6eaa996954d5521a6763231f07c2b43605d052abdf39d6c668ac94bc89f543052d050530c70c48a49a970867c00178f9076dd0e151d254632767b2926e9baa22c6d0c213f1f45de74991396d7e8d10508cf679139410ab311b1279dd3c0d37facca54d523cd14a3df488eb8f592c5a19bcfede67c8170815c588adf39d188197da40492aac5b183c303f6ef23b0b5e48ff73b2d806afb0fb4f16ba32769249d3a7ca0ef0b9b3d57852dc9a979b6d56f3dc170e28dcb2e536d
--> RSA e (17 bits): 010001
Old: User ID (Tag 13)
    User ID: alice (test key) <alice@example.com>
Old: Signature (Tag 2)

...

Now that I think about it, I'm not entirely sure what I can do to speed things up, since the calculations are done by GMP, not my me for the most part. Maybe change RNGs?

[GeorgeKalovyrnas]

I have some good news for you and for me too of course. :-)
In my specific case, (i.e. SHA1 key) I've managed to smash the decryption time record.
At the beginning the decryption process was almost 2.5 minutes, and now it's down to 10 seconds.
What I have actually done was to remove the STL strings in calc() member function, and instead use plain old pointers.
That did the job.

[calccrypto]

Huh. I didn't realize I was doing so much string copying in the hashing code.

[GeorgeKalovyrnas]

In function SHA1::calc it has, one string allocation inside the "for" loop and a couple of substring operations. When you have millions of iterations, these operations are really expensive.

[GeorgeKalovyrnas]

Using OpenSSL's SHA1 functions I've managed to bring down the total time from 10 seconds to 3 seconds.

[calccrypto]

Wow...

Would you care to add analogous changes to the other hash/encryption functions? I would be happy to add using OpenSSL as a configurable option to OpenPGP. I could do it, but I would like to have an example piece of code to work off of.

[calccrypto]

I created a new branch to start integrating OpenSSL into OpenPGP.

https://github.com/calccrypto/OpenPGP/tree/openssl

[GeorgeKalovyrnas]

Sure, I will try to help you, although I don't have experience using OpenSSL. This was my first attempt to do so.

[calccrypto]

061db39

Here's the first pass with adding hashes. The files will probably be reorganized at some point, but it works for now. You should be able to enable OpenSSL by adding -DUSE_OPENSSL=True to your cmake options.

[calccrypto]

I don't think I will be adding in the OpenSSL encryption algorithms. They have all sorts of weird quirks that were making it impossible to properly integrate:

• IDEA and Camellia don't exist, even though they aren't disabled.
• Twofish is not implemented.
• Blowfish keys are padded even though I don't want them to be.
• There were jumps using uninitialized variables everywhere, causing valgrind to vomit.
• Something in OpenSSL was messing with GMP and causing segfaults everywhere.

[GeorgeKalovyrnas]

OK
It's your choice to follow the path that you want.
As far as I know IDEA and Camellia are supported, but not by default. Also, if you use OpenSSL functions to great extend, then maybe you can get rid off GMP, which is a big hassle.

Of course there are other cryptographic libraries that include all the functions that you need. For example crypto++. And I am sure that you find one that matches your needs and project's license.
But definitely you need to optimize the hashing algorithms to obtain better speeds. It may seems of minor value for a modern PC, but for low end devices is crucial.

I will try to give you my version of improvement, which doesn't include OpenSSL functionality.

[calccrypto]

I've merged the OpenSSL stuff into master with 9187f64. You can use OpenSSL hashing and rng with -DUSE_OPENSSL=ON, or individually select each one with -DUSE_OPENSSL_HASH=On and -DUSE_OPENSSL_RNG=On

[calccrypto]

@GeorgeKalovyrnas Can I close this issue?

[GeorgeKalovyrnas]

Yes sure.
Congratulations. Very good job.
Thanks a lot.