Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

Cryptogram: AES Broken? 277

Posted by chrisd from the small-s-boxes-lead-to-weirdness dept.
bcrowell writes "The latest CryptoGram reports that AES (Rijndael) and Serpent may have been broken. The good news is that when cryptographers say 'broken' they don't necessarily mean broken in a way that is practical to exploit right now. Still, maybe we need to assume that any given type of crypto is only temporary. All of cryptography depends on a small number of problems that are believed to be hard. And all bets are definitely off when quantum computers arrive on the scene. Maybe someday we'll look back fondly on the golden age of privacy."
This discussion has been archived. No new comments can be posted.

Cryptogram: AES Broken? More

Cryptogram: AES Broken?

Comments Filter:

  • Quantum computing for white hats (Score:3, Insightful)

    by kingpin2k ( 523489 ) on Monday September 16, 2002 @08:46AM (#4264922)
    Wouldn't the same quantum computing that allows people to break today's crypto enable white hats to use increasingly complex algorithms and S-boxes to protect data? I mean, it's not as if crypto crackers are going to have these bad ass machines while the good guys sit around on 486's, right? Am I missing something?
    • Not really missing.. but the point is that bad guys upgrade first step ahead of good guys. first we have the virus and then we have the anti-virus.. not the ohther way round.. The problem is that quantum computing will make the coverable space huge.. So "good guys" will not really know what they missed and finding something goodies missed will be randomly possible... now all the random theory shit i cant put here, but the biggest challenge in quantum crypto is mapping the coverage, a lot of loopholes can be left of everything is uncertain.... and our knowledge of quantum mechs is still infantile.
    • The underlying idea of both symmetric abd asymmetric cryptography is that there exists operations that are very asymmetric. For example, multiplying two numbers together is extremely much faster than factoring them, and there are several other.

      Quantum computing changes this balance. So your white hats won't be able to multiply a billion times faster even if the black hats can factor a billion times faster.

      Kjella
    • No.

      Slightly different quantum computation will do though, quantum crypto allows transmission of entirely secure messages, that is an unbreakable system. It isn't guarenteed by the hardness of a couple of mathematical challenges but by the actaul laws of physics themselves. Not only can a quantum crypto stream not be broken, but it can detect when somebody attempts to listen in. This has been demonstarted using both air and fibre as a transmission system (can't be arsed to google for a link but there should be plenty out there, it was textbook for our quantum computation course).

      On the other hand, a quantum computer would break all the old cryptosystems quite easily (not sure about eliptic curves), however they are years away from being feasible and there are a lot of hard problems to solve first.
    • Not necessarily. Quantum computing is a technique that is potentially very useful for operations that are highly parallelizable, and less so for operations that tend to be inherently sequential.


      More complex algorithms for encryption do not necessarily mean more security. If factoring, for example, is only linearly hard in the number of digits of the large pseudoprime, then you could theoretically generate absolutely massive pseudoprimes, but at some point the method becomes useless.


      The problem is that our notion of "hard" and "one-way" problems is all based on the concept of NP-completeness. This concept is broken by quantum computation. We would need to find new problems that are QC-complete, in other words, problems that are hard (exponential time and # qubits) even with quantum computation, and base new encryption methods around such problems.


      I'm not up to date on the literature of computational complexity, but I'm fairly sure such problems should be possible to find, a class of harder problems than NP-complete problems. But since functional QC is so far off, this is not really a practical issue yet, but I'm sure it's of theoretical interest to many.

      • It's easy to get confused here. There is a quantum computer algorithm for factoring, because factoring happens to map well to quantum concepts. But factoring is not NP-complete - in fact, it is in P. If you could reduce an NP-complete problem to a factoring operation, you would have proven that P=NP.

        The theories that posit QC as the solution to P=NP tend to involve poorly-defined "oracle machines" based on QC hand-waving, rather than any actual well-defined algorithms. It is very much an open question whether QC has anything interesting to say about P=NP.

        -Graham
        • Sorry I was mistaken - you are right that factoring is not proven to be NP hard or NP complete (dredging up CS knowledge from 4 or 5 years back here).


          However, you are not 100% correct either. Most practical experience does not suggest a polynomial time solution exists (with the exception of Shor's Algorithm and the quantum factoring algorithm - this does mean the problem is in BQP, the new class of bounded-error, quantum polynomial time). If you look up the modern definitions of P, it seems to refer only to deterministic sequential machines, and I don't think that includes quantum computers strictly speaking.


          I guess this is a quibble, but a worthwhile one, since the whole point is that there is a class of problems that _seems_ to be made easier (i.e. polynomial) by quantum computing, though it's not clear that those same problems don't have non-quantum polynomial solutions, it certainly appears that way based on everything we know.


          You seem to be correct though that there is no proof of anything about P=NP from QC (I just looked it up and I'll be damned if I could make any sense of the articles I found without some serious study).

    • Unfortunately this thread does not appear to be talking about the AES issue at all, but garbled understanding of what quantum crypto can do.

      According to the cryptographer's panel at RSA quantum computing is much less of a threat than many assume. In the first place quantum computing tends not to be effective against symetric algorithms. Secondly RSA turns out to be based on a problem that is very very hard with conventional computing and very very easy with quantum computing. It is not clear that all possible public key algorithms are susceptable to attack using quantum techniques.

      In other words don't get the idea that quantum computing immediately means the end of cryptography.

      On the actual topic of AES I would not call this a 'break', in fact nothing less than breaking the cipher for real should count as a break. There are plenty of 'breaks' of DES but none of them are easier than brute force when applied in practice. What we have is a theoretical compromise that is way outside the capabilities of any current technology.

      Or consider it this way, given the known problems with 3DES (limited block size, severe limitation on safe amount of ciphertext generation) I don't feel like sticking with 3DES as a result of the article.

    • Quantum computing means that you can either tell what color somebody's hat is or how many hats they'r ewearing, but not both simultaneously :-)

      Quantum computing appears to allow the user to cheat, by picking the correct n-bit value out of 2**n bits, for a class of problems that mostly look like the factoring problems that make RSA public key crypto work. This doesn't appear to make things faster for the white hats, because the white hats already knew what the correct bits were for data that was intended for them or data that they were trying to sign.
      • We need to start exploring the theory of QC, to find algorithms that don't get exponentially faster with QC.
      • We also need to start remembering and improving the symmetric-key-based Key Distribution Center (KDC) models like Kerberos [mit.edu] that don't depend on public-key crypto. We abandoned most of these, because public-key is much more convenient and doesn't have big obvious centralized security targets that can be attacked, but they still do an amazing number of jobs just fine.
      • Today's problem is attacks on the Rijndael and Serpent AES winner/candidate symmetric-key algorithms, which has been proposed as a replacement for 3DES, the current highly-trusted-but-slow symmetric-key algorithm. We need to watch the crypto math folks apply their new techniques to the other AES candidates, so we can tell if any of them are still usable or if we have to get the NSA to run another contest. These aren't particularly affected by Quantum Cryptography.
  • And all bets are definitely off when quantum computers arrive on the scene.

    couldn't these be described as "weapons of mass decryption"? [visions of 'sneakers' all over again]

  • Quantum (Score:2, Interesting)

    by caluml ( 551744 )
    Seriously, once quantum computers arrive, and we all have to ditch our factored encryption, what are we left with?
    Is it really back to XORing our messages with random data known to both ends?
    That sucks.

    And the cry went up - make quantum computers illegal. Only terrorists want quantum computers... ;)
  • It will continue to exist so long as the average hacker has a computer within 2 or 3 orders of magnitude of power of the government. Easy.

  • Comment removed (Score:3, Interesting)

    by account_deleted ( 4530225 ) on Monday September 16, 2002 @08:49AM (#4264937)
    Comment removed based on user account deletion

    • Re:Quantum computing =/= no privacy (Score:5, Informative)

      by stevelinton ( 4044 ) <sal@dcs.st-and.ac.uk> on Monday September 16, 2002 @09:04AM (#4265016) Homepage
      Quantum Computing and Quantum Cryptography are unrelated technologoies. Quantum crypto is indeed "unbreakable", but requires a single physical channel connecting source and destination. It will not carry over routers and absolutely cannot be used for normal internet email for instance.

      Quantum computing would break a range of encryption techniques, especially most public-key techniques, but nothing known today rules out new and more robust digital encryption technologies being developed that Quantum Computers could not break, and I imagine plenty of people are working on them.

      • Addendum (Score:4, Informative)

        by seizer ( 16950 ) on Monday September 16, 2002 @09:34AM (#4265186) Homepage
        It's probably worth noting that IBM has already demonstrated a quantum computer running a factoring algorithm:

        (See here) [ibm.com]
      • In fact elyptic curves appear to be immune to quantum techniques that have so far been postulated. This does not mean that a fast method will not be found to break EC's simply that there is not yet any knowledge of a technique that significantly weakens EC's.

        • Re:Quantum computing =/= no privacy (Score:4, Insightful)

          by aminorex ( 141494 ) on Monday September 16, 2002 @11:18AM (#4265958) Homepage Journal
          It will always be the case that crypto which depends
          on computational intractability rather than a
          demonstrable computational impossibility will always
          be open to some future innovation rendering it
          trivial to crack. Elliptic curve crypto seems to
          have the best prospects for the future right now,
          and you can use it right now: El Gamal is
          implemented in GPG.


          But to say that QC will render effective crypto a
          historical artifact is clearly mistaken. If it
          were true, it would imply that there are *no*
          hard problems any more, once QC techniques are
          employed. All that QC can do is compute functions
          over a finite field with effectively infinite
          parallelism. It's unfortunate that most crypto
          systems today rely upon functions over a finite
          field, but there are plenty of hard problems that
          are only valid over function spaces, for example.

    • when quantum computers arrive

      I have a Quantum hard drive, but I didn't know they were getting in the PC business.

      Hmmm... now that I think about it, I thought they got bought out by Maxtor. I think you're just bluffing about "Quantum computers" and this power they will supposedly have.

  • The end of privacy (Score:5, Insightful)

    by bjelkeman ( 107902 ) on Monday September 16, 2002 @08:49AM (#4264939) Homepage Journal
    on the golden age of privacy

    That is quite a funny statement. 99% of all email is being sent in clear text, often passing through gateways which have permanent wiretaps installed. Phone tapping is at an all time high in the west and there are cameras on nearly every street corner around where I live.

    Privacy.... I had a lot more privacy 20 years ago, that is for certain.
    • Hah, too true. :) The "golden age of privacy" would be known more as the "golden age of privacy that nobody bothered to take advantage of when they could".
    • Privacy.... I had a lot more privacy 20 years ago, that is for certain.
      I doubt that. 20 years ago, your neighbour, your baker and your butcher knew more about you than any mass e-mail marketing company does nowadays. The only difference is that they didn't send you spam, but for sure your butcher knew that you didn't know the difference between a normal and an excellent steak, and sold you the first one for the price of the second one. So you were f*cked even then, only you didn't know it.

      In order to provide some on-topic content also: I thought the basis of all (public-key) encryption was based on one "hard to solve" problem only, namely the "factoring in prime numbers" problem -- are there any problems that I missed?
      • el gamal is based on discrete logs on a finite field

      • I doubt that. 20 years ago, your neighbour, your baker and your butcher knew more about you than any mass e-mail marketing company does nowadays.
        Uhh... sorry to be literal, but 20 years ago I didn't know my butcher personally and I still don't. I buy mostly buy meat at the supermarket. I think it was more like 60 years ago that everyone bought meat from the local butcher.

        On the other hand, my credit card issuer knows far more about me than any e-mail marketer. They know that I play golf once a week, how much I spend in the grocery store, when and where I go on vacation, etc. All the average e-mail marketer (thinks they) know about me is that I like rape pr0n.

        -a

      • are there any problems that I missed?

        RSA is based upon the Integer Factorization Problem (IFP) (*).

        Elgamal / DH are based upon the Discrete Log Problem (*)

        Eliptic Curves Cryptography is based upon, erm, Eliptic Curves.

        (*) Note: there are no proofs that RSA or DH/Elgamal are actually as hard as the underlying IFP or DLP - e.g. they could be broken even if factoring is "hard".


  • When quantum computers come out, we'll develop problems that are believed to be hard on quantum computers...

    we can not assume that either side of the crypto equation will remain dormant, using only today's technologies. The next Bruce Schneier [amazon.com] will happen along (or maybe the man himself) and we'll be dealing with the golden age of quantum cryptography.

  • gross oversimplification (Score:3, Funny)

    by jukal ( 523582 ) on Monday September 16, 2002 @08:51AM (#4264951) Journal
    Basically, the attack works by trying to express the entire algorithm as multivariate quadratic polynomials, and then using an innovative technique to treat the terms of those polynomials as individual variables. This gives you a system of linear equations in a quadratically large number of variables, which you have to solve. There are a bunch of minimization techniques, and several other clever tricks you can use to make the solution easier. (This is a gross oversimplification of the paper; read it for more detail.)

    Uhm. emm. EZ? :)

    • What's the problem? You should have seen all of that stuff, at least on a basic level, in high school if you went to school in the USA. This is assuming you took the college prep route of courses.
      • >What's the problem?

        The fact that my and your sense of humour did not intersect. :) To me, it seemed that the clip was like straight from Dilbert mission statement generator [dilbert.com]. Anyway, the description is very good, but to one like me, who does not use math terms actively, it takes some time to understand what it means in practise and how to use the information. And at first sight it seems like the recipe for Energy Bolt spell. But then again, I am mathematic moron :)

  • Nice article... (Score:2, Funny)

    by 26199 ( 577806 )

    ...I love the first line:

    AES may have been broken. Serpent, too. Or maybe not. In either case, there's no need to panic. Yet. But there might be soon. Maybe.

    Lovely summary, guys :-)

  • Quantum Computing and Privacy (Score:4, Insightful)

    by hillct ( 230132 ) on Monday September 16, 2002 @09:01AM (#4264998) Homepage Journal
    Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware. International politics would be forever changed. The basis for personal freedom (now based on privacy) would have to shift to something as alien as mutual trust and maybe even respect.

    The focus of international intelligence gathering would shift radically back to human intelligence (which is already happening for other reasons) and the new basis for security would become that of access cintrol through discontinuity - if you network is not connected to your neighbor's, then he can't get access to it regardless of his technical sophistocation.

    The days of the NSA Sneaker-Net would return (picture NSA computer geeks running from one terminal to another with DLTs in order to keep the systems in communication, such that data could only flow in one direction.

    Disclaimer: IANAF - I Am Not A Futurist

    --CTH

    • Re:Quantum Computing and Privacy (Score:5, Insightful)

      by sql*kitten ( 1359 ) on Monday September 16, 2002 @09:08AM (#4265046)
      Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware

      How would this technology work against one-time pads? Besides, historically technologies have always tended to balance. Someone makes a better tank, then someone makes a better tank-killer, then the cycle repeats. If today's sophisticated encryption can in the future be defeated with cheap devices, then the crypto that this future society considers sophisticated would be well beyond ours. Consider the relative computational power of Bletchly Park and the sophistication of Engima of the early 40s and the power and sophistication of a 21st Century desktop PC.

      International politics would be forever changed.

      Not really. It would simply switch from broadcast and ciphers to the diplomatic bag and codes - which is how it worked for centuries. Complexity in international affairs is nothing new.
      • Not really. It would simply switch from broadcast and ciphers to the diplomatic bag and codes

        Where of course, Numbers Stations [ibmpcug.co.uk] come in.

        For all the advances in asymetric cryptography, Numbers Stations / OTP has remained the system of choice for many organizations. This says something about asymetric cryptography; either that it isnt trusted, that its impractical for espionage, or something else...

      • Someone makes a better tank, then someone makes a better tank-killer, then the cycle repeats.

        Very true, but it bears pointing out that the direction of the advantage seems to be different.

        In the battle between warhead and armor, the warhead tends to retain the lead most all of the time, because it's basically easier to blow holes in something than to withstand massive force.

        In the battle between cipher and cryptanalyst, the ciphers have tended to retain the lead, which seems to imply that creating an algorithm that munges data in complex ways is basically easier than unraveling said munging. This is *not* to say that good cipher design is easy or that anyone can do it; it's fiendishly difficult, because the attackers are fiendishly clever. Still, over the last 50 years or so, history shows us that the ciphers have tended to stay ahead of the cryptanalysts. DES is a shining example, given that it has been the #1 target for 30 years and has stood essentially undamaged.

        • I'm picking a few nits here, but there are several chinks in DES's armor.
          • It has been known for some time that there are many weak keys in DES.
          • In 1990, Biham and Shamir published a differential cryptanalysis attack on reduced round variants of DES.
          • In 1993 Matthew Wiener published an initial design for a DES-breaking machine. At the time, it would have cost $2M.
          • In 1998 Biryukov and Kushilevitz published a ciphertext-only attack on reduced round DES reducing the workload by 2^20.
          • Near this time, I recall seeing a paper claiming to reduce DES to a 2^48 problem, but I'm unable to find a citation tonight.
          • In 1998, Wiener's machine was built by the Paul Kocher and EFF for about $250,000, and it breaks DES keys in about three days, on average.

          So yes, I agree that DES is the granddaddy of Feistel network ciphers. Few of the cryptanalytic attacks work without ungodly amounts of chosen plaintext or artificially reduced round counts. But code breaks have generally occurred within months or years of implementation, not decades. As Gwido Langer, the chief of Poland's Biuro Szyfrow, said about breaking the German Enigma (when the British were unable to) "You don't have the same motivation as we do." Until after World War II, most code systems were broken during the same wars they were supposed to be protecting, and for that same reason.

          The wartime and/or government codebreakers also have one more advantage: they don't typically announce their breaks to their enemies du jour. The recently released Venona papers show how Soviet spies who were given (faulty) one-time pads in 1942-1946 had them broken between 1948 and 1980.

          Yes, it's a constant struggle. Yes, DES looks pretty good. But I wouldn't want to trust ALL of the national eggs to any single one of the currently commercially-available baskets.

          • It has been known for some time that there are many weak keys in DES.

            Depending on your definition of "many", this is true. The complementation property of DES is a small weakness as well. These issues reduce the strength of DES by a miniscule amount.

            Near this time, I recall seeing a paper claiming to reduce DES to a 2^48 problem, but I'm unable to find a citation tonight.

            You're probably thinking of Matsui's Linear Cryptanalysis.

            In 1998, Wiener's machine was built by the Paul Kocher and EFF for about $250,000, and it breaks DES keys in about three days, on average.

            The DES key size was always too small, but that was what the NSA wanted. Remember that the original cipher (Lucifer) had a 128-bit key. 3DES addresses this problem handily, if not elegantly.

            Also, if you'll permit me to pick nits, Deep Crack recovers a key in about 5 days, on average.

            Overall, though, all of the concerted effort focused on DES has reduced its effective key size very little. That effective key size was too small to begin with, but 3DES has an effective key size that is adequate for a few years yet, particularly since linear and differential attacks cannot be used to speed up the "meet-in-the-middle" attack.

            This is a pretty impressive record, in my opinion.

    • There was no privacy in most small towns all over the world. Until people started moving around, there was a local neighbor who knew what was going on. Ever try to hide something in a small school? The local gossip made sure you didn't. Most of our privacy today is an illusion based on non-existent anonymity.
  • http://www.newsfactor.com/perl/story/13468.html

    Quantum computing is a *good* thing.

  • Strictly Speaking (Score:2, Insightful)

    by Beautyon ( 214567 )
    All of cryptography depends on a small number of problems that are believed to be hard.

    This is not true; The "One Time Pad" does not rely on a difficult problem like factoring for its basis.

    And all bets are definitely off when quantum computers arrive on the scene. Maybe someday we'll look back fondly on the golden age of privacy.

    OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.

    Now legislation ending the golden age of privacy is another matter entirely.
    • OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.

      Only if your pad is truly random. There's a scene in Cryptonomicon in which they realize the vicar's wife is looking at the letters as she draws them out of the tombola used to randomize; being a native English speaker she is subconsciously biased to prefer certain letters over others, and this is enough to open a chink in the armor.
      • When I use the term "OPT", it is implicit that I mean "when OTPt is deployed correctly".

        It would be a little crazy to say "OTP, when it is deployed improperly, cannot be broken", now wouldnt it?
    • While this is true, there's a reason that no one uses one-time-pads : they're a pain in the ass. In terms of practical usefulness, really only governments are willing to go to the trouble.

      The big problem is that once you've encrypted something with an OTP, the security (and secrecy) of the OTP is *everything*. If anyone gets the OTP, your encryption is done for.

      So, managing the OTPs becomes the biggest challenge in using them. First, you have to have an OTP about the same size as the file you're encrypting, to ensure that no statistical games can be played to re-build the key, and you have to have a seperate OTP for every message you encrypt. Also, getting an OTP to someone else you want to encrypt a message to is not an easy matter. You have to be sure that no one else can see the transaction that shares the OTP, since that would immediately destroy the security of the system.

      Compare this to any symmetric-key system: Yeah, you've also got a key that's central to the cipher. But, the key does not need to be approximately the same size as the file encrypted (as is the case with OTPs), which, for big files, is a huge deal.

      Basically, there's a reason we like symmetric-key algorithms, and it's mostly to do with usability. If an encryption system is such a pain in the ass that no one uses it, then its impact in the real world will be zero.
      • Basically, there's a reason we like symmetric-key algorithms, and it's mostly to do with usability. If an encryption system is such a pain in the ass that no one uses it, then its impact in the real world will be zero.

        I totally agree with you about OTP being a pain in the ass to manage, but as far as its impact in the real world, you could not be more wrong.

        Numbers Stations [ibmpcug.co.uk] have relied on OTP for decades, and continue to do so till today.

        Like anything, it depends how much you want a to protect your communications. If OTP is going to save your life, as in espionage, it becomes much less of a pain in the ass. If you want to encrypt your daily email with the 20 people in your Mozilla address book, then things get very messy very quickly, and of course, you can forget stuff like ecommerce, which instantly become "unwieldly" to put it mildly.

    • Re:Strictly Speaking (Score:2, Informative)

      by Delta ( 16579 )
      OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.

      OTP is not unbreakable.

      While the algorithm itself isn't breakable, the strenght of a OTP based solution will still depend on several weak points, like the random number source.

      There's plenty of room for trying to attack it, using statistical analysis and estimates to try to be able to break it.
      • OTP is not unbreakable.

        OTP *is* unbreakable. [std.com]

        This is a well established fact. Like I said elewhere in this thread, its clear that I mean "when it is implimented correctly", as it would make absolutely no sense to imply "OTP is unbreakable when it is implimented poorly".
  • ...maybe we need to assume that any given type of crypto is only temporary.

    Well that's a serious problem if you ever, ever thought cryptography had any sort of permanence!

    For one thing, an encrypted message is of no use to the receiver if they can't DE-crypt it, *poof* crypto is not permanent.

    I'd recommend reading "The Code Book" by Simon Singh as the first two-thirds of the book are a history lesson that demonstates to me how cryptography endagers the lives/way of life of those who rely on it to protect themselves (in particular, Mary Queen of Scots and Enigma).

  • Old data is the problem (Score:5, Insightful)

    by BESTouff ( 531293 ) on Monday September 16, 2002 @09:11AM (#4265061)
    The problem is that old encrypted data doesn't "evolve" with the computing/crypto capacity.

    Imagine some black hat just archived all encrypted data he could get (bank transactions, private conversations, you name it) then decrypts them in 10 years when he can buy his brand new quantum computer. All this old data may prove very valuable for him.

    Perhaps very sensitive data shouldn't even transit on the net because you can't tell if it'll be decryptable in the future.

  • So use one-time pads (Score:2, Insightful)

    by wiredog ( 43288 )
    They're easy to generate. All you need is a good source of randomness. A small analog input card connected to a thermocouple wire with a bad (therefore noisy) connection makes a wonderful source of randomness. Use the low four bits of a 12 bit card. Two reads gives one random byte. String random bytes together to generate however many you need.

    Once you have the list of numbers, get the list of words and phrases to encode. Put one random number next to each word or phrase (watch for duplicate codes here!)

    Put the pad on a cd, send it to whoever you want to communicate with. Doing this last part is the only large potential insecurity, plus it's inefficient. But the one time pad is theoretically unbreakable.

    • But the one time pad is theoretically unbreakable.

      Here it's fitting to note the words of Steve Bellowin:

      "As a practical person, I've observed that one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong."

      In operation, there are many 'gotchas' to watch out for, never reuse a pad for example.

      Google for 'Venona' and 'one time pad' for a good example of even the experts (KGB et al) getting one time pads wrong.

    • If you number individual words and phrases, then you can only use each word or phrase once, otherwise it's not a one-time pad anymore. Think about it... how long would it take a cryptanalyst to figure out the code for "the" or "you"?

      The pad should simply be a chunk of random bits, and both sides need to keep track of which bits have been used. Then encrypt your messages by xoring them with an unused stretch of bits.

      • Don't encode 'the' or 'you'. Encode them as parts of phrases, or leave them out where possible.

        I used one time pads in the army. You wouldn't use one to transmit War and Peace. But you would use it to send "Attack is Tomorrow, sell IBM". Or to send "Name of agent in NSA is CowboyNeal."

        Those would be encoded as the phrases "attack is tomorrow", "sell IBM", "name of agent","in NSA". The word "is" could be encoded, or dropped (the sentence would be parseable without it.) Only "CowboyNeal" might have to be encoded letter by letter. Or it could be encoded as "cowboy"+"n"+"e"+"a"+"l".

        Generally, using a one time pad to encode letter by letter is a bad idea. Done only when there is no alternative.

        • Sorry -- dark nl is correct, and you're wrong. Here's an example of how to use a one-time pad: Your pad = random string of bits, like 0111 0101 0001 Your message = string of bits, say, 1010 1010 1010 Encrypted message = pad XOR message = 1101 1111 1011 Decrypted message = pad XOR encrypted message = 1010 1010 1010. It has nothing to do with substituting for words or letters. The drawback to one-time pads is that each side needs to have the same pad, which must be at least as long as the message to be encrypted. The pad has to be shared and stored in a secure fashion, which makes it impractical in most cases.
          • I think you're arguing two different points. You're worrying about how the pad actually works, and he's worried about maximizing the use you get out of the pad (by dropping unnecessary words out of the message to be encrypted). These two worries are clearly related, but not identical.

            I would say that he is correct: in practice, you would want to drop unnecessary or redundant info out of the message. Since OTPs rely so heavily on securely sharing the pad, you want to maximize the use you can get out of the pad you have without re-use. This means dropping redundant words. In common computer practice, we'd just zip the damn thing before sending it, hopefully greatly increasing the entropy (and decreasing the length) of the message before even bothering to encrypt it, but that's a whole other topic for discussion.
            • Actually, the entropy of the message doesn't matter with a one-time pad, so long as your pad is truly random, but you're right that compressing the message gives you more use out of that pad.
          • I'm talking about the classic implementation. You have two columns. Left column is the lits of words/phrases, right column is the list of codes used for those words/phrases. It can be done by hand (as I did it in the Army), or automated.

            The Army still uses one time pads that way.

            • As Rich0 pointed out, this isn't a "one-time pad" as understood by cryptographers, even though you may have been using your code a single time. This is a codebook, and it is not 100% secure. One-time pads, on the other hand, are the only provably 100% secure cryptosystem.
    • A much more common source of randomness that was published in Phrack Volume 8 Issue 54 is to use a cleaned white noise signal from a soundcard. See This link [phrack.com] for more details.

  • MAYBE? (Score:2, Insightful)

    by Winterblink ( 575267 )
    maybe we need to assume that any given type of crypto is only temporary

    If I'm not mistaken, this is rule #1 of cryptography. Doesn't really matter what algorithm you use or how secure everyone or anyone thinks it is, they're always able to be cracked. Which cryptosystem you use is more a measure of reasonable security -- do you want your messages secured for years, decades, etc., with an assumed increase of computing power?

  • What Schneier really meant to say... (Score:4, Interesting)

    by BigBadBri ( 595126 ) on Monday September 16, 2002 @09:27AM (#4265141)
    Serpent and Rijndael are vulnerable to this attack - it seems Twofish isn't - damn government should have chosen Twofish for AES instead...

    Seriously, though - any approach that manages to reduce the difficulty of cracking these algorithms by a factor of 2^100 is impressive, and Schneier at least simplifies it enough that us folks with very rusty number theory can appreciate the achievement.

    His comment later in Cryptogram about his name appearing on a list of banned words is much, much scarier - looks like he's upset someone in the content censorship Gestapo. That same content filter would deny access to today's Slashdot front page - nasty.

  • One Time Pad != Encryption (Score:4, Insightful)

    by Kjella ( 173770 ) on Monday September 16, 2002 @09:39AM (#4265220) Homepage
    Basicly, it's just a delay mechanism that will let you transfer messages securely at a later time assuming you've transmitted equally much information securely already. So the question is, why don't you use the secure medium in the first place? Ok granted, you can send an agent out on a mission with an OTP and he can communicate securely with home base, but I mean for everyday use?

    The typical idea about cryptography is to use a secure medium to provide the key, while using the insecure medium to send the data, because the insecure medium is much faster/better/easier to use. So I can meet you in person and get the key, or call you on the phone and verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well), and then use the Internet as a medium from then on.

    The OTP "solution" would be to say a random sequence of 1s and 0s, then use those to decrypt the irc converation later, not really an option. You'd "run out" of pad rather quickly. Oh, and quantum computing does as far as I know not affect encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).

    Kjella
    Kjella
    • One Time Pads are still practial for situations where absolute privacy is a must. The intelligence community still uses them and I could even see a bussiness use them if it was necessary. IT's not quite as difficult as you might think:

      You get a source of random data, there are plenty available and prepare a harddrive or harddrives that contain that data. Being that harddrive capacities are now in the 200GB range, you can get quite a lot of data. You then duplicate the drives once and only once. A secure, trusted courier then takes the drives to the other location where they are installed. You now have a good OTP system setup. Your encrypting/decrypting stations just need to be physically secure and keep track of what part of the pad has been used. When it's all used up, you destroy the drives.

      Now I can't think of anything that needs this level of security today, but it's not so impratical that a company couldn't or wouldn't do it if there was a reason. Under this system you just have an encryption channel that will give you X total GB of data (half duplex) transfer before it has to be refreshed. This would give you teh capacity to use this to secure a company intranet or something, but it wouldn't be unreasonab;e to get a years worth of small messages that require the utmost secearcy to be transfered this way.
    • So the question is, why don't you use the secure medium in the first place?

      Because I only get to see my brother once a year in Cuba. And he has a problem carrying back CD-Rs of random pad material through customs.

      verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well),

      Passive evesdropping (aka wiretapping) does not interefere while verifing a public key fingerprint. So you can verify fingerprints of a public key in a public place.

      OTP has other problems, beyond the typical key distribution problem. If a non-random source is used for generating the key material, or if the key pad is accidential reused, then trouble stikes, like it did with Venoma [nsa.gov].

      OTP also lacks message integerity, so if an attack could cut and paste blocks of encrypted ciphertext, Bob would not be able to detect the altered message if the decrypted text make sense (deposit $1000 to account #1233335632 rather than the modified message of deposit $4950292.95 to #1233335632)

      encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).

      Now what methods are you referring to here? Elliptic Curve Cryptography [certicom.ca] normally is used as a faster version of the Discrete Logarithm Problem [rsasecurity.com] (DLP) where it is faster and easier to Exponentiate (x^y) than it is to calculate its discrete logarithm (x such that g^x = h) which is the inverse operation and is much harder to calculate.

      So I would be interested in this method of using elliptic integrals.

      Quantum computing changes the games of cryptography, but it does not end the struggle of cryptographer vs. cryptanalysis. AES when used with a 256-bit key is expected to withstand a bruce force key search using quantum computing within the near future (less than 10-20 years). Of course quantum computing being a young field there is a chance that a radical discovery may ruin our present best estimates for future capabilitities.
    • If you're just sending text, then there's really no risk of running out of pad. Fill a zip disk with noise. Give it to the other party. Now, how long will it be before you've exchanged 100M of correspondence?

      1 personal meeting yields a lifetime of secure communication.

    • The definitive text on cryptography, The Handbook of Applied Cryptography [uwaterloo.ca], defines the OTP as a type of encryption...I know this is Slashdot but I don't think your arbitrary definitions help here.

      Sending a CD worth of random data via a secure channel in advance and then sending an encrypted message with the knowledge that it will be unbreakable is sometimes worth prior thought. Sure, it may not be usefull for the masses who require this kind of security or don't know their going to communicate in the future but to claim that this cipher "isn't encryption" is bull.

  • My fear is that we could see optimizations of the XSL attack breaking AES with a 2^80-ish complexity, in which case things starts to get dicey about ten years from now. (emphasis added by me)

    So, ten years or more. Heck, at that point, shouldn't quantum computers be breaking this stuff anyhow?

  • The XSL attack (Score:2, Interesting)

    by jlcooke ( 50413 )
    The XSL attack is highly subjective.

    All you "so is GPG broken?" put your pants back on.

    Summary of attack:
    XSL stands for three of the basic operations in Rijndael and Serpent. The reason why this attack works is because the substitution layer of Rijndael/AES and Serpent can be expressed very neatly as the same domain as the Linear layers.

    Now when I say 'neatly' I mean 'it would be possible' not no one's shown us this monster set of equations relatnig the (128+128/192/256) bit inputs to the 128 bit outputs. The Rijndael/AES and Serpent ciphers may be what we call "over defined".

    Think back to high school when you have N liniearly independent linear equations and N-1 unknowns. You had an infinate number of posibilities for solutions. If you had N eqns and N unkn's you had 1 sol'n. If you had N eqns and N+1 unkn's you were in a funny place.

    The authors suggest Rijndael/AES Serpent is in the latter catagory of the differential nature (and not the linear nature you learned in high school).

    So what does this mean? The possibility HAS NOT BE EXCLUDED that this attack is possible. It really proves demostrates nothing that it's at all possible. Which is best anyone's been able to do in the past 6 years.

    JLC

    See sci.crypt thread:
    http://groups.google.ca/groups?q=XSL+group%3Asci.c rypt [google.ca]
  • Here's Bruce Schneier on the subject [politechbot.com]:
    Some of the confusion stems from different definitions of "attack." To a cryptographer, an attack is anything that breaks the algorithm faster than brute force, even if it is completely impractical. To an engineer, an attack is something that is practical, or at least might be practical in a few years. An attack that breaks AES to a cryptographer might not to an engineer. The rest of the confusion stems from not being sure the attack actually works.

  • All of cryptography depends on a small number of problems that are believed to be hard.

    This is really only true of public key cryptography. Symmetric ciphers (like AES, Twofish, Serpent and DES) depend upon really complex applications of transposition and substitution, not on mathematical problems hoped to be NP-hard (when recast as a decision problem, blah, blah, blah).

    The breakthrough in the mentioned papers is just a collection of techniques used to try to create usable mathematical models of these complex mishmashes of operations, thereby allowing them to be analyzed and attacked. This is fundamentally different from public key encryption algorithms which are very simple and trivially easy to model, but reduce to models of (we hope) intractable problems.

    Whether or not it is possible to create a symmetric cipher of sufficient complexity and non-linearity that it is impossible to cryptanalyze is, of course, an open question that will probably never be fully answered. In the arms race between cipher designers and cryptanalysts the top cipher designers have always managed to stay substantially ahead of the top cryptanalysts, however. Witness the fact that DES has withstood 30 years of concerted attack, without a significant attack being found (other than the built-in small key size, of course).

    Speaking of DES, what I'm most interesting in knowing right now is if these new attacks can be applied to it. 3DES is still the most important cipher in the real world and will be for some time.

    And all bets are definitely off when quantum computers arrive on the scene.

    Again, bcrowell doesn't know the difference between symmetric and asymmetric ciphers. No one has devised a way to use quantum computers to attack symmetric ciphers. That's not to say it won't happen, but, as I understand it (not much), modelling complex problems in a QC is very, very difficult. QCs are good at simple problems with a large solution space.

    Maybe someday we'll look back fondly on the golden age of privacy.

    If we lose all of our privacy it will be because we choose to, not because of any lack of technological tools.

    • Asymmetric algorithms, by nature of their highly condensed problems(factor this number) are both vulnerable in polynomial time to an arbitrarily precise quantum computer, as Shor explains:

      "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"
      http://epubs.siam.org/sam-bin/dbq/artic le/29317

      Given that all modern crypto protocols use some variant of asymmetric crypto to transmit their symmetric key, a break in the asymmetry eventually breaks the symmetry too.

      That being said, I'm personally suspicious of quantum computing. Naive students learning about lossless compression algorithms inevitably believe they can apply the same algorithm multiple times, each time shrinking the data further and further. This actually works for some algorithms, for one or two runs. Eventually Shannon takes hold; the system refuses to compress below the level of entropy in the data (indeed, it starts to expand).

      I suspect there's an analogous limit on the quantum scale, past which entropic capacity will prevent computation at high qubit levels. I could be wrong, and I'll be suitably impressed when the hardware shows up on my doorstep. But computationally relevant quantum logic hasn't been shown yet, and we shouldn't act like "it's only a matter of time".

      It'll be something to be excited about if quantum computing proves feasible. I'd hate to see that achievement spoiled by "We've known it was possible for a decade."

      Of course, I'm just being mildly cranky. I ain't a fan of quantum crypto either -- entanglement and crypto don't work too well in the same conceptual universe. A little skepticism is useful :-)

      Yours Truly,

      Dan Kaminsky
      DoxPara Research
      http://www.doxpara.com

      • Given that all modern crypto protocols use some variant of asymmetric crypto to transmit their symmetric key, a break in the asymmetry eventually breaks the symmetry too.

        Actually, this is not always true.

        It is true of most protocols used on the net, but other areas of secure computing rely pretty much exclusively on symmetric algorithms. For example, my work is primarily in security for systems involving smart cards. Given that:

        • Distributing secure tokens like smart cards solves the key distibution problem;
        • Symmetric algorithms are more vulnerable to certain non-cryptographic attacks when performed by small devices;
        • The most common asymmetric algorithms have key sizes and processing times which strain the resources of small devices; and
        • The asymmetric algorithms with small key sizes are often encumbered by patents...

        ...symmetric crypto makes more sense. Similarly, the banking system relies almost entirely on 3DES, more because of inertia than any security reasoning but, still, PK is rare.

        In many, many real-world security scenarios, key distribution can be solved without PK, and in many cases the result is simpler and therefore more secure (complexity being the enemy of security).

        I suspect there's an analogous limit on the quantum scale, past which entropic capacity will prevent computation at high qubit levels.

        I'm not qualified to comment, but the more far-out claims for QC, even from those who understand it, seem much too good to be true.

        Of course, I'm just being mildly cranky. I ain't a fan of quantum crypto either -- entanglement and crypto don't work too well in the same conceptual universe. A little skepticism is useful :-)

        Certainly is :-)

        I see quantum crypto as an interesting idea, but in practice I don't think it offers very much over what can be accomplished with standard cryptography. Sure, it's nicer to have a theory that allows you to say "I *know* no one is tapping this line", but unless your attacker is a major world government, a good symmetric stream cipher with a decent automatic rekeying system, plus some strong message authentication codes, is perfectly adequate. Actually, it's almost certainly adequate even if your attacker *is* a major world governnment.

  • Where my cryptogram? (Score:3)

    by Leto2 ( 113578 ) on Monday September 16, 2002 @11:27AM (#4266019) Homepage
    If you're wondering why you didn't receive your Cryptogram this month, look in your spamfolder:

    SPAM: -------------------- Start SpamAssassin results ---------------------- SPAM: This mail is probably spam. The original message has been altered SPAM: so you can recognise or block similar unwanted mail in future. SPAM: See http://spamassassin.org/tag/ for more details. SPAM: SPAM: Content analysis details: (5.6 hits, 5 required) SPAM: DOUBLE_CAPSWORD (1.1 points) BODY: A word in all caps repeated on the line SPAM: PORN_10 (0.6 points) BODY: Uses words and phrases which indicate porn (10) SPAM: ONE_HUNDRED_PC_FREE (3.4 points) BODY: No such thing as a free lunch (2) SPAM: PORN_3 (0.5 points) Uses words and phrases which indicate porn (3) SPAM: SPAM: -------------------- End of SpamAssassin results ---------------------

  • quantum computing & one time pads (Score:5, Informative)

    by David Jao ( 2759 ) <djao@dominia.org> on Monday September 16, 2002 @11:41AM (#4266112) Homepage
    For a professional mathematician, reading all the uninformed opining here on quantum computing and one time pads is, frankly, painful on the eyes.

    I'm a Ph.D student at Harvard. I've done cryptography research in the past. So listen up people.

    1. Quantum computing does not destroy cryptography as we know it. It is important to realize exactly what quantum computing does and does not do. For symmetric ciphers, quantum computers reduce the cost of brute force search by a square root. So AES goes down from a 2^256 cipher to a 2^128 cipher. But 2^128 is still quite safe. And even if AES were to fall, it would not be an insurmountable problem to design something better.

      As for public key cryptography, most but not all public key cryptosystems are completely broken by quantum computers. Luckily we still have some public key cryptosystems that have not yet been broken using quantum algorithms. Elliptic curve discrete log is one such example.

    2. One time pads are not the answer. Yes the security of one time pads has been proven but this proof relies on a stronger-than-you-think collection of assumptions that is almost never realized in real life. One time pads are very useful in certain situations but completely unsuitable for cryptography as most people use it.

  • Some Clarifications (Score:3, Informative)

    by TheRealFoxFire ( 523782 ) on Monday September 16, 2002 @11:45AM (#4266131)
    I've seen a lot of mis-statements by various /.ers that I'd like to clarify:

    - ElGamal is not an elliptic curve algorithm. Its a classical public key encryption system based on the discrete logarithm problem. Most DL problems can be refactored as elliptic curve problems though, so perhaps the poster was referring to a possible EC ElGamal. At any rate, I'm pretty sure GPG uses classical ElGamal.

    - Symmetric ciphers are rarely broken by raw computational power (brute force). In fact, algorithms above about 80 bits are impossible to break by brute force due to the laws of physics.

    - Quantum Cryptography today involves means of transmitting data at very low bitrates over a channel in which eavesdropping is impossible. QC is pretty much only useful for exchanging keys for symmetric algorihms (like AES, Twofish) securely, as the data rate is to slow to be practical for anything else.

    - Assymetric Cryptography (public key) is based on several hard problems. The two that are used widely today:
    * The prime factoring problem (RSA)
    * The Discrete Logarithm problem (DSA, ElGamal)
    One will become widely available soon:
    * The elliptic curve problem

    - Yes, OTP is still perfectly secure, but its still perfectly useless, as w/ OTP you just shift the security to two other areas; truely random pad generation, and secure distribution of the pads.
  • And all bets are definitely off when quantum computers arrive on the scene.

    Well, except for quantum crypto, which IIRC is actualy as secure as one time pad.
  • The reason why the kinds of attacks which convert Rijndael in to a complex system of equations look risky for Rijndael is because Rijndael has an S-box which is very easy to describe algebraciaclly. The solution is to replace Rijndael's S-box with another S-box.

    In fact, the Rijndael designers were considering changing Rijndael's S-box during the AES process. NIST, however, for not entirely known reasons, did not allow the Rijndael designers to do this.

    Now, as it turns out, the Rijndael designers have designed some other ciphers after Rijndael. These ciphers have different S-Boxes. In fact, the Rijndael designers revised ("tweaked" as they call it) each cipher to have a representation which is easy to implement in hardware; most of the die space used when implementing Rijndael on an ASIC is implementing the S-box.

    The ciphers in question are Whirlpool [terra.com.br] and Anubis [terra.com.br] (Anubis uses an involutional S-box which might possibly make it weaker). In fact, my software project [maradns.org] does not use Rijndael proper as a psudo-random-number-generator; it uses a Rijndael variant with the "tweaked" Whirlpool S-box.

    - Sam

    P.S. I should also mention Khazad [terra.com.br], named after the bridge Gandalf fights balrog at, which uses Anubis' S-box.

Slashdot Top Deals

"If it ain't broke, don't fix it." - Bert Lantz

Close