4 ms·

> you'd need to check 2^256 possible keys it's very unlikely you'd have to check the entire keyspace before you found it. On average it would be about half.

greenavocado 1y ago
Is there a more efficient way? What's the state of the art?
- timschmidt 1y ago
  IDK, let's ask a mathematician. Oh, they all work for NSA.
  - aaronbrethorst 1y ago
    Womp womp. https://therecord.media/nsa-to-cut-up-to-2000-roles-downsizing https://therecord.media/nsa-to-cut-up-to-2000-roles-downsizi...
    - timschmidt 1y ago
      I like to tell myself that everyone at NSA is a fine upstanding patriot, and that the agency only ever does what is in the best interest of the American People, but that does feel naive at times. Like when they infiltrate international standards bodies to introduce backdoors. Is downsizing the NSA something we're upset about?
      - akimbostrawman 1y ago
        It doesn't even really matter what character most of them have. Most information is on need to know basis for a reason so the one giving the orders can tell a tale about foreign terrorists while the grunts happily surveil the common man.
      - gosub100 1y ago
        Or when they walk out the door with gigabytes of secret data in their pocket.
- bb88 1y ago
  If you can find a quantum computing solution it's at worst O(sqrt(n)). There still seems to be a time factor, if not energy factor to computation. Shor's algorithm for factoring prime numbers is at best O(log(n)^2 * log(log(n)))
- kragen 1y ago
  Only slightly more efficient, 2²⁵⁴·³: https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Known_attacks https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#K...
MichaelDickens 1y ago
That reduces the runtime from 2.7 x 10^41 universe lifetimes to 1.35 x 10^41. I'm still not worried.
- dankwizard 1y ago
  When the NSA invented AES-256 they have a code they can input to just bypass it.
  - bonzini 1y ago
    It's worth noting that when the NSA invented DES, they took a cipher from IBM and made it more resistant (to differential cryptanalysis, a technique that at the time wasn't known outside the NSA itself).
    - kragen 1y ago
      The NSA made it more resistant to differential cryptanalysis, but hundreds of times less resistant to brute-force attack; see http://cr.yp.to/talks/2022.11.10/slides-djb-20221110-nsa-4x3.pdf http://cr.yp.to/talks/2022.11.10/slides-djb-20221110-nsa-4x3... > NSA gave Tuchman a clearance and brought him in to work jointly with the Agency on his Lucifer modification. . . . NSA tried to convince IBM to reduce the length of the key from 64 to 48 bits. Ultimately, they compromised on a 56-bit key. https://blog.cr.yp.to/20220805-nsa.html https://blog.cr.yp.to/20220805-nsa.html > The cryptographic core of NSA's sabotage of DES was remarkably blunt: NSA simply convinced Tuchman to limit the key size to 56 bits, a glaring weakness. > Whit Diffie and Marty Hellman wrote a paper explaining in considerable detail how to build a machine for $20 million that would break each DES key with an amortized cost of just $5000/key using mid-1970s technology. They predicted that the cost of such a brute-force attack would drop "in about 10 years time" to about $50/key, simply from chip technology improving. > Diffie and Hellman already distributed drafts of their paper before DES was standardized. Did NSA say, oh, oops, you caught us, this isn't secure? > Of course not. NSA claimed that, according to their own estimates, the attack was 30000 times more expensive: "instead of one day he gets something like 91 years". The Diffie and Hellman paper from 01977 is https://ee.stanford.edu/~hellman/publications/27.pdf https://ee.stanford.edu/~hellman/publications/27.pdf. The main source here is https://archive.org/details/cold_war_iii-nsa/cold_war_iii-ISCAP/page/n239/mode/2up https://archive.org/details/cold_war_iii-nsa/cold_war_iii-IS..., "American Cryptology during the Cold War, 1945-1989", DOCID: 523696, REF ID: A523696, a declassified internal NSA history. Longer version of the quote above, originally classified TOP SECRET UMBRA, from p.232 (p.240/271) > (S CCO) The decision to get involved with NBS was hardly unanimous. From the SIGINT standpoint, a competent industry standard could spread into undesirable areas, like Third World government communications, narcotics traffickers, and international terrorism targets. But NSA had only recently discovered the large-scale Soviet pilfering of information from U.S. government and defense industry telephone communications. This argued the opposite case - that, as Frank Rowlett had contended since World War II, in the long run it was more important to secure one's own communications than to exploit those of the enemy. > (FOUO) Once that decision had been made, the debate turned to the issue of minimizing the damage. Narrowing the encryption problem to a single, influential algorithm might drive out competitors, and that would reduce the field that NSA had to be concerned about. Could a public encryption standard be made secure enough to protect against everything but a massive brute force attack, but weak enough to still permit an attack of some nature using very sophisticated (and expensive) techniques? NSA worked closely with IBM to strengthen the algorithm against all except brute force attacks and to strengthen substitution tables, called S-boxes. Conversely, NSA tried to convince IBM to reduce the length of the key from 64 to 48 bits. Ultimately, they compromised on a 56-bit key. This may sound like a paranoid conspiracy theory, but it is the point of view of an NSA insider, writing in 01998 for an audience of NSA cryptoanalysts and cryptographers to educate them on the history of cryptology during the Cold War. It is understandable that Schneier and others believed that the overall influence of the NSA on DES was to increase its security, because they did not have access to this declassified material when they formed those opinions; it wasn't declassified until July 26, 02013.

greenavocado 1y ago

Is there a more efficient way? What's the state of the art?

timschmidt 1y ago
IDK, let's ask a mathematician. Oh, they all work for NSA.
- aaronbrethorst 1y ago
  Womp womp. https://therecord.media/nsa-to-cut-up-to-2000-roles-downsizing https://therecord.media/nsa-to-cut-up-to-2000-roles-downsizi...
  - timschmidt 1y ago
    I like to tell myself that everyone at NSA is a fine upstanding patriot, and that the agency only ever does what is in the best interest of the American People, but that does feel naive at times. Like when they infiltrate international standards bodies to introduce backdoors. Is downsizing the NSA something we're upset about?
    - akimbostrawman 1y ago
      It doesn't even really matter what character most of them have. Most information is on need to know basis for a reason so the one giving the orders can tell a tale about foreign terrorists while the grunts happily surveil the common man.
    - gosub100 1y ago
      Or when they walk out the door with gigabytes of secret data in their pocket.
bb88 1y ago
If you can find a quantum computing solution it's at worst O(sqrt(n)). There still seems to be a time factor, if not energy factor to computation. Shor's algorithm for factoring prime numbers is at best O(log(n)^2 * log(log(n)))
kragen 1y ago
Only slightly more efficient, 2²⁵⁴·³: https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Known_attacks https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#K...

MichaelDickens 1y ago

That reduces the runtime from 2.7 x 10^41 universe lifetimes to 1.35 x 10^41. I'm still not worried.

dankwizard 1y ago
When the NSA invented AES-256 they have a code they can input to just bypass it.
- bonzini 1y ago
  It's worth noting that when the NSA invented DES, they took a cipher from IBM and made it more resistant (to differential cryptanalysis, a technique that at the time wasn't known outside the NSA itself).
  - kragen 1y ago
    The NSA made it more resistant to differential cryptanalysis, but hundreds of times less resistant to brute-force attack; see http://cr.yp.to/talks/2022.11.10/slides-djb-20221110-nsa-4x3.pdf http://cr.yp.to/talks/2022.11.10/slides-djb-20221110-nsa-4x3... > NSA gave Tuchman a clearance and brought him in to work jointly with the Agency on his Lucifer modification. . . . NSA tried to convince IBM to reduce the length of the key from 64 to 48 bits. Ultimately, they compromised on a 56-bit key. https://blog.cr.yp.to/20220805-nsa.html https://blog.cr.yp.to/20220805-nsa.html > The cryptographic core of NSA's sabotage of DES was remarkably blunt: NSA simply convinced Tuchman to limit the key size to 56 bits, a glaring weakness. > Whit Diffie and Marty Hellman wrote a paper explaining in considerable detail how to build a machine for $20 million that would break each DES key with an amortized cost of just $5000/key using mid-1970s technology. They predicted that the cost of such a brute-force attack would drop "in about 10 years time" to about $50/key, simply from chip technology improving. > Diffie and Hellman already distributed drafts of their paper before DES was standardized. Did NSA say, oh, oops, you caught us, this isn't secure? > Of course not. NSA claimed that, according to their own estimates, the attack was 30000 times more expensive: "instead of one day he gets something like 91 years". The Diffie and Hellman paper from 01977 is https://ee.stanford.edu/~hellman/publications/27.pdf https://ee.stanford.edu/~hellman/publications/27.pdf. The main source here is https://archive.org/details/cold_war_iii-nsa/cold_war_iii-ISCAP/page/n239/mode/2up https://archive.org/details/cold_war_iii-nsa/cold_war_iii-IS..., "American Cryptology during the Cold War, 1945-1989", DOCID: 523696, REF ID: A523696, a declassified internal NSA history. Longer version of the quote above, originally classified TOP SECRET UMBRA, from p.232 (p.240/271) > (S CCO) The decision to get involved with NBS was hardly unanimous. From the SIGINT standpoint, a competent industry standard could spread into undesirable areas, like Third World government communications, narcotics traffickers, and international terrorism targets. But NSA had only recently discovered the large-scale Soviet pilfering of information from U.S. government and defense industry telephone communications. This argued the opposite case - that, as Frank Rowlett had contended since World War II, in the long run it was more important to secure one's own communications than to exploit those of the enemy. > (FOUO) Once that decision had been made, the debate turned to the issue of minimizing the damage. Narrowing the encryption problem to a single, influential algorithm might drive out competitors, and that would reduce the field that NSA had to be concerned about. Could a public encryption standard be made secure enough to protect against everything but a massive brute force attack, but weak enough to still permit an attack of some nature using very sophisticated (and expensive) techniques? NSA worked closely with IBM to strengthen the algorithm against all except brute force attacks and to strengthen substitution tables, called S-boxes. Conversely, NSA tried to convince IBM to reduce the length of the key from 64 to 48 bits. Ultimately, they compromised on a 56-bit key. This may sound like a paranoid conspiracy theory, but it is the point of view of an NSA insider, writing in 01998 for an audience of NSA cryptoanalysts and cryptographers to educate them on the history of cryptology during the Cold War. It is understandable that Schneier and others believed that the overall influence of the NSA on DES was to increase its security, because they did not have access to this declassified material when they formed those opinions; it wasn't declassified until July 26, 02013.