3 ms·

I dislike that Quanta used the term "Back Door" in their headline. That has a pretty specific meaning in information security generally and cryptography particu

I dislike that Quanta used the term "Back Door" in their headline. That has a pretty specific meaning in information security generally and cryptography particularly. This was not a back door. The tl;dr: it was conjectured that a more feasible method of factoring large numbers might exist by finding their unique polynomial representation. Polynomials are more quickly factored than integers, and to every integer there corresponds a unique polynomial per the fundamental theorem of algebra. But that method doesn't actually work, because as polynomials get larger they become commensurately more difficult to factor. In other words, it is as or more difficult to find the polynomial you'd want than it is to just find the prime factors for any given RSA semiprime. This is a neat result, but nothing is changing for RSA.

segfaultbuserr 8y ago
To people with some infosec knowledge, the poor choice of word "backdoor" sounds as if that the article is about importing an asymmetric backdoor to RSA encryption, which is not the case. If the author wants to have a casual style of writing, I think "loophole" could be used.
- throwawaymath 8y ago
  Agreed. "Loophole" would have been a particularly better choice of terminology. RSA has never had a "back door" in the sense of, e.g., DUAL_EC_DRBG.
- dang 8y ago
  Ok, we've put a loophole in the title above.
chrismeller 8y ago
I would go a step further and say that “sealed” implies they somehow changed something that directly impacts all RSA encryption. At least that’s the way I read it. Almost like taking down a botnet by taking over the domain or IP it’s C&C server uses. The reality was far less movie plot worthy.
- segfaultbuserr 8y ago
  > “sealed” implies they somehow changed something that directly impacts all RSA encryption. So we are talking about holes in RSA, some readers may find the following interesting, that in fact, RSA does have a problematic aspect (well, many) that can be called a "loophole": the padding. You are encrypting a short message (the symmetric key) by using a large public key, so the message have to be padded. From now the real fun started, intuitive solutions are prone to various forms of mathematical and cryptographic tricks, you get chosen ciphertext attack, and gives an attacker a straightforward "padding oracle". If you can manipulate the ciphertext and asks the server if the ciphertext is valid (or not), often, the attacker can deduce knowledge of the message or even the private key. Bleichenbacher attack and Coppersmith attack are known in the 90s, yet we still see exploitations in 2015. Proper padding is tricky to design and implement. As a response to this problem, OAEP, a padding algorithm with rigorous security proof, has finally been designed, and it should put an end to these attacks eventually. Yet, recently there have been some theoretical doubts about the soundness of the proof. But it turns out, you don't have to encrypt the session key as a message and padding it securely to begin with. Cryptographer Victor Shoup purposed RSA-KEM. The basic idea is, we can just keep generating a stream of meaningless random numbers using a CSPRNG, until it's long enough to be encrypted by the public key. Then, put these random numbers to a hash function (or any other secure KDF), the output will be the session key. This scheme is known as RSA-KEM, offers strong security guarantee, yet it only uses a simple approach that is hard to get wrong. https://en.wikipedia.org/wiki/Key_encapsulation https://en.wikipedia.org/wiki/Key_encapsulation
hopler 8y ago
Quanta does that intentionally, as clickbait to generate popular interest in their mathematical aricles that don't actually have applications. It's a scientific embarassment. Nature's magazine/blog does it to.
- hackinthebochs 8y ago
  > It's a scientific embarassment. A little over the top, don't you think? A little clickbait isn't a disservice to the science. Quanta is a layman magazine. Baiting layman interest with more familiar terms even if less technically accurate is ultimately a service to science.
pbsd 8y ago
The first step in the number field sieve is to represent the number to be factored as a polynomial (two, in fact), and it is assumed in the following steps that these polynomials do not split. If these polynomials did split with reasonable probability, the number field sieve would be a lot shorter. The usual reference for this is Brilhart et al. [1], which deals with polynomial representations in arbitrary bases, as opposed to strictly base 2, as is the case here. [1] https://doi.org/10.4153/CJM-1981-080-0 https://doi.org/10.4153/CJM-1981-080-0
Animats 8y ago
That's Quanta, which is a crap science mag. That article doesn't even seem to link to the actual paper. The actual paper is linked above. It's good to know that this approach to factoring is less vulnerable than suspected. We still don't have a proven lower bound on factoring, though. There's always the possibility that someone will make a breakthrough.
deleted 8y ago
[deleted]

