Lessons learnt from previous migrations
mathilde.chenu
To understand how the post-quantum migration could be fostered following the publication of the standards, I am studying the previous cryptographic transitions from ECC to RSA and from DES to AES. For this reason, I would be interested to hear your views on what happened at the time (I cannot recall myself, I was busy learning how to read and write in the early 2000s).
The subjects was only partly discussed in the "Deprecation timeline for quantum-vulnerable cryptography" mails, so I take this opportunity to follow-up. In particular, I would be grateful to hear your views on the following questions:
- According to the web almanach
from 2022 (2023 is not published yet), about 30% of websites were using
TLS 1.2, which still allows for RSA key exchanges. It does not say
which algorithm was used though. Is there an archive recording the
percentage of https key exchanges still made using RSA in 2022, or even
today?
- Looking back, were the deprecation timelines, including the one from NIST SP 800-131A, accurately set? For example the RSA-1024 validity was extended from 2010 to 2013, did it slow down the migration?
- How much time did it take for the companies/industries to adopt the new standards after the standard publication? Is 12-15 years really accurate? Which sectors were faster/slower to migrate? Was it different for ECC, before open competitions, and AES?
- Some
industries claim that they postponed their post-quantum migration due
to the lack of mature libraries. Was it also the case for ECC or AES? Or
was it only a convenient reason to stay put? And how much time did it
take to have reliable and trusted libraries?
- Did
the Dual_EC_DRNG issue had an impact on following migrations? Or other events?
The use of encryption increased following Snowden's revelations, is
there any evidence that it also helped migration?
Any other insights, or any pointer to relevant web archives, are also very welcomed.
Thanks,
Mathilde Chenu
Joint Research Center
Ispra, Italy
John Mattsson
Hi Mathilde,
I think there has been many more transitions. E.g., DES to 3DES, 3DES to AES, AES-CBC to AES-GCM, SHA-1 to SHA-256, No-PFS to PFS, and RSA/FFDH to ECC.
- Cloudflare’s blog from February 2024 says that TLS 1.3 is used by more than 93% of the connections. Figure 14.5 in the Web Almanac states that 97% of requests support perfect forward secrecy. There are however still much more to do in the migration to PFS, e.g., key agreement in 5G. The lack of PFS in AKA means that a SIGINT agency with access to SIM keys can passively eavesdrop on all mobile phone calls for these keys. Unfortunately, the proposal to address this significant weakness was objected by organizations from France, UK, and US. No technical reasons were given. Support from Swedish, Finish, Chinese, German, and US organizations.
- Cryptographic migrations often take much longer than 12-15 years. It is common with hardware with lifetimes of 20 years that simply cannot be updated. Root-of-trusts for e.g., firmware update can often not be changed and a device with hardware acceleration of algorithm A can typically not migrate to algorithm B without unacceptable performance loss. Complying with NISTIR 8547 means that almost all existing hardware and most hardware deployed in the next few years will have to be replaced.
- Dual_EC_DRNG had truly horrible effects. After Suite B went all in for ECC, many industries planned for a migration from RSA/FFDH to ECC. One example is mobile systems where I helped driving the decision to introduce and recommend ECC everywhere. Dual_EC_DRNG unfortunately led to huge uncertainty regarding ECC in general, significantly delaying migration, and sometime making it go backwards. I have seen examples of implementations reading about Dual_EC_DRNG (or reading safecurves.cr.yp.to) and then turning off ECC even if the only other thing supported was FFDH-1024 and RSA-1024 (and not the good kind of FFDH-1024 and RSA-1024). I think the increased use of encryption following Snowden (who recently swore an oath of allegiance to Russia) led to more focus on high performance cryptography, which helped migration to AES, AES-GCM, and ECC. I have also heard stories of products using no encryption rather than encryption with Simon/Speck, which sometimes is the only ciphers with acceptable performance. I hope the lesson for SIGINTs are “Don’t intentionally weaken cybersecurity systems”, but I fear the lesson likely is “Don’t get caught”.
Cheers,
John
--
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 visit
https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/-mHtgYQ9SA-9STTK-Vf380Jy2vEZzFA5sPUaHXt7kPUqHq2l_CJehBQC9spj8F9Vc-narI5J90lgdFXau_nxxm7OUBwroYi3buCszMDmGvc%3D%40protonmail.com.
Simo Sorce
> I think there has been many more transitions. E.g., DES to 3DES, 3DES to AES, AES-CBC to AES-GCM, SHA-1 to SHA-256, No-PFS to PFS, and RSA/FFDH to ECC.
And RC2 -> RC4 -> No more stream ciphers
There are also signature schemes like DSA and Elgamal and others.
There are also examples of algorithms requested strongly by other
national agencies that substantially went nowhere but where implemented
in crypto libraries anyway, like Camellia, and others that have some
diffusion/migration only within the countries of origin like the
Russian GOST standards (Hashing, ECC, etc..) and the Chinese
SM2,SM3,SM4
The lesson is generally that any change is really hard and always takes
a lot longer than it should and there is a long tail of implementation
and *protocols* that keeps going through the motions using algorithms
that have no shred of security left without revision. For example the
authentication scheme Digest-MD5 is still alive and the places where it
was used have not updated their spec even though multiple generations
of authentication schemes have come and gone already ...
HTH
--
Simo Sorce
Distinguished Engineer
RHEL Crypto Team
Red Hat, Inc
John Mattsson
Simo Sorce wrote:
>And RC2 -> RC4 -> No more stream ciphers
Yes RC4 was used quite a lot, but RC4 was not at all the end of stream ciphers. SNOW 3G, SNOW 5G, ZUC, and ZUC-256 are specified for use in mobile networks and ChaCha20 is very popular in a lot of different use cases. Nothing wrong with stream ciphers. The confidentiality advantages for SNOW 5G and ChaCha20 are much better than for AES-256-GCM.
Cheers,
John
Simo Sorce
> Simo Sorce wrote:
> > And RC2 -> RC4 -> No more stream ciphers
> Yes RC4 was used quite a lot, but RC4 was not at all the end of stream ciphers. SNOW 3G, SNOW 5G, ZUC, and ZUC-256 are specified for use in mobile networks and ChaCha20 is very popular in a lot of different use cases. Nothing wrong with stream ciphers. The confidentiality advantages for SNOW 5G and ChaCha20 are much better than for AES-256-GCM.
(afaik). The other thing with Chacha20-poly1305 is that while there was
very widespread adoption no migration to it was "required".
Taylor R Campbell
> From: Simo Sorce <si...@redhat.com>
> On Mon, 2024-12-02 at 23:30 +0000, 'John Mattsson' via pqc-forum wrote:
> > I think there has been many more transitions. E.g., DES to 3DES, 3DES to AES, AES-CBC to AES-GCM, SHA-1 to SHA-256, No-PFS to PFS, and RSA/FFDH to ECC.
>
> And MD2 -> MD4 -> MD5 -> SHA1
> And RC2 -> RC4 -> No more stream ciphers
Just about all web traffic today goes through one of two stream
ciphers, AES-CTR or ChaCha.
Your mail was sent using the stream cipher AES-CTR, via the TLS cipher
suite TLS_AES_256_GCM_SHA384, along every hop of the way from
m8.users.ipa.redhat.com to smtp.gmail.com to relay.mimecast.com to
mx.google.com, according to the message header.
Out of the box, OpenSSH only uses cipher suites based on stream
ciphers (also AES-CTR and ChaCha).
Of course there's more to it -- there's also authenticators and key
agreement and signatures -- but it is not the case that there are `no
more stream ciphers' today. It is exactly the opposite: almost all
encryption of arbitrary message data in practice is built out of
stream ciphers, and encryption _without_ a stream cipher component
like AES-CBC is the exception! The design is ubiquitous even though
building one out of a block cipher like AES costs a PRF/PRP-switching
hit to security.
D. J. Bernstein
here are some examples of different types of data that are available:
https://eprint.iacr.org/2013/734
https://eprint.iacr.org/2016/995
https://eprint.iacr.org/2018/298
https://ianix.com/pub/chacha-deployment.html
https://ianix.com/pub/ed25519-deployment.html
https://ianix.com/pub/curve25519-deployment.html
https://mailarchive.ietf.org/arch/msg/tls/6OfxXrOKkQd7vM8D5AceYXUuI8o/
https://mailarchive.ietf.org/arch/msg/tls/pQRDJ9MBwnmLHp86Zvs_CfYUFaY/
https://mailarchive.ietf.org/arch/msg/tls/lWh_uimMIgQ6SMV_BSkJDh34eQM/
Regarding motivations, https://blog.cr.yp.to/20220805-nsa.html includes
various links to arguments for DES, DSA, and Dual EC. Regarding RC4
motivations, some links:
https://simson.net/ref/NeXT/nextworld/NextWorld_Extra/92.09.Sept.NWE/92.09.Sept.NWExtra11.html
https://web.archive.org/web/20131001024142/https://www.emc.com/emc-plus/rsa-labs/historical/rsa-security-response-weaknesses-algorithm-rc4.htm
https://blog.qualys.com/product-tech/2011/10/17/mitigating-the-beast-attack-on-tls
Regarding RSA-vs.-ECC motivations, some links:
https://web.archive.org/web/20000903072819/https://csrc.nist.gov/encryption/kms/kms-comments.pdf
https://eprint.iacr.org/2008/390
https://bugzilla.redhat.com/show_bug.cgi?id=319901
https://mailarchive.ietf.org/arch/msg/tls/MKZdnppZDJQ0l3WUftba390Qrns/
https://lists.mindrot.org/pipermail/openssh-unix-dev/2013-September/031659.html
To be clear, linking doesn't imply endorsement. A statement "X was
motivated by Y" can be incorrect even when it's coming from X, and Y
itself can be incorrect or otherwise a flawed argument; Dual EC is a
well-documented example of these effects.
Simo Sorce writes:
> And RC2 -> RC4 -> No more stream ciphers
ChaCha20 stream cipher. Together those account for ~100% of TLS
encryption today, plus many further stream-cipher deployments, as
illustrated by the chacha-deployment link above. There are also
applications that mix stream-cipher usage with block-cipher usage: e.g.,
https://security.googleblog.com/2019/02/introducing-adiantum-encryption-for.html
encrypts 4080 bytes from each disk block using a stream cipher (namely
ChaCha12) plus 16 bytes using a block cipher (namely AES).
---D. J. Bernstein
Simo Sorce
> No more stream ciphers?
Ignore this part, please, I did not express myself correctly. I merely
meant no more stream cipher of this kind, but there is no point in
discussing the details or quantity of modern stream ciphers, the topic
was migrations and how long they took and how [un]successful they have
been.
Regards,
Simo.
mathilde.chenu
@John: you mentioned that Dual_ECC convinced some players *not* to use other safe and sound ECC-based protocols. Is there any evidence, from your personal experience or from the literature, that the attacks on SIKE had the same 'brake' effect on the PQC migration for industries? Or did it rather encourage them towards hybridization and/or crypto-agility (let's be hopeful)?
@Simo: You said that Chacha20 did not need standardization since it was already widely adopted. Does the absence of standard and/or reference specification creates issues of interoperability between systems? Any cases of industries or companies refusing to use it because it was not officially standardized? Would there be any argument in favor of standardizing it now?
@Dan: Thanks for the refs.
An additional question: The security of symmetric primitives seems to be better understood than for asymmetric primitives. Is this reflected in the delays for them to be adopted? In particular I have AES and SHA-3 in mind, which seemed to have been adopted quickly (I might be wrong though). Any evidence of asymmetric transitions being systematically longer than symmetric ones?
Cheers,
Mathilde Chenu
Joint Research Centre
> 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.
Simo Sorce
> @Simo: You said that Chacha20 did not need standardization since it was already widely adopted. Does the absence of standard and/or reference specification creates issues of interoperability between systems? Any cases of industries or companies refusing to use it because it was not officially standardized? Would there be any argument in favor of standardizing it now?
The algorithm was standardized by IETF in RFC 7539 (updated in RFC
8439) after being published by D, J. Bernstein.
However it was not adopted by NIST as a national standard therefore it
is not allowed to be used by government agencies that need to follow
the FIPS standards.
There are many arguments in favor of NIST adopting it, yet NIST has
been focusing mostly on asymmetric ciphers for the past few years and
has shown no movement in standardizing a second symmetric cipher after
AES.
Paul Hoffman
> The algorithm was standardized by IETF in RFC 7539 (updated in RFC
> 8439) after being published by D, J. Bernstein.
--Paul Hoffman
David A. Cooper
Scott Fluhrer (sfluhrer)
> -----Original Message-----
> From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Simo
> Sorce
> Sent: Thursday, December 5, 2024 9:41 AM
> To: mathilde.chenu <mathild...@protonmail.com>
> Cc: pqc-...@list.nist.gov
> Subject: Re: [pqc-forum] Lessons learnt from previous migrations
>
> focusing mostly on asymmetric ciphers for the past few years and has shown
> no movement in standardizing a second symmetric cipher after AES.
Simo Sorce
they are used as if they were standards and guide interoperable
implementations.
Simo.
John Mattsson
NIST has been extremely active also when it comes to symmetric cryptography. Thanks for that! In addition to Ascon, NIST is also planning discussing/planning standardizing
of Rijndael-256-256, a Keccak AEAD, Accordions, and Accordion derived functions.
https://csrc.nist.gov/csrc/media/Presentations/2024/options-for-encryption-algorithms-and-modes/images-media/sess-3-regenscheid-acm-workshop-2024.pdf
https://csrc.nist.gov/news/2024/proposal-to-update-fips-202-and-revise-sp-800-185
https://csrc.nist.gov/files/pubs/other/2024/04/10/proposal-of-requirements-for-an-accordion-mode-dis/iprd/docs/proposal-of-requirements-for-an-accordion-mode-discussion-draft.pdf
I wholeheartedly welcome all of these initiatives. We need a backup to AES, algorithms with better properties, and algorithms with better which are not so easy to shoot yourself in the foot with.
Cheers,
John
--
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.
Q R
--
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.
Simo Sorce
I was under the impression that the Ascon family was limited in scope
due to supporting only up to 128 bit keys (last I checked) and the
"lightweight" origin, so I did not understand it as a full alternative
to AES, but only an option for lower security devices.
I also appreciate the work on new modes, my comment was not meant in
any way to diminish the work NIST is doing in all these areas.
Regards,
Simo.
John Mattsson
Q R <amz...@gmail.com> wrote
>Are the Ascon ciphers quantum - safe?
All symmetric crypto is quantum-safe. The idea that symmetric cryptography will be practically affected by CRQCs is a misconception. While classical supercomputers might be able to brute force AES-128 around the year 2090, a huge cluster of one billion CRQCs (according to one estimate costing one billion USD each) would take a million years of uninterrupted calculation to find a single AES-128 key. The qubits would take up the surface area of the moon. Algorithms with quadratic (n2) speedup like Grover’s algorithm (which is proven to be optimal) will not provide any practical quantum advantage for breaking symmetric cryptography and likely not for any other problems.
Most other 128-bit algorithms such as SNOW 3G, ZUC, TUAK, KMAC128, Ascon, etc. are likely to have similar quantum overhead for Grover’s algorithm which is known to be
optimal. Even if an algorithm has slightly lower quantum overhead than AES-128, the algorithm would still fulfill the requirement (comparable to key search on AES-128) for quantum resistance category 1.
IETF Statement on Quantum Safe Cryptographic Protocol Inventory
https://datatracker.ietf.org/liaison/1942/
3GPP Statement on PQC Migration
https://www.3gpp.org/ftp/tsg_sa/WG3_Security/TSGS3_118_Hyderabad/docs/S3-244307.zip
Sam Jaques, “Quantum Attacks on AES”
https://www.youtube.com/watch?v=eB4po9Br1YY&t=3227s
Oh, Jang, Baksi, Seo, “Depth-Optimized Implementation of ASCON Quantum Circuit”
https://eprint.iacr.org/2023/1030.pdf
Cheers,
John
From:
pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Q R <amz...@gmail.com>
Date: Thursday, 5 December 2024 at 16:38
To: Scott Fluhrer (sfluhrer) <sflu...@cisco.com>
Cc: Simo Sorce <si...@redhat.com>, mathilde.chenu <mathild...@protonmail.com>, pqc-...@list.nist.gov <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Lessons learnt from previous migrations
|
You don't often get email from amz...@gmail.com. Learn why this is important |
John Mattsson
Mathilde Chenu wrote:
>@John: you mentioned that Dual_ECC convinced some players *not* to use other safe and sound ECC-based protocols. Is there any evidence, from your personal experience or from the literature,
that the attacks on SIKE had the same 'brake' effect on the PQC migration for industries? Or did it rather encourage them towards hybridization and/or crypto-agility (let's be hopeful)?
I don’t think SIKE being broken had a huge practical effect, but yes, I would say that the attacks on SIKE and Rainbow likely encouraged/will encourage hybridization. Other things that have been driving industry to use more hybridization is bugs and side-channels in implementations, requirements from European governments, and NISTIR 8547. Before NISTIR 8547 many industries were planning to do prioritization between different use cases, different protection lifetimes, and different value of the proteced data/item. Systems migrated later when implementations have been hardened could likely have used standalone ML-KEM and ML-DSA, but the broad-brush approach required by NISTIR 8547 will likely lead to much more hybridization. And once hybridization is used, I am sceptical to if it will ever be removed. You need strong reasons to change things.
I was very positive to NIST including SIKE in later rounds to foster reasearch into Isogeny-based cryptography and KEMs with compact public keys and ciphertexts but we did not have any plans to use SIKE anytime soon. We typically only use algorithms after they are specified by NIST, IETF/IRTF, and ETSI SAGE. . I kind of agree with Shamir that said that you should wait at least 20 years, and isogeny-based cryptography was invented in 2011. Isogeny-based crypto is also a bit too slow to be useful in practice. The biggest impact of the SIKE attack was that it provided a lot of idea to isogeny research which is once again a very hot topic. I relly like Wouter CastryckOne talk at Eurocrypt https://www.youtube.com/watch?v=CpqjkfuXeoQ
We are perfectly fine with using algorithms such as ChaCha20 specified by CFRG but not NIST. One exception is LMS and XMSS were we considered using using the CFRG specs until NIST standardized and forbid key export. Using LMS or XMSS and not being compliant with NIST requirements would have looked bad.
Cheers,
John
D. J. Bernstein
> Please note that neither of these RFC are standards. They were
> developed in the IRTF, which is not the IETF, and the IRTF is limited
> to publishing informational and experimental RFCs, not standards.
RFC 8446, "The Transport Layer Security (TLS) Protocol Version 1.3", is
an IETF document saying, inter alia, that a "TLS-compliant application"
(i.e., every implementation of TLS 1.3) "SHOULD implement" RFC 7905.
Like thousands of other IETF documents that are called "standards", RFC
7905 and RFC 8446 both have formal IETF status "Proposed Standard" (as
listed in https://www.rfc-editor.org/standards). As RFC 7127 explains,
"IETF Proposed Standards are of such quality that they are ready for the
usual market-based product development and deployment efforts into the
Internet". IETF has pretty much abandoned the old idea of moving
documents beyond the "Proposed Standard" status.
Internally, RFC 7905 is factored via the informational specifications of
ChaCha20 and Poly1305 in RFC 7539. For people who mistakenly refer to
RFC 7539 as an IETF standard, a useful correction might be something
like the following: "Please note that IETF's ChaCha20 standards are
actually RFC 7634, RFC 7905, RFC 8103, RFC 8446, etc."
---D. J. Bernstein