kokke / tiny-ecdh-c Goto Github PK

Hello, I'm using sect163k1 elliptic curve and in order to generate the public key I'm executing the following code:

int ecdh_generate_keys(uint8_t* public, uint8_t* private);

Is the result following a standard specification (compressed / uncompressed / hybrid) format defined in SEC1v2?

Thanks in advance!

hey, love your stuff. Very readable code!

have however botched it some and rewrote the sign and verify functions
where i got these below to "match".
I write in quotes because i have tried to dumb it down as much as possible and i probably skip some important steps... also thought maby it could spark some idea for you :)

#define ECC_CURVE NIST_B163
#define ECC_CURVE NIST_K163
#define ECC_CURVE NIST_B233
#define ECC_CURVE NIST_K233
#define ECC_CURVE NIST_K409
#define ECC_CURVE NIST_B571
#define ECC_CURVE NIST_K571

ecdh_example.c

sign((const uint8_t*)prv, msg, k, signature);
verify((const uint8_t*)pub, msg, (const uint8_t*)signature);

ecdh.c

void compress_signature(uint8_t* sig1, uint8_t* sig2, uint8_t* signature) {
  for (int i=0; i<ECC_PRV_KEY_SIZE; i++) {
    signature[i] = sig1[i];
    signature[i+ECC_PRV_KEY_SIZE] = sig2[i];
  }
}

void decompress_signature(const uint8_t* signature, uint8_t* sig1, uint8_t* sig2) {
  for (int i=0; i<ECC_PRV_KEY_SIZE; i++) {
    sig1[i] = signature[i];
    sig2[i] = signature[i+ECC_PRV_KEY_SIZE];
  }
}

void sign(const uint8_t* private_key, uint8_t* hash, uint8_t* random_k, uint8_t* signature) {
  gf2elem_t r, s, z, k;
  uint8_t sig1[ECC_PRV_KEY_SIZE], sig2[ECC_PRV_KEY_SIZE];
  int nbits = bitvec_degree(base_order);

  bitvec_set_zero(r);
  bitvec_set_zero(s);
  bitvec_copy(z, (uint32_t*)hash);
    
  for (int i = (nbits - 1); i < BITVEC_NBITS; ++i) {
    bitvec_clr_bit(z, i);
  }
  bitvec_copy(k, (uint32_t*)random_k);

  gf2point_copy(r, s, base_x, base_y);
  gf2point_mul(r, s, k);

  gf2field_inv(s, k);
  gf2field_mul(r, r, (uint32_t*)private_key);
  gf2field_add(r, r, z);
  nbits = bitvec_degree(r);
  for (int i = (nbits - 1); i < BITVEC_NBITS; ++i) {
    bitvec_clr_bit(r, i);
  }
  gf2field_mul(s, s, r);
  nbits = bitvec_degree(s);
  bitvec_copy((uint32_t*)sig1, (uint32_t*)r);
  bitvec_copy((uint32_t*)sig2, (uint32_t*)s);
  compress_signature(sig1, sig2, signature);
}
 

void verify(const uint8_t* public_key, uint8_t* hash, const uint8_t* signature) {
  gf2elem_t r, s, z, k, w, u1, u2, x, y;
  uint8_t rr[ECC_PRV_KEY_SIZE], ss[ECC_PRV_KEY_SIZE];  
  int nbits = bitvec_degree(base_order);

  bitvec_copy(z, (uint32_t*)hash);
  decompress_signature(signature, rr, ss); 
  bitvec_copy(r, (uint32_t*)rr);
  bitvec_copy(s, (uint32_t*)ss);
  
  gf2field_inv(w, s);
  gf2field_mul(u1, z, w);
  gf2field_mul(u2, r, w);
  
  bitvec_degree(u1);
  bitvec_degree(u2);
  
  bitvec_copy(x, base_x);
  bitvec_copy(y, base_y);
  
  gf2point_mul(u1, u1, x);
  gf2point_mul(u2, u2, (uint32_t*)public_key);
  gf2point_add(x, y, u1, u2);
  
  if (bitvec_degree(r) == bitvec_degree(x)) {
    printf("Matching\n"); 
  } else {
    printf("Not matching\n");
  } 
} 

