Problem in Elliptic Curve Cryptography DSA

[Ricardo_Costa]

Hello,

It seems there is a problem in the ECCPSignDSA function. It fails with ippStsMessageErr when the message digest value is greater than the EC group order value, even if both have the same bit length. That should not happen according to the standards (IEEE1363-2000/10.2.2 or FIPS186-3/6.4), which define that the message digest shall be at most the same length in bits of the group order, but not itsvalue. Similarly, the Nyberg-Rueppel version shall accept messages of at most (n-1) bits of the group order.

Also, the IPP documentation states, incorrectly, for both schemes:

ippStsMessageErr

Indicates an error condition if the value of msg pointed by pMsgDigest falls outside the range of [1, 1-n] where n is the order of the elliptic curve base point G.

I believe there is a typo, it should read "n-1" instead of "1-n" for the NR version and just "n" for the DSA version, and "n" would be the bit length of the values instead of the values themselves.

I have attached a modifiedsample from the documentationto demonstrate the problem (see ecc.cpp). A 256-bit message digest with all bits set to1 should be fine forthe 256-bit EC, but ippsECCPSignDSA rejects it, because the order value is smaller. If the digest is set to be less than the order value, no error occurs.

Using the latest IPP 7.0.3.

Regards,
Ricardo.

[Joseph_S_Intel]

Hi Recardo,
I have contacted engineering to ask that they review the issue and will get back to you with their response. Thanks for the report.

Walt

[Andrzej_Chrzeszczyk · Accepted solution]

Hello Ricardo

Look at similar thread:
http://software.intel.com/en-us/forums/showthread.php?t=58862

(The answers 2),3) are not recommended
for security reasons)

I'm not representing Intel's developers but I'm accepting their assumption
that the curve order is larger than the hash value
It is natural for me (although more restrictive than that in FIPS)

Andrzej Chrzeszczyk

[Ricardo_Costa]

Thanks for pointing it out, that explains the problem. However the documentation refers to the standards but do not implement them exactly, so it's still an error.

Also, I don't know if the signature offers the same bits of security when using (hash % n) instead of the full length. Is it guaranteed to keep the same security properties?

Ricardo

[Andrzej_Chrzeszczyk]

The signature computations are performed modulo n
so the reduction modulo n of the hash does not change the result

(assuming that the appropriate bit lengths are OK
FIPS186-3 p.30:
"It is recommended that the security strength associated with the bit length of n
and the security strength of the hash function be the same unless ...")

Andrzej Chrzeszczyk

[Ying_H_Intel]

Hi Andrzej, Ricardo,

Thanks for the informative discussions.
Here is some comments forour engineers,

Definitely, the ippCP manual has typo in "Return Values" description. Namely in ippStsMessageErr explanation.

The legal range of message to be signed is [1,n-1]. Exactly this range is used in the ippsSignDSA check stage.

In attached code (ecc.cpp) the value being signed is (2^256) -1 and goes beyond the order of used EC.

That is why error the code is returned by ippsSignDSA.

Thanks
Ying H.

[Andrzej_Chrzeszczyk]

Hello Ying
Thanks

You mean of course ippsECCPSignDSA check stage

Andrzej Chrzeszczyk

[Ying_H_Intel]

Dear all,

Just let you knowthat IPP 7.0.5 released in Intel registration center <<https://registrationcenter.intel.com/>>. The documentation typo was supposed fixed the version. You are welcomed to try it.

Best Wishes,
Ying