Unsecure EC scalar multiplication

[antonio-fr]

You should warn clearly that this implementation of ECC point multiplication is not secure at all regarding side-channel attacks (power, EM/RF emissions, memory read), and timing measurements. Depending of the bits of the scalar number (usually a private secret), the operations performed are very different.
https://github.com/albertobsd/ecctools/blob/main/gmpecc.c#L99

All the operations requiring this point multiplication are affected and are not secure. Public key computation (with keygen, or calculatefromkey) and sharedsecret ECDH.

This should not be used in any system in production, or securing a private key.

[albertobsd]

You should warn clearly that this implementation of ECC point multiplication is not secure at all regarding side-channel attacks (power, EM/RF emissions, memory read), and timing measurements. Depending of the bits of the scalar number (usually a private secret), the operations performed are very different. https://github.com/albertobsd/ecctools/blob/main/gmpecc.c#L99

Yes i agree totally with you, if the user system is compromised what we can do? Nothing...

I guest that you already warning to you users not to use the python scripts to work with real Keys right?

I think that this is an issue of all the cryptography tools most of them. Please if you found another way around let me know.

Regards!

[albertobsd]

For GMP i think that i can use some kind of custom memory allocators:

https://gmplib.org/manual/Custom-Allocation

And use then with the gcrypt secure memory allocator
https://gnupg.org/documentation/manuals/gcrypt/Memory-allocation.html#Memory-allocation

But that maybe only solve the the part of read the key from the memory, for the other thing that you say like EM/RF emissions really nobody is protected. Anyway those kind of attacks are only performed against Important people.

Example if you create a private key in trusted page like https://www.bitaddress.org/bitaddress.org-v3.3.0-SHA256-dec17c07685e1870960903d8f58090475b25af946fe95a734f88408cef4aa194.html you also are exposed to same attacks that you mention before.

As i know most of those attacks are high in complexity and only will performed by a high skilled hackers. As i said before if the user system is compromised what we can do?

Regards!

[antonio-fr]

If the user system is compromised what we can do? Nothing...

Well, it's not about the system compromised, it's more about external leakage that can lead to a private key recovery. This doesn't require any compromise of the system. The issue I'm referring about is that the private information leak outside of the system because of bad coding practice relative to the security.

You already warning to you users not to use the python scripts to work with real Keys right?

Can you share to which Python script you are referring to? I'm maintaining Uniblow a crypto wallet, which is in Python. Still the cryptographic parts are all in C.

This is an issue of all the cryptography tools most of them. Please if you found another way around let me know.

Not at all. Most of the systems are secure relative to this issue. The good and secure cryptographic tools use secure "ladder" algorithms about this. For example it means not having any "if" branches on the private key data, or performing the same computations on both branches. Sometimes it even means computing with fake data, one "if" path is real, an other is "fake", but for an external PoV one can't tell which one was taken, hence it is secured.
The issue is specifically that your code performs many operations if the bit is 1 and none if the bit is 0. That leaks directly the private keys bits, outside of your system. In practice it means your code shall not do like that.
A better advice actually is not to code you own cryptography, and use well tested and secure libraries such as libsodium, OpenSSL, WolfSSL, secp256k1 (if ECP k1),... That doesn't mean you can't make your own software to discover how it works internally, for educational purpose. I just say you need to clearly states this work is insecure and for educational purpose.
Elliptic scalar point is very hard to make it immune to this issue. So let others specialists take care about this part.
Overall, it is just a matter of warn the users about this, because you did your cryptography, and that's bad result.

This issue has nothing to do with memory allocation. Maybe you can improve this part, but don't spend time about this, because you're right if a system is compromised internally, there nothing to do. But here I'm talking about external attacks, your code is actually leaking the private data beyond the system boundary.

Most of those attacks are high in complexity and only will performed by a high skilled hackers.

First of all, the issue here is obvious and easy to exploit. Then it is just a matter to warn clearly that this software is not secure, and shall not be used with private data, with lot of money in it, securing very private message, and it is provided for educational purpose. Better safe than sorry. Of course bad actors will focus on valuable information, but imagine someone who is Important person uses this software, or a software editor picks your CLI or code, one will be targeted and defeated. So do you best to prevent the use of this software as it is to protect any sensitive or valuable data/keys.

If you're interested on the matter, I share some research work about practical defeat using side channels. There are related to leakage of ECDSA data because of issue in the ladder algorithm.

1. Minerva Leaky Loops
   A timing issue leaks some bits of the ephemeral key. Leading to private key recovery.
   https://minerva.crocs.fi.muni.cz/
   https://eprint.iacr.org/2020/728.pdf

Note that I developed a computational tool that can be use in such cases, to recover private key from internal known nonce data. https://github.com/bitlogik/lattice-attack

2. A side journey to Titan
   A issue in scalar multiplication in some old secure element leak internal nonce part, leading to private key recovery outside the secure element.
   https://hardwear.io/netherlands-2021/presentation/A-Side-Journey-to-Titan.pdf
   https://ninjalab.io/wp-content/uploads/2021/01/a_side_journey_to_titan.pdf