Hi @kokke
I am using ECDH to exchange the keys and AES-128,192,256 for data encryption(Your previous implementation).For this to happen I need to exchange the specific length keys.Can your ECDH implementation generate 128,192 or 256 bit length keys.

Hello, I'm using this library to create a shared secret using 'sect163k1' elliptic curve.

At the end of the ecdh_example.c I noticed the shared secret has ECC_PUB_KEY_SIZE byte size.
Shouldn't it be ECC_PRV_KEY_SIZE? I'm not saying it's wrong, just trying to understand the code.

Thanks in advance!

Hello,

I would like to use your library to generate a secret key which is going to be used to make an encrypted channel between PC and STM32l082 microcontroller. I wrote a test code on the microcontroller, where i simulate the generation of the keys and secret for both sides (PC and STM32l082). Public and private keys are successfully generated for both sides, but i'm having a problem when i want to generate a shared secret. For one side it is successfully generated, but for the other side, the function ecdh_shared_secret() always returns 0 (array secb is not populated with values).

Here is also my testing code snippet:

int main(void)
{
	uint8_t puba[ECC_PUB_KEY_SIZE] = {0};
	uint8_t prva[ECC_PRV_KEY_SIZE] = {0};
	uint8_t seca[ECC_PUB_KEY_SIZE] = {0};
	uint8_t pubb[ECC_PUB_KEY_SIZE] = {0};
	uint8_t prvb[ECC_PRV_KEY_SIZE] = {0};
	uint8_t secb[ECC_PUB_KEY_SIZE] = {0};

	// Initializes the Flash interface and the Systick
	HAL_Init();

	// Configure the system clock
	SystemClock_Config();
	SystemCoreClockUpdate();

	// Initialize peripherals
	Random_Init();
	Leds_Init();
	USB_Init();

	// Generate private and public keys for both sides
	do
	{
		for (int i = 0; i < ECC_PRV_KEY_SIZE; i++)
			prva[i] = Random_GetNumber() % 256;
	}
	while(ecdh_generate_keys(puba, prva) == 0);

	do
	{
		for (int i = 0; i < ECC_PRV_KEY_SIZE; i++)
			prvb[i] = Random_GetNumber() % 256;
	}
	while(ecdh_generate_keys(pubb, prvb) == 0);

	// Generate shared secret on both sides
	if(ecdh_shared_secret(prva, pubb, seca) == 0)
		for(;;);

	if(ecdh_shared_secret(prvb, puba, secb) == 0)
		for(;;); // Here is the problem. It always returns 0

	while (1)
	{

	}
}

I tried to compile the code also on the PC, where i get the same results. I'm using the sect163k1 elliptic curve. Where do you think is the problem?

Thank you in advance.

I tried to compare the public keys which are created from your algorithm with the result from OpenSSL but the created keys are different. I used the the sect163r2 curve.

Do you have tested your version against OpenSSL or LibreSSL?

I was trying to verify the implementation against openssl, and this library doesn't create the same public-key from a private key.

I generated reference data with the following command:
openssl ecparam -name sect233k1 -out sect233k1.pem
openssl genpkey -paramfile sect233k1.pem -text -out prv_key.pem

If I run tiny-ECDH with the -DECC_CURVE=NIST_K233, and I feed in the private key from below, (starting at 0x22), I get a different public key output.

**prva[0] = 0x22;
prva[1] = 0xa0;
...

assert(ecdh_generate_keys(puba, prva));**

Is there anything in the order of private key bytes that I need to do?

prv_key.pem output
-----BEGIN PRIVATE KEY-----
MH4CAQAwEAYHKoZIzj0CAQYFK4EEABoEZzBlAgEBBB4AIqCLwypv1g0HbqYx3oGu
nJ0NRy4SMico04gPkmGhQAM+AAQALdAhSNtJVEMAE1DU8P674eeCl50LY7uoC+xS
spIB3H1RSLjsLFPUo5aHjY5IdgQlNFYPNXLTsn/tYGE=
-----END PRIVATE KEY-----
Private-Key: (232 bit)
priv:
22:a0:8b:c3:2a:6f:d6:0d:07:6e:a6:31:de:81:ae:
9c:9d:0d:47:2e:12:32:27:28:d3:88:0f:92:61
pub:
04:00:2d:d0:21:48:db:49:54:43:00:13:50:d4:f0:
fe:bb:e1:e7:82:97:9d:0b:63:bb:a8:0b:ec:52:b2:
92:01:dc:7d:51:48:b8:ec:2c:53:d4:a3:96:87:8d:
8e:48:76:04:25:34:56:0f:35:72:d3:b2:7f:ed:60:
61
ASN1 OID: sect233k1
NIST CURVE: K-233

Hello, I tried troubleshooting this library. I was attracted by how readable and well commented it is, but it seems there might be deeper problems with this implementation that I do not have time to inspect. Here are my findings to get the ball rolling:

Casting a uint8_t array to a uint32_t is dangerous, as it is affected by the underlying architecture's endianness. When you bit shift, the shift is abstracting the hardware's endianness and treating everything as big endian. So the safest procedure is to either copy to a uint32_t array via bitshifts, or to define it as such in the first place. The other option is to only use byte arrays of uint8_t. I didn't see a good reason to go for the uint32_t.

There may be unexpected behavior caused by bitvec_clr_bits(). If the range you are clearing over is not less than 32 or a multiple of 32, you will have some uncleared bits floating in the middle of the cleared range. It would be safer to clear strictly in one direction as opposed to starting at the LSB of each byte. (Clever use of & 31U as a mod 32 (consider commenting).)

In step 2 of the signing, you are not taking the leftmost bits. You are actually blanking the MS (most significant) bits with use of bitvec_clr_bits() incrementing over a range. It can be said that you're modding the natural number represented by the entire hash. This may cause variation when testing results against other libraries. Maybe you could use bitvec_clr_bits() as is, but decrement over a range starting at the LSB; then you'd be blanking right to left.

I would check the conditional operations in the Galois field arithmetic. There are places where you say, if this is zero then it's the equivalent of the addition of that, etc.. I would check all to be safe actually.

I would also consider not defining the bitvec with a size (see this post). More importantly though, it makes the copy calls unclear to the reader. How do we know we are copying the right ranges? I do see the value in the sizes updating automatically, but it wouldn't hurt to just pass these #defined values as parameters.

Using NIST_K163 so the number of bits is 163. A margin (BITVEC_MARGIN) of 3 bits is added for intermediate calculations (166 bits), then the number of 32 bit words (BITVEC_NWORDS) is calculated (6) and then number of bytes (BITVEC_NBYTES) from the number of 32 bit words = 24.
The private key size is 21 bytes (168 bits ECC_PRV_KEY_SIZE) and the public key double that (42 bytes ECC_PUB_KEY_SIZE) and buffers are allocated as such.
In ecdh_generate_keys() gf2point_copy() is called which copies the base_x into the public key buffer and base_y into the second half of the public key buffer. The second copy function bitvec_copy() copies BITVEC_NWORDS (6) into the public buffer offset BITVEC_NBYTES (24) so we clobber 6 bytes of memory past the buffer (24+24=48 bytes, buffer is 42 bytes).
Only the strengths which are not a multiple of 32 bits are affected (80 & 112 bits).

Do you intend to support curve BrainpoolP256r1 with Generic Mapping (GM) (uncompressed point, Ephermeral Keys) ??

ecdsa_verify is using gf2field_mul instead of gf2point_mul.

