9 ms·

A Swiss Company Says It Found Weakness That Imperils Encryption

28 points by Sami_Lehtinen 6y ago

caminocorner 6y ago
The article only has limited details, which are near the bottom of the article: > The company said that its research found vulnerabilities that affect symmetric encryption ciphers, including the Advanced Encryption Standard, or AES, which is widely used to secure data transmitted over the internet and to encrypt files. Using a method known as quantum annealing, the company said its research found that even the strongest versions of AES encryption may be decipherable by quantum computers that could be available in a few years from now. > Vinokur said in an interview that Terra Quantum’s team made the discovery after figuring out how to invert what’s called a “hash function,” a mathematical algorithm that converts a message or portion of data into a numerical value. The research will show that “what was once believed unbreakable doesn’t exist anymore,” Vinokur said, adding that the finding “means a thousand other ways can be found soon.”
- DennisP 6y ago
  Quantum annealing is significantly easier than the full quantum computers required to break public-key encryption, or run Grover's algorithm. Quantum annealers are commercially available right now with thousands of qubits, and seem to be advancing quickly. If they really could break AES or find hash collisions with annealers, that would be a pretty big deal.
vmception 6y ago
> The company, which is backed by the Zurich-based venture capital firm Lakestar LP, has developed a new encryption protocol that it says can’t be broken by quantum computers. Vinokur said the new protocol utilizes a method known as quantum key distribution. > Terra Quantum is currently pursuing a patent for the new protocol. But the company will make it available for free, according to Pflitsch. doubt. they found the problem, and have also developed the solution. will need more information on the problem.
- microtherion 6y ago
  The web site looks rather clickbaity: https://terraquantum.swiss https://terraquantum.swiss Looking at the team: https://terraquantum.swiss/team/ https://terraquantum.swiss/team/ The CEO is a physicist, but describing yourself as a "CERN Quantum Physicist" strikes me as a bit gauche, if you did part of your degree there and then went for greener pa$ture$ with the Boston Consulting Group. Co-Founder is a German lawyer. CTO is Russian, as are apparently all members of the technical team, with the exception of one German. The only Swiss is in the URL (Not to go all ultra-nationalist, but I can't help suspecting that they picked Switzerland for the lax corporate regulatory environment, and it irritates me that they'd play up their Swiss connection without even a few token Swiss on board). Their place of business, Rorschach, has the distinction of being literally the furthest you can get away from CERN while still being in Switzerland. Not necessarily on the A list of places to locate high tech companies in Switzerland, but, I hear, on the A list of places with business friendly regulations.
  - vmception 6y ago
    I don't weigh any of those things heavily - especially the Swiss company needing Swiss people - or the location. All cantons in Switzerland compete for business and its very convenient that any sparsely populated canton can have imbued a regulator (a random nobody) with such wide powers to make it most convenient for a business, and that business inherits the brand of Switzerland. I need the paper and confirmation from other people's interpretation of the paper.
    - microtherion 6y ago
      St. Gallen, where they are located, is not "sparsely populated", they are quite urbanized and they do have a substantial non-financial industry. I did not mean to imply that the company was completely bogus, but they seem to be a bit more hype driven and less product driven than a typical startup.
      - vmception 6y ago
        yeah we agree on that and I don’t find it surprising after what I quoted in the article I think its sad that startups and entreprenuers are tasked with both identifying a problem and a solution. They should be different people because the competencies are very different, and the possible solutions are much more numerous than the one team will come up with. But you cant woo investors or customers like that, you pretty much have to be indistinguishable from a grifter and if you fail you’ve officially become one.
