Pelayo Bernedo Azpiri

2016-11-20 20:17:10 UTC

The XEd25519 signature method creates signatures compatible with Ed25519

using X25519 keys. If the sign bit of the public key is negative then the

private scalar used for signing is negated in order to obtain a positive

public key. The Ed25519 specification requires that the private scalars

have bit 254 set and the lower 3 bits cleared. This makes the private

scalar a multiple of the cofactor. Private scalars obtained by negating a

private X25519 key that already includes the bit masking do not conform to

this Ed25519 requirement. From my very limited understanding it seems that

this is not a problem for the single signature verification as defined in

XEd25519. Ed25519 also defines batch signature verification. Batch

verification is 3 times faster than single signature verification (at least

in the ed25519-donna implementation). Therefore there is an incentive for

an Ed25519 implementation to use batch verification whenever applicable.

Given that XEd25519 signatures are compatible with Ed25519, can they be

used with Ed25519 batch verification? What are the security considerations

of not conforming to the bit masking required by Ed25519?

The specification for the XEd25519 verification states that the X25519

public key shall be converted to an Ed25519 public key (the convert_mont

routine). Instead of this conversion, it could mention the direct

decompression from Montgomery u to Edwards as shown in

https://moderncrypto.org/mail-archive/curves/2015/000376.html (also by the

same author as the XEdDSA specification). I have implemented this based on

ed25519-donna and there is no measurable difference in the time required

for verification of signatures using compressed Montgomery or compressed

Edwards points.

XEd25519 signatures are fully compatible with Ed25519 signatures. If the

requirement of Ed25519 compatibility is dropped and the only goal is to be

able to use X25519 keys for signing and verifying, then the computation of

the hash(R || A || M) can be done with the X25519 public key instead of the

Ed25519 public key. This still ties the message to the public key as

explained in

https://www.ietf.org/mail-archive/web/cfrg/current/msg07335.html. Using the

public X25519 key would avoid the need to keep the public Ed25519 key for

signing and would also eliminate the need for caching it. Using the X25519

public key in hash(R || A || M) together with the direct decompression from

Montgomery coordinates would remove all mentions of the Ed25519 public

keys, simplifying key management.

An alternative method for generating signatures with X25519 keys was

proposed in https://moderncrypto.org/mail-archive/curves/2014/000293.html

(by the same author as the XEdDSA specification). In this proposal the sign

bit is stored in the signature. The method is otherwise identical to

Ed25519, except that it allows the attacker to choose the sign bit. In this

proposal all private scalars comply with the bit masking requirements of

Ed25519. How does this scheme compare to XEd25519? It would allow batch

verification but it is not clear to me if allowing an attacker to choose

the sign bit would somehow offer a practical attack.

Pelayo.

using X25519 keys. If the sign bit of the public key is negative then the

private scalar used for signing is negated in order to obtain a positive

public key. The Ed25519 specification requires that the private scalars

have bit 254 set and the lower 3 bits cleared. This makes the private

scalar a multiple of the cofactor. Private scalars obtained by negating a

private X25519 key that already includes the bit masking do not conform to

this Ed25519 requirement. From my very limited understanding it seems that

this is not a problem for the single signature verification as defined in

XEd25519. Ed25519 also defines batch signature verification. Batch

verification is 3 times faster than single signature verification (at least

in the ed25519-donna implementation). Therefore there is an incentive for

an Ed25519 implementation to use batch verification whenever applicable.

Given that XEd25519 signatures are compatible with Ed25519, can they be

used with Ed25519 batch verification? What are the security considerations

of not conforming to the bit masking required by Ed25519?

The specification for the XEd25519 verification states that the X25519

public key shall be converted to an Ed25519 public key (the convert_mont

routine). Instead of this conversion, it could mention the direct

decompression from Montgomery u to Edwards as shown in

https://moderncrypto.org/mail-archive/curves/2015/000376.html (also by the

same author as the XEdDSA specification). I have implemented this based on

ed25519-donna and there is no measurable difference in the time required

for verification of signatures using compressed Montgomery or compressed

Edwards points.

XEd25519 signatures are fully compatible with Ed25519 signatures. If the

requirement of Ed25519 compatibility is dropped and the only goal is to be

able to use X25519 keys for signing and verifying, then the computation of

the hash(R || A || M) can be done with the X25519 public key instead of the

Ed25519 public key. This still ties the message to the public key as

explained in

https://www.ietf.org/mail-archive/web/cfrg/current/msg07335.html. Using the

public X25519 key would avoid the need to keep the public Ed25519 key for

signing and would also eliminate the need for caching it. Using the X25519

public key in hash(R || A || M) together with the direct decompression from

Montgomery coordinates would remove all mentions of the Ed25519 public

keys, simplifying key management.

An alternative method for generating signatures with X25519 keys was

proposed in https://moderncrypto.org/mail-archive/curves/2014/000293.html

(by the same author as the XEdDSA specification). In this proposal the sign

bit is stored in the signature. The method is otherwise identical to

Ed25519, except that it allows the attacker to choose the sign bit. In this

proposal all private scalars comply with the bit masking requirements of

Ed25519. How does this scheme compare to XEd25519? It would allow batch

verification but it is not clear to me if allowing an attacker to choose

the sign bit would somehow offer a practical attack.

Pelayo.