Intel® Integrated Performance Primitives
Deliberate problems developing high-performance vision, signal, security, and storage applications.

Problem in Elliptic Curve Cryptography DSA

Ricardo_Costa
Beginner
767 Views

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.
0 Kudos
1 Solution
Andrzej_Chrzeszczyk
New Contributor I
767 Views
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

View solution in original post

0 Kudos
7 Replies
Joseph_S_Intel
Employee
767 Views
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
0 Kudos
Andrzej_Chrzeszczyk
New Contributor I
768 Views
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
0 Kudos
Ricardo_Costa
Beginner
767 Views
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
0 Kudos
Andrzej_Chrzeszczyk
New Contributor I
767 Views
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
0 Kudos
Ying_H_Intel
Employee
767 Views
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.

0 Kudos
Andrzej_Chrzeszczyk
New Contributor I
767 Views
Hello Ying
Thanks

You mean of course ippsECCPSignDSA check stage

Andrzej Chrzeszczyk
0 Kudos
Ying_H_Intel
Employee
767 Views

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

0 Kudos
Reply