EDDSA.decodePoint should fails on ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

[mahnunchik]

Working with ed25519 curve I've faced with strange behaviour: decodePoint doesn't fails on points out of field.

import elliptic from 'elliptic';

const ec = new elliptic.eddsa('ed25519');

const point = ec.decodePoint('ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff');
// doesn't throw Error('invalid point')

point.validate();
// returns true

What do you think?

• Is it a bug?
• Is it an implementation feature?
• Or I don't understand the logic behind the decodePoint?

[mahnunchik]

I'm working on implementing the following method on js: https://github.com/monero-project/monero/blob/v0.17.1.9/src/crypto/crypto-ops.c#L1334-L1424

There are several test cases: https://github.com/monero-project/monero/blob/v0.17.1.9/tests/crypto/tests.txt (rows starts with check_key).

The following test reports false positive results using decodePoint and validate methods:

✕ keyCheck 'edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'
✕ keyCheck 'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f' is valid 'false'
✕ keyCheck 'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' is valid 'false'

[mahnunchik]

One more observation: decodePoint from bytes and encodePoint from point produces the different bytes.

import BN from 'bn.js';
import elliptic from 'elliptic';

const hex = 'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff';
console.log('original:', hex);
// original: ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
const point = ec.decodePoint(hex);
console.log('encoded:', new BN(ec.encodePoint(point)).toString('hex'));
// encoded: 1200000000000000000000000000000000000000000000000000000000000080

[mahnunchik]

@indutny congrats with the new job in signalapp but could you please have a look at this issue 😃

[mahnunchik]

Or maybe @fanatid could assist?

[fanatid]

This happened because the input y part of the point can be reduced on creating point:

elliptic/lib/elliptic/curve/edwards.js

Line 74 in 43ac7f2

y = y.toRed(this.red);

Input y: 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Red value: 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
As result we get 0x12

[mahnunchik]

@fanatid thank you for the clarification.

Should it be considered as correct behaviour? Or maybe it is better to throw the error 'invalid point'?

For now there is the following condition for several keys:

ec.encodePoint(ec.decodePoint(key))) !== key

[mahnunchik]

Yep, I'm collecting issues/questions/suggestions related to ed25519 and little endian order of bytes used by that curve 😕

• little-endian constructor ignoring important zeroes little-endian constructor ignoring important zeroes bn.js#208
• Add endian argument to toString method Add endian argument to toString method bn.js#272
• EDDSA decodePoint doesn't support Buffer as argument EDDSA decodePoint doesn't support Buffer as argument #248

[mahnunchik]

Hi @fanatid @indutny

According to specification:

First, interpret the string as an integer in little-endian
representation. Bit 255 of this number is the least significant
bit of the x-coordinate and denote this value x_0. The
y-coordinate is recovered simply by clearing this bit. If the
resulting value is >= p, decoding fails.

https://tools.ietf.org/html/rfc8032#section-5.1.3

[fanatid]

Hi @mahnunchik, I agree that we should fix decoding.

[fanatid]

Out of interest, did you consider using WASM instead of implementing already existed code on JS?

[mahnunchik]

No, for my task I've decided to implement it in JS because 12+ mb of WASM is too heavy. Also there are some existing libraries: elliptic 💥 https://github.com/chrisdickinson/varint https://github.com/jafalter/bulletproof-js I will use to implement.

[mahnunchik]

Related question: what is the purpose of point.validate method?

elliptic/lib/elliptic/curve/edwards.js

Lines 99 to 112 in e71b2d9

	EdwardsCurve.prototype.validate = function validate(point) {
	if (point.isInfinity())
	return true;
	// Curve: A * X^2 + Y^2 = C^2 * (1 + D * X^2 * Y^2)
	point.normalize();
	var x2 = point.x.redSqr();
	var y2 = point.y.redSqr();
	var lhs = x2.redMul(this.a).redAdd(y2);
	var rhs = this.c2.redMul(this.one.redAdd(this.d.redMul(x2).redMul(y2)));
	return lhs.cmp(rhs) === 0;
	};

[mahnunchik]

While dive deep and deeper, I'd like to ask: what is the reason to use Tonelli-Shanks algorithm here:

• https://github.com/indutny/elliptic/blob/master/lib/elliptic/curve/edwards.js#L89
• https://github.com/indutny/bn.js/blob/v4.x/lib/bn.js#L3241-L3296

Instead of trick from spec: https://tools.ietf.org/html/rfc8032#section-5.1.3

I mean x = (u/v)^(p+3)/8 = u*v^3*(u*v^7)^(p-5)/8.

In my tests it is at least 5 times faster.

---

If I decide to prepare fix for this issue, could you please provide some information: which tests is required, where it is better to place it.

[mahnunchik]

@indutny @fanatid could you please have a look at PR #253

[paulmillr]

@mahnunchik hey, great job with all these notices. Fedor did some nice work with elliptic, but we need to move forward. Could you take a look at https://github.com/paulmillr/noble-ed25519? I'm using unwrapped pow to square root of curve P, it's super fast!