In essence the KEM construct can be used with any asymmetric algorithm, however depending on the properties of the asymmetric algorithm the way to implement the KEM might differ (in order to have it secure).
However, I wonder if the “BetterKEM” construct is universal and can be used with all (existing) asymmetric algorithms?
(This what follows is not a critique of the article, but of the standards and general research in this field.)
The issue that annoys me with applied cryptography in general is that most cryptographers focus too much on efficiency, and thus most “standardized” constructs are quite “bizarre” and hard to understand the “why?”. However, perhaps more problematic, is that these constructs aren’t portable between different algorithms; what works in one context is completely broken in the other.
For example, RSA-KEM (the standard one) doesn’t seem to translate to Kyber-KEM. However (and I say “if” because I can’t assess this myself), if the “BetterKEM” you’ve highlighted would apply to Kyber, then why don’t cryptographers just choose to standardize that? It would simpler for everybody involved.
Then, if one needs to employ multiple asymmetric algorithms (say RSA or X25519 with Kyber), then have each of its KEMs do the binding to their public keys, and hash the concatenations of the results (i.e. hybrid-r2 = hash(X25519-KEM-r2 || Kyber-KEM-r2); indeed it’s wasteful in terms of CPU cycles but it’s so much simpler to implement and most importantly test and verify.
BTW, @soatok, I closely follow your blog because most of your articles tackle cryptographic problems from a practical applied point of view. Thanks for writing these articles!
However, I wonder if the “BetterKEM” construct is universal and can be used with all (existing) asymmetric algorithms?
For example, RSA-KEM (the standard one) doesn’t seem to translate to Kyber-KEM. However (and I say “if” because I can’t assess this myself), if the “BetterKEM” you’ve highlighted would apply to Kyber, then why don’t cryptographers just choose to standardize that? It would simpler for everybody involved.
The reason has less to do with cryptographers and more to do with standards organizations (with a few practical arguments).
Most cryptography that any of us uses in our day-to-day is transport-layer; i.e., TLS, Quic, SSH.
TLS 1.3+ (which is where PQ crypto is going to land) uses full transcript hashing in its KDF. Adding more context to the underlying primitive is, from this perspective, a duplication of effort.
The ongoing debate on the CFRG touches on this stuff, although it is admittedly a bit hard to follow.
What it doesn’t touch on: NIST and the IETF are so heavily over-indexed on the TLS use-case that they basically ignored the possibility of non-interactive key exchanges for the immediate future. Fortunately, ML-KEM can be used with static public keys.
If this oversight was corrected, it’s probable that they would prioritize differently.
Most cryptography that any of us uses in our day-to-day is transport-layer; i.e., TLS, Quic, SSH.
Indeed, but most of us also use (directly or behind the scenes) encryption, password managers, backup systems, etc. all of which do resort to “at-rest-encryption”, and because we are lacking actual best practices, we end up with broken and compromised systems.
For example NaCl / libsodium is one of the few libraries that actually try to provide developers with useful and safe constructs. (Unfortunately these two libraries only cover a limited set of use-cases, and sometimes they are either too low-level or too high-level for certain use-cases.)
TLS 1.3+ (which is where PQ crypto is going to land) uses full transcript hashing in its KDF. Adding more context to the underlying primitive is, from this perspective, a duplication of effort.
Perhaps. But, if they would have used some generally available building blocks (say something that OpenSSL / LibreSSL / libsodium / etc. provides out-of-the-box as ready-to-use constructs), then perhaps we wouldn’t have so many broken TLS implementations…
If I could put things from another perspective: at the moment cryptography is where computer-science was before general-purpose programming languages were introduced – we only have assembler (our low-level raw cryptographic primitives) and each application (our protocols) is custom built one-instruction-after-another for a particular use-case; there are no reusable libraries in sight (i.e. higher-level cryptographic building-blocks).
Indeed. I have some projects I’m exploring with my current employer to help bridge the gap between low-level building blocks and higher-level reusable components, but it will be a while before anything gets released (and when it does, it probably won’t be associated with my fursona).
This is exactly the article I needed when reading “How to Hold KEMs.” I had thought due to the title, the previous submission would be more like this one and quickly was in over my head. This type of “build an intuition” material is very much appreciated by me, as it always seems cryptography assumes a pretty high level understanding of the maths behind it already. Even the, “You can’t possibly get this wrong.” style APIs still feel foreign, and are often are used wrong just due to an incorrect intuition about what is at play.
Possible typo in OversimplifiedKEM.encaps method, I’m assuming it should be return kdf(c)?
Fundamentally a lot of cryptography is very simple when you get the intuition, but when super-precise mathematical jargon gets interspersed it can be hard to gain the intuition.
Of course that jargon is important for cryptographers to convey precise notions to one another, but not great for lay-people
In essence the KEM construct can be used with any asymmetric algorithm, however depending on the properties of the asymmetric algorithm the way to implement the KEM might differ (in order to have it secure).
However, I wonder if the “BetterKEM” construct is universal and can be used with all (existing) asymmetric algorithms?
(This what follows is not a critique of the article, but of the standards and general research in this field.)
The issue that annoys me with applied cryptography in general is that most cryptographers focus too much on efficiency, and thus most “standardized” constructs are quite “bizarre” and hard to understand the “why?”. However, perhaps more problematic, is that these constructs aren’t portable between different algorithms; what works in one context is completely broken in the other.
For example, RSA-KEM (the standard one) doesn’t seem to translate to Kyber-KEM. However (and I say “if” because I can’t assess this myself), if the “BetterKEM” you’ve highlighted would apply to Kyber, then why don’t cryptographers just choose to standardize that? It would simpler for everybody involved.
Then, if one needs to employ multiple asymmetric algorithms (say RSA or X25519 with Kyber), then have each of its KEMs do the binding to their public keys, and hash the concatenations of the results (i.e.
hybrid-r2 = hash(X25519-KEM-r2 || Kyber-KEM-r2); indeed it’s wasteful in terms of CPU cycles but it’s so much simpler to implement and most importantly test and verify.BTW, @soatok, I closely follow your blog because most of your articles tackle cryptographic problems from a practical applied point of view. Thanks for writing these articles!
The reason has less to do with cryptographers and more to do with standards organizations (with a few practical arguments).
Most cryptography that any of us uses in our day-to-day is transport-layer; i.e., TLS, Quic, SSH.
TLS 1.3+ (which is where PQ crypto is going to land) uses full transcript hashing in its KDF. Adding more context to the underlying primitive is, from this perspective, a duplication of effort.
The ongoing debate on the CFRG touches on this stuff, although it is admittedly a bit hard to follow.
What it doesn’t touch on: NIST and the IETF are so heavily over-indexed on the TLS use-case that they basically ignored the possibility of non-interactive key exchanges for the immediate future. Fortunately, ML-KEM can be used with static public keys.
If this oversight was corrected, it’s probable that they would prioritize differently.
Indeed, but most of us also use (directly or behind the scenes) encryption, password managers, backup systems, etc. all of which do resort to “at-rest-encryption”, and because we are lacking actual best practices, we end up with broken and compromised systems.
For example NaCl /
libsodiumis one of the few libraries that actually try to provide developers with useful and safe constructs. (Unfortunately these two libraries only cover a limited set of use-cases, and sometimes they are either too low-level or too high-level for certain use-cases.)Perhaps. But, if they would have used some generally available building blocks (say something that OpenSSL / LibreSSL /
libsodium/ etc. provides out-of-the-box as ready-to-use constructs), then perhaps we wouldn’t have so many broken TLS implementations…If I could put things from another perspective: at the moment cryptography is where computer-science was before general-purpose programming languages were introduced – we only have assembler (our low-level raw cryptographic primitives) and each application (our protocols) is custom built one-instruction-after-another for a particular use-case; there are no reusable libraries in sight (i.e. higher-level cryptographic building-blocks).
Indeed. I have some projects I’m exploring with my current employer to help bridge the gap between low-level building blocks and higher-level reusable components, but it will be a while before anything gets released (and when it does, it probably won’t be associated with my fursona).
This is exactly the article I needed when reading “How to Hold KEMs.” I had thought due to the title, the previous submission would be more like this one and quickly was in over my head. This type of “build an intuition” material is very much appreciated by me, as it always seems cryptography assumes a pretty high level understanding of the maths behind it already. Even the, “You can’t possibly get this wrong.” style APIs still feel foreign, and are often are used wrong just due to an incorrect intuition about what is at play.
Possible typo in
OversimplifiedKEM.encapsmethod, I’m assuming it should bereturn kdf(c)?Fundamentally a lot of cryptography is very simple when you get the intuition, but when super-precise mathematical jargon gets interspersed it can be hard to gain the intuition.
Of course that jargon is important for cryptographers to convey precise notions to one another, but not great for lay-people
Nope, but it should include both
candkdf(r). :)I’ve updated the post to fix the pseudocode.
The
encapsmethod needed to returncandkdf(r)and the post is now fixed.I’m on Firefox Android with uBlock and I’m getting the no adblocker detected message anyway.
Known issue, no known fix
https://github.com/stefanbohacek/detect-missing-adblocker/issues/19