back to article We need to talk about mathematical backdoors in encryption algorithms

Security researchers regularly set out to find implementation problems in cryptographic algorithms, but not enough effort is going towards the search for mathematical backdoors, two cryptography professors have argued. Governments and intelligence agencies strive to control and bypass or circumvent cryptographic protection of …

Page:

      1. Anonymous Coward
        Anonymous Coward

        No~

        You seem to be describing Enigma? That was broken (in as much as the search space to decrypt it was reduced from the theoretical maximum, to one that could be searched by the comically slow computers of the time). Not quite sure how it was broken, some really smart Poles and us Brits somehow figured out how.

        But nope. One of the basic axioms of cryptography, is any question of the form 'Can't you just...' is very likely to have the answer 'no'.

        1. Anonymous Coward
          Anonymous Coward

          Re: No~

          But nope. One of the basic axioms of cryptography, is any question of the form 'Can't you just...' is very likely to have the answer 'no'.

          Only true when developing security. From an attack perspective 'Can't you just' is what seems to bring the biggest rewards. Most security holes tend to be the simple things from the news reports I read.

        2. Anonymous Coward
          Anonymous Coward

          Re: No~

          Not quite sure how it was broken, some really smart Poles and us Brits somehow figured out how.

          If memory serves me right, the poles obtained the first copy of the machine (not the naval version though). (*). The analysis of that showed several implementation weakness.

          The rest as they say is history. Most of it is well known, some not so much. One detail usually omitted by most historians was that the diplomatic cyphers of the Axis were broken by Great Britain even before the war started (I am going to leave some of consequences of that as food for thought).

          Bletchley park actively looked for cases where deciphered cyphertext from diplomatic dispatches was relayed for whatever reason to the Kriegsmarine or the Wermacht or vice versa and used it to speed up the search. This definitely happened during the battle of the Denmark straights (that one is documented). It also happened on many other occasions.

          (*)Similar story to WW1 where the Russian successfully obtained the German Navy codebooks within the first week of the war and shared them with Britain

        3. CommanderGalaxian

          Re: No~

          "Not quite sure how it was broken, some really smart Poles and us Brits somehow figured out how."

          An an Enigma machine was captured and they were able to see how the rotors worked - in essence they got hold of the source code - thus giving them a significant leg up.

          German operators were also often lazy - they didn't change their station identifiers and pre-amble greetings - in essence similar to using the same seed over and over again in a pseudo random number generator.

  1. Anonymous Coward
    Anonymous Coward

    Encrypt with AES, then with the Russian GOST and you are golden.

  2. DougS Silver badge

    Layered encryption

    If you used multiple algorithms wrapping each other it would be less efficient, but even if one had a backdoor you'd need a backdoor to all of them to get at the juicy plaintext.

    I've read claims that encrypting already encrypted content is somehow less secure than a single layer of encryption, but I've never seen anything to back up that claim. I suspect it is an "old wives tale" of cryptography, but if anyone can point to evidence it really is the case, please do so. Obviously if there's some "known plaintext" like in a header or something you'd remove that or obfuscate it in some way to prevent it being levered as a way of breaking its outer layer (t.b.h. the same potential known header issue exists with compressed files and tar files, but no one suggests an encrypted bzip2 or tar file is less secure...)

    1. Sven Coenye

      Re: Layered encryption

      That is essentially what 3DES was: content run through the 56 bit DES three times. DES was terminally compromised by 1998 yet 3DES is still in use.

      1. DougS Silver badge

        Re: Layered encryption

        DES was "terminally compromised" by an attack that reduced the effective key length of 56 bit DES to 40 bits which was crackable even in the late 90s. 3DES would have gone from an effective key length of 168 bits to 120 bits, which is still secure (note that these key lengths can't be compared to the key lengths of other schemes like AES where 120 bits would be useless)

        If there was a mathematical backdoor in DES, then triple DES wouldn't do much good. But if you encrypted with say 3DES, then AES, and finally Twofish, for example, then even if there were mathematical attacks against two of them, you'd be saved by the third.

        1. Anonymous Coward
          Anonymous Coward

          Re: Layered encryption

          DougS wrote:

          "3DES would have gone from an effective key length of 168 bits to 120 bits, which is still secure (note that these key lengths can't be compared to the key lengths of other schemes like AES where 120 bits would be useless)"

          3DES only doubled the effective key length - so it would go down to 112/80 bits (not 168/120).

          It is part of the classic problem that applying the encryption twice only gives you one extra bit of key-strength (due to a meet-in-the-middle attack).

        2. Wim Ton

          Re: Layered encryption

          Not exactly "terminally compromised". You need 2^47 chosen plaintext-ciphertext pairs to achieve this.

      2. Charles 9 Silver badge

        Re: Layered encryption

        Except the second 3DES step was a DEcryption precisely BECAUSE just encrypting three times introduced common-mode failures. And the reason for using 3DES was that technology of the time (90's) had DES built in but was not strong enough to do any better, so this was a stopgap that didn't require new hardware.

        1. Anonymous Coward
          Anonymous Coward

          Re: Layered encryption

          Charles9 wrote:

          "Except the second 3DES step was a DEcryption precisely BECAUSE just encrypting three times introduced common-mode failures."

          I thought that this was done so that using 3DES with the same key in both parts gave you DES - which was a boon for compatibility when needed. E(D(E(Text,Pwd),Pwd),Pwd) == E(Text,Pwd).

          [For proper 3DES it is E(D(E(Text,Pwd1),Pwd2),Pwd1)].

          1. Wim Ton

            Re: Layered encryption

            The other reason was, that it was not known at the time if DES was a group, so encrypting 3 times with 3 different keys would be equivalent to encrypting once with a different key.

    2. handleoclast Silver badge

      Re: Layered encryption

      There are some known problems with chaining encryption, even with different keys at each stage.

      The few that I know of involved repeated encryptions using the same algorithm. The obvious one is ROT-13: two rounds of ROT-13 don't make things more secure, precisely the opposite (toy example, but very easy to comprehend). Three passes through DES result in something easier to crack than a single pass. That's why 3DES used an encryption followed by a decryption (with a different key) followed by another encryption.

      The basic worry with repetitions of a single algorithm is that the algorithm might form the equivalent of a mathematical group. Like the ROT-13 example, but more complex. In such a case at best you gain nothing (encryption with k1 followed by encryption with k2 is the same as encryption with k3), and at worst the result is easier to crack.

      Chaining different algorithms with different keys is probably safer. Chaining different algorithms with the same key may not be. Probably is, but may not be.

      1. DougS Silver badge

        Re: Layered encryption

        Well if you used the same key then an attack on the outer layer of encryption that recovered the key would be sufficient to decrypt the entire thing. So obviously you'd need a separate key for each layer. In reality it would just be a longer combined key, which you'd split and use part of it for each layer.

  3. aidanstevens

    We need to talk about...

    We need to talk about news articles with the heading beginning "We need to talk about..."

  4. Anonymous Coward
    Anonymous Coward

    Chain algos together?

    Can't you just chain algorithms together? Assuming you never reveal any of the output from the intermediate steps, and treat the assembly as a black box that takes plain text and spits out cyphertext, wouldn't it become exponentially harder for the NSA to use any of their backdoors? Or require them to be able to backdoor every single crypto algorithm in the chain... so if even one is secure, the whole thing remains unbroken?

    In which case, pick an american one, a russian one, a chinese one... and assume none are cooperating.

    1. Voland's right hand Silver badge

      Re: Chain algos together?

      a russian one

      They also use AES. That is what GOST specifies at present. The differences where if memory serves me right in the preferred public/private key and sigs. I think GOST specified ElGamal, while we use mostly Diffie-Helman.

  5. Steve Knox

    Not A Backdoor

    how to exploit it to recover the 120-bit key in around 10 seconds with only 600kB of data (300kB of plaintexts + 300kB of corresponding ciphertexts)

    If they already have plaintexts, then this is NOT a backdoor.

    The point of a backdoor is to be able to decrypt a message (i.e, gain access to plaintext) without access to the original key. If you have the plaintext already, you're not looking for a backdoor, because you don't need it. For a backdoor to be considered reliable, it needs to be useful without ANY access to plaintext.

    Maybe this is just poor summation by the article author, but as presented in the article, this is a key-recovery algorithm/attack, not a backdoor.

    1. Milton Silver badge

      Re: Not A Backdoor

      I think you are only partly justified in saying that. Ofttimes a cryptographer*¹ has or guesses at a crib—some plain text he knows or shrewdly expects to have been included in the original message—and uses that as a lever to begin teasing out the key, thereafter decrypting the whole message. Indeed, feeding cribs into an adversary's information system can be helpful. Let Station X, known to be using Cipher69, learn of your grave concern about the ship "Wazottliqueeg" on its mission to deliver vital "Sponzagurgs" and hope that they soon after transmit a message to HQ (preferably triggering a chain of concerned conversations throughout their network) and you have seeded an unusual crib into his commo which just might help you crack his encryption.

      Pursuing that example a little further, if you have introduced yourself, or are aware of, mathematical weaknesses in Cipher69 (NOT the same as knowing the key or having an alternate key, something I think not all commenters here have understood: sorry) then you are in a vastly better position to use those weaknesses and the crib to prise open the whole caboodle.

      *¹ "Cryptographer" in this case being the mathematicians and coders who wrote a code-breaking program

    2. handleoclast Silver badge

      Re: Not A Backdoor

      If they already have plaintexts, then this is NOT a backdoor.

      You're missing the point: it's called a "known plaintext" attack. If you obtain sufficient plaintexts and corresponding ciphertexts encoded with the same key then weaknesses in the algorithm may allow you to determine the secret key using far less effort than brute force. Then the next ciphertext you see is easily deciphered, even if you don't have access to the corresponding plaintext.

      The backdoor is the bit in his algorithm that makes it easy to recover the key with only a small amount of plaintext data and corresponding ciphertext. Easy if you know about the backdoor, very difficult if you don't.

    3. John Smith 19 Gold badge
      Unhappy

      "If you have the plaintext already, you're not looking for a backdoor, "

      Not necessarily.

      The classic example of a "crib" was the Enigma work where they looked for radio station operators who ended their messages "Heil Hitler."

      Then you back convert it to get the settings for the whole message traffic from that site (or "node" in today's packet using world) for the period that code is valid for.

      Does anyone doubt such cribs exist today, either due to rules of an organization, or inserted automatically by the transmission software?

  6. StargateSg7 Bronze badge

    Even the old standby AES-256 has a "Technical Backdoor" which is a byproduct of it being based upon integer-based manipulation AND a basic factor of where MOST of the data that gets encrypted is ASCII 8-bit text or UNICODE 16-bit bit TEXT which TENDS to have vowels, consonants and other characters NUMERICALLY IN CLOSE PROXIMITY to each other.

    A group of students from the University of Toronto in 2016 were able to demonstrate using donated supercomputer time on an IBM Watson deep learning system that such encrypted data could be converted to Greyscale, RGB and YCC/TUV/YCbCr colour pixels in order to graphically isolate integer values that resulted when specific combinations of vowels and consonants (ASCII or UNICODE values) were encrypted using SPECIFIC non-random keys and non-random key lengths.

    They were able to take advantage of human password usage foibles to bring down the normally ASTRONOMICAL numeric combinations of AES from 2 to the 256th power down to under 2^128th power which is actually computationally doable on modern multi-GPU network-based encryption cracking systems. The IBM Watson system found evidence of quadratic curves, linear rising and reductions in values and simple curves when input data and specific key combinations were graphed as a colour or greyscale chart. The curves and linear values WERE ONLY VISIBLE when those keys and data were present. This enabled ISLANDS OF PROBABILITY to be derived so that more conventional brute force computations could concentrate on those "Islands of Probability" when determining which key ranges to start brute force attacks against.

    So long you have TRULY RANDOM FULL-WIDTH KEYS, then AES-256 is STILL good to go! ...BUT....if you use common words, number combinations and/or punctuation as your passcode, THEN you allow deep learning systems to find the POSSIBLE starting and ending points of specific and LIKELY letter/number/punctuation combinations where a brute force attack should be initiated.

    This is the nature of the beast for ANY type of integer-based and curve-based encryption and hashing algorithms such as Twofish, Blowfish CAAST, AES, SHA2/3, Elliptic Curve, etc. where you use non-random human-readable text-based keys. THEY CAN BE BROKEN! You MUST USE Shor's Algorithm Resistant encryption techniques such as Mult-variate, Lattice, etc which will even protect against newer Quantum Computing technology from breaking your encryption.

    While ALL encryption algorithms based upon integer/curve manipulation ARE eventually mathematically derivable...SOME algorithms are better than others. The Canadian-made CAAST-256 is great! AES-256 is great! And even Elliptic Curve is pretty good for MOST personal and commercial-level secrecy purposes.

    It's when you are protecting data against a TRULY LARGE AGENCY such as the NSA, MI6/MI5/GCHQ

    or the GRU ...THEN...you will have an uphill battle against organizations who can AFFORD to spend

    many months and many man-hours on breaking those codes with 20milliondollar supercomputers! Your average local or national police agency or local community government is HOPELESSLY UNABLE to crack even the waaaay-old Blowfish encryption algorithm!

    So go ahead and remember to use the FULL WIDTH of AES-256 with as much random encryption key combinations as humanly possible to remember without writing down and you are MOSTLY SAFE against data encryption breakage!

  7. Milton Silver badge

    Simplify and add lightness

    I am assuming that the emphasis on "mathematical backdoors" is strict, which means that we can analyse the issue without going down a level to the *implementation* of the math.

    A math backdoor is something we should be able to find by looking at the math itself, in the knowledge that if it were perfectly and without error implemented as algorithm and program code, the backdoor would still be there. We're NOT discussing deliberate wrinkles in the coding of the system. (If we do include those—think of an implementation that is deliberately careless with registers, for example—then I would have thought such failings would be discoverable by minutely comparing the *intention* of the math with the actuality of the code.)

    If it is a math-only issue, "simplify and add lightness" would seem to be particularly relevant, because the more complex the math, the easier it will be to hide weaknesses in the thicket. Whether it's elliptic curves or something else, we should be bearing down hard on the simplest solutions that do the job (and yes, I recognise that "simple" is relative in this case!)

    I guess I am a little surprised to have received the impression that we may be using algorithms whose fundamental math has not been exhaustively analysed, distilled and checked out by armies of brilliant sceptics ... hmm, if Bruce Schneier won't come along to this thread and make a post, I'm gonna have to go beard him in his lair ;-)

  8. Lars Silver badge
    Coat

    ESIEA

    ESIEA (university),

    The École supérieure d'informatique, électronique, automatique (ESIEA) is a French grande école for engineers. Its five-year general engineering program focuses in the field of Science and Technology in the Digital Computer, electronic and automatic.

  9. Anonymous Coward
    Anonymous Coward

    What is wrong with Enigma on Steriods?

    Take a large random number file Say (20Mb)

    Take a random BIT offset, XOR your message

    Repeat (say 4 times)

    Even if the Random number file is known, the encryption is of known difficulty to decrypt

    ~2^24 x 2^24 x 2^24 x 2^24

    No clever maths, known probability to break, fast to implement

    Or have I got my math wrong?

    1. Charles 9 Silver badge

      Re: What is wrong with Enigma on Steriods?

      That's why a One-Time Pad MUST be one time only. Reuse of ANY part allows for an analysis of the ciphertext to locate common mode features which will stand out if you say plot it as a bit mapped picture.

      1. Panicnow

        Re: What is wrong with Enigma on Steriods?

        But the 4x offset neutralises that attack to the point that the "one-time-pad" can be public!

        1. Charles 9 Silver badge

          Re: What is wrong with Enigma on Steriods?

          No it doesn't. Checking for reuse of a one-time pad is extremely trivial (you can simply XOR two ciphertexts against each other IIRC), meaning it's possible to check for offsets and steps pretty quickly, too. That's why I mentioned bitmap analysis, which makes it easy to visually spot these flaws. Otherwise, re-usable pads would've already been endorsed.

  10. John Smith 19 Gold badge
    Unhappy

    Note the argument about the default RSA algo is *not* the same.

    It was known (by anyone bothering to check) that the default RSA RNG was less secure than it could be.

    The NSA were relying on people trusting RSA to set up the most secure algo by default.

    This is not a "Backdoor" in the conventional sense. You don't get a "Magic key" that you run over all the encrypted data and it "magically" decodes.

    Instead you get a process that, when given a chunk of encrypted data and the matching plaintext, can cough up the key the rest of the encrypted data, trading a shortish chunk of computation with the ability to bypass any future encryption.

    So would a "statistical" test actually find such a weakness to begin with?

    His argument is that "absence of evidence is not evidence of absence" and that's true. The question is of course do the TLA's have tools that create apparently secure algorithms which are actually quite vulnerable.

  11. Sproggit

    A Matter Of Perspective

    One of the things that is all too easy to overlook when considering "safe" cryptographic algorithms from unsafe ones is that, fundamentally, this can simply be a matter of perspective.

    I recall the anecdote from the development of the 3DES algorithm. Triple-DES, or 3DES, is a block cipher, meaning that it takes messages, "chunks" them into fixed-lengths blocks, then encrypts the payload.

    When the algorithms were being developed, a shortlist [I think it was a set of four] were provided to the NSA for review and comment. After a relatively brief interval, the response came back, "You can use these three, but not this one..." The submitters were baffled: they had tried their best and honestly felt that each of the submitted candidates were as good as the rest.

    *Years* later - having been given the enormously helpful clue from the NSA that there might be something suspect with #4, a flaw was found.

    This anecdote is relevant here because it shows that what even a well-practiced security researcher can think of as robustly secure can yield to the level of scrutiny that the likes of NSA and GCHQ can bring to bear. This isn't to say that in many [most] cases that extrinsic, peripheral or side-channel data won't be instrumental to a successful crack, only that 99.999% of us [and I include myself in that category] simply can't comprehend the resources and abilities that defence agencies can bring to bear if they so choose.

    My 2 cents: work on the basis that everything you exchange cryptographically can be read with relative ease and you won't be too far wrong.

    1. Charles 9 Silver badge

      Re: A Matter Of Perspective

      "My 2 cents: work on the basis that everything you exchange cryptographically can be read with relative ease and you won't be too far wrong."

      But that's essentially DTA Mode, which means you can't get anything done. So like I said, you eventually have to place your trust in something just to get through the day.

  12. Anonymous Coward
    Anonymous Coward

    Why the focus on PUBLIC and MATHEMATICAL methods?

    Why the focus on mathematical methods for encryption (like RSA or PGP)? What if Alice and Bob have created a word substitution cipher based on some unknown dictionary? This would only be useful for ascii text messages, but I guess that covers quite a lot of ground!

    *

    Here's an example of a message encoded with a private word substitution method. Please let me know what it says....

    *

    unquadded Ivesdale blackcock stroma Unona chenfish Cassiope mesmerizable viduation arthrosporous restraints catechist yabbi EUUG mid-wicket incapacitator orthoxazin glyptology cymbalom divert Gallicolae augurs forepassed rain-soaked languet Hessler unbannered overtopping chevalier lumen hout alada Merras Noxapater macaroon shutdown viscerating Frederico cider thioarsenic virologies clerico-political dull-eared nonprogrammable caulking prerecording Bisaltae cod-bait bisonant Hephaesteum veinier unsententiousness muvule Gadswoons weak-kneedness mavens scandinavia courlan tunicary Aflex Fonteyn overapprehended -mony Phelgen looks sympiesometer chiccories conduplicate acidophilus Landbert preleased commercialised periclean goyazite cordonazo acetates bewitchingness noseherb pomeria faker-out grub-street prelection tallitim ideas unquerulousness Cinclidotus gardener Mustelus orchotomy khoums knightliness nacket information intimado helpful Klangfarbe disciplinableness paxilla moile dilling mercantilism dumby extrorsal planirostal pyrophanite Wendell Haute-Normandie old-time matgrass Elijah

    1. Charles 9 Silver badge

      Re: Why the focus on PUBLIC and MATHEMATICAL methods?

      That requires keeping a pad or the like, and the plods can simply seize the pad (by seizing EVERYTHING).

      1. Anonymous Coward
        Anonymous Coward

        Re: Why the focus on PUBLIC and MATHEMATICAL methods?

        @Charles_9

        I'm not sure that your comment makes sense....."the Plods" would also seize the private keys for any other type of secret messaging.

        *

        cyclopaedias Robert squattingly syllabary aggregates cornets Ause one-chambered editorializations Rif haemoglobic Eleanore backscraper repentantly saskatoon straddle-fashion sugat colibertus bilobular asymbolical atactic apostolical stiff-horned Flathead chacate termor Merri Tzapotec OOP boondoggle ugly-tempered nonimmateriality interrogatives potlines macaroon shutdown incremented beduke phosphore thioarsenic virologies sawney trullization nympheum inorganity indyl dainty-toothed bongo trapezing yodles Rhabdomonas Gekkota Kawkawlin spermo- forefoot katogle submucosae gravilea bowlder micromyeloblast polonian hangment furnaces Hagood lithotripsy amenuse reoccurred Huang

        *

        1. Charles 9 Silver badge

          Re: Why the focus on PUBLIC and MATHEMATICAL methods?

          Except they can't seize something that ONLY exists in your head. Last I checked, they don't have anything resembling an Alpha Catch, Aurora Chair, or any other "brain draining" technology.

    2. CommanderGalaxian
      FAIL

      Re: Why the focus on PUBLIC and MATHEMATICAL methods?

      "What if Alice and Bob have created a word substitution cipher based on some unknown dictionary? "

      Effectively what you are describing is a one-time pad - or in this case a one-time dictionary.

      Fine if you only ever encrypt one message with it using that dictionary just once. But once you use that same dictionary for several messages. you run into the bog standard problems you get with any substitution cipher - i.e. letter frequency and word frequency.

Page:

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2019