-
Notifications
You must be signed in to change notification settings - Fork 7
/
README.txt
155 lines (118 loc) · 6.7 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
DETERMINISTIC FALCON IMPLEMENTATION
===================================
Version: 2021-12-03
Falcon is a post-quantum signature algorithm, submitted to NIST's
Post-Quantum Cryptography project:
https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
Falcon is based on NTRU lattices, used with a hash-and-sign structure
and a Fourier-based sampling method that allows efficient signature
generation and verification, while producing and using relatively
compact signatures and public keys. The official Falcon Web site is:
https://falcon-sign.info/
This implementation slightly extends the official Falcon code to
support a fully deterministic (or "derandomized") signing mode; the
interface is given in deterministic.h. (This is an alternative to the
randomized-hashing mode enabled by the original implementation.) For
the motivation for, and specification of, the deterministic mode, see
falcon-det.pdf .
This implementation is written in C and is configurable at compile
time through macros which are documented in config.h; each macro is a
boolean option and can be enabled or disabled in config.h and/or as a
command-line parameter to the compiler. Several implementation
strategies are available; however, in all cases, the same API is
implemented.
*** CRITICAL SECURITY WARNING ***
For robust determinism across supported devices, which is needed to
prevent a potential catastrophic security failure in the deterministic
mode, it is STRONGLY RECOMMENDED that the following macro settings be
used, as is done in config.h (see that file for further details):
- floating-point emulation (FALCON_FPEMU) should be enabled, in lieu
of native FP operations.
- "fused multiply-add" (FALCON_FMA) should be disabled, *especially*
if native FP operations are enabled.
- other optimizations like FALCON_AVX2 and FALCON_ASM_CORTEXM4
should be disabled as a cautionary measure, unless they are needed
for performance and can be thoroughly checked to not affect
determinism on the relevant signing devices.
(According to the documentation below, FALCOM_FMA and FALCON_AVX2 have
no effect when FALCON_FPEMU is enabled, but in config.h they are
explicitly disabled as a defensive measure.)
*** END CRITICAL SECURITY WARNING ***
Main options are the following:
- FALCON_FPNATIVE and FALCON_FPEMU
If using FALCON_FPNATIVE, then the C 'double' type is used for all
floating-point operations. This is the default. This requires the
'double' type to implement IEEE-754 semantics, in particular
rounding to the exact precision of the 'binary64' type (i.e. "53
bits"). The Falcon implementation takes special steps to ensure
these properties on most common architectures. When using this
engine, the code _may_ need to call the standard library function
sqrt() (depending on the local architecture), which may in turn
require linking with a specific library (e.g. adding '-lm' to the
link command on Unix-like systems).
FALCON_FPEMU does not use the C 'double' type, but instead works
over only 64-bit integers and embeds its own emulation of IEEE-754
operations. This is slower but portable, since it will work on any
machine with a C99-compliant compiler.
- FALCON_AVX2 and FALCON_FMA
FALCON_AVX2, when enabled, activates the use of AVX2 compiler
intrinsics. This works only on x86 CPU that offer AVX2 opcodes.
Use of AVX2 improves performance. FALCON_AVX2 has no effect if
FALCON_FPEMU is used.
FALCON_FMA further enables the use for FMA ("fused multiply-add")
compiler intrinsics for an extra boost to performance. This
setting is ignored unless FALCON_FPNATIVE and FALCON_AVX2 are
both used. Occasionally (but rarely), use of FALCON_FMA will
change the keys and/or signatures generated from a given random
seed, impacting reproducibility of test vectors; however, this
has no bearing on the security of normal usage.
- FALCON_ASM_CORTEXM4
When enabled, inline assembly routines for FP emulation and SHAKE256
will be used. This will work only on the ARM Cortex M3, M4 and
compatible CPU. This assembly code is constant-time on the M4, and
about twice faster than the generic C code used by FALCON_FPEMU.
USAGE
-----
See the Makefile for compilation flags, and config.h for configurable
options. Type 'make' to compile: this will generate two binaries called
'test_falcon' and 'speed'. 'test_falcon' runs unit tests to verify that
everything computes the expected values. 'speed' runs performance
benchmarks on Falcon-256, Falcon-512 and Falcon-1024 (Falcon-256 is a
reduced version that is faster and smaller than Falcon-512, but provides
only reduced security, and not part of the "official" Falcon).
Applications that want to use Falcon normally work on the external API,
which is documented in the "falcon.h" file. This is the only file that
an external application needs to use.
For research purposes, the inner API is documented in "inner.h". This
API gives access to many internal functions that perform some elementary
operations used in Falcon. That API also has some non-obvious
requirements, such as alignment on temporary buffers, or the need to
adjust FPU precision on 32-bit x86 systems.
LICENSE
-------
This code is provided under the MIT license:
==========================(LICENSE BEGIN)============================
Copyright (c) 2017-2020 Falcon Project
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
===========================(LICENSE END)=============================
The main code was written by Thomas Pornin <[email protected]>, to
whom questions may be addressed. I'll endeavour to respond more or less
promptly.
The deterministic mode was written by David Lazar
<[email protected]>, with input from Chris Peikert
<[email protected]> and others from Algorand, Inc.