Seeking community feedback on which signature formats should be supported by FIPS 206 (FN-DSA/ Falcon)
Perlner, Ray A. (Fed)
Dear all,
Multiple encodings are currently specified for signature in section 3.11.3 of the Falcon submission document: https://falcon-sign.info/falcon.pdf . We are looking for community feedback on which of these should be supported by FIPS 206. Briefly, these options may be described as
- Compressed signatures padded with zeroes to a fixed byte length: This is currently the default encoding
- Unpadded compressed signatures: These are variable length, but on average, shorter than padded signatures
- Uncompressed signatures: These are longer than the other encodings, but may be useful in applications where signatures or signed messages need to be kept secret. The lack of compression is intended to avoid leakage of information about signatures or signed messages via a timing side channel.
If the FIPS ends up supporting multiple encodings, we intend to include domain separation in the message digest to maintain strong unforgeability. In any case, we intend to specify a signature format for the output of FN-DSA rather than a signed message format, which will consist of a domain separator (if needed), the salt, and the encoded s_2 value. We are currently leaning towards including both a and c in the standard.
Thank You,
Ray Perlner (NIST PQC)
niux_d...@icloud.com
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB4855D7C7586D7138728C16FF9C4C2%40DM6PR09MB4855.namprd09.prod.outlook.com.
Sebastien Riou
Sebastien Riou
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/7E162EFC-3377-4DCF-8202-C4F6EED471EE%40icloud.com.
Bas Westerbaan
--
Perlner, Ray A. (Fed)
Hi Bas,
You ask: “Is the concern the number of iterations (line 4 algorithm 10)? I haven't fully understood Falcon yet, so excuse me if the following suggestion is naive, but what about picking a new r in the rare care Compress() fails?”
I hadn’t considered this particular loop. I agree that choosing a new r in each iteration seems like it would rule out any leakage from compression failure (although I’m not sure why we should be more worried about timing leakage from compression failure than about timing leakage from the check on line 8.)
That said, the concern about timing comes directly from the Falcon submission document which says on page 48: “This uncompressed format yields larger signatures and is meant to support the uncommon situations in which signature values and signed messages are secret: uncompressed signatures can be decoded and encoded with constant-time implementations that do not leak information through timing-based side channels.”
At least within the quoted text, it seems like the concern is the timing of compression and decompression itself. Speaking for myself, it seems like compress and decompress could be quite inefficient to implement in constant time (and no secret dependent memory access), given that the encoding of each coefficient can vary between 9 to 24 bits (with low values like 9 and 10 being predominant.) But perhaps compression and decompression are fast enough to begin with that even slowing them down by several orders of magnitude has no meaningful impact on overall performance of signing and verification.
Also speaking for myself, of the applications listed here I’m more concerned about the case where the signature itself is the secret, e.g. SAML assertions where the signature is used as a bearer token.
For cases where the message needs to be secret, I am less concerned. I would assume the signature would also be encrypted (otherwise the signature could be used to mount a dictionary attack regardless of any timing leakage). Then, I would think timing leakage could at most reveal a randomized hash of the message, where the salt is unknown (I don’t see any way there should be a timing leakage revealing the salt if the hashing is done in a constant time way.)
Hope this clarifies,
Ray
Bas Westerbaan
Could someone give an estimate on what "but on average, shorter than padded signatures" means in practice?
That said, the concern about timing comes directly from the Falcon submission document which says on page 48: “This uncompressed format yields larger signatures and is meant to support the uncommon situations in which signature values and signed messages are secret: uncompressed signatures can be decoded and encoded with constant-time implementations that do not leak information through timing-based side channels.”
At least within the quoted text, it seems like the concern is the timing of compression and decompression itself. Speaking for myself, it seems like compress and decompress could be quite inefficient to implement in constant time (and no secret dependent memory access), given that the encoding of each coefficient can vary between 9 to 24 bits (with low values like 9 and 10 being predominant.) But perhaps compression and decompression are fast enough to begin with that even slowing them down by several orders of magnitude has no meaningful impact on overall performance of signing and verification.
// maximum size of output in bytes
#define M 154
// number of uint64s required to hold the output
#define L 20
// Computes unary code for the 512 entries in
int unary(uint8_t *out, uint8_t *in) {
uint64_t buf[L] = {0};
int total = 0;
for (int i = 0; i < N; i++) {
int shift = in[i] + 1;
total += shift;
for (int j = L-1; j > 0; j--) {
buf[j] = (buf[j] << shift) | (buf[j-1] >> (64-shift));
}
buf[0] <<= shift;
buf[0] ^= (1 << (shift-1));
}
for (int i = 0; i < M; i++) {
out[i] = (buf[i>>3] >> (i&7)) & 255;
}
return total;
}
John Mattsson
Thanks Bas,
(Google groups seem to have sent my previous mail to the spamfolder…)
So, 651.59 ±
2.55 bytes instead of 666. While I personally, as a heavy metal fan, is strangely
drawn to the number 666, I think the right choice for most applications is (b). Most protocols do not rely on signatures being a fixed size, i.e., they have a signature length field. I think (b) should be the default. I don’t see any problems
with variable length signatures in general.
Is the suggestion for (b) to not only remove the padding but also the “abort if str is too long” in the compress() function?
7: if (|str| > slen) then
8: str ←
⊥
▷ Abort if str is too long
9: else
10: str ← (str∥0slen−|str|)
▷ Pad str to slen bits
I like the idea of getting rid of aborts unless it has some security reasons. I have not read up on FN-DSA enough yet.
Thinking about protocols (X.509, CMP, CRL, OCSP, TLS, IKEv2, JOSE, COSE, EDHOC, Group OSCORE, MIKEY,…) I cannot come up with a single one that does not have a signature length field.
(c) seems like it could be useful to protect against side-channels in Sign-then-Encrypt, which is how you should compose sign and encrypt. My understanding is that the (c) signatures would be 809 bytes for level 1.
I think NIST should include (b) and (c). I currently don’t see any use of (a).
Cheers,
John
From:
'Bas Westerbaan' via pqc-forum <pqc-...@list.nist.gov>
Date: Tuesday, 29 October 2024 at 13:24
To: John Preuß Mattsson <john.m...@gmail.com>
Cc: pqc-forum <pqc-...@list.nist.gov>, Perlner, Ray A. (Fed) <ray.p...@nist.gov>
Subject: Re: [pqc-forum] Seeking community feedback on which signature formats should be supported by FIPS 206 (FN-DSA/ Falcon)
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to
pqc-forum+...@list.nist.gov.
Kris Kwiatkowski
From an integration perspective, implementing unpadded compressed signatures can be a bit more challenging. Some existing software interfaces assume that signatures have a fixed size, making variable sizes inconvenient and potentially leading to insecure implementations.
Additionally, the size difference between padded-compressed and unpadded-compressed signatures is minimal, with the latter being slightly longer in the worst-case scenario. This suggests that the benefits of a smaller unpadded-compressed signature do not outweigh the complications it introduces. Therefore, I believe that not standardizing unpadded-compressed signatures is a sound decision. This aligns with the design choices made for Dilithium, which also includes padding.
Currently, I don't have a strong preference between options a) and c). I think making Falcon easier to implement securely in different scenarios (even if they don't exist yet) could be beneficial. On the other hand, NIST IR 8413-upd1 mentions that Falcon was selected partly due to its short signature size (one of the reasons). Following that reasoning, the compressed padded signature is about 200 bytes smaller than the constant-time signature (for 512), indicating that keeping this option is a way to go.
I also acknowledge that we will have both Pre-hash and Pure signing versions. If NIST chooses to retain options a, b, and c, we could potentially end up with six different variations. It seems wise to minimize these variations, as the differences among them are relatively slight.
I think keeping a) and c) makes sense. And if we can choose only one, that would be perfect.
--
Kris Kwiatkowski
Cryptography Dev
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Kris Kwiatkowski
I don’t assume the signature length is always fixed.
John Mattsson
As pointed out by Danny Niu, ECDSA signatures are variable length in many encodings including the most common ASN.1 DER. I think the assumption that the signature length is always fixed is bad, and the quicker we can force such badly designed software to update, the better.
Cheers,
John
From:
pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Kris Kwiatkowski <kr...@amongbytes.com>
Date: Wednesday, 30 October 2024 at 10:02
To: Perlner, Ray A. (Fed) <ray.p...@nist.gov>
Cc: pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Seeking community feedback on which signature formats should be supported by FIPS 206 (FN-DSA/ Falcon)
Hello,
From an integration perspective, implementing unpadded compressed signatures can be a bit more challenging. Some existing software interfaces assume that signatures have a fixed size, making variable sizes inconvenient and potentially leading to insecure implementations.
Additionally, the size difference between padded-compressed and unpadded-compressed signatures is minimal, with the latter being slightly longer in the worst-case scenario. This suggests that the benefits of a smaller unpadded-compressed signature do not outweigh
the complications it introduces. Therefore, I believe that not standardizing unpadded-compressed signatures is a sound decision. This aligns with the design choices made for Dilithium, which also includes padding.
Currently, I don't have a strong preference between options a) and c). I think making Falcon easier to implement securely in different scenarios (even if they don't exist yet) could be beneficial. On the other hand, NIST IR 8413-upd1 mentions that Falcon was
selected partly due to its short signature size (one of the reasons). Following that reasoning, the compressed padded signature is about 200 bytes smaller than the constant-time signature (for 512), indicating that keeping this option is a way to go.
I also acknowledge that we will have both Pre-hash and Pure signing versions. If NIST chooses to retain options a, b, and c, we could potentially end up with six different variations. It seems wise to minimize these variations, as the differences among them
are relatively slight.
I think keeping a) and c) makes sense. And if we can choose only one, that would be perfect.
--
Kris Kwiatkowski
Cryptography Dev
> On 22 Oct 2024, at 18:53, 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov> wrote:
>
> Dear all,
> Multiple encodings are currently specified for signature in section 3.11.3 of the Falcon submission document: https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Ffalcon-sign.info%2Ffalcon.pdf&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7Cb5f7c30e53fa4cc0cb3808dcf8c1818a%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638658757447341615%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C40000%7C%7C%7C&sdata=XvmoY8Uuf4ZPeMhG97yUs7iwxDkgUW5RH5Tm%2Fao0XxY%3D&reserved=0 . We are looking for community feedback on which of these should be supported by FIPS 206. Briefly, these options may be described as
>
> • Compressed signatures padded with zeroes to a fixed byte length: This is currently the default encoding
> • Unpadded compressed signatures: These are variable length, but on average, shorter than padded signatures
> • Uncompressed signatures: These are longer than the other encodings, but may be useful in applications where signatures or signed messages need to be kept secret. The lack of compression is intended to avoid leakage of information about signatures
or signed messages via a timing side channel.
> If the FIPS ends up supporting multiple encodings, we intend to include domain separation in the message digest to maintain strong unforgeability. In any case, we intend to specify a signature format for the output of FN-DSA rather than a signed message
format, which will consist of a domain separator (if needed), the salt, and the encoded s_2 value. We are currently leaning towards including both a and c in the standard.
> Thank You,
> Ray Perlner (NIST PQC)
>
> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
John Preuß Mattsson
Could someone give an estimate on what "but on average, shorter than padded signatures" means in practice?
Unless the difference is very small, Option b (Unpadded compressed signatures) makes most sense to me. Most protocols already have a length field for the signature length. Protocols not having a length field could add one or pad themselves.
Phillip Gajland
I agree that selecting a new salt when compression fails is a good approach and improves security. In fact, our work actually suggests choosing a new salt if the preimages from the sampler are too large. You can find more details in our post here: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/IvlTWZE4IIk.
While we didn't specifically address the compression procedure, the same rationale applies to both compression and sampling.
Regards,
Phillip (with Eike and Jonas)
Sebastien Riou
- secure boot typically relies on OTP for storage. That memory is fixed and very limited (when the size is kilo bits, that's already a large one!). In such cases having something "smaller on average" does not help because we have to reserve the maximum size.
- high security devices will always prefer things with fixed size. variable size introduces complexity, complexity is hard to verify (both from functional and security point of view). With a variable size object, I need a test vector for each size. If I have multiple variable size objects, ideally I need to test all size combinations...
Sebastien Riou
- A key pair unique to each chip
- A signature of the public key by a root key (typically this signature is done by an HSM owned by the chip manufacturer)
Sebastien Riou
Director, Product Security Architecture
PQShield Ltd
M: +33 782 320 285
Do you have any examples for applications/hardware/products where storing signatures in OTP would make sense?For keys I fully agree, then storing either the key directly, the hash of the key ladder or the seed to expand the key makes sense - however I've never encountered the same for signatures.
Agree on the second point though.
Best regards,
Axel Keskikangas
Expert Engineer, Core Technologies Systems
Axis Communications ABGränden 1, SE-223 69 Lund, SwedenTel: +46 46 272 18 00, Fax: +46 46 13 61 30, www.axis.com
From: 'Sebastien Riou' via pqc-forum <pqc-...@list.nist.gov>
Sent: Wednesday, October 30, 2024 16:44
To: John Mattsson <john.m...@ericsson.com>
Cc: Kris Kwiatkowski <kr...@amongbytes.com>; Perlner, Ray A. (Fed) <ray.p...@nist.gov>; pqc-forum <pqc-...@list.nist.gov>
Thomas Pornin
- The "constant-time" hashing came out mostly as a reflex, i.e. when I implemented the hashing I noticed that it was not, in general, constant-time. Usually, people don't worry about that; for instance, in plain RSA signature verification, implementations run the modular exponentiation, then check that the padding is there, extract the hashed message, and compare that hash value with the expected hash value. That last comparison is typically done with a non-constant-time memcmp() and nobody minds that, because it is generally accepted that signature verification uses only public data.
For that question of constant-time hashing to matter, you have to imagine a rather contrived scenario in which the signed data is secret and has low entropy, making it amenable to enumeration ("brute force"). But that's not sufficient! For the scenario to make sense, you also need the signature value to be public; indeed, in Falcon, what is hashed is the concatenation of a random 40-byte nonce and the message; if the attacker does not have the nonce, then the brute force does not work. On the other hand, if the signature is known to the attacker, and the public key is also known to the attacker, then an approximate hashed message can be recomputed: indeed, in Falcon, the signature is a polynomial s2 such that s1 + s2*h = hashed-message, "h" being the public key (another polynomial) and s1 a "short polynomial" (a polynomial with a small norm). Given s2 (signature) and h (public key), an attacker can enumerate possible messages, and see if the hash process yields a polynomial s1 which is indeed short. Note that the ability to extract the hashed message from the public key + signature is not a new property; again, RSA has it.
Thus, we are now considering an hypothetical scenario where signatures are computed over secret data with low entropy; the said secret data must be known to the signer but also the verifier; the signature value is public, but the public key is not public. I am not aware of any plausible situation that matches all these conditions; and if there is one, then other existing schemes such as RSA are already inappropriate. So my intuition is that such situations do not exist, the "constant-time hashing of the message in Falcon" is not a real worry, and I was wrong to raise it in the first place. It would be better if we all simply forgot that such a debate existed in the first place.
- For the signature size: the difference in size between the compressed (variable-size) and padded (fixed-size) signatures is small; we are talking about an average gain of less than 3% here (651 vs 666). Sometimes a small gain matters, and I have seen situations where people run ECDSA repeatedly in a loop until the (r,s) values happen to be slightly smaller, just to gain a few bits in a dedicated encoded format! But in general, a less than 3% change is not going to matter.
I have observed (and written!) many implementations of various cryptographic protocols over the last two decades (and more), and many times have I witnessed that variable-sized elements are a problem. They require a length field, and thus some parsing. On the reception site, the receiver still has to account for the maximum possible size (not everybody has the luxury of dynamic memory allocation! Small microcontrollers exist). Parsing code is a source of bugs and buffer overflows, and invariably this is where security vulnerabilities occur (I professionally audit cryptographic implementations most of the time, and this is what I observe: the issues are usually in the parsing, not in the cryptography). It is true that many existing protocols use length fields and variable-size elements, e.g. for signatures and public keys; this is Bad and we should be ashamed. When the size gain is very slight, having a variable size is not a feature; it's a mistake, that we should endeavour not to make. It's a traditional error, but we are not compelled to follow tradition for the sake of it, especially when it's misguided.
On top of that, the fixed vs variable size question is, in fact, mostly meaningless. When a Falcon signature has the "padded" format, it is in fact padded with zeros. It is thus completely possible to define an extra "compressed encoding" of signatures for people who do have or want a length field: simply remove the trailing bytes of value zero when writing out the signature, and add them back when reading it. This can be done without any knowledge of the involved keys, so that's in fact not something that needs to be addressed in the FN-DSA standard; anybody can do that after the fact, it's only an encoding convention of the transport layer. The only part of the question that is really relevant to the FN-DSA standard is not whether the output signature has a fixed size, but whether it has a bounded size, i.e. whether the signer enforces a given maximum size for signatures. Having such a bound is very valuable for implementations, since that allows some guarantees on required buffer sizes. Enforcing a maximum bound (at e.g. 666 bytes for Falcon-512) is something that only the signer can do (by restarting if the generated signature turns out to be too long) so it must be part of the standard.
- Forget the "constant-time" thing for message hashing, it's a freak notion that does not make sense in that context (and it's my fault it ever happened, sorry).
- Signatures should be fixed-size, which means they should have, internally, a maximum size enforced by the signer, and with some padding with bytes of value zero to reach that size. People who want a variable size can strip the padding bytes at the transport level, if that's what they wish; they would be wrong and it will lead them to a path of sorrow, but I cannot prevent them from doing it.
John Mattsson
Hi,
I think it is important that signature algorithms (for a fixed message length) can be implemented in close to constant time for practical reasons, i.e. not only because of timing side-channels. This applies to both signing and verification. For many use cases, worst case time is the important measure to meet requirements, not average time (but you can ignore things that have very little probability like < 2^128). At a minimum, you would like guarantees that FN-DSA completes with X nines probability within a certain time. An example use of the nines terminology is this web server written in Erlang (Ericsson language), which claims nine nines (99.9999999%) availability. https://ninenines.eu/
I dislike loops with an unlimited number of integrations. Not only do you need to over dimension the CPU/ASIC/FPGA to meet requirements, but it might be very hard to theoretically understand how the probability distribution for the completion time looks like.
I don't think variable length fields is a big problem in general. Fixed sizes and padding on the other hand have in the past led to a large amount of practical vulnerabilities, CBC, RSA, etc. If a length field is considered complex, I don’t think you should use compression in the first place.
While 15 bytes on average might not sound much, if you design all aspects of your system like this, the end result becomes slow and inefficient. As we say in Europe: “Många bäckar små gör en stor å”, “Les petits ruisseaux font les grandes rivières”, “Kleinvieh macht auch Mist”…
Thomas Pornin wrote that the padding "can be done without any knowledge of the involved keys, so that's in fact not something that needs to be addressed in the FN-DSA standard". I would say that this points to that padding should be left to the application. My understanding is that the also the compression function can be done without any knowledge of the involved keys (correct me if I am wrong). I think it makes sense to move the compression and padding outside of the sign() function. The number of the beast 666, seems like an arbitrarily chosen tradeoff between uncompressed and variable length, which might not be the best tradeoff for all applications.
Cheers,
John
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9b0bca11-be47-433c-8dc3-e8922610a528n%40list.nist.gov.
Bas Westerbaan
Hi,
I think it is important that signature algorithms (for a fixed message length) can be implemented in close to constant time for practical reasons, i.e. not only because of timing side-channels.
I dislike loops with an unlimited number of integrations. Not only do you need to over dimension the CPU/ASIC/FPGA to meet requirements, but it might be very hard to theoretically understand how the probability distribution for the completion time looks like.
John Mattsson
Bas Westerban wrote:
>ML-DSA signing is not constant time. And its rejection probability is much worse than anything we >propose here for Falcon.
Yes, I am not completely happy about that, but I don't remember the specific details of ML-DSA. For Falcon, I hope NIST standardizes (c) and allow people to do (b) and (a), and potentially (a)’ with other tradeoffs. I am not against (a), but I don't think it is a good solution for everything.
Bas Westerban wrote:
>We can cut off at 2^-128 probability.
Yes.
Thomas Pornin
failed on step 8 (L2 norm): 55
length number
644 2
645 23
646 217
647 1712
648 9523
649 42910
650 146717
651 398673
652 857067
653 1470559
654 2025989
655 2250651
656 2024118
657 1482775
658 889549
659 438755
660 178744
661 60428
662 16671
663 3943
664 797
665 108
666 12
667 2