Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Infinite for loop while embedding data in an Ed25519 point #466

Open
parinayc20 opened this issue Jul 21, 2022 · 1 comment
Open

Infinite for loop while embedding data in an Ed25519 point #466

parinayc20 opened this issue Jul 21, 2022 · 1 comment

Comments

@parinayc20
Copy link
Contributor

The Embed function in the Point class uses the following process to embed data into a point.

// How many bytes to embed?
	dl := P.EmbedLen()
	if dl > len(data) {
		dl = len(data)
	}

for {
		// Pick a random point, with optional embedded data
		var b [32]byte
		rand.XORKeyStream(b[:], b[:])
		if data != nil {
			b[0] = byte(dl)       // Encode length in low 8 bits
			copy(b[1:1+dl], data) // Copy in data to embed
		}
		if !P.ge.FromBytes(b[:]) { // Try to decode
			continue // invalid point, retry
		}

		// If we're using the full group,
		// we just need any point on the curve, so we're done.
		//		if c.full {
		//			return P,data[dl:]
		//		}

		// We're using the prime-order subgroup,
		// so we need to make sure the point is in that subencoding.
		// If we're not trying to embed data,
		// we can convert our point into one in the subgroup
		// simply by multiplying it by the cofactor.

		if data == nil {
			P.Mul(cofactorScalar, P) // multiply by cofactor
			if P.Equal(nullPoint) {
				continue // unlucky; try again
			}
			return P // success
		}

		// Since we need the point's y-coordinate to hold our data,
		// we must simply check if the point is in the subgroup
		// and retry point generation until it is.

		var Q point
		Q.Mul(primeOrderScalar, P)
		if Q.Equal(nullPoint) {
			return P // success
		}
		// Keep trying...
	}

In here we fill an array with random bytes then replace an fixed amount of with the data bytes and then check if the result is a valid point on the curve. If not then repeat the same process again. I doubt that maliciously crafted data can cause the loop to run infinitely. Correct me if I am wrong on some point. If not how should we solve this issue.

@ineiti
Copy link
Member

ineiti commented Aug 2, 2022

From what I remember, if the EmbedLen() returns the correct number, it is quite sure to find a point corresponding to that embedded data. But I don't think that there is a proof for that, and that it has been merely taken in a paper. Perhaps @Daeinar, @nikkolasg, or @bford remember more?

A code-path I don't understand, however, is the one where data == nil. From what I understand, this would return an INvalid point, but loop when it's a valid point. Which seems wrong.

Also I would've considered not adding the 'length' byte to the encoding, but rather letting the caller decide how they want the data to be embedded... But it's too late for this change now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants