• Sc chevron_right

      Bounty to Recover NIST’s Elliptic Curve Seeds

      news.movim.eu / Schneier · Tuesday, 10 October - 20:18 · 1 minute

    This is a fun challenge:

    The NIST elliptic curves that power much of modern cryptography were generated in the late ’90s by hashing seeds provided by the NSA. How were the seeds generated? Rumor has it that they are in turn hashes of English sentences, but the person who picked them, Dr. Jerry Solinas, passed away in early 2023 leaving behind a cryptographic mystery, some conspiracy theories, and an historical password cracking challenge.

    So there’s a $12K prize to recover the hash seeds.

    Some backstory :

    Some of the backstory here (it’s the funniest fucking backstory ever): it’s lately been circulating—though I think this may have been somewhat common knowledge among practitioners, though definitely not to me—that the “random” seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string “Give Jerry a raise”.

    At the time, the “pass a string through SHA1” thing was meant to increase confidence in the curve seeds; the idea was that SHA1 would destroy any possible structure in the seed, so NSA couldn’t have selected a deliberately weak seed. Of course, NIST/NSA then set about destroying its reputation in the 2000’s, and this explanation wasn’t nearly enough to quell conspiracy theories.

    But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he’d forgotten the string he used!

    If you’re a true conspiracist, you’re certain nobody is going to find a string that generates any of these seeds. On the flip side, if anyone does find them, that’ll be a pretty devastating blow to the theory that the NIST P-curves were maliciously generated—even for people totally unfamiliar with basic curve math.

    Note that this is not the constants used in the Dual_EC_PRNG random-number generator that the NSA backdoored . This is something different.

    • Sc chevron_right

      Backdoor in TETRA Police Radios

      news.movim.eu / Schneier · Tuesday, 25 July, 2023 - 15:51 · 1 minute

    Seems that there is a deliberate backdoor in the twenty-year-old TErrestrial Trunked RAdio (TETRA) standard used by police forces around the world.

    The European Telecommunications Standards Institute (ETSI), an organization that standardizes technologies across the industry, first created TETRA in 1995. Since then, TETRA has been used in products, including radios, sold by Motorola, Airbus, and more. Crucially, TETRA is not open-source. Instead, it relies on what the researchers describe in their presentation slides as “secret, proprietary cryptography,” meaning it is typically difficult for outside experts to verify how secure the standard really is.

    The researchers said they worked around this limitation by purchasing a TETRA-powered radio from eBay. In order to then access the cryptographic component of the radio itself, Wetzels said the team found a vulnerability in an interface of the radio.

    […]

    Most interestingly is the researchers’ findings of what they describe as the backdoor in TEA1. Ordinarily, radios using TEA1 used a key of 80-bits. But Wetzels said the team found a “secret reduction step” which dramatically lowers the amount of entropy the initial key offered. An attacker who followed this step would then be able to decrypt intercepted traffic with consumer-level hardware and a cheap software defined radio dongle.

    Looks like the encryption algorithm was intentionally weakened by intelligence agencies to facilitate easy eavesdropping.

    Specifically on the researchers’ claims of a backdoor in TEA1, Boyer added “At this time, we would like to point out that the research findings do not relate to any backdoors. The TETRA security standards have been specified together with national security agencies and are designed for and subject to export control regulations which determine the strength of the encryption.”

    And I would like to point out that that’s the very definition of a backdoor.

    Why aren’t we done with secret, proprietary cryptography? It’s just not a good idea.

    Details of the security analysis. Another news article .

    • chevron_right

      Asymmetric Cryptographic Commitments

      pubsub.slavino.sk / dholecrypto · Monday, 3 April, 2023 - 15:43 edit

    Recently, it occurred to me that there wasn’t a good, focused resource that covers commitments in the context of asymmetric cryptography. I had covered confused deputy attacks in my very short (don’t look at the scroll bar) blog post on database cryptography., and that’s definitely relevant. I had also touched on the subject of commitment […]

    Značky: #Cryptography, #Network, #cryptography, #AEAD, #commitments

    • chevron_right

      Lost and found: Codebreakers decipher 50+ letters of Mary, Queen of Scots

      news.movim.eu / ArsTechnica · Wednesday, 8 February, 2023 - 00:01 · 1 minute

    Sample ciphertext (F38) found in the archives of the Bibliothèque Nationale de France, now attributed to Mary, Queen of Scots.

    Enlarge / Sample ciphertext (F38) found in the archives of the Bibliothèque Nationale de France, now attributed to Mary, Queen of Scots. (credit: Bibliothèque nationale de France)

    An international team of code-breakers has successfully cracked the cipher of over 50 mysterious letters unearthed in French archives. The team discovered that the letters had been written by Mary, Queen of Scots, to trusted allies during her imprisonment in England by Queen Elizabeth I (her cousin)—and most were previously unknown to historians. The team described in a new paper published in the journal Cryptologia how they broke Mary's cipher, then decoded and translated several of the letters. The publication coincides with the anniversary of Mary's execution on February 8, 1587.

    "This is a truly exciting discovery," said co-author George Lasry , a computer scientist and cryptographer in Israel. "Mary, Queen of Scots, has left an extensive corpus of letters held in various archives. There was prior evidence, however, that other letters from Mary Stuart were missing from those collections, such as those referenced in other sources but not found elsewhere. The letters we have deciphered are most likely part of this lost secret correspondence.” Lasry is part of the multi-disciplinary DECRYPT Project devoted to mapping, digitizing, transcribing, and deciphering historical ciphers.

    Mary sought to protect her most private letters from being intercepted and read by hostile parties. For instance, she engaged in what's known as " letter-locking ," a common practice at the time to protect private letters from prying eyes. As we've reported previously , Jana Dambrogio, a conservator at MIT Libraries, coined the term "letter-locking" after discovering such letters while a fellow at the Vatican Secret Archives in 2000.

    Read 14 remaining paragraphs | Comments

    • Sc chevron_right

      Breaking RSA with a Quantum Computer

      news.movim.eu / Schneier · Thursday, 12 January, 2023 - 18:51 · 4 minutes

    A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. This is something to take seriously. It might not be correct, but it’s not obviously wrong.

    We have long known from Shor’s algorithm that factoring with a quantum computer is easy. But it takes a big quantum computer, on the orders of millions of qbits, to factor anything resembling the key sizes we use today. What the researchers have done is combine classical lattice reduction factoring techniques with a quantum approximate optimization algorithm. This means that they only need a quantum computer with 372 qbits, which is well within what’s possible today. (The IBM Osprey is a 433-qbit quantum computer, for example. Others are on their way as well.)

    The Chinese group didn’t have that large a quantum computer to work with. They were able to factor 48-bit numbers using a 10-qbit quantum computer. And while there are always potential problems when scaling something like this up by a factor of 50, there are no obvious barriers.

    Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics. And there’s the nagging question of why the Chinese government didn’t classify this research. But…wow…maybe…and yikes! Or not.

    Factoring integers with sublinear resources on a superconducting quantum processor

    Abstract: Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglogN ), which is sublinear in the bit length of the integer N , making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.

    In email, Roger Grimes told me: “Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers…but reviewers found a flaw in his algorithm and that guy had to retract his paper. But this Chinese team realized that the step that killed the whole thing could be solved by small quantum computers. So they tested and it worked.”

    EDITED TO ADD: One of the issues with the algorithm is that it relies on a recent factoring paper by Claus Schnorr. It’s a controversial paper; and despite the “this destroys the RSA cryptosystem” claim in the abstract, it does nothing of the sort. Schnorr’s algorithm works well with smaller moduli—around the same order as ones the Chinese group has tested—but falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think that’s what’s behind Grimes’s comment) but don’t give any details—and they haven’t tested it with larger moduli. So if it’s true that the Chinese paper depends on this Schnorr technique that doesn’t scale, the techniques in this Chinese paper won’t scale, either. (On the other hand, if it does scale then I think it also breaks a bunch of lattice-based public-key cryptosystems.)

    I am much less worried that this technique will work now. But this is something the IBM quantum computing people can test right now.

    EDITED TO ADD (1/4): A reporter just asked me my gut feel about this. I replied that I don’t think this will break RSA. Several times a year the cryptography community received “breakthroughs” from people outside the community. That’s why we created the RSA Factoring Challenge: to force people to provide proofs of their claims. In general, the smart bet is on the new techniques not working. But someday, that bet will be wrong. Is it today? Probably not. But it could be. We’re in the worst possible position right now: we don’t have the facts to know. Someone needs to implement the quantum algorithm and see.

    EDITED TO ADD (1/5): Scott Aaronson’s take is a “no”:

    In the new paper, the authors spend page after page saying-without-saying that it might soon become possible to break RSA-2048, using a NISQ (i.e., non-fault-tolerant) quantum computer. They do so via two time-tested strategems:

    1. the detailed exploration of irrelevancies (mostly, optimization of the number of qubits, while ignoring the number of gates), and
    2. complete silence about the one crucial point.

    Then, finally, they come clean about the one crucial point in a single sentence of the Conclusion section:

    It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.

    “Unclear” is an understatement here. It seems to me that a miracle would be required for the approach here to yield any benefit at all, compared to just running the classical Schnorr’s algorithm on your laptop. And if the latter were able to break RSA, it would’ve already done so.

    All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many.

    EDITED TO ADD (1/7): More commentary . Again: no need to panic.

    EDITED TO ADD (1/12): Peter Shor has suspicions .

    • chevron_right

      What We Do in the /etc/shadow – Cryptography with Passwords

      pubsub.slavino.sk / dholecrypto · Thursday, 29 December, 2022 - 15:44 edit

    Ever since the famous “Open Sesame” line from One Thousand and One Nights, humanity was doomed to suffer from the scourge of passwords. Even in a world where we use hardware tokens with asymmetric cryptography to obviate the need for passwords in modern authentication protocols, we’ll still need to include “something you know” for legal […]

    Značky: #Cryptography, #Network, #OPAQUE, #PBKDF2

    • chevron_right

      Extending the AES-GCM Nonce Without Nightmare Fuel

      pubsub.slavino.sk / dholecrypto · Wednesday, 21 December, 2022 - 19:11 edit

    When it comes to AES-GCM, I am not a fan. Most of my gripes fall into one of two categories: However, one of my gripes technically belongs in both categories: The small nonce size, which is caused by AES’s block size, limits the amount of data you can safely encrypt with a single symmetric key. […]

    Značky: #cryptography, #AES-GCM, #XChaCha20, #Network, #Cryptography

    • chevron_right

      It took nearly 500 years for researchers to crack Charles V’s secret code

      news.movim.eu / ArsTechnica · Tuesday, 29 November, 2022 - 20:48 · 1 minute

    Researchers have finally cracked the secret code of this 1547 letter from Holy Roman Emperor Charles V to his ambassador.

    Enlarge / Researchers have finally cracked the secret code of this 1547 letter from Holy Roman Emperor Charles V to his ambassador. (credit: Bibliotheque Stanislas de Nancy)

    In 1547, Holy Roman Emperor Charles V penned a letter to his ambassador, Jean de Saint-Mauris, part of which was written in the ruler's secret code. Nearly five centuries later, researchers have finally cracked that code , revealing Charles V's fear of a secret assassination plot and continued tensions with France, despite having signed a peace treaty with the French king a few years earlier.

    The future Holy Roman Emperor was born in 1500 to Philip of Hapsburg and Joanna of Trastamara—daughter of Ferdinand II of Aragon and Isabella I of Castile in Spain. She was nicknamed "Joanna the Mad" because of her rumored mental illness and actually gave birth to Charles in a bathroom in the wee hours because she insisted on attending a ball despite clearly having labor pains. Generations of inbreeding conferred on Charles an enlarged jaw (mandibular prognathism), a condition that later became known as "Hapsburg jaw," since it became even worse in subsequent generations. Charles also suffered from epilepsy and gout; the latter became so severe late in life that he had to be carried around in a sedan chair.

    Charles V began inheriting various family titles at a young age, and his dominion eventually encompassed the Holy Roman Empire—which extended from Germany to northern Italy in the early 16th century and included Austrian hereditary lands, the Burgundian states, and the Kingdom of Spain. During his reign, he continued the Spanish colonization of the Americas and embarked on a short-lived German colonization effort, earning the label "the empire on which the sun never sets." As his health deteriorated, Charles V abdicated as emperor in favor of his brother Ferdinand in 1556, although it was not legally recognized until February 1558. He retired to the Monastery of Yuste in 1557 and died the following September.

    Read 6 remaining paragraphs | Comments