ghshephard 6y ago
Hold on - I thought that AES fell into the category of encryption systems that wasn't vulnerable (for the forseeable future) to quantum attacks. I swear a ton of really smart people I follow on twitter claimed that it wasn't, and that it was all the public key/factoring stuff that would collapse. See: https://qvault.io/2020/09/10/is-aes-256-quantum-resistant https://qvault.io/2020/09/10/is-aes-256-quantum-resistant
- bccdee 6y ago
  AES really shouldn't be vulnerable to quantum attacks. Hence the expert they cited saying that the story "[..] seems somewhat unlikely on the face of it." This'll be a really big deal... IF it's true.
  - jandrewrogers 6y ago
    AES has been observed to be very slightly leaky but not in a way that is practically exploitable, partly because even finding it is memory hard on a large volume of data. I know respected crypto experts that have been looking into this anomaly for a few years. It isn't out of the realm of possibility that there is a quantum shortcut related to that state leak.
- AnimalMuppet 6y ago
  If I understand correctly (and I may not), AES wasn't vulnerable to known or projected quantum attacks. And that was true, right up until Terra developed a new kind of attack. And that's always been true, even with non-quantum attacks. You're invulnerable to known attacks? Great, until someone invents a whole new kind of attack. Note well: All this is assuming that the article is accurate...
  - SAI_Peregrinus 6y ago
    Not quite correct. Grover's Algorithm is provably asymptotically optimal for quantum attacks. That is, you'll never do better with just a quantum computer than Grover's will, unless you can also do better without the quantum computer. (One caveat is that Grover's has substantial low-order terms, and one could come up with an algorithm having the same big-O complexity but better practical efficiency. But they don't seem to be claiming that.) It's not known that there are no classical attacks on AES. Just that a lot of people have looked quite hard for over 20 years and haven't found anything useful. Terra hasn't provided any evidence of their attacks. Lots of claims, no proof. That doesn't inspire any trust in their claims, especially since proof would be easy. They claim to have found a way to "invert" MD5, which probably means a second preimage attack. If they had that, they could release data which hashes to an all-zero output. If they were ethical and telling the truth, they'd provide proof. If they were unethical and telling the truth, they'd generalize it to find second-preimages on double SHA256, and have a vastly more efficient way to mine bitcoin (and/or forge bitcoin transactions) and make a bunch of money instead of or before putting out a press release. Neither of these things (or anything similar) has happened, so they're almost certainly lying.
tppiotrowski 6y ago
Vinokur said in an interview that Terra Quantum’s team made the discovery after figuring out how to invert what’s called a “hash function,” Can someone comment if “invert” really means invert or if it means an instant way of brute forcing all possible/probable inputs. Isn’t there an infinite number of inputs that produce the same hash, thus inverting a hash function would produce infinite results? Edit: forgot hashing usually truncates the payload to the 4096 characters/etc so I guess the inputs are finite.
- whatshisface 6y ago
  It's easy enough to ask for something like "the shortest string that hashes to this," or "what do I have to append to my string to make it hash to that." But you have a good point, there is no unique answer to inverting a hash - you need additional criteria for there to be one answer.
- umvi 6y ago
  > Isn’t there an infinite number of inputs that produce the same hash, thus inverting a hash function would produce infinite results? Well you only need to find a solution, you don't need to find all solutions (of which there are infinite as you say). Brute force is the only known way currently of discovering a solution, but perhaps Terra Quantum figured out some sort of "shortcut" that reduces the time to find a solution for a particular hash function. Until they release more details I'm highly skeptical you could quickly find a solution to something like sha256
  - warkdarrior 6y ago
    In practice you to find a meaningful solution, i.e., it has to have the right structure/format. If I'm trying to hack your email (whatever that means), the solution would need to look like a valid email message, with reasonable headers and in the expected language.
  - tppiotrowski 6y ago
    > Well you only need to find a solution, you don't need to find all solutions You're right! It doesn't matter that I don't know your actual password. Any text that hashes to the same value will work in the "password" input field.
