Cryptogram: AES Broken? - Slashdot
Close
binspam
dupe
notthebest
offtopic
slownewsday
stale
stupid
fresh
funny
insightful
interesting
maybe
offtopic
flamebait
troll
redundant
overrated
insightful
interesting
informative
funny
underrated
descriptive
typo
dupe
error
1405331
story
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."
You may like to read:
Big trouble In The World Of "Big Physics"
'USB-A Isn't Going Anywhere, So Stop Removing the Port'
New Book Argues Hybrid Schedules 'Don't Work', Return-to-Office Brings Motivation and Learning
'A Black Hole': America's New Graduates Discover a Dismal Job Market
Toxic Workplaces Are Worsening: 80% of U.S. Workers Say Their Job Hurts Mental Health
WSJ: Tech-Industry Workers Now 'Miserable', Fearing Layoffs, Working Longer Hours
Red Hat Explains Stance on KDE/Gnome Desktop Changes
This discussion has been archived.
No new comments can be posted.
Cryptogram: AES Broken?
More
Cryptogram: AES Broken?
Comments Filter:
All
Insightful
Informative
Interesting
Funny
The Fine Print:
The following comments are owned by whoever posted them. We are not responsible for them in any way.
Quantum computing for white hats
Score:
, Insightful)
by
kingpin2k
( 523489 )
writes:
on Monday September 16, 2002 @08:46AM (
#4264922
Wouldn't the same quantum computing that allows people to break today's crypto enable white hats to use increasingly complex algorithms and S-boxes to protect data? I mean, it's not as if crypto crackers are going to have these bad ass machines while the good guys sit around on 486's, right? Am I missing something?
Share
Re:Quantum computing for white hats
Score:
by
tanveer1979
( 530624 )
writes:
Not really missing.. but the point is that bad guys upgrade first step ahead of good guys. first we have the virus and then we have the anti-virus.. not the ohther way round.. The problem is that quantum computing will make the coverable space huge.. So "good guys" will not really know what they missed and finding something goodies missed will be randomly possible... now all the random theory shit i cant put here, but the biggest challenge in quantum crypto is mapping the coverage, a lot of loopholes can be left of everything is uncertain.... and our knowledge of quantum mechs is still infantile.
Yes, you're missing something.
Score:
by
Kjella
( 173770 )
writes:
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
Re:Quantum computing for white hats
Score:
, Informative)
by
smallfries
( 601545 )
writes:
No.
Slightly different quantum computation will do though, quantum crypto allows transmission of entirely secure messages, that is an unbreakable system. It isn't guarenteed by the hardness of a couple of mathematical challenges but by the actaul laws of physics themselves. Not only can a quantum crypto stream not be broken, but it can detect when somebody attempts to listen in. This has been demonstarted using both air and fibre as a transmission system (can't be arsed to google for a link but there should be plenty out there, it was textbook for our quantum computation course).
On the other hand, a quantum computer would break all the old cryptosystems quite easily (not sure about eliptic curves), however they are years away from being feasible and there are a lot of hard problems to solve first.
Re:Quantum computing for white hats
Score:
by
Fnkmaster
( 89084 )
writes:
Not necessarily. Quantum computing is a technique that is potentially very useful for operations that are highly parallelizable, and less so for operations that tend to be inherently sequential.
More complex algorithms for encryption do not necessarily mean more security. If factoring, for example, is only linearly hard in the number of digits of the large pseudoprime, then you could theoretically generate absolutely massive pseudoprimes, but at some point the method becomes useless.
The problem is that our notion of "hard" and "one-way" problems is all based on the concept of NP-completeness. This concept is broken by quantum computation. We would need to find new problems that are QC-complete, in other words, problems that are hard (exponential time and # qubits) even with quantum computation, and base new encryption methods around such problems.
I'm not up to date on the literature of computational complexity, but I'm fairly sure such problems should be possible to find, a class of harder problems than NP-complete problems. But since functional QC is so far off, this is not really a practical issue yet, but I'm sure it's of theoretical interest to many.
Re:Quantum computing for white hats
Score:
by
ghjm
( 8918 )
writes:
It's easy to get confused here. There is a quantum computer algorithm for factoring, because factoring happens to map well to quantum concepts. But factoring is not NP-complete - in fact, it is in P. If you could reduce an NP-complete problem to a factoring operation, you would have proven that P=NP.
The theories that posit QC as the solution to P=NP tend to involve poorly-defined "oracle machines" based on QC hand-waving, rather than any actual well-defined algorithms. It is very much an open question whether QC has anything interesting to say about P=NP.
-Graham
Re:Quantum computing for white hats
Score:
by
Fnkmaster
( 89084 )
writes:
Sorry I was mistaken - you are right that factoring is not
proven
to be NP hard or NP complete (dredging up CS knowledge from 4 or 5 years back here).
However, you are not 100% correct either. Most practical experience does not suggest a polynomial time solution exists (with the exception of Shor's Algorithm and the quantum factoring algorithm - this does mean the problem is in BQP, the new class of bounded-error, quantum polynomial time). If you look up the modern definitions of P, it seems to refer only to deterministic sequential machines, and I don't think that includes quantum computers strictly speaking.
I guess this is a quibble, but a worthwhile one, since the whole point is that there is a class of problems that _seems_ to be made easier (i.e. polynomial) by quantum computing, though it's not clear that those same problems don't have non-quantum polynomial solutions, it certainly appears that way based on everything we know.
You seem to be correct though that there is no proof of anything about P=NP from QC (I just looked it up and I'll be damned if I could make any sense of the articles I found without some serious study).
Re:Quantum computing for white hats
Score:
by
Zeinfeld
( 263942 )
writes:
Unfortunately this thread does not appear to be talking about the AES issue at all, but garbled understanding of what quantum crypto can do.
According to the cryptographer's panel at RSA quantum computing is much less of a threat than many assume. In the first place quantum computing tends not to be effective against symetric algorithms. Secondly RSA turns out to be based on a problem that is very very hard with conventional computing and very very easy with quantum computing. It is not clear that all possible public key algorithms are susceptable to attack using quantum techniques.
In other words don't get the idea that quantum computing immediately means the end of cryptography.
On the actual topic of AES I would not call this a 'break', in fact nothing less than breaking the cipher for real should count as a break. There are plenty of 'breaks' of DES but none of them are easier than brute force when applied in practice. What we have is a theoretical compromise that is way outside the capabilities of any current technology.
Or consider it this way, given the known problems with 3DES (limited block size, severe limitation on safe amount of ciphertext generation) I don't feel like sticking with 3DES as a result of the article.
Re:Quantum computing for white hats
Score:
by
billstewart
( 78916 )
writes:
Quantum computing means that you can either tell what color somebody's hat is or how many hats they'r ewearing, but not both simultaneously
:-)
Quantum computing appears to allow the user to cheat, by picking the correct n-bit value out of 2**n bits, for a class of problems that mostly look like the factoring problems that make RSA public key crypto work.
This doesn't appear to make things faster for the white hats, because the white hats already knew what the correct bits were for data that was intended for them or data that they were trying to sign.
We need to start exploring the theory of QC, to find algorithms that don't get exponentially faster with QC.
We also need to start remembering and improving the symmetric-key-based Key Distribution Center (KDC) models like
Kerberos
[mit.edu] that don't depend on public-key crypto. We abandoned most of these, because public-key is much more convenient and doesn't have big obvious centralized security targets that can be attacked, but they still do an amazing number of jobs just fine.
Today's problem is attacks on the Rijndael and Serpent AES winner/candidate symmetric-key algorithms, which has been proposed as a replacement for 3DES, the current highly-trusted-but-slow symmetric-key algorithm. We need to watch the crypto math folks apply their new techniques to the other AES candidates, so we can tell if any of them are still usable or if we have to get the NSA to run another contest. These aren't particularly affected by Quantum Cryptography.
quantum computers
Score:
, Funny)
by
ch-chuck
( 9622 )
writes:
And all bets are definitely off when quantum computers arrive on the scene.
couldn't these be described as "weapons of mass decryption"? [visions of 'sneakers' all over again]
Quantum
Score:
, Interesting)
by
caluml
( 551744 )
writes:
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...
;)
Golden Age of Privacy
Score:
by
marko123
( 131635 )
writes:
It will continue to exist so long as the average hacker has a computer within 2 or 3 orders of magnitude of power of the government. Easy.
Comment removed
Score:
, Interesting)
by
account_deleted
( 4530225 )
writes:
on Monday September 16, 2002 @08:49AM (
#4264937
Comment removed based on user account deletion
Share
Re:Quantum computing =/= no privacy
Score:
, Informative)
by
stevelinton
( 4044 )
writes:
sal@dcs.st-and.ac.uk
on Monday September 16, 2002 @09:04AM (
#4265016
Homepage
Quantum Computing and Quantum Cryptography are unrelated technologoies. Quantum crypto is indeed "unbreakable", but requires a single physical channel connecting source and destination. It will not carry over routers and absolutely cannot be used for normal internet email for instance.
Quantum computing would break a range of encryption techniques, especially most public-key techniques, but nothing known today rules out new and more robust digital encryption technologies being developed that Quantum Computers could not break, and I imagine plenty of people are working on them.
Parent
Share
Addendum
Score:
, Informative)
by
seizer
( 16950 )
writes:
on Monday September 16, 2002 @09:34AM (
#4265186
Homepage
It's probably worth noting that IBM has already demonstrated a quantum computer running a factoring algorithm:
(See here)
[ibm.com]
Parent
Share
Re:Quantum computing =/= no privacy
Score:
, Insightful)
by
afidel
( 530433 )
writes:
In fact elyptic curves appear to be immune to quantum techniques that have so far been postulated. This does not mean that a fast method will not be found to break EC's simply that there is not yet any knowledge of a technique that significantly weakens EC's.
Re:Quantum computing =/= no privacy
Score:
, Insightful)
by
aminorex
( 141494 )
writes:
on Monday September 16, 2002 @11:18AM (
#4265958
Homepage
Journal
It will always be the case that crypto which depends
on computational intractability rather than a
demonstrable computational impossibility will always
be open to some future innovation rendering it
trivial to crack. Elliptic curve crypto seems to
have the best prospects for the future right now,
and you can use it right now: El Gamal is
implemented in GPG.
But to say that QC will render effective crypto a
historical artifact is clearly mistaken. If it
were true, it would imply that there are *no*
hard problems any more, once QC techniques are
employed. All that QC can do is compute functions
over a finite field with effectively infinite
parallelism. It's unfortunate that most crypto
systems today rely upon functions over a finite
field, but there are plenty of hard problems that
are only valid over function spaces, for example.
Parent
Share
Re:Quantum computing =/= no privacy
Score:
by
stevelinton
( 4044 )
writes:
Very interesting. Thanks for the link. Still a long way from implementation though.
Re:Quantum computing =/= no privacy
Score:
, Funny)
by
smyle
( 108107 )
writes:
when quantum computers arrive
I have a Quantum hard drive, but I didn't know they were getting in the PC business.
Hmmm... now that I think about it, I thought they got bought out by Maxtor. I think you're just bluffing about "Quantum computers" and this power they will supposedly have.
Re:Quantum computing =/= no privacy
Score:
by
ssimpson
( 133662 )
writes:
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.
The end of privacy
Score:
, Insightful)
by
bjelkeman
( 107902 )
writes:
on Monday September 16, 2002 @08:49AM (
#4264939
Homepage
Journal
on the golden age of privacy
That is quite a funny statement. 99% of all email is being sent in clear text, often passing through gateways which have permanent wiretaps installed. Phone tapping is at an all time high in the west and there are cameras on nearly every street corner around where I live.
Privacy.... I had a lot more privacy 20 years ago, that is for certain.
Share
Re:The end of privacy
Score:
, Insightful)
by
Winterblink
( 575267 )
writes:
Hah, too true.
:) The "golden age of privacy" would be known more as the "golden age of privacy that nobody bothered to take advantage of when they could".
Re:The end of privacy
Score:
, Interesting)
by
Methusalem
( 572742 )
writes:
Privacy.... I had a lot more privacy 20 years ago, that is for certain.
I doubt that. 20 years ago, your neighbour, your baker and your butcher knew more about you than any mass e-mail marketing company does nowadays. The only difference is that they didn't send you spam, but for sure your butcher knew that you didn't know the difference between a normal and an excellent steak, and sold you the first one for the price of the second one. So you were f*cked even then, only you didn't know it.
In order to provide some on-topic content also: I thought the basis of all (public-key) encryption was based on one "hard to solve" problem only, namely the "factoring in prime numbers" problem -- are there any problems that I missed?
Re:The end of privacy
Score:
by
moebius_4d
( 26199 )
writes:
el gamal is based on discrete logs on a finite field
Re:The end of privacy
Score:
by
God! Awful
( 181117 )
writes:
I doubt that. 20 years ago, your neighbour, your baker and your butcher knew more about you than any mass e-mail marketing company does nowadays.
Uhh... sorry to be literal, but 20 years ago I didn't know my butcher personally and I still don't. I buy mostly buy meat at the supermarket. I think it was more like 60 years ago that everyone bought meat from the local butcher.
On the other hand, my credit card issuer knows far more about me than any e-mail marketer. They know that I play golf once a week, how much I spend in the grocery store, when and where I go on vacation, etc. All the average e-mail marketer (thinks they) know about me is that I like rape pr0n.
-a
Re:The end of privacy
Score:
by
ssimpson
( 133662 )
writes:
are there any problems that I missed?
RSA is based upon the Integer Factorization Problem (IFP) (*).
Elgamal / DH are based upon the Discrete Log Problem (*)
Eliptic Curves Cryptography is based upon, erm, Eliptic Curves.
(*) Note: there are no proofs that RSA or DH/Elgamal are actually as hard as the underlying IFP or DLP - e.g. they could be broken even if factoring is "hard".
quantum crypto
Score:
by
TechnoVooDooDaddy
( 470187 )
writes:
When quantum computers come out, we'll develop problems that are believed to be hard on quantum computers...
we can not assume that either side of the crypto equation will remain dormant, using only today's technologies. The next
Bruce Schneier
[amazon.com] will happen along (or maybe the man himself) and we'll be dealing with the golden age of quantum cryptography.
gross oversimplification
Score:
, Funny)
by
jukal
( 523582 )
writes:
on Monday September 16, 2002 @08:51AM (
#4264951
Journal
Basically, the attack works by trying to express the entire algorithm as multivariate quadratic polynomials, and then using an innovative technique to treat the terms of those polynomials as individual variables. This gives you a system of linear equations in a quadratically large number of variables, which you have to solve. There are a bunch of minimization techniques, and several other clever tricks you can use to make the solution easier. (This is a gross oversimplification of the paper; read it for more detail.)
Uhm. emm. EZ?
:)
Share
Re:gross oversimplification
Score:
by
Lord Ender
( 156273 )
writes:
What's the problem? You should have seen all of that stuff, at least on a basic level, in high school if you went to school in the USA. This is assuming you took the college prep route of courses.
Re:gross oversimplification
Score:
by
jukal
( 523582 )
writes:
>What's the problem?
The fact that my and your sense of humour did not intersect.
:) To me, it seemed that the clip was like straight from
Dilbert mission statement generator
[dilbert.com]. Anyway, the description is very good, but to one like me, who does not use math terms actively, it takes some time to understand what it means in practise and how to use the information. And at first sight it seems like the recipe for Energy Bolt spell. But then again, I am mathematic moron
:)
Nice article...
Score:
, Funny)
by
26199
( 577806 )
writes:
...I love the first line:
AES may have been broken. Serpent, too. Or maybe not. In either case, there's no need to panic. Yet. But there might be soon. Maybe.
Lovely summary, guys
:-)
Quantum Computing and Privacy
Score:
, Insightful)
by
hillct
( 230132 )
writes:
on Monday September 16, 2002 @09:01AM (
#4264998
Homepage
Journal
Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware. International politics would be forever changed. The basis for personal freedom (now based on privacy) would have to shift to something as alien as mutual trust and maybe even respect.
The focus of international intelligence gathering would shift radically back to human intelligence (which is already happening for other reasons) and the new basis for security would become that of access cintrol through discontinuity - if you network is not connected to your neighbor's, then he can't get access to it regardless of his technical sophistocation.
The days of the NSA Sneaker-Net would return (picture NSA computer geeks running from one terminal to another with DLTs in order to keep the systems in communication, such that data could only flow in one direction.
Disclaimer: IANAF - I Am Not A Futurist
--CTH
Share
Re:Quantum Computing and Privacy
Score:
, Insightful)
by
sql*kitten
( 1359 )
writes:
on Monday September 16, 2002 @09:08AM (
#4265046
Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware
How would this technology work against one-time pads? Besides, historically technologies have always tended to balance. Someone makes a better tank, then someone makes a better tank-killer, then the cycle repeats. If today's sophisticated encryption can in the future be defeated with cheap devices, then the crypto that this future society considers sophisticated would be well beyond ours. Consider the relative computational power of Bletchly Park and the sophistication of Engima of the early 40s and the power and sophistication of a 21st Century desktop PC.
International politics would be forever changed.
Not really. It would simply switch from broadcast and ciphers to the diplomatic bag and codes - which is how it worked for centuries. Complexity in international affairs is nothing new.
Parent
Share
Re:Quantum Computing and Privacy
Score:
by
Beautyon
( 214567 )
writes:
Not really. It would simply switch from broadcast and ciphers to the diplomatic bag and codes
Where of course,
Numbers Stations
[ibmpcug.co.uk] come in.
For all the advances in asymetric cryptography, Numbers Stations / OTP has remained the system of choice for many organizations. This says something about asymetric cryptography; either that it isnt trusted, that its impractical for espionage, or something else...
Re:Quantum Computing and Privacy
Score:
by
swillden
( 191260 )
writes:
Someone makes a better tank, then someone makes a better tank-killer, then the cycle repeats.
Very true, but it bears pointing out that the direction of the advantage seems to be different.
In the battle between warhead and armor, the warhead tends to retain the lead most all of the time, because it's basically easier to blow holes in something than to withstand massive force.
In the battle between cipher and cryptanalyst, the ciphers have tended to retain the lead, which seems to imply that creating an algorithm that munges data in complex ways is basically easier than unraveling said munging. This is *not* to say that good cipher design is easy or that anyone can do it; it's fiendishly difficult, because the attackers are fiendishly clever. Still, over the last 50 years or so, history shows us that the ciphers have tended to stay ahead of the cryptanalysts. DES is a shining example, given that it has been the #1 target for 30 years and has stood essentially undamaged.
Re:Quantum Computing and Privacy
Score:
by
plover
( 150551 )
writes:
I'm picking a few nits here, but there are several chinks in DES's armor.
It has been known for some time that there are many weak keys in DES.
In 1990, Biham and Shamir published a differential cryptanalysis attack on reduced round variants of DES.
In 1993 Matthew Wiener published an initial design for a DES-breaking machine. At the time, it would have cost $2M.
In 1998 Biryukov and Kushilevitz published a ciphertext-only attack on reduced round DES reducing the workload by 2^20.
Near this time, I recall seeing a paper claiming to reduce DES to a 2^48 problem, but I'm unable to find a citation tonight.
In 1998, Wiener's machine was built by the Paul Kocher and EFF for about $250,000, and it breaks DES keys in about three days, on average.
So yes, I agree that DES is the granddaddy of Feistel network ciphers. Few of the cryptanalytic attacks work without ungodly amounts of chosen plaintext or artificially reduced round counts. But code breaks have generally occurred within months or years of implementation, not decades. As Gwido Langer, the chief of Poland's Biuro Szyfrow, said about breaking the German Enigma (when the British were unable to) "You don't have the same motivation as we do." Until after World War II, most code systems were broken during the same wars they were supposed to be protecting, and for that same reason.
The wartime and/or government codebreakers also have one more advantage: they don't typically announce their breaks to their enemies du jour. The recently released Venona papers show how Soviet spies who were given (faulty) one-time pads in 1942-1946 had them broken between 1948 and 1980.
Yes, it's a constant struggle. Yes, DES looks pretty good. But I wouldn't want to trust ALL of the national eggs to any single one of the currently commercially-available baskets.
Re:Quantum Computing and Privacy
Score:
by
swillden
( 191260 )
writes:
It has been known for some time that there are many weak keys in DES.
Depending on your definition of "many", this is true. The complementation property of DES is a small weakness as well. These issues reduce the strength of DES by a miniscule amount.
Near this time, I recall seeing a paper claiming to reduce DES to a 2^48 problem, but I'm unable to find a citation tonight.
You're probably thinking of Matsui's Linear Cryptanalysis.
In 1998, Wiener's machine was built by the Paul Kocher and EFF for about $250,000, and it breaks DES keys in about three days, on average.
The DES key size was always too small, but that was what the NSA wanted. Remember that the original cipher (Lucifer) had a 128-bit key. 3DES addresses this problem handily, if not elegantly.
Also, if you'll permit me to pick nits, Deep Crack recovers a key in about 5 days, on average.
Overall, though, all of the concerted effort focused on DES has reduced its effective key size very little. That effective key size was too small to begin with, but 3DES has an effective key size that is adequate for a few years yet, particularly since linear and differential attacks cannot be used to speed up the "meet-in-the-middle" attack.
This is a pretty impressive record, in my opinion.
Re:Quantum Computing and Privacy
Score:
by
swillden
( 191260 )
writes:
Yes, that is the tradition. But the mind and effect of man is finite. Eventually we will end up with "The Answer" -- and no further cycle.
Only if there is a "The Answer". It's certainly not clear that there will be such an answer in the case of either the warhead/armor evolution or the cryptographer/cryptanalyst evolution, mainly because what often happens to allow one side to take the lead over the other is a changing of the rules.
To use some examples from the armor/warhead debate, consider that the debate started as armor vs. blade, progressed to armor vs. projectile, then to armor vs. explosive warhead, then to armor vs. shaped charge, then to armor vs. ultradense projectile backed by shaped charge. Further consider that armor changed radically a few times along the way as well, changing materials, thickness and composition (especially lately, with highly-engineered composites). Not only that but armor has even acquired the ability to actively "fight back" -- reactive armor. In tanks it takes the form of explosives attached to the tank's armor plate that explode to slow penetrators and distort shaped charges. In naval warfare, you can even view anti-missile defensive systems as part of the "armor". A set of Aegis-equipped ships with high-speed data links and layered missile defensive systems creates a sort of a "virtual" armor that encloses all of the ships. Now consider how far removed that is from a bronze sword hitting a boiled leather cuirass, and tell me that man's imagination is limited.
Things like quantum computing are based on the fundimental physics of the universe. While I can't say if they are, or are not, the end-game cycle -- they're surely isn't much left to work with.
Which does not mean that quantum computers will be able to solved all problems. In fact, there are already plenty of problems known that quantum computers will not be able to solve, and there is only a tiny set of problems for which it's clear that quantum computers will be any help at all.
Plus, QM does not give us a "fundamental" understanding of the universe; it has numerous well-known flaws (mainly in terms of what it does not explain), and who knows what else we may be able to do given a deeper understanding of How Things Work.
AC is Troll or Clueless on OTP vs QC
Score:
by
billstewart
( 78916 )
writes:
As the other posters have pointed out, quantum computing doesn't affect One-Time Pad security. The glaring weakness in AC's argument is that the computation to determine whether a guess is correct is NOT polynomial-time - there's no way to tell if a "1" in the cyphertext is a message bit of 0 and a pad bit of 1 or the other way around.
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
:-)
Re:Quantum Computing and Privacy
Score:
by
thogard
( 43403 )
writes:
There was no privacy in most small towns all over the world. Until people started moving around, there was a local neighbor who knew what was going on. Ever try to hide something in a small school? The local gossip made sure you didn't. Most of our privacy today is an illusion based on non-existent anonymity.
Do not fear the Quantum Age
Score:
by
psicE
( 126646 )
writes:
Quantum computing is a *good* thing.
Strictly Speaking
Score:
, Insightful)
by
Beautyon
( 214567 )
writes:
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.
Re:Strictly Speaking
Score:
by
sql*kitten
( 1359 )
writes:
OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.
Only if your pad is truly random. There's a scene in Cryptonomicon in which they realize the vicar's wife is looking at the letters as she draws them out of the tombola used to randomize; being a native English speaker she is subconsciously biased to prefer certain letters over others, and this is enough to open a chink in the armor.
Re:Strictly Speaking
Score:
by
Beautyon
( 214567 )
writes:
When I use the term "OPT", it is implicit that I mean "when OTPt is deployed correctly".
It would be a little crazy to say "OTP, when it is deployed improperly, cannot be broken", now wouldnt it?
Re:Strictly Speaking
Score:
by
gclef
( 96311 )
writes:
While this is true, there's a reason that no one uses one-time-pads : they're a pain in the ass. In terms of practical usefulness, really only governments are willing to go to the trouble.
The big problem is that once you've encrypted something with an OTP, the security (and secrecy) of the OTP is *everything*. If anyone gets the OTP, your encryption is done for.
So, managing the OTPs becomes the biggest challenge in using them. First, you have to have an OTP about the same size as the file you're encrypting, to ensure that no statistical games can be played to re-build the key, and you have to have a seperate OTP for every message you encrypt. Also, getting an OTP to someone else you want to encrypt a message to is not an easy matter. You have to be sure that no one else can see the transaction that shares the OTP, since that would immediately destroy the security of the system.
Compare this to any symmetric-key system: Yeah, you've also got a key that's central to the cipher. But, the key does not need to be approximately the same size as the file encrypted (as is the case with OTPs), which, for big files, is a huge deal.
Basically, there's a reason we like symmetric-key algorithms, and it's mostly to do with usability. If an encryption system is such a pain in the ass that no one uses it, then its impact in the real world will be zero.
Re:Strictly Speaking
Score:
by
Beautyon
( 214567 )
writes:
Basically, there's a reason we like symmetric-key algorithms, and it's mostly to do with usability. If an encryption system is such a pain in the ass that no one uses it, then its impact in the real world will be zero.
I totally agree with you about OTP being a pain in the ass to manage, but as far as its impact in the real world, you could not be more wrong.
Numbers Stations
[ibmpcug.co.uk] have relied on OTP for decades, and continue to do so till today.
Like anything, it depends how much you want a to protect your communications. If OTP is going to save your life, as in espionage, it becomes much less of a pain in the ass. If you want to encrypt your daily email with the 20 people in your Mozilla address book, then things get very messy very quickly, and of course, you can forget stuff like ecommerce, which instantly become "unwieldly" to put it mildly.
Re:Strictly Speaking
Score:
, Informative)
by
Delta
( 16579 )
writes:
OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.
OTP is not unbreakable.
While the algorithm itself isn't breakable, the strenght of a OTP based solution will still depend on several weak points, like the random number source.
There's plenty of room for trying to attack it, using statistical analysis and estimates to try to be able to break it.
Re:Strictly Speaking
Score:
by
Beautyon
( 214567 )
writes:
OTP is not unbreakable.
OTP *is* unbreakable.
[std.com]
This is a well established fact. Like I said elewhere in this thread, its clear that I mean "when it is implimented correctly", as it would make absolutely no sense to imply "OTP is unbreakable when it is implimented poorly".
Well... yeah!
Score:
by
rocjoe71
( 545053 )
writes:
...maybe we need to assume that any given type of crypto is only temporary.
Well that's a serious problem if you ever, ever thought cryptography had any sort of permanence!
For one thing, an encrypted message is of no use to the receiver if they can't DE-crypt it, *poof* crypto is not permanent.
I'd recommend reading "The Code Book" by Simon Singh as the first two-thirds of the book are a history lesson that demonstates to me how cryptography endagers the lives/way of life of those who rely on it to protect themselves (in particular, Mary Queen of Scots and Enigma).
Old data is the problem
Score:
, Insightful)
by
BESTouff
( 531293 )
writes:
on Monday September 16, 2002 @09:11AM (
#4265061
The problem is that old encrypted data doesn't "evolve" with the computing/crypto capacity.
Imagine some black hat just archived all encrypted data he could get (bank transactions, private conversations, you name it) then decrypts them in 10 years when he can buy his brand new quantum computer. All this old data may prove very valuable for him.
Perhaps very sensitive data shouldn't even transit on the net because you can't tell if it'll be decryptable in the future.
Share
So use one-time pads
Score:
, Insightful)
by
wiredog
( 43288 )
writes:
They're easy to generate. All you need is a good source of randomness. A small analog input card connected to a thermocouple wire with a bad (therefore noisy) connection makes a wonderful source of randomness. Use the low four bits of a 12 bit card. Two reads gives one random byte. String random bytes together to generate however many you need.
Once you have the list of numbers, get the list of words and phrases to encode. Put one random number next to each word or phrase (watch for duplicate codes here!)
Put the pad on a cd, send it to whoever you want to communicate with. Doing this last part is the only large potential insecurity, plus it's inefficient. But the one time pad is theoretically unbreakable.
Re:So use one-time pads
Score:
, Informative)
by
lars_stefan_axelsson
( 236283 )
writes:
But the one time pad is theoretically unbreakable.
Here it's fitting to note the words of Steve Bellowin:
"As a practical person, I've observed that one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong."
In operation, there are many 'gotchas' to watch out for,
never
reuse a pad for example.
Google for 'Venona' and 'one time pad' for a good example of even the experts (KGB et al) getting one time pads wrong.
That's the wrong way to use them.
Score:
, Informative)
by
dark-nl
( 568618 )
writes:
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.
'the' or 'you'
Score:
by
wiredog
( 43288 )
writes:
Don't encode 'the' or 'you'. Encode them as parts of phrases, or leave them out where possible.
I used one time pads in the army. You wouldn't use one to transmit War and Peace. But you would use it to send "Attack is Tomorrow, sell IBM". Or to send "Name of agent in NSA is CowboyNeal."
Those would be encoded as the phrases "attack is tomorrow", "sell IBM", "name of agent","in NSA". The word "is" could be encoded, or dropped (the sentence would be parseable without it.) Only "CowboyNeal" might have to be encoded letter by letter. Or it could be encoded as "cowboy"+"n"+"e"+"a"+"l".
Generally, using a one time pad to encode letter by letter is a bad idea. Done only when there is no alternative.
Re:'the' or 'you'
Score:
, Insightful)
by
Peter T Ermit
( 577444 )
writes:
Sorry -- dark nl is correct, and you're wrong. Here's an example of how to use a one-time pad:
Your pad = random string of bits, like 0111 0101 0001
Your message = string of bits, say, 1010 1010 1010
Encrypted message = pad XOR message = 1101 1111 1011
Decrypted message = pad XOR encrypted message = 1010 1010 1010.
It has nothing to do with substituting for words or letters.
The drawback to one-time pads is that each side needs to have the same pad, which must be at least as long as the message to be encrypted. The pad has to be shared and stored in a secure fashion, which makes it impractical in most cases.
Re:'the' or 'you'
Score:
by
gclef
( 96311 )
writes:
I think you're arguing two different points. You're worrying about how the pad actually works, and he's worried about maximizing the use you get out of the pad (by dropping unnecessary words out of the message to be encrypted). These two worries are clearly related, but not identical.
I would say that he is correct: in practice, you would want to drop unnecessary or redundant info out of the message. Since OTPs rely so heavily on securely sharing the pad, you want to maximize the use you can get out of the pad you have without re-use. This means dropping redundant words. In common computer practice, we'd just zip the damn thing before sending it, hopefully greatly increasing the entropy (and decreasing the length) of the message before even bothering to encrypt it, but that's a whole other topic for discussion.
Re:'the' or 'you'
Score:
by
Peter T Ermit
( 577444 )
writes:
Actually, the entropy of the message doesn't matter with a one-time pad, so long as your pad is truly random, but you're right that compressing the message gives you more use out of that pad.
Re:'the' or 'you'
Score:
by
Peter T Ermit
( 577444 )
writes:
Codebooks aren't actually unbreakable, as you point out in your second paragraph. There's still redundancy (if nothing else, through syntax) that can give you a better-than-brute-force attack, even if it's impractical to crack the message.
And as for XOR; you're right. However, it's almost always used because you need a reversible bitwise function. I can only think of four, two of which are trivial, leaving only XOR and (not XOR) as your possibilities. If you do operations on chunks larger than bits, you have more options, though.
Different implementations
Score:
by
wiredog
( 43288 )
writes:
I'm talking about the classic implementation. You have two columns. Left column is the lits of words/phrases, right column is the list of codes used for those words/phrases. It can be done by hand (as I did it in the Army), or automated.
The Army still uses one time pads that way.
Re:Different implementations
Score:
by
Peter T Ermit
( 577444 )
writes:
As Rich0 pointed out, this isn't a "one-time pad" as understood by cryptographers, even though you may have been using your code a single time. This is a codebook, and it is not 100% secure. One-time pads, on the other hand, are the only provably 100% secure cryptosystem.
Re:Different implementations
Score:
by
Peter T Ermit
( 577444 )
writes:
They're worth a read.
Thank you for your condescension. I've read plenty of crypto books.
The one-time pad protocol is 100%, provably secure. Period. The only weaknesses don't have to do with the protocol itself. Flawed implementations (insecure pad; non-random generator of pad, etc.) will ruin any cryptosystem. And if you're objecting to my use of the term "cryptosystem" instead of "protocol" in the previous comment, you obviously know what I meant, so why the fuss?
Re:So use one-time pads
Score:
by
afidel
( 530433 )
writes:
A much more common source of randomness that was published in Phrack Volume 8 Issue 54 is to use a cleaned white noise signal from a soundcard. See
This link
[phrack.com] for more details.
Re:So use one-time pads
Score:
by
autocracy
( 192714 )
writes:
Not 1-26, and not 1-10... 1 or 0. Bit level XOR is the "proper" way to do it.
Re:So use one-time pads
Score:
by
Luyseyal
( 3154 )
writes:
Postal Workers of the world rejoice!
:)
-l
MAYBE?
Score:
, Insightful)
by
Winterblink
( 575267 )
writes:
maybe we need to assume that any given type of crypto is only temporary
If I'm not mistaken, this is rule #1 of cryptography. Doesn't really matter what algorithm you use or how secure everyone or anyone thinks it is, they're always able to be cracked. Which cryptosystem you use is more a measure of reasonable security -- do you want your messages secured for years, decades, etc., with an assumed increase of computing power?
What Schneier really meant to say...
Score:
, Interesting)
by
BigBadBri
( 595126 )
writes:
on Monday September 16, 2002 @09:27AM (
#4265141
Serpent and Rijndael are vulnerable to this attack - it seems Twofish isn't - damn government should have chosen Twofish for AES instead...
Seriously, though - any approach that manages to reduce the difficulty of cracking these algorithms by a factor of 2^100 is impressive, and Schneier at least simplifies it enough that us folks with very rusty number theory can appreciate the achievement.
His comment later in Cryptogram about his name appearing on a list of banned words is much, much scarier - looks like he's upset someone in the content censorship Gestapo. That same content filter would deny access to today's Slashdot front page - nasty.
Share
Re:What Schneier really meant to say...
Score:
by
BitterOak
( 537666 )
writes:
Also note:It seems that the XSL might break AES 256 bits, but it is not certain. There is little chance however that it will break the most used AES 128 bits.. Funny, i would have gone with bigger keys, but they seem to get less secure.
Recall that "breaking" an algorithm means finding a method of attack with a work factor less than 2^k where k is the key length in bits. "Breaking" in this context doesn't mean recovering plaintext of encrypted communications. Since they have demonstrated an attack with a work factor of 2^200, that means that 256-bit AES was "broken" but 128-bit AES was not.
One Time Pad != Encryption
Score:
, Insightful)
by
Kjella
( 173770 )
writes:
on Monday September 16, 2002 @09:39AM (
#4265220
Homepage
Basicly, it's just a delay mechanism that will let you transfer messages securely at a later time assuming you've transmitted equally much information securely already. So the question is, why don't you use the secure medium in the first place? Ok granted, you can send an agent out on a mission with an OTP and he can communicate securely with home base, but I mean for everyday use?
The typical idea about cryptography is to use a secure medium to provide the key, while using the insecure medium to send the data, because the insecure medium is much faster/better/easier to use. So I can meet you in person and get the key, or call you on the phone and verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well), and then use the Internet as a medium from then on.
The OTP "solution" would be to say a random sequence of 1s and 0s, then use those to decrypt the irc converation later, not really an option. You'd "run out" of pad rather quickly. Oh, and quantum computing does as far as I know not affect encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).
Kjella
Kjella
Share
Re:One Time Pad != Encryption
Score:
by
Sycraft-fu
( 314770 )
writes:
One Time Pads are still practial for situations where absolute privacy is a must. The intelligence community still uses them and I could even see a bussiness use them if it was necessary. IT's not quite as difficult as you might think:
You get a source of random data, there are plenty available and prepare a harddrive or harddrives that contain that data. Being that harddrive capacities are now in the 200GB range, you can get quite a lot of data. You then duplicate the drives once and only once. A secure, trusted courier then takes the drives to the other location where they are installed. You now have a good OTP system setup. Your encrypting/decrypting stations just need to be physically secure and keep track of what part of the pad has been used. When it's all used up, you destroy the drives.
Now I can't think of anything that needs this level of security today, but it's not so impratical that a company couldn't or wouldn't do it if there was a reason. Under this system you just have an encryption channel that will give you X total GB of data (half duplex) transfer before it has to be refreshed. This would give you teh capacity to use this to secure a company intranet or something, but it wouldn't be unreasonab;e to get a years worth of small messages that require the utmost secearcy to be transfered this way.
Re:One Time Pad != Encryption
Score:
by
plcurechax
( 247883 )
writes:
So the question is, why don't you use the secure medium in the first place?
Because I only get to see my brother once a year in Cuba. And he has a problem carrying back CD-Rs of random pad material through customs.
verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well),
Passive evesdropping (aka wiretapping) does not interefere while verifing a public key fingerprint. So you can verify fingerprints of a public key in a public place.
OTP has other problems, beyond the typical key distribution problem. If a non-random source is used for generating the key material, or if the key pad is accidential reused, then trouble stikes, like it did with
Venoma
[nsa.gov].
OTP also lacks message integerity, so if an attack could cut and paste blocks of encrypted ciphertext, Bob would not be able to detect the altered message if the decrypted text make sense (deposit $1000 to account #1233335632 rather than the modified message of deposit $4950292.95 to #1233335632)
encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).
Now what methods are you referring to here?
Elliptic Curve Cryptography
[certicom.ca] normally is used as a faster version of the
Discrete Logarithm Problem
[rsasecurity.com] (DLP) where it is faster and easier to Exponentiate (x^y) than it is to calculate its discrete logarithm (x such that g^x = h) which is the inverse operation and is much harder to calculate.
So I would be interested in this method of using elliptic integrals.
Quantum computing changes the games of cryptography, but it does
not
end the struggle of cryptographer vs. cryptanalysis. AES when used with a 256-bit key is expected to withstand a bruce force key search using quantum computing within the near future (less than 10-20 years). Of course quantum computing being a young field there is a chance that a radical discovery may ruin our present best estimates for future capabilitities.
Re:One Time Pad != Encryption
Score:
by
shimmin
( 469139 )
writes:
If you're just sending text, then there's really no risk of running out of pad. Fill a zip disk with noise. Give it to the other party. Now, how long will it be before you've exchanged 100M of correspondence?
1 personal meeting yields a lifetime of secure communication.
Re:One Time Pad != Encryption
Score:
, Insightful)
by
ssimpson
( 133662 )
writes:
The definitive text on cryptography,
The Handbook of Applied Cryptography
[uwaterloo.ca], defines the OTP as a type of encryption...I know this is Slashdot but I don't think your arbitrary definitions help here.
Sending a CD worth of random data via a secure channel in advance and then sending an encrypted message with the knowledge that it will be unbreakable is sometimes worth prior thought. Sure, it may not be usefull for the masses who require this kind of security or don't know their going to communicate in the future but to claim that this cipher "isn't encryption" is bull.
As Bruce says, relax...for now.
Score:
by
mbourgon
( 186257 )
writes:
My fear is that we could see optimizations of the XSL attack breaking AES with a 2^80-ish complexity, in which case things starts to get dicey about
ten years from now.
(emphasis added by me)
So, ten years
or more
. Heck, at that point, shouldn't quantum computers be breaking this stuff anyhow?
The XSL attack
Score:
, Interesting)
by
jlcooke
( 50413 )
writes:
The XSL attack is highly subjective.
All you "so is GPG broken?" put your pants back on.
Summary of attack:
XSL stands for three of the basic operations in Rijndael and Serpent. The reason why this attack works is because the substitution layer of Rijndael/AES and Serpent can be expressed very neatly as the same domain as the Linear layers.
Now when I say 'neatly' I mean 'it would be possible' not no one's shown us this monster set of equations relatnig the (128+128/192/256) bit inputs to the 128 bit outputs. The Rijndael/AES and Serpent ciphers may be what we call "over defined".
Think back to high school when you have N liniearly independent linear equations and N-1 unknowns. You had an infinate number of posibilities for solutions. If you had N eqns and N unkn's you had 1 sol'n. If you had N eqns and N+1 unkn's you were in a funny place.
The authors suggest Rijndael/AES Serpent is in the latter catagory of the differential nature (and not the linear nature you learned in high school).
So what does this mean? The possibility HAS NOT BE EXCLUDED that this attack is possible. It really proves demostrates nothing that it's at all possible. Which is best anyone's been able to do in the past 6 years.
JLC
See sci.crypt thread:
rypt
[google.ca]
Bruce Schneier on the subject
Score:
by
prostoalex
( 308614 )
writes:
Here's
Bruce Schneier on the subject
[politechbot.com]:
Some of the confusion stems from different definitions of "attack." To a
cryptographer, an attack is anything that breaks the algorithm faster than
brute force, even if it is completely impractical. To an engineer, an
attack is something that is practical, or at least might be practical in a
few years. An attack that breaks AES to a cryptographer might not to an
engineer. The rest of the confusion stems from not being sure the attack
actually works.
Some corrections to the article
Score:
by
swillden
( 191260 )
writes:
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.
Re:Some corrections to the article
Score:
by
Effugas
( 2378 )
writes:
Asymmetric algorithms, by nature of their highly condensed problems(factor this number) are both vulnerable in polynomial time to an arbitrarily precise quantum computer, as Shor explains:
"Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"
le/29317
Given that all modern crypto protocols use some variant of asymmetric crypto to transmit their symmetric key, a break in the asymmetry eventually breaks the symmetry too.
That being said, I'm personally suspicious of quantum computing. Naive students learning about lossless compression algorithms inevitably believe they can apply the same algorithm multiple times, each time shrinking the data further and further. This actually works for some algorithms, for one or two runs. Eventually Shannon takes hold; the system refuses to compress below the level of entropy in the data (indeed, it starts to expand).
I suspect there's an analogous limit on the quantum scale, past which entropic capacity will prevent computation at high qubit levels. I could be wrong, and I'll be suitably impressed when the hardware shows up on my doorstep. But computationally relevant quantum logic hasn't been shown yet, and we shouldn't act like "it's only a matter of time".
It'll be something to be excited about if quantum computing proves feasible. I'd hate to see that achievement spoiled by "We've known it was possible for a decade."
Of course, I'm just being mildly cranky. I ain't a fan of quantum crypto either -- entanglement and crypto don't work too well in the same conceptual universe. A little skepticism is useful
:-)
Yours Truly,
Dan Kaminsky
DoxPara Research
Re:Some corrections to the article
Score:
by
swillden
( 191260 )
writes:
Given that all modern crypto protocols use some variant of asymmetric crypto to transmit their symmetric key, a break in the asymmetry eventually breaks the symmetry too.
Actually, this is not always true.
It is true of most protocols used on the net, but other areas of secure computing rely pretty much exclusively on symmetric algorithms. For example, my work is primarily in security for systems involving smart cards. Given that:
Distributing secure tokens like smart cards solves the key distibution problem;
Symmetric algorithms are more vulnerable to certain non-cryptographic attacks when performed by small devices;
The most common asymmetric algorithms have key sizes and processing times which strain the resources of small devices; and
The asymmetric algorithms with small key sizes are often encumbered by patents...
...symmetric crypto makes more sense. Similarly, the banking system relies almost entirely on 3DES, more because of inertia than any security reasoning but, still, PK is rare.
In many, many real-world security scenarios, key distribution can be solved without PK, and in many cases the result is simpler and therefore more secure (complexity being the enemy of security).
I suspect there's an analogous limit on the quantum scale, past which entropic capacity will prevent computation at high qubit levels.
I'm not qualified to comment, but the more far-out claims for QC, even from those who understand it, seem much too good to be true.
Of course, I'm just being mildly cranky. I ain't a fan of quantum crypto either -- entanglement and crypto don't work too well in the same conceptual universe. A little skepticism is useful
:-)
Certainly is
:-)
I see quantum crypto as an interesting idea, but in practice I don't think it offers very much over what can be accomplished with standard cryptography. Sure, it's nicer to have a theory that allows you to say "I *know* no one is tapping this line", but unless your attacker is a major world government, a good symmetric stream cipher with a decent automatic rekeying system, plus some strong message authentication codes, is perfectly adequate. Actually, it's almost certainly adequate even if your attacker *is* a major world governnment.
Where my cryptogram?
Score:
by
Leto2
( 113578 )
writes:
on Monday September 16, 2002 @11:27AM (
#4266019
Homepage
If you're wondering why you didn't receive your Cryptogram this month, look in your spamfolder:
SPAM: -------------------- Start SpamAssassin results ----------------------
SPAM: This mail is probably spam. The original message has been altered
SPAM: so you can recognise or block similar unwanted mail in future.
SPAM: See http://spamassassin.org/tag/ for more details.
SPAM:
SPAM: Content analysis details: (5.6 hits, 5 required)
SPAM: DOUBLE_CAPSWORD (1.1 points) BODY: A word in all caps repeated on the line
SPAM: PORN_10 (0.6 points) BODY: Uses words and phrases which indicate porn (10)
SPAM: ONE_HUNDRED_PC_FREE (3.4 points) BODY: No such thing as a free lunch (2)
SPAM: PORN_3 (0.5 points) Uses words and phrases which indicate porn (3)
SPAM:
SPAM: -------------------- End of SpamAssassin results ---------------------
Share
quantum computing & one time pads
Score:
, Informative)
by
David Jao
( 2759 )
writes:
djao@dominia.org
on Monday September 16, 2002 @11:41AM (
#4266112
Homepage
For a professional mathematician, reading all the uninformed opining here on quantum computing and one time pads is, frankly, painful on the eyes.
I'm a Ph.D student at Harvard. I've done cryptography research in the past. So listen up people.
Quantum computing does not destroy cryptography as we know it.
It is important to realize exactly what quantum computing does and does not do. For symmetric ciphers, quantum computers reduce the cost of brute force search by a square root. So AES goes down from a 2^256 cipher to a 2^128 cipher. But 2^128 is still quite safe. And even if AES were to fall, it would not be an insurmountable problem to design something better.
As for public key cryptography,
most but not all
public key cryptosystems are completely broken by quantum computers. Luckily we still have some public key cryptosystems that have not yet been broken using quantum algorithms. Elliptic curve discrete log is one such example.
One time pads are not the answer.
Yes the security of one time pads has been proven but this proof relies on a stronger-than-you-think collection of assumptions that is almost never realized in real life. One time pads are very useful in certain situations but completely unsuitable for cryptography as most people use it.
Share
Some Clarifications
Score:
, Informative)
by
TheRealFoxFire
( 523782 )
writes:
on Monday September 16, 2002 @11:45AM (
#4266131
I've seen a lot of mis-statements by various
/.ers that I'd like to clarify:
- ElGamal is not an elliptic curve algorithm. Its a classical public key encryption system based on the discrete logarithm problem. Most DL problems can be refactored as elliptic curve problems though, so perhaps the poster was referring to a possible EC ElGamal. At any rate, I'm pretty sure GPG uses classical ElGamal.
- Symmetric ciphers are rarely broken by raw computational power (brute force). In fact, algorithms above about 80 bits are impossible to break by brute force due to the laws of physics.
- Quantum Cryptography today involves means of transmitting data at very low bitrates over a channel in which eavesdropping is impossible. QC is pretty much only useful for exchanging keys for symmetric algorihms (like AES, Twofish) securely, as the data rate is to slow to be practical for anything else.
- Assymetric Cryptography (public key) is based on several hard problems. The two that are used widely today:
* The prime factoring problem (RSA)
* The Discrete Logarithm problem (DSA, ElGamal)
One will become widely available soon:
* The elliptic curve problem
- Yes, OTP is still perfectly secure, but its still perfectly useless, as w/ OTP you just shift the security to two other areas; truely random pad generation, and secure distribution of the pads.
Share
Not exactly...
Score:
by
autopr0n
( 534291 )
writes:
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.
Rijndael variant which should foil this attack
Score:
by
Kiwi
( 5214 )
writes:
The reason why the kinds of attacks which convert Rijndael in to a complex system of equations look risky for Rijndael is because Rijndael has an S-box which is very easy to describe algebraciaclly. The solution is to replace Rijndael's S-box with another S-box.
In fact, the Rijndael designers were considering changing Rijndael's S-box during the AES process. NIST, however, for not entirely known reasons, did not allow the Rijndael designers to do this.
Now, as it turns out, the Rijndael designers have designed some other ciphers after Rijndael. These ciphers have different S-Boxes. In fact, the Rijndael designers revised ("tweaked" as they call it) each cipher to have a representation which is easy to implement in hardware; most of the die space used when implementing Rijndael on an ASIC is implementing the S-box.
The ciphers in question are
Whirlpool
[terra.com.br] and
Anubis
[terra.com.br] (Anubis uses an involutional S-box which might possibly make it weaker). In fact,
my software project
[maradns.org] does not use Rijndael proper as a psudo-random-number-generator; it uses a Rijndael variant with the "tweaked" Whirlpool S-box.
- Sam
P.S. I should also mention
Khazad
[terra.com.br], named after the bridge Gandalf fights balrog at, which uses Anubis' S-box.
Re:I'm no mathematician,
Score:
by
sydneyfong
( 410107 )
writes:
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.
Re:I'm no mathematician,
Score:
by
blancolioni
( 147353 )
writes:
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.
Factorisation of large primes is easy
Score:
, Funny)
by
Anonymous Coward
writes:
on Monday September 16, 2002 @09:28AM (
#4265145
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:
11196101758632245023844192896470191898640653514
65 3312226061172388866411883192711465357531654742487
6705499231816716709596104312851026148204520267693
4743164426897859795946706446495251525120838802455
0457281147705641545578609788550063865724021006158
0855981583667294584667338232052098467631115139588
519279703
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
65 3312226061172388866411883192711465357531654742487
6705499231816716709596104312851026148204520267693
4743164426897859795946706446495251525120838802455
0457281147705641545578609788550063865724021006158
0855981583667294584667338232052098467631115139588
519279703 * 1 = 1119610175863224502384419289647019189864065351466
3312226061172388866411883192711465357531654742487
6705499231816716709596104312851026148204520267693
4743164426897859795946706446495251525120838802455
0457281147705641545578609788550063865724021006158
0855981583667294584667338232052098467631115139588
519279703
Parent
Share
Definition of "Broken"
Score:
, Informative)
by
therealmoose
( 558253 )
writes:
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).
Re:I'm no mathematician,
Score:
by
iabervon
( 1971 )
writes:
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.
... but crypto is mathematical
Score:
by
billstewart
( 78916 )
writes:
No, it's not just brute force, and you'll have to think mathematically, at least real briefly, to get the concept. It's easy to build cryptosystems that are exponentially hard to crack - adding 1 bit to the key length doubles the effort required to crack it. If you have a 100-bit key, then adding 1 bit makes your job 1% harder (or more commonly 2% or sometimes a bit more) and makes the cracker's job 100% harder. Adding 10 bits makes your job 10-20% harder, and makes the cracker's job 1024 times harder. Adding 100 bits makes your job 2-4 times harder, and makes the cracker's job ~10**32 times harder. If the cracker's computer still fits on the planet, you can add a few percent to your workload, and the cracker has to buy another planet for his computer. Repeat as often as needed.
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.
Re:Maybe?
Score:
, Informative)
by
Noryungi
( 70322 )
writes:
Since when has any crypto been considered even remotely permanently unbreakable?
Since the
one-time pad
[std.com], 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.
Re:Maybe?
Score:
, Informative)
by
jonatha
( 204526 )
writes:
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.
Re:Maybe?
Score:
, Informative)
by
Dwonis
( 52652 )
writes:
DES is symmetric, and I'm pretty sure AES (Rijindael) and Serpent are, as well.
Re:Maybe?
Score:
, Interesting)
by
dfay
( 75405 )
writes:
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).
Re:Maybe?
Score:
by
swillden
( 191260 )
writes:
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.
All of the mentioned algorithms are symmetric.
Symmetry/asymmetry has nothing whatsoever to do with "susceptibility to cracking methods". It's about whether the same key is used for both enciphering and deciphering (symmetric) or whether two different keys are used (asymmetric).
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.
Re:Maybe?
Score:
by
autocracy
( 192714 )
writes:
It's all over the comments for his article, but I have to throw it in - the only widely agreed upon method of encryption that is "unbreakable" is the one-time pad. Do a search if you don't understand it. The concept is really fairly easy and widely documented.
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
:)
Re:Quantum cryptography
Score:
by
kasperd
( 592156 )
writes:
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.
Re:Quantum cryptography
Score:
by
kasperd
( 592156 )
writes:
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.
Re:This was completely predicable because...
Score:
, Informative)
by
mh_cryptonomicon
( 608940 )
writes:
on Monday September 16, 2002 @11:25AM (
#4266007
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?
Parent
Share
Re:Sounds like sour grapes...
Score:
, Insightful)
by
epine
( 68316 )
writes:
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.
Re:Well... If AES isn't sufficient...
Score:
by
Jugalator
( 259273 )
writes:
LOL
I suppose some of you *cough*the moderators*cough* didn't get it?
:)
Related Links
Top of the:
day
week
month
243
comments
'USB-A Isn't Going Anywhere, So Stop Removing the Port'
209
comments
New Book Argues Hybrid Schedules 'Don't Work', Return-to-Office Brings Motivation and Learning
200
comments
'A Black Hole': America's New Graduates Discover a Dismal Job Market
187
comments
Toxic Workplaces Are Worsening: 80% of U.S. Workers Say Their Job Hurts Mental Health
166
comments
WSJ: Tech-Industry Workers Now 'Miserable', Fearing Layoffs, Working Longer Hours
next
Red Hat Explains Stance on KDE/Gnome Desktop Changes
570
comments
previous
Big trouble In The World Of "Big Physics"
39
comments
Slashdot Top Deals
To iterate is human, to recurse, divine.
-- Robert Heller
Close
Working...