Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

FFI version of SuiteB AES functions #1398

Closed
qsctr opened this issue Aug 12, 2022 · 4 comments · Fixed by #1416
Closed

FFI version of SuiteB AES functions #1398

qsctr opened this issue Aug 12, 2022 · 4 comments · Fixed by #1416
Assignees
Labels
FFI Foreign function interface

Comments

@qsctr
Copy link
Contributor

qsctr commented Aug 12, 2022

As a demo for the FFI, implement a drop-in replacement for the builtin SuiteB module that uses the FFI instead of Cryptol and Haskell primitives, and see if it results in a speedup in code like this.

@qsctr qsctr added the FFI Foreign function interface label Aug 12, 2022
@qsctr qsctr self-assigned this Aug 16, 2022
@qsctr
Copy link
Contributor Author

qsctr commented Aug 30, 2022

I ended up implementing this with AES-NI in #1416, but I also have an implementation of just the AES-128 key expansion and encryption functions using the tiny-AES-c library in the ffi-aes branch. I didn't end up using it because the way it does decryption and other key sizes doesn't really map well to the SuiteB interface, and I didn't find any other C libraries that had the interface I wanted, so I used AES-NI directly.

@weaversa
Copy link
Collaborator

weaversa commented Sep 1, 2022

@qsctr Here's one I did using openssl's sha384 implementation -- https://github.com/weaversa/cryptol-ffi-tests. I'm wondering why it's so slow? I have a 2meg file (just random data) and Cryptol reads it in immediately (:readByteArray). It's the same shape as the foreign function type. However, it takes a long time for a result to come back. I saw your comment that your AES-NI should go fast if all the data was presented at once, which is what I thought I did here --where's the slowdown happening?

@qsctr
Copy link
Contributor Author

qsctr commented Sep 1, 2022

I think when you do :readByteArray the file is read immediately but the Cryptol sequence is evaluated lazily, and the evaluation is implemented in an inefficient way (it seems like it just turns the bytes into a huge number and calls split on it) so it takes a long time to even just evaluate the result of :readByteArray. I just did deepseq it () right after :readByteArray and it took about 5 minutes to run.

@qsctr
Copy link
Contributor Author

qsctr commented Sep 6, 2022

Ok, after further investigation it seems like processing the result of :readByteArray takes quadratic time in the size of the file, see #1428 for more details. Furthermore, forcing the result and then using it doesn't help, because it doesn't change the underlying representation of the sequence and every time you traverse through it it will be quadratic. So to actually test the performance of sha384 I passed the result of :readByteArray through this foreign function

foreign id : {n} [n][8] -> [n][8]
void id(size_t len, uint8_t *in, uint8_t *out) {
    for (size_t i = 0; i < len; ++i) {
        out[i] = in[i];
    }
}

which essentially rebuilds the sequence in an optimized way, where it stores the actual values so lookup is constant time instead of linear time. Then running sha384 on the result of that took less than a second on my computer.

@yav yav closed this as completed in #1416 Sep 14, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
FFI Foreign function interface
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants