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 …

  1. captain_solo

    This is why you have to know your threat model. I understand and accept that much of what I consider "encrypted" in my daily internet use, from SSL to something like Signal even, is probably not secure from a determined state actor who is targeting my traffic. There is mathematics knowledge in the Cryptonomicon of the U.S. Intel agencies that has never been revealed and likely only shared maybe with the U.K. given the nature of the relationship there since WWII efforts to defeat encryption.

    The resistance to end to end encryption by these entities means they likely can't decrypt en masse probably because of processing requirements, but if you are a target they can spend a little processor time on, assume they have some of these tricks buried in the algorithms to ensure they can reverse most commercially available implementations.

    I assume also that other nation-states have similar if not equal capabilities, although they probably have less leverage to incorporate such backdoors into commercial products than the U.S. since the game was pretty much invented here.

    1. Anonymous Coward
      Anonymous Coward

      OK, so let's assume I know my threat model.

      Now I'm passing encrypted data but the algorithm has got a back-door (mathematical in the is case). Surly the main problem is that once the "key" leaks from government then my messages are no longer secure.

      It doesn't matter what the back-door mechanism is, once it becomes known it will be exploited and the exploits will become common place... or have I missed something?

      1. Yet Another Anonymous coward Silver badge

        It is more likely that a deliberate weakness in the algorithm makes it easier ie practical for a nation state to crack rather than just a magic backdoor key that decrypts all the data.

    2. The Man Who Fell To Earth Silver badge
      Black Helicopters

      The resistance to end to end encryption by these entities

      The resistance to end to end encryption by these entities would be there regardless of whether they can easily intercept & decrypt en masse. A couple of reasons come to mind, and I'm sure there are others:

      1. Intercepting & decrypting en masse would be even easier with official backdoors.

      2. Dropping opposition to end-to-end encryption would let everyone know you can already intercept & decrypt en masse.

      1. CommanderGalaxian
        Black Helicopters

        Re: The resistance to end to end encryption by these entities

        Exactly. That's why the likes of UK Gov greet about how unfair it is that ordinary folks use cryption like WhatsApp. Because WhatsApp is already well rogered.

    3. Anonymous Coward
      Anonymous Coward

      This is why you have to know your threat model. I understand and accept that much of what I consider "encrypted" in my daily internet use, from SSL to something like Signal even, is probably not secure from a determined state actor who is targeting my traffic

      Here's a fun question: why would you trust a FreeSSL cert when generation and root cert is in the hands of a US company? Yet they are *everywhere*. Well done..

      1. Anonymous Coward
        Anonymous Coward

        Re: fun question

        Using FreeSSL or any other CA doesn’t expose your private key, so encryption is unaffected.

        Where your choice of CA matters is around trust - will the CA issue a certificate to a third party that allows the third party to impersonate you? HSTS/certificate pinning helps to address this.

      2. Anonymous Coward
        Anonymous Coward

        Re Fun question

        Ref Fun Question:

        Lots of websites don't use encryption to encrypt, they use it to avoid being demoted/flagged by Google and the other browser manufacturers. Some that do use it for encryption use it only to demonstrate good practice to their customers and to avoid falling prey to the non-state eavesdropper which is fair enough.

        I'm not advocating 'casual' use of encryption here (selection / configuration of ciphers, operational management) but there are myriad reasons people use encryption that are not driven by threat modelling, paranoia or distrust in government.

    4. Anonymous Coward
      Anonymous Coward

      OpenBSD

      This makes me wonder if the standard version of OpenBSD is still restricted for usage in the USA?

      and in answering my own question:

      from the website - https://www.openbsd.org/cvsync.html - and at the very bottom of this link.

      "IMPORTANT NOTE: There are a few issues relating to cryptographic software that everyone should be aware of:

      The OpenBSD sources are from Canada. As researched by a Canadian individual and as described in the Export Control list of Canada, it is legal to export crypto software from Canada to the world.

      However, if you are outside the USA or Canada, you should not fetch the cryptographic sections of the OpenBSD sources from a CVSync server located in the USA. The files in question are...

      src/kerberosIV/*

      src/kerberosV/*

      src/lib/libdes/*

      src/lib/libc/crypt/crypt.c

      src/lib/libc/crypt/morecrypt.c

      src/sys/crypto

      src/sys/netinet

      src/usr.sbin/afs/src/rxkad/*

      Because of the USA ITAR munitions list, crypto software may only be exported to Canada from the USA."

    5. Anonymous Coward
      Anonymous Coward

      Whilst it is certainly an interesting piece that has been presented I have to wonder how long it will be before such back-doors, if they exist, become known? If they are there then I would expect that at some point someone gains a conscience and releases the information. It's not like you need to extract reams of data like Snowden, you simply have to publicise "algorithm XYZ has a known exploitable weakness ABC built in". In the end it does seem that all information wishes to be free.

  2. cbars

    National products

    So what does the UK use? I'd like to know what to recommend instead of AES.

    Edit: found it, it's AES

    https://www.ncsc.gov.uk/guidance/tls-external-facing-services#profiles

    Ha

    1. Anonymous Coward
      Anonymous Coward

      Re: National products

      @cbars

      I suggest you go spend some time in the company of Mr Google before making such stupidly misinformed comments.

      What does the UK government use ?

      Well, for stuff up to RESTRICTED marking (i.e. annoying if it became public, but not the end of the world), UK gov can use whatever they like, and AES just happens to be handy.

      For stuff beyond RESTRICTED that would cause serious headaches if it became public, UK government has a range of secret-squirrel algorithms developed by the great minds of the doughnut-shaped mathematicians.

      1. Anonymous Coward
        Anonymous Coward

        Re: National products

        "RESTRICTED"? That dates you.

        1. Anonymous Coward
          Anonymous Coward

          Re: National products

          Well at least I know there is more to UK government encryption than meets the eye.

          I can't believe you seriously thought they used AES ... haha !

        2. Steve Davies 3 Silver badge

          Re: National products

          In some HMG departments, the Weather forecast is 'restricted' even though it is publicly available.

          Those departments classify everything because it creates jobs for the great and worthy.

      2. cbars

        Re: National products

        Hi A.C.

        Bit rude.

        Note the "ha" at the end of my post. Think about it for a second.... cool, so we understand each other :)

        Chill out, you are a grown human, after all. Me and DuckDuckGo are good friends, and his dad is bigger than your dad.

      3. Mark 65 Silver badge

        Re: National products

        When I read

        Serious countries (USA, UK, Germany, France) do not use foreign algorithms for high-security needs. They mandatorily have to use national products and standards (from the algorithm to its implementation),” he added.

        I wondered whether they use these mysterious other algorithms because they are

        1. Stronger, or

        2. They have a known flaw in them allowing the country's spy agency to be able to track and decrypt information being leaked to the enemy.

        There are valid reasons for both.

  3. 's water music Silver badge
    Big Brother

    turning it up to 11

    So could you not use double pass encryption using algorithms from two (or more) different geo-political blocs (obvs not two that both mandate ROT13...)?

    Semi-serious question.

    1. Charles 9 Silver badge

      Re: turning it up to 11

      Difficult to say, but based on what we know of chaining hashing algorithms, you may end up with a counterintuitive result of making it easier to crack your ciphertext rather than harder since most encryption works on similar fundamental principles that can result in common modes of exploitation. Even the one-time pad has its weaknesses. They could intercept your pad or determine where the ciphertext is being transmitted and mess with it to de-synchronize you.

      1. Doctor Syntax Silver badge

        Re: turning it up to 11

        "based on what we know of chaining hashing algorithms, you may end up with a counterintuitive result of making it easier to crack your ciphertext"

        Nevertheless it's something the theoreticians should be looking at.

        The critical point could be key exchange algorithms. It's not going to help if you have a very strong message encryption based on chaining algorithms from multiple sources if the key exchange is vulnerable.

  4. Reader2435

    Useful contribution by Mr Filiol... but I'm sure that safe backdoors could be put into crypto if we just use the right hashtags...

    Can I take up my seat in the house of commons now? Or did I prove myself over-qualified by getting his name right?

    1. Rich 11 Silver badge
      Joke

      Or did I prove myself over-qualified by getting his name right?

      Your application for a seat has been rejected on the grounds that you listened to an expert who is not just clearly an expert but also clearly foreign.

  5. PyLETS
    Meh

    Bank Vault locks - cardboard doors

    Perhaps the cryptographic equivalent of bank vault locks can be got through by the tiny elite likely to be in the know, but why would anyone bother most of the time ?

    Those who hold such high value secrets (i.e. knowledge of algorithm weaknesses) where these exist will want to use them very infrequently and against only the highest value targets for fear of disclosure through honeypot techniques and well tuned intrusion detection systems. It's all basic spy craft - those with high value sources protect these as much as they can which means most who could usefully know are denied access, information gained from these sources has to be very carefully guarded and sanitised prior to declassification and use, and the more use that is made will increase the probability that this kind of source gets disclosed sooner rather than later.

    Everything else will involve getting through the cardboard doors - the very many and various implementation weaknesses against which very few systems are likely to be properly protected. So I don't think I'll be rolling my own crypto or combining multiple forms of it or engaging in other obscurity exercises likely to fail when I'm not yet doing the thousand other things I'd have to do (including knowing all my chip technologies and binary device drivers and system software) to avoid the cardboard doors.

    The targets I have to defend just aren't valuable enough for me to worry about algorithms no-one has yet discovered unsafe despite large prizes for effective attacks being on offer for those who try to discover these backdoors.

    1. Yet Another Anonymous coward Silver badge

      Re: Bank Vault locks - cardboard doors

      The problem is that those who hold the high value secrets might know this but their bosses have a timeline of the next prime ministers questions.

      Would it be worth risking a backdoor into AES to get some dirt on the EU Brexit negotators? What about on the DUP - that should be worth a £Bn. Or the 11 rebel MPs ?

      1. PyLETS

        Re: Bank Vault locks - cardboard doors

        "The problem is that those who hold the high value secrets might know this but their bosses have a timeline of the next prime ministers questions."

        This is probably why those in the know seem unlikely to want to include politicians within their inner circle.

  6. fishman

    Backdoors

    If there are backdoors put in, who will hold the backdoor keys? Even the NSA has leaks.

    1. Charles 9 Silver badge

      Re: Backdoors

      But not necessarily at the top levels, unless you can prove otherwise.

      1. Gio Ciampa

        Re: Backdoors

        A leak is a leak is a leak - who cares what level it originates from?

        1. Charles 9 Silver badge

          Re: Backdoors

          It determines the sensitivity of the intel which leaks (and by extension how paranoid they are about it). The difference between interfering with routine operations and possibly triggering World War III.

    2. CommanderGalaxian
      Black Helicopters

      Re: Backdoors

      "Even the NSA has leaks."

      The likes of the NSA and GCHQ will have millions of secrets - and yet how often are there actual leaks? Next to never. People who apply for these jobs like keeping secrets - they like operating in a grey area of moral ambiguity. These organisations screen people to ensure the likelyhood of those they employ becoming a whistleblower are tiny.

      And when leaks do occur - it tends to have life changing consequences for the leaker - think Manning and Snowden.

  7. This post has been deleted by its author

    1. This post has been deleted by its author

  8. Voland's right hand Silver badge

    Slightly more complicated as far as AES is concerned

    AES is a result of an open competition and was not designed in USA. It was designed in Belgium. While it is theoretically possible that the two cryptography researchers who came up with it are a NSA plant and it has an existing hole, I find this idea a bit too far fetched. Very far fetched. In fact so far fetched that whoever came up with needs to share what they are smoking.

    AES and its standardization process, however, are one of the exceptions on the cryptography scene. It happened during a short lull in-between the insanity storms. We have regressed since and quite a bit almost back to the days of the Clipper chip adn 40 bit export level DES.

    I suspect the next candidate will be purely USA-based and will follow the same design pattern as the elliptic RNG and several other interesting NSA-advised NIST ideas which appeared after AES.

    1. This post has been deleted by its author

      1. Tomato42 Silver badge

        Re: Slightly more complicated as far as AES is concerned

        > known weakness in one of the S-Boxes in AES - this information is a while back and cannot recall the details.

        that's the first time I hear this...

        > I also recall someone stating that there is a vulnerability when using 256bit keys as opposed to 128bit keys ?

        that's a related-key vulnerability (it's easier to perform for AES-256 than it is for AES-128), if your keys come from a PRF (as they do in S/MIME, TLS and IPsec, among others), it's only of academic importance

        > With the recent BGP event, perhaps this is an indicator that our security is not as good as we believe ?

        BGP has no security, the problem is that it was designed at the time when it was not a problem, the world changed around it - but it's a problem as well known as the lack of security in HTTP

        1. Adam 1 Silver badge

          Re: Slightly more complicated as far as AES is concerned

          Weaknesses is too strong a word. Noone has (publicly admitted to) found an exploit, but the simplicity of theb fact that all the keys from all the rounds are derived from the single initial key is incredibly trivial and therefore can feel too good to be true.

          As an aside, this is one of the more accessible ways to explain AES.

          1. This post has been deleted by its author

  9. Anonymous Coward
    Anonymous Coward

    Hmmmmm

    The lack of anyone currently plugging BitCoin (other cryptocurrencies are available) to note this speaks volumes ...

  10. Mark 85 Silver badge

    The problem is normal, human paranoia and the for some value of normal urge to control others and/or monitor everything. We (the people) want our comms to be secure and private. Government has decided that because they can, everything should be slurped and stored "just in case". Some of it gets processed but most comms are just stored or so we've been told.

    There is two inherent issues thought... the old "if you have done nothing wrong, nothing to fear".. which is bull since everyone has done at least one or two things wrong. The other is the old "give me five lines and I'll find something to hang you with" thing. Do we want to continue living in the shadow of this? Or do we (here in the States) wish to continue to exercise our Constitutional rights to free and unfettered speech?

    I do believe that many of us are paranoid about comms for very valid reasons given the nature of governments (all of them) of late. And then there's the crims and financial gain....

  11. Anonymous Coward
    Anonymous Coward

    AES Backdoor...

    AES has a back door of sorts. AES was chosen over, say, Blowfish because AES is easier to implement in IoT (wasn't called that back then, but that is the idea). This is public knowledge.

    Well, NSA has its own fabs and can make billions of AES decryptors, so you know the routine.

    You don't need an idiot Filiol backdoor, just one that the NSA can use. In BEA-1 case, once you know the backdoor, for all intents and purposes the algorithm is broken; the break is simply too easy to implement.

    The main problem with Filiol et al premise is that they want a COMMON backdoor that is "easy" to use. This is logically equivalent to a promiscuous key-- once known, game over. There is no magic backdoor method in mathematics that is going to let Joe Plod read encrypted data easily yet prevents Jane Cracker from doing the same once the secret is out.

    1. This post has been deleted by its author

      1. This post has been deleted by its author

      2. Anonymous Coward
        Anonymous Coward

        Re: AES Backdoor...

        Yes, Reijndael was chosen for AES after an open competition (unless you believe in a Dutch conspiracy) as the best fast secure symmetric algo. You can find all the candidates and the analysis online. Not all processors have AES-specific instructions but there are a lot of MCUs that have them. ECIES is an asymmetric scheme, a very different fish. There are MCUs available for that now. What you will find is ECIES used as an AES key-transport mechanism. And yes, ECC is preferred over RSA in small devices.

        1. Anonymous Coward
          Anonymous Coward

          Re: AES Backdoor...

          Flemish, not Dutch.

      3. This post has been deleted by its author

      4. CrysTalK

        Re: AES Backdoor...

        I thought that AES was chosen since it was the best performance vs security, but was not chosen to be implemented on small devices due to its low processing requirement.

        ......

        I seem to recall that Elliptic Curve encryption is the chosen encryption for small devices since it is relatively secure and requires minimal processing to encrypt.

        AES = symmetric cipher (would use just a single key for encryption and decryption)

        Elliptic Curve =assymmetric cipher (uses 2 keys, a private and a public key)

        Wonder why you mixed and compared both when they're not the same.

    2. Sven Coenye

      Re: AES Backdoor...

      "The main problem with Filiol et al premise is that they want a COMMON backdoor that is "easy" to use"

      No. Filiol does not want that. He created a backdoor that is undetected by all current crypto validation tests, then asked "how do you know your current crypto algorithm does not already contain a similar thing?"

    3. Mark 65 Silver badge

      Re: AES Backdoor...

      Question - given the amount of, predominantly US designed, chips containing AES-NI style encryption assisting circuitry is it possible that AES is secure but Intel have kindly implemented the instruction set in such a way to given their buddies at the NSA a leg-up? The management chip and all its flaws also smacks of a helping hand.

  12. Anonymous Coward
    Anonymous Coward

    As I understand it and let me know if I'm wrong.

    In crypto the key changes so to have a master key it would also need a part that is always the same which then makes the crypto easy to break because when you initialise the crypto the same key would always be present and mathematically linked to the other key reducing the number of options for that key.

    1. Anonymous Coward
      Anonymous Coward

      Thanks for the down votes without explaining why I was wrong.

      So I looked up AES myself and rather than as I believed the key rotates between users the key stays the same and shuffles the data round based on the encryption key with the number of shuffles depending on the bit value for the key. That makes sense as to why it's difficult to crack but doesn't explain why it's not difficult to put a back door in? It also makes detecting the backdoor technically impossible as it would be the same process as trying to get the key in the first place so without it being leaked you wouldn't and couldn't know.

      So my next question is why can't you use rotating keys where it transforms with each transfer of data and the previous key is used to determine that transformation? Not only would you need to crack the original key but you would need every piece of data between the start and finish to decrypt it all.

      Again, if I'm wrong then please discuss as I'm trying to learn. Thanks.

      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.

  13. Anonymous Coward
    Anonymous Coward

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

  14. 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.

  15. aidanstevens

    We need to talk about...

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

  16. 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.

  17. 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?

  18. 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!

  19. 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 ;-)

  20. 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.

  21. 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.

  22. 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.

  23. 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.

  24. 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.

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