Take stock of all algorithms #892
Comments
|
Here is a draft of a YML file showing the information to be collected about an algorithm and its implementations. name: FrodoKEM
type: kem
principal-submitters:
- Michael Naehrig
- Erdem Alkim
- Joppe Bos
- Léo Ducas
- Karen Easterbrook
- Brian LaMacchia
- Patrick Longa
- Ilya Mironov
- Valeria Nikolaenko
- Christopher Peikert
- Ananth Raghunathan
- Douglas Stebila
auxiliary-submitters: []
crypto_assumption: learning with errors (LWE)
website: https://frodokem.org/
nist-round: 3
variants:
- name: FrodoKEM-640-AES
claimed-nist-level: 1
claimed-security: IND-CCA2
length-public-key: 9616
length-ciphertext: 9720
length-secret-key: 19888
length-shared-secret: 16
supported_configurations:
-
platforms: [Linux x86, macOS x86, Windows x86]
builds:
- build: portable
comments: portable C with optional use of AVX2 and AESNI instructions (selected at compile-time, enabled by default if available)
cpu_features: [AVX2, AESNI]
common_crypto:
- AES: liboqs
- SHA2: liboqs
implementation: based on https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db optimized implementation
no_secret_dependent_branching_claimed: true
no_secret_dependent_branching_checked_by_valgrind: true
large_stack_usage: false (this is where we might say an algorithm has large stack usage and may cause failures when run in threads)
- build: non-portable with AVX2 and AESNI
comments: portable C with use of AVX2 and AESNI instructions
cpu_features: [AVX2, AESNI]
common_crypto:
- AES: liboqs
- SHA2: liboqs
implementation: based on https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db optimized implementation
no_secret_dependent_branching_claimed: true
no_secret_dependent_branching_checked_by_valgrind: true
large_stack_usage: false
- build: non-portable without AVX2 or AESNI
comments: portable C
cpu_features: [AVX2, AESNI]
common_crypto:
- AES: liboqs
- SHA2: liboqs
implementation: based on https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db optimized implementation
no_secret_dependent_branching_claimed: true
no_secret_dependent_branching_checked_by_valgrind: true
large_stack_usage: false
-
platforms: [Linux ARM]
builds:
- build: all
comments: portable C
cpu_features: []
common_crypto:
- AES: liboqs
- SHA2: liboqs
implementation: based on https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db optimized implementation
no_secret_dependent_branching_claimed: true
no_secret_dependent_branching_checked_by_valgrind: true
large_stack_usage: false |
|
Thanks for this first cut. First questions:
|
The concrete requirement here was "have we observed it crashing in multi-threaded tests in the language wrappers"?
Not systematically, just inspired by.
This was intended to keep track that we've updated to the Round 3 version. |
|
Beyond the already answered questions above, do we safely assume that each algorithm is using common RAND? Should we have a test to validate that? Looking at other common code, is it correct that Frodo unlike other algorithms doesn't use SHA3 (incl. SHA3x4)? Last question: Do we agree that the If so, I'd support using/filling this template for all algorithms (and release 0.5 when all algs have the |
|
Looks very good. Is the goal to use these files also for a direct upstream-import of the implementations? If so it can make sense to unify some of the structure and naming (e.g. "implementations" vs. "supported_configurations", the way to encode the supported platforms). Compare for example here: https://github.com/pq-crystals/dilithium/blob/master/Dilithium2_META.yml Additional information that can be useful:
Is it x86 or x86_64?
Similar here, do we want to detail the ARM architecture (aarch64, armhf, armel, ..)? |
I hadn't thought to check if people are using something other than common RAND. I'm not aware of anyone doing that in the algorithms we have. Not sure how we'd validate that automatically though.
Oops, all Frodo variants do use SHA3, not SHA2; the -SHAKE variants just use it more. Will have to fix. And yes, hopefully this will resolve #849. |
The initial goal was to provide an organized summary of the implementations characteristics, for people to understand what we have and to generate relevant documentation/tables. It was not an immediate goal to tie in with the copy-from-upstream mechanism; I was worried that expanding the scope too far would mean it never gets done.
Okay if we imagine this to be used for automatically connecting with code; less necessary if we imagine this is oriented around documentation (since those KATs are already present in the same commit elsewhere in the liboqs repo).
Specifically?
To me that's more of an output characteristic, something that would e.g. be measured using profiling, rather than reported on a specification document like this one.
Yes, that is a good point. |
+1. Also, such properties are compiler&platform dependent. @bhess If you're not aware of it, you may want to head over to https://openquantumsafe.org/benchmarking/visualization/mem_sig_series.html (where you can --among many other options-- toggle between maxHeap and maxStack usage comparisons) to take a look at what we already have. Suggestions for improvements always welcome. Oh, and
are also captured there. |
|
What about changing the build_configurations:
x86-64:
-
type: portable
comments: portable C with optional use of AVX2 and AESNI instructions (selected at compile-time, enabled by default if available)
platforms: [Linux, macOS, Windows]
cpu_features: [AVX2, AESNI]
common_crypto:
- AES: liboqs
- SHA2: liboqs
implementation: based on https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db optimized implementation
no_secret_dependent_branching_claimed: true
no_secret_dependent_branching_checked_by_valgrind: true
large_stack_usage: false (this is where we might say an algorithm has large stack usage and may cause failures when run in threads)
-
type: non-portable with AVX2 and AESNI
comments: non-portable C with use of AVX2 and AESNI instructions
cpu_features: [AVX2, AESNI]
platforms: [Linux, macOS, Windows]
common_crypto:
- AES: liboqs
- SHA2: liboqs
implementation: based on https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db optimized implementation
no_secret_dependent_branching_claimed: true
no_secret_dependent_branching_checked_by_valgrind: true
large_stack_usage: false
armhf:
-
type: portable
platforms: [Linux]
comments: portable C
cpu_features: []
common_crypto:
- AES: liboqs
- SHA2: liboqs
implementation: based on https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db optimized implementation
no_secret_dependent_branching_claimed: true
no_secret_dependent_branching_checked_by_valgrind: true
large_stack_usage: false
armel:
.... |
|
That seems fine to me, @xvzcf. |
|
Last remaining issue before releasing 0.6, right? Would it be an idea to complete a release of liboqs and all subprojects before the end of May/PQC workshop? For 0.5 it took us a month to move from RC on liboqs until final release of all subprojects... Thus, what about focusing on/closing this now and having a liboqs-0.6 RC by the end of April? |
|
Greed. @xvzcf have you made any progress on generating documentation from the sample YML file? |
No, will look at it today. |
|
Here's the slightly reworked YAML: name: FrodoKEM
type: kem
principal-submitters:
- Michael Naehrig
- Erdem Alkim
- Joppe Bos
- Léo Ducas
- Karen Easterbrook
- Brian LaMacchia
- Patrick Longa
- Ilya Mironov
- Valeria Nikolaenko
- Christopher Peikert
- Ananth Raghunathan
- Douglas Stebila
auxiliary-submitters: []
crypto-assumption: learning with errors (LWE)
website: https://frodokem.org/
nist-round: 3
spec-version: NIST Round 3 submission
spdx-license-identifier: MIT
implementation-chain:
- SAMPLE_URL_LEAF
- SAMPLE_URL_INT
- https://github.com/microsoft/PQCrypto-LWEKE/commit/669522db63850fa64d1a24a47e138e80a59349db
implementation-type: optimized
parameter-sets:
-
name: FrodoKEM-640-AES
claimed-nist-level: 1
claimed-security: IND-CCA2
length-public-key: 9616
length-ciphertext: 9720
length-secret-key: 19888
length-shared-secret: 16
implementations:
-
arch: x86-64
portable: yes
platforms: [Linux, macOS, Windows]
cpu-extensions-used: [AVX2, AESNI]
common-crypto:
- AES: liboqs
- SHA2: liboqs
no-secret-dependent-branching-claimed: true
no-secret-dependent-branching-checked-by-valgrind: true
large-stack-usage: false
-
arch: armel
portable: no
cpu-extensions-used: []
platforms: [Linux, macOS, Windows]
common-crypto:
- AES: liboqs
- SHA2: liboqs
no-secret-dependent-branching-claimed: true
no-secret-dependent-branching-checked-by-valgrind: true
large-stack-usage: false
-
arch: armhf
portable: yes
platforms: [Linux]
cpu-extensions-used: []
common-crypto:
- AES: liboqs
- SHA2: liboqs
no-secret-dependent-branching-claimed: true
no-secret-dependent-branching-checked-by-valgrind: true
large-stack-usage: falseand the associated documentation markdown: FrodoKEM
Parameter set summary
Link to memory consumption benchmark: https://openquantumsafe.org/benchmarking/visualization/mem_kem.html#refselector=Performance&familyselector=Frodo FrodoKEM-640-AES implementation characteristics
Explanation of terms
|
|
@open-quantum-safe/core thoughts? |
|
Looks basically OK to me. Suggestions for improvement: What about putting this link behind the truth value concerning "Large stack usage": https://openquantumsafe.org/benchmarking/visualization/mem_kem.html ? May avoid discussions what constitutes "large" with clear figures. Also, would it be reasonable to add "in optimized implementation" behind the "CPU Extensions Used" heading (or a footnote -- to document there's both optimized and reference code available; the latter of which arguably always is portable). |
|
I'd be more inclined to put the link in the explanation section (unless there's a link to display numbers only for a specific implementation of choice on that page) For the latter, I'll edit my comment above to add an
|
That's a good feature idea for profiling visualization. Now so implemented: If open-quantum-safe/profiling#54 is landed you can direct link to specific algorithms and implementations, e.g. https://openquantumsafe.org/benchmarking/visualization/mem_kem.html#refselector=Performance&familyselector=Frodo |
|
@xvzcf Linking to specific profiling pages/algs now works as advertised above. Could we now finalize this (and put the resultant docs into 0.6.0)? |
I've updated the markdown to include a link to the benchmark (under the parameter set summary section). |
|
I've put the example YML file for FrodoKEM in a new-datasheets branch in the docs/algorithms/kem folder. It's ready for other people to adapt for other schemes. As promised, here are the assignments. Please try to do this within the next week, you can push directly to the new-datasheets branch. If you have any problems / questions, please ask on here. KEMs:
Signatures:
|
|
OK for me to take on HQC and Rainbow. Question(s) on FrodoKEM: Is that really complete/correct?
liboqs/docs/algorithms/kem/frodokem.yml Line 44 in bac7c59
Finally, am I assuming correct that we don't explicitly/separately list reference implementation(s) -- unless no optimized variant is available? |
|
Additional question regarding secret dependent branching: Do I assume correct that we shall state One could argue that the claim to this property is made by the authors, though, as the NIST submission states "Our optimized AVX2 implementation is now constant time and avoids secret dependent memory access" (in my eyes code branches are --code-- memory accesses). Given this, these bits now confuse me a bit: Could @xvzcf @jschanck @dstebila please provide guidance/a link as to how to set these truth values? |
You're right, fixed; thanks.
That's just so you all can see the syntax, will be removed for Frodo eventually since Frodo doesn't need them.
Yes. |
I'd say we should put a link to the suppression file indicating the exceptions. |
How/where? Also, please note that in the case of HQC it's 3 files. Until that's clear, I'll consider HQC done: Please take a look. If you'd want me to extend the YAML->MD converter, please let me know where that code is (@xvzcf ? Didn't find it in |
|
Regarding HQC: How about I open an issue describing the non-constant time behaviour that is documented in the suppression files, and then we link to the issue. |
|
Added a yml file for Dilithium. A few minor comments: For The Frodo yml lists macOS and Windows as target platforms for armel and armhf. Isn't it just Linux (or perhaps macOS because of M1)? liboqs/docs/algorithms/kem/frodokem.yml Line 40 in 46cc308 liboqs/docs/algorithms/kem/frodokem.yml Line 52 in 46cc308 The Frodo yml lists "armel" as not portable. Is this correct? liboqs/docs/algorithms/kem/frodokem.yml Line 50 in 46cc308
For SIKE, I believe that the issues were resolved after #914. @christianpaquin @jschanck Could the two SIKE-related files be removed from here? https://github.com/open-quantum-safe/liboqs/tree/main/tests/constant_time/kem/issues.
There is some code to partially generate the .md files after copy_from_upstream: https://github.com/open-quantum-safe/liboqs/tree/main/scripts/copy_from_upstream/docs/algorithms. This should be obsolete after completing this here, but it could serve as a template for generating .md files from the new yml-files. |
My aim here was that these would just be (possibly opaque) identifiers that just make it possible to look up what "flavor" we pulled from the upstream code (if the upstream has three implementations
I did not check whether the values were correct, just copy-pasted to hash out what the general YAML file would look like.
I'll paste the quick-and-dirty script I wrote to generate the markdown files in a separate comment. I think we'll have to ensure consistency between the information in these new YAML files and, for example, copy_from_upstream.yml (such as making sure the |
|
The python script I used: #!/usr/bin/env python3
import argparse
import sys
from tabulate import tabulate
import yaml
import os
config = {}
with open('frodokem.yml', mode='r', encoding='utf-8') as f:
config = yaml.safe_load(f.read())
with open('frodokem-new-sample.md', mode='w', encoding='utf-8') as f:
f.write('# {}\n\n'.format(config['name']))
f.write('- **Algorithm type**: key encapsulation mechanism\n')
f.write('- **Main cryptographic assumption**: {}.\n'.format(config['crypto-assumption']))
f.write('- **Authors website**: {}.\n'.format(config['website']))
f.write('- **Specification version**: {}.\n'.format(config['spec-version']))
f.write('- **Implementation**: {} version from:\n'.format(config['implementation-type']))
for url in config['implementation-chain'][:-1]:
f.write(' - {}, which takes it from\n'.format(url))
f.write(' - {}\n'.format(config['implementation-chain'][-1]))
f.write('- **Implementation type**: {}\n'.format(config['implementation-type']))
f.write('- **License (SPDX-Identifier)**: {}.\n'.format(config['spdx-license-identifier']))
f.write('\n## Parameter set summary\n\n')
table = [['Parameter set',
'Security Model',
'Claimed NIST Level',
'Public key size (bytes)',
'Secret key size (bytes)',
'Ciphertext size (bytes)',
'Shared secret size (bytes)']]
for parameter_set in config['parameter-sets']:
table.append([parameter_set['name'],
parameter_set['claimed-security'],
parameter_set['claimed-nist-level'],
parameter_set['length-public-key'],
parameter_set['length-secret-key'],
parameter_set['length-ciphertext'],
parameter_set['length-shared-secret']])
f.write(tabulate(table, tablefmt="pipe", headers="firstrow", colalign=("center",)))
f.write('\n')
for parameter_set in config['parameter-sets']:
f.write('\n## {} implementation characteristics\n\n'.format(parameter_set['name']))
table = [['Architecture',
'Platforms',
'CPU Extensions Used',
'Portable?',
'No branching-on-secrets claimed?',
'No branching-on-secrets checked by valgrind?',
'Large stack usage?']]
for impl in parameter_set['implementations']:
table.append([impl['arch'],
''.join(p + ',' for p in impl['platforms']),
''.join(e + ',' for e in impl['cpu-extensions-used']),
impl['portable'],
impl['no-secret-dependent-branching-claimed'],
impl['no-secret-dependent-branching-checked-by-valgrind'],
impl['large-stack-usage']])
f.write(tabulate(table, tablefmt="pipe", headers="firstrow", colalign=("center",)))
f.write('\n')
f.write('\n## Explanation of terms\n\n')
f.write('- Large stack usage: INSERT_EXPLANATION_HERE') |
|
Since we are pushing 0.6, I took the liberty of delaying my assigned algs to next week, to address urgent deadlines this week. Hoping to get to this before our next meeting. |
|
How are we supposed to answer questions fields that vary depending on platform support. For example, for SIKE, some optimizations are available on Linux and Darwin, but the build will revert to the portable version on Windows. Should I duplicate the arch entry: or should I combined both: There are already 4 (params) x 2 (SIDH/SIKE) x 2 (compressed or not) = 16 variants for SIKE, each with 4 archs, so I'm weary of adding another split. |
|
Go with duplicating for now, that way you can describe which combinations of arch/platform have which properties more precisely. |
|
I added NTRU and Kyber. Some questions: What is the top-level "implementation type" field for? This feels like it should be under parameter-sets/implementations, if it's necessary at all. liboqs/docs/algorithms/kem/frodokem.yml Line 26 in 3874c1f Does "portable" mean the implementation can be selected at runtime? If so, maybe change the name of the field to something like "dynamic-dispatch". liboqs/docs/algorithms/kem/frodokem.yml Lines 38 to 41 in 3874c1f I've used "arch: any" / "platforms: any" for plain C. Is this OK? liboqs/docs/algorithms/kem/ntru.yml Lines 47 to 49 in 3874c1f |
|
Resolved for KEMs by #1030. Equivalent PR for signatures will close this issue. |
|
Closed by #1053 |
This issue to capture what we discussed today (also for the benefit of @christianpaquin):
@dstebila @xvzcf are working on this.
The text was updated successfully, but these errors were encountered: