Buffer overflow in ecdh_demo

[xennex22]

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

[kokke]

Hi @xennex22 and thanks for opening this issue :)

Am I misunderstanding you or would a solution be to just increase the buffer-sizes for 80 + 112 bit curves to be 32-bit aligned?

[xennex22]

That would work, but I do not understand the underlying functions enough to know if this is an indication of a problem with the intermediate calculations. Otherwise I'd stick something in the header file so it can be used in the application code. Either

define ECC_PUB_KEY_BUF_SIZE 48 etc after each #define ECC_PRV_KEY_SIZE, or you could go for #define ECC_PUB_KEY_BUF_SIZE (2 ((int)(ECC_PRV_KEY_SIZE+3)/4) 4) in the body, but I would prefer the former as you are already just calling out the private key size for each curve type, and it is more obvious what the size is.

Edit: Private key buffers have overruns too. bitvec_degree() starts at the 32 bit word boundary past the length of the buffer.

define ECC_PRV_KEY_SIZE 21

define ECC_PRV_KEY_BUF_SIZE 24

define ECC_PUB_KEY_BUF_SIZE (2 * ECC_PRV_KEY_BUF_SIZE)

[xennex22]

ecdh.c #936 change: gf2field_mul(u1, x1, y1); / u1 G / to: gf2point_mul(x1, y1, u1); // (x1,y1) = u1 G(base)

ecdh.c #940 change: gf2field_mul(u2, w, z); / u2 Q / to: gf2point_mul(w, z, u2); // (w,z) = u2 public

Still does't work.

I'm not happy with the modulo code (repeated several times):

if (bitvec_get_bit(x1, CURVE_DEGREE)) { printf("reduction on x1\n"); gf2field_add(x1, x1, polynomial); }

bitvec_get_bit() only looks at the highest bit of the number but if the number can be greater than n if the next highest bit is set. Again, my lack of understanding prevents me from determining if this is a problem.

You can see this in ecdsa_verify when s is inverted - it will possibly set most of the high bits.

[kokke]

Closing because this fixes the buffer overflow: https://github.com/kokke/tiny-ECDH-c/commit/fefb541f284818605cd09990a2e0a84b09bc381d

Clang's address-sanitizer no longer complains about the issue you've pointed out about non-32bit alignedness for the private key sizes.