colpabar 6y ago
> A Swiss Company Says It Found Weakness That Imperils Encryption and of course there are no links to anyone actually saying this. There are links to stock quotes, to the definition of a hash function, to people in the same field but different companies. But _of course_ there is nowhere for me to go and read what was actually said. This is off topic, but I would LOVE to make it a requirement that for any article with a headline like "X claims Y" to put a link to X saying Y as the first item. I really don't care what bloomberg has to say about quantum computing. edit: there's a bit more info here[1], but still no links to any source for the statement of any kind. > They Terra Quantum discovered a weakness on the message-digest algorithm MD5. The Terra Quantum team found that one can crack an algorithm using a quantum annealer containing about 20,000 qubits. No such annealer exists today, and while it is impossible to predict when it may be created, it is conceivable that such an annealer could become available to hackers in the future. I think there's a reason the only hits I get for this are business journals. [1]: https://www.businesswire.com/news/home/20210208005290/en/Terra-Quantum-Makes-Electronically-Transmitted-Communications-Unbreakable-After-Revealing-Weakness-in-%E2%80%98post-quantum-Cryptography%E2%80%99 https://www.businesswire.com/news/home/20210208005290/en/Ter...
- chapium 6y ago
  They discovered an attack on part of AES. Article is light on details, but this is not the end of crypto algorithms as the article implies.
  - pdimitar 6y ago
    What do you mean by an attack on "part of AES"?
    - chapium 6y ago
      It was mentioned pretty vaguely in the article, so its hard to tell. It mentioned it effects a hashing function. I'm not sure if it meant AES as a whole or a component of it.
- tchalla 6y ago
CyberRabbi 6y ago
Please ban clickbait
- yorwba 6y ago
  Clickbait is already banned. This story was also submitted with a less-clickbaity, more-informative title: https://news.ycombinator.com/item?id=26066955 https://news.ycombinator.com/item?id=26066955 But, predictably, it got fewer clicks.
  - CyberRabbi 6y ago
    The title isn’t the issue. The entire premise of the story is misleading. There are also no primary sources or peer reviewed claims. This is essentially an ad for a company under the guise of news. Please ban.
SAI_Peregrinus 6y ago
They say this, but provide no evidence.
osy 6y ago
tl;dr: The Big Hack (2021)
tobr 6y ago
Why is this flagged? Obviously the claim is pretty insubstantial, but there’s nothing wrong with the article as far as I can tell.
haspoken 6y ago
http://archive.is/hXc15 http://archive.is/hXc15

28 points by Sami_Lehtinen 6y ago

The article only has limited details, which are near the bottom of the article: > The company said that its research found vulnerabilities that affect symmetric encryption ciphers, including the Advanced Encryption Standard, or AES, which is widely used to secure data transmitted over the internet and to encrypt files. Using a method known as quantum annealing, the company said its research found that even the strongest versions of AES encryption may be decipherable by quantum computers that could be available in a few years from now. > Vinokur said in an interview that Terra Quantum’s team made the discovery after figuring out how to invert what’s called a “hash function,” a mathematical algorithm that converts a message or portion of data into a numerical value. The research will show that “what was once believed unbreakable doesn’t exist anymore,” Vinokur said, adding that the finding “means a thousand other ways can be found soon.”

DennisP 6y ago
Quantum annealing is significantly easier than the full quantum computers required to break public-key encryption, or run Grover's algorithm. Quantum annealers are commercially available right now with thousands of qubits, and seem to be advancing quickly. If they really could break AES or find hash collisions with annealers, that would be a pretty big deal.

vmception 6y ago

> The company, which is backed by the Zurich-based venture capital firm Lakestar LP, has developed a new encryption protocol that it says can’t be broken by quantum computers. Vinokur said the new protocol utilizes a method known as quantum key distribution. > Terra Quantum is currently pursuing a patent for the new protocol. But the company will make it available for free, according to Pflitsch. doubt. they found the problem, and have also developed the solution. will need more information on the problem.