3. Trezor Power Analysis
   A very poor EC ladder algorithm combined with insecure hardware leak the private key with some signatures performed.
   https://test.jochen-hoenicke.de/crypto/trezor-power-analysis/

[albertobsd]

3. Trezor Power Analysis

It need physical access to the hardware no?

I will change the code from:

		for(i = 0; i < no_of_bits; i++) {
			if(mpz_tstbit(m, i))	{
				mpz_set(SM_T.x, R->x);
				mpz_set(SM_T.y, R->y);
				mpz_set(SM_Q.x,DoublingG[i].x);
				mpz_set(SM_Q.y,DoublingG[i].y);
				Point_Addition(&SM_T, &SM_Q, R);
			}
		}

To

		for(i = 0; i < no_of_bits; i++) {
			if(mpz_tstbit(m, i))	{
				mpz_set(SM_T.x, R->x);
				mpz_set(SM_T.y, R->y);
				mpz_set(SM_Q.x,DoublingG[i].x);
				mpz_set(SM_Q.y,DoublingG[i].y);
				Point_Addition(&SM_T, &SM_Q, R);
			}
			else {
				mpz_set(Dummy.x, R->x);
				mpz_set(Dummy.y, R->y);
				mpz_set(Dummy.x,DoublingG[i].x);
				mpz_set(Dummy.y,DoublingG[i].y);
				Point_Addition(&Dummy, &Dummy, R);
			}
		}

BTW someone else request to you to review the code ? or just for fun?

[antonio-fr]

Yes most of these attacks requires a physical access to the derive, or at least being in near proximity. I've seen in some cases the physical proximity can be achieved by server co-location. E.g. you rent a virtual server in the same machine. Also this kind of attack need to run some signatures to leak from the code when it is running (no run, no leak). But the signatures do not have to be queried by the hacker, it can be the user.

This code looks far better. On average it will double the time it takes to compute, but that avoids loud side-channel leak. EC algos in cryptographic libraries achieve both performance and security. That's why the best option is to delegate this task to this kind of libraries.

I randomly found your repo, as I'm very interested in applied crypto algorithms. And then when I saw it performs point multiplication, I was curious to see how you handle it. And then I was "Oh my god", I need to tell it to warn the users. Because you algorithm choice was the worse regarding security. And to tell you to take care when you are designing cryptographic "core" algorithms, it is much more hard that one can think.

[antonio-fr]

I forgot to tell, take care your dummy points need to be random. Else if 0, their "trace analysis" would likely reveal some difference btw the branches, and one could tell which one was taken, so this dummy would be useless.

[antonio-fr]

In case you really want to provide your own crypto secure code. You may follow some algorithms guidelines. For example FIPS ones for EC : FIPS 186-4 Appendix 4. That means you don't choose yourself the method and the algorithm, but you just implement the algorithm they propose. That doesn't mean the implementation will be OK, but at least the algorithm and method to compute used is OK. The same advice stands for modular arithmetic and private key generation (B.4 provides 2 methods for generation).

[antonio-fr]

At some point, it is much easier, and secure to rely on cryptographic libraries, that did this hard work. In C, I personally enjoy WolfSSL and libsodium. Not sure libsodium can handle EC Weistrass/Koblitz, it is maybe only compatible with Ed25519 (and X25519).

[albertobsd]

Thanks a lot I adde the warning: https://github.com/albertobsd/ecctools#warning

Also I just add the use of secure memory by libgrypt
And modify the code for the Scalar multiplication.

I forgot to tell, take care your dummy points need to be random. Else if 0, their "trace analysis" would likely reveal some difference btw the branches, and one could tell which one was taken, so this dummy would be useless.

I think that this is not the case for this code if you check: https://github.com/albertobsd/ecctools/blob/main/gmpecc.c#L108

		for(i = 0; i < no_of_bits; i++) {
			if(mpz_tstbit(m, i))	{
				mpz_set(SM_T.x, R->x);
				mpz_set(SM_T.y, R->y);
				mpz_set(SM_Q.x,DoublingG[i].x);
				mpz_set(SM_Q.y,DoublingG[i].y);
				Point_Addition(&SM_T, &SM_Q, R);
			}
			else	{	/* Doing exactly the same operations but with destination dummy */
				mpz_set(Dummy.x, R->x);
				mpz_set(Dummy.y, R->y);
				mpz_set(Dummy.x,DoublingG[i].x);
				mpz_set(Dummy.y,DoublingG[i].y);
				Point_Addition(&SM_T, &SM_Q, &Dummy);
			}
		}

If you check both parts do the same Operations first set of the Dummy point and then do the same Point_Addition but the destination is the dummy point in the else part.

This was a really rudimentary Scalar multiplication, I can improve it a lot and keep the same security by only adding Bytes 32 times instead of bits 256 times, this require a little extra precalculated points for every byte but it can solve both problems performance and security.

Again thanks a lot is really cool talk with somebody that know what is he doing, instead with people who only request new features.

btw I'm reading all your links.

Regards!