using K-163, i've generated a public key from the private key [0, 1, 2, ...] .... the results do NOT match the public key i generate using nodejs (which itself uses openssl, i believe)....

i've seen other issues suggesting that there may not (yet) be compatibility with other crypto libraries....

said another way, are there standard test vectors which you've used??? do you have some "expected output for this particular input" tests????

Is point compression supported? I need a compressed version of my public key which is 22 bytes long for a sect163k1 curve key pair. I can't find a way to get this right now.

I tried running the code on Contiki -2.7.. unable to run getting error related to assert.Please help me I am new to this..

Hello,
thanks for your work. I wanted to play with your implementation on both a 64 bits PC and a 16bits PIC24F µC. I played with k163 curve.

On PC, it works like a charm (although it generates a public key filled with 0x00 when I build in release and works in debug) but on the PIC24F, it takes around 30s (!) to execute ecdh_generate_keys() and the final result is a public key filled with 0x00. May I have incorrectly used it so that it generates such a public key? Is the implementation supposed to work on 16bits CPUs?

Hi kokke, thanks for a great project! I have it working for k163 + k283.
To get it working for all my cases I had to do some tweaks. The main issue was that in your algorithms, coeff_a is treated as constant 1. As far as I can see, it is only for k163 that a is 1, it is 0 for all other curves.

I'm completely new at GitHub projects, how do you want me to proceed? I have made a clone of your project, I could upload my changes there and make a pull request?

Kind regards!

/tmp/cc6EXGlG.o: In function ecdh_demo': ecdh_example.c:(.text+0x150): undefined reference to ecdh_generate_keys'
ecdh_example.c:(.text+0x1ad): undefined reference to ecdh_generate_keys' ecdh_example.c:(.text+0x1ea): undefined reference to ecdh_shared_secret'
ecdh_example.c:(.text+0x227): undefined reference to ecdh_shared_secret' /tmp/cc6EXGlG.o: In function ecdsa_broken':
ecdh_example.c:(.text+0x337): undefined reference to ecdh_generate_keys' ecdh_example.c:(.text+0x358): undefined reference to ecdsa_sign'
ecdh_example.c:(.text+0x372): undefined reference to `ecdsa_verify'
collect2: error: ld returned 1 exit status

Kokke! Thanks for the project, looks great!

A few questions:

1. Can it be used on big endian machines with same results?
2. In ecdh.h two curves NIST_K409 and NIST_K571 are marked as not working. What is a possible reason?

Hi, really compact and very readable implementation that I have just started following - did SG7 and yourself make any plans/progress?
Many thanks

/tmp/cc6EXGlG.o: In function `ecdh_demo':

ecdh_example.c:(.text+0x150): undefined reference to ecdh_generate_keys' ecdh_example.c:(.text+0x1ad): undefined reference to ecdh_generate_keys'
ecdh_example.c:(.text+0x1ea): undefined reference to ecdh_shared_secret' ecdh_example.c:(.text+0x227): undefined reference to ecdh_shared_secret'

/tmp/cc6EXGlG.o: In function `ecdsa_broken':

ecdh_example.c:(.text+0x337): undefined reference to ecdh_generate_keys' ecdh_example.c:(.text+0x358): undefined reference to ecdsa_sign'
ecdh_example.c:(.text+0x372): undefined reference to `ecdsa_verify'
collect2: error: ld returned 1 exit status

We want to use it in a 32-bit processor. but it gives an overflow error. would appreciate your help.

region ‘IMEM’ overflowed by 17932 bytes.

Hii,

In this code both ECDH and ECDSA working ?

NIST_K571
const gf2elem_t coeff_b = { 0x00000001,

NIST_K409
const gf2elem_t coeff_b = { 0x00000001,

When using same private key to generate public key and share key，if copy private key in each step the result will be different

K-163 is still too difficult for IoT devices. May I have simpler parameters, such as 20 bits, not 80 bits in K-163?

Any new updates on ecdsa? If anyone has fixed it please drop a link of that.