microtherion 6y ago
The web site looks rather clickbaity: https://terraquantum.swiss https://terraquantum.swiss Looking at the team: https://terraquantum.swiss/team/ https://terraquantum.swiss/team/ The CEO is a physicist, but describing yourself as a "CERN Quantum Physicist" strikes me as a bit gauche, if you did part of your degree there and then went for greener pa$ture$ with the Boston Consulting Group. Co-Founder is a German lawyer. CTO is Russian, as are apparently all members of the technical team, with the exception of one German. The only Swiss is in the URL (Not to go all ultra-nationalist, but I can't help suspecting that they picked Switzerland for the lax corporate regulatory environment, and it irritates me that they'd play up their Swiss connection without even a few token Swiss on board). Their place of business, Rorschach, has the distinction of being literally the furthest you can get away from CERN while still being in Switzerland. Not necessarily on the A list of places to locate high tech companies in Switzerland, but, I hear, on the A list of places with business friendly regulations.
- vmception 6y ago
  I don't weigh any of those things heavily - especially the Swiss company needing Swiss people - or the location. All cantons in Switzerland compete for business and its very convenient that any sparsely populated canton can have imbued a regulator (a random nobody) with such wide powers to make it most convenient for a business, and that business inherits the brand of Switzerland. I need the paper and confirmation from other people's interpretation of the paper.
  - microtherion 6y ago
    St. Gallen, where they are located, is not "sparsely populated", they are quite urbanized and they do have a substantial non-financial industry. I did not mean to imply that the company was completely bogus, but they seem to be a bit more hype driven and less product driven than a typical startup.
    - vmception 6y ago
      yeah we agree on that and I don’t find it surprising after what I quoted in the article I think its sad that startups and entreprenuers are tasked with both identifying a problem and a solution. They should be different people because the competencies are very different, and the possible solutions are much more numerous than the one team will come up with. But you cant woo investors or customers like that, you pretty much have to be indistinguishable from a grifter and if you fail you’ve officially become one.

ghshephard 6y ago

Hold on - I thought that AES fell into the category of encryption systems that wasn't vulnerable (for the forseeable future) to quantum attacks. I swear a ton of really smart people I follow on twitter claimed that it wasn't, and that it was all the public key/factoring stuff that would collapse. See: https://qvault.io/2020/09/10/is-aes-256-quantum-resistant https://qvault.io/2020/09/10/is-aes-256-quantum-resistant

bccdee 6y ago
AES really shouldn't be vulnerable to quantum attacks. Hence the expert they cited saying that the story "[..] seems somewhat unlikely on the face of it." This'll be a really big deal... IF it's true.
- jandrewrogers 6y ago
  AES has been observed to be very slightly leaky but not in a way that is practically exploitable, partly because even finding it is memory hard on a large volume of data. I know respected crypto experts that have been looking into this anomaly for a few years. It isn't out of the realm of possibility that there is a quantum shortcut related to that state leak.
AnimalMuppet 6y ago
If I understand correctly (and I may not), AES wasn't vulnerable to known or projected quantum attacks. And that was true, right up until Terra developed a new kind of attack. And that's always been true, even with non-quantum attacks. You're invulnerable to known attacks? Great, until someone invents a whole new kind of attack. Note well: All this is assuming that the article is accurate...
- SAI_Peregrinus 6y ago
  Not quite correct. Grover's Algorithm is provably asymptotically optimal for quantum attacks. That is, you'll never do better with just a quantum computer than Grover's will, unless you can also do better without the quantum computer. (One caveat is that Grover's has substantial low-order terms, and one could come up with an algorithm having the same big-O complexity but better practical efficiency. But they don't seem to be claiming that.) It's not known that there are no classical attacks on AES. Just that a lot of people have looked quite hard for over 20 years and haven't found anything useful. Terra hasn't provided any evidence of their attacks. Lots of claims, no proof. That doesn't inspire any trust in their claims, especially since proof would be easy. They claim to have found a way to "invert" MD5, which probably means a second preimage attack. If they had that, they could release data which hashes to an all-zero output. If they were ethical and telling the truth, they'd provide proof. If they were unethical and telling the truth, they'd generalize it to find second-preimages on double SHA256, and have a vastly more efficient way to mine bitcoin (and/or forge bitcoin transactions) and make a bunch of money instead of or before putting out a press release. Neither of these things (or anything similar) has happened, so they're almost certainly lying.

tppiotrowski 6y ago

