diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/FORMAT.md | 41 | ||||
| -rw-r--r-- | docs/IMPLEMENTATIONS.md | 34 | ||||
| -rw-r--r-- | docs/TESTS.md | 79 |
3 files changed, 99 insertions, 55 deletions
diff --git a/docs/FORMAT.md b/docs/FORMAT.md index bde2543..16af130 100644 --- a/docs/FORMAT.md +++ b/docs/FORMAT.md @@ -1,6 +1,14 @@ # Format ECTester mostly reads/outputs data in either human-readable format or using CSV. +## Test runs +By default test runs are output in a human readable format, however YAML and XML is also supported and can be selected +by using the `--format` option. Also, prefixing the output file name when using the `-o/--output` option allows to output +the same test run in different formats to different files. + +For example: +`--format yaml -o default_output.yaml -o xml:output_file.xml -o text:readable_text_file.txt ` + ## Curves Input files for the `-c/--curve` option should be in CSV, little-endian hexadecimal format. Output of the `-e/--export` option will also be in this format. @@ -42,22 +50,37 @@ Input files for the `-k/--key`, `-pub/--public` and `-priv/--private` options sh ## Key generation output(CSV) Output of the `-g/--generate` option. -`index;time;pubW;privS` +For ECTesterReader this has the format: + +`index;genTime[milli];exportTime[milli];pubW;privS` where `pubW` is the public key used in ANSI X9.62 format, +`privS` is the private key, `genTime` is the time required to generate the keypair and `exportTime` is the time required to export it (send it to the reader). + +For ECTesterStandalone: + +`index;time[nano];pubW;privS` ## KeyAgreement output(CSV) Output of the `-dh/--ecdh` option. -`index;time;pubW;privS;secret` +For ECTesterReader this has the format: + +`index;time[milli];pubW;privS;secret` where `pubW` is the public key used in ANSI X9.62 format, `privS` is the private key +and `secret` is the KeyAgreement result. + +For ECTesterStandalone this has the format: and the same meaning as for ECTesterReader. + +`index;time[nano];pubW;privS;secret` and the same meaning as for ECTesterReader. ## Signature output(CSV) Output of the `-dsa/--ecdsa` option. -`index;time;signature` +For ECTesterReader this has the format: -## Test runs -By default test runs are output in a human readable format, however YAML and XML is also supported and can be selected -by using the `--format` option. Also, prefixing the output file name when using the `-o/--output` option allows to output -the same test run in different formats to different files. +`index;signTime[milli];verifyTime[milli];data;pubW;privS;signature;nonce;valid` where `pubW` is the public key used +in ANSI X9.62 format, `privS` is the private key, `signTime` and `verifyTime` are the durations of the sign and verify operations, +`data` is the signed data (if available), `signature` is the produced signature, `nonce` is the `k` (nonce) value recovered from the signature +abd the private key (if possible), `valid` denotes the verification result. -For example: -`--format yaml -o default_output.yaml -o xml:output_file.xml -o text:readable_text_file.txt ` +For ECTesterStandalone this has the format: + + `index;signTime[nano];verifyTime[nano];data;pubW;privS;signature;nonce;verified` and the same meaning as for ECTesterReader.
\ No newline at end of file diff --git a/docs/IMPLEMENTATIONS.md b/docs/IMPLEMENTATIONS.md index b4a4ea8..d333ed5 100644 --- a/docs/IMPLEMENTATIONS.md +++ b/docs/IMPLEMENTATIONS.md @@ -249,7 +249,7 @@ Uses binary addition chain. INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). OUTPUT: [k]P. 1. Q ← ∞. - 2. For i from t - 1 downto 0 do + 2. For i from 0 to t-1 do 2.1 If k_i = 1 then Q ← Q + P. 2.2 P ← 2P. 3. Return(Q). @@ -432,7 +432,7 @@ The same name, Montgomery ladder, is used both for the general ladder idea of ex INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). OUTPUT: [k]P . 1. P_1 ← P and P_2 ← [2]P - 2. For i = t − 2 downto 0 do + 2. For i = t − 1 downto 0 do 2.1 If k_i = 0 then P_1 ← [2]P_1; P_2 ← P_1 + P_2. Else @@ -443,13 +443,13 @@ The same name, Montgomery ladder, is used both for the general ladder idea of ex INPUT: G ∈ E(F_q), k = (1, k_{t−2}, ..., k_0)2 OUTPUT: Y = kG - R0 ← G; R1 ← [2]G - for j = t − 2 downto 0 do - if (k_j = 0) then - R1 ← R0 + R1; R0 ← [2]R0 - else [if (kj = 1)] - R0 ← R0 + R1; R1 ← [2]R1 - return R0 + 1. R0 ← G; R1 ← [2]G + 2. for j = t − 2 downto 0 do + 2.1 if (k_j = 0) then + R1 ← R0 + R1; R0 ← [2]R0 + else [if (kj = 1)] + R0 ← R0 + R1; R1 ← [2]R1 + 3. return R0 Montgomery addition formulas (Projective coordinates/XZ coordinates):[^2] @@ -536,17 +536,27 @@ y_n &= \frac{(x_n + x_1)((x_n + x_1)(x_{n+1} + x_1) + x_1^2 + y_1)}{x_1} + y_1 ## References [^1]: HANKERSON, Darrel; MENEZES, Alfred J.; VANSTONE, Scott. Guide to Elliptic Curve Cryptography. New York, USA: Springer, 2004. ISBN 9780387218465. Available from DOI: [10.1007/b97644](https://dx.doi.org/10.1007/b97644). -[^2]: COHEN, Henri; FREY, Gerhard; AVANZI, Roberto M.; DOCHE, Christophe; LANGE, -Tanja; NGUYEN, Kim; VERCAUTEREN, Frederik. Handbook of Elliptic and Hyper- -elliptic Curve Cryptography. CRC Press, 2005-07-19. Discrete Mathematics and It’s Applications, no. 34. ISBN 9781584885184. + +[^2]: COHEN, Henri; FREY, Gerhard; AVANZI, Roberto M.; DOCHE, Christophe; LANGE, Tanja; NGUYEN, Kim; VERCAUTEREN, Frederik. Handbook of Elliptic and Hyper-elliptic Curve Cryptography. CRC Press, 2005-07-19. Discrete Mathematics and It’s Applications, no. 34. ISBN 9781584885184. + [^3]: BERNSTEIN, Daniel J.; LANGE, Tanja. Explicit Formulas Database, <https://www.hyperelliptic.org/EFD/> + [^4]: <http://point-at-infinity.org/ecc/> + [^5]: KNUTH, Donald: The Art of Computer Programming, Volume 2: Seminumerical algorithms + [^6]: GORDON, Daniel M.: A survey of fast exponentiation methods. + [^7]: MORAIN, Francois; OLIVOS, Jorge: Speeding up the computations on an elliptic curve using addition-subtraction chains. + [^8]: JOYE, Marc; YEN, Sung-Ming: The Montgomery Powering Ladder. + [^9]: MOLLER, Bodo: Securing Elliptic Curve Point Multiplication against Side-Channel Attacks. + [^10]: MOLLER, Bodo: Improved Techniques for Fast Exponentiation. + [^11]: MOLLER, Bodo: Fractional Windows Revisited: Improved Signed-Digit Representations for Efficient Exponentiation. + [^12]: KOYAMA, Kenji; TSURUOKA, Yukio: Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method. + [^13]: GALLANT, Robert P.; LAMBERT, Robert J.; VANSTONE, Scott A.: Faster point multiplication on elliptic curves with efficient endomorphisms.
\ No newline at end of file diff --git a/docs/TESTS.md b/docs/TESTS.md index 25f61a8..5d32d9d 100644 --- a/docs/TESTS.md +++ b/docs/TESTS.md @@ -17,7 +17,7 @@ confirmation before running, be cautious.** ## Default -Tests the default curves present on the card. These might not be present or the card might not even support ECC. +Tests support for ECC and the presence of default curves on the target. These might not be present or the target might not even support ECC. Tests keypair allocation, generation, ECDH and ECDSA. ECDH is first tested with two valid generated keypairs, then with a compressed public key to test support for compressed points. @@ -25,7 +25,7 @@ This test suite is run if no argument is provided to `-t / --test`. ## Test-Vectors -Tests using known test vectors provided by NIST/SECG/Brainpool: +Tests ECDH using known test vectors provided by NIST/SECG/Brainpool: [SECG - GEC2](http://read.pudn.com/downloads168/doc/772358/TestVectorsforSEC%201-gec2.pdf) @@ -37,8 +37,12 @@ Tests using known test vectors provided by NIST/SECG/Brainpool: ## Compression -Tests support for compression of public points in ECDH as specified in ANSI X9.62. Tests ECDH with points in compressed -and hybrid form. Also tests card response to a hybrid point with wrong `y` coordinate and to the point at infinity(as public key in ECDH). +Tests support for compression of public points in ECDH as specified in ANSI X9.62. The standard specifies two forms of point compression, +fully compressed point contains the `x` coordinate and one bit of the `y` coordinate, from which the whole point can be reconstructed, hybrid form +of a compressed point contains both the `x` and `y` coordinates but also one bit of the `y` coordinate. + +Tests ECDH with points in compressed and hybrid form. Also tests target response to a hybrid point with wrong `y` coordinate and to the point at infinity(as public key in ECDH). +Tests ECDH with invalid compressed point, where `x` does not lie on the curve. - Compressed form, valid - Hybrid form, valid @@ -48,29 +52,35 @@ and hybrid form. Also tests card response to a hybrid point with wrong `y` coord ## Miscellaneous -Some miscellaneous tests, tries ECDH and ECDSA over supersingular curves, anomalous curves and Barreto-Naehrig curves with small embedding degree and CM discriminant. +Some miscellaneous tests, tries ECDH and ECDSA over super-singular curves, anomalous curves and Barreto-Naehrig curves with small embedding degree and CM discriminant. +Also tests ECDH over MNT curves, M curves and Curve25519 transformed into short Weierstrass form. ## Signature -Tests ECDSA verification, with invalid signatures. +Tests ECDSA verification, with well-formed but invalid and malformed signatures. - - Well-formed(DER) invalid signatures: - - r = random, s = random - - r = 0, s = random - - r = random, s = 0 - - r = 1, s = random - - r = random, s = 1 - - r = 0, s = 0 - - r = 0, s = 1 - - r = 1, s = 0 - - r = 1, s = 1 - - s = p - - s = 2 * p - - Invalid signatures: - - Signature shorter than specified in ASN.1 SEQUENCE header. - - Signature longer than specified in ASN.1 SEQUENCE header. - - r shorter/longer than specified in its ASN.1 header. - - s shorter/longer than specified in its ASN.1 header. +- Well-formed(DER) invalid signatures: + - r = random, s = random + - r = 0, s = random + - r = random, s = 0 + - r = 1, s = random + - r = random, s = 1 + - r = 0, s = 0 + - r = 0, s = 1 + - r = 1, s = 0 + - r = 1, s = 1 + - r = random, s = p + - r = random, s = 2 * p +- Invalid signatures: + - Signature shorter than specified in ASN.1 SEQUENCE header. + - Signature longer than specified in ASN.1 SEQUENCE header. + - r shorter/longer than specified in its ASN.1 header. + - s shorter/longer than specified in its ASN.1 header. + - ASN.1 SEQUENCE has indefinite length. + - ASN.1 SEQUENCE has length that will overflow a 16 bit integer. + - ASN.1 SEQUENCE has length that will overflow a 32 bit integer. + - ASN.1 SEQUENCE has length that will overflow a 64 bit integer. +- Test verifying a valid signature, but with a negated public key. ## Wrong @@ -91,9 +101,9 @@ This test suite also does some additional tests with corrupting the parameters: - G = infinity - r = 0 - r = 1 - - r = some prime larger than original r (and \[r\]G != infinity) - - r = some prime smaller than original r (and \[r\]G != infninity) - - r = some composite number (and \[r\]G != infinity) + - r = some prime larger than original r (and [r]G != infinity) + - r = some prime smaller than original r (and [r]G != infninity) + - r = some composite number (and [r]G != infinity) - k = 0xff - k = 0 @@ -104,7 +114,7 @@ This test suite also does some additional tests with corrupting the parameters: ## Composite Tests using curves that don't have a prime order/nearly prime order. -These tests should generally fail, a success here implies the card will use a non-secure curve if such curve is set +These tests should generally fail, a success here implies the target will use a non-secure curve if such curve is set by the applet. Operations over such curves are susceptible to small-subgroup attacks. - r = quite a smooth number, many small factors, r = \|G\| @@ -113,37 +123,37 @@ by the applet. Operations over such curves are susceptible to small-subgroup att This is performed over a 160 bit field size, in two passes: - First pass tests the full range from 2 bits to 152, with more frequent tests towards the beginning and end. - The second pass tests the range 140 - 158 bits with one bit steps. - + - r = p * q = \|G\| - r = G = Carmichael number = p * q * s - - \[r\]G = infinity but r != \|G\|, so \|G\| divides r + - [r]G = infinity but r != \|G\|, so \|G\| divides r ## Invalid Tests using known named curves from several categories(SECG/NIST/Brainpool) against pre-generated *invalid* public keys. -ECDH should definitely fail, a success here implies the card is susceptible to invalid curve attacks. +ECDH should definitely fail, a success here implies the target is susceptible to invalid curve attacks. See [Practical Invalid Curve Attacks on TLS-ECDH](https://www.nds.rub.de/media/nds/veroeffentlichungen/2015/09/14/main-full.pdf) for more information. ## Twist Tests using known named curves froms several categories(SECG/NIST) against pre-generated points on twists of said curves. -ECDH should fail, a success here implies the card is not twist secure, if a curve with an unsecure twist is used, -the card might compute on the twist, if a point on the twist is supplied. +ECDH should fail, a success here implies the target is not twist secure, if a curve with an unsecure twist is used, +the target might compute on the twist, if a point on the twist is supplied. See [SafeCurves on twist security](https://safecurves.cr.yp.to/twist.html) for more information. ## Degenerate Tests using known named curves froms several categories(SECG/NIST) against pre-generated points on the degenerate line -`Y: x = 0`. ECDH should fail, a success here might mean the card does not check that the point lies on the correct curve +`Y: x = 0`. ECDH should fail, a success here might mean the target does not check that the point lies on the correct curve and uses a curve model vulnerable to such degenerate points. See [Degenerate Curve Attacks - Extending Invalid Curve Attacks to Edwards Curves and Other Models](https://eprint.iacr.org/2015/1233.pdf) for more information. ## Cofactor -Tests whether the card correctly rejects points that lie on the curve but not on the subgroup generated by the specified generator +Tests whether the target correctly rejects points that lie on the curve but not on the subgroup generated by the specified generator during ECDH. Does this with curves where the cofactor subgroup has small order, then with curves that have order equal to the product of two large primes, sets the generator with order of one prime and tries points on the subgroup of the other prime order. @@ -166,6 +176,7 @@ Custom edge-case private key values over SECG curves are tested: - s < r, s = r, s > r - s = r - 1, s = r + 1 - s = k\*r - 1, s = k\*r, s = k\*r + 1 + - s = 111111...1111, s = 101010...1010, s = 010101...0101 - s around r (s < r, on a curve where \|r\| > \|p\|) - s around p (on a curve where where \|r\| > \|p\|) - s around 0 (s > 0, on a curve where \|r\| > \|p\|) |