Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

Rijndael Picked for AES 142

Posted by michael from the crackers-get-new-target dept.
^BR writes "Rijndael the Belgian algorithm candidate to being AES won the competition. It has just been announced by NIST. The scoop. Too bad for Twofish and Serpent." More info should appear at the NIST AES website soon.
This discussion has been archived. No new comments can be posted.

Rijndael Picked for AES More

Rijndael Picked for AES

Comments Filter:

  • Reasons for the selection (Score:3)

    by XNormal ( 8617 ) on Monday October 02, 2000 @09:00AM (#738628) Homepage
    It's quite likely that the reason for the selection has nothing to do with cryptography or any other technically relevent reason.

    Hitachi has a patent which all finalists but Rijndael appear to infringe. Given the fact that Twofish, Serpent and Rijndael are all very secure, efficient to implement on all relevant platforms and are more or less the same on all other technical issues the determining factor is probably the patent issue.

    Quite depressing, actually.

    (BTW, it's not just me saying that all three would have made a great AES- many of the contenstants themselves have said so).

    ----
  • The press release says to pronounce it /Rhine-Dahl/
  • While that's certainly true in Dutch, I believe in English 'Holland' is often used as a synonym [dictionary.com] for 'the Netherlands' - certainly colloquially [dictionary.com]quick check on dictionary.com [dictionary.com] seems to corroborate [dictionary.com] this.

    Sorry, not meaning to sound like a twat [dictionary.com], just wasting some time...
  • DES is also very fast in hardware, and absolutely sucks in software. It's one of the big reasons a replacement is being sought, rather than just continuing on with DESX.

    Nobody cares how fast the crypto is in hardware, really.
  • The point being, he means security through obscurity of algorithm, and you're talking about security through obscurity of data. Different things.

    Ah, but the point I was making is that the data is what is being obscured, not the algorithm. Using the switching of the gates, you can (reliably) detect where things are in the current state of the smart card. Using that information, you can determine what exactly is being read/written wrt memory. Using that information, you can determine the keys needed to unlock the smart card. The end result? The data is being obscured, not the algorithm.

  • The whole purpose of this open standard competition was to expose the algorithims to everyone. This isn't just the NSA - Every development team that developed an algorithim was composed of some of the best cryptographers around (inclding guys like Bruce Schneier)

    Then, after developing their algorithims, all these developers spent their spare time trying to break everyone else's implementation. The algorithims were open to everyone, and in some cases, they were effectively knocked out of the competition by weaknesses in their implementation.

    I realize there are exceptions and the the NSA has behaved badly in the past, but read what this competition was about and how it was run. This was probably the best peer-reviewed encryption scheme/contest/implementation ever run, and anyone with a decent knowledge of encryption can look at the algorithim and decide for themselves how secure it is. (trolls talking out of their ass won't know it, but the experts will) -

    And if you're still hung up about it, I'll bet Twofish and Serpent are going to be around for awhile. I might look at Twofish anyway for stuff I mess with.
  • I didn't mean to imply that those algorithms were any the worse for their corporate backing. I only wanted to point out that the selection of Rjindael puts cryptography in the realm where it really belongs: academia and the public domain. Any one of the algorithms would have been a decent choice, but I found it pleasing that the non-corporate offering won out.

    You don't have to be nasty about it. "Gratuitous drivel"??? What do you think Slashdot's all about man?

    -konstant
    Yes! We are all individuals! I'm not!
  • And your processor would be the equivalent of a 1.1 Ghz machine overclocked to 5.19 Nhz (1 Nhz = 1 nonillion hz [american] (1 quintillion hz british)(For those that don't know the number system that high, that is 1,000,000,000,000,000,000,000,000,000,000 hz) (See here [m-w.com] if you want to know more about the names of numbers).

    The question to ask is: Will it run Quake?

  • I read something (abcnews? salon?) that said, paraphrased, "[if moores law holds and quantum computing doesn't hit the mainstraim, we should get ~30 years out of this.]"

    That makes me nervous. I know that conspiracy theorists claim the government has wacky superior technology, and I'm a firm believer that the government doesn't pay well enough to retain such talent, but it makes me wonder just what they keep from us.

    My question is: how long does it take to deploy this new crypto the most mission critical areas? Like banks, brokers, IRS, medical, etc.?? I'm asking because let's say IBM demonstrates a QC in the next 5 years that can crack the new crypto? How soon can the infrastructure absorb and assimilate sweeping new protocols?


    ---
    Unto the land of the dead shalt thou be sent at last.
    Surely thou shalt repent of thy cunning.

  • First Hand Report (Score:5)

    by bde123 ( 239218 ) on Monday October 02, 2000 @09:05AM (#738637)
    NIST is just down the street from where I work, so a co-worker and I crashed the press conference. After navigating the sprawling government expanse, we arrived at the lecture room only to be interrogated as to what press organization we are from. Mind you, showing up in t-shirts and shorts probably didn't help our credibility much, so I claimed that we were from Slashdot and we were allowed in with a shiny press kit. The small audience was divided up between press people and stiff jaw types in conservative suits and ties. (spooks) I can't decide, though, which group decided to stare more at our hacker apparel, wondering who let the 2 techies in. To NIST's credit, the evaluation of the various algorithms seems to have been done totally in the public eye. The analysis of the various candidate algorithms is supposedly posted publically and the algorithms are royalty-free. Plus, no modifications were allowed to the algorithms, so it's fairly unlikely that the NSA got their fingers into it. To give props to SecurityFocus, a representative questioned the involvement of the NSA and asked why we should trust the government.
  • >Twofish, RC6, Mars, etc were basically all ego-gratification projects intended to maintain corporate visibility in the cryptography market

    This is, to be polite, bs. Different cryptographic approaches merely reflect different "scientific" schools or preferences.

    Pluses and minuses can exist in different proposals without the them being easily attributable to gratuitous drivel from the peanut gallery.

  • Smart card applications the key consideration? (Score:5)

    by BitMan ( 15055 ) on Monday October 02, 2000 @09:06AM (#738639)

    In addition to the open-ended key size of Rijndael, after reading the AES Round 1 report [nist.gov], it looks like smart card applications were a key consideration (possible THE key?).

    With smart cards, the issue is two fold. One, you need small code footprint, which both Rijndael and TwoFish did satisfy. And, two, the main means to hack smart cards is via power/EMI analysis.

    Any circuit draws power and puts out EMI with the switching of its gates. Since there are power draws when they switch, the two are usually intertwined. I am familar with these because this because Theseus Logic [theseus.com]'s (my employer's) NCL (null convention logic) technology is ideal for smartcards because of its more uniform power (gates switch independently so they are not switching and drawing power at the same time) further resulting in a drastically reduced EMI signature compared to CBL (clocked boolean logic). In addition to being reduced, the power/EMI signature it looks nothing like CBL and those years of learning what CBL circuits look like from a power/EMI standpoint are not applicable to NCL at all.

    TwoFish uses a very predictable addition subroutine that would put out a reguarly timed power/EMI signature. Rijndael seems to reduce its use of such easily identifyable operations (at least when analyzed under [6] in the report).

    [ BTW, one thing I didn't understand was this statement about TwoFish: "During Round 1, there were a few concerns regarding the overall complexity of its design." Anyone know what they meant by this? ]

    -- Bryan "TheBS" Smith

  • Re:This is a sad day for Belgium (Score:1)

    by Anonymous Coward
    +1, best troll posted today.

    outstanding!

    when do the trolympics officially kick off?

  • Where did you see this? Do you know the article/patent # for this patent?

    I would like to look this up and read it.

    Thanks.

    StickBoy
  • How does it work? Does it translate everything into Dutch?

    Looks like double Dutch - it's more secure.
  • Any predictions on how long it will take someone to crack this encryption method?

    You can sure bet people will start trying!

    Perhaps it will be a future project for distributed.net [distributed.net]?

  • Public domain Java implementation (Score:3)

    by iXus ( 21877 ) on Monday October 02, 2000 @08:26AM (#738644)

    Cryptix [cryptix.org] releases it's Java implementation of Rijndael in the public domain. The BSD licensed Cryptix is also the first crypto toolkit that officially supports the AES.

    Open source rules!

  • Rijndael is just as secure as the other finalists. Every other finalist also had published attacks versus reduced round versions. The paper you refer to talks about attacks on reduced round variants. In particular, the 9 round attack on Rijndael requires not only encryption of chosen plaintexts, but also encryptions under 255 other keys related to the secret key in a manner chosen by the adversary.

    However, the AES paper talks about these reduced round variants saying,

    It is difficult, however, to extrapolate the data for reduced-round variants to the actual algorithms. The attacks on reduced round variants are generally not even practical at this time...As noted earlier, no general attacks against any of the finalists is known. Hence, the determination of the level of security provided by the finalists is largely guesswork.

    They also note that since Rijndael had one of the simplest structures that it received a disproportionate amount of review downward biasing its security relative to other contenders. Twofish, for instance, on the other hand is very complicated, making analysis difficult during the timeframe of the AES development process.

    Do you have any rational reason for preferring an algorithm that received very little cryptanalysis over one that received tons of it and was found that nothing short of a brute force search over its keyspace would suffice?

    Government agencies and contracts are going to require AES. Large businesses are going to use AES. Everyone will use AES. That is why the AES panel had a vested interest in choosing the best algorithm. And they picked Rijndael. Having read their final report, unless you're a competent cryptanalyst (I don't know about you, but I'm not) I don't see any reason to doubt the competence of the AES selection panel or their final selection.
  • "Too bad for Twofish and Serpent."

    Still, that doesn't prevent us from using it. I'd much rather see the people have the better encryption algorihm. :-)
  • I swear this story appeared not two seconds ago, and already the site is down for the count.

  • I'm not quite sure I buy your conjecture.

    Let's say Mr Merkle designs a chip that's 99.9999% efficient at reversing the computation, including factoring in the extra gate counts for the circuit.

    Now, throw a generously tight 10000 bit twiddles at each key.

    That's 1% of his original figure, for ~84 days of the full output of the sun. Yeah, we should be able to manage that, no problem.

    He says, tongue firmly planted in cheek.



    -

  • According to the paper, for the number of rounds specified, there is no known attack that is stronger than exhaustive key search. Hence, adding rounds will add nothing to security. You have to increase the key length to achieve this.

    Although NIST is reasonably certain that Rijndael is secure with the specified number of rounds, this is no guarantee that it is this strong against future attacks. No proofs of it's security were made, only assertions. It is possible that increasing the number of rounds would provide protection against future attacks.

  • Yes, but as someone else pointed out, in two-way communication, RSA (or something like it) is still typically used to pass the "session" keys that are used to do the block ciphering. No matter how good your block cipher is, it is still at the mercy of whatever you use to exchange the keys.

  • Rational for Rinjdael (Score:4)

    by nweaver ( 113078 ) on Monday October 02, 2000 @09:17AM (#738651) Homepage

    For those who are interested in technical analysis, the NIST Report [nist.gov] is online.

    The basic gist of the report is that all algorithms are secure to NIST's comfort, with a large number of various details. The main reason for selecting Rinjdael over the other algorithms came down to performance.

    Whereas the other algorithms either ran well or poorly depending on the platform (Serpent poor in register-poor software and a large initial requirement for hardware, Twofish being very slow for software subkey generation, MARS requiring 32 bit multiply and having awful subkey generation, and RC6 also requiring 32 bit multiply and poor subkey generation), Rijndael runs well regardless of platform, be it hardware or software, smartcard microcontroller or IA64.

    I also seriously doubt that the Hitachi patent claim had anything to do with the selection. IT was not even mentioned in the report on the IP section, and was incredably vague (Hitachi was claiming a patent on rotation in encryption. The Caesar cypher could probably be claimed as 2000 year old prior art).


    Nicholas C Weaver
    nweaver@cs.berkeley.edu

  • Please see the fact sheet before spreading misinformation:

    The algorithm's developers have suggested the following pronunciation alternatives: "Reign Dahl," "Rain Doll" and "Rhine Dahl."

    From the AES Fact Sheet [nist.gov].

    -Adam
  • NSA swiping patents has nothing to do with NIST choosing an algorithm for use by the general population. The AES choice is intented to be available without years of court battles about patents. And in this case the USA seems to want a standard that can be used globally, which non-US patents might interfer with no matter what the NSA said.

    So if Rijndael wasn't invented here where was it? Oh, I see, you're a US-AC vs a Dutch-AC.

  • You can read Hitachi 's letter [nist.gov] in the Round 2 Comments section of the AES site.

    It's clear from the IP Issues forum [nist.gov] that this was a concern. It will be interesting to see whether the final announcement mentions the patent.

    I don't know whether the other algorithms actually infringe; I suspect it's a case of CYA, given NIST's "Speak now or forever be sued" note regarding IP.

  • Re:I think Rijndael is the best candidate (Score:5)

    by slickwillie ( 34689 ) on Monday October 02, 2000 @09:26AM (#738655)
    How does it work? Does it translate everything into Dutch?
  • Dude, I'm gonna have to go with Belgian fries for supper tonite to celebrate!

    (aww, woulda done it anyways ;)

    Your Working Boy,

  • From the Rijndael FAQ: Can't you give it another name ? (Propose it as a tweak !)
    [snip]
    I second the call for "bob"! (although I would've supported "peter", too)

    Or you could just call it "AES". At least, you can now. :)

    It will probably be called "AES". Just as people call it "DES" instead of "Lucifer" (although in that case they really are different algorithms).

  • The question to ask is: Will it run Quake?

    Sure it will run quake as long as you don't mind being in a really strong radiation field. You're processor and mainboard would be emitting gamma rays (possibly cosmic radiation) which carry a wavelength around 10^-22 m (extremely high energy)

    This would most likely kill you within a few hours, possibly less depending on how much you catch. At the very least don't expect to have any kids. Lead vests aren't doing to do you much good here, just make sure you've got a couple meters of lead between you and your computer. That is of course assuming you can keep it cool (which with today's technology would be imposable)

  • The guy I talked to who worked for the NSA on math/crypto said the NSA would not disclose any weakness they found, but they would advise NIST whether a given algorithm was good or bad. So, if you trust them (I do on this count), they would keep NIST from choosing a code they could crack, but not reveal how to do so.

    It was supposed to go something like:

    NIST: We have these 6 finalists. We think we would like to use #2.
    NSA: You really don't want to do that.
    NIST: Ok, how about #6?
    NSA: Sounds good.
    NIST: #6 it is!

  • Nonsense. When IBM was first contracted to develop DES it was developed with a 128 bit key. The NSA forced IBM to lower it.
  • The Hitachi patent claim basically covers combining the output of one stage with a bit shitfed copy of that same output to create a new output, in a reversable format.

    i.e., they patented: a2 = a1 ^ ( a1 << 1 );

    The patent examiner should be fired. His boss should be fired, and his boss, ad nauseum.

    'course this is how things work today, so now we have a, AES cipher with weaknesses especially suited to hardware cryptanalysis. Sure that was entirely coincidental.
  • Maybe the key 2^84-1 is equivalent to rot13?

    Then don't use that key. If there are only a "few" (say 10 billion), the chance of selecting one of them randomly, is almost nil. Presumably the reviewers focused on checking for weak keys, among all the candidates.
  • Aha, this is why we use Triple-DES (the odd number of encodings is resistant to these meet in the middle attacks). So, how about using Triple-AES? Or even better, how about a TripleDES-AES-Twofish triple, for the really paranoid? I'll write the key down on a pad that I keep in my desk drawer.

  • I would vote for 'koeieuier' as the official name of the algorithm, as proposed on the Rijndael webpage ;-)

    Maybe some application making use of the algorithm could be named 'koeieuier'

  • Plus, no modifications were allowed to the algorithms, so it's fairly unlikely that the NSA got their fingers into it. To give props to SecurityFocus, a representative questioned the involvement of the NSA and asked why we should trust the government. And that's good? The NSA had their fingers in DES and from all accounts, including Coppersmith's, they made it stronger.

  • Good commentary from Counterpane (Score:3)

    by Eck ( 2901 ) on Monday October 02, 2000 @09:30AM (#738666)
    The commentary [counterpane.com] by folks over at Counterpane (Bruce Schneier, et al) seems quite good. They say good things about Rijndael, regardless of whether they really wanted their own Twofish to win out.

  • This is just frickin' lovely... (Score:1)

    by Anonymous Coward
    ...just when the "how do you pronounce Linux" discussions finally die down, this comes along.

    The next thing I invent in this business will named Bob. I promise.

  • Re: Rijndael Picked for AES (Score:3)

    by AnUnnamedSource ( 174313 ) on Monday October 02, 2000 @09:33AM (#738668) Homepage
    Now that No Such Agency has found a way to crack it. ;-)

    -- "On second thought, let's not go there. 'Tis a silly place."

  • It will be interesting to see whether the final announcement mentions the patent.

    Oops, I should have kept reading. The Report on the Development of the AES [nist.gov] does have a statement that seems to indirectly reference Hitachi's patent claim: "After comments were analyzed, and the review process was completed, IP was not a factor in NIST's selection of the proposed AES algorithm."

  • Sure, if they do it in public, it's great.

    But there's also stories that they modified the initial values of DES in such a way as to weaken them.

  • NIST encouraged competing cryptographers and the NSA (the world's largest employer of cryptographers and mathematicians) to critique the algorithms, building up a body of review that led to today's choice of the new standard.

    I love this statement. Do you really think the NSA would tell the outside world if they discovered a weakness? It would be in ther best interest to sit on the knowledge so they can use it. Let everyone else out there be complacent that the data is secure while the NSA (and possibly some other trusted agencies) use it for monitoring.

  • Re:From the Cryptix List (Score:3)

    by iXus ( 21877 ) on Monday October 02, 2000 @09:47AM (#738672)

    Do you really think the NSA would tell the outside world if they discovered a weakness?

    People thought the same thing about DES. It turned out that the NSA had indeed tweaked the algorithm: they made it stronger!, so it could resist an attack the outside world had not discovered yet.

  • Nobody cares how fast the crypto is in hardware, really.

    A lot of people care very much how fast the crypto is in hardware (and how much the absolute minimum memory needed is.

    Smartcards are expected to become more and more widespread, and will often need some form of crypto on them. These are very restrained environments where the last byte matters.

    Furthermore, if you wish to build a secure network (or a VPN), network adapters that automatically encrypt all traffic is a way to do it. This also requires hardware encryption.

    So encryption in hardware is important.

  • [ BTW, one thing I didn't understand was this statement about TwoFish: "During Round 1, there were a few concerns regarding the overall complexity of its design." Anyone know what they meant by this? ]

    I think that I do. There's really two problems with a very complex cipher. First, a complex cipher can be harder to analyse, thereby increasing the probability that a hidden flaw isn't found before the competition is over (3-4 years is a short time for cipher analysis).

    Secondly, a complex design makes implementation harder, increasing the probability that a hidden flaw in the implementation exposes the cleartext.

  • I'm not either, but that won't stop me :)

    It really should have :-)

    Factoring a 256-bit number using Shor's algorithm for a quantum computer should take up to 769 qubits (we have, what, 5 or 7 so far?) and runs in O((lg n)^2 * lg lg n), which is O(really fast). For a 256-bit n the inner part works out to 524288, which doesn't tell you much but at least you can see it doesn't grow that fast.

    Factoring a 256 bit number is not really that hard. A 512 bit number has been succesfully factored using normal computers. Furthermore factoring has absolutely nothing to do with this. Factoring is for breaking assymetrical ciphers.

    Furthermore, noone has shown that quantum computers can be used for breaking symmetrical ciphers, they are not magical in any way.

  • At last some positive news involving Belgium! Plus it's nice to so some noted work come out of the university I went to! Congrats to those involved!
  • Nee hoor, "daal" is de correcte spelling. Dat het niet meer in de alledaagse taal wordt gebruikt, is irrelevant. En "daal" betekent vallei.

    Wel, als het niet meer gebruikt wordt is het archaïsch. En kan je veel beter "dal" gebruiken. Q.E.D.

    Well, if it's not used anymore, it's archaic. En it's better to use "dal". Q.E.D.

  • not true. Mother Russia does this all the time :).

    --

  • Ask Qualcomm or Nokia if they don't care how fast in hardware Rijndael is... moron.

    --

  • Check out this link [counterpane.com]. Cryptanalysis has already begun to reduce the complexity considerably.
  • Rijndael is such a good encryption scheme that it even protects us from reading information about it on their web servers!
  • As a tool, code for the new AES algorithm is less than 10,000 bytes, and thus cryptography slips into the average application with less implication on costs than the price of a new PC.

    wtf?

  • With mayonnaise. Like John Travolta.

  • Re:From the Cryptix List (Score:3)

    by Vryl ( 31994 ) on Monday October 02, 2000 @10:08AM (#738684) Journal
    This is a good point. NSA paranoia is all good and proper, but moderated with some common sense, please.

    I seriously doubt the security establishment would allow the finalist to have a weakness that they discovered in what is really quite a short amount of time. If they disovered it, then so could someone else. The 'national security' danger is actually much higher with a compromised AES candidate, than with one that the NSA can break. [insert rant on infrastructural warfare]

    Strong crypto is here to stay, and I think finally the NSA realises this. The US and others are all better off with strong crypto than without it.

    As others have pointed out at other times, most crypto schemes fail due to weaknesses in implementation or human protocol reasons, not due to weaknesses in the underlying cypher, so there is still plenty of latitude for the NSA. Have you tempest hardened your PC lately? Checked your keyboard for surreptitious key-logging gear? Installed 24/7 armed security guards in the server room?

  • Is factoring numbers that useful for symmetric key encryption? I thought that this was mostly useful for breaking RSA and related public key encryption systems.

  • The NIST made statements that they would protect all users of the algorithm in case a patent issue came up. In other words, Hitachi would have to deal with the US Govt to resolve the issue, not the people who implemented it.

  • Oh yeah? They can scare people into submission. Fancy a twenty-something years in a federal high security facility for treason?

    You can't force someone to create, nor invent.


    ---
    Unto the land of the dead shalt thou be sent at last.
    Surely thou shalt repent of thy cunning.
  • And "those years of learning what CBL circuits look like from a power/EMI standpoint are not applicable to NCL at all" looks like security by obscurity.


    You're right, it is. However, security through obscurity should always be one facet of a security plan. To use the tired old bank analogy, you get a very good combination lock on your safe. And then you don't give out the combination. Your lock is your open source security (everybody knows how strong it is). Your combiation is your private key.


    On the other hand, if you don't believe in security through obscurity in any fashion, perhaps you would be so kind as to provide the following information:


    1. All passwords known to you.
    2. Your government issued ID number (here in the states, your Social Security Number).
    3. Your mother's maiden name.
    4. Names, expiration dates, and numbers of all credit card numbers you have.
    5. Any other information about you which may be helpful in performing an identity theft.

  • I wanted Twofish to win just because of Bruce Schneier and what I've learned from him about cryptography. His book on Applied Cryptography has taught me almost everything I know. Still, even his analysis concluded that either Twofish, Rijndael or Serpent would make a good standard (MARS and RC6 were either too bloated, slow, or insecure) - although he felt Twofish was a better tradeoff overall. I can't make a judgement cause I'm not at a level to make that decision. (Hell, I'm not that good yet, otherwise I wouldn't be just a WAN engineer)

    Bruce's analysis of the algorithms is interesting and can be found at http://www.counterpane.com/crypto-gram-0004.html - There are also papers on counterpane's website showing some comparisions that do put Rijndael at a pretty good spot - usually side by side with Twofish.
  • With smart cards, the issue is two fold. One, you need small code footprint, which both Rijndael and TwoFish did satisfy.

    And RC6 and MARS did not. In fact, MARS takes up more than 200 bytes of RAM : more than is on most 'smart' cards. Although you might be able to adjust to algorithm to get this down the ~100 (the same as RC6), Twofish, Serpent, and Rijndael are all 50-60.

    There's a really interesting paper on AES candidate performance here: http://www.counterpane.com:80/a es- comparison.pdf [counterpane.com]

  • Oh my, I kinda wish they had chosen "koeieuier" (cow-udder). That would have been impossible to pronounce for anyone who doesn't speak Dutch ;-)

    So, does anyone know why they named it Rijndael? Its meaning (Rhine-valley) doesn't have anything to do with encryption, plus they used an archaic spelling (correct would be Rijndaal). Is there a person or place involved with that name?

  • Re:let the cracking begin... (Score:3)

    by milkman1 ( 139222 ) on Monday October 02, 2000 @11:14AM (#738693)
    Does no one read the errata for books before quoting them as truth. See:
    http://www.counterpane.com/ac2errv30.html

    * Page 157: The section on "Thermodynamic Limitations" is not quite correct. It requires kT energy to set or clear a single bit because these are irreversible operations. However,
    complementing a bit is reversible and hence has no minimum required energy. It turns out that it is theoretically possible to do any computation in a reversible manner except for copying
    out the answer. At this theoretical level, energy requirements for exhaustive cryptanalysis are therefore linear in the key length, not exponential.
  • Don't be foolish. It will translate it into Flemish. ;-)
  • IANA Cryptography Specialist but what about chaining two of the algorithms?

    I remember that in PGP the message is compressed first (so the amount of redundancy is minimised) and then encrypted.
  • Ok Sherlock, if you _really_ distrust the NSA, Rijndael, Twofish etc etc. and are ultimately paranoid that no algorithm ever invented by any country/government body/research or educational institution/company/etc. why don't you use the one-time pad then? A moron could understand its principle, the only problem you got there is how are you going to hide/transport the keys which will be stored on some high density media? Sheesh, have a little faith in the world's eye on cryptology...

    --

  • It's ad nauseam, spell-meister :).

    --

  • Of course the data on the smart card has to be secured. But BitMan didn't claim that it was more difficult to spy on NCL than on CBL. He said that nobody did study it, yet.
  • Here's an interesting point on that exploit, from the NIST Rijndael FAQ... If you could crack a DES key in 1 second, how long would it take to brute force that 128bit key? Hint: I'm feeling pretty safe :)

    16. What is the chance that someone could use the "DES Cracker"-like hardware to crack an AES key?

    In the late 1990s, specialized "DES Cracker" machines were built that could recover a DES key after a few hours. In other words, by trying possible key values, the hardware could determine which key was used to encrypt a message.

    Assuming that one could build a machine that could recover a DES key in a second (i.e., try 2^55 keys per second), then it would take that machine approximately 149 thousand-billion (149 trillion) years to crack a 128-bit AES key. To put that into perspective, the universe is believed to be less than 20 billion years old.
  • urgh.. koeieuier.. it's even worse than zeeeend.

    it's also misspelt, and should be koeienuier in the new spelling. ;) I wonder how english speakers would pronounce it...

    //rdj.
  • [Meg Ryan] Who is this "Bub" you keep talking about

    [Kevin Kline] You know, Bub, as in Bub Deelan

    [Meg Ryan] Oh, you mean Baaaaahhb!

    Regards, Treefrog

  • Here [kuleuven.ac.be] it is.

    Don't try this with IE, since it won't work:
    *** Error 404: Wrong Browser ***
    I am sorry to inform you that this page is not accessible with Microsoft's Internet Explorer.

    I had a good laugh when I tried it and saw the error message. On purpose I assume, since his page reveals that he is a Linux fanatic and obviously doesn't like MSFT.
  • ... by the Technical Advisory Committee to Develop a Federal Information Processing Standard for the Federal Key Management Infrastructure [nist.gov] which chooses to refer to itself as "Bob" rather than "TACDFIPSFKMI". See here [mit.edu] if you don't believe me. As they both have something to do with Federal crypto standards, it would be too confusing to have them both named "Bob".
  • ..people working for government are no gods. They understand very well that if for any reason they discovered a weakness in the algorythm, they may very well expect somebody (probably some whiz kids in ex-KGB lab) will find it out as well. They have no interest to offer a weak algorythm for a standard - well, if they do, they are dumber than I thought.. To spy on us there are many more methods than an encryption backdoor.

  • Re: increasing security (Score:4)

    by __aawsxp7741 ( 78632 ) on Monday October 02, 2000 @10:24AM (#738706)
    Secondly, if you increase the number of rounds in Rjindael you can effectively double the security, and even then it is still one of the fastest candidates in software.
    Where did you get this? According to the paper [nist.gov], for the number of rounds specified, there is no known attack that is stronger than exhaustive key search. Hence, adding rounds will add nothing to security. You have to increase the key length to achieve this.
  • In addition to the open-ended key size of Rijndael, after reading the AES Round 1 report, it looks like smart card applications were a key consideration (possible THE key?).

    This shouldn't come as a surprise because John Daemen [kuleuven.ac.be] is currently working for ProtonWorld [protonworld.com], a Belgian smart card company. Millions of people here in Belgium are using their e-purse smartcards daily to make small payments. I wouldn't be surprised if RijnDael is the main algorithm behind Proton [protonworld.com].

  • As others have pointed out at other times, most crypto schemes fail due to weaknesses in implementation or human protocol reasons, not due to weaknesses in the underlying cypher, so there is still plenty of latitude for the NSA. Have you tempest hardened your PC lately? Checked your keyboard for surreptitious key-logging gear? Installed 24/7 armed security guards in the server room?

    Of course, the armed guards have to be sufficiently well-paid (and well-vetted). It's often even easier to compromise people than hardware.

  • I think Rijndael is the best candidate (Score:4)

    by Kiwi ( 5214 ) on Monday October 02, 2000 @08:29AM (#738717) Homepage Journal
    I feel that Rijndael [google.com] (Google mirror, main page slashdotted) is the best candidate because it has the following advantages over the more populsr Twofish:
    • Rijndael has better performance on hardware than Twofish.
    • Rijndael is more extensible. In addition to a variable key size, Rijndael has a variable block size.
    I am very pleased to see Rijndael become the new AES standard.

    BTW, you pronounce it "Rain Doll".

    - Sam

  • Have a look at this table [cryptosavvy.com] from a paper by Arjen Lenstra and Eric Verheul. 128 bits of security should be more than enough until way beyound the year 2040 according to them.

    Distributed.net would need 2^64 more times processor power to crack Rijndael than it needs to crack RC5-64... so don't expect that to happen soon.

  • More information (Score:5)

    by fremen ( 33537 ) on Monday October 02, 2000 @08:35AM (#738724)
    More information can be found on the Rijndael algorithm here [nist.gov]. This link includes a copy of the white paper [nist.gov] on the algorithm in PDF format, as well as the source code [nist.gov].

  • From the Cryptix List (Score:5)

    by Vryl ( 31994 ) on Monday October 02, 2000 @08:36AM (#738727) Journal
    Date sent: Mon, 2 Oct 2000 12:36:00 -0400 (AST)
    From: Ian Grigg
    To: cryptix-users@cryptix.org
    Subject: Rijndael is GREEN
    Copies to: coderpunks@toad.com, cryptography@c2.net, cypherpynks@cyberpass.net, dbs@philodox.com, iang@systemics.com
    Send reply to: iang@systemics.com

    For Release 11.00 EDT Monday 2nd October 2000

    Rijndael is GREEN

    NIST chooses Rijndael as the Advanced Encryption Standard

    Announced today in Washington, DC, the National Institute of Standards and Technology (NIST) has chosen Rijndael as the Advanced Encryption Algorithm for the 21st century.

    Rijndael -- pronounced Rhine-Dahl -- is the creation of two Belgian cryptographers, Joan Daemen and Vincent Rijmen.

    The Cryptix Development Team congratulates Vincent and Joan on their extraordinary achievement and announces the immediate release of the Cryptix JCE and Cryptix 3.2, both enabled with AES as Rijndael.

    International Cryptoplumbing

    An international team of open source crypto volunteers from The Cryptix Development Team supported the cryptographers participating in the NIST contest, efforts that were recognised with the award of a Certificate Of Appreciation from the United States Department Of Commerce.

    Raif S. Naffah, from Australia, led the Cryptix AES Support Project which provided the Java code and tools for most finalists, including Rijndael, for submission to NIST.

    Paulo Barreto, Brazilian mathematician and programmer, provided coding support for optimising Rijndael implementations; he has been coding and reviewing algorithms for the Belgian team for many years, including the predecessor to Rijndael, the Square cipher.

    Free Crypto

    Under the terms of the NIST contest, Rijndael is free and unencumbered for all purposes and all peoples. Cryptix developers have agreed to match this condition, and hereby place their Rijndael code in the public domain.

    Normally, all Cryptix code is free for all purposes, but requires acknowledgement of The Cryptix Foundation as owners under an extremely liberal "BSD licence." Even this condition is now dropped for the Rijndael code, so that all commercial providers of Java cryptography, including Sun, Baltimore, RSA Labs, and IAIK, may quickly offer their customers the best code.

    No Arms Race Need Apply

    Cryptography has long been treated as a munition by the US government. Today's decision marks the end of an era stretching back to the days of Enigma and Magic intercepts. The new algorithm and the accompanying code base is absolutely unimpaired by political or commercial limitations.

    As a science, cryptography is the special domain of mathematicians; formulas flow across borders as fast as emails. As an idea, the Rijndael cipher can be written out in 10 or so pages of paper, making it impermeable to regulations.

    Fuel For The Revolution

    As a tool, code for the new AES algorithm is less than 10,000 bytes, and thus cryptography slips into the average application with less implication on costs than the price of a new PC. As a building block, AES will help to fuel the new industrial revolution in electronic commerce. Ciphers such as Rijndael will keep valuable messages secure in the wild west of the Internet far better than the old methods of obscurity and regulation.

    Released by The Cryptix Foundation Limited, a Nevis corporation dedicated to the spread of strong crypto.

    Links:

    NIST announces the winner of AES as Rijndael:

    http://www.nist.gov/aes/

    The Rijndael page of the Cryptography team, Joan Daemen and Vincent Rijmen:

    http://www.esat.kuleuven.ac.be/~rijmen/rijndael/

    Cryptix places Rijndael code in public domain:

    http://www.cryptix.org/aes/

    Cryptix products JCE and Cryptix 3 now released with Rijndael as AES:

    http://www.cryptix.org/news/02102000.html

    http://www.cryptix.org/products/jce/index.html

    http://www.cryptix.org/products/cryptix31/index. html

    http://www.cryptix.org/products/aes/index.html

    About The Rijndael Team

    Dr Joan Daemen is currently employed by Proton World International. Dr Vincent Rijmen is a cryptography researcher with Katholieke Universiteit Leuven in Belgium.

    About Cryptix

    Java cryptography was first provided under the label of Cryptix in 1996. The Cryptix Development Team now includes crypto- plumbers -- programmers who work with the algorithms and ciphers of cryptographers to produce code and applications -- from 8 countries and publishes the most popular Java cryptography suite.

    Cryptix products are generally published under the BSD licence, making them free for all purposes when used with due acknowledgement as to source. The Cryptix implementations of Rijndael, written as part of our AES support project, are now placed in the public domain so that all commercial suppliers can proceed to support the AES without having to give any acknowledgement.

    About National Institute of Standards and Technology

    The National Institute of Standards and Technology (NIST), an agency of the U.S. Department Of Commerce, is charged by the US Congress with developing standards for industry. Many of its standards achieve world-wide acceptance, and the predecessor DES has been accepted as the de facto standard for encryption for three decades, albeit with much controversy.

    About the Advanced Encryption Standard

    In order to allay concerns of interference, NIST sponsored the open competition for the new algorithm, encouraging entries from around the world. Some 21 submissions were narrowed down to five finalists.

    NIST encouraged competing cryptographers and the NSA (the world's largest employer of cryptographers and mathematicians) to critique the algorithms, building up a body of review that led to today's choice of the new standard.

    End.

  • Of course, perhaps Quantum computing may change some or all of this, but I am not qualified to comment on that.

    I'm not either, but that won't stop me :)

    Factoring a 256-bit number using Shor's algorithm for a quantum computer should take up to 769 qubits (we have, what, 5 or 7 so far?) and runs in O((lg n)^2 * lg lg n), which is O(really fast). For a 256-bit n the inner part works out to 524288, which doesn't tell you much but at least you can see it doesn't grow that fast.

  • Re:let the cracking begin... (Score:5)

    by Anonymous Coward on Monday October 02, 2000 @10:46AM (#738732)
    The usual thermodynamic argument is simply incorrect. There is no lower limit to the energy required to perform an operation, as long as the operation is reversible. Ralph C. Merkle (from XEROX PARC) has done very recent work on this that raises the possibility of actually constructing such a computer, as opposed to the theoretical possibility of designing a computer that requires no energy to operate. You might also try the work of Samuel Olesky, Victor Chung, and W. Toynston, but their work tends to be much more technical. Schneier might be a good cryptographer, but he isn't a very good physicist (nor should he be expected to be). QC has nothing to do with this at all; an entirely classical computer can be made reversible.

    To quote from Merkle's conclusion: "In summary, reversible computations are consistent with the basic laws of physics at a microscopic scale, while irreversible computations are in some sense fundamentally incompatible. The price we must pay for this incompatibility is heat. If we don't want to pay the price then we must learn to compute in harmony with the natural laws of physics, e.g., we must learn how to design reversible computers."
  • Quantum computing won't change this (in the forseeable future) for two reasons:
    1. # of Qubits

    2. The current state of the art quantum computer does not have enough qubits to really do anything useful. The progress rate (how often the number of qubits is upped) is not fast, and I suspect it will slow at the larger numbers as it gets much harder to make sure that some cosmic ray doesn't hit your machine screwing it all up ("measuring" the state).
    3. No quantum keysearch algorithm

    4. Quantum computing isn't some silver bullet that solves every crypto problem instantly. Quantum computers are very fast at factoring and at taking discrete logarithms, which most modern public key algorithms are based on. However, to this day there aren't any general quantum algorithms for exhausting a keyspace quickly. Don't believe the inaccurate "does everything but in parallel" descriptions that the tech media keeps spouting off. It's not telling the whole story on how quantum algorithms work. To do things in parallel, the bogus answers (keys here) must cancel each other out (like in vector addition), leaving the real answer. You can't just say, "try all keys at once". It's not that simple.
  • Feynman wrote about reversible computing, too. (I really enjoyed reading a collection of his work called "The Physics of Computation.") From what I remember, reversible computing has no energy requirements as long as you're willing to wait arbitrarily long for the result. Since the computation is reversible, the computing process is as likely to go backwards as forwards without any driving force. So, if you actually want an answer within the lifetime of a universe, you do in fact need to use some energy. But IANA physicist, just married to one.
  • I think this may have been falsely identified as a troll.

    While most technically savvy readers know that public code review is more important for cryptographic systems than any other kind of software, I think that Froid is simply still in the "security through obscurity" frame of mind.

  • So, does anyone know why they named it Rijndael?

    From the cryptix release:

    Rijndael -- pronounced Rhine-Dahl -- is the creation of two Belgian cryptographers, Joan Daemen and Vincent Rijmen.

    Sounds like it's named that way to get Rijmen and Daemen in there.

    Zombies heersen over Belgie!
    (Zombies rule Belgium!) -- Zippy the Pinhead.

  • Any predictions on how long it will take someone to crack this encryption method? You can sure bet people will start trying!

    Ciphers should always be attacked for weaknesses, and attacks on the 5 AES finalists began the moment they were submitted, and they will (and should) continue.

    In it's securist implementation it's likely that key exhaustion is the only way to crack this one.

    Rich...

  • >BTW, you pronounce it "Rain Doll".

    As opposed to ridg-en-dale or free-beer?

    --
  • Yes, that is just "one" portion of the benefits. Just like when dealing with security, obscurity is NOT the "main" one.

    -- Bryan "TheBS" Smith

  • The NSA DID strengthen DES (Score:5)

    by nweaver ( 113078 ) on Monday October 02, 2000 @12:19PM (#738761) Homepage

    The NSA tinkered with DES in two manners: Changing the S-boxes and reducing the key length. Both of these actually were done to strengthen the algorithm.

    The S-box changes were rather mysterious, and were the origin of major speculation on the NSAs motives. However, when differential cryptoanalysis was discovered (about 15-20 years later), it was discovered that the S-box tweaks were specifically to strengthen DES against differential attacks. The NSA specifically modified the cypher to defend against a then publically unknown attack.

    The second, reducing the key size, happened to also coincide to the differential behavior of DES. The core of the algorithm itself is really only about 2^56, not 2^64 in terms of work to cryptoanalyze. The key length was reduced to accuratly reflect the other cost of breaking the algorithm.

    Remember, the NSA has a STRONG interest in insuring that the AES winner is a quality algorithm, since it will be used for secure but unclassified US government communications.[1] Also, while at the AES conference, talking with one of the NSA representatives, he was very happy with the security of all 5 algorithms and the process, that all the algorithms the NSA didn't like were eliminated in the first round.

    [1] For classified systems, the NSA will still probably use their own algorithms, although this isn't suprising since the entire systems tend to be much more sophisticated in terms of system security. COTS solutions don't work for that market.


    Nicholas C Weaver
    nweaver@cs.berkeley.edu

  • But there's also stories that they modified the initial values of DES in such a way as to weaken them.

    There have been lots of stories like that. However there is the fact that DES-with-NSA changes is resistant to diffrentional cryptoanalsis, and DES-without-NSA-changes falls to a DA attack much faster then brute force keysearches.

    So if the NSA weakened DES they accidentally also strengthened it. More likely they "just" strengthened it. It does show that they (use to) have at least a 15 year lead. Probbably shortened a bit by now, but who knows?

  • Re:Encryption Blues (Score:4)

    by nweaver ( 113078 ) on Monday October 02, 2000 @12:31PM (#738763) Homepage

    1.Rijndael is harder to implement than, say Serpent, in my opinion.

    I don't understand why you would say this: The Rijndael algorithm (Just call it "rain-doll") is probably the second simplest AES algorithm to implement[1]. True, the paper can be a little bit confusing for an implementer (since it begins with the mathematical motivation), the algorithm itself is incredably easy: The S-box is a table lookup. The key addition is XOR. The row shift is just a byte manipulation. And the column mixing is simply 4 table lookups and XORs.

    Compare this to Serpent, which requires a rather arcane set of sbox optimizations to run well, or the very complicated structures of Twofish or, glod forbid, MARS.

    [1] The only easier one is RC6, which has been described as something you can specify on a cocktail napkin.


    Nicholas C Weaver
    nweaver@cs.berkeley.edu

  • Square was the predecesor to Rijndael: It had some vulnerabilities which Rijndael was designed to correct.


    Nicholas C Weaver
    nweaver@cs.berkeley.edu

  • bob? Sounds great! (Score:5)

    by BMazurek ( 137285 ) on Monday October 02, 2000 @08:45AM (#738766)
    From the Rijndael FAQ:
    Can't you give it another name ? (Propose it as a tweak !)
    Dutch is a wonderful language. Currently we are debating about the names "Herfstvrucht", "Angstschreeuw" and "Koeieuier". Other suggestions are welcome of course. Derek Brown, Toronto, Ontario, Canada, proposes "bob".

    I second the call for "bob"! (although I would've supported "peter", too)

  • why twofish lost & rjindael won (Score:5)

    by konstant ( 63560 ) on Monday October 02, 2000 @08:49AM (#738767)
    I'm really gratified by these results. Recently I was implementing all the major AES candidates (in C++) in order to find one that might solve a problem I was running up against at work. Of them all, the only one I really could understand was Rjindael (pronounced "Rhine Dale" btw).

    For all the respect Schneier gets and deserves, Twofish is a horribly convoluted algorithm. They even had to publish a 200 page book explaining the damn thing, for gods sake, and even then the supposed experts who evaluated it for AES stated that they weren't confident they understood all its ins and outs.

    Basically Rjindael is secure for two good reasons. The first is that mere humans like me can understand it, and that sort of simplicity means more probing minds, more redundant testing, and higher confidence of security. Not to mention easier implementation. Secondly, if you increase the number of rounds in Rjindael you can effectively double the security, and even then it is still one of the fastest candidates in software.

    Twofish, RC6, Mars, etc were basically all ego-gratification projects intended to maintain corporate visibility in the cryptography market. There really is no better advertisement for your services than saying that you wrote AES. Rjindael on the other hand was an act of love - some hacker in Europe figured he knew crypto as well as all the suits. Looks like he proved it, too.


    -konstant
    Yes! We are all individuals! I'm not!

  • Re:let the cracking begin... (Score:4)

    by Vryl ( 31994 ) on Monday October 02, 2000 @08:56AM (#738769) Journal
    Ok, NO brute force attack will crack a 256 bit key.

    I resort once again to quoting Schneier, Applied Cryptography, Second Edition, pp157, 158: (slightly edited)

    "One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information.
    ... an ideal computer running at 3.2deg Kelvin [temperature of the cosmic background radiation of the universe] would consume 4.4*10^-16 ergs every time it set or cleared a bit.
    If we built a Dyson sphere around the sun and captured all of its energy for 32 years, without any loss, we could power a computer to count up to 2^192.
    These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than mattter and occupy something other than space."

    Of course, perhaps Quantum computing may change some or all of this, but I am not qualified to comment on that.

Slashdot Top Deals

Real Programmers don't eat quiche. They eat Twinkies and Szechwan food.

Close