back to article 128-bit crypto scheme allegedly cracked in two hours

Crypto researchers are preparing to scatter the ashes of a class of Discrete Logarithm Problems (DLPs) as the future of security, following a claim by Swiss researchers to have cracked a 128-bit crypto scheme in two hours. So as not to frighten the horses, The Register will start by pointing out that our understanding of this …

COMMENTS

This topic is closed for new posts.
  1. Sceptic Tank Silver badge
    WTF?

    Right on, man!

    "Since asymptotically more efficient techniques can be brought to bare as bit lengths increase, we conclude that small characteristic pairings at all security levels should now be regarded as completely insecure.”

    ...

    Ok, insecure. Got that.

    1. Anonymous Coward
      Anonymous Coward

      And the obvious error in that sentence is ...

      It should be "bear" rather than "bare", I would guess.

      (The local cable television company once sent me brochure in which, according to the description of their soft-porn channel, the young women in their programming "bear all". I wasn't quite sure whether that was an error.)

      1. tony2heads

        Re: And the obvious error in that sentence is ...

        No they carry stuff around AND behave like ursines

        1. Anonymous C0ward

          Re: And the obvious error in that sentence is ...

          But do they sh*t in the woods?

          1. Anonymous Coward
            Gimp

            Re: And the obvious error in that sentence is ...

            Actually, from the titles of most tv-porn (for which I don't pay so only see the titles/descriptions) 'bear' is probably the correct spelling of the correct word. Some people have to do 'anything' for money.

        2. Robin

          Re: And the obvious error in that sentence is ...

          "No they carry stuff around AND behave like ursines"

          It's true, I've seen plenty of such material involving people ursinating.

  2. Jonski

    Better password needed

    Than '123456'.

    1. frank ly

      Re: Better password needed

      123456 isn't a prime number so if course it's not secure. (I may be getting confused here.)

      1. d3rrial

        Re: Better password needed

        And even if he had said 123457 which is prime it wouldn't be a secure number to base your elliptic curve / discrete log. security on. The primes for these methods have to be HUGE numbers, usually 1024 bit and longer.

        But I think your pre-poster was confusing password schemes with general cryptographic schemes.

        1. Anonymous Coward
          Anonymous Coward

          Re: Better password needed

          "But I think your pre-poster was confusing password schemes with general cryptographic schemes."

          No, I think he was exhibiting something called irony. A concept which it seems is not well understood by a lot of people on El Reg.

          1. Dr Patrick J R Harkin

            Re: Better password needed

            "No, I think he was exhibiting something called irony. "

            That's like silvery, isn't it? Only cheaper?

  3. Jolyon Ralph

    94.6 bits

    How on earth can you have .6 of a bit?

    All this new fangled computer technical speak is making me feel very old.

    In my day if you had 128 bits of space for your program you were happy

    1. Anonymous Coward
      Anonymous Coward

      Re: 94.6 bits

      Wondering the same myself, it must be some typo perhaps it should be 96bits as that makes more sesnse.

      1. d3rrial

        Re: 94.6 bits

        It does make sense in cryptography. 94.6 bits of security / entropy doesn't mean actual bits implemented in hardware. It's a mathematical / statistical - value / factor. As in "more secure than 94 bits, but less secure than 95 bits".

    2. Longrod_von_Hugendong
      Coat

      Re: 94.6 bits

      Is that the BRMB of bits? (I am sure BRMB was on 96.4, its a Birmingham radio station that doesn't exist anymore...)

      YMMV on this joke...

    3. BlueGreen

      Re: 94.6 bits

      Like you can have 2.4 children (on average).

      Put another way, if you have 2 bits you have 00 / 01 / 10 / 11 which = 4 combinations. If I only want to store gender flag as male / female / unknown I can map those to 00 / 01 / 10 with 11 left over. So for gender I need more than one bit but not *all* of 2 bits' worth of encoding. So it might take 1.5 bits[**].

      What can we do with the remaining 0.5 bits? Can we use it? Yes. If we had another 3-option field, say marital status, as single / married / divorced, we could use 2 bits for that as well ie 00 / 01 / 10 with 11 left over so overall we now have 2 bits for gender + 2 bits for status = 4 bits overall.

      However if we combined them we have 9 combinations of gender X marital status = 9 options. Now this is a bad example (sorry) as you can't *quite* get that into 3 bits (8 combinations) but with a better one that I don't have time to do, you can see how it would work. So you can 'share' parts of a bit, combining them up into whole bits to actually use them.

      [**] for example. The figure's probably different as it's a log thingy but you get the idea.

      1. Steven Roper
        Joke

        @BlueGreen Re: 94.6 bits

        "So for gender I need more than one bit but not *all* of 2 bits' worth of encoding. So it might take 1.5 bits"

        Except that in these margin times with all the gender-fluid/gender-diverse options demanded by some ("otherkin/beast male-psyche femme-presenting" etc. etc.) you now need at least 16 bits to store all the possible gender variations people come up with!

        Admittedly, your two bits can at least serve for those who are genuinely gender-diverse: unknown/male/female/transgender fits perfectly.

    4. Phil Endecott

      Re: 94.6 bits

      > How on earth can you have .6 of a bit?

      Well, for example, one decimal digit stores log2(10) = 3.322 bits of information.

      So you could say that a 10-digit decimal number is "33.22 bits".

      Look up "Arithmetic Coding" for one practical application of fractional bits.

      1. Sir Runcible Spoon
        Joke

        Re: 94.6 bits

        So how does this affect my 5.1 surround sound?

    5. Anonymous Coward
      Coat

      Re: 94.6 bits

      Easy it's quatum computing. On, Off and a little bit inbetween.

    6. Anonymous Coward
      Anonymous Coward

      Re: 94.6 bits

      If you have N bits, there are 2^N states. It's possible to have systems with a number of states that's not an integer power of 2. Hence fractional bits.

    7. Rick Giles
      Coat

      Re: 94.6 bits

      There used to be a really good rock station on 94.6...

  4. Pascal Monett Silver badge
    Coat

    Nice to know

    It's nice to know that there are still some seriously intelligent people on this planet.

    Too bad for curvy ellipses then, I'll just be happy to still find them in magazines.

    What ? The door ? Oh. Right.

  5. John Smith 19 Gold badge
    Joke

    Welcome

    The Advanced Advanced Encryption Standard.

    1. Anonymous Coward
      Anonymous Coward

      Re: Welcome

      No idea why you got a down vote, either the Joke icon wasn't obvious enough, the joke was so bad it deserved one, or proving the point, geeks have absolutely no sense of humour..

  6. Matt Bryant Silver badge
    Facepalm

    Too smart for their own good?

    It seems so many modern cryptologist get enamoured with 'pretty maths' and the power of supercomputers and just don't think beyond how 'clever' their solution appears to them. Maths should not be the be all and end all of security. After all, there were no supercomputers and very little 'pretty maths' about in India back in 2000BC, but all our modern-day clever mathematicians and their pattern-matching supercomputers still can't decipher the Indus Script.

    1. Anonymous Coward
      Anonymous Coward

      Re: Too smart for their own good?

      The problem with the Indus Script isn't pattern matching but rather figuring out the rules of the script: something that is more akin to cryptanalysis and something that requires something more than a discrete computer to figure out.

      It also doesn't help that Indus Script is so brief (lending very little material for research) and so isolated (nothing like a Rosetta Stone to help bridge to another language).

      1. Matt Bryant Silver badge
        Stop

        Re: Anon Cluetard Re: Too smart for their own good?

        "The problem with the Indus Script isn't pattern matching but rather figuring out the rules of the script....." Which implies their 'rules' are a lot better than 'pretty' mathematical solutions. Instead of thinking only in terms of maths, which will always just result in a mathematical task to break the cypher, maybe we should be a bit more imaginative.

        "....It also doesn't help that Indus Script is so brief...." Whilst the instances are indeed short samples, there have been over 4000 examples of the script found. Please try a different excuse for the mathematicians.

    2. Filippo Silver badge

      Re: Too smart for their own good?

      There's little text in Indus Script, and none of it has a translation. Are you suggesting that a good encryption algorithm should only be used for a handful of messages in the whole world, and said messages should never get translated into cleartext?

      1. Matt Bryant Silver badge
        Facepalm

        Re: Filippo Re: Too smart for their own good?

        "There's little text in Indus Script....." Apart from the 4000+ examples found so far you mean? The Rosetta Stone provided insight into three different Ancient Egyptian languages with far less.

        "......and none of it has a translation......" Again, you are failing to see that pattern matching alone should identify common terms, which implies there is more to the scripts than just jottings. The obvious example would be the predecessor of diplomatic codes, ancient civilisations such as the Assyrians having a completely separate language for their diplomatic missives.

        ".....Are you suggesting that a good encryption algorithm should only be used for a handful of messages in the whole world...." Well, that is the idea behind a one-time pad.....

        "....and said messages should never get translated into cleartext?" The most secure instant communication system used by either side in WW2 was the Navajo code talkers, American Indians embedded with the troops that could instantly talk to each other in their own language without needing to waste time encrypting or decrypting messages. It is a classic example of parallel thinking producing a far simpler and more secure system than 'pretty' maths. Or maybe combine maths with non-mathematical tools.

        1. Anonymous Coward
          Anonymous Coward

          Re: Filippo Too smart for their own good?

          "The most secure instant communication system used by either side in WW2 was the Navajo code talkers, American Indians embedded with the troops that could instantly talk to each other in their own language without needing to waste time encrypting or decrypting messages. It is a classic example of parallel thinking producing a far simpler and more secure system than 'pretty' maths."

          That system is simply security by obscurity. If the germans had figured out which language it was and somehow got hold of a navajo speaker without the americans knowing (not entirely impossible given they had spies on the continental USA) the whole scheme would have been done for.

          1. Matt Bryant Silver badge
            Boffin

            Re: boltar Re: Filippo Too smart for their own good?

            ".....If the germans had figured out which language it was and somehow got hold of a navajo speaker without the americans knowing...." The trick was first used in WW1 (with Cherokees, IIRC) and the Germans learned of it between the Wars. Hitler was so concerned that he sent teams of anthropologists to the States to try and learn all the Indian languages but they failed due to the diversity of the languages. The Germans passed their knowledge on to the Japs who screened all captured Americans for any they thought looked like Red Indians, and tried to coerce them into translating recorded Navajo messages. They failed. The USMC already had a plan in place to switch to another Red Indian language if the scheme had been compromised, they had plenty to choose from.

            1. Anonymous Coward
              Anonymous Coward

              Re: boltar Filippo Too smart for their own good?

              Matt: So you're being radical and want to find an alternative to this smartass maths based security boffinry? Well it's been invented already and it's called "security through obscurity." Go look it up.

            2. Anonymous Coward
              Anonymous Coward

              Re: boltar Filippo Too smart for their own good?

              "he Germans passed their knowledge on to the Japs who screened all captured Americans for any they thought looked like Red Indians, and tried to coerce them into translating recorded Navajo messages. They failed. "

              If thats the case then those captured navajos were seriously brave given the depths od depravity the japanese were quite happy to descend to in WW2.

              1. Bryan Maguire

                Re: boltar Filippo Too smart for their own good?

                The problem with that is that not all "red indians" were navajo. and the codetalkers didnt use plaintext navajo. They coded all the messages before sending them so even if they were intercepted by a navajo speaker they wouldnt make much sense.

                1. asdf

                  Re: boltar Filippo Too smart for their own good?

                  >so even if they were intercepted by a navajo speaker they wouldnt make much sense.

                  I think I remember reading they also had handlers who were under orders to kill the speakers if they were going to be captured by the enemy.

              2. Matt Bryant Silver badge
                Boffin

                Re: boltar Filippo Too smart for their own good?

                ".....then those captured navajos were seriously brave given the depths od depravity the japanese were quite happy to descend to in WW2." Unfortunately, the Japanese had a problem in picking out Red Indians, in a similar manner the typical Westerner would have a problem differentiating Chinese from Japanese. Several Hispanic-American soldiers were reputedly also tortured by mistake, along with at least one Italian-American.

          2. asdf

            Re: Filippo Too smart for their own good?

            >"The most secure instant communication system used by either side in WW2 was the Navajo code talkers,

            Do you have a citation for that claim? Even then considering how long most sides kept information about the topic in general classified my guess is there is only a handful of people that would even know if this was the truth and they weren't very likely to write a paper on it. Like the false claim of how successful the Patriot missiles were in the first Gulf War it's not unusual for the victors to claim all sorts of things occurred for consumption by their own people for various propaganda purposes.

            1. Matt Bryant Silver badge
              FAIL

              Re: asdf Re: Filippo Too smart for their own good?

              ".....Do you have a citation for that claim?....." Go do some research of your own, you ignoramus. Here, you can read how the Japanses had broken the US Army and Air Force codes but couldn't break the Navajo Code at Spartacus Ed., a suitably Leftie site even you would have a hard time ignoring (http://spartacus-educational.com/2WWnavajo.htm).

              1. asdf

                Re: asdf Filippo Too smart for their own good?

                >The most secure instant communication system used by either side in WW2 was the Navajo code talkers,

                >but couldn't break the Navajo Code at Spartacus Ed., a suitably Leftie site even you would have a hard time ignoring (http://spartacus-educational.com/2WWnavajo.htm).

                Funny nowhere does that reference claim it was the most secure comm system. It does show at least one security by obscurity (and even then they used code as well instead of just their native language) example seemed to work before the era of the internet and an incredible amount of data being available on demand. But sure lets forsake math. What has it ever done for us?

                1. Matt Bryant Silver badge
                  FAIL

                  Re: asdf Filippo Too smart for their own good?

                  "....Funny nowhere does that reference claim it was the most secure comm system...." The Navajo Code was both quick and versatile, which encryption technologies of the day were not (it could take hours for an Enigma message to be encrypted and transmitted), and it had the security of not requiring a mechanical coding device such as an encryption machine or one-time pad. You can quibble all you like in an attempt to hide your ignorance, it makes no difference to the fact of the code's success nor that it was the Yanks you despise so much that were clever enough to implement it.

                  ".....But sure lets forsake math. What has it ever done for us?" And now you're just over-reaching as usual. I did not say 'abandon maths', I said we should not think of it only for security. Ah, I see the problem - you and that whole thinking part are strangers.

      2. Anonymous Coward
        Anonymous Coward

        Re: Too smart for their own good?

        >Are you suggesting that a good encryption algorithm should only be used for a handful of messages >in the whole world

        How about just one short message? The scheme is known as a one time pad and is uncrackable.

    3. This post has been deleted by its author

  7. PM.

    I wonder who promoted this encryption standards ?

    The agency with three letter acronym , starting with letter N ?

    1. Anonymous Coward
      Anonymous Coward

      NIST requires at least 160 bits

      128 bits for export to non-friendly nations.

  8. drunk.smile
    Trollface

    New Uncrackable Crypto

    I propose a new method of encoding data for cryptography.

    Step 1. The data to encode is allocated a sequential ID number.

    Step 2. The ID number is multiplied by 5.

    Step 3: The ID number is then converted into Chinese number format and a Salt is added.

    Step 4: The SaltedID is then encrypted using the most secure algorithm available today.

    Step 4: The original data string is then uploaded to the Amazon cloud along with the SaltedID number for reference. Only the SaltedID remains in the encoded dataset.

    Step 5: For encoding and decoding the data first the SaltedID is decrypted, then re-encrypted and then used to find the original data stored in the cloud and download this to the user.

    Fool.proof.

    1. d3rrial

      Re: New Uncrackable Crypto

      Or you just go and take 100 datasets of 2000 true random characters, label them 1 to 100, print it out twice into two books, give one to your friend, keep one for yourself and then just go and XOR whatever message you want to send with these 2000 letters, send your friend the index (the number from 1 to 100) and he'll just have to XOR your message with the dataset corresponding to the index to get the clear text. 100% proven security, impossible to crack.

      Just as fool proof, doesn't rely on Amazon Cloud (really?) and is called One-time pad

      1. Christopher E. Stith

        Re: New Uncrackable Crypto

        Managing the pads is left as an exercise, but I have code for OTP encryption on my arm.

        Archival Storage -- Perlmonks

      2. Michael Wojcik Silver badge

        Re: New Uncrackable Crypto

        Or you just go and take 100 datasets of 2000 true random characters, label them 1 to 100, print it out twice into two books, give one to your friend, keep one for yourself and then just go and XOR whatever message you want to send with these 2000 letters, send your friend the index (the number from 1 to 100) and he'll just have to XOR your message with the dataset corresponding to the index to get the clear text. 100% proven security, impossible to crack.

        For it to be an OTP, you have to ensure the pad is never reused - a detail your description omits. More importantly, what you've described isn't an OTP unless your "true random characters" actually represent every possible value of your symbol set, and the size of that symbol set is a power of two. Otherwise the result of exclusive-ORing plaintext and pad characters will be biased, since your pad omits some binary strings in its symbol space. Also, your random source has to be unbiased (or more precisely have no bias that an attacker can learn of); of course it's possible to compensate for bias in a random source by post-processing.

        When OTPs are implemented with computers, they're generally implemented using pads of random bytes, not "characters". But OTPs are very rarely used, because they simply rearrange the basic cryptography problem: you create a secure channel for your message by requiring a secure channel for your key.

        100% proven security, impossible to crack

        I know OTPs are the Internet Hero of armchair cryptographers, but this sort of rubbish doesn't do anyone any favors. OTPs do not offer "100% proven security", because "100% security" is a meaningless phrase. An attacker can steal the pad, or coopt the recipient. Communications security is more than just confidentiality; a MITM attacker can alter the message in transit even without being able to decrypt it. Message integrity can be added, but the confidentiality proof of the OTP stems from all plaintexts of a given length being equally probable preimages for a ciphertext; when a message can be verified, some messages become more probable, so the OTP's confidentiality is reduced. More importantly, communications security is not the entirety of security, and security itself is only relevant in the context of a threat model.

    2. 4ecks
      Coat

      Re: New Uncrackable Crypto

      Or -

      1) Put plaintext through Google Translate into Klingon.

      2) Create "Klingon plaintext" document in Word95 and then add lots of formatting, different fonts and text sizes.

      3) Open with Office2013/365

      4) "Save as" .docx

      5) Rename file type to .doc

      Instant double encryption including an obscure proprietary method, unfortunately you'll probably never be able to unscramble it. ;-)

  9. Herby

    All of this is why...

    ...you PUBLISH your encryption algorithms. Then they can be reviewed by others in the field, and the weaknesses exposed. This works most of the time until some goverNment'S Agency finds out the "solution" and keeps it to themselves. Thankfully there are other eyes that will speak up and tell you the problems, as in this instance.

    Encryption looks simple, but it isn't. Best leave it to experts than roll your own.

    1. FutureShock999

      Re: All of this is why...

      And of course, if you left it to experts, and chose a publicly reviewed cryptosystem, then for many years you could have been using RC4 encryption and been quite happy (as even Skype was when using it). Um, of course...RC4 wasn't REALLY secure, was it???

      That is the problem with all of the public-reviewed systems. There is an underlying assumption that there are enough eyeballs and experts actually putting in the months necessary to break it in all kinds of ways. But as the recent HTPS breakage shows, there sometimes just are not enough eyeballs probing it to find the errors...

      1. Michael Wojcik Silver badge

        Re: All of this is why...

        RC4 wasn't REALLY secure, was it???

        Nothing is "REALLY secure". That phrase has no meaning.

        RC4 was perfectly suitable for the vast (vast, all but a vanishingly small fraction) majority of its applications. It remains perfectly suitable for a great many applications today. The work factor and other requirements for breaking RC4 are still considerable. Under many threat models it's completely acceptable.

        And there were a great many people looking at RC4, which is why we now know about its weaknesses. It's utterly irrelevant for your argument.

This topic is closed for new posts.