topic Problem in Elliptic Curve Cryptography DSA in Intel® Integrated Performance Primitives

Problem in Elliptic Curve Cryptography DSA

Ricardo_Costa — Tue, 10 May 2011 23:43:53 GMT

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.

Problem in Elliptic Curve Cryptography DSA

Joseph_S_Intel — Fri, 20 May 2011 18:44:54 GMT

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

Problem in Elliptic Curve Cryptography DSA

Andrzej_Chrzeszczyk — Sun, 22 May 2011 11:20:14 GMT

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

Problem in Elliptic Curve Cryptography DSA

Ricardo_Costa — Sun, 22 May 2011 20:06:33 GMT

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

Problem in Elliptic Curve Cryptography DSA

Andrzej_Chrzeszczyk — Mon, 23 May 2011 02:12:19 GMT

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

Problem in Elliptic Curve Cryptography DSA

Ying_H_Intel — Wed, 25 May 2011 04:25:53 GMT

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.

Problem in Elliptic Curve Cryptography DSA

Andrzej_Chrzeszczyk — Wed, 25 May 2011 09:18:03 GMT

Hello Ying
Thanks

You mean of course ippsECCPSignDSA check stage

Andrzej Chrzeszczyk

Problem in Elliptic Curve Cryptography DSA

Ying_H_Intel — Thu, 08 Sep 2011 08:55:02 GMT

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