Vinokur said in an interview that Terra Quantum’s team made the discovery after figuring out how to invert what’s called a “hash function,” Can someone comment if “invert” really means invert or if it means an instant way of brute forcing all possible/probable inputs. Isn’t there an infinite number of inputs that produce the same hash, thus inverting a hash function would produce infinite results? Edit: forgot hashing usually truncates the payload to the 4096 characters/etc so I guess the inputs are finite.

whatshisface 6y ago
It's easy enough to ask for something like "the shortest string that hashes to this," or "what do I have to append to my string to make it hash to that." But you have a good point, there is no unique answer to inverting a hash - you need additional criteria for there to be one answer.
umvi 6y ago
> Isn’t there an infinite number of inputs that produce the same hash, thus inverting a hash function would produce infinite results? Well you only need to find a solution, you don't need to find all solutions (of which there are infinite as you say). Brute force is the only known way currently of discovering a solution, but perhaps Terra Quantum figured out some sort of "shortcut" that reduces the time to find a solution for a particular hash function. Until they release more details I'm highly skeptical you could quickly find a solution to something like sha256
- warkdarrior 6y ago
  In practice you to find a meaningful solution, i.e., it has to have the right structure/format. If I'm trying to hack your email (whatever that means), the solution would need to look like a valid email message, with reasonable headers and in the expected language.
- tppiotrowski 6y ago
  > Well you only need to find a solution, you don't need to find all solutions You're right! It doesn't matter that I don't know your actual password. Any text that hashes to the same value will work in the "password" input field.

colpabar 6y ago

> A Swiss Company Says It Found Weakness That Imperils Encryption and of course there are no links to anyone actually saying this. There are links to stock quotes, to the definition of a hash function, to people in the same field but different companies. But _of course_ there is nowhere for me to go and read what was actually said. This is off topic, but I would LOVE to make it a requirement that for any article with a headline like "X claims Y" to put a link to X saying Y as the first item. I really don't care what bloomberg has to say about quantum computing. edit: there's a bit more info here[1], but still no links to any source for the statement of any kind. > They Terra Quantum discovered a weakness on the message-digest algorithm MD5. The Terra Quantum team found that one can crack an algorithm using a quantum annealer containing about 20,000 qubits. No such annealer exists today, and while it is impossible to predict when it may be created, it is conceivable that such an annealer could become available to hackers in the future. I think there's a reason the only hits I get for this are business journals. [1]: https://www.businesswire.com/news/home/20210208005290/en/Terra-Quantum-Makes-Electronically-Transmitted-Communications-Unbreakable-After-Revealing-Weakness-in-%E2%80%98post-quantum-Cryptography%E2%80%99 https://www.businesswire.com/news/home/20210208005290/en/Ter...

chapium 6y ago
They discovered an attack on part of AES. Article is light on details, but this is not the end of crypto algorithms as the article implies.
- pdimitar 6y ago
  What do you mean by an attack on "part of AES"?
  - chapium 6y ago
    It was mentioned pretty vaguely in the article, so its hard to tell. It mentioned it effects a hashing function. I'm not sure if it meant AES as a whole or a component of it.
tchalla 6y ago

CyberRabbi 6y ago

Please ban clickbait

yorwba 6y ago
Clickbait is already banned. This story was also submitted with a less-clickbaity, more-informative title: https://news.ycombinator.com/item?id=26066955 https://news.ycombinator.com/item?id=26066955 But, predictably, it got fewer clicks.
- CyberRabbi 6y ago
  The title isn’t the issue. The entire premise of the story is misleading. There are also no primary sources or peer reviewed claims. This is essentially an ad for a company under the guise of news. Please ban.

SAI_Peregrinus 6y ago

They say this, but provide no evidence.

osy 6y ago

tl;dr: The Big Hack (2021)

tobr 6y ago

Why is this flagged? Obviously the claim is pretty insubstantial, but there’s nothing wrong with the article as far as I can tell.

haspoken 6y ago

http://archive.is/hXc15 http://archive.is/hXc15