TODO: come up with todo list
see comments starting at https://bugs.libre-soc.org/show_bug.cgi?id=773#c1
if you want a known-good library to test against, you can use python3-cryptography, which uses openssl internally, and is available in debian buster (you will want that rather than installing it through pip). iirc, one or more of our repos has it as a dependency somewhere, icr for sure. https://cryptography.io/en/latest/hazmat/primitives/asymmetric/ed25519/
(In reply to Jacob Lifshay from comment #2) > if you want a known-good library to test against, you can use > python3-cryptography, which uses openssl internally, no. absolutely not. that, when added to the unit tests, becomes *yet another* dependency, including openssl. cryptography has a de-facto standard way of dealing with this problem for 30+ years: the author of the algorithm *provides a reference implementation* and in that reference implementation are included some "known examples". given that the probability of being wrong even when running just one single example is (2^128-1) / (2^128) for a 128-bit algorithm and (2^256-1) / (2^256) for a 256-bit one it is an absolute no-brainer to justify "success" on the basis of passing *even one* of the "known examples" provided by a c reference implementation. run two well-known examples and that becomes a probability of (2^128-1)^2 / (2^128)^2 please *do not* add yet more software dependencies when it is very simple to just find (and copy verbatim) the source code of the reference implementation and drop it straight into the crypto/ directory, exactly as konstantinos has *already done* with chacha20: https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=crypto/chacha20/src/test.c;hb=HEAD please let konstantinos get on with this task uninterrupted, and help review when he has made commits.
(In reply to Luke Kenneth Casson Leighton from comment #3) > given that the probability of being wrong even when running just one > single example is (2^128-1) / (2^128) for a 128-bit algorithm and > (2^256-1) / (2^256) for a 256-bit one it is an absolute no-brainer > to justify "success" on the basis of passing *even one* of the "known > examples" > provided by a c reference implementation. run two well-known examples > and that becomes a probability of (2^128-1)^2 / (2^128)^2 that assumes the crypto primitive was implemented correctly, the probability is much higher than that that the primitive is wrong for only some inputs. e.g. AES-128 uses at most 160 of the 256 S-box entries for any one encryption (each round has 16 S-box accesses, there are 10 rounds), so, assuming those are randomly distributed, for 2 AES-128 encryptions, only about 183 S-box entries are ever accessed, so if you have one wrong, you have about a 72% percent chance of detecting that. my code: import random def count_accessed(c): sbox = [False] * 256 for _ in range(c): sbox[random.randrange(256)] = True return sum(sbox) def wrong_accessed(c, w): for _ in range(c): if random.randrange(256) < w: return True return False # average number of S-box entries accessed for 2 encryptions: c = 10000; print(sum(count_accessed(160*2) for _ in range(c)) / c) # probability one wrong S-box entry will be accessed for 2 encryptions: c = 10000; print(sum(wrong_accessed(160*2, 1) for _ in range(c)) / c)
(In reply to Jacob Lifshay from comment #4) > that assumes the crypto primitive was implemented correctly, the probability > is much higher than that that the primitive is wrong for only some inputs. jacob! please do not interfere! Konstantinos has this covered and you are distracting him. i will not warn you again.
https://libre-soc.org/irclog/%23libre-soc.2023-09-14.log.html#t2023-09-14T10:45:15 konstantinos it is only necessary to run one test (or two) - those of the reference implementation's "known-good" values - just like with chacha20. it was and will always remain completely unnecessary to run for 49 minutes, the absolute maximum should be 3-5 minutes and even that is pushing it. could you also take the opportunity to remove the dependency on openssl, cutting back to the absolute bare-minimum stand-alone unit test, just like with chacha20? the project's requirements are that openpower-isa dependencies are kept to the absolute minimum (gtest was a sensible strategic addition), and openssl as a hard requirement is simply far too large and in this case unnecessary and unjustifiable. i appreciate that there is a desire to run the unit tests "as-is", however it is well beyond the scope of what is required: a *stand-alone* and bare-minimum demonstration
OpenSSL can be actually be removed easily, by using the builtin SHA512 hash function. Already fixed and will commit asap. That's the easy part. Regarding the tests, I'm going to implement smaller unit tests for the curve/ed25519 code and have already started preparing a separate unit test that will do just a single iteration. This will still take a long time -no way this is going to end in 3-5 minutes, but at least it will be a complete demonstration of SVP64 implementation ed25519.
(In reply to Konstantinos Margaritis (markos) from comment #7) > OpenSSL can be actually be removed easily, by using the builtin SHA512 hash > function. Already fixed and will commit asap. That's the easy part. fantastic (cf: git commit) https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=8d1160cf5 > Regarding the tests, I'm going to implement smaller unit tests for the > curve/ed25519 code and have already started preparing a separate unit test > that will do just a single iteration. brilliant. btw once we have the mdwn-to-c compiler in place and the c-based decoder it becomes possibe to wrap those in python and dramatically speed up ISACaller.
adding test function for curve25519_mul using barrett reduction / carry-save https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=8051365d9b8c
working version of python curve25519_mul https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=de10b86f7b3
from michiel: ---- Hi Luke, I'm going through this as we speak, and don't understand how the repo works here. In the OpenPower ISA repo, under /crypto I see a checkout of this code: https://github.com/floodyberry/ed25519-donna and I see some preliminary code in src/openpower/decoder/isa/ed25519/curve25519_mul.py but that is just a first sketch and doesn't work, right? Or does it, and is there a way we should test this? Best, Michiel
(In reply to Luke Kenneth Casson Leighton from comment #11) > from michiel: > > ---- > > Hi Luke, > > I'm going through this as we speak, and don't understand how the repo works > here. > > In the OpenPower ISA repo, under /crypto I see a checkout of this code: > > https://github.com/floodyberry/ed25519-donna the main function i converted from c to python, months go, and cut/paste it to lines 10-32. it is the key functuon, being a complete big-int multiply. > and I see some preliminary code in > src/openpower/decoder/isa/ed25519/curve25519_mul.py yes. no. not preliminary: sufficient complete and self-contained to prove the point. implementing Triangular REMAP is under a completely different grant if i recall correctly. > but that is just a first sketch and doesn't work, right? that's incorrect - just run it. lines 78-80 set up 5 "random" tests. > Or does it, and is there a way we should test this? python3 curve25519_mul.py it shows (lines 42 and 44, and 54 and 57) that a triangular REMAP in hardware would do auto-looping around a single instruction (multiply-and-add). that demonstrates that the entire loop(s) would each reduce down to three instructions, just like Matrix REMAP is only three instructions. and that makes for a massive reduction in code density.
assigned to 2021-02-052@nlnet.nl awaiting review QUESTIONS if any on this bugtracker to meet full transparency project requirements since inception for trust and audit purposes.