Slashdot Mirror
Cryptogram: AES Broken?
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."
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?
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]
try { do() || do_not(); } catch (JediException err) { yoda(err); }
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...
Get your own free personal location tracker
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.
http://pcblues.com - Digits and Wood
Comment removed based on user account deletion
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.
Akvo.org - the open source for water and sanitation
we can not assume that either side of the crypto equation will remain dormant, using only today's technologies. The next Bruce Schneier will happen along (or maybe the man himself) and we'll be dealing with the golden age of quantum cryptography.
Uhm. emm. EZ? :)
Sure you can try that (good luck!), but when it takes all the computers in the world to run for a few hundred/thousand years to get the result, or when the number of cycles is more than the number of atoms in the universe, it's basically impossible to find the match.
Don't quote me on this.
...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 :-)
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
Live today, because you never know what tomorrow brings
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
--Got Lists? | Top 95 Star Wars Line
http://www.newsfactor.com/perl/story/13468.html
Quantum computing is a *good* thing.
Not even close, but isn't breaking encryption just a matter of throwing enough processor cycles at it until it finds a match?
This is correct. But if you can show that a massively parallel computer the size of the Earth would take billions of years to crack your code, then you can feel reasonably secure. Factorisation of large primes is a task that (probably) falls into this category -- it hasn't yet been shown to be easier.
If, on the other hand, you're talking about trying every message against the encrypted text, then that doesn't work either, because (a) it takes even longer than cracking the code, and (b) any message is potentially the plain text.
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.
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.
ATH0 Bitcoin: 1DnwFLXczVZV8kLJbMYoheUrpqHesjxrSi
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).
Height: 38U, Weight: 0 Newtons, Eyes: #0000FF, OS: Gray Matter 1.0 (Alpha)
Since when has any crypto been considered even remotely permanently unbreakable?
Since the one-time pad, that's when. This has been mathematically proven, as well, as early as 1910 or 1920, if I remember well.
OTOH, it is true that a one-time pad is symmetric (sp?) crypto. modern crypto, such as AES, DES, Serpent and others mentioned in Cryptogram are assymetric, and, as such, more susceptible to cracking methods.
The right to offend is far more important than the right not to be offended. (Rowan Atkinson)
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.
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.
Best Slashdot Co
Broken to a cryptographer means anything easier than brute-force. So in theory, this methed requires throwing less processor cycles at it than just totally random throwing, but it's still "just throwing processor cycles at it" in a sense. Broken to an engineer means something that is reasonable to do that cracks the code. That this is not (yet).
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?
"I'm a leaf on the wind. Watch how I soar."
-Hoban Washburn
modern crypto, such as AES, DES, Serpent and others mentioned in Cryptogram are assymetric
AES and DES are symmetric. Serpent probably is too, inasmuch as it was an AES finalist.
The SCO lawsuit makes me wish my company were in Utah. We need a new building.
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.
oh brave new world, that has such people in it!
Contrary to what appears to be a prevailing belief on slashdot that it's difficult to factor large primes, with current advances in parallel computation and quantum computing this is actually quite an easy task. I present to you the following 1024 bit prime:
6 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703
6 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703 * 1 = 11196101758632245023844192896470191898640653514665 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703
11196101758632245023844192896470191898640653514
Now we have to factor it. We step up to the main terminal of our quantum computer beowulf cluster and type in the question, "Of which numbers is this the product?". Qubits flip, waveforms collapse, a cat in a box somewhere dies (of radiation poisoning, strangely, or charmingly), and out pops the statement:
11196101758632245023844192896470191898640653514
DES is symmetric, and I'm pretty sure AES (Rijindael) and Serpent are, as well.
Beyond that, all crypto is considered breakable - the question is the amount of computational effort required. A "perfect" cypher will require each possible key to be checked and each with have an equal chance of being correct (and of being wrong). A "broken" cypher allows a considerable shortcut in the process of discovering what it has been used to encrypt. This shortcut may cut the time required in half, it might make it happen only 5% faster. The question to be asked is: is the person who wrote the paper stating an insecurity correct? How much of a risk is it?
According to CryptoGram, this attack is expected to take a large nominal amount of known plaintext, and hence might not be that risky after all. I personally like Blowfish better anyway :)
SIG: HUP
It's probably worth noting that IBM has already demonstrated a quantum computer running a factoring algorithm:
(See here)
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.
There are 4 boxes to use in the defense of liberty: soap, ballot, jury, ammo. Use in that order. Starting now.
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
Live today, because you never know what tomorrow brings
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?
"Sometimes a woman is a kind of religion, she can save your soul & set you free from all your sins" - Bad Examples
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.
AES, DES, Serpent are all symmetric, as were all of the entries to the NIST AES contest. I forget if it was a condition of the contest.
Since these are all symmetric, key distribution must either happen over another channel, or through a public key exchange method, all of which (AFAIK) use asymmetric algorithms. I don't know that I'd say that asymmetric algorithms are more susceptible, though. The biggest disadvantage to those algorithms is that they tend to require a lot more computing power, and one of the goals of the NIST AES contest was to provide an algorithm that would be implementable on really small platforms, such as embedded devices and smart cards. In fact, one of the best traits of Rijndael is that it seemed just as secure as the other entries while remaining very simple. It has been implemented on a few small 8-bit microcontrollers, and, when optimized, can take as little as 32 bytes of state (RAM).
The XSL attack is highly subjective.
c rypt
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.
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.
Sleep is just a poor substitute for caffeine, anyway. -Bob Lehmann
key distribution problem
If we get quantum computers and quantum cryptography, it will be the end of public key cryptography. We will need to exchange the initial keys face to face. The keys will not be used for encryption but rather integrity, which is a requirement for quantum cryptography to work. Obviously we will need to use unconditionally secure message-authentication-codes on our messages. Luckily the key needed for integrity does not grow linearly with the key size like keys needed for confidentiality.
This means that once we have exchanged the initial keys, we can just append new key material to our messages whenever we send quantum encrypted data. This will provide us with a key for integrity the next time we need to communicate.
To be very secure, I would not like to use a fixed key size for all future communication. I'd rather increase the key size by a few bits whenever a message is being exchanged. With a fixed key size, the chance of breaking the system will converge toward 100% as the number of attempts converges toward infinity. With a growing key size, the chance of every breaking the system will converge toward a small number, that is exponentially small as a function of the initial key size.
This still leaves the DoS problem. An attacker might just keep messing up the messages until we run out of key material for signing messages. I see no solution other than keeping a lot of key material ready for the future, and not keep trying too many times in a short period of time if we keep seeing false signatures.
Even though we have no public keys, we can still build up trust networks. If Alice has already exchanged keys with Bob and Charlie, Alice can do the key exchange for Bob and Charlie. Of course this will only work if Bob and Charlie trust Alice. But if Bob and Charlie has exchanged keys with different middlemen, they can once send messages signed with all their keys. Unless all middlemen are corrupt, Bob and Charlie will discover any invalid key.
Do you care about the security of your wireless mouse?
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
-I like my women like I like my tea: green-
Umm... you might be a little confused as to how AES was selected. AES selection criteria were public, as were discussions on the strengths (and weaknesses) of finalist algorithms. In addition, I know two of the AES conference program committee personally, and believe that had the NSA attempted any shinanigans, they would have been resisted and/or reported loudly.
These knee-jerk reactions to the NSA being evil really are counter-productive. Of course there are evil people in the US Government; there are evil people in every walk of life. I just don't think there are enough evil people in the NSA to conspire against the "good" people in the NSA.
You might be too young to remember, but back in the 70's there was a big commotion about the NSA modifying IBM's original S-Boxes. Many people at that time claimed very loudly that the NSA was inserting a back door into the algorithm. The NSA was pretty tight-lipped about why they made these changes; I think they still are, BTW. As it turns out, the original IBM S-Boxes were more succeptable to differential cryptanalysis than the ones the NSA reccomended for use with DES.
Remember that the NSA has a dual mandate. First, it is supposed to intercept, decode, and/or decrypt foreign elint intercepts. This is one of the reasons why they're one of the largest employers of foreign language specialists. Second, they are supposed to develop technologies to protect US national interests. The two missions sometimes conflict, but ever since Herb Lin at the National Academy of Sciences published his report on why it is in the US' national interest to allow widespread use of strong crypto for domestic applications, most (if not all) of the NSA types I've encountered have supported the development and use of strong crypto.
Of course, there are federal groups that like to sneak into people's homes and install keyboard sniffers. But, if that is going to be your law-enforcement surveilance technique of choice, why bother forcing bad crypto on the populous?
<grub> Reading
I'm a Ph.D student at Harvard. I've done cryptography research in the past. So listen up people.
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.
That's how you break the encryption on a document. People will generally choose the strength of the encryption (that is, how long it will take to break it by the best known method) so that, by the time you've done this, they don't care any more.
Breaking an encryption method is a different thing. This is done by analyzing the method in order to try to find a better method for breaking encrypted documents than the best method previously known. If this is sucessful, it means that all of the encryption that has been done with that method so far is weaker than had been thought. Of course, the initial method is just trying all possible keys, and it may actually be somewhat foolish to think that there is any cryptosystem which doesn't have a better method; that would mean that all of the key contributes to strength, rather than any of it being weak but necessary to get the algorithm to work. And, from the perspective of what you should use, even the strongest attack so far (if it even works) on AES is harder than brute force on triple DES.
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.
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.
Best Slashdot Co
Very interesting. Thanks for the link. Still a long way from implementation though.
I was in contact with the Twofish team during their candidacy concerning some work I had done on an improved instruction sequencing. One member of the team told me they figured rinjy was the most elegant proposal and that they would be very happy to see it prevail. Sure, they wanted to win. But more than that, they wanted the security industry to adopt a solid foundation.
There are times when Bruce has struck me as shrill or biased, but this isn't one of those times. What he's dealing with here is the very deep theme about whether the world's cryptographic fraternity is capable of sensing the right turn more often than not. If the wise men can't lead us to paradise, who can?
I'd say that's an issue worth talking about.
OTOH, it is true that a one-time pad is symmetric (sp?) crypto. modern crypto, such as AES, DES, Serpent and others mentioned in Cryptogram are assymetric, and, as such, more susceptible to cracking methods.
In theory it may appear that asymmetric ciphers are easier to break, because the attacker has more information -- the public key, which has a known mathematical relationship with the private key. However, the relationships between the keys are based on hard problems in math. In most cases, finding a way to determine the private key from the public key would constitute a major advance in mathematics, and one that has defeated mathematicians for centuries.
Symmetric algorithms, on the other hand, are not based on unsolved math problems, but rather on piling up carefully-chosen linear and non-linear operations until the result is too complicated to unravel. The papers referenced describe some new tools for modeling such complex structures, and claim that the new tools can unravel them far enough to produce a better-than brute force attack with very few known plaintext/ciphertext pairs.
To sum up: asymmetric crypto systems rely on the fact that we have no known method of solving the mathematical problems on which they are based. Symmetric crypto systems rely on the fact that we have no mathematical tools known to be capable of unraveling such complex sequences of simple operations.
In both cases, the ciphers can fall to new mathematics, and there's really no reason to think one is more likely to fall than the other.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
autopr0n is like, down and stuff.
No - Mix + Mash ciphers aren't automagically immune, see quote from Schneier:
"While quantum computation can make problems such as factoring and discrete logarithms (which public-key cryptography are based on) easy, they can only reduce the complexity of any arbitrary computation by a square root. So, for example, if a 128-bit key length was long enough pre quantum computation, then a 256-bit key will be long enough post quantum computation."
-- B.Schneier, 10th Oct 1998 posting to soc.history.what-if USENET group
E.g. 3DES will be pretty much toast, as will AES128.
"Mary had a crypto key, she kept it in escrow, and everything that Mary said, the Feds were sure to know."
The Army still uses one time pads that way.
Best Slashdot Co
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 and Anubis (Anubis uses an involutional S-box which might possibly make it weaker). In fact, my software project 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, named after the bridge Gandalf fights balrog at, which uses Anubis' S-box.
The secret to enjoying Slashdot is to realize that it should not be taken too seriously.
LOL
:)
I suppose some of you *cough*the moderators*cough* didn't get it?
Beware: In C++, your friends can see your privates!
In normal public/private hybrid systems, you use the public-key algorithm to encrypt a random secret session key, and then use the session key with a symmetric-key algorithm to encrypt the message. For some popular categories of factoring-based public-key algorithms, a hypothetical QC can instantly factor the key, and you can do the polynomial-time validation to show that the decryption key you've pulled out of the quanta matches the public encryption key. (OTPs don't let you do that.) You can then use the session key to crank the symmetric-key algorithm. The lead article that this discussion is about deals with weaknesses in the new symmetric-key algorithms that all of us were hoping we could use to replace Triple-DES, which appears to be very strong but is slow and clumsy (and neither 3DES nor AES appears to be attackable using QCs.)
Since widespread use of OTPs means a return to lots of couriers with briefcases attached to their arms, I suppose there are some non-mathematical ways to use QC to attack OTPs - hit the courier on the head with the QC, and then use the liquid helium from the qc to help shatter the handcuff chain, or offer the courier a Quantum Computer as bribe, or whatever :-)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
The way you crack these algorithms is to throw mathematicians at them until some of them stick. Once you've done that, if there's anything left to bother with, then you can figure out how many processor cycles you'd need to throw at the problem to break it, and decide whether that's feasible.
If your conclusion is that it's not feasible to break, then you need to decide whether to use rubber-hose cryptanalysis to get the key, or steal the target's computer where they saved the unencrypted version, or look for the yellow sticky notes next to their desk, or put a camera in their ceiling to watch them type in their keys.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Even if he only has some of your messages ... say for example he is missing a message where 8 bits are added to the key. He knows your 160-bit key but needs your 168-bit key. Guess what? He only has to break an 8-bit key, which can be done on the Atari 2600 in his basement.
You missed the point.
Adding bits does help. And breaking the system is not about just trying the possible combinations. You cannot decrypt the quantum encrypted data, your only chance of breaking the system is forging a message from one of the two parties during the communication. You cannot just try all possible keys, you have only one try. If you send an invalid message, it will be discovered.
And when talking about adding a few bits every time, I talk about a few bits larger key. All the bits in the new key are brand new random bits. So basically you will have to start all over again every time you try. And every time you try, your chance of breaking the system is smaller than last time you tried.
Do you care about the security of your wireless mouse?
Agreed, it's not impossible to use a OTP, and there are situations where it isn't much hassle. The case you describe is certainly realistic, however it is not very common and the benefit of OTP for this situation is unclear.
Generaly the most valuable data transferred is transmitted in circumstances where OTPs aren't practical. Sure it's easy to use for your buddy across town, but what about the corporate office halfway across the world that needs a product design worth 100's of millions of dollars of the open market. Or what about the corporate VPN which transfers 100's of megs a day?
And yes, OTP is possible even in these situations, but the practicalities are so difficult and costly that it's rarely, if ever used.
Let's face it, I've never had any personal information in my possession worth more than a house. Sure, some information is personal finances, and some of it might be embarrassing, but embarrassing me, or embezzling a few grand from my credit card account doesn't get anyone anything worth the effort of analyzing a decent (2^80 or longer) block cipher. Heck, I'd question if anything personal to me was worth breaking a 2^56 cipher like DES, and that doesn't take very long, but I'm not taking that chance in general.
Any block cipher can be brute-force broken given enough time and enough money. They question you have to ask is the information protected valuable enough to be worth spending the time and money on? Does someone really want to dedicate a several million dollar machine for several years to break a 2^64 strength-cipher you used? That information would still have to be worth a decent portion of the cost of the machine after a few years of crunching.
In reality the most practical uses of OTP's are the situations where the added security of a OTP is more-or-less moot. If I'm in close physical proximity with frequent meetings, and it's only to a friend, the value of the data is low, and the odds that I'm going to have anything to say that I can't say next time I see them is also low.
It's larger organizations like banks, companies, and governments that are exchanging large volumes of information that make the fattest, juiciest targets for analysis and they can't deploy OTP's for all of their needs, there's just too much data to do so.
Are your secrets worth more than theirs?
-Matt
O(n^1.5) seems slightly worse than linear to me.
First off, a point I agree with you on:
:)
>It boils down to - do you really need to have the
>data 100% secure. If you don't, then of course
>don't do it. But if you even think you might do,
>then surely it makes sense to have the ability to
>do it in place, so you can use it if you need to.
Agreed. If you really need it, nothing else will do. However, encryption is only one tiny piece of security, you'd better be sure the rest of your setup is up-to-snuff:
> I`m not sure why you think OTPs are so a) expensive and b) clumsy to use.
>The actual program to do the en/decryption can be written in VB in a few minutes - it's trivial
a) because it is clumsy and b) because it is expensive. This has been proven, Governments have and do use OTP's. There is a genuine reason why OTPs are rarely used in even government/military applications anymore.. it was too clumsy and too costly FOR THEM to use in realistic scenarios. Really, People aren't just discounting it without trying it.
I'll give you the application can be trivialy written in any language, heck, you can do it by hand easily enough. But the cost of actual use of OTP's is high when you realize how much surounding security is needed:
1) secure random number generation:
hardware: ~$700, consisiting of a dedicated PC w/CD burner a camera and a few lavalamps.
software cost: free
facilities: if you want this cipher to be more costly to break than analyzing a block cipher, you'd better be damn sure that breaking in here is a multi-million dollar adventure. If someone can pick a lock, break in and copy your pads, you're lost.
Dedicated room, Monitored alarm system, tamper-seals on system, high-grade locks, extra heavy walls.
~8,000 + alarm service fees.
2) OTP software: free
3) Trusted personal exchange of OTP CD's (again, you have to be sure nobody can copy these, so it must be hand escorted).
Travel expenses: ~$10 - $1000, depending on where your associate is and how far you have to go.
Salary for 2 days: (I'm thinking corporate, or your cost of missing work for a few days) $160 - $1600, depending on payrate of person traveling. (note: this only applies if the travel isn't across town and involves flying somewhere far)
This can probably be restricted to once annually
4) Burglary Rated safe ( TL-15 or better, preferably TLTR-30 or better) to store the pads in:
~$1000 (assuming TL-15) per site, per safe.
(note: the fire safes you can buy at target are NOT designed to resist burglary attempts).
Again, if someone can break in, grab and copy your pad, it's not secure. If you aren't worried about breakins, why are you worried about unbreakable encryption?
So once you start including physical security to obtain a minimal level of safety against having your pad stolen, yes.. it is damn clumsy and quite expensive.
-Matt