segfaultbuserr 8y ago

To people with some infosec knowledge, the poor choice of word "backdoor" sounds as if that the article is about importing an asymmetric backdoor to RSA encryption, which is not the case. If the author wants to have a casual style of writing, I think "loophole" could be used.

throwawaymath 8y ago
Agreed. "Loophole" would have been a particularly better choice of terminology. RSA has never had a "back door" in the sense of, e.g., DUAL_EC_DRBG.
dang 8y ago
Ok, we've put a loophole in the title above.

chrismeller 8y ago

I would go a step further and say that “sealed” implies they somehow changed something that directly impacts all RSA encryption. At least that’s the way I read it. Almost like taking down a botnet by taking over the domain or IP it’s C&C server uses. The reality was far less movie plot worthy.

segfaultbuserr 8y ago
> “sealed” implies they somehow changed something that directly impacts all RSA encryption. So we are talking about holes in RSA, some readers may find the following interesting, that in fact, RSA does have a problematic aspect (well, many) that can be called a "loophole": the padding. You are encrypting a short message (the symmetric key) by using a large public key, so the message have to be padded. From now the real fun started, intuitive solutions are prone to various forms of mathematical and cryptographic tricks, you get chosen ciphertext attack, and gives an attacker a straightforward "padding oracle". If you can manipulate the ciphertext and asks the server if the ciphertext is valid (or not), often, the attacker can deduce knowledge of the message or even the private key. Bleichenbacher attack and Coppersmith attack are known in the 90s, yet we still see exploitations in 2015. Proper padding is tricky to design and implement. As a response to this problem, OAEP, a padding algorithm with rigorous security proof, has finally been designed, and it should put an end to these attacks eventually. Yet, recently there have been some theoretical doubts about the soundness of the proof. But it turns out, you don't have to encrypt the session key as a message and padding it securely to begin with. Cryptographer Victor Shoup purposed RSA-KEM. The basic idea is, we can just keep generating a stream of meaningless random numbers using a CSPRNG, until it's long enough to be encrypted by the public key. Then, put these random numbers to a hash function (or any other secure KDF), the output will be the session key. This scheme is known as RSA-KEM, offers strong security guarantee, yet it only uses a simple approach that is hard to get wrong. https://en.wikipedia.org/wiki/Key_encapsulation https://en.wikipedia.org/wiki/Key_encapsulation

hopler 8y ago

Quanta does that intentionally, as clickbait to generate popular interest in their mathematical aricles that don't actually have applications. It's a scientific embarassment. Nature's magazine/blog does it to.

hackinthebochs 8y ago
> It's a scientific embarassment. A little over the top, don't you think? A little clickbait isn't a disservice to the science. Quanta is a layman magazine. Baiting layman interest with more familiar terms even if less technically accurate is ultimately a service to science.

pbsd 8y ago

The first step in the number field sieve is to represent the number to be factored as a polynomial (two, in fact), and it is assumed in the following steps that these polynomials do not split. If these polynomials did split with reasonable probability, the number field sieve would be a lot shorter. The usual reference for this is Brilhart et al. [1], which deals with polynomial representations in arbitrary bases, as opposed to strictly base 2, as is the case here. [1] https://doi.org/10.4153/CJM-1981-080-0 https://doi.org/10.4153/CJM-1981-080-0

Animats 8y ago

That's Quanta, which is a crap science mag. That article doesn't even seem to link to the actual paper. The actual paper is linked above. It's good to know that this approach to factoring is less vulnerable than suspected. We still don't have a proven lower bound on factoring, though. There's always the possibility that someone will make a breakthrough.

deleted 8y ago